\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}}
\newcommand{\mis}[1]{\texttt{#1}}
\usepackage{hyperref}
\usepackage{pstricks,pst-plot,pst-3dplot,pst-grad,pst-tree,pst-math,pst-eucl}
\usepackage{pst-plot,pst-tree,pst-eucl,pst-math,pstricks-add}
\usepackage[margin=1cm,bottom=1.5cm]{geometry}
\begin{document}
\fbox{\textsc{25NSIJ2G11}}


\bigskip

\textbf{Exercice 1} (6 points)

\medskip

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

\begin{enumerate}
\item Le rôle des clés primaires est de pouvoir identifier de façon unique un enregistrement d'une table.

\item Sans le champ \mis{id\_match}, on ne pourrait pas stocker dans la table \mis{match} deux matchs entre les mêmes équipes dans le même ordre et avec le même score final (et donc le même gagnant).

\item Sur l'extrait présenté, \mis{SELECT prenom FROM joueur WHERE ann\_naiss < 1985;} renvoie la table :

\begin{center}
\begin{tabular}{|c|}
\hline
prenom\\
\hline
Henri\\
Laure\\
Brigitte\\
Laure\\
\hline
\end{tabular}
\end{center}

\item  \mis{SELECT DISTINCT prenom FROM joueur WHERE ann\_naiss < 1985;} permet d'éviter les doublons. 

\item \mis{SELECT nom, ann\_naiss, num\_port FROM joueur WHERE commune="Bois-Plage";} convient.

\item On utilise une jointure puisqu'on a besoin des deux tables \mis{joueur} et 
\mis{equipe}.

\mis{SELECT joueur.nom, prenom FROM joueur JOIN equipe ON joueur.id\_joueur = equipe.j\_1}

\mis{WHERE equipe.nom = "Les Kangourous";}

\item La requête \mis{UPDATE equipe SET points = 5 WHERE nom = "Volley Warriors";} effectue la mise à jour demandée.

\item La requête \mis{DELETE FROM joueur WHERE id\_joueur = 35;} supprime le joueur d'identifiant 35 (en supposant que ce joueur est d'abord supprimé de l'équipe des Volley Warriors dans la table \mis{equipe} faute de quoi on peut avoir une erreur de violation de contrainte de référence).

\item \mis{SELECT id\_match FROM match WHERE eq\_1 = 12 OR eq\_2 = 12;} convient.

\item \mis{SELECT id\_match FROM match JOIN equipe ON match.eq\_1 = equipe.id\_equipe JOIN joueur}

\mis{ON equipe.j\_1 = joueur.id\_joueur WHERE commune = "Bois-Plage";} convient.  

\item \mis{SELECT DISTINCT joueur.nom, prenom FROM joueur JOIN equipe ON joueur.id\_joueur = equipe.j\_1}

\mis{JOIN match ON equipe.id\_equipe = eq\_gagnante ORDER BY joueur.nom, prenom ;}

permet de joindre les trois tables pour répondre à la question posée.

\end{enumerate}


\bigskip

\textbf{Exercice 2} (6 points)


\medskip

\textit{Cet exercice porte sur les listes, les dictionnaires, les fonctions et la récursivité}

\medskip

\textbf{Partie A}

\begin{enumerate}

\item En ASCII, \mip{'E'} est codé par \mip{0x45} et \mip{'W'} par \mip{Ox57}, la somme est \mip{0x9C} soit une clé égale à $9\times16+12=156$.

  

\item Les mots \mip{'SAC'} et \mip{'CAS'} ont la même clé puisqu'ils contiennent exactement les mêmes lettres, on ajoute les même codes ASCII.

\item On complète les lignes 2 à 4 dans la fonction \mip{code_hachage}.

\begin{minted}[linenos]{python}
def code_hachage(mot):
    somme = 0
    for caractere in mot:
        somme = somme + ord(caractere)
    return somme % 0x100
\end{minted}

\item L'expression \mintinline{python}{somme % 0x100} permet d'obtenir le reste dans la division entière de somme par \mip{0x100} c'est-à-dire 256. Autrement dit on ne garde que l'octet de poids faible de la somme, comme voulu. 


\end{enumerate}

\newpage

\textbf{Partie B}



\begin{enumerate}[resume]
\item La boucle \mip{while} des lignes 3-10 contient exactement une comparaison de chaînes ligne 4. Or cette boucle est exécutée au pire des cas \mip{len(liste)} comme on peut le voir grâce au variant de boucle \mip{i}. 
La complexité est donc linéaire en $n$.

\item L'expression booléenne \mip{c in dico} permet de savoir si la clé \mip{c} est une clé du dictionnaire \mip{dico}. 

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

\begin{minted}{python}
def ajouter_mot_dict(dict_mots, mot):
    h = code_hachage(mot)
    if h in dict_mots:
        ajouter_mot_liste(dict_mots[h], mot)
    else:
        dict_mots[h]=[mot]
\end{minted}


\end{enumerate}
\bigskip



\textbf{Partie C}



\begin{enumerate}[resume]
\item Dans l'exemple donné, les valeurs successives de \mip{debut} et \mip{fin} sont données dans le tableau ci-dessous.

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
appel&0&1&2\\
\hline
\mip{debut}&0&0&1\\
\hline
\mip{fin}&5&1&1\\
\hline
\end{tabular}
\end{center}

\item Une recherche simple nécessite dans le pire des cas d'examine r tous les mots un par un un, alors qu'avec une recherche dichotomique on élimine la moitié des mots candidats à chaque comparaison. 

\item La complexité de la recherche dichotomique est logarithmique, en $O(\log_2 (n))$ pour une liste de longueur $n$.

\item On écrit la fonction demandée.

\begin{minted}{python}
def mot_present(dict_mots, mot):
    h = code_hachage(mot)
    mots = dict_mots[h]
    return est_present(mots, mot, 0, len(mots))
\end{minted}

\end{enumerate}
\bigskip


\textbf{Exercice 3} (8 points)

\medskip

\textit{Cet exercice porte sur les graphes, la programmation objet et la récursivité.}

\medskip

\begin{enumerate}
\item Le chemin 3 -> 9 -> 1 -> 2 -> 4 -> 8 est non prolongeable.


\end{enumerate}

\bigskip

\textbf{Partie A}



\begin{enumerate}[resume]
\item Le \mip{for valeur in range(1, n+1)} signifie que la variable \mip{valeur} prendra les valeurs \mip{1, 2 , ..., n} bornes incluses.

\item Après l'exécution du code \mip{jeu_9 = creer_jeu(9)}, la valeur de \mip{jeu_9[0].valeur} est \mip{1}.

\item À la ligne 5 on vérifie que la valeur de \mip{s} est un diviseur de la valeur de \mip{self} et que \mip{s} et \mip{self} sont distincts. 

\item Après l’exécution de \mip{jeu_9[5].relier_diviseurs(jeu)}, le contenu de \mip{jeu_9[5].diviseurs} la liste des sommets dont la valeur divise 6,  \mip{[jeu_9[1], jeu_9[1], jeu_9[2]]}.

\item On écrit la ligne 6.

\begin{minted}[linenos,firstnumber=6]{python}
        sommet.relier_diviseurs(jeu)
\end{minted}

\item On complète la ligne 3 du code de la méthode \mip{liste_diviseurs}.

\begin{minted}[linenos,firstnumber=3]{python}
        return [sommet.valeur for sommet in self.diviseurs] 
\end{minted}

\item On complète le jeu de tests en utilisant l'exemple \mip{jeu9}.

\begin{minted}[linenos]{python}
l_div_3 = jeu9[2].lister_diviseurs()
l_mult_3 = jeu9[2].lister_multiples()
assert 1 in l_div_3
assert 6 in l_mult_3
assert 9 in l_mult_3
\end{minted}

\end{enumerate}

\bigskip

\textbf{Partie B}



\begin{enumerate}[resume]
\item La ligne \mip{assert not self.est_vide()} interrompra l'exécution du programme si la file est vide.

\item On complète le code de la méthode \mip{taille}.

\begin{minted}[linenos]{python}
    def taille(self):
        return len(self.donnees) - self.decalage
\end{minted}

\item On écrit le jeu de test demandé.

\begin{minted}[linenos]{python}
f = File()
f.enfiler(1)
f.enfiler(2)
f.enfiler(3)
assert f.taille() == 3
u = f.defiler()
assert u == 1
v = f.defiler()
assert v == 2
w = f.defiler()
assert w == 3
assert f.est_vide()
\end{minted}

\end{enumerate}




\bigskip

\textbf{Partie C}



\begin{enumerate}[resume]
\item On complète le code de la fonction \mip{rechercher_chemins}.




\begin{minted}[linenos]{python}
def rechercher_chemins(jeu):
    chemins_np = []
    f = File()
    for sommet in jeu:
        f.enfiler([sommet])
        while not f.est_vide():
            chemin = f.defiler()
            dernier = chemin[-1]
            voisins = dernier.diviseurs + dernier.multiples
            prolongeable = False
            for voisin in voisins:
                if voisin not in chemin:
                    prolongeable = True
                    f.enfiler(chemin + [voisin])
            if not prolongeable:
                chemins_np.append(chemin)
    return chemins_np
\end{minted}


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




\begin{minted}[linenos]{python}
def valeurs_chemin(chemin):
    return [sommet.valeur for sommet in chemin]
\end{minted}


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

\begin{minted}[linenos]{python}
chemins = []
for chemin in rechercher_chemins(jeu9):
    chemins.append(valeurs_chemin(chemin))
\end{minted}


\newpage

\item On écrit le code de la fonction \mip{extraire_plus_longs_chemins}.


\begin{minted}[linenos]{python}
def extraire_plus_longs_chemins(L_chemins):
    plc=[]  # plus longs chemins
    lmax=0  # longueur maximale
    for chemin in L_chemins:
        if len(chemin) > lmax:
            plc = [chemin]
        elif len(chemin) == lmax:
            pls.append(chemin)
    return plc
\end{minted}


\item Le nombre de chemins semble croître de manière rapide, peut-être exponentielle. Cela signifie que pour un nombre de sommets de l'ordre de quelques dizaines on aura besoin d'un meilleur algorithme, ou bien d'un plus gros ordinateur.



\end{enumerate}






\end{document}



\begin{minted}{python}

\end{minted}
