\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{minted}
\newcommand{\mip}[1]{\mintinline{python}{#1}}
\usepackage{hyperref}
\usepackage{pstricks,pst-plot,pst-3dplot,pst-grad,pst-tree,pst-math,pst-eucl}
\usepackage{pst-plot,pst-tree,pst-eucl,pst-math,pstricks-add}
\usepackage[margin=1cm,bottom=1.5cm]{geometry}
\begin{document}
\fbox{\textsc{25NSIJ1AN1}}


\bigskip

\textbf{Exercice 1} (6 points)

\medskip

\textit{Cet exercice porte sur les arbres binaires, la récursivité et la programmation orientée objet.}

\begin{enumerate}
\item Le végétal observé est un Sorbier.
\item Les renseignements fournis ne permettent pas de conclure.
\item On écrit le code demandé, en commençant par les feuilles et en terminant par la racine.

\begin{minted}{python}
feuille1=Feuille_resultat([])
feuille2=Feuille_resultat(["Sorbier"])
feuille3=Feuille_resultat(["Robinier","Noyer"])
noeud1=Noeud("Bord denté ?",feuille2,feuille3)
feuille4=Feuille_resultat([])
noeud2=Noeud("Alternées ?",noeud1,feuille4)
arbre_2=Noeud("Simples ?",feuille1,noeud2)
\end{minted}

\end{enumerate}

On écrit les méthodes demandées.

\begin{enumerate}[resume]

\item \begin{minted}{python}
class Noeud:
    ...
    def est_resultat(self):
        return False
\end{minted}

\item \begin{minted}{python}    
class Feuille_resultat:
    ...
    def est_resultat(self):
        return True       

\end{minted}


\item \begin{minted}{python}
class Feuille_resultat:
    ...
    def nb_vegetaux(self):
        return len(self.vegetaux)
\end{minted}

\item \begin{minted}{python}  
class Noeud:      
    ...
    def nb_vegetaux(self):
        return self.sioui.nb_vegetaux()+self.sinon.nb_vegetaux()   

\end{minted}

\item \begin{minted}{python}
class Feuille_resultat:
    ...
    def liste_questions(self):
        return []
\end{minted}

\item \begin{minted}{python}  
class Noeud:      
    ...
    def liste_questions(self):
        return [self.question]+self.sioui.liste_questions()+self.sinon.liste_questions()   

\end{minted}


\item On écrit une fonction \mip{est_bien_renseigne}.

\begin{minted}{python}
def est_bien_renseigne(dico_vegetal,arbre):
    questions=arbre.liste_questions()
    for q in questions:
        if q not in dico_vegetal:
            return False
    return True
\end{minted}

\newpage

\item On écrit une fonction \mip{identifier_vegetaux}.
\begin{minted}{python}  
def identifier_vegetaux(dico_vegetal,arbre):
    while not arbre.est_resultat():
        if dico_vegetal[arbre.question]:
            arbre=arbre.sioui
        else:
            arbre=arbre.sinon
    return arbre.vegetaux
\end{minted}

\end{enumerate}




\bigskip

\textbf{Exercice 2} (6 points)


\medskip

\textit{Cet exercice porte sur la programmation orientée objet, la récursivité et les algorithmes
gloutons.}



\begin{enumerate}
\item On écrit la méthode \mip{passer_transit} de la classe \mip{Colis}.

\begin{minted}{python}
class Colis:
    ...
    def passer_transit(self):
        self.etat='transit'
\end{minted}

\item On modifie la fonction \mip{ajouter_colis} afin qu'elle ne rajoute pas les colis de plus de 25 kg, avec le répugnant effet de bord consistant à afficher un message d'erreur plutôt que de lever une exception (oui, c'est un jugement de valeur).

\begin{minted}[linenos]{python}
def ajouter_colis(liste,colis):
    if colis.poids<=25:
        liste.append(colis)
    else:
        print("Dépassement du poids maximal autorisé") # beurk
\end{minted}

\item \mip{nb_colis=len} est adapté. On peut imaginer que la réponse attendue est plutôt celle présentée ci-dessous.

\begin{minted}{python}
def nb_colis(liste):
    return len(liste)
\end{minted}

\item  On a complété la fonction \mip{poids_total}.

\begin{minted}[linenos]{python}
def poids_total(liste):
    total=0
    for c in liste:
        total=total+c.poids
    return total
\end{minted}

\item On écrit une fonction \mip{liste_colis_etat}.

\begin{minipage}[t]{4cm}
\begin{minted}{python}
def liste_colis_etat(liste,statut):
    res=[]
    for c in liste:
        if c.etat==statut:
            res.append(c)
    return res
\end{minted}
\end{minipage}

\smallskip

\textit{ou bien} 

\begin{minipage}[t]{9cm}\begin{minted}{python}
def liste_colis_etat(liste,statut):
    return [c for c in liste if c.etat==statut]
\end{minted}
\end{minipage}


\item Le tri utilisé ici est un tri sélection, de quadratique dans le pire des cas (et quadratique dans le meilleur des cas : contrairement à d'autres tris, le tri sélection est toujours quadratique, le nombre d'opérations ne dépend que du nombre de données et pas de l'ordre initial des données).

\item On aurait pu utiliser un tri fusion, de complexité quasi-linéaire en $n \log(n)$, basé sur le brillant principe diviser pour régner.% (divide ut regnes comme disait Philippe Vador, père d'Alexandre "The Great" Skywalker).


\newpage

\item On a complété le code de la fonction \mip{chargement_glouton}.

\begin{minted}[linenos]{python}
def chargement_glouton(liste, rang, capacite):
    if rang == len(liste):
        return []
    elif liste[rang].poids <= capacite:
        return [liste[rang]] + chargement_glouton(liste, rang+1,capacite-liste[rang].poids)
    else:
        return chargement_glouton(liste, rang+1, capacite)
\end{minted}

\item La fonction est récursive, elle s'appelle elle-même, et pour les appels récursifs Python utilise une pile de taille finie, qui peut déborder si la profondeur de récursion est excessive.

\item On écrit une fonction itérative \mip{chargement_glouton2}.

\begin{minted}{python}
def chargement_glouton2(liste,capacite):
    colis_a_charger=[]
    for c in liste:
        if c.poids<=capacite:
            colis_a_charger.append(c)
            capacite=capacite-c.poids
    return colis_a_charger
\end{minted}



\end{enumerate}
\bigskip

\textbf{Exercice 3} (8 points)

\medskip

\textit{Cet exercice porte sur les graphes, les bases de données, les tris, les algorithmes
gloutons et la récursivité.}

\textbf{Partie A}

\begin{enumerate}
\item Le type de l'attribut \texttt{annee} de la table \texttt{enfant} est \texttt{INT}.
\item On pourrait imposer que cet attribut doive appartenir à un intervalle compatible avec le statut d'enfant, entre 0 et 18 ans d'après l'énoncé.
\item Une contrainte de référence qui s'applique à la table \texttt{enfant} est que le numéro de téléphone doit être présent dans une ligne de la table \texttt{parent}.
\item Le numéro de téléphone \texttt{tel} fera une excellente clé primaire pour la table \texttt{parent}.
\item La requête \texttt{UPDATE parent SET tel=33619782812 WHERE tel=33600782812;} lève une erreur de contrainte de référence car la clé qu'on veut modifier est référencée par la table \texttt{enfant}.

\item On complète la séquence de requêtes.

\texttt{INSERT INTO parent VALUES ('Bauges', 33619782812, 73340);}

\texttt{UPDATE enfant SET num\_parent = 33619782812 WHERE num\_parent = 33600782812;}


\texttt{DELETE FROM parent WHERE tel = 33600782812;}


\item La requête \texttt{SELECT prenom FROM enfant WHERE annee<2014 ORDER BY annee} fournit le résultat suivant, à partir de l'extrait de la table \texttt{enfant} fourni.

\begin{center}
\begin{tabular}{|c|}
\hline
prenom\\
\hline
Nakamura\\
Hawa\\
Kian\\
Adrien\\
\hline
\end{tabular}
\end{center}


\item La requête \texttt{SELECT prenom FROM enfant WHERE num\_parent=3619861122 ORDER BY prenom;} convient.

\item On utilise ici une jointure des deux tables \texttt{enfant} et \texttt{parent}.

\texttt{SELECT id, prenom FROM enfant}

\texttt{JOIN parent ON parent.tel=enfant.num\_parent}

\texttt{WHERE parent.codep=38520;}

Cette requête permet d'obtenir les identifiants et les les prénoms des enfants dont le parent habite dans une des huit villes qui partagent le code postal 38520, La Garde, Le Bourg d'Oisans, Ornon, Oulles, Saint-Christophe en Oisans, Vénosc, Villard Notre Dame, Villard Reymond.
\end{enumerate}


\newpage

\textbf{Partie B}



\begin{enumerate}[resume]
\item La relation \og les enfants ne s'entendent pas \fg{} est symétrique et peut être modélisée par un graphe non orienté.

\item On a représenté ci-dessous le graphe \mip{g2}.

\begin{center}
\begin{minipage}{10cm}
\psset{unit=8mm}
\begin{pspicture}(8,4)
\cnodeput(2,2){A}{Adrien}
\cnodeput(5,3){E}{Elisabeth}
\cnodeput(3,0){Lu}{Lucas}
\cnodeput(0,1){Le}{Léa}
\cnodeput(6,1){I}{Ian}
\cnodeput(8,2){J}{Joseph}
\ncarc{A}{E}\ncarc{A}{Le}\ncarc{E}{I}\ncarc{E}{Lu}\ncarc{I}{J}\ncarc{I}{Lu}
\end{pspicture}
\end{minipage}
\end{center}

\bigskip
\item On écrit une fonction \mip{degre}.

\begin{minted}{python}
def degre(g,s):
    return len(g[s])
\end{minted}

\item On complète les ligne demandées.

\begin{minted}[linenos,firstnumber=7]{python}
        while j>=0 and degre(g,sommets[j])<degre(g,sommet_courant):
            sommets[j+1]=sommets[j]
            j=j-1
        sommets[j+1]=sommet_courant
\end{minted}

\item Le tri insertion utilisé est quadratique en le nombre $n$ d'élément triés, dans le pire des cas (par contre il est linéaire sur un tableua déjà trié). 



\item On colorie le graphe avec trois couleurs (le triangle Elise Octavie Virgile implique que deux couleurs ne suffisent pas).


\begin{center}
\begin{minipage}{14cm}
\psset{unit=8mm}
\begin{pspicture}(14,5)
\cnodeput[fillstyle=solid,fillcolor=red](1,3){E}{Elise}
\cnodeput[fillstyle=solid,fillcolor=blue](4.5,4.5){O}{Octavie}
\cnodeput[fillstyle=solid,fillcolor=green](5,0.5){V}{Virgile}
\cnodeput[fillstyle=solid,fillcolor=red](7.5,4.5){P}{Pierre}
\cnodeput[fillstyle=solid,fillcolor=blue](11,3){R}{Raphael}
\cnodeput[fillstyle=solid,fillcolor=red](8.5,0.5){S}{Sixtine}
\ncline{E}{O}\ncline{E}{V}\ncline{O}{V}\ncline{O}{P}\ncline{P}{R}\ncline{R}{V}
\end{pspicture}
\end{minipage}
\end{center} 

\bigskip
De façon équivalente, on peut proposer le coloriage sous la forme de ce dictionnaire :

\mip{{'Elise':0,'Octavie':1,'Virgile':2,'Pierre':0,'Raphael':1,'Sixtine':0}}.
\item On complète la fonction \mip{colorer_graphe}.

\begin{minted}{python}
def colorer_graphe(g,dc):
    for s in dc:
        couleur=plus_petite_couleur_hors_voisins(g,dc,s)
        dc[s]=couleur
\end{minted}

\item On complète la fonction \mip{welsh_powell}

\begin{minted}{python}
def welsh_powell(g):
    dc={s:-1 for s in g}
    sommets=sommets_tries(g)
    for s in sommets:
        dc[s]=plus_petite_couleur_hors_voisins(g,dc,s)
    return dc
\end{minted}

\end{enumerate}





\end{document}