C7 Terminaison, correction, complexité ¶
"Beware of bugs in the above code; I have only proved it correct, not tried it."
(Correspondance avec van Emde Boas)
Cours¶
Attention
Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.
Travaux dirigés¶
Travaux pratiques¶
Danger
En cas de difficultés sur les exercices de programmation proposés dans ce chapitre, revenir sur ceux du chapitre précédent d'introduction à OCaml.
Exercice 1 : Compilation en OCaml¶
-
Écrire dans
utopune fonction récursivesomme_carres : int -> intqui prend en entrée un entiernpositif et renvoie la somme des carrés des entiers de 0 àn(on calculera récursivement sans utiliser la formule donnant le résultat général). Utiliser cette fonction afin de calculer la somme des carrés des entiers de 1 à 2024. -
On veut maintenant écrire une version compilée de ce programme. Recopier dans
VS Codele code de la fonctionsomme_carres. Le compilateur OCaml estocamlopt: comme avecgcc, on peut préciser le nom de l'exécutable créé avec l'option-o.Aide
Par exemple, pour compiler le programme
hello.mlet produire l'exécutablehello.exe, on écrira simplementocamlopt hello.ml -o hello.exe.Afin que le programme compilé affiche la somme des carrés des entiers de 1 à 2024, on ajoute en fin de programme :
let () = print_int (somme_carres 2024); print_newline () ;;. En effet, la dernière expression ne doit être qu'un simple affichage ; écrirelet () = ...permet de vérifier que l'évaluation de l'expression (un affichage avec effet de bord) renvoie bien().
Exercice 2 : Fonctions anonymes¶
On peut définir en OCaml des fonctions anonymes à l'aide de la syntaxe fun arg1 .. argn -> expr. Par exemple, l'expression let c = (fun n -> n*n) 10;; s'évalue à 100 car on applique la fonction (anonyme) \(n \mapsto n^2\) à 10.
-
Écrire une fonction
entiersqui prend en argument un entiernet renvoie la liste des entiers denà1. -
En utilisant une fonction anonyme et
List.map, transformer cette liste en celle des inverses (flottants) de ces entiers. -
Calculer la somme des éléments de cette liste à l'aide de
List.fold_left.
Exercice 3 : Création et affichage¶
-
Écrire en OCaml une fonction
aleatoirequi prend en arguments un entiernet deux entiersvminetvmaxet renvoie une liste denvaleurs entières comprises entrevminetvmax.Aide
En OCaml, la fonction
Random.intrenvoie un entier au hasard entre 0 (inclus) et la valeur entière donnée en argument (exclus). -
Écrire en OCaml une fonction
affichequi prend en argument une liste d'entiers et l'affiche à la façon deutop. Par exemple,affiche [2; 6; 7]doit afficher dans le terminal[2; 6; 7].
Exercice 4 : Manipulations de listes¶
-
Écrire une fonction
pair_impair : int list -> int list * int listqui prend en argument une liste d'entiers et renvoie la liste des éléments pairs et celle des éléments impairs. Par exemple,pair_impair [2; 7; 5; 4; 11; 8];;renvoie([2; 4; 8], [7; 5; 11]). -
Écrire une fonction
entrelace : 'a list -> 'a list -> 'a listqui entrelace les deux listes données en argument en piochant alternativement un élément dans chacune des deux listes (jusqu'à ce que l'une des deux soit vide). Par exemple,entrelace [1; 2; 3] [2; 6; 5];;renvoie[1; 2; 2; 6; 3; 5]. -
Écrire une fonction
compression : int list -> int listqui prend en argument une liste et renvoie cette liste dans laquelle les éléments consécutifs égaux ont été supprimés. Par exemple,compression [2; 2; 2; 1; 1; 2; 2; 2; 2]renvoie[2; 1; 2].
Exercice 5 : Tri par insertion en OCaml¶
-
Écrire en OCaml une fonction
insertionqui prend en argument un entiernet une liste triée d'entiersentierset renvoie la liste dans laquellena été inséré à la bonne position dansentiers. Par exemple,insertion 3 [2; 7; 8]doit renvoyer[2; 3; 7; 8]. -
En déduire une fonction
tri_insertionqui prend en argument une liste d'entiers et renvoie cette liste triée en utilisant l'algorithme du tri par insertion. -
Tester en générant des listes aléatoires à l'aide des fonctions de l'exercice 3.
Exercice 6 : Tri par sélection en OCaml¶
-
Écrire en OCaml une fonction
min_restequi prend en argument une listeentierset renvoie un couple composé du minimum de la listeentierset de la listeentiersprivée d'une seule occurrence du minimum. Par exemple :min_reste [6; 7; 3; 8; 10]doit renvoyer(3, [6; 7; 8; 10])min_reste [2; 6; 1; 3; 1; 5]doit renvoyer(1, [2; 6; 3; 1; 5])
-
En déduire une fonction
tri_selectionqui prend en argument une listeentierset renvoie cette liste triée dans l'ordre croissant en utilisant l'algorithme du tri par sélection. -
Tester en utilisant les fonctions de l'exercice 3.
Exercice 7 : Palindrome¶
En OCaml, String.sub : string -> int -> int -> string prend en arguments une chaîne de caractères s et deux entiers n et m et renvoie la portion de s commençant à l'indice n et de longueur m. Par exemple, String.sub "abcdef" 2 3 ;; renvoie la chaîne "cde".
Écrire une fonction est_palindrome : string -> bool qui renvoie true si et seulement si la chaîne fournie en argument est un palindrome.
Exercice 8 : Code de César en OCaml¶
-
Écrire en OCaml une fonction
chiffre_caracterequi prend en argument un caractèrecaret une clécle(un entier) et renvoiecarchiffré en utilisant le code de César de cléclelorsquecarest une lettre (majuscule ou minuscule), sinon on ne fait rien et on renvoiecar.Aide
Pour faire un pattern matching sur les lettres minuscules, on peut écrire
| 'a'..'z' -> -
Écrire une fonction
restequi prend en argument une chaîne et renvoie cette chaîne privée de son premier caractère. -
Écrire une fonction récursive
cesarqui prend en argument une chaîne et une clé et permet de chiffrer (ou de déchiffrer) cette chaîne avec le code de César. -
La fonction
String.mappermet d'appliquer une fonction à chaque caractère d'une chaîne à la façon deList.map. Proposer une version du chiffrement de César utilisantString.map.
Exercice 9 : Tri fusion en OCaml¶
-
Écrire une fonction
separeen OCaml qui prend en argument une listelet renvoie deux listes contenant chacune la moitié (à une unité près) des éléments del.Aide
On pourra utiliser un pattern matching sur le motif
h1::h2::tet mettreh1dans la première liste eth2dans la seconde. -
Écrire une fonction
fusionqui prend en argument deux listes déjà triées et renvoie la fusion de ces deux listes. -
Écrire le
tri_fusionen OCaml à l'aide de ces deux fonctions. -
Le tri rapide est similaire au tri fusion mais pour séparer les deux listes, on utilise un pivot choisi au hasard dans la liste et on sépare ensuite la liste entre les éléments inférieurs au pivot et les éléments supérieurs au pivot. Implémenter en OCaml ce nouvel algorithme de tri.
-
Quelle est la complexité de ce nouvel algorithme dans le pire des cas ?
-
Effectuer des mesures de temps de calcul pour ce nouvel algorithme. Commenter.
Exercice 10 : Médiane¶
Cet exercice est à traiter en langage C.
-
Écrire une fonction
medianequi prend en argument un tableau d'entiers supposé déjà trié et renvoie sa médiane.Aide
On prendra la valeur centrale dans le cas d'un tableau contenant un nombre impair d'éléments et la moyenne arithmétique entre les deux valeurs centrales dans le cas contraire.
-
On s'intéresse dans la suite de l'exercice à la recherche de la médiane de la fusion de deux tableaux triés. On veut donc écrire une fonction
mediane_fusionqui prend en entrée deux tableaux d'entierstab1(de longueurn1) ettab2(de longueurn2) et renvoie la médiane de la fusion.a. Concaténation et tri
On propose ici d'utiliser la méthode consistant à concaténer les deux tableauxtab1ettab2, à trier le résultat, puis à calculer la médiane en utilisant la fonction écrite à la question 1. Donner la complexité de cette méthode puis en proposer une implémentation sous la forme d'une fonctionmed_fusion_tri.b. Parcours des deux tableaux
On propose maintenant d'utiliser deux indicesi1eti2afin de parcourir en alternance chacun des deux tableaux jusqu'à obtenir au moins la moitié des éléments. Pour cela, on initialise ces deux indicesi1eti2à 0, puis à chaque étape, après comparaison entre les élémentstab1[i1]ettab2[i2], on incrémentei1oui2. Lorsque la somme des deux indices vaut la moitié den1+n2, cela signifie qu'on a atteint la médiane. Donner la complexité de cette méthode et en proposer une implémentation sous la forme d'une fonctionmed_fusion_parcours.c. Recherche dichotomique
-
On suppose qu'on a partitionné les éléments des deux tableaux
tab1ettab2en prenant leskpremiers éléments detab1et leslpremiers éléments detab2. Donner les conditions portant surketlpour que cette partition représente la moitié gauche du tableau trié issu de la fusion detab1ettab2(on pourra s'aider d'un schéma). -
En déduire une stratégie de recherche par dichotomie afin de déterminer la valeur correcte de
k(nombre d'éléments à prendre danstab1), et la mettre en place en écrivant une fonctionmed_dicho. Quelle est la complexité de cette nouvelle méthode ?Aide
On fera attention aux cas limites dans les indices.
-
Exercice 11 : Règle de Wolfram¶
On considère une variante du jeu de la vie se déroulant dans un tableau à une dimension. L'évolution de la case d'indice \(i\) de ce tableau ne dépend que de l'état de la case d'indice \(i\) et de ses voisines immédiates (les cases d'indices \(i-1\) et \(i+1\)). On donne ci-dessous l'évolution de la case centrale en fonction de l'état de ces 3 cases en notant "#" une case vivante et "." une case morte :
...\(\rightarrow\).(si les 3 cases sont vides, la case centrale reste vide)..#\(\rightarrow\)#.#.\(\rightarrow\)..##\(\rightarrow\)##..\(\rightarrow\)##.#\(\rightarrow\).##.\(\rightarrow\)####\(\rightarrow\).
D'autre part, on considère ici un tableau fini de \(N\) cases et on considère que la voisine de gauche de la case d'indice 0 ainsi que la voisine de droite de la case d'indice \(N-1\) sont toujours des cellules mortes. On donne ci-dessous un exemple d'évolution avec \(N=10\) :
| 🟐 | 🟐 | 🟐 | 🟐 | 🟐 | 🟐 |
évolue en
| 🟐 | 🟐 | 🟐 | 🟐 | 🟐 |
-
Implémentation de la règle 90 en langage C
Afin de représenter une configuration d'un jeu de la vie, on propose le type structuré suivant :
où le champ
sizecorrespond au nombre de cellules présentes dans la configuration et le champcellsest un pointeur qui sera initialisé vers une zone mémoire desizebooléens.a. Écrire les fonctions
config init(int size, bool state)etvoid display(config c)qui permettent respectivement de créer une configuration de taillesizeavec la valeurstatepour toutes ses cellules et d'afficher une configuration (on utilisera.pour une cellule morte et#pour une cellule vivante).b. Écrire la fonction
void evolution(config *c)qui modifie une configuration en la faisant évoluer une fois avec les règles données en introduction. On pourra s'aider d'une fonction annexebool rule90(bool prev, bool current, bool next)qui renvoie l'état de la cellule centrale pour le triplet de cellulesprev, current, next.c. Pour \(N=30\) et pour le tableau initial représenté par
"...............#.............."(toutes les cases sont mortes sauf la case d'indice 15), afficher les 100 premières évolutions successives.Aide
Les premières lignes sont :
...............#.............. ..............#.#............. .............#...#............ ............#.#.#.#........... ...........#.......#.......... ..........#.#.....#.#......... .........#...#...#...#........ ........#.#.#.#.#.#.#.#....... .......#...............#...... ......#.#.............#.#..... .....#...#...........#...#.... ....#.#.#.#.........#.#.#.#... -
Généralisation aux 256 règles de Wolfram
La règle d'évolution donnée en introduction est un cas particulier des règles de Wolfram et puisque l'évolution d'une case ne dépend que de l'état de ses voisines immédiates, il existe en réalité 256 règles possibles. Par exemple, puisque \(177 = (10110001)_2\), la règle 177 correspond aux évolutions suivantes : *
...\(\rightarrow\)#*..#\(\rightarrow\).*.#.\(\rightarrow\).*.##\(\rightarrow\).*#..\(\rightarrow\)#*#.#\(\rightarrow\)#*##.\(\rightarrow\).*###\(\rightarrow\)#C'est-à-dire que le bit de rang \(k\) (\(0 \leqslant k \leqslant 7\)) de l'écriture binaire de 177 correspond à l'évolution de la configuration dont l'écriture en base 2 vaut \(k\).
a. Écrire une fonction
bool rule(bool prev, bool current, bool next, int rnumber)qui, pour un numéro de règlernumber, renvoie l'évolution de la case centrale du triplet de cellulesprev, current, next.b. Tester votre programme en faisant évoluer une configuration initiale de 500 cellules toutes mortes sauf celle d'indice 1 qui est vivante en utilisant la règle 60. Quel est le nombre de cellules vivantes après 500 évolutions ?
-
Implémentation en OCaml
Reprendre entièrement l'exercice précédent en OCaml en représentant une configuration par le type
bool list.
Exercice 12 : Mesure empirique de la complexité en C¶
Cet exercice permet d'observer expérimentalement le lien entre la complexité théorique en notation \(\GO\) et le temps réel d'exécution mesuré sur machine.
-
Écrire en C la recherche séquentielle
bool recherche_seq(int elt, int tab[], int n)et la recherche dichotomiquebool recherche_dicho(int elt, int tab[], int n)dans un tableau d'entiers trié. -
On utilise la bibliothèque
<time.h>pour mesurer le temps CPU consommé :Écrire un programme qui initialise un tableau trié de taille \(n\) (par exemple avecclock_t debut = clock(); // code à mesurer clock_t fin = clock(); double temps_sec = (double)(fin - debut) / CLOCKS_PER_SEC;tab[i] = 2 * i), recherche un élément impair (absent du tableau, afin de se placer systématiquement dans le pire des cas), et mesure le temps écoulé. Pour obtenir des mesures stables, on pourra répéter la recherche un grand nombre de fois (par exemple \(1\,000\) ou \(10\,000\) fois). -
Mesurer les temps d'exécution \(T(n)\) pour des tailles de tableau doublées successivement : $\(n \in \{20\,000, \, 40\,000, \, 80\,000, \, 160\,000, \, 320\,000\}\)$
-
Pour chaque algorithme, calculer les ratios \(\dfrac{T(2n)}{T(n)}\) :
- Quel comportement théorique et pratique observe-t-on pour la recherche séquentielle (\(\GO(n)\)) ?
-
Pourquoi le temps de la recherche dichotomique reste-t-il quasi insensible au doublement de la taille (\(\GO(\log n)\)) ?
-
Répéter l'expérience avec le tri par sélection (
tri_selection) pour \(n \in \{1\,000, \, 2\,000, \, 4\,000, \, 8\,000\}\). Calculer les ratios \(\dfrac{T(2n)}{T(n)}\). Que constate-t-on ? Est-ce cohérent avec la complexité théorique \(\GO(n^2)\) ?
Exercice 13 : Décompte d'opérations : Exponentiation¶
On s'intéresse ici au décompte exact du nombre de multiplications nécessaires pour calculer \(a^n\) (\(a \in \N, n \in \N\)) selon l'algorithme employé, et à la comparaison entre complexité linéaire et logarithmique.
-
Écrire en OCaml une fonction
puiss_naive_count : int -> int -> int * intqui prend en argument deux entiersaetnet renvoie le couple(res, nb_mult)oùresvaut \(a^n\) etnb_multest le nombre de multiplications effectuées par l'algorithme naïf (\(a^n = a \times a^{n-1}\)). Vérifier que pour tout \(n \geqslant 1\), le nombre de multiplications vaut exactement \(n - 1\). -
Écrire une fonction
puiss_rapide_count : int -> int -> int * intqui calcule \(a^n\) par l'algorithme d'exponentiation rapide récursif et renvoie également le nombre de multiplications effectuées : - si \(n = 0\), \(a^0 = 1\) (0 multiplication) ;
- si \(n\) est pair non nul, \(a^n = (a^{n/2})^2\) : on calcule récursivement \(a^{n/2}\), puis on élève au carré (1 multiplication supplémentaire) ;
-
si \(n\) est impair, \(a^n = a \times (a^{n/2})^2\) : on élève au carré le résultat de \(a^{n/2}\), puis on multiplie par \(a\) (2 multiplications supplémentaires).
-
Écrire une fonction affichant un tableau comparatif du nombre de multiplications pour : $\(n \in \{1, 2, 4, 8, 16, 32, 64, 1\,024, 65\,536\}\)$ Vérifier expérimentalement que le nombre de multiplications pour l'exponentiation rapide reste toujours inférieur ou égal à \(2 \lfloor \log_2 n \rfloor\).
-
Afin d'éviter le dépassement de capacité sur les entiers machine lors de calculs avec de très grands exposants, écrire une fonction
puiss_mod : int -> int -> int -> intcalculant \(a^n \pmod m\) en temps \(\GO(\log n)\). Calculer par exemple \(7^{1\,000\,000} \pmod{101}\) et constater que le résultat est obtenu instantanément.
Humour d'informaticien¶
