\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}}
\newcommand{\mis}[1]{\mintinline{sql}{#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{stackengine}
\usepackage[margin=1cm,bottom=1.5cm]{geometry}
\begin{document}
\fbox{\textsc{25NSIJ1G11}}


\bigskip

\textbf{Exercice 1} (6 points)

\medskip

\textit{Cet exercice porte sur les graphes et la programmation orientée objet.}

\medskip

\textbf{Partie A}

\begin{enumerate}
\item Le code \mip{balise12 = Balise(12, ['vert', 'noir'])} permet d'instancier la balise 12. 

\item \mip{balise9.voisines = [balise8, balise9, balise12]} permet de compléter l'implémentation du graphe.

\item Le résultat est \mip{[2, 5, 6]}. La méthode 1 renvoie les numéros des balises voisines de la balie considérée.

\item Le résultat est \mip{['noir', 'vert']}. La méthode 2 permet d'enlever une couleur à une balise, tandis que la méthode 3 permet d'ajouter une couleur à la balise. 

\item On complète les lignes 6 à 9 de la fonction \mip{itineraire}. 

\begin{minted}[linenos,firstnumber=6]{python}
    while balise.num_balise != balise_fin.num_balise :
        for b in balise.voisines :
            if (couleur in b.couleurs_balise) and (b not in chemin):
                balise = b
\end{minted}

\textit{Remarquons que ce code est incorrect dans le cas où il y a une bifurcation, c'est-à-dire lorsque plusieurs balises peuvent compléter un chemin, car alors toutes ces balises seront appendues au chemin, même si seule la dernière servira à continuer le chemin.}

\item Le résultat du parcours en profondeur est 1, 2, 4, 5, 10, 7, 6, 3, 11, 9, 8, 12.


\end{enumerate}


\medskip


\textbf{Partie B}

\begin{enumerate}[resume]
\item La ligne 33 devient \mip{balise4.voisines = [(balise2, 13), (balise5, 21), (balise6, 15)]}.

\item Le résultat est \mip{balise5}. La fonction \mip{mystere} renvoie la balise la plus proche de la balise passée en paramètre, parmi les balises dont l'attribut \mip{visitee} est \mip{False}.
\item Le parcours glouton sera 1, 2, 4, 6, 11, 9, 12 (de durée totale $5+13+15+8+16+4=61$ minutes).
\item On complète la fonction \mip{itineraire_trail}.

\begin{minted}[linenos,firstnumber=1]{python}


def itineraire_trail(balise_debut, balise_fin):
    balise_debut.visitee = True
    balise = balise_debut
    chemin= [balise]
    while balise_fin not in chemin:
        prochaine = mystere(balise)
        if prochaine != None:
            prochaine.visitee = True
            balise = prochaine
            chemin.append(balise)
        else:
            return None
    return [b.num_balise for b in chemin]
\end{minted}
\item \textbf{Proposition A} L'algorithme est un algorithme glouton. 
\item Un avantage d'un algorithme glouton est qu'il a en général une complexité raisonnable et donne une solution rapidement, par contre un algorithme glouton n'est pas forcément optimal.
\end{enumerate}





\bigskip

\textbf{Exercice 2} (6 points)


\medskip

\textit{Cet exercice porte sur l’algorithmique, la récursivité et les files.}



\begin{enumerate}
\item Après l'instruction \mip{v = plateau[1][2]}, la variable \mip{v} vaut \mip{6}. 

\item On complète le programme.


\begin{minted}{python}
def plateau_init(n, m, cartes):
    shuffle(cartes)
    plateau = []
    for i in range(n):
        plateau.append([cartes[i+j*n] for j in range(m)])
    return plateau
\end{minted}

\item On complète la fonction.


\begin{minted}{python}
def carte_voisines(n, m, i, j):
    voisines = []
    for i2 in range(i-1, i+2):
        for j2 in range(j-1, j+2):
            if (i2, j2) != (i,j) and i2 in range(n) and j2 in range(m):
                voisines.append((i2, j2))
    return voisines
\end{minted}

\item La valeur de \mip{e1} est $9+8+6+7=30$, \mip{e2} n'a pas de valeur car la chaîne n'existe pas, les cartes \mip{(1, 2)} et \mip{(2, 0)} ne sont pas voisines, \mip{e2} n'a pas de valeur car la chaîne n'existe pas, la carte \mip{(1, 4)} n'existe pas.  


%e1 : 9+8+6+7=30
%e2 : nope
%e3 : nope
%  6  7  11  6
%  8 14   6  7
% 12  9   8  5


\item On écrit la fonction demandée.


\begin{minted}{python}
def chaine_evalue(plateau, chaine):
    n, m = len(plateau), len(plateau[0])
    position=chaine[0]
    if position[0] in range(n) and position[1] in range(m):
        valeur = plateau[position[0]][position[1]]
    else:
        return None
    for k in range(1, len(chaine)):
        if chaine[k] in cartes_voisines(n, m, position[0], position[1]):
            position = chaine[k]
            valeur = valeur + plateau[position[0]][position[1]]
        else:
            return None
    return valeur
\end{minted}

\item Avec un parcours en largeur, on va examiner  les chaînes par longueur croissante, ce qui permettra d'arrêter la recherche dès qu'on aura trouvée une solution car on saura que cette solution est optimale.

\item On complète les lignes l3, l8, l10 et l15.


\begin{minted}[linenos,firstnumber=3]{python}
    a_visiter = file_init()
\end{minted}

\begin{minted}[linenos,firstnumber=8]{python}
    while not file_est_vide(a_visiter)
\end{minted}

\begin{minted}[linenos,firstnumber=10]{python}
        if chaine_evalue(plateau, chemin) == cible:
\end{minted}

\begin{minted}[linenos,firstnumber=15]{python}
            if (i, j) not in chemin:
\end{minted}

\item Pour accumuler toutes les solutions trouvées, on peut utiliser une variable \mip{solutions} de type \mip{list}, qu'on initialise à \mip{[]} et qu'on renvoie ligne 20, et la ligne 11 devient \mip{solution.append(chemin)}.

\textit{Notons qu'on obtient ainsi toutes les solutions, pas seulement les plus courtes.}

\end{enumerate}
\bigskip

\textbf{Exercice 3} (8 points)

\medskip

\textit{Cet exercice porte sur  les types de données construits (listes et dictionnaires), sur les
arbres binaires de recherche et sur les bases de données.}

\medskip

\begin{enumerate}
\item La ligne \mip{enregistrement['latitude']} affiche la valeur \mip{38.38825}.

\item La boucle des lignes 4 et 5 extrait la date, la boucle des lignes 6 et 7 extrait l'horaire, l'appel \mip{nettoyage_datetime('2024-06-27T23:36:01.000000Z')} renvoie le couple \mip{('2024-06-27', '23:36:01')}.

\item Les appels \mip{len(frames)} et \mip{len(frames[1])} renvoient \mip{4} et \mip{5} respectivement.

\item On écrit une fonction pour détecter une éventuelle anomalie d'altitude.
\begin{minted}{python}
def detecter_anomalie(element):
    altitude = element['altitude']
    return altitude < 0 or altitude > 35000 
\end{minted}

\item On écrit la fonction demandée.
\begin{minted}{python}
def liste_num_serie(frames):
    numeros = []
    for element in frames:
        num = element['num_serie']
        if num not in numeros:
            numeros.append(num)
    return numeros
\end{minted}



\item On complète la fonction \mip{distance_totale}.
\begin{minted}{python}
def distance_totale(dep):
    total = 0
    for i in range(1, len(dep)):
        total = total + distance_haversine(dep[i-1], dep[i])
    return total
\end{minted}

\item \mip{sonde623 = Sonde(623, 38.38825, 27.09004, '2024-06-27', sonde500, sonde700)}

\item On complète l'arbre.

\begin{center}
\begin{minipage}{16cm}
\psset{unit=8mm}
\begin{pspicture}(15,8)
\rput(8,7){\ovalnode{sonde623}{\stackanchor[6pt]{sonde623}{623}}}
\rput(4,4){\ovalnode{sonde500}{\stackanchor[6pt]{sonde500}{500}}}
\rput(12,4){\ovalnode{sonde700}{\stackanchor[6pt]{sonde700}{700}}}
\rput(2,1){\ovalnode{sonde300}{\stackanchor[6pt]{sonde300}{300}}}
\rput(6,1){\ovalnode{sonde575}{\stackanchor[6pt]{sonde575}{575}}}
\rput(10,1){\ovalnode{sonde650}{\stackanchor[6pt]{sonde650}{650}}}
\rput(14,1){\ovalnode{sonde900}{\stackanchor[6pt]{sonde900}{900}}}
\ncline{sonde623}{sonde500}
\ncline{sonde623}{sonde700}
\ncline{sonde500}{sonde300}
\ncline{sonde500}{sonde575}
\ncline{sonde700}{sonde650}
\ncline{sonde700}{sonde900}
\end{pspicture}
\end{minipage}
\end{center} 

\item C'est un parcours infixe qui permet de parcourir l'ABR dans l'ordre croissant des numéros de série.

\item On complète la méthode.

\begin{minted}[linenos,firstnumber=1]{python}
    def rechercher(self, numero):
        if self.est_vide():
            return False
        if numero == self.num_serie:
            return self
        elif numero < self.num_serie:
            return self.gauche.rechercher(numero)
        else:
            return self.droit.rechercher(numero)
\end{minted}

\item La méthode \mip{rechercher} est une méthode récursive car elle s'appelle elle-même.

\item Dans la relation \mis{abonne}, l'attribut \mis{id_abonne} peut servir de clé primaire s'il est unique, c'est-à-dire si chaque ligne a un \mis{id_abonne} distinct.

\item Dans la relation \mip{infos_recuperation}, les clés \mis{num_serie} et \mip{id_abonne} sont des clés étrangères qui référencent respectivement les relations \mis{sonde} et \mis{abonne}. 

\item La requête \mis{SELECT nom, prenom FROM abonne WHERE id_abonne>20;} renvoie la table :

\begin{center}
\begin{tabular}{|c|c|}
\hline
nom&prenom\\
\hline
'Détoile'&'Diane'\\
\hline
'Girard'&'Antoine'\\
\hline
\end{tabular}
\end{center}

\item On ajoute les données demandées dans la relation \mis{info_recuperation} avec la 

requête \mis{INSERT INTO info_recuperation VALUES (14,480,24,'2024-07-10',47.230,12.244);}

\item La requête \mis{SELECT num_serie, nom, date_recup FROM info_recuperation JOIN abonne}

\mis{ON info_recuperation.id_abonne = abonne.id_abonne;} convient.

\end{enumerate}





\end{document}