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

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


\bigskip

\textbf{Exercice 1} (6 points)

\medskip

\textit{Cet exercice porte sur la décidabilité, l’algorithmique et la programmation en Python.}

\begin{enumerate}
\item Après l'exécution du programme contenu dans la variable \mip{programme1}, \mip{x} vaut \mip{0} et \mip{y} vaut \mip{20}.

\item Un programme Python est un fichier texte et peut donc être vu comme une chaîne de caractères.

\item Les programmes 3 et 5 terminent, les 4 et 6 ne terminent pas.

\item La fonction \mip{arret_essai1} renvoie \mip{True} si le programme passé en paramètre termine, ce qui permet de répondre partiellement au problème. Cependant si ce programme passé en paramètre ne termine pas alors la fonction \mip{arret_essai1} ne termine pas et ne renvoie donc pas le \mip{False} attendu. 

\item Le principe de l'algorithme Boyer-Moore est de chercher un \mip{motif} de longueur \mip{m} dans un \mip{texte} de longueur \mip{t} en alignant le motif avec le début du texte, en position \mip{i=0} puis de comparer \mip{motif[j]} avec \mip{texte[i+j]} en partant de \mip{j=m-1} vers \mip{j=0}. Si on arrive à \mip{j==0} avec des comparaisons vraies, on a trouvé une occurrence du motif et on renvoie \mip{True}. Sinon, en fonction de l'indice \mip{j} où la comparaison échoue, on peut décaler le motif d'un nombre de positions qui dépend de la lettre \mip{texte[i+j]}. On recommence à la nouvelle position ; si on dépasse la fin du texte (si \mip{i>t-m}) alors on renvoie \mip{False}. 


\item On écrit la fonction demandée. 
\begin{minted}{python}
def arret_essai2(programme):
    return not recherche('while',programme)
\end{minted}




\item Les programmes 7 et 8 correspondent aux deux cas à mettre en évidence. On a utilisé une fonction récursive dans le programme 7, qui crée l'équivalent d'une boucle infinie.

\begin{minted}{python}
programme7="""
def boucle_infinie():
    boucle_infinie()
boucle_infinie()
"""
\end{minted}

\begin{minted}{python}
programme8="""
n=10
while n>0:
    n=n-1
"""
\end{minted}


\item On écrit la fonction demandée.

\begin{minted}{python}
def terminaison_inverse(programme):
    if arret(programme):
        boucle_infinie()
\end{minted}

\item Si \mip{programme_paradoxal} termine, alors \mip{programme_paradoxal} ne termine pas 

puisque \mip{programme_paradoxal="terminaison_inverse(programme_paradoxal)"}, par construction de la fonction \mip{terminaison_inverse}.

Si \mip{programme_paradoxal} ne termine pas, alors \mip{programme_paradoxal} termine 

puisque \mip{programme_paradoxal="terminaison_inverse(programme_paradoxal)"}, par construction de la fonction \mip{terminaison_inverse}.

Mais \mip{programme_paradoxal} ne peut pas à la fois terminer et ne pas terminer, c'est absurde.

\item On a prouvé par l'absurde qu'une fonction \mip{arret} telle que décrite ne peut exister. 

\item Ce résultat est un résultat général qui n'est pas dû aux limitations de langage Python.
\end{enumerate}

\newpage

\textbf{Exercice 2} (6 points)


\medskip

\textit{Cet exercice porte sur les arbres et la compression d’un fichier texte.}

\medskip

\textbf{Partie A}

\begin{enumerate}
\item Avec l'encodage ISO8859-1, chaque caractère est codé sur un octet\footnote{Ce n'est pas le cas en général, p.ex UTF8 code chaque caractère sur un à quatre octets.} donc \mip{txt="SIX ANANAS"}, qui comporte dix caractères en comptant l'espace, est codé sur dix octets soit quatre-vingt bits. 

\item Le codage de \mip{txt} est 53495820414E414E4153.
\end{enumerate}

\bigskip

\textbf{Partie B}



\begin{enumerate}[resume]
\item Le tableau d'occurrences associé à la chaîne \mip{txt} est :

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Symbole&SP&A&I&N&S&X\\
\hline
Nombre d'occurrences&1&3&1&2&2&1\\
\hline
\end{tabular}
\end{center}

dans l'ordre alphabétique des symboles.


\item La somme des nombres d'occurrences est le nombre de caractères de la chaîne, donc le nombre d'octets utilisé pour coder cette chaîne avec l'encodage ISO8859-1.


\item On a complété le code.


\begin{minted}{python}
def occurrence(texte):
    dico={}
    for lettre in texte:
        if lettre in dico:
            dico[lettre] = dico[lettre]+1
        else:
            dico[lettre] = 1
    return dico
\end{minted}

\item On construit l'arbre de Huffman, en partant du tableau de la question 3\footnote{L'ordre initial aurait été \psset{unit=6mm}
\begin{pspicture}(-1,-0.5)(7,1.5)
\cnodeput(0,0){SP}{1}\rput(0,-1){I}
\cnodeput(1,0){I}{1}\rput(1,-1){X}
\cnodeput(2,0){X}{1}\rput(2,-1){SP}
\cnodeput(3,0){N}{2}\rput(3,-1){S}
\cnodeput(4,0){S}{2}\rput(4,-1){N}
\cnodeput(5,0){A}{3}\rput(5,-1){A}
\end{pspicture} avec le \mip{dict} obtenu par la fonction de la question 5.}.

%S:2,I:1,X:1,SP:1,A:3,N:2


\begin{center}
\begin{minipage}{20cm}
\psset{unit=8mm}
\begin{pspicture}(-1,-11)(8,0.5)
\cnodeput(0,0){SP}{1}\rput(0,-1){SP}
\cnodeput(1,0){I}{1}\rput(1,-1){I}
\cnodeput(2,0){X}{1}\rput(2,-1){X}
\cnodeput(3,0){N}{2}\rput(3,-1){N}
\cnodeput(4,0){S}{2}\rput(4,-1){S}
\cnodeput(5,0){A}{3}\rput(5,-1){A}
\rput(6.5,0){Étape 0}

\cnodeput(1,-4){SP}{1}\rput(1,-5){SP}
\cnodeput(2,-4){I}{1}\rput(2,-5){I}
\cnodeput(1.5,-2.5){SPI}{2}\ncline{SPI}{SP}\ncline{SPI}{I}
\cnodeput(0,-4){X}{1}\rput(0,-5){X}
\cnodeput(3,-4){N}{2}\rput(3,-5){N}
\cnodeput(4,-4){S}{2}\rput(4,-5){S}
\cnodeput(5,-4){A}{3}\rput(5,-5){A}
\rput(4.5,-3){Étape 1}

\cnodeput(3,-9.5){SP}{1}\rput(3,-10.5){SP}
\cnodeput(4,-9.5){I}{1}\rput(4,-10.5){I}
\cnodeput(3.5,-8){SPI}{2}\ncline{SPI}{SP}\ncline{SPI}{I}
\cnodeput(2,-9.5){X}{1}\rput(2,-10.5){X}
\cnodeput(2.75,-6.5){XSPI}{3}\ncline{XSPI}{X}\ncline{XSPI}{SPI}
\cnodeput(0,-9.5){N}{2}\rput(0,-10.5){N}
\cnodeput(1,-9.5){S}{2}\rput(1,-10.5){S}
\cnodeput(5,-9.5){A}{3}\rput(5,-10.5){A}
\rput(5,-7){Étape 2}

\cnodeput(10,-3){SP}{1}\rput(10,-4){SP}
\cnodeput(11,-3){I}{1}\rput(11,-4){I}
\cnodeput(10.5,-1.5){SPI}{2}\ncline{SPI}{SP}\ncline{SPI}{I}
\cnodeput(9,-3){X}{1}\rput(9,-4){X}
\cnodeput(9.75,0){XSPI}{3}\ncline{XSPI}{X}\ncline{XSPI}{SPI}
\cnodeput(12,-3){N}{2}\rput(12,-4){N}
\cnodeput(13,-3){S}{2}\rput(13,-4){S}
\cnodeput(12.5,-1.5){NS}{4}\ncline{NS}{N}\ncline{NS}{S}
\cnodeput(8,-3){A}{3}\rput(8,-4){A}
\rput(12,-0.5){Étape 3}

\cnodeput(10,-10){A}{3}\rput(10,-11){A}
\cnodeput(12,-10){SP}{1}\rput(12,-11){SP}
\cnodeput(13,-10){I}{1}\rput(13,-11){I}
\cnodeput(12.5,-8.5){SPI}{2}\ncline{SPI}{SP}\ncline{SPI}{I}
\cnodeput(11,-10){X}{1}\rput(11,-11){X}
\cnodeput(11.75,-7){XSPI}{3}\ncline{XSPI}{X}\ncline{XSPI}{SPI}
\cnodeput(10.9,-5.5){AXSPI}{6}\ncline{AXSPI}{A}\ncline{AXSPI}{XSPI}
\cnodeput(8,-10){N}{2}\rput(8,-11){N}
\cnodeput(9,-10){S}{2}\rput(9,-11){S}
\cnodeput(8.5,-8.5){NS}{4}\ncline{NS}{N}\ncline{NS}{S}
\rput(9,-7){Étape 4}

\cnodeput(18,-6){A}{3}\rput(18,-7){A}
\cnodeput(20,-6){SP}{1}\rput(20,-7){SP}
\cnodeput(21,-6){I}{1}\rput(21,-7){I}
\cnodeput(20.5,-4.5){SPI}{2}\ncline{SPI}{SP}\ncline{SPI}{I}
\cnodeput(19,-6){X}{1}\rput(19,-7){X}
\cnodeput(19.75,-3){XSPI}{3}\ncline{XSPI}{X}\ncline{XSPI}{SPI}
\cnodeput(18.9,-1.5){AXSPI}{6}\ncline{AXSPI}{A}\ncline{AXSPI}{XSPI}
\cnodeput(16,-6){N}{2}\rput(16,-7){N}
\cnodeput(17,-6){S}{2}\rput(17,-7){S}
\cnodeput(16.5,-4.5){NS}{4}\ncline{NS}{N}\ncline{NS}{S}
\cnodeput(17.7,0){NSAXSPI}{10}\ncline{NSAXSPI}{NS}\ncline{NSAXSPI}{AXSPI}
\rput(20,0){Étape 5}

\rput(16,-5.25){0}\rput(17,-5.25){1}
\rput(20,-5.25){0}\rput(21,-5.25){1}
\rput(19.15,-4.5){0}\rput(20.3,-3.5){1}
\rput(18.2,-3.75){0}\rput(19.6,-2.25){1}
\rput(16.8,-2.25){0}\rput(18.6,-0.75){1}

\end{pspicture}
\end{minipage}
\end{center}


\item Le poids de la racine de cet arbre, 10, est la longueur de la chaîne.
\item Il s'agit d'un parcours en profondeur pour lequel on stockera un couple \mip{symbole:code} pour chaque feuille parcourue.
\item La table de codage est donnée par ce tableau.

\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
Symbole&N&S&A&X&SP&I\\
\hline
Code&00&01&10&110&1110&1111\\
\hline

\end{tabular}
\item Le symbole N est codé sur deux bits, le symbole I sur quatre bits, donc le codage de Huffman est de longueur variable. 
\item La chaîne \mip{txt} est codée par 0111111101110100010001001, sur 25 bits.
\item Le taux de compression est $\dfrac{80-25}{80}=0,6875$ soit 68,75 \,\% (malheureusement il faut aussi garder trace de l'arbre de décodage).

\end{enumerate}

\bigskip

\textbf{Exercice 3} (8 points)

\medskip

\textit{Cet exercice porte sur les dictionnaires et leurs algorithmes associés, le traitement de données en table, la sécurisation des communications et la programmation en général.}

\textbf{Partie A}

\begin{enumerate}
\item La requête \mis{SELECT "id-kimono" FROM location WHERE fin='';} convient. 
\item La requête \mis{SELECT COUNT("id-kimono") FROM kimono WHERE "taille-kimono"=130;} convient.
\item La requête \mis{SELECT nom, prenom FROM adherent JOIN location}

\mis{ON adherent."numero-licence"=location."numero-licence" WHERE "id-kimono"=42 AND fin='';} convient.
\item La requête \mis{UPDATE adherent SET "taille-adherent"="taille-adherent"+10}


\mis{WHERE "taille-adherent"<160;} convient.
\item Les requêtes \mis{DELETE FROM location WHERE "id-kimono"=25;} 

puis \mis{DELETE FROM kimono WHERE "id-kimono"=25;}, dans cet ordre, conviennent.

\end{enumerate}

NOTA BENE L'utilisation de - dans les noms des champs oblige à utiliser des \textit{identificateurs délimités} par des guillemets doubles dans les requêtes ci-dessus.
\bigskip

\textbf{Partie B}



\begin{enumerate}[resume]
\item Eddie Nirrer peut avoir comme numéro de licence M12102021NIRRE01 par exemple.
\item Cet adhérent est né le 23 septembre 1974, il peut s'appeler Marti.
\item L'expression \mip{tab_adherents[1]['prenom']} permet d'accéder à la chaîne \mip{'STEPHANIE'}.
\item On accède à \mip{'F03071997DUPON01'} par \mip{tab_adherents[0]['numero-licence']}.

\item On complète la fonction demandée.

\begin{minted}{python}
def nombre_adherents(table, annee):
    compteur = 0
    for adherent in table:
        if adherent['annee'] == annee:
            compteur = compteur + 1
    return compteur
\end{minted}

\item On écrit la fonction demandée.

\begin{minted}{python}
def adherent_plus_age(table):
    res = [table[0]]
    annee = table[0]['annee']
    for i in range(1, len(table)):
        adherent = table[i]
        if adherent['annee'] == annee:
            res.append(adherent)
        if adherent['annee'] < annee:
            res = [adherent]
            annee = adherent['annee']
    return res
\end{minted}

\item On écrit la fonction demandée.

\begin{minted}{python}
def verification_licence(adherent):
    licence = adherent['numero-licence']    
    if extraire(licence, 0, 1) != adherent['sexe']:
        return False
    if extraire(licence, 1, 3) != adherent['jour']:
        return False
    if extraire(licence, 3, 5) != adherent['mois']:
        return False
    if extraire(licence, 5, 9) != adherent['annee']:
        return False
    if extraire(licence, 9, 14) != extraire(adherent['nom'], 0, 5):
        return False
    return True
    
\end{minted}


ou bien 

\begin{minted}{python}
def verification_licence(adherent):
    licence = adherent['numero-licence']    
    return extraire(licence, 0, 1) == adherent['sexe'] \
        and extraire(licence, 1, 3) == adherent['jour'] \
        and extraire(licence, 3, 5) == adherent['mois'] \
        and extraire(licence, 5, 9) == adherent['annee'] \
        and extraire(licence, 9, 14) == extraire(adherent['nom'], 0, 5) \
\end{minted}
\end{enumerate}





\end{document}