\thumb

\begin{qcm}{Vérification de connaissances}{5} % titre , temps
% https://info.sio2.be/infobase/6/9.php
\begin{questions}
\item Un ordinateur comprend mieux:

\begin{tabularx}{\linewidth}{@{}l@{~}X@{}}
\choix &des instructions en anglais;\\
\choix &des instructions en langage binaire (0 et 1);\\
\choix &des instructions exprimées en langage d'ordinateur (Fortran,\linebreak Python,...)
\end{tabularx}


\item \resetchoix Lorsque l'on rédige un programme pour un ordinateur, on utilise:

\choix un langage informatique comme C, Basic, PHP,...;

\choix le langage binaire (0 et 1) obligatoirement;

\choix de préférence l'anglais.


\item \resetchoix Si on veut pouvoir modifier aisément un programme, il vaut mieux\linebreak disposer:

\begin{tabularx}{\linewidth}{@{}l@{~}X@{}}
\choix &du programme binaire; \\
\choix &du programme source;\\
\choix &du programme rédigé en anglais ou en français; \\
\choix &la question n'a pas de sens: c'est impossible de modifier un\\
& programme.
\end{tabularx}

\item \resetchoix La compilation, c'est:

\begin{tabularx}{\linewidth}{@{}l@{~}X@{}}
\choix &la transformation du texte du programme binaire vers un langage\\
& informatique;\\
\choix &la transformation du programme rédigé en anglais vers le français; \\
\choix &l'ajout bout à bout de différents programmes;\\
\choix &la transformation d'un programme source, écrit dans un langage\newline informatique, en langage binaire ou en langage intermédiaire.
\end{tabularx}

\item \resetchoix La compilation d'un programme doit se faire:

\choix avant chaque utilisation du programme;

\choix régulièrement pendant le fonctionnement du programme;

\choix à chaque modification du code source;

\choix jamais.

\item \resetchoix Si je veux diffuser un programme, mais que je ne souhaite pas que les utilisateurs sachent comment il fonctionne,

\begin{tabularx}{\linewidth}{@{}l@{~}X@{}}
\choix & je dois distribuer le code binaire uniquement; \\
\choix & je dois distribuer le code source uniquement; \\
\choix & il n'y a aucun moyen d'empêcher les utilisateurs de comprendre\\
& comment le programme fonctionne.
\end{tabularx}

\item \resetchoix Si je veux diffuser un programme et que je souhaite que les utilisateurs puissent l'améliorer...

\begin{tabularx}{\linewidth}{@{}l@{~}X@{}}
\choix &je dois distribuer le code binaire uniquement; \\
\choix &je dois diffuser le code source du programme; \\
\choix &il n'y a aucun moyen de permettre aux utilisateurs d'améliorer un programme.
\end{tabularx}

\item \resetchoix Un code source en langage interprété:

\choix peut être directement exécuté par le noyau et le processeur;

\choix ne peut pas être directement exécuté par le noyau et le processeur.
\end{questions}
\end{qcm}

\begin{corrige}
\begin{questions}
\item Réponse \choix[b]. Un ordinateur ne sait interpréter que le langage binaire.

\item Réponse \choix[a]. Les langages informatiques permettent d'obtenir (compilation) des programmes binaires (ou intermédiaires) qui sont compris par les ordinateurs (ou par un programme interpréteur).

\item Réponse \choix[b]. Il est beaucoup plus facile pour un humain de comprendre et de modifier un code source qu'un programme binaire.

\item Réponse \choix[d]. La compilation est précisément la traduction du programme source en programme binaire (ou intermédiaire).

\item Réponse \choix[c]. Quand on modifie le code source d'un programme, il faut le compiler à nouveau pour remplacer le\linebreak programme binaire déjà existant afin de prendre en compte les dernières modifications.

\item Réponse \choix[a]. En ne disposant que du code binaire d'un programme, il est humainement difficile de le comprendre et de le modifier.

\item Réponse \choix[b]. Un programme peut être modifié en ayant son code source.

\item Réponse \choix[b]. Un code source en langage interprété ne peut pas être directement exécuté par le noyau et le processeur. C'est le cas de Python (contrairement au C).
\end{questions}
\end{corrige}

%%%

\begin{exo}{Fonction mystère}{\null}{1}{5} 
\label{exo:fct-mystere}% ref dans le cours (renvois exos)
Que fait la fonction suivante ?

\begin{listing}{}{02-ex01.py}\end{listing}
\end{exo}

\begin{corrige}
La première instruction de la fonction consiste à tester si la liste \texttt{L} est absente, auquel cas la fonction retourne \texttt{M}, c'est-à-dire une liste vide.

Ensuite, on définit \texttt{a} comme étant le premier élément de \texttt{L} tout en enlevant cet élément de \texttt{L} (la méthode \texttt{pop(i)} supprime l'élément d'indice $i$).

Si \texttt{a} n'est pas dans la liste \texttt{M} alors on l'y ajoute.

En écrivant \texttt{return mystere(L,M)}, on exécute à nouveau la fonction \texttt{mystere} avec pour arguments la nouvelle liste \texttt{L} (donc sans l'élément \texttt{a}) et \texttt{M} (qui contient alors \texttt{a}).

Au final, on obtient une liste \texttt{M} des éléments distincts de \texttt{L}.

\Par

La fonction retourne donc la liste des éléments distincts d'une autre liste.
\end{corrige}


%%%

\begin{exo}{Le retour de la fonction mystère}{\null}{1}{5} 
Que fait la fonction suivante :

\begin{listing}{}{02-ex02.py}
\end{listing}
\end{exo}

\begin{corrige}
La fonction commence par tester si la liste a un seul élément, auquel cas elle retourne cet élément. Cela nous donne donc un indice sur ce qu'elle fait : le retour est un nombre.

Ensuite, on compare les deux premiers éléments de la liste : si le premier est plus petit que le deuxième alors on supprime le deuxième sinon on supprime le premier; on ne garde donc que le plus petit des deux premiers éléments et on écourte la liste d'un élément (le plus grand des deux premiers).

On termine par faire appel à la fonction elle-même.

\Par


Il s'agit donc ici de diminuer la liste initiale en ne conservant que le plus petit des deux premiers éléments à chaque fois. L'élément restant au final est donc le plus petit élément de la liste initiale.
\end{corrige}


%%% 

\begin{exo}{Calcul du pgcd de deux nombres}{\null}{1}{10}
\index{Pgcd (récursivité)} 
\label{exo-calcul-pgcd-recursif}
\'Ecrire en Python une fonction récursive \texttt{pgcd(a,b)} renvoyant le plus grand diviseur commun de deux nombres $a$ et $b$.

Pour cela, on utilisera le résultat mathématique suivant :
\begin{center}
\og $\text{pgcd}(a,b)=\text{pgcd}(b,r)$, où $a=bq+r$. \fg{} 
\end{center}
\end{exo}

\begin{corrige}
Une fonction récursive permettant de calculer et d'afficher le pgcd de deux nombres $a$ et $b$ est la suivante:

\begin{listing}{}{02-ex03.py}\end{listing}

\Par

Rappelons que l'opérateur \og \texttt{\%} \fg{} permet d'obtenir le reste d'une division euclidienne. Ainsi, \og \texttt{a \% b} \fg{} représente le reste de la division euclidienne de \texttt{a} par \texttt{b}.
\end{corrige}

%%% 

\begin{exo}{Nombre d'adhérents}{\null}{1}{10} 
\enlargethispage*{4em}
Une association a remarqué que d'une année à l'autre,
\begin{itemize}
\item elle perd 5 \% de ses adhérents;
\item elle gagne \numprint{200} adhérents.
\end{itemize}
\begin{questions}
\item En admettant que le nombre d'adhérents de cette association était égal à \numprint{2000} au 1\ier{} janvier 2019, écrire en Python une fonction récursive nommée \texttt{nombre(n)} affichant le nombre théorique d'adhérents après $n$\linebreak années, $n\geqslant1$.
\item Dans ce même programme, afficher le nombre théorique d'adhérents au cours des 20 prochaines années.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item La fonction récursive calculant et donnant le nombre théorique \linebreak d'adhérents est :

\begin{listing}{}{02-ex04.py}\end{listing}

\Par

En effet, on peut noter $u_n$ le nombre d'adhérents lors de l'année $2019+n$. Ainsi, $u_0=\numprint{2000}$ et $u_{n+1}=0,95u_n+200$ (une perte de 5~\% revient à conserver 95~\% de la valeur précédente). Cette dernière égalité nous donne la formule récursive à mettre dans la fonction.

\newpage

\item Pour afficher les 20 valeurs qui suivent la première, on utilise une boucle itérative:


\Par

\qquad\texttt{for i in range(1,21):}

\qquad\qquad\texttt{print(nombre(i))}
\end{questions}
\end{corrige}

%%%

\begin{exo}{Suite de Fibonacci}{\null}{1}{10} 
\index{Fibonacci (suite de)}
La suite de Fibonacci est la suite numérique définie par :
\[
F_0=F_1=1\qquad,\qquad \forall n\geqslant0,\ F_{n+2}=F_{n+1}+F_n.
\]
\'Ecrire en Python une fonction récursive \texttt{Fibo(n)} permettant d'afficher le terme $F_n$, où $n\geqslant0$, puis afficher les termes de $F_0$ à $F_{20}$.
\end{exo}

\begin{corrige}
\label{prog-gen-suite-fibo}
Voici une suggestion de fonction:

\nathanlive{progmargin}{}
\begin{listing}{}{02-ex05.py}\end{listing}

\Par

En effet, la relation $\forall n\geqslant0,\ F_{n+2}=F_{n+1}+F_n$ peut aussi s'écrire :
\[
\forall n\geqslant2,\ F_{n}=F_{n-1}+F_{n-2}\;,
\]
d'où la formule : \og \texttt{ f = fibo(n-1)+fibo(n-2)} \fg.

Cependant, ce programme (naïf) n'est pas optimal. En effet, des mêmes termes sont calculés plusieurs fois, ce qui rend le programme quelque peu inefficace.

Nous verrons dans le chapitre suivant une autre solution utilisant la\linebreak \textit{programmation dynamique} (voir exercice \ref{prog-dyn-suite-fibo} page \pageref{prog-dyn-suite-fibo}).
\end{corrige}


%%%

\begin{exo}{La fonction compteur}{\null}{2}{10} 
\'Ecrire une fonction récursive \texttt{compteur(chaine,caractere)} retournant le nombre de fois que l'on peut compter le caractère dans la chaîne.

Par exemple, \texttt{compteur('Bonjour Lucie','u')} renvoie le nombre 2 car il y a deux \og u \fg{} dans la chaîne \og Bonjour Lucie \fg.

\begin{Remarque}
la méthode \texttt{count} permet d'obtenir ce résultat, mais le but de cet exercice n'est pas de se servir de cette méthode. On peut en effet avoir le nombre d'occurrences du caractère \og p \fg{} dans une chaîne en tapant \texttt{chaine.count('p')}.
\end{Remarque}
\end{exo}

\begin{corrige}
Une première possibilité est la suivante :

\nathanlive{progmargin}{}
\begin{listing}{}{02-ex06.py}\end{listing}

\Par\enlargethispage*{3em}

L'idée consiste ici à comparer le premier caractère de la chaîne au caractère recherché; s'ils coïncident alors on ajoute 1 au nombre d'occurrences du\linebreak caractère dans la chaîne obtenue à partir de la chaîne principale en ayant enlevé le premier caractère. Sinon, on n'ajoute rien.	

\newpage

Une autre possibilité, bien moins naturelle, est la proposition suivante:

\nathanlive{progmargin}{}
\begin{listing}{}{02-ex07.py} \end{listing}

\begin{methode}
On transforme d'abord la chaîne de caractères en une liste.
\end{methode}
\enlargethispage*{3em}
Si le caractère est trouvé dans les éléments de cette nouvelle liste alors on l'enlève (avec la méthode \texttt{pop}) et on ajoute 1 au compteur qui correspond à la chaîne initiale privée du caractère enlevé (la liste a été transformée en chaîne avec la méthode \texttt{str}).

Enfin, il ne faut pas oublier de retourner \og 0 \fg{} si le caractère n'est pas présent... sinon, un magnifique message d'erreur apparaît!

Mais cette façon de voir est légèrement tirée par les cheveux...
\end{corrige}

%%%

\begin{exo}{La vengeance de la fonction mystère}{\null}{2}{10} 
On considère le programme suivant:

\begin{listing}{}{02-ex08.py}\end{listing}

\begin{questions}
\item Quel résultat retourne \texttt{f(7,9)} ? (exécuter le programme à la main)
\item En déduire la signification de la valeur retournée par cette fonction pour deux entiers naturels non nuls $a$ et $b$ quelconques.
\item Pour une fonction récursive, un \textit{cas de base} est un cas qui ne nécessite pas d'appel récursif à la fonction.

Quel est le cas de base de cette fonction ?

\item Qu'est-ce qui garantit que le programme s'arrête ?

\item La complexité de cette fonction est-elle linéaire ? Quadratique ?\\ Exponentielle ?
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item La fonction calcule :
\begin{align*}
7+f(7,8) & = 7 + 7 + f(7,7)\\
& = 2\times7 + 7 + f(7,6)\\
& = 3\times7 + 7 + f(7,5)\\
& = 4 \times7 + 7 + f(7,4)\\
& = 5 \times7 + 7 + f(7,3)\\
& = 6 \times7 + 7 + f(7,2)\\
& = 7 \times7 + 7 + f(7,1)\\
& = 8 \times 7 + 7 = 9 \times 7 = 63.
\end{align*} 

\item De l'exemple précédent, on peut remarquer que la fonction retourne\linebreak $a \times b$.

\item Le cas de base de cette fonction est \og $b=1$ \fg{} car dans ce cas, on retourne une valeur (ici, la valeur de $a$).

\item Le fait d'appeler \texttt{f(a,b-1)} et le fait que $b$ soit un entier naturel non nul nous assure que la valeur de $b$ diminue de 1 en 1 et qu'elle va atteindre la valeur \og 1 \fg, auquel cas le programme s'arrête.

\item Dans la mesure où il n'y a pas de multiplication, la complexité est ici linéaire : elle est en $O(a)$.
\end{questions}
\newpage
\end{corrige}

%%%

\begin{exo}{Diagonale de Cantor}{\null}{2}{15} 
\index{Cantor (diagonale de)}
Dans un repère, les points à coordonnées entières sont numérotés selon le principe suivant:

\Par

\begin{figure}
\begin{center}
\includegraphics{053_prog-exo-diagcantor}
\figcaption{Diagonale de Cantor}
\end{center}
\end{figure}

\Par

\'Ecrire une fonction récursive \texttt{numero(x,y)} qui retourne le numéro du point de coordonnés $(x;y)$.

Par exemple, \texttt{numero(3,2)} doit retourner le nombre \og 17 \fg.
\end{exo}

\begin{corrige}
Une fonction possible est la suivante:

\begin{listing}{}{02-ex09.py}\end{listing}

\Par

L'idée ici est de partir du point de coordonnées $(x,y)$, qui initialise notre compteur à 1, et d'ajouter \texttt{numero(x+1,y-1)} tant que l'on ne se trouve pas sur l'axe des abscisses. Si l'ordonnée est nulle, il faut en effet revenir à une abscisse nulle et à une ordonnée qui est égale à l'abscisse du point duquel nous sommes partis diminuée de 1 : \texttt{numero(0,x-1)}.

On s'arrête pour le point de cordonnées $(0,0)$. À chaque fois que l'on fait appel à la fonction récursive, on ajoute 1 (car un point est compté en plus).
\end{corrige}

%%%

\begin{exo}{Les tours de Hanoï}{\null}{3}{20} 
\index{Hanoï (tours de)}
Selon Wikipedia:
\Par
\quad\begin{tabularx}{\linewidth}{@{}|X@{}}
Les tours de Hanoï (originellement, la tour d'Hanoï) sont un jeu de réflexion imaginé par le mathématicien français Édouard Lucas, et consistant à\linebreak déplacer des disques de diamètres différents d'une tour de « départ » à une tour d'« arrivée » en passant par une tour « intermédiaire », et ceci en un minimum de coups, tout en respectant les règles page suivante.
\end{tabularx}

\Par
\quad\begin{tabularx}{\linewidth}{@{}|X@{}}
\vspace*{-1em}
\begin{itemize}
\item on ne peut déplacer plus d'un disque à la fois ;
\item on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.
\end{itemize}
On suppose que cette dernière règle est également respectée dans la\linebreak configuration de départ.
\end{tabularx}
\Par
Ainsi, en notant $n$ le nombre de disques, la configuration de départ pour $n=3$ est la suivante:
\Par
\begin{figure}
\begin{center}
\includegraphics{062_recurs-hanoi01}
\figcaption{Configuration initiale des tours de Hanoï}
\label{toursHanoi}
\end{center}
\end{figure}
\Par
Pour résoudre le jeu, il faut déplacer tous les disques sur la Tour 3 en se servant de la tour 2 comme intermédiaire, ceci en commençant par déplacer le disque bleu sur la tour 3, puis le disque vert sur la tour 2, puis on peut mettre le disque bleu sur le disque vert, etc.

\begin{questions}
\item Pour $n=3$, résoudre \og à la main \fg{} le jeu. On notera (comme sur la\linebreak figure~\ref{toursHanoi}) les disques avec les chiffres 1, 2 et 3 et on décrira les\linebreak déplacements (par exemple, 1 va sur T3, 2 va sur T2, etc.)

\item Pour $n$ quelconque, ramener le problème initial à un même problème en faisant intervenir les $n-1$ premiers disques d'une part et le $n$-ième disque d'autre part.

\item En déduire une fonction récursive \texttt{hanoi(n,start=1,end=3,aux=2)} permettant d'afficher tous les mouvements jusqu'à résolution complète du jeu, où \texttt{start} désigne le numéro de la tour d'où provient un disque, \texttt{end} celui de la tour vers laquelle on déplace le disque et \texttt{aux} celui de la tour auxiliaire.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
%\item \multido{\i=1+1}{6}{Déplacement \i:
%\begin{center}
%\includegraphics{recurs-hanoi0\i}
%\end{center}
%\Par
%}
\item Déplacement 1:
\begin{center}
\includegraphics{062_recurs-hanoi01}
\end{center}
\Par
Déplacement 2:
\begin{center}
\includegraphics{062_recurs-hanoi02}
\end{center}
\Par
Déplacement 3:
\begin{center}
\includegraphics{062_recurs-hanoi03}
\end{center}
\Par
Déplacement 4:
\begin{center}
\includegraphics{063_recurs-hanoi04}
\end{center}
\Par
Déplacement 5:
\begin{center}
\includegraphics{063_recurs-hanoi05}
\end{center}
\Par
Déplacement 6:
\begin{center}
\includegraphics{063_recurs-hanoi06}
\end{center}
\Par

\item Afin de résoudre le jeu, il faut qu'à l'avant-dernier déplacement, tous les $n-1$ plus petits disques soient empilés sur la tour 2 afin de pouvoir déplacer le disque $n$ vers la tour 3.

\Par

Déplacer $n$ disques de T1 vers T3 (en utilisant T2 comme intermédiaire) revient à:
\begin{itemize}
\item déplacer $n-1$ disques de T1 à T2 (en utilisant T3 comme intermédiaire);
\item déplacer le $n$-ième disque de T1 vers T3;
\item déplacer à nouveau les $n-1$ disques de T2 vers T3 (en utilisant T1 comme intermédiaire).
\end{itemize}

\item Dans la fonction récursive, il faut une condition d'arrêt (le cas de base) : ce sera le cas où $n=1$, auquel cas on affichera : \og Déplacement du disque de la tour $X$ vers la tour 3 \fg, qui marquera presque la fin de la récursivité (il faudra encore déplacer à nouveau les $n-1$ disques situés sur T2).

Si $n \neq 1$ alors le problème revient à déplacer $n-1$ disques vers la tour auxiliaire, donc on devra faire appel à \texttt{hanoi(n-1,start,aux,end)}, puis on devra déplacer les $n-1$ disques de l'auxiliaire vers la dernière tour, donc faire appel à \texttt{hanoi(n-1,aux,end,start)}.

\nathanlive{progmargin}{}
\begin{listing}{}{02-ex10.py}\end{listing}

\Par

{\ttfamily

\pychevrons hanoi(3)\\
T 1  --> T 3\\
T 1  --> T 2\\
T 3  --> T 2\\
T 1  --> T 3\\
T 2  --> T 1\\
T 2  --> T 3\\
T 1  --> T 3
}
\end{questions}
\end{corrige}

%%%

\begin{exo}{Grille de Sudoku}{\null}{3}{50} 
\index{Sudoku}
\label{exo:sudoku}
Un \textit{Sudoku} classique est une grille de 9 lignes et 9 colonnes, donc composée de 9 blocs distincts de 3 lignes et 3 colonnes.

Remplir une grille de Sudoku consiste à utiliser tous les chiffres de 1 à 9 pour chacun des 9 blocs de sorte que chaque ligne et chaque colonne de la grille totale ne comporte aucun chiffre en double.

Dans cet exercice, on décidera de représenter une telle grille par une liste \texttt{S} de neuf listes à neuf éléments, chacune des listes représentant une ligne.

L'objectif de cet exercice est d'obtenir le remplissage de la grille page suivante (figure \ref{grille-sudoku}).
\enlargethispage*{5em}

\begin{questions}
\item Compléter la variable:\texttt{S = [ [0,1,0,0,7,8,0,0,0] , ... ] }

\item \'Ecrire une fonction \texttt{ligne(S,i)} qui retourne la liste des chiffres de 1 à 9 qui apparaissent sur la ligne $i$. On devra avoir pour notre grille:

\vspace*{-2mm}
\hrulefill

{\ttfamily
\pychevrons ligne(S,0)

[1,7,8]
}

\vspace*{-2mm}
\hrulefill

\newpage

\begin{figure}
\begin{center}
\includegraphics{055_sdd-sudoku}
\figcaption{Grille de Sudoku à implémenter}
\label{grille-sudoku}
\end{center}
\end{figure}



\item \'Ecrire une fonction \texttt{colonne(S,j)} qui retourne la liste des chiffres de 1 à 9 qui apparaissent dans la colonne $j$. On devra avoir pour notre grille:

\hrulefill

{\ttfamily
\pychevrons colonnes(S,0)

[1]
}

\hrulefill


\item \'Ecrire une fonction \texttt{bloc(S,i,j)} qui retourne la liste des chiffres de 1 à 9 qui apparaissent sur le bloc $3\times 3$ auquel appartient la case de la ligne $i$ et de la colonne $j$. On devra avoir pour notre grille:

\hrulefill

{\ttfamily
\pychevrons bloc(S,3,4)

[6,9,1,5,8]
}

\hrulefill
\enlargethispage*{5em}

\item \'Ecrire alors une fonction \texttt{possibles(S,i,j)} qui retourne la liste des chiffres de 1 à 9 que l'on peut écrire dans la case de la ligne \texttt{i} et de la colonne \texttt{j} (en tenant compte des règles du jeu). On devra avoir pour notre grille: 

\hrulefill

{\ttfamily
\pychevrons possibles(S,0,0)

[2,3,4,6,9]
}

\item On complète la grille de la ligne 0 à la ligne 8, de la colonne 0 à la colonne 8.

\'Ecrire une fonction \texttt{suivante(i,j)} qui reçoit en paramètre la ligne \texttt{i} et la colonne \texttt{j} d'une case, et qui renvoie le tuple (ligne,colonne) de la case suivante. On devra avoir:

\Par

\hrulefill

{\ttfamily
\pychevrons suivante(0,0) , suivante(0,8) , suivante(8,8)

(0,1) , (1,0) , (9,0)
}

\hrulefill

\item Compléter la fonction principale de résolution suivante:

\begin{listing}{}{02-ex11-1.py}
\end{listing}

\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-2.py}
\end{listing}

\Par

\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-3.py}
\end{listing}

\Par

\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-4.py}
\end{listing}

\newpage
\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-5.py}
\end{listing}

\Par

Ici, la difficulté réside dans le choix de la méthode que l'on souhaite adopter. Dans la proposition faite, nous avons fait le choix de calculer les indices de la case haut-gauche du bloc auquel appartient la case $(i,j)$. Pour se faire, on calcule le quotient de $i$ par 3 (si $i=4$ alors le quotient est 1) et on le multiplie par 3 car les lignes des cases haut-gauche sont toutes 0, 3 ou 6.

Il en est de même pour les colonnes.

\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-6.py}
\end{listing}

\Par

Il s'agit ici de trouver tous les nombres $k$ compris entre 1 et 9 (\texttt{for k in range(1,10)}) qui ne sont pas encore dans le bloc auquel appartient la case $(i,j)$ (\texttt{if k not in bloc(S,i,j)}), qui ne sont pas non plus sur la ligne $i$ (\texttt{if k not in ligne(S,i)}) ni dans la colonne $j$\linebreak (\texttt{for k not in colonne(S,j)}).

\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-7.py}
\end{listing}

\enlargethispage*{\baselineskip}
\item ~\par\vspace*{-8mm}\begin{listing}{}{02-ex11-8-1.txt}\end{listing}
\newpage
\begin{listing}{}{02-ex11-8-2.txt}\end{listing}

\Par

Explications:
\begin{itemize}
\item on commence par le plus évident : si $i=9$, c'est que l'on est arrivé à remplir la grille donc on retourne \texttt{True};

\item sinon, si la case $(i,j)$ est déjà remplie, on passe à la case suivante et on résout la grille;

\item le cas le plus difficile : si la case n'est pas remplie alors on teste chaque chiffre possible et on regarde si la résolution de la grille est possible en passant à la case suivante. Si tel est le cas, on renvoie \texttt{True};

\item si on sort de la boucle, c'est que la grille n'est pas solvable.\\On remplace alors le chiffre de la case $(i,j)$ par 0 (afin de revenir en\linebreak arrière d'une case) et on retourne \texttt{False} pour signifier la non-résolubilité de la grille actuelle.
\end{itemize}
\end{questions}

\nathanlive{prog}{Téléchargez le programme complet avec Nathan Live.}%02-ex11.py

\begin{anecdote}
La méthode consistant à tester tous les nombres et à revenir en arrière si la solution n'est pas satisfaisante est appelée \textit{backtracking}.
\end{anecdote}
\end{corrige}

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

\begin{exo}{Preuve : incalculabilité}{\null}{3}{30}
\index{Incalculabilité (preuve)}
\label{exo:incalculabilité}
\label{pb-calculabilite}  % référence dans le cours, section "calculabilité"... of course !
Cet exercice a pour but de démontrer que tous les problèmes ne sont pas calculables.

Pour cela, nous aurons besoin des définitions suivantes :

\begin{itemize}
\item une \textit{bijection} de $\N$ vers l'ensemble $E$ est une fonction $f$ telle que:
\begin{itemize}
\item[$\to$] quel que soit l'entier naturel $n$, il existe une unique image de $n$ par $f$;
\item[$\to$] \mbox{quel que soit l'élément $e$ de $E$, il existe un unique antécédent dans $\N$ à $e$.}
\end{itemize}

La fonction $n \mapsto 2n$ est par exemple une bijection de $\N$ vers l'ensemble des entiers positifs pairs;

\item un ensemble $E$ est \textit{dénombrable} s'il existe une bijection de $\N$ vers $E$.
\end{itemize}


\begin{questions}
\item Un algorithme est une succession de caractères pris dans un alphabet fini, noté $A$. Montrer que l'ensemble $\mathcal{A}$ des algorithmes est dénombrable.

\textit{Aide :} on pourra se servir de l'ensemble $C$ des combinaisons des\linebreak caractères de $\cal A$.

\item Un problème de décision peut être représenté par une fonction\linebreak booléenne $f\;:\;n\to\{0;1\}$ (\og 0 \fg{} pour le cas où la propriété est fausse pour la variable et \og 1 \fg{} dans le cas contraire).

Par exemple, le problème \og Est-ce que l'entier est pair ? \fg{} se représente par la fonction $f\;:\; 2p \mapsto 1$ et $f\;:\; 2p+1 \mapsto 0$, pour tout entier naturel $p$.

On note $\mathcal{B}$ l'ensemble des fonctions booléennes. 

On suppose que $\mathcal{B}$ est dénombrable, c'est-à-dire qu'il existe des\linebreak fonctions $f_1$, $f_2$, ... qui peuvent être représentées par exemple comme page ci-contre.

\Par

\begin{center}
\begin{tabular}{|C|*5{Zc}}
\hline
Valeurs de $n$ & 0 & 1 & 2 & 3 & $\cdots$\\
\hline
$f_0$ & 1 & 0 & 0 & 1 & $\cdots$\\
\hline
$f_1$ & 1 & 1 & 0 & 0 & $\cdots$\\
\hline
$f_2$ & 0 & 1 & 0 & 0 & $\cdots$\\
\hline
$\vdots$ & & & & & \\
\hline
\end{tabular}
\end{center}

\Par

On pose alors $g$ telle que :
\[
\begin{array}{lccl}
g\;:\; & \N & \to & \{0;1\}\\
       &  k & \mapsto & 1-f_{k}(k)
\end{array}
\]
\begin{questions}
\item Calculer $g(0)$, $g(1)$ et $g(2)$ pour les fonctions $f_0$, $f_1$ et $f_2$ données en exemple dans l'énoncé.
\item Dans un cas général, montrer que, quel que soit l'entier naturel $k$, $g\neq f_k$.
\item Justifier que $g \in\mathcal{B}$ et conclure à une contradiction.

Que cela permet-il de conclure sur $\mathcal{B}$ ?
\end{questions}

\item Justifier alors que tous les problèmes ne sont pas dénombrables.
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Notons $A=\{a_0,a_1,\cdots,a_{n-1}\}$ l'ensemble des caractères nécessaires à la rédaction des algorithmes.

\Par

Considérons alors la fonction $f$ définie comme suit :

\Par

\begin{center}
\begin{tabular}{c@{\quad$\mapsto$\quad}c}
0 & $a_0$\\
$\vdots$ & $\vdots$\\
$n-1$ & $a_{n-1}$\\
$n$ & $a_0a_0$\\
$n+1$ & $a_0a_1$\\
$\vdots$ & $\vdots$\\
$2n-1$ & $a_0a_{n-1}$\\
$2n$ & $a_0a_0a_0$\\
$\vdots$ & $\vdots$
\end{tabular}
\end{center}

$f$ est manifestement une bijection de $\N$ vers l'ensemble $C$ constitué des combinaisons des $n$ caractères de $A$. Or, $\mathcal{A}$ (l'ensemble des algorithmes) est inclus dans $C$ (car tout algorithme est une combinaison des caractères de $A$).

Il existe donc bien une bijection de $\N$ vers $\mathcal{A}$, donc $\mathcal{A}$ est dénombrable.

\item
\begin{questions}
\item $g(0)=1-f_0(0)=1-1=0$.

$g(1)=1-f_1(1)=1-1=0$.

$g(2)=1-f_2(2)=1-0=1$.

\item Dans un cas général, 
\begin{itemize}
\item $g(0) = 1-f_0(0)$ donc $g(0) \neq f_0(0)$, ce qui montre que $g \neq f_0$;
\item $g(1) = 1-f_1(1)$ donc $g(1) \neq f_1(1)$, ce qui montre que $g \neq f_1$;
\item quel que soit l'entier $k$, $g(k)=1-f_k(k) \neq f_k(k)$, donc $g \neq f_k$.
\end{itemize}

\item Quel que soit l'entier naturel $k$, $f_k\in\mathcal{B}$ donc $g\;:\;1-f_k\in\mathcal{B}$.

Or, nous venons de montrer à la question précédente que $g$ n'était pas une fonction $f_k$, donc que $g \not\in\mathcal{B}$. Il y a donc bien une contradiction.

Cela suppose donc que notre hypothèse de départ est fausse, à\linebreak savoir que $\mathcal{B}$ est dénombrable.
\end{questions}

\item D'une part, nous avons montré que l'ensemble des algorithmes était\linebreak dénombrable, d'autre part que l'ensemble des fonctions représentant les problèmes de décisions ne l'était pas. Cela signifie que ce dernier\linebreak ensemble a un cardinal supérieur à celui de l'ensemble $\mathcal{A}$, et donc qu'il existe plus de problèmes de décision que d'algorithmes.
\end{questions}
\end{corrige}


 

\thumb
\AfficheCorrige
