Skip to content

C7 Terminaison, correction, complexité

"Beware of bugs in the above code; I have only proved it correct, not tried it."
Donald Knuth
(Correspondance avec van Emde Boas)

Cours

Support de cours chapitre 7

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

Fiche de TD7

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

  1. Écrire dans utop une fonction récursive somme_carres : int -> int qui prend en entrée un entier n positif 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.

  2. On veut maintenant écrire une version compilée de ce programme. Recopier dans VS Code le code de la fonction somme_carres. Le compilateur OCaml est ocamlopt : comme avec gcc, on peut préciser le nom de l'exécutable créé avec l'option -o.

    Aide

    Par exemple, pour compiler le programme hello.ml et produire l'exécutable hello.exe, on écrira simplement ocamlopt 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 ; écrire let () = ... 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.

  1. Écrire une fonction entiers qui prend en argument un entier n et renvoie la liste des entiers de n à 1.

  2. En utilisant une fonction anonyme et List.map, transformer cette liste en celle des inverses (flottants) de ces entiers.

  3. Calculer la somme des éléments de cette liste à l'aide de List.fold_left.

▪ Exercice 3 : Création et affichage

  1. Écrire en OCaml une fonction aleatoire qui prend en arguments un entier n et deux entiers vmin et vmax et renvoie une liste de n valeurs entières comprises entre vmin et vmax.

    Aide

    En OCaml, la fonction Random.int renvoie un entier au hasard entre 0 (inclus) et la valeur entière donnée en argument (exclus).

  2. Écrire en OCaml une fonction affiche qui prend en argument une liste d'entiers et l'affiche à la façon de utop. Par exemple, affiche [2; 6; 7] doit afficher dans le terminal [2; 6; 7].

▪ Exercice 4 : Manipulations de listes

  1. Écrire une fonction pair_impair : int list -> int list * int list qui 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]).

  2. Écrire une fonction entrelace : 'a list -> 'a list -> 'a list qui 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].

  3. Écrire une fonction compression : int list -> int list qui 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

  1. Écrire en OCaml une fonction insertion qui prend en argument un entier n et une liste triée d'entiers entiers et renvoie la liste dans laquelle n a été inséré à la bonne position dans entiers. Par exemple, insertion 3 [2; 7; 8] doit renvoyer [2; 3; 7; 8].

  2. En déduire une fonction tri_insertion qui prend en argument une liste d'entiers et renvoie cette liste triée en utilisant l'algorithme du tri par insertion.

  3. 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

  1. Écrire en OCaml une fonction min_reste qui prend en argument une liste entiers et renvoie un couple composé du minimum de la liste entiers et de la liste entiers privé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])
  2. En déduire une fonction tri_selection qui prend en argument une liste entiers et renvoie cette liste triée dans l'ordre croissant en utilisant l'algorithme du tri par sélection.

  3. 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

  1. Écrire en OCaml une fonction chiffre_caractere qui prend en argument un caractère car et une clé cle (un entier) et renvoie car chiffré en utilisant le code de César de clé cle lorsque car est une lettre (majuscule ou minuscule), sinon on ne fait rien et on renvoie car.

    Aide

    Pour faire un pattern matching sur les lettres minuscules, on peut écrire | 'a'..'z' ->

  2. Écrire une fonction reste qui prend en argument une chaîne et renvoie cette chaîne privée de son premier caractère.

  3. Écrire une fonction récursive cesar qui 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.

  4. La fonction String.map permet d'appliquer une fonction à chaque caractère d'une chaîne à la façon de List.map. Proposer une version du chiffrement de César utilisant String.map.

▪ Exercice 9 : Tri fusion en OCaml

  1. Écrire une fonction separe en OCaml qui prend en argument une liste l et renvoie deux listes contenant chacune la moitié (à une unité près) des éléments de l.

    Aide

    On pourra utiliser un pattern matching sur le motif h1::h2::t et mettre h1 dans la première liste et h2 dans la seconde.

  2. Écrire une fonction fusion qui prend en argument deux listes déjà triées et renvoie la fusion de ces deux listes.

  3. Écrire le tri_fusion en OCaml à l'aide de ces deux fonctions.

  4. 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.

  5. Quelle est la complexité de ce nouvel algorithme dans le pire des cas ?

  6. Effectuer des mesures de temps de calcul pour ce nouvel algorithme. Commenter.

▪ Exercice 10 : Médiane

Cet exercice est à traiter en langage C.

  1. Écrire une fonction mediane qui 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.

  2. 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_fusion qui prend en entrée deux tableaux d'entiers tab1 (de longueur n1) et tab2 (de longueur n2) 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 tableaux tab1 et tab2, à 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 fonction med_fusion_tri.

    b. Parcours des deux tableaux
    On propose maintenant d'utiliser deux indices i1 et i2 afin de parcourir en alternance chacun des deux tableaux jusqu'à obtenir au moins la moitié des éléments. Pour cela, on initialise ces deux indices i1 et i2 à 0, puis à chaque étape, après comparaison entre les éléments tab1[i1] et tab2[i2], on incrémente i1 ou i2. Lorsque la somme des deux indices vaut la moitié de n1+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 fonction med_fusion_parcours.

    c. Recherche dichotomique

    1. On suppose qu'on a partitionné les éléments des deux tableaux tab1 et tab2 en prenant les k premiers éléments de tab1 et les l premiers éléments de tab2. Donner les conditions portant sur k et l pour que cette partition représente la moitié gauche du tableau trié issu de la fusion de tab1 et tab2 (on pourra s'aider d'un schéma).

    2. En déduire une stratégie de recherche par dichotomie afin de déterminer la valeur correcte de k (nombre d'éléments à prendre dans tab1), et la mettre en place en écrivant une fonction med_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

  🟐🟐🟐 🟐  🟐
  1. 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 :

        struct config_s
        {
            int size;
            bool *cells;
        };
        typedef struct config_s config;
    

    où le champ size correspond au nombre de cellules présentes dans la configuration et le champ cells est un pointeur qui sera initialisé vers une zone mémoire de size booléens.

    a. Écrire les fonctions config init(int size, bool state) et void display(config c) qui permettent respectivement de créer une configuration de taille size avec la valeur state pour 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 annexe bool rule90(bool prev, bool current, bool next) qui renvoie l'état de la cellule centrale pour le triplet de cellules prev, 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 :

    ...............#..............
    ..............#.#.............
    .............#...#............
    ............#.#.#.#...........
    ...........#.......#..........
    ..........#.#.....#.#.........
    .........#...#...#...#........
    ........#.#.#.#.#.#.#.#.......
    .......#...............#......
    ......#.#.............#.#.....
    .....#...#...........#...#....
    ....#.#.#.#.........#.#.#.#...
    

  2. 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ègle rnumber, renvoie l'évolution de la case centrale du triplet de cellules prev, 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 ?

  3. 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.

  1. Écrire en C la recherche séquentielle bool recherche_seq(int elt, int tab[], int n) et la recherche dichotomique bool recherche_dicho(int elt, int tab[], int n) dans un tableau d'entiers trié.

  2. On utilise la bibliothèque <time.h> pour mesurer le temps CPU consommé :

    clock_t debut = clock();
    // code à mesurer
    clock_t fin = clock();
    double temps_sec = (double)(fin - debut) / CLOCKS_PER_SEC;
    
    Écrire un programme qui initialise un tableau trié de taille \(n\) (par exemple avec 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).

  3. 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\}\)$

  4. Pour chaque algorithme, calculer les ratios \(\dfrac{T(2n)}{T(n)}\) :

  5. Quel comportement théorique et pratique observe-t-on pour la recherche séquentielle (\(\GO(n)\)) ?
  6. Pourquoi le temps de la recherche dichotomique reste-t-il quasi insensible au doublement de la taille (\(\GO(\log n)\)) ?

  7. 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.

  1. Écrire en OCaml une fonction puiss_naive_count : int -> int -> int * int qui prend en argument deux entiers a et n et renvoie le couple (res, nb_mult) où res vaut \(a^n\) et nb_mult est 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\).

  2. Écrire une fonction puiss_rapide_count : int -> int -> int * int qui calcule \(a^n\) par l'algorithme d'exponentiation rapide récursif et renvoie également le nombre de multiplications effectuées :

  3. si \(n = 0\), \(a^0 = 1\) (0 multiplication) ;
  4. 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) ;
  5. 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).

  6. É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\).

  7. 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 -> int calculant \(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

BinarySearch