% !TEX encoding = UTF-8 Unicode

% Liste des codes à inclure
\begin{filecontents*}{AS-25-S2-Exo1-1}
SELECT nom FROM station WHERE latitude = -22.276000 AND longitude = 166.452833
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo1-2}
SELECT COUNT(nom_colonne) FROM table
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo1-2b}
SELECT COUNT(idStat) FROM station
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo1-5}
>>>liste_obs = creation_liste_obs('observations.csv')
>>>liste_obs = supp_champs(liste_obs)
>>>transtype(liste_obs)
>>>liste_obs[0]
[98801001, 'BELEP AEROD.', -19.719833, 163.661, 88, 2024010100,
0.0, 5.0, 80, 25.7]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo1-12}
import csv

def creation_liste_obs(fichier) :
    liste_obs=[]
    with open(fichier,'r') as csvfile:
        fic=csv.reader(csvfile,delimiter=',')
        for ligne in fic:
            liste_obs.append(ligne)
    return liste_obs

def supp_champs(L) :
    res = []
    for i in range(1,len(L)):
        res.append(L[i])
    return res

def transtype(L):
    i=0
    while i < len(L):
        L[i] = [int(L[i][0]),
                L[i][1],
                float(L[i][2]),
                float(L[i][3]),
                int(L[i][4]),
                int(L[i][5]),
                float(L[i][6]),
                float(L[i][7]),
                int(L[i][8]),
                float(L[i][9])]
    i = i + 1
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo1-12b}
def distance(p1, p2):
    """Renvoie la distance entre deux points définis par leu
     latitude et leur longitude. p1 et p2 sont des tuples
    (latitude,longitude)"""
    # Cette fonction n'est pas à compléter

def coord(l_obs , stat_ref):
    """Renvoie la latitude et la longitude données dans la
    liste d’observation l_obs de la station stat_ref"""
    # Cette fonction est à compléter à la question 8.
    for obs in l_obs :
        if ... :
            return ...,...
            
def liste_stations(l_obs, stat_ref, dist):
    """Renvoie la liste des identifiants ID_STATION des
    stations données dans la liste l_obs situées à une distance
    inférieure à dist de la station de référence stat_ref"""
    # Cette fonction n'est pas à compléter

def nettoyage(l_obs, stat_ref):
    """Renvoie la liste des températures des stations données
    dans la liste d’observations l_obs situées à une distance
    inférieure à 2000 unités de la station de référence
    stat_ref."""
    # Cette fonction est à compléter à la question 10.

def moyenne(L):
    """Calcule et renvoie la moyenne de tous les nombres
    contenus dans la liste passée en paramètre. L est une liste de
    flottants."""
    # Cette fonction est à compléter à la question 11.
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo2-1}
class tube:
    def __init__(self):
        self.taille = 0
        self.contenu = [0, 0, 0]

    def est_vide(self):
        return self.taille == 0

    def empiler(self, couleur):
        if self.taille < 3:
            self.contenu[self.taille] = couleur
            self.taille = self.taille + 1

    def depiler(self):
        if self.taille > 0:
            self.taille = self.taille - 1
            couleur = self.contenu[...]
            self.contenu[self.taille] = 0
            return ...
        else:
            return ...
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo2-1b}
t = tube()
t.taille = 2
t.contenu = [1, 3, 0]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo2-7}
def verser(self, other):
    while ...
        couleur = self.depiler()
        other.empiler(couleur)
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo2-8}
tube1 = tube()
tube1.contenu = [1, 3, 0]
tube1.taille = 2
tube2 = tube()
tube2.contenu = [3, 3, 0]
tube2.taille = 2
tube3 = tube()
tube3.contenu = [2, 2, 0]
tube3.taille = 2
tube4 = tube()
tube4.contenu = [1, 1, 2]
tube4.taille = 3
etat = [tube1, tube2, tube3, tube4]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-2}
>>> voisins(G, 2)
[1, 3, 4, 5]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-3}
>>> degre_du_sommet(G, 2)
4
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-4}
>>> degre_sommets(G)
[(1, 2), (2, 4), (3, 3), (4, 4), (5, 5), (6, 2), (7, 1), (8, 2), (9, 1)]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-4b}
def tri_liste(l_deg):
    """l_deg : liste de tuples (sommets,degré).
    Trie la liste l_deg par degrés décroissants"""
    for i in range(len(l_deg)+1):
        som_max = i
        deg_max = l_deg[i][1]
        for j in range(i+1, len(l_deg)):
            if deg_max < l_deg[j][1]:
                som_max = j
                deg_max = l_deg[j][1]
        temp = l_deg[i]
        l_deg[i] = l_deg[som_max]
        l_deg[som_max] = temp
    return l_deg
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-7}
>>> tri_sommets(G)
[5, 2, 4, 3, 1, 6, 8, 7,9]
\end{filecontents*}

\begin{filecontents*}{AS-25-S2-Exo3-7b}
def coloration(g):
    """Renvoie une coloration du graphe g"""
    # Algorithme de Welsh-Powell, limité à 4 couleurs

    couleur = ['Rouge', 'Bleu', 'Vert', 'Jaune']
    coloration_sommets = {}
    for s_i in g:
        coloration_sommets[s_i] = None
    for s_i in tri_sommets(g):
        couleurs_voisins_s_i = [coloration_sommets[s_j] for s_j in voisins(g, s_i)]
        k = 0
        while couleur[k] in couleurs_voisins_s_i :
            k = k + 1
        coloration_sommets[s_i] = couleur[k]
    return coloration_sommets
\end{filecontents*}


% PREAMBULE
\documentclass[a4paper]{article}

\usepackage{AEIF} 

\SujetBac{\textit{Bac NSI}}{\textbf{Amérique du sud - novembre 2025 - sujet 2}}{\textit{Session 2025}}{}{}{}
	

\newcommand{\Proc}[3]{\draw (#1,0) -- ++(#2,0) -- ++(0,0.75) -- ++(-#2,0) -- cycle; \draw ({#1+#2/2},0.375) node{#3};}	
\newcommand{\car}[2]{\draw[fill=black](#1,#2) -- ++(0.5,0) --++(0,0.5) -- ++(-0.5,0) -- cycle;}

\begin{document}

\title{\vspace{-1cm}\textbf{Amérique du sud - novembre 2025 - sujet 2}}
\date{}

\maketitle

\vspace{-1.5cm}
\Exo{Bases de données, SQL, programmation Python, listes - 6 points}{\ \\
Dans cet exercice, on pourra utiliser les clauses du langage SQL pour :
\itemizes{\item construire des requêtes d’interrogation à l’aide de \texttt{SELECT}, \texttt{FROM}, \texttt{WHERE} (avec les opérateurs logiques \texttt{AND} et \texttt{OR}) et \texttt{JOIN ... ON} ;
\item construire des requêtes d’insertion et de mise à jour à l’aide de \texttt{UPDATE}, \texttt{INSERT} et \texttt{DELETE} ;
\item affiner les recherches à l’aide de \texttt{DISTINCT} et \texttt{ORDER BY}.}
Le but de cet exercice est d’établir une prédiction de la météo du jour en utilisant les observations du jour précédent de plusieurs stations météorologiques voisines.\\\\
\textbf{Partie A}\\
Une version simplifiée des observations peut être représentée sous forme de tables dont la description est donnée ci-dessous. Les clés primaires ont été soulignées et les clés étrangères sont indiquées par un \texttt{\#} :
\setcounter{figure}{0}
\vspace{-0.25cm}\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\draw[fill=LightGray](0,-0.6)rectangle(5,0);
\draw(0,0)rectangle(5,-3.7);
\draw(2.5,-0.3)node{\texttt{station}};
\draw(.5,-1)node[right]{\texttt{\underline{idStat}: INT}};
\draw(.5,-1.6)node[right]{\texttt{nom : TEXT}};
\draw(.5,-2.2)node[right]{\texttt{latitude: REAL}};
\draw(.5,-2.8)node[right]{\texttt{longitude: REAL}};
\draw(.5,-3.4)node[right]{\texttt{hauteur : REAL}};
\draw[->,>=latex](5,-0.9)--(6.5,-0.9)--(6.5,-1.5)--(8,-1.5);
\draw[fill=LightGray](8,-0.6)rectangle(14.4,0);
\draw(8,0)rectangle(14.4,-4.9);
\draw(11.2,-0.3)node{\texttt{observation}};
\draw(8.5,-1)node[right]{\texttt{\underline{idObs} : INT}};
\draw(8.5,-1.6)node[right]{\texttt{\#idStat : INT}};
\draw(8.5,-2.2)node[right]{\texttt{date : TEXT(\squote AAAAMMJJHH\squote)}};
\draw(8.5,-2.8)node[right]{\texttt{precip : REAL}};
\draw(8.5,-3.4)node[right]{\texttt{forceVent : REAL}};
\draw(8.5,-4)node[right]{\texttt{dirVent : INT}};
\draw(8.5,-4.6)node[right]{\texttt{temp : REAL}};
\end{tikzpicture}
\caption{Tables}
\end{figure}
\end{center}
\vspace{-1cm}Dans cette partie, on considère les observations météorologiques de la Nouvelle-Calédonie.
\itemizes{\item La table \texttt{station} contient l’identifiant \texttt{idStat}, le nom \texttt{nom} et les coordonnées géographiques de toutes les stations météorologiques.
\item La table \texttt{observation} contient l’identifiant \texttt{idStat} de l’observation, la date de l’observation \texttt{date}, la hauteur de précipitation \texttt{precip}, la force du vent \texttt{forceVent}, la direction du vent \texttt{dirVent} et la température \texttt{temp} heure par heure de toutes les stations.}
\begin{center}
\renewcommand{\arraystretch}{1.3}
\texttt{\begin{tabular}{|*{5}{c|}}
\hline
\multicolumn{5}{|c|}{\textnormal{Extrait de la table} station}
\tabularnewline\hline
idStat&nom&latitude&longitude&hauteur
\tabularnewline\hline
...&...&...&...&...
\tabularnewline\hline
98818001&NOUMEA&-22.276000&166.452833&69
\tabularnewline\hline
98818002&MAGENTA&-22.260333&166.473667&3
\tabularnewline\hline
...&...&...&...&...
\tabularnewline\hline
\end{tabular}}
\end{center}
\begin{center}
\renewcommand{\arraystretch}{1.3}
\texttt{\begin{tabular}{|*{7}{c|}}
\hline
\multicolumn{7}{|c|}{\textnormal{Extrait de la table} observation}
\tabularnewline\hline
idObs&idStat&date&precip&forceVent&dirVent&temp
\tabularnewline\hline
...&...&...&...&...&...&...
\tabularnewline\hline
123456&98818001&2023123121&0.0&5.7&260&24.4
\tabularnewline\hline
123457&98818001&2023123122&0.0&5.5&260&24.4
\tabularnewline\hline
123458&98818001&2023123123&0.2&5.5&250&24.1
\tabularnewline\hline
123459&98818002&2023010100&0.0&4.7&260&24.1
\tabularnewline\hline
123460&98818002&2023010101&1.4&3.5&80&23.5
\tabularnewline\hline
123461&98818002&2023010102&0.4&2.1&190&23.4
\tabularnewline\hline
123462&98818002&2023010103&0.2&1.7&330&23.4
\tabularnewline\hline
123463&98818002&2023123122&0.1&1.8&310&22.7
\tabularnewline\hline
...&...&...&...&...&...&...
\tabularnewline\hline
\end{tabular}}
\end{center}
\begin{enumerate}
\item Donner le résultat de la requête ci-dessous en considérant les extraits de table fournis.
\end{enumerate}
\CodeInfo{sql}{AS-25-S2-Exo1-1}
\begin{enumerate}[resume]
\item Écrire une requête permettant d’obtenir le nom de toutes les stations météorologiques triées par ordre alphabétique.
\end{enumerate}
En SQL, la fonction d’agrégation \texttt{COUNT} permet de compter le nombre d’enregistrements dans une table. Pour connaître le nombre de lignes totales dans une colonne, la syntaxe est la suivante :
\CodeInfo{sql}{AS-25-S2-Exo1-2}
Par exemple pour compter le nombre de stations météorologiques de la Nouvelle-Calédonie, la requête est la suivante :
\CodeInfo{sql}{AS-25-S2-Exo1-2b}
Dans la table \texttt{observation}, les relevés météorologiques sont effectués au même moment pour toutes les stations (date identique). Ainsi, chaque station a le même nombre de relevés.
\begin{enumerate}[resume]
\item Écrire une requête permettant d’obtenir la force et la direction du vent à BOURAKE le 2 janvier 2023 à 14h.
\item Écrire une requête permettant d’obtenir le nombre total de relevés en Nouvelle-Calédonie.
\end{enumerate}
On souhaite regrouper toutes les informations dans une seule table \texttt{meteo}.
\begin{enumerate}[resume]
\item Écrire le schéma relationnel de la table \texttt{meteo} en supprimant les données \texttt{hauteur}, \texttt{precip}, \texttt{forceVent} et \texttt{dirVent}.\\
\end{enumerate}
\textbf{Partie B}\\
Les données collectées sont stockées dans un unique fichier texte au format csv (\textit{Comma Separated Values}, valeurs séparées par des virgules). Le module Python \texttt{csv} implémente des classes pour lire et écrire des données tabulaires au format csv.\\\\
On fournit ci-dessous un extrait du fichier \texttt{observations.csv} qui donne heure par heure les précipitations en millimètre, la force du vent en mètre par seconde et la direction du vent en degré (de 0 à 360 degrés) ainsi que la température en degré Celsius de la journée du 01/01/2024 pour toutes les stations météorologiques de Nouvelle-Calédonie :
\begin{center}
\begin{figure}[!h]
\centering\includegraphics[scale=0.5]{AS-25-S2-Exo1.png}
\caption{Extrait fichier \texttt{observations.csv}}
\end{figure}
\hfill\textit{Source : d’après \url{meteo.data.gouv}}
\end{center}
Pour la suite de l’exercice, on dispose du code Python donné en annexe ainsi que de la documentation suivante :
\itemizes{\item\python{with open('mon_fichier.csv', 'r') as csvfile} ouvre le fichier\python{mon_fichier.csv} en mode lecture (\texttt{r}) ;
\item\python{csv.reader(csvfile, delimiter=',')} renvoie un objet lecteur, qui itérera sur les lignes de l’objet \texttt{csvfile} donné. Chaque ligne lue depuis le fichier csv est renvoyée comme une liste de chaînes de caractères.}
Dans la console, on saisit la suite d’instructions suivante
\CodeInfo{python}{AS-25-S2-Exo1-5}
\begin{enumerate}[resume]
\item Expliquer cette liste de commande et le résultat obtenu.
\end{enumerate}
Dans la suite de l’exercice, la variable \texttt{liste\_obs} est initialisée avec les valeurs du fichier \texttt{observations.csv}. La fonction \texttt{distance} renvoie la distance entre deux points définis par leur latitude et leur longitude. Cette fonction utilise des fonctions du module Python \texttt{math}.
\begin{enumerate}[resume]
\item Donner la ligne de commande nécessaire à l’utilisation du module Python \texttt{math}.
\end{enumerate}
On rappelle les informations relatives à une observations sont données dans l’ordre suivant :\\\texttt{ID\_STATION,NOM\_STATION,LATITUDE,LONGITUDE,ALTITUDE,AAAAMMJJHH,PRECIPITATION,FORCE\_VENT,\\DIR\_VENT,TEMPERATURE}
\begin{enumerate}[resume]
\item Compléter les lignes 42 et 43 de la fonction \texttt{coord}, qui prend en paramètres une liste d’observations \texttt{l\_obs} et un nom de station \texttt{stat\_ref}, et qui renvoie un tuple composé de sa latitude et sa longitude.
\end{enumerate}
On considère la fonction \texttt{liste\_stations} qui prend en paramètres une liste d’observations \texttt{l\_obs}, un nom de station \texttt{stat\_ref} et un flottant \texttt{dist} et qui renvoie la liste des identifiants \texttt{ID\_STATION} des stations données dans la liste \texttt{l\_obs} situées à une distance inférieure à \texttt{dist} de la station de référence \texttt{stat\_ref}.
\begin{enumerate}[resume]
\item Écrire un algorithme en pseudo-code de la fonction \texttt{liste\_stations}.
\item Écrire une fonction \texttt{nettoyage} qui prend en paramètres une liste d’observations \texttt{l\_obs} et station de référence \texttt{stat\_ref} (nom de la station), et qui renvoie la liste des températures des stations données dans la liste d’observations \texttt{l\_obs} situées à une distance inférieure à $2000$ unités de la station de référence \texttt{stat\_ref}.
\item Écrire la fonction \texttt{moyenne} qui calcule et renvoie la moyenne de toutes les valeurs de type float contenues dans la liste passée en paramètre.
\end{enumerate}
On considère maintenant le fichier \texttt{observations2.csv} donnant heure par heure les observations de la journée du 01/01/2024 pour toutes les stations météorologiques de France.
\begin{enumerate}[resume]
\item Donner les commandes permettant d’obtenir la moyenne des températures des stations situées à moins de $2000$ unités de la station \texttt{Paris\_11} le 1 janvier 2024.\\
\end{enumerate}
\textbf{ANNEXE}
\CodeInfoNum{python}{AS-25-S2-Exo1-12}
\CodeInfoNumStart{python}{31}{AS-25-S2-Exo1-12b}}

\newpage

\Exo{Structure de pile, POO et algorithmique - 6 points}{\ \\
\textbf{Défi Tubes} est un jeu à un joueur. Le joueur dispose de 4 tubes. Chaque tube peut contenir de 0 à 3 phases. Chaque phase possède une couleur. Il y a 3 couleurs possibles. On peut s’imaginer ces phases comme des palets de couleur dans le tube. Pour modéliser les couleurs, on utilisera les entiers 1, 2 et 3. Lorsqu’un tube contient 0 phase, on dit que le tube est vide. Lorsqu’il en a 3, on dit qu’il est plein. Lorsqu’un tube n’est pas vide, sa dernière couleur est la couleur de sa phase supérieure.
\setcounter{figure}{0}
\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\draw(0,3.5)--(0,0)--(1,0)--(1,3.5);
\foreach \y in {1,2,3} \draw(0,\y)--(1,\y);
\draw(-2.5,1.5)node{phases};
\foreach \y in {1,2,3} \draw[->,>=latex] (-1.8,{\y/5+1.1})--(-0.2,{\y-0.5});
\draw[->,>=latex] (1.8,2.5) node[right]{dernière couleur}--(1.2,2.5);
\draw(0.5,2.5)node{1};
\draw(0.5,1.5)node{1};
\draw(0.5,0.5)node{2};
\end{tikzpicture}
\caption{Exemple de tube}
\end{figure}
\end{center}
Le jeu \textbf{Défi Tube} consiste à verser successivement la dernière couleur des tubes dans les autres tubes avec les contraintes suivantes :
\itemizes{\item on ne peut rien verser dans un tube plein ;
\item pour verser un tube 1 dans un tube 2, il faut que la dernière couleur du tube 1 soit la même que celle du tube 2 ou que le tube 2 soit vide. Dans ces deux cas, on retire la dernière couleur du tube 1 pour qu’elle devienne la dernière couleur du tube 2. On réitère cela tant que la dernière couleur du tube 1 est la même et que le tube 2 n’est pas plein.}
Le jeu se termine lorsque 3 des 4 tubes sont pleins et que leurs 3 phases sont de même couleur.\\\\
Les figures 2, 3, 4 et 5 ci-après représentent un exemple de partie du jeu \textbf{Défi Tube}.
\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\foreach \x in {0,3,6,9} {
\draw(\x,3.5)--(\x,0)--({\x+1},0)--({\x+1},3.5);
\foreach \y in {1,2,3} \draw(\x,\y)--({\x+1},\y);}
\foreach \x in {1,2,3,4} \draw({3*\x-2.5},-0.8) node{tube \x};
\draw(0.5,0.5)node{1};
\draw(0.5,1.5)node{3};
\draw(3.5,0.5)node{3};
\draw(3.5,1.5)node{3};
\draw(6.5,0.5)node{2};
\draw(6.5,1.5)node{2};
\draw(9.5,0.5)node{2};
\draw(9.5,1.5)node{1};
\draw(9.5,2.5)node{1};
\end{tikzpicture}
\caption{État initial du jeu}
\end{figure}
\end{center}
\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\foreach \x in {0,3,6,9} {
\draw(\x,3.5)--(\x,0)--({\x+1},0)--({\x+1},3.5);
\foreach \y in {1,2,3} \draw(\x,\y)--({\x+1},\y);}
\foreach \x in {1,2,3,4} \draw({3*\x-2.5},-0.8) node{tube \x};
\draw(0.5,0.5)node{1};
\draw(3.5,2.5)node{3};
\draw(3.5,0.5)node{3};
\draw(3.5,1.5)node{3};
\draw(6.5,0.5)node{2};
\draw(6.5,1.5)node{2};
\draw(9.5,0.5)node{2};
\draw(9.5,1.5)node{1};
\draw(9.5,2.5)node{1};
\end{tikzpicture}
\caption{On a versé le tube 1 dans le tube 2}
\end{figure}
\end{center}
\newpage
\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\foreach \x in {0,3,6,9} {
\draw(\x,3.5)--(\x,0)--({\x+1},0)--({\x+1},3.5);
\foreach \y in {1,2,3} \draw(\x,\y)--({\x+1},\y);}
\foreach \x in {1,2,3,4} \draw({3*\x-2.5},-0.8) node{tube \x};
\draw(0.5,0.5)node{1};
\draw(3.5,2.5)node{3};
\draw(3.5,0.5)node{3};
\draw(3.5,1.5)node{3};
\draw(6.5,0.5)node{2};
\draw(6.5,1.5)node{2};
\draw(9.5,0.5)node{2};
\draw(0.5,1.5)node{1};
\draw(0.5,2.5)node{1};
\end{tikzpicture}
\caption{On a versé le tube 4 dans le tube 1}
\end{figure}
\end{center}
\vspace{-1.25cm}\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\foreach \x in {0,3,6,9} {
\draw(\x,3.5)--(\x,0)--({\x+1},0)--({\x+1},3.5);
\foreach \y in {1,2,3} \draw(\x,\y)--({\x+1},\y);}
\foreach \x in {1,2,3,4} \draw({3*\x-2.5},-0.8) node{tube \x};
\draw(0.5,0.5)node{1};
\draw(3.5,2.5)node{3};
\draw(3.5,0.5)node{3};
\draw(3.5,1.5)node{3};
\draw(9.5,2.5)node{2};
\draw(9.5,1.5)node{2};
\draw(9.5,0.5)node{2};
\draw(0.5,1.5)node{1};
\draw(0.5,2.5)node{1};
\end{tikzpicture}
\caption{On a versé le tube 3 dans le tube 4}
\end{figure}
\end{center}
\vspace{-0.75cm}À la figure 5, la partie est terminée.
\begin{enumerate}
\item Donner un exemple d’une autre séquence de versements permettant de terminer le jeu en partant de la situation de la figure 4.
\end{enumerate}
Ainsi le déroulement du jeu n’est pas unique.\\\\
\textbf{Partie A : les tubes}\\
Pour modéliser le jeu \textbf{Défi Tube}, chaque tube sera représenté par une pile finie de taille maximale 3. Les tubes sont modélisés par des objets de la classe \texttt{tube} dont le code est donné ci-dessous.
\CodeInfoNum{python}{AS-25-S2-Exo2-1}
Chaque instance de la classe \texttt{tube} a deux attributs :
\itemizes{\item l’attribut \texttt{taille} représente le nombre d’éléments non nuls dans le tube;
\item l’attribut \texttt{contenu} représente la liste (de taille 3) des éléments du tube. Lorsqu’une phase n’est pas vide, elle contiendra une couleur 1, 2, ou 3. Lorsqu’une phase est vide, sa valeur est 0.}
\newpage
\noindent Par exemple, le tube suivant :
\vspace{-0.25cm}\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\draw(0,3.5)--(0,0)--(1,0)--(1,3.5);
\foreach \y in {1,2,3} \draw(0,\y)--(1,\y);
\draw(0.5,1.5)node{3};
\draw(0.5,0.5)node{1};
\end{tikzpicture}
\caption{tube 1}
\end{figure}
\end{center}
\vspace{-0.75cm}sera modélisé avec la classe \texttt{tube} par le code :
\CodeInfo{python}{AS-25-S2-Exo2-1b}
\begin{enumerate}[resume]
\item Expliquer ce qu’est la structure de pile en précisant ce que sont les méthodes \texttt{empiler} et \texttt{depiler}.
\item Expliquer les lignes 11 et 12 du code de la classe \texttt{tube}.
\item Recopier et compléter le code de la méthode \texttt{depiler} précédente. Lorsque le tube est vide, la méthode \texttt{depiler} doit renvoyer \texttt{-1}.
\item Écrire une méthode \texttt{est\_plein} de la classe \texttt{tube}. Cette méthode renvoie \texttt{True} si le tube est plein et \texttt{False} si le tube n’est pas plein.
\item Écrire une méthode \texttt{est\_homogene} de la classe \texttt{tube} qui renvoie \texttt{True} si le tube est plein et si son contenu est composé de trois fois la même couleur, et qui renvoie \texttt{False} sinon.
\item Écrire une méthode \texttt{derniere\_couleur} de la classe \texttt{tube} qui renvoie le numéro de la dernière couleur du tube. Si le tube est vide, la méthode renverra la valeur \texttt{-1}.
\end{enumerate}
Le code incomplet d’une méthode \texttt{verser} de la classe \texttt{tube} est donné ci-dessous :
\CodeInfoNum{python}{AS-25-S2-Exo2-7}
\begin{enumerate}[resume]
\item Recopier et compléter le code de cette méthode \texttt{verser} afin de verser l’instance \texttt{self} de la classe \texttt{tube} dans l’instance \texttt{other}. On veillera à vérifier toutes les conditions nécessaires au bon déroulement de cette opération.\\
\end{enumerate}
\textbf{Partie B : le jeu}\\
Pour modéliser le jeu, on appellera état du jeu une liste de 4 tubes. Le code suivant permet de représenter l’état de la figure 2.
\CodeInfo{python}{AS-25-S2-Exo2-8}
\begin{enumerate}[resume]
\item En utilisant la méthode \texttt{verser} et la variable \texttt{etat} représentant la figure 2, écrire un code permettant de faire passer la variable \texttt{etat} de la représentation en figure 2 à celle de la figure 3.
\item Écrire une fonction \texttt{gagne} qui prend comme argument un état et qui renvoie \texttt{True} si la partie est terminée et \texttt{False} sinon.
\end{enumerate}}

\newpage

\Exo{POO, graphes et réseaux - 8 points}{\ \\
\textbf{Partie A}\\
On considère un réseau d’antennes radios, représenté dans la figure 1, où les disques représentent la zone d’émission de chaque antenne. Pour éviter toute interférence, deux antennes \og proches\fg\ géographiquement doivent émettre à des fréquences différentes.
\setcounter{figure}{0}
\begin{center}
\begin{figure}[!h]
\centering\includegraphics[scale=0.6]{AS-25-S2-Exo3}
\caption{Réseau d'antennes}
\end{figure}
\end{center}
On modélise ainsi le réseau d’antennes par un graphe non orienté, appelé graphe d’interférences, dont les sommets sont les antennes numérotées de $1$ à $n$, $n$ étant un entier naturel supérieur ou égal à $1$, et les sommets sont reliés par une arête si leurs zones d’émission s’intersectent.\\\\
Soit \texttt{G} le graphe associé au réseau d’antennes précédent :
\begin{center}
\begin{figure}[!h]
\centering\begin{tikzpicture}
\node[draw,circle](s1) at (0.5,4) {1};
\node[draw,circle](s2) at (2.5,4) {2};
\node[draw,circle](s3) at (4.5,3.7) {3};
\node[draw,circle](s4) at (4,2.5) {4};
\node[draw,circle](s5) at (1.5,2.5) {5};
\node[draw,circle](s6) at (2.7,1.5) {6};
\node[draw,circle](s7) at (.5,1.7) {7};
\node[draw,circle](s8) at (5.5,2.7) {8};
\node[draw,circle](s9) at (6.8,3.5) {9};
\draw (s1) -- (s2);
\draw (s1) -- (s5);
\draw (s2) -- (s3);
\draw (s2) -- (s4);
\draw (s2) -- (s5);
\draw (s3) -- (s4);
\draw (s3) -- (s8);
\draw (s4) -- (s5);
\draw (s4) -- (s6);
\draw (s5) -- (s6);
\draw (s5) -- (s7);
\draw (s8) -- (s9);
\end{tikzpicture}
\caption{Modélisation du réseau sous la forme d’un graphe \texttt{G}}
\end{figure}
\end{center}
Les fréquences à allouer sont associées à des couleurs comme rouge, vert, jaune, bleu, etc. Pour éviter les interférences, la coloration doit être une coloration propre : deux sommets adjacents ne peuvent recevoir la même couleur.\\\\
Dans cet exercice, on représente le graphe \texttt{G} par un dictionnaire de listes d’adjacence dont les clefs sont les sommets de type int et les valeurs sont des listes de voisins du sommet clef, chaque liste contenant des éléments de type int.
\begin{enumerate}
\item Donner la valeur associée à la clé \texttt{1} dans ce dictionnaire.
\item Écrire une fonction \texttt{voisins}, qui prend en paramètres un dictionnaire et un entier, telle que \texttt{voisins(graphe, k)} renvoie une liste contenant les voisins du sommet \texttt{k} dans le graphe qui est modélisé par le dictionnaire de listes d’adjacence graphe.\\
Par exemple :
\end{enumerate}
\CodeInfo{python}{AS-25-S2-Exo3-2}
L’algorithme de Welsh et Powell consiste à colorer séquentiellement le graphe en visitant les sommets par ordre de degrés décroissants. Le degré d’un sommet d’un graphe non orienté est le nombre d’arêtes dont le sommet est une extrémité. L’idée est que les sommets ayant beaucoup de voisins sont plus difficiles à colorer : il faut les colorier en premier.
\begin{enumerate}[resume]
\item Écrire la fonction \texttt{degre\_du\_sommet} qui prend en paramètres un graphe modélisé par le dictionnaire de listes d’adjacence \texttt{graphe} et un sommet \texttt{sommet} et qui renvoie le degré du sommet \texttt{sommet}.\\
Par exemple :
\end{enumerate}
\CodeInfo{python}{AS-25-S2-Exo3-3}
\begin{enumerate}[resume]
\item Écrire la fonction \texttt{degre\_sommets} qui prend en paramètre un graphe modélisé par le dictionnaire de listes d’adjacence \texttt{graphe} et qui renvoie la liste des tuples \texttt{(sommet, degre)} de chaque sommet du graphe.\\
Par exemple :
\end{enumerate}
\CodeInfo{python}{AS-25-S2-Exo3-4}
On définit la fonction \texttt{tri\_liste} ci-après :
\CodeInfoNum{python}{AS-25-S2-Exo3-4b}
À l’exécution, \texttt{tri\_liste([(1, 2), (2, 2), (3, 3)])} renvoie l’erreur suivante :
\begin{center}\texttt{IndexError: list index out of range}\end{center}
\begin{enumerate}[resume]
\item Commenter puis corriger cette erreur.
\item Choisir parmi les tris proposés celui qui correspond à la fonction \texttt{tri\_liste} : tri par insertion, tri par sélection, tri fusion, tri bulle.
\item Écrire une fonction \texttt{tri\_sommets} qui prend en paramètre un graphe \texttt{graphe} et qui ne renvoie que la liste des sommets du graphe \texttt{graphe} triés par degré décroissant. On pourra utiliser les fonctions définies dans les questions précédentes.\\
Par exemple :
\end{enumerate}
\CodeInfo{python}{AS-25-S2-Exo3-7}
On suppose que le graphe est planaire, c’est-à-dire qu’il existe une représentation de ce graphe dans un plan pour laquelle les arêtes ne se croisent pas, et on définit la fonction \texttt{coloration} ci-après.
\CodeInfoNum{python}{AS-25-S2-Exo3-7b}
\begin{enumerate}[resume]
\item Donner le type et le contenu de la variable \texttt{coloration\_sommets} de la fonction \texttt{coloration} ci-dessus pour le graphe \texttt{G}, après execution de la boucle des lignes 7 et 8.
\item Recopier et compléter le renvoi de la fonction \texttt{coloration} appliquée au graphe \texttt{G} donné plus haut.\\
\python{\{1: 'Vert', 2: ..., ...\}}
\end{enumerate}
\newpage
\noindent\textbf{Partie B}\\
On s’intéresse maintenant à un réseau informatique.
\vspace{-0.5cm}\begin{center}
\begin{figure}[!h]
\centering\includegraphics[scale=0.55]{AS-25-S2-Exo3b}
\caption{Réseau entreprise}
\end{figure}
\end{center}
\vspace{-0.5cm}Dans cette partie, les adresses IP sont composées de $4$ octets, soit $32$ bits. Elles sont notées \texttt{X1.X2.X3.X4}, où \texttt{X1}, \texttt{X2}, \texttt{X3} et \texttt{X4} sont les représentations décimales des quatre octets. La notation \texttt{X1.X2.X3.X4/n} signifie que les \texttt{n} premiers bits de l’adresse IP représentent la partie \og réseau \fg, les bits suivants représentent la partie \og hôte\fg.\\\\
On fournit les données suivantes concernant le réseau de cette entreprise.
\itemizes{\item Réseau local L1 :
\itemizeb{\item Adresse IP de l’ordinateur P1 : \texttt{190.12.10.25/24}
\item S1 : switch}
\item Réseau local L2 :
\itemizeb{\item Adresse réseau : \texttt{12.128.0.0}
\item Masque de sous réseau : \texttt{255.255.0.0}
\item S2 : switch
\item P2 : ordinateur\\}}
Extrait de l’arborescence du système de fichiers de l’ordinateur P2 :
\begin{center}
\begin{figure}[!h]
\centering\texttt{\begin{tikzpicture}[scale=1.4]
\node(a) at (0,5) {/};
\node[draw, rectangle](b1) at (-3,4) {bin};
\node[draw, rectangle](b2) at (-1,4) {etc};
\node[draw, rectangle](b3) at (1,4) {home};
\node[draw, rectangle](b4) at (3,4) {lib};
\node[draw, rectangle](c1) at (-1,3) {picky};
\node[draw, rectangle](c2) at (1,3) {maurice};
\node[draw, rectangle](c3) at (3,3) {timothee};
\node[draw, rectangle](d1) at (-1,2) {travail};
\node[draw, rectangle](d2) at (2,2) {photos};
\node(d3) at (4,2) {fic1.txt};
\node[draw, rectangle](d4) at (6,2) {important};
\node[draw, rectangle](e1) at (-3,1) {TP};
\node[draw, rectangle](e2) at (-0.5,1) {cours};
\node(e3) at (2,1) {photo1.png};
\node(e4) at (6,1) {prog1.py};
\node(f) at (-3,0) {prog2.py};
\draw (a) -- (b1);
\draw (a) -- (b2);
\draw (a) -- (b3);
\draw (a) -- (b4);
\draw (b3) -- (c1);
\draw (b3) -- (c2);
\draw (b3) -- (c3);
\draw (c3) -- (d1);
\draw (c3) -- (d2);
\draw (c3) -- (d3);
\draw (c3) -- (d4);
\draw (d1) -- (e1);
\draw (d1) -- (e2);
\draw (d2) -- (e3);
\draw (d4) -- (e4);
\draw (e1) -- (f);
\end{tikzpicture}}
\caption{Arborescence}
\end{figure}
\end{center}
\newpage
\noindent Extrait du manuel de la commande \texttt{cp} :
\begin{center}
\begin{figure}[!h]
\centering\includegraphics[scale=0.55]{AS-25-S2-Exo3c}
\caption{Manuel de la commande \texttt{cp}}
\end{figure}
\end{center}
\begin{enumerate}[resume]
\item Donner une commande en ligne qui permet de copier le fichier \texttt{prog1.py} dans le répertoire \texttt{TP} lorsqu’on se trouve dans le répertoire nommé \texttt{important}.
\item Donner la commande qui permet de vérifier si l’ordinateur P1 est accessible lorsque l’on travaille sur l’ordinateur P2.
\item Donner une adresse possible pour l’ordinateur P2 du réseau local L2.
\end{enumerate}
Dans le cadre du protocole RIP, le chemin emprunté par les informations est celui qui aura la distance la plus petite en nombre de sauts. Dans le cadre du protocole OSPF, le chemin emprunté par les informations est celui qui aura le coût total minimal.\\\\
Extraits des tables de routage :
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{|c|c|c|}
\hline
Routeur&Destination&Passerelle
\tabularnewline\hline
R1&R9&R2
\tabularnewline\hline
R2&R9&R3
\tabularnewline\hline
R3&R9&R8
\tabularnewline\hline
R4&R9&R3
\tabularnewline\hline
R5&R9&R4
\tabularnewline\hline
R6&R9&R4
\tabularnewline\hline
R7&R9&R5
\tabularnewline\hline
R8&R9&R9
\tabularnewline\hline
R9&R9&LOCALHOST
\tabularnewline\hline
\end{tabular}
\end{center}
\begin{enumerate}[resume]
\item Donner le chemin emprunté par un paquet de données allant de l’ordinateur P1 à l’ordinateur P2, en utilisant l’extrait de la table de routage.
\item Donner le nom du protocole de routage qui semble être utilisé.
\end{enumerate}
Dans les questions suivantes, on utilise le protocole de routage OSPF.\\\\
Pour calculer le coût $C$ d’une liaison, on utilise la formule :
$$C = \dfrac{10^8}{BP},$$
où $BP$ est la bande passante en bits par seconde.
\begin{enumerate}[resume]
\item Calculer les coûts pour des liaisons de $100$ Mbits/s, $1$ Gbits/s et $10$ Gbits/s.
\item Déterminer la route qui sera empruntée par le paquet de données envoyé de l’ordinateur P1 à l’ordinateur P2, en respectant le protocole OSPF.
\end{enumerate}}

\end{document}