\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{multirow}
\usepackage{minted}
\newcommand{\mip}[1]{\mintinline{python}{#1}}
\newcommand{\mis}[1]{\mintinline{sql}{#1}}

\usepackage{hyperref}
\usepackage{pstricks,pst-tree,pst-math,pst-eucl,pstricks-add}
\usepackage{tikz}
\usepackage[margin=1.5cm,bottom=1.5cm]{geometry}
\begin{document}
\fbox{\textsc{25NSIPE4}}


\bigskip

\textbf{Exercice 1} (6 points)

\medskip

\textit{Cet exercice porte sur les bases de données relationnelles et les requêtes SQL.}

\medskip

\begin{enumerate}
\item L’attribut \texttt{nom} n'est pas unique donc ne peut pas être choisi comme clé primaire, p.ex Lisa Benard et Emma Benard partagent le même nom.
\item La requête \texttt{SELECT nom, prenom FROM joueurs WHERE genre=2;} permet d’obtenir les noms et prénoms des joueuses du
club.
\item La requête \texttt{INSERT INTO joueurs VALUES (6, "Gervais", "Nathan", 1) ;} permet d’ajouter dans la table le joueur dont le prénom
est Nathan et le nom est Gervais, en choisissant une valeur pour l’identifiant \texttt{id}
cohérente avec le reste de la base.

\item La requête \texttt{UPDATE competitions SET nom="Open de Tours" WHERE id=3 ; } permet de corriger la faute de frappe.
\item La requête \texttt{SELECT nom, annee FROM competitions ORDER BY annee ;} permet d’obtenir la liste des noms des tournois, ainsi que
leur année, en triant par année croissante.


\item La requête \texttt{SELECT nom, prenom FROM joueurs JOIN participe ON joueurs.id=participe.id\_joueur}

\texttt{WHERE nb\_gagnant > nb\_fautes ;} permet d’obtenir le nom et le prénom des joueurs et des
joueuses ayant obtenu un nombre de coups gagnants strictement supérieur au
nombre de fautes lors d’une compétition, la même personne pouvant apparaître
plusieurs fois si elle a rempli ces conditions lors de plusieurs compétitions.
\item La requête \texttt{SELECT joueurs.nom, prenom, competition.nom FROM joueurs JOIN participe}

\texttt{ON joueurs.id=participe.id\_joueur JOIN competitions ON participe.id\_compet=competitions.id}

\texttt{WHERE genre=2 AND annee=2023 ;} permet d’obtenir le nom, le prénom des joueuses et le
nom des compétitions auxquelles elles ont participé en 2023.
\item Pour supprimer de la table \texttt{joueurs} la joueuse Emma Benard qui ne
fait plus partie du club, il faut d'abord supprimer dans la table \texttt{participe} toutes les lignes concernant Emma, pour éviter des violations de contraintes de référence.
\item Pour insérer Agathe et ses résultats dans la base, en choisissant
pour identifiant pour la table \texttt{joueurs} la valeur 7 et pour la table
\texttt{competitions} la valeur 5, on utilise dans cet ordre les requêtes :

\texttt{INSERT INTO joueurs VALUES (7, "Turion", "Agathe", 2) ;}

\texttt{DELETE FROM participe WHERE id\_compet=5;}

\texttt{DELETE FROM competitions WHERE id=5;}

\texttt{INSERT INTO competitions VALUES (5, "Tournoi de Blois", 2024) ;}

\texttt{INSERT INTO participe VALUES (7, 5, 14, 15, 2) ;}

On a commencé par supprimer l'Open de Nantes 2021 et toutes les références qui y sont faites dans la table \texttt{participe}.

\end{enumerate}





\bigskip

\bigskip

\textbf{Exercice 2} (6 points)

\medskip

\textit{Cet exercice porte sur les réseaux, le routage, les graphes et la programmation.}


\medskip

\textbf{Partie A : Réseau et adressage}

\smallskip


\begin{enumerate}
\item Parmi les deux adresses IP suivantes : 137.254.128.200 et 137.254.128.210,
 l’adresse IP de la machine déjà connectée au sous-réseau Commerces est 137.254.128.200 à cause de la politique utilisée pour la numérotation.
\item Il n'est pas possible d’ajouter 132 machines sur le sous-réseau
Commerces, puisque le masque de sous réseau est 255.255.255.0 ce qui signifie qu'il y a 254 adresses disponibles qui vont de 137.254.128.1 à 137.254.128.254 (les adresses 137.254.128.0 et 137.254.128.255 étant l'adresse du sous-réseau lui-même et l'adresse de diffusion respectivement) ; or 207 machines sont déjà connectées, on ne peut en ajouter que 47.
\end{enumerate}
\medskip

\textbf{Partie B : Programmation d'un protocole de routage}

\smallskip
\begin{enumerate}[resume]
\item Donner la liste des routeurs par lesquels transite un message envoyé depuis
une machine du sous-réseau Navigation à destination d’une machine du sous-
réseau Commerces est R1-R3-R6-R7 par lecture des tables de routage.
\item Lorsque qu’une machine du sous-réseau
Commerces envoie des données à destination d’une machine du sous-réseau
Navigation, le début du routage est R7-R4-R6-R4 et on a une boucle infinie R7-R4-R6-R4-R6-R4-R6-R4-R6-R4-...

\item Le dictionnaire correspondant au réseau de la Figure 2 est 

\mip{{'R1': ['R2', 'R3'], 'R2': ['R1','R3','R5'], 'R3': ['R1', 'R2'], 'R5': ['R2']}}
\item Le principe d’une fonction récursive est de s'appeler elle-même.


\item On écrit une fonction
\mip{plus_court_chemin(graphe, r_depart, r_arrivee)}.

\begin{minted}{python}
def plus_court_chemin(graphe, r_depart, r_arrivee):
    chemins = liste_chemins(graphe, r_depart, r_arrivee)
    meilleur_chemin=chemins[0] # on suppose qu'il y a au moins un chemin !
    for k in range(1, len(chemins)):
        if len(chemins[k])<len(meilleur_chemin):
            meilleur_chemin = chemins[k]
    return meilleur_chemin
\end{minted}

\item On complète la fonction \mip{plus_court_chemin_largeur(graphe,
r_depart, r_arrivee)}.

\begin{minted}{python}
def plus_court_chemin_largeur(graphe, r_depart, r_arrivee):
    dict_chemins = {}
    L = [r_depart]
    sommets_marques = [r_depart]
    dict_chemins[r_depart] = [r_depart]
    for r in L: # sérieusement, ne faites pas ça ; L est modifiée dans la boucle
        for s_r in graphe[r]:
            if not s_r in sommets_marques:
                sommets_marques.append(s_r)
                dict_chemins[s_r] = dict_chemins[r] + [s_r]
                if s_r == r_arrivee :
                    return dict_chemins[s_r]
                L.append(s_r)
\end{minted}


\item On écrit une fonction \mip{table_routage(graphe, routeur)}.

\begin{minted}{python}
def table_routage(graphe, routeur):
    table = dict()
    for destination in graphe:
        if destination != routeur:
            route = plus_court_chemin_largeur(graphe, routeur, destination)
            table[destination] = route[1]
    return table
\end{minted}


\end{enumerate}


\bigskip
\textbf{Partie C : Utilisation du protocole OSPF}

\smallskip



\begin{enumerate}[resume]
\item Le coût correspondant à la liaison Ethernet est $\dfrac{10^9}{10 \times 10^6}=100$, le coût correspondant à la liaison Fast Ethernet est $\dfrac{10^9}{100 \times 10^6}=10$, le coût correspondant à la liaison Fibre est $\dfrac{10^9}{500 \times 10^6}=2$.
\item Un message envoyé depuis le
routeur R1 à destination du routeur R7, en respectant le protocole OSPF, suit la route R1-R3-R2-R5-R6-R4-R7.

\newpage

\item On complète la table de routage du routeur R2 en respectant
le protocole OSPF ; on a indiqué les coûts.
\end{enumerate}

\vspace{-5mm}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
\multicolumn{3}{|c|}{Table de routage de R2}\\
\hline
Destination & Suivant & Coût\\
\hline
R1&R3& 4\\
\hline
R3&R3&2\\
\hline
R4&R5&14\\
\hline
R5&R5&10\\
\hline
R6&R5&12\\
\hline
R7&R5&16\\
\hline
\end{tabular}
\end{center}






\textbf{Exercice 3} (8 points)

\medskip

\textit{Cet exercice porte sur l’algorithmique des tableaux, la gestion de bugs, les listes, les
piles et la programmation orientée objet.}

\medskip



\textbf{Partie A}

\smallskip

\begin{enumerate}
\item Le résultat que doit renvoyer \mip{tri_dictatorial([31, 45, 41, 28, 37, 108, 127, 2, 124, 421])}
est \mip{[31, 45, 108, 127, 421]}.
\item Le tri dictatorial ne conserve pas l'ensemble des valeurs de la liste passée en paramètre donc il n’est pas un algorithme de tri.

\item On déroule l’appel \mip{tri_dictatorial([8, 2, 9, 6, 12])} dans un tableau.


\begin{center}
\begin{tabular}{|c|c|c|c|c|l|}
\hline
étape&\mip{i}&\mip{serie[i]}&\mip{serie[i-1]}&\mip{serie[i]>=serie[i-1]}& \mip{serie_triee}\\
\hline
0&&&&&\mip{[8]}\\
\hline
1&1&\mip{2}&\mip{8}&\mip{False}&\mip{[8]}\\
\hline
2&2&\mip{9}&\mip{2}&\mip{True}&\mip{[8, 9]}\\
\hline
3&3&\mip{6}&\mip{9}&\mip{False}&\mip{[8, 9]}\\
\hline
4&4&\mip{12}&\mip{6}&\mip{True}&\mip{[8, 9, 12]}\\
\hline
\end{tabular}
\end{center}

La valeur renvoyée est \mip{[8, 9, 12]}.


\item L’erreur obtenue est une erreur d'index puisqu'on essaie d'accéder au premier élément d'une liste vide. On peut proposer cette modification, qui respecte davantage la description de l'algorithme :

\medskip
\begin{minipage}{12cm}
\begin{minted}[linenos]{python}
def tri_dictatorial(serie):
    if serie == []:
        return []
    serie_triee = [serie[0]]
    for i in range(1, len(serie)):
        if serie[i] >= serie[i - 1]:
            serie_triee.append(serie[i])
    return serie_triee
\end{minted}
\end{minipage}
\medskip

\item Des tests utilisant des cas d'usage ne peuvent pas être exhaustifs, il se peut qu'un cas d'usage non testé provoque une erreur, même si en général on essaie de choisir suffisamment de cas d'usage pour avoir une bonne couverture du code.
\item La cause du problème est la comparaison \mip{serie[i] >= serie[i - 1]} qui devrait 

être \mip{serie[i] >= serie_triee[-1]}.
\end{enumerate}

\bigskip



\textbf{Partie B}


\medskip

\begin{enumerate}[resume]
\item On construit les trois maillons \mip{m1}, \mip{m0} et \mip{m8}
et la liste chaînée représentés ci-dessus avec les instructions suivantes.

\begin{minted}{python}
m8 = Maillon(8, None)
m0 = Maillon(0, m8)
m1 = Maillon (1, m0)
ma_liste = Liste(m1)
\end{minted}

\item On indique ce que renvoie chacune des instructions.

\begin{minted}{python}
>>> m1.valeur == 1
True
>>> m1.suivant.valeur == 8
False
>>> m1.suivant.suivant == None
False
>>> m1.suivant.suivant.suivant == None
True
\end{minted}

\item L'instruction \mip{ma_liste.tete.suivant = m8} convient, mais le résultat \textbf{n'est pas} une liste chaînée. 



\item On complète la fonction \mip{tri_dictatorial_chaine}.

\begin{minted}{python}
def tri_dictatorial_chaine(chaine):
    maillon = chaine.tete
    while maillon.suivant is not None :
        if maillon.valeur <= maillon.suivant.valeur: 
            maillon = maillon.suivant
        else:
            maillon.suivant = maillon.suivant.suivant
\end{minted}

\end{enumerate}

\bigskip

\textbf{Partie C}

\medskip



\begin{enumerate}[resume]
\item Une pile est une structure linéaire LIFO last-in first-out, dans laquelle on peut empiler un élément à la fois, et dépiler le dernier élément empilé si la pile n'est pas vide.
\item On a remis les lignes de pseudo-code dans l’ordre en respectant les indentation.


\begin{itemize}
    \item[$\star$] si \mip{p} n’est pas vide :
    \begin{itemize}
        \item[$\bullet$] on crée une pile intermédiaire \mip{p2} vide ;
        \item[$\bullet$] on dépile \mip{p}, on stocke l’élément obtenu dans la variable \mip{dernier_conservé} et on l’empile dans \mip{p2} ;
        \item[$\bullet$] tant que \mip{p} n’est pas vide :
        \begin{itemize}
            \item[$+$] si \mip{candidat} est supérieure ou égal à
\mip{dernier_conservé} :
            \begin{itemize}
                 \item[$-$] \mip{dernier_conservé} prend la valeur de \mip{candidat} et on l’empile dans \mip{p2}
            \end{itemize}
        \end{itemize}
        \item[$\bullet$] tant que \mip{p2} n’est pas vide :
        \begin{itemize}
            \item[$+$] on dépile \mip{p2} et on empile l’élément obtenu dans \mip{p} ;
        \end{itemize}
    \end{itemize}
\end{itemize}



\item On écrit en Python la fonction \mip{tri_dictatorial_pile} qui prend en paramètre \mip{p} une instance de \mip{Pile} et modifie cette pile afin qu’elle ne conserve que des
éléments triés selon le pseudo-tri dictatorial.

\begin{minted}{python}
def tri_dictatorial_pile(p):
    if not p.est_vide():
        p2 = Pile
        dernier_conserve = p.depiler()
        p2.empiler(dernier_conserve)
        while not p.est_vide():
            candidat = p.depiler()
            if candidat>=dernier_conserve:
                dernier_conserve=candidat
                p2.empile(candidat)
        while not p2.est_vide():
            p.empile(p2.depile())
\end{minted}

\end{enumerate}

\end{document}



