\addtocontents{toc}{\protect\newpage}
\devoirsynthese{Baccalauréat Blanc}{Baccalauréat blanc}

\vspace*{-1cm}
\textit{Voir nos conseils de méthode \og Spécial Bac \fg dans la partie  \og Méthodes de travail \fg en début d'ouvrage.}

\Par

La durée de l'épreuve est de 3 h 30 min. 

Le ou la candidat·e devra choisir trois des cinq exercices proposés.

Chaque exercice est noté sur 4 points.


\begin{exobb}{Programmation}{\null}{2}{70}
Trois suites numériques $(u_n)$, $(v_n)$ et $(w_n)$ sont définies par leurs premiers termes $u_0=1$, $v_0=2$, $w_0=3$ et, pour tout entier naturel $n$, par les égalités suivantes:
\[
\begin{cases}
u_{n+1} & = u_n+v_n-w_n\\
v_{n+1} & = u_n-v_n+w_n\\
w_{n+1} & = \dfrac{u_n-v_n}{w_n}
\end{cases}
\]
Nous souhaitons écrire en Python un programme permettant de calculer $u_n$, $v_n$ et $w_n$ pour un entier $n$ quelconque.

\begin{questions}
\item \textit{Approche naïve.}
\begin{questions}
\item Compléter l'algorithme suivant:
\begin{center}
\begin{minipage}{0.7\linewidth}
\begin{algorithme}{}
u $\leftarrow$ 1
v $\leftarrow$ 2
w $\leftarrow$ 3
n est un entier

Pour k variant de 1 à n:
\hspace*{2em}...
\hspace*{2em}...
\hspace*{2em}u $\leftarrow$ ...
\hspace*{2em}v $\leftarrow$ ...
\hspace*{2em}w $\leftarrow$ ...
Fin du Pour

Afficher u, v et w
\end{algorithme}
\end{minipage}
\end{center}

\Par

\item Proposer un programme Python correspondant à cet algorithme afin d'obtenir $u_7$, $v_7$ et $w_7$.

\item Montrer que la complexité de cet algorithme est en $O(n)$.
\end{questions}

\item \textit{Approche dynamique.}

\begin{questions}
\enlargethispage*{2em}
\item Proposer une approche dynamique de type \og Bottom Up \fg{} de\linebreak l'algorithme précédent. On donnera directement un programme écrit en Python qui permet d'obtenir $u_7$, $v_7$ et $w_7$.

\item Compléter le programme de type \og Top Down \fg{} suivant afin qu'il affiche $u_7$, $v_7$ et $w_7$.

\begin{listing}{}{bb-ex1-q2b.py}\end{listing}
\end{questions}
\end{questions}
\end{exobb}

%

\begin{corrigebb}
\begin{questions}
\item \textit{Approche naïve.}
\begin{questions}
\item L'algorithme complété est le suivant:
\begin{center}
\begin{minipage}{0.7\linewidth}
\begin{algorithme}{}
u $\leftarrow$ 1
v $\leftarrow$ 2
w $\leftarrow$ 3
n est un entier

Pour k variant de 1 à n:
\hspace*{2em}utemp $\leftarrow$ u
\hspace*{2em}vtemp $\leftarrow$ v
\hspace*{2em}u $\leftarrow$ u + v - w
\hspace*{2em}v $\leftarrow$ utemp - v + w
\hspace*{2em}w $\leftarrow$ (utemp - vtemp) / w
Fin du Pour

Afficher u, v et w
\end{algorithme}
\end{minipage}

\end{center}

\Par

Dans la mesure où la variable \texttt{u} est affectée d'une nouvelle valeur dans la boucle, et dans la mesure où il est nécessaire d'avoir la valeur précédente de \texttt{u} pour calculer la nouvelle valeur de \texttt{v}, il est nécessaire de stocker cette valeur précédente de \texttt{u} dans une autre variable (que nous avons ici nommée \texttt{utemp}).

Il en est de même pour \texttt{v} car il est nécessaire d'avoir la valeur précédente de \texttt{v} pour calculer la nouvelle valeur de \texttt{w}.

\item Un programme Python correspondant à cet algorithme est le\linebreak suivant:

\begin{listing}{}{bb-ex1-q1b-c.py}
\end{listing}

\Par

\item Afin de connaître la complexité de l'algorithme, il faut compter le nombre d'instructions élémentaires (affectations et opérations).

\newpage

\begin{itemize}
\item Il y a avant tout quatre affectations pour \texttt{u}, \texttt{v}, \texttt{w} et \texttt{n};
\item ensuite, pour chaque passage dans la boucle itérative, il y a :
\begin{itemize}
\item[$\to$] 1 affectation pour la variable \texttt{i};
\item[$\to$] 2 affectations pour \texttt{u}\_\texttt{tmp} et \texttt{v}\_\texttt{tmp}
\item[$\to$] 2 opérations et 1 affectation pour \texttt{u}, \texttt{v} et \texttt{w}.
\end{itemize}
Il y a donc:
\[
4 + n(1+2+3\times3)=12n+4
\]
instructions élémentaires. 

La complexité est alors affine, donc en $O(n)$.
\end{itemize}
\begin{Remarque}
dans la pratique, on n'effectue pas tous ces calculs. On se contente de dénombrer le nombre de boucles (ici, il y en a $n$) et de déceler s'il y a des imbrications (ce qui aurait pour conséquence d'élever au carré le $n$ s'il y en a une, élever au cube s'il y en a deux, etc.).

Ainsi, dans cette question, nous aurions pu simplement dire qu'il y a $n$ boucles sans imbrication, ce qui signifie que la complexité est en $O(n)$.
\end{Remarque}
\end{questions}

\item 

\begin{questions}

\item L'idée est ici de construire une liste pour chaque suite.

Un programme possible est alors le suivant:

\begin{listing}{}{bb-ex1-q2a-c.py}\end{listing}


\item Le programme de type %ERR NON DETECTEE \og Bottom Up \fg{} 
\og Top Down \fg{} 
complété est le suivant:

\nathanlive{progmargin}{}%bb-ex1-q2b-c.py
\begin{listing}{}{bb-ex1-q2b-c-1.txt}\end{listing}
\Par
\begin{center}
\textit{(suite du programme page ci-contre)}
\end{center}
\newpage
\begin{listing}{}{bb-ex1-q2b-c-2.txt}\end{listing}
\end{questions}
\end{questions}
\end{corrigebb}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exobb}{Base de données}{\null}{2}{70}
L'entreprise MQWZ, dont le début de l'activité est enregistré au 2 janvier 2020, demande à ses salariés une présence du lundi au vendredi, de 8~h~00 à 12~h~00 et de 14~h~00 à 17~h~00. Son PDG, \'Evariste Galois, demande à son directeur des ressources humaines (DRH), Bart Ernest, de créer une base de données dans laquelle seront enregistrées diverses informations sur le personnel. Pour cela, l'entreprise dispose du système de gestion MySQL. La requête suivante est utilisée pour créer la base de données.

\begin{listing}[language=SQL]{}{bb-ex4-1.sql}\end{listing}

\subsectionnn{Partie A}

\begin{questions}
\item Deux requêtes sont écrites page suivante.
\begin{questions}
\item Quel rôle joue l'attribut \og id \fg{} pour chacune des tables \texttt{personnel} et \texttt{postes} ?
\item L'attribut \og postes\_id \fg{} de la table \texttt{personnel} doit contenir des valeurs de l'attribut \og id \fg{} de la table \texttt{postes}.\\
Quel nom donne-t-on à cet attribut ?
\end{questions}

\begin{listing}[language=SQL]{}{bb-ex4-2.sql}\end{listing}


\item Que fait la requête suivante ?
\begin{listing}[language=SQL]{}{bb-ex4-3.sql}\end{listing}

\item Bart Ernest doit enregistrer les intitulés \og PDG \fg{} et \og DRH \fg{}  dans la table \texttt{postes}.

\'Ecrire la requête SQL de sorte que les enregistrements correspondent à ceux déjà faits dans la table \texttt{personnel} ?

\item Une autre table est créée à l'aide de la requête suivante:\enlargethispage*{\baselineskip}
\begin{listing}[language=SQL]{}{bb-ex4-4.sql}\end{listing}
\Par

Elle contient toutes les absences du personnel.

Le type \og DATE \fg{} permet d'enregistrer une date au format \texttt{YYYY-MM-DD}.

\Par

\'Ecrire une requête SQL permettant de compter le nombre d'enregistrements de la table \texttt{absences} pendant la période du lundi 1\ier{} février 2021 au vendredi 5 février 2021 inclus.
\end{questions}

\subsectionnn{Partie B}

Une table \texttt{salaires} est créée à l'aide de la requête suivante:
\begin{listing}[language=SQL]{}{bb-ex4-5.sql}\end{listing}
\Par
où:
\begin{itemize}
\item \og id\_personnel \fg{} contient une valeur de l'attribut \og id \fg{} de la table \texttt{personnel};
\item \og jour\_versement \fg{} contient la date (au format YYYY-MM-DD) où est émis le virement du salaire de la personne correspondant à l'attribut\linebreak \og id\_personnel \fg;
\item \og montant \fg{} contient le salaire (en euros) de la personne.
\end{itemize}

\begin{questions}
\item
\begin{questions}
\item \'Ecrire une requête SQL permettant de retourner le salaire moyen de l'entreprise sur l'ensemble de la table \texttt{salaires}.
\item \'Ecrire une requête SQL permettant de retourner le salaire moyen de l'entreprise en 2020, en supposant que tous les salaires de l'année 2020 ont été enregistrés le dernier jour de chaque mois.
\item \'Ecrire une requête SQL permettant de retourner le salaire moyen en 2020 de toutes les personnes de l'entreprise sauf le PDG, en supposant que tous les salaires de cette année sont enregistrés.
\end{questions}

\item \'Ecrire une requête SQL permettant de calculer le salaire annuel d'\'Evariste Galois en 2020.

\enlargethispage*{3em}
\item Afin de compléter la table \texttt{salaires}, une table nommée \texttt{base}\_\texttt{salaires} est créée à l'aide de la requête suivante:
\begin{listing}[language=SQL]{}{bb-ex4-6.sql}\end{listing}
\Par
où:
\begin{itemize}
\item \og id\_personnel \fg{} contient une valeur de l'attribut \og id \fg{} de la table \texttt{personnel};
\item \og salaire\_horaire \fg{} contient le salaire horaire (en euros) de la personne correspondant à l'attribut \og id\_personnel \fg;
\item \og base\_horaire \fg{} contient le nombre d'heures de travail que la personne doit effectuer par jour.
\end{itemize}

La requête suivante:
\begin{listing}[language=SQL]{}{bb-ex4-13.sql}\end{listing}
\Par
crée une vue nommée \og abs\_view \fg{}, qui est une table dont les enregistrements sont les \og id \fg{} des personnes ayant été absentes au moins une fois en février 2021 ainsi que le nombre total d'heures d'absence pour chacune d'elles.

\begin{questions}
\item \'Ecrire une requête SQL créant une vue nommée \og suppressions \fg{} créant une table à deux attributs : \og id\_personnel \fg{} et\linebreak \og total\_suppressions \fg{} contenant respectivement les \og id \fg{} des personnes ayant été absentes en février 2021 ainsi que la retenue sur salaire de ces personnes (valeur obtenue en multipliant le nombre d'heures d'absence par le salaire horaire de la personne).

\item En déduire une requête permettant d'afficher le salaire de février 2021 du PDG de l'entreprise, sachant qu'il y a 20 jours de travail au cours de ce mois.
\end{questions}
\end{questions}
\end{exobb}

\begin{corrigebb}
\subsectionnn{Partie A}
\begin{questions}
\item 
\begin{questions}
\item Dans chacune des tables \texttt{personnel} et \texttt{postes}, la présence de \og \texttt{PRIMARY KEY (id)} \fg assure le fait que l'attribut \og id \fg{} joue le rôle de \textit{clé primaire} pour chacune d'elles.

\item L'attribut \og postes\_id \fg{} met en relation deux tables: il s'agit donc d'une \textit{clé étrangère}.
\end{questions}

\item La requête proposée est une requête de type \og INSERT INTO \fg{}: elle enregistre donc une entrée, en l'occurrence dans la table \texttt{personnel}. Nous pouvons constater la présence de deux entrées (avec pour noms \og GALOIS \fg{} et \og ERNEST \fg.

Elle effectue donc deux enregistrements dans la table \texttt{personnel}.

\item La requête SQL permettant d'enregistrer les deux types de postes \og PDG \fg{} et \og DRH \fg{} est la suivante:
\begin{listing}[language=SQL]{}{bb-ex4-7.sql}\end{listing}
\Par
Il faut ici faire attention au fait que l'id de chaque enregistrement doit correspondre à ceux déjà informés dans la requête d'insertion des noms dans la table \texttt{personnel}; or, nous voyons que \og GALOIS \fg{} à un\linebreak \texttt{postes}\_\texttt{id} égal à 1 et \og ERNEST \fg, un \texttt{postes}\_\texttt{id} égal à 2, d'où le fait que \og PDG \fg{} (correspondant au poste de GALOIS) est inséré avant \og DRH \fg (afin d'avoir un \texttt{id} égal à 1, tout en attribuant un \texttt{id} égal à 2 pour \og DRH \fg).
\enlargethispage*{\baselineskip}

\item Une requête SQL permettant de compter le nombre d'enregistrements de la table \texttt{absences} pendant la période du lundi 1\ier{} février 2021 au vendredi 5 février 2021 inclus est celle page ci-contre.\newpage
\begin{listing}[language=SQL]{}{bb-ex4-8.sql}\end{listing}
\Par
Il faut ici faire attention à la présence des apostrophes pour les dates. Sans ces caractères, la requête échoue.
\end{questions}

\subsectionnn{Partie B}

\begin{questions}
\item 
\begin{questions}
\item Une requête SQL permettant de retourner le salaire moyen de l'entreprise sur l'ensemble de la table \texttt{salaires} est la suivante:
\begin{listing}[language=SQL]{}{bb-ex4-9.sql}\end{listing}
\Par
Par cette requête, on calcule la moyenne sur l'intégralité des enregistrements de la table car aucune condition n'y apparaît.

\item Une requête SQL permettant de retourner le salaire moyen de l'entreprise en 2020, en supposant que tous les salaires de l'année 2020 ont été enregistrés le dernier jour de chaque mois est:
\begin{listing}[language=SQL]{}{bb-ex4-10.sql}\end{listing}

\item Une requête SQL permettant de retourner le salaire moyen en 2020 de toutes les personnes de l'entreprise sauf le PDG, en supposant que tous les salaires de l'année 2020 ont été enregistrés le dernier jour de chaque mois est:
\begin{listing}[language=SQL]{}{bb-ex4-11.sql}\end{listing}
\end{questions}

\item Une requête SQL permettant de calculer le salaire annuel d'\'Evariste Galois en 2020 est la suivante:
\begin{listing}[language=SQL]{}{bb-ex4-12.sql}\end{listing}

\item 
\begin{questions}
\item Une requête possible est la suivante:
\begin{listing}[language=SQL]{}{bb-ex4-14.sql}\end{listing}

\enlargethispage*{2em}
\item Une requête possible est :
\begin{listing}[language=SQL]{}{bb-ex4-15.sql}\end{listing}
\Par
Pour cette requête, nous avons utilisé le fait que pour calculer le salaire après absences éventuelles, il faut:
\begin{itemize}
\item calculer le salaire \og normal \fg{} : 
\[
20\text{ jours } \times \text{nombre d'heures travaillées par jour} \times \text{salaire horaire}
\]
\item enlever la retenue calculée dans la vue \texttt{suppressions}.
\end{itemize}
\end{questions}
\end{questions}
\end{corrigebb}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exobb}{Programmation et base de données}{\null}{2}{70}
On considère la classe \texttt{wezz} définie en annexe (voir page \pageref{annexe-bb}).
\enlargethispage*{5em}

\begin{questions}
\item 
\begin{questions}
\item Voici une suite d'instructions en mode console:
\Par
\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
\pychevrons obj = wezz(8,3,15)\\
\pychevrons print( obj.somme() )\\
~298\\
\pychevrons print( obj.div() )\\
~[1, 2, 149, 298]
\end{tabularx}
\Par
Comment interpréter ces deux résultats ?

\item L'appel à la méthode \texttt{somme} dans la méthode \texttt{div} pose un problème en terme de complexité. Lequel ?

Proposer alors une amélioration de la méthode \texttt{div}.

\item Compléter le programme suivant afin de définir la méthode \texttt{div} de manière encore plus concise.

\begin{listing}{}{bb-ex2-q1c.py}
\end{listing}
\end{questions}

\item On s'intéresse à la méthode \texttt{fct}.
\begin{questions}
\item Expliquer le rôle de l'attribut \texttt{*args}.
\item Expliquer pourquoi cette méthode peut être qualifiée de récursive.
\item Qu'est-ce qui nous assure l'arrêt de cette méthode ?
\item Que retourne \texttt{wezz(3,7,5).fct()} ?\\
On donnera uniquement le résultat.
\end{questions}

\item On souhaite maintenant effectuer un grand nombre de calculs sur\linebreak différents \og wezz \fg{} et stocker les résultats dans une base de données que l'on nomme \og wezz.db \fg. On utilise pour cela le système de gestion de base de données \textit{MySQL}.

On considère alors la fonction \texttt{insert}\_\texttt{sql} définie en annexe 2 (voir page \pageref{annexe-2-bb}).

\begin{questions}
\item Expliquer la requête SQL : 
\Par

\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
INSERT INTO wezz.simulations (a,b,c,s)\\
VALUES (\%s,\%s,\%s,\%s)
\end{tabularx}

\item Quelle requête SQL permet d'obtenir tous les enregistrements où la valeur de \og $s$ \fg{}  est strictement inférieure à 500 ?

\item Quelle requête SQL permet d'obtenir tous les enregistrements classés selon un ordre croissant sur \og $a$ \fg, puis sur \og $b$ \fg, puis sur \og $c$ \fg ?

\item Quelle requête SQL permet d'obtenir la moyenne des valeurs de \og 
$s$ \fg{} ?

\item On suppose que l'on a fait appel à la fonction \texttt{insert}\_\texttt{sql} à cinq reprises.

Qu'affiche alors la requête:
\Par
\quad\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
SELECT COUNT(*) FROM simulations
\end{tabularx}

\end{questions}
\end{questions}

\newpage

\subsubsectionnn{Annexe 1 : définition de la classe \og wezz \fg{} }

\begin{listing}{}{bb-wezz.py}\end{listing}
\label{annexe-bb}

\newpage

\subsubsectionnn{Annexe 2 : définition de la fonction \og insert\_sql \fg}

\begin{listing}{}{bb-ex2-q3.py}
\end{listing}
\label{annexe-2-bb}

\vspace*{1cm}

% bb-ex2-complet.py
\nathanlive{prog}{Téléchargez les annexes 1 et 2 en une fois.}
\end{exobb}


%


\begin{corrigebb}
\begin{questions}
\item
\begin{questions}
\item Procédons par étape.
\begin{itemize}
\item La méthode \texttt{somme} : elle permet simplement de retourner la somme $a^2+b^2+c^2$. Dans notre cas, elle retourne $8^2 + 3^2 + 15^2 = 298$.

\item La méthode \texttt{div} : on commence ici par initialiser une liste vide \texttt{L}, puis on entre dans une boucle itérative en \texttt{n}, pour \texttt{n} variant de 1 à 298 dans notre cas.

L'instruction \og \texttt{if self.somme() \% n == 0} \fg{} teste si la somme obtenue est divisible par \texttt{n}. Si le test est positif, on ajoute dans la liste \texttt{L} la valeur de \texttt{n}.

Ainsi, \texttt{L} contiendra à la sortie de la boucle itérative tous les\linebreak diviseurs de 298.
\end{itemize}


\textit{Conclusion :} \texttt{[1, 2, 149, 298]} est l'ensemble de tous les\linebreak diviseurs de 298.

\item Dans la méthode \texttt{div}, on calcule la somme $a^2+b^2+c^3$ 298 fois dans notre cas, ce qui n'est pas idéal. On peut facilement y remédier en réécrivant la méthode de la manière suivante:

\begin{listing}{}{bb-ex2-q1b-c.py}\end{listing}


\item On peut en effet définir la liste \texttt{L} de manière plus concise ainsi:

\begin{listing}{}{bb-ex2-q1c-c.py}\end{listing}
\end{questions}

\item
\begin{questions}
\item L'attribut \texttt{*args} permet de faire passer des valeurs à la méthode \texttt{fct} de manière optionnelle. 

\item Cette méthode est récursive car elle s'appelle au sein même de sa définition : elle fait appel à elle-même.

\item Par définition, les variables \texttt{a}, \texttt{b} et \texttt{c} sont entières et positives (ou nulles). 

De plus, à chaque appel de la méthode \texttt{fct}, leurs valeurs diminuent de 1. Il existe donc un appel où une des variables est égale à 0. Or, quand cela se produit, la méthode retourne \og 0 \fg, et s'arrête donc. 

C'est ce qui nous assure que la méthode s'arrête.

\item \texttt{wezz(3,7,5).fct()} retourne 168. En effet, on calcule successivement : $\min(3,7,5)=3$, $\min(2,6,4)=2$, $\min(1,5,3)=1$, $\min(0,4,2)=0$ : on calcule alors : $1\times5\times3+0=15$, puis $2\times6\times4+15=63$ et finalement $3\times7\times5+63=168$.
\end{questions}

\item
\begin{questions}
\item ~\par 

\vspace*{-7mm}
\begin{listing}[language=SQL]{}{bb-ex3-q3-a.sql}\end{listing}
\Par
Cette requête SQL permet d'insérer un enregistrement dans la table \texttt{simulations} de la base de données \texttt{wezz}. Cet enregistrement est composé de quatre attributs : les valeurs de $a$, $b$, $c$ et $d$.

\vspace*{-3mm}
\begin{Remarque}
on ne mentionne pas l'attribut \og id \fg car il est auto-incrémenté, donc sa valeur est générée par le SGBD.
\end{Remarque}

\item Une requête SQL permettant d'obtenir tous les enregistrements où la valeur de \og s \fg{} est strictement inférieure à 500 est:
\begin{listing}[language=SQL]{}{bb-ex3-q3-b.sql}\end{listing}

\item La requête SQL qui permet d'obtenir tous les enregistrements classés selon un ordre croissant sur \og $a$ \fg, puis sur \og $b$ \fg, puis sur \og $c$ \fg est:
\begin{listing}[language=SQL]{}{bb-ex3-q3-c.sql}\end{listing}


\item La requête SQL qui permet d'obtenir la moyenne des valeurs de \og 
$s$ \fg{} est:
\begin{listing}[language=SQL]{}{bb-ex3-q3-d.sql}\end{listing}
\enlargethispage*{3em}

\item La requête suivante permet de compter le nombre d'enregistrements dans la table \texttt{simulations}.
\begin{listing}[language=SQL]{}{bb-ex3-q3-e.sql}\end{listing}
\Par
Dans la mesure où la fonction \texttt{insert}\_\texttt{sql} insère 100 enregistrements dans la table \texttt{simulations} et qu'on y a fait appel cinq fois, la requête doit afficher : \og 500 \fg{} ($5 \times 100$).
\end{questions}
\end{questions}
\newpage
\end{corrigebb}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\begin{exobb}{Programmation et graphes}{\null}{2}{70}
On souhaite implémenter en Python un graphe où les sommets sont les\linebreak régions de la France métropolitaine et où les arêtes représentent la\linebreak mitoyenneté entre deux régions. On notera $\mathcal{G}$ ce graphe.

\Par

\begin{minipage}{5cm}
\begin{figure}
\begin{center}
\includegraphics{319_BacBlanc-CarteFrance-mini}
\figcaption{Carte de la France métropolitaine et de ses régions}
\end{center}
\end{figure}
\end{minipage}
\hfill
\begin{minipage}{55mm}
Les sommets du graphes sont notés:
\begin{itemize}
\item IDF : Île-De-France;
\item HDF : Hauts-De-France;
\item N : Normandie;
\item B : Bretagne;
\item PDL : Pays-De-La-Loire;
\item NA : Nouvelle-Aquitaine;
\item O : Occitanie;
\item C : Corse;
\item PACA : \mbox{Provence-Alpes-Côte-D'Azur;}
\item ARA : Auvergne-Rhône-Alpes;
\item BFC : Bourgogne-Franche-Comté;
\item GE : Grand-Est;
\item CVL : Centre-Val-De-Loire.
\end{itemize}
\end{minipage}



On supposera que la Corse n'est mitoyenne qu'à la région PACA.

\begin{questions}
\item Donner une représentation sagittale de $\mathcal{G}$.
\item 
\begin{questions}
\item Quel est l'ordre de $\mathcal{G}$ ?
\item $\mathcal{G}$ est-il connexe ?
\item $\mathcal{G}$ est-il cyclique ?
\end{questions}

\item 
\begin{questions}
\item\label{qBB-mat} Donner la première ligne de la matrice d'adjacence $A$ de $\mathcal{G}$. Pour cela, on conviendra de noter les sommets dans l'ordre alphabétique, donc dans l'ordre suivant:
\Par
\begin{center}
ARA, B, BFC, C, CVL, GE, HDF, IDF, N, NA, O, PACA, PDL.
\end{center}

\item Donner l'ensemble d'adjacence de $\mathcal{G}$ sous la forme \og sommet S$_i$ : liste de sommets reliés à $S_i$ \fg.
\item Pour implémenter $\mathcal{G}$, que semble-t-il plus cohérent d'utiliser entre la matrice d'adjacence et l'ensemble d'adjacence ? Justifier.
\end{questions}

\item On utilise la classe suivante pour implémenter $\mathcal{G}$:

\begin{listing}{}{bb-ex3-q4.py}\end{listing}

\Par
\begin{questions}
\item On décide de noter \og \texttt{G} \fg le graphe implémenté. 

Quelle instruction permet de créer une instance \texttt{G} de la classe \texttt{Graphe()} ?

\item Quelles instructions permettent de définir les arrêtes du sommet NA à tous ses sommets mitoyens ?


\item On suppose à présent que tous les sommets du graphe ont été définis sur l'objet \texttt{G} à la manière de la question précédente et on s'intéresse à l'instruction:
\Par
\texttt{\pychevrons print(G.sommets())}
\Par
Expliquer ce que fait cette instruction. On écrira, à titre d'exemple, les deux premières lignes du résultat escompté.
\end{questions}

\item À la classe \og Graphe \fg{} précédemment définie, on ajoute la méthode \texttt{mystere} suivante:
\begin{listing}{}{bb-ex3-q5.py}\end{listing}
\Par

Que renvoie-t-elle ?





\item Proposer un algorithme qui permet d'obtenir la matrice d'adjacence du graphe $\cal G$ obtenue à la question \ref{qBB-mat}.

\item Proposer alors une méthode \texttt{mat} à ajouter à la classe \texttt{Graphe} qui\linebreak retourne la matrice d'adjacence du graphe.
\end{questions}
\end{exobb}


%%%

\begin{corrigebb}
\begin{questions}
\item Une représentation sagittale du graphe $\mathcal{G}$ est la suivante:
\begin{figure}
\begin{center}
\includegraphics{331_BacBlanc-Graphe}
\figcaption{Représentation sagittale du graphe $\cal G$}
\end{center}
\end{figure}

\item
\begin{questions}
\item L'ordre d'un graphe est le nombre de sommets. Donc l'ordre de $\cal G$ est ici égal au nombre de régions représentées, à savoir 13.

\item Un graphe est connexe s'il ne comporte pas de sommets isolés, ce qui est le cas ici. Donc $\cal G$ est connexe.

\item Un graphe est cyclique si, pour n'importe quel sommet, il existe un chemin le reliant à lui-même, ce qui n'est pas le cas pour $\cal G$. En effet, il n'existe aucun cycle de sommet C.
\end{questions}

\item
\begin{questions}
\item Les sommets sont classés par ordre alphabétique, ce qui donne :
\Par
\begin{center}
ARA, B, BFC, C, CVL, GE, HDF, IDF, N, NA, O, PACA, PDL.
\end{center}
%La matrice est donc la suivante:
%\Par
%\begin{center}
%\scalebox{0.87}{$A = \left(
%\begin{array}{*{13}{c}}
%0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\\%1
%0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\%2
%1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\%3
%0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\%4
%1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1\\%5
%0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\%6
%0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\%7
%0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\%8
%0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\%9
%1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\\%10
%1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0\\%11
%1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\%12
%0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\%13
%\end{array}
%\right)$}
%\end{center}
%\Par
On ne demande ici que la première ligne $A[1]$ de la matrice : 
\[ A[1] = \left(\begin{array}{*{13}{c}}0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0\end{array}\right).\]
Ici, les \og 1 \fg{} représentent les connexions entre \og ARA \fg{} et les\linebreak sommets : BFC, CVL, NA, O et PACA.

\newpage

\item L'ensemble d'adjacence de $\cal G$ est :
\begin{itemize}
\item ARA : BFC, CVL, NA, O, PACA
\item B : N, PDL
\item BFC : ARA, CVL, GE, IDF
\item C :PACA
\item CVL : ARA, BFC, IDF, N, NA, PDL
\item GE : BFC, HDF, IDF
\item HDF : GE, IDF, N
\item IDF : BFC, CVL, GE, HDF, N
\item N : B, CVL, IDF, HDF, PDL
\item NA : ARA, CVL, O, PDL
\item O : ARA, NA, PACA
\item PACA : ARA, C, O
\item PDL :  B, CVL, N, NA
\end{itemize}

\item Afin d'implémenter le graphe $\cal G$, il semble plus cohérent d'utiliser la liste d'adjacence. En effet, la matrice $A$ est creuse (beaucoup de \og 0 \fg), ce qui occuperait de la mémoire pour rien, sans compter que le nombre de coefficients à saisir étant important, le risque de faire des erreurs dans la saisie n'est pas négligeable.
\end{questions}

\item 
\begin{questions}
\item L'instruction qui permet de créer une instance \texttt{G} de la classe \texttt{Graphe} est:

\Par

\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
G = Graphe()
\end{tabularx}

\item Les instructions permettant de définir les arrêtes du sommet NA à ses voisins sont :

\Par

\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
liste = [ 'PDL' , 'CVL' , 'ARA' , 'O']\\
for i in liste:\\
\quad G.edge('NA' , i)
\end{tabularx}

\begin{Remarque}
bien entendu, il y a plusieurs possibilités pour cette question. Nous aurions pu éviter la boucle et écrire quatre\linebreak instructions de la forme \og \texttt{G.edge('NA','<sommet>'} \fg.
\end{Remarque}

\item L'instruction \og \texttt{print( G.sommets() )} \fg{} affiche le dictionnaire qui contient tous les sommets du graphe $\cal G$ (en tant que clés) et tous les sommets qui sont reliés aux clés (dans une liste). Ainsi, les deux première lignes affichées sont:

\Par

\begin{tabularx}{\linewidth}{@{}|>{\ttfamily}X@{}}
ARA : ['BFC', 'CVL', 'NA', 'O', 'PACA']\\
B : ['N', 'PDL']
%BFC : ['ARA', 'N', 'PDL', 'CVL', 'GE', 'IDF']\\
%CVL : ['ARA', 'BFC', 'IDF', 'N', 'NA', 'PDL']\\
%NA : ['ARA', 'CVL', 'O', 'PDL']\\
%O : ['ARA', 'NA', 'PACA']\\
%
%N : ['B', 'BFC', 'CVL', 'HDF', 'IDF', 'PDL']\\
%PDL : ['B', 'BFC', 'CVL', 'N', 'NA']\\
%C : ['PACA']\\
%PACA : ['C', 'O', 'ARA']\\
%IDF : ['CVL', 'GE', 'HDF', 'BFC', 'N']\\
%GE : ['BFC', 'HDF', 'IDF']\\
%HDF : ['GE', 'IDF', 'N']
\end{tabularx}
\end{questions}

\item La méthode \texttt{mystere} ajoutée à la classe \texttt{Graphe} est une méthode de parcours (en largeur) à partir du sommet \og NA \fg.

En effet, la liste \texttt{tmp} est une file dans laquelle on place en tête le sommet \og NA \fg. Ensuite, tant que cette file n'est pas vide (\texttt{while tmp:}), on définit un sommet \texttt{S} comme étant le premier élément de la file ; s'il n'est pas dans la liste \texttt{sortie} (initialement vide), on l'y ajoute. On définit alors une liste \texttt{unvisited} complétée par les sommets qui sont dans la valeur correspondant à la clé du sommet et qui ne sont pas dans la liste \texttt{sortie} dans le dictionnaire \texttt{sommets} du graphe.

Il s'agit donc bien ici d'un algorithme de parcours de graphe.

\item Voici un algorithme qui permet d'obtenir la matrice $A$ :

\begin{algorithme}{}
A $\leftarrow$ matrice de dimension 13 remplie de 0
S $\leftarrow$ liste des sommets du graphe triée par ordre
\hspace*{48ex}alphabétique
Pour chaque élément "e" de S:
\quad L $\leftarrow$ liste des sommets connectés à "e"
\quad Pour chaque élément "c" de L:
\qquad i $\leftarrow$ indice de "e" dans S
\qquad j $\leftarrow$ indice de "c"
\qquad A[i][j] $\leftarrow$ 1
\quad Fin Pour
Fin Pour
Afficher A
\end{algorithme}

\item Une méthode \texttt{mat} possible est la suivante:

\begin{listing}{}{bb-ex3-q7-c.py}\end{listing}
\Par
\nathanlive{prog}{Télécharger la classe complète.} % bb-ex3.py

\newpage

%\begin{attention}La façon de définir initialement la matrice A a son importance. En effet, écrire :\Par{\ttfamily A = [ [0] * len(self.sommets) ] * len(self.sommets)}\Par ne sera pas correct car au final, la méthode renvoie dans cette\linebreak situation une matrice remplie de \og 1 \fg. En effet, en définissant la\linebreak matrice A ainsi, quand on pense modifier un coefficient, on modifie en fait une colonne entière! Par exemple, le code suivant:\Par{\ttfamily\pychevrons a = [ [0] * 3] * 3\\\pychevrons a[1][1] = 1\\\pychevrons a}\Par renvoie : \texttt{[[0, 1, 0], [0, 1, 0], [0, 1, 0]]}.\Par En définissant ainsi la matrice, ce sont les mêmes références qui sont utilisées. Autrement dit, en mémoire, il n'y a pas création des $3\times3$ emplacements mais de 3 seulement. Et ces mêmes 3 emplacements sont référencés de 3 manières différentes.\\La \og case \fg{}  \texttt{a[0][0]} est la même que la case \texttt{a[1][0]} et que la case \texttt{a[2][0]}. \\C'est une particularité déconcertante de Python.\end{attention}
\end{questions}
\end{corrigebb}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exobb}{Réseau}{\null}{2}{70}
\subsectionnn{Partie A : routage statique}

Soit un réseau domestique composé des éléments suivants:
\begin{itemize}
\item une box internet (BOX);
\item une TV connectée à un port ethernet de la box;
\item un routeur/point d'accès wifi (R), connecté à un port Ethernet de la box et qui gère un réseau sans fil différent du réseau filaire (représenté en orange);
\item un premier PC (PC1) relié à un port Ethernet de la box et qui dispose aussi d'une connexion wifi;
\item un second PC (PC2), une caméra wifi (CAM) et un smartphone (TEL), tous les trois connectés au réseau wifi.
\end{itemize}
\begin{figure}
\begin{center}
\includegraphics{321_bb-routage-statique}
\figcaption{Représentation du réseau domestique}
\end{center}
\end{figure}
\begin{questions}
\item Compléter la table de routage (simplifiée) du PC1:
\Par
\begin{center}
\begin{tabular}{|*3{Zc|}}
\tabulartitle
\hline
Destination réseau & Masque réseau & Passerelle\\
\hline
192.168.1.0 & ?  .  ?  .  ?  .  ? & Interface locale ethernet \\
\hline
?  .  ?  .  ?  .  ? & ?  .  ?  .  ?  .  ? & Interface locale wifi\\
\hline
0.0.0.0 & 0.0.0.0 & 192.168.1.1\\
\hline
\end{tabular}
\end{center}

\item Que signifie la dernière ligne du tableau ?

\item L'ordinateur \og PC1 \fg se connecte à la caméra Wifi (CAM). 

Quelle ligne de la table de routage ci-dessus correspond à la route utilisée ? Expliquer comment est opéré ce choix et quelle est l'adresse IP source utilisée par PC1.
\enlargethispage*{4em}

\item Écrire la table de routage (simplifiée) de l'ordinateur \og PC2 \fg à la manière de celle présentée en question 1.

\item Le smartphone a-t-il connaissance de l'adresse locale de la box internet ? Expliquer.
\end{questions}

\subsectionnn{Partie B : routage RIP}

On considère la topologie réseau suivante, qui peut être assimilée à un graphe où chaque sommet représente un routeur implémentant le protocole RIP.

\Par

\begin{figure}
\begin{center}
\includegraphics{322_bb-topologie-rip}
\figcaption{Graphe représentant la topologie réseau}
\end{center}
\end{figure}

\begin{questions}
\item Rappeler les grands principes du protocole RIP.
\item On s'intéresse au routeur A.
\begin{questions}
\item Quelles sont les routes qui lui permettent de joindre D et les métriques correspondantes ?
\item Quelles seront les routes établies par chacun des routeurs pour rejoindre D après convergence (c'est-à-dire une fois que les routeurs auront échangé suffisamment d'informations RIP pour que les tables de routage de chacun soient complètes). Mentionner les métriques correspondantes.
\end{questions}

\item Donner les tables de routage complètes des routeurs A et B après convergence.

\item Le routeur A tombe en panne.
\begin{questions}
\item Expliquer sommairement la gestion de cette panne par le protocole RIP.
\item Donner la nouvelle table de routage de B après re-convergence.
\item Quelle(s) sera (seront) la (les) route(s) B $\to$ C conservée(s) ?

Expliquer.
\end{questions}
\end{questions}

\subsectionnn{Partie C : routage OSPF}
\enlargethispage*{4em}

On considère la topologie réseau suivante, qui peut être assimilée à un graphe où chaque sommet représente un routeur implémentant le protocole OSPF. Les chiffres sont les coûts supposés des métriques OSPF assignées à chaque liaison inter-routeur.

\Par

\begin{figure}
\begin{center}
\includegraphics{322_bb-topologie-ospf}
\figcaption{Graphe représentant la topologie réseau}
\end{center}
\end{figure}

\begin{questions}
\item Rappeler les grands principes du protocole OSPF (comparé au protocole RIP).
\item Quelle sera la route utilisée entre G et E après convergence (c'est-à-dire lorsque les routeurs auront effectué suffisamment d'échanges de tables de routage pour que toutes les relations d'adjacence soient propagées) ?

Quelle aurait été cette route avec le protocole RIP ?

\item On veut déterminer la table de routage de B sous la forme:\label{bbqtableB}
\Par
\begin{center}
\begin{tabular}{|*3{Zc|}}
\tabulartitle
\hline
Destination & Passerelle à utiliser & Métrique\\
\hline
A&   & \\
\hline
C &  & \\
\hline
$\ldots$ & $\ldots$ & $\ldots$\\
\hline
\end{tabular}
\end{center}
\begin{questions}
\item Quel est l'algorithme utilisé dans la pratique pour déterminer le chemin optimal entre B et chacun des routeurs destinataires envisagés ? Expliquer.

\item Donner la table de routage complète de B après convergence.
\end{questions}

\item \textit{Question bonus.} Le routeur D est à présent connecté à un routeur R supplémentaire qui appartient à un réseau inconnu (réseau mystère). 

\Par

\begin{figure}
\begin{center}
\includegraphics{323_bb-connexion-mystere}
\figcaption{Graphe après connexion à un réseau mystère}
\end{center}
\end{figure}
\Par
\begin{minipage}{0.45\linewidth}
Après quelques minutes de fonctionnement du réseau, la convergence est supposée établie et R échange sa table de routage avec chaque routeur A à H. Voici ci-contre un extrait de la table de routage transmise par R.
\end{minipage}
\hfill
\begin{minipage}{0.5\linewidth}
\begin{tabular}{|Zc|>{\centering\arraybackslash}m{17mm}|Zc|}
\tabulartitle
\hline
\small Destination & \small Passerelle à utiliser & \small Métrique\\
\hline
C & D & 8\\
\hline
D & D & 3\\
\hline
$\ldots$ & $\ldots$ & $\ldots$\\
\hline
I & I & 2\\
\hline
J & J & 1\\
\hline
K & I & 6\\
\hline
L & J & 2\\
\hline
M & J & 5\\
\hline
\end{tabular}
\end{minipage}
\enlargethispage*{4em}
\begin{questions}
\item À partir de ces informations, compléter la table de routage de B précédemment renseignée à la question \ref{bbqtableB}.

\item Dessiner une topologie possible des routeurs I à M du réseau mystère (il y a beaucoup de possibilités !). On impose uniquement qu'elle soit compatible avec les tables de routage de B et de R.
\end{questions}
\end{questions}
\end{exobb}

\begin{corrigebb}
\subsectionnn{Partie A : routage statique}
\begin{questions}
\item La table complétée est la suivante:
\Par
\begin{center}
\begin{tabular}{|*3{Zc|}}
\tabulartitle
\hline
Destination réseau & Masque réseau & Passerelle\\
\hline
192.168.1.0 & \color{DR}255.255.255.0 & Interface locale ethernet \\
\hline
\color{DR}192.168.5.0 & \color{DR}255.255.255.0 & Interface locale wifi\\
\hline
0.0.0.0 & 0.0.0.0 & 192.168.1.1\\
\hline
\end{tabular}
\end{center}

\item La dernière ligne de la table signifie qu'il s'agit de la passerelle \og par défaut \fg, c'est-à-dire que tous les paquets de données TCP/IP qui ne correspondent pas à un des autres réseaux listés seront envoyés à l'hôte 192.168.1.1 (la box internet).
\Par
Cette configuration (usuelle) est indispensable pour permettre le routage des échanges vers les sites internet et tous les services du réseau public. La box sert d'intermédiaire. Elle fait transiter les informations entre le réseau local et le web grâce à des protocoles de translation d'adresses IP qui ne sont pas au programme de terminale.

\item PC1 doit joindre l'hôte: 192.168.5.132 (CAM). L'algorithme de recherche de la passerelle/interface à utiliser est le suivant:
\begin{itemize}
\item PC1 examine tour à tour les lignes de sa table de routage, en commençant par celles dont le masque de réseau est le plus long (contient le plus grand nombre de bits à 1).
\item Pour chaque ligne examinée, il effectue un \og ET \fg logique (binaire) entre l'adresse de destination et le masque réseau.
\item Si le résultat de l'opération correspond à l'adresse du réseau destinataire (colonne de gauche), alors il utilise la passerelle mentionnée dans la ligne (colonne de droite). Sinon, il passe à l'examen de la ligne suivante.
\end{itemize}

\Par

\textit{Examen de la ligne 1.}

\Par

\begin{tabular}{Zr@{\quad}ZlZcZl}
 & 192.168.5.132 & $\to$ &\small 1100 0000 . 1010 1000 . 0000 0101 . 1000 0100\\
ET & 255.255.255.0 & $\to$ &\small 1111 1111 . 1111 1111 . 1111 1111 . 0000 0000\\
$=$ & 192.168.5.0 & $\leftarrow$ &\small 1100 0000 . 1010 1000 . 0000 0101 . 0000 0000
\end{tabular}

\Par

Le résultat (192.168.5.0) ne correspond pas au réseau de destination de la ligne 1 (colonne de gauche). Ce n'est donc pas cette ligne qui est utilisée.

\Par

\textit{Examen de la ligne 2.}

\Par

Le calcul est identique car les deux lignes ont le même masque de réseau. Donc on obtient le même résultat: 192.168.5.0.

Cette fois-ci, il correspond au réseau destination de la ligne 2 (colonne de gauche) donc c'est la passerelle située sur cette ligne: \og Interface locale wifi \fg qui est utilisée.

La communication sera donc directe entre les deux équipements et empruntera le réseau Wifi auquel PC1 est directement connecté. Elle ne transitera pas par un routeur. L'adresse source utilisée par PC1 sera celle de son interface wifi: 192.168.5.54.

\item La table de routage de l'ordinateur \og PC2 \fg{} est la suivante:
\Par
\begin{center}
\begin{tabular}{|*3{Zl|}}
\tabulartitle
\hline
Destination réseau&
Masque réseau&
Passerelle\\
192.168.5.0&
255.255.255.0&
Interface locale wifi\\
0.0.0.0&
0.0.0.0&
192.168.5.120\\
\hline
\end{tabular}
\end{center}
\begin{itemize}
\item Les communications vers des destinataires situés sur le réseau Wifi (192.168.5.0/24) sont directes (ligne 1).
\item Toutes les autres communications, à destination du réseau Internet ou des équipements situés sur le réseau local ethernet, transitent par le routeur/point d'accès R qui est donc la passerelle par défaut.
\end{itemize}

\item Le smartphone ne peut pas découvrir la topologie du réseau car ce n'est pas un routeur et il n'implémente pas de protocole de routage dynamique comme RIP ou OSPF. Il ne peut donc déduire que la présence des équipements connectés au même réseau que lui c'est-à-dire le réseau Wifi.

Il a la même table de routage que PC2 et envoie toute communication à destination du réseau Internet vers le routeur R qui est sa passerelle par défaut. C'est R qui se charge de faire le relai vers la box internet et qui retransmettra les réponses obtenues au smartphone.
\end{questions}

\subsectionnn{Partie B : routage RIP}

\begin{questions}
\item Les grands principes du protocole RIP sont:
\begin{itemize}
\item RIP est un protocole de routage dynamique à vecteur de distance.
\item Chaque routeur envoie périodiquement sa table de routage aux routeurs voisins.
\item Les routeurs complètent ainsi progressivement leur table de routage et effectuent un décompte du nombre de routeurs présents sur chaque liaison.
\item Ils utilisent ce nombre (nombre de sauts) en tant que métrique pour déterminer les itinéraires les plus pertinents.
\item Lorsqu'il existe plusieurs liaisons différentes pour rejoindre un même routeur, seule(s) celle(s) de métrique la plus faible est (sont) conservée(s).
\end{itemize}

\item 
\begin{questions}
\item Les routes qui permettent au routeur A de joindre D et les métriques correspondantes sont les suivantes:
\Par
\begin{center}
\begin{tabular}{|Zl|Zl|}
\tabulartitle\hline
Route&
Métrique\\
\hline
A $\to$ C $\to$ D &
1\\\hline
A $\to$ B $\to$ E $\to$ D&
2\\\hline
A $\to$ B $\to$ G $\to$ F $\to$ C $\to$ D&
4\\\hline
A $\to$ C $\to$ F $\to$ G $\to$ B $\to$ E $\to$ D&
5\\\hline
\end{tabular}
\end{center}

\item Les routes établies par chacun des routeurs pour rejoindre D après convergence ainsi que leurs métriques sont:
\Par
\begin{center}
\begin{tabular}{|*4{Zc|}}
\tabulartitle\hline
Routeur&
Destination&
Passerelle&
Métrique\\
\hline
A & \multirow{7}{*}{D} & C & 1\\\cline{1-1}\cline{3-4}
B &  & E & 1\\\cline{1-1}\cline{3-4}
C &  & D & 0\\\cline{1-1}\cline{3-4}
E &  & D & 0\\\cline{1-1}\cline{3-4}
F &  & C & 1\\\cline{1-1}\cline{3-4}
\multirow{2}{*}{G} &  & B & 2\\\cline{3-4}
 &  & F & 2\\\hline
\end{tabular}
\end{center}
\end{questions}

\item Les tables de routage complètes des routeurs A et B après convergence sont:
\Par
\begin{center}
\begin{tabular}{|*4{Zc|}}
\tabulartitle\hline
Routeur&
Destination&
Passerelle&
Métrique\\
\hline
\multirow{6}{*}{A}&
B&
B&
0\\\cline{2-4}
&
C&
C&
0\\\cline{2-4}
&
D&
C&
1\\\cline{2-4}
&
E&
B&
1\\\cline{2-4}
&
F&
C&
1\\\cline{2-4}
&
G&
B&
1\\\hline
\multirow{6}{*}{B}&
A&
A&
0\\\cline{2-4}
&
C&
A&
1\\\cline{2-4}
&
D&
E&
1\\\cline{2-4}
&
E&
E&
0\\\cline{2-4}
&
F&
G&
1\\\cline{2-4}
&
G&
G&
0\\\hline
\end{tabular}
\end{center}
\item
\begin{questions}
\item Le protocole RIP gère la panne du routeur A de la manière suivante:
\begin{itemize}
\item les routeurs B et C, voisins de A, ne recevront plus ses données RIP périodiques. Au bout d'un certain temps, ils vont décréter A comme \og absent \fg;
\item B et C vont désactiver de leurs tables de routage toutes les routes faisant intervenir A en tant que destinataire ou passerelle;
\item les nouvelles tables de routage vont se propager de proche en proche jusqu'à une nouvelle convergence.
\end{itemize}

\item La nouvelle table de routage de B après re-convergence est la suivante:
\Par
\begin{center}
\begin{tabular}{|*4{Zc|}}
\tabulartitle\hline
Routeur&
Destination&
Passerelle&
Métrique\\
\hline
\multirow{6}{*}{B}&
C&
E&
2\\\cline{2-4}
&
C&
G&
2\\\cline{2-4}
&
D&
E&
1\\\cline{2-4}
&
E&
E&
0\\\cline{2-4}
&
F&
G&
1\\\cline{2-4}
&
G&
G&
0\\\hline
\end{tabular}
\end{center}
\Par
Le routeur C ne peut plus être atteint en utilisant A comme passerelle. Les deux autres chemins possibles font respectivement intervenir les routeurs E et G et ont une métrique identique de 2 sauts. 

\item Les métriques des deux routes étant identiques, B conserve ces deux itinéraires. Dans la pratique, il diffusera les paquets à destination de C, alternativement à E et G pour répartir la charge réseau entre les deux chemins jugés équivalents.
\end{questions}
\end{questions}

\subsectionnn{Partie C : routage OSPF}

\begin{questions}
\item Les grands principes du protocole OSPF (comparé au protocole RIP) sont:
\begin{itemize}
\item OSPF est un protocole de routage dynamique à états de lien;
\item comme dans le cas de RIP, chaque routeur envoie périodiquement sa table de routage aux routeurs voisins et les routeurs complètent ainsi progressivement leur propre table de routage;
\item à la différence de RIP, la métrique est ici calculée en fonction de la performance de débit de chaque liaison. Plus une liaison est rapide plus sa métrique est faible;
\item lorsque qu'un même destinataire peut être joint par plusieurs liaisons différentes, les routeurs ne conservent que celle(s) de métrique la plus faible (donc au débit le plus élevé).
\end{itemize}

\item 
\begin{itemize}
\item Après convergence, seule la route de métrique OSPF la plus faible sera conservée soit:
\begin{center}
G $\to$ B $\to$ A $\to$ F $\to$ E  (métrique OSPF = 7).
\end{center}
Les autres routes (G $\to$ H $\to$ E et G $\to$ B $\to$ C $\to$ D $\to$ E) ont des métrique OSPF plus élevées (respectivement 9 et 11).

\item Le protocole RIP aurait retenu la route faisant intervenir le moins de routeurs possible (limitation du nombre de sauts) soit G $\to$ H $\to$ E dont le débit est pourtant inférieur. Le protocole OSPF semble donc plus orienté performances.
\end{itemize}

\item
\begin{questions}
\item Il s'agit ici de rechercher les plus courts chemins pondérés vers chacun des routeurs destinataires car ce sont uniquement ces chemins qui seront retenus une fois la convergence établie.

Dans la pratique, c'est l'algorithme de Dijkstra qui fait référence et permet de trouver les chemins les plus courts en effectuant un minimum d'opérations.

\item \mbox{La table de routage complète de B après convergence est la suivante:}
\Par
\begin{center}
\begin{tabular}{|*3{Zc|}}
\tabulartitle\hline
Destination&
Passerelle à utiliser&
Métrique\\
\hline
A&
A&
3\\\hline
C&
C&
2\\\hline
D&
C&
7\\\hline
E&
A&
6\\\hline
F&
A&
5\\\hline
G&
G&
1\\\hline
H&
G&
6\\\hline
\end{tabular}
\end{center}
\end{questions}

\item 
\begin{questions}
\item La table de routage de B précédemment renseignée complétée est:
\Par
\begin{center}
\begin{tabular}{|*3{Zc|}}
\tabulartitle\hline
Destination&
Passerelle à utiliser&
Métrique\\\hline
A&
A&
3\\\hline
C&
C&
2\\\hline
D&
C&
7\\\hline
E&
A&
6\\\hline
F&
A&
5\\\hline
G&
G&
1\\\hline
H&
G&
6\\\hline
I&
C&
12\\\hline
J&
C&
11\\\hline
K&
C&
16\\\hline
L&
C&
12\\\hline
M&
C&
15\\\hline
\end{tabular}
\end{center}
\enlargethispage*{4em}
\item Voici une topologie possible, compatible avec la table de routage donnée dans l'énoncé et celle de R.
\begin{center}
\includegraphics{338_bb-reseau-mystere-corrige}
\end{center}
\end{questions}
\end{questions}
\end{corrigebb}
\onglet 
\AfficheCorrigeBB
