Complexite des Algorithmes - Recursion et structures de donnees

Complexite des Algorithmes Recursion et structures de donnees Semestre 8 Andon Tchechmedjiev IMT Mines Ales.

Outline 1. Modèle de coût et récursion 2. Récurrences et diviser pour régner 3. Fil rouge : Le Jeu Ataxx 4. Structures équilibrées et coût mémoire 5. Minimax et élagage alpha-beta.

Modèle de coût et récursion.

Modèle de coût et récursion Objectifs de la séance 1. Comprendre pourquoi l’analyse du coût précède le codage. 2. Définir un modèle de coût : opérations élémentaires, taille de l’entrée. 3. Manipuler les notations O(·), Ω(·), Θ(·). 4. Observer la pile d’appels d’une fonction récursive en C. 5. Distinguer coût temporel et coût en mémoire. 3 / Semestre 8.

Modèle de coût et récursion Deux programmes, deux histoires Recherche linéaire Parcourir un tableau de n éléments un par un. Coût au pire : n comparaisons. Recherche dichotomique Diviser le tableau trié par 2 à chaque étape. Coût au pire : ⌈log2 n⌉ comparaisons. Pour n = 106 : 1 000 000 comparaisons vs 20 comparaisons. 4 / Semestre 8.

Modèle de coût et récursion Ordres de grandeur typiques 5 10 15 20 25 30 35 40 0 100 200 300 Taille de l’entrée n Nombre d’opérations log2 n n n log2 n n2 2n 5 / Semestre 8.

Modèle de coût et récursion Quand ça devient irréaliste n n log n n2 2n n! 10 33 100 1 024 3 628 800 20 86 400 ≈ 106 ≈ 2,4 × 1018 50 282 2 500 ≈ 1015 ≈ 3,0 × 1064 100 664 10 000 ≈ 1030 ≈ 9,3 × 10157 À raison de 109 opérations/seconde, 250 prend 13 jours. 2100 prend 4 × 1013 années. 6 / Semestre 8.

Modèle de coût et récursion Modèle de coût : principes Definition : Taille de l’entrée Le paramètre n qui capture la quantité de données que l’algorithme doit traiter : nombre d’éléments, longueur d’une chaîne, dimension d’une matrice. . . On compte les opérations élémentaires : comparaisons, affectations, opérations arithmétiques. On s’intéresse au pire cas sauf mention contraire. On ignore les constantes multiplicatives et les termes de bas ordre. 7 / Semestre 8.

Modèle de coût et récursion Compter les opérations : exemple 1 int max_tab(int tab[], int n) 7 } 8 return m; 9 } Nombre de comparaisons : exactement n − 1. Nombre d’affectations : entre 1 et n (pire cas). Coût total : Θ(n). 8 / Semestre 8.

Modèle de coût et récursion Notation O(·) — Borne supérieure asymptotique Definition : Grand O f(n) = O(g(n)) s’il existe c > 0 et n0 ∈ N tels que ∀n ⩾ n0, f(n) ⩽ c · g(n) f(n) c · g(n) n0 n A partir de n0, f reste en dessous de c · g. 9 / Semestre 8.

Modèle de coût et récursion Notation Ω(·) et Θ(·) Definition : Grand Omega f(n) = Ω(g(n)) ssi ∃c > 0, n0 tels que f(n) ⩾ c · g(n) pour n ⩾ n0. Borne inférieure : l’algorithme fait au moins autant. Definition : Grand Theta f(n) = Θ(g(n)) ssi f(n) = O(g(n)) et f(n) = Ω(g(n)). Encadrement serré : on connaît l’ordre exact. f(n) c2 · g(n) c1 · g(n) n 10 / Semestre 8.

Modèle de coût et récursion Résumé des notations Notation Signification Analogie f = O(g) f croit au plus aussi vite que g f ⩽ g f = Ω(g) f croit au moins aussi vite que g f ⩾ g f = Θ(g) f et g ont le même taux de croissance f ≈ g 11 / Semestre 8.

Modèle de coût et récursion Règles de calcul utiles 1. Somme : O(f) + O(g) = O(max(f, g)) 2. Produit : O(f) · O(g) = O(f · g) 3. Constante : k · f(n) = Θ(f(n)) pour k > 0 4. Polynome : aknk + . . . + a0 = Θ(nk) Exemple : Boucles imbriquées Boucle externe n itérations × boucle interne n itérations ⇒ O(n2). Attention : seulement si la boucle interne fait toujours n itérations! 12 / Semestre 8.

Modèle de coût et récursion Récursion : rappel Definition : Fonction récursive Fonction qui s’appelle elle-même sur une entrée plus petite, jusqu’a atteindre un cas de base. 1 int factorielle(int n) Chaque appel récursif crée un nouveau cadre de pile (stack frame). Le cadre stocke les paramètres, les variables locales et l’adresse de retour. 13 / Semestre 8.

Modèle de coût et récursion Trace de la pile pour factorielle(4) fact(4) t0 fact(4) fact(3) t1 fact(4) fact(3) fact(2) t2 fact(4) fact(3) fact(2) fact(1) t3 Profondeur maximale de la pile : n cadres. Coût mémoire de la récursion : Θ(n). Un débordement de pile (stack overflow) survient si n est trop grand. 14 / Semestre 8.

Modèle de coût et récursion Anatomie d’un cadre de pile en C adresse de retour ancien pointeur de cadre (rbp) paramètre: n = 3 variable locale: result adresses hautes adresses basses rsp rbp cadre de pile À chaque appel de fonction en C, le compilateur : • empile l’adresse de retour (instruction suivante), • sauvegarde l’ancien pointeur de cadre, • réserve de l’espace pour les paramètres et va- riables locales. Au retour, le cadre est dépilé et l’exécution reprend. 15 / Semestre 8.

Modèle de coût et récursion Exemple détaillé : pile de somme_rec(3) 1 int somme_rec(int n) 6 // appel initial: somme_rec (3) 16 / Semestre 8.

Modèle de coût et récursion Exemple détaillé : pile de somme_rec(3) Empilement (appels) n=3 s=? appel 1 n=3 s=? n=2 s=? appel 2 n=3 s=? n=2 s=? n=1 s=? appel 3 n=3 s=? n=2 s=? n=1 s=? n=0 ret 0 cas de base Dépilement (retours) n=3 s=? n=2 s=? n=1 s=0 → ret 1 ret 0+1=1 n=3 s=? n=2 s=1 → ret 3 ret 2+1=3 n=3 s=3 → ret 6 ret 3+3=6 Profondeur max : n + 1 cadres ⇒ mémoire Θ(n). 17 / Semestre 8.

Modèle de coût et récursion Version itérative équivalente 1 int factorielle_iter (int n) 6 return result; 7 } Coût temps : Θ(n) (identique). Coût mémoire : Θ(1) (pas de pile récursive). La version itérative est souvent plus sobre en mémoire. 18 / Semestre 8.

Modèle de coût et récursion Récursion double : Fibonacci naïf 1 int fib(int n) 5 4 3 2 1 2 3 2 1 L’arbre a une taille exponentielle : Θ(φn) nœuds (φ ≈ 1,618). Beaucoup de sous-problèmes sont recalculés inutilement. 19 / Semestre 8.

Modèle de coût et récursion Coût mémoire : deux composantes Mémoire totale = mémoire de l’entrée + mémoire auxiliaire Mémoire auxiliaire = variables locales + pile de récursion + structures annexes Exemple : Tri en place Un tri qui réorganise le tableau sans copie supplémentaire. Mémoire auxiliaire : O(1) ou O(log n) (pile de récursion). Exemple : Tri fusion classique Nécessite un tableau auxiliaire pour fusionner. Mémoire auxiliaire : O(n). 20 / Semestre 8.

Modèle de coût et récursion Visualiser la mémoire en C Pile (stack) variables locales adresse de retour paramètres ↑ croit vers le bas Tas (heap) malloc malloc allocation dynamique La pile grossit à chaque appel de fonction. Le tas grossit à chaque malloc (structures de données). Le coût mémoire total combine les deux. 21 / Semestre 8.

Modèle de coût et récursion Pièges fréquents 1. Confondre mesure et classe. Un programme rapide sur une petite entrée peut être en O(2n). 2. Oublier la pile. Une récursion de profondeur n coute Θ(n) en mémoire. 3. Ignorer le coût cache. strlen dans une boucle : O(n) par appel ⇒ O(n2) au total. 4. Analyser la mauvaise variable. Le coût depend de ce qui change entre les appels. 22 / Semestre 8.

Modèle de coût et récursion Mini-exercice : analyser ces trois versions Version A (itérative) int s = 0; for (int i=1; i<=n; i++) s += i; Version B (récursive) int sum(int n) Version C (fermee) int s = n * (n + 1) / 2; Temps Mémoire aux. A Θ(n) Θ(1) B Θ(n) Θ(n) C Θ(1) Θ(1) 23 / Semestre 8.

Récurrences et diviser pour régner.

Récurrences et diviser pour régner Plan de la séance 1. Écrire une équation de récurrence à partir d’un algorithme récursif. 2. Dérouler, dessiner et résoudre la récurrence. 3. Appliquer le théorème maître aux formes standard. 4. Analyser le tri fusion et la dichotomie en détail. 5. Identifier les pièges : récursion cachée, exponentielle involontaire. 25 / Semestre 8.

Récurrences et diviser pour régner Rappel : de l’algorithme à la récurrence Si un algorithme de taille n : 1. fait un travail local de coût f(n), 2. puis lance a appels récursifs sur des sous-problèmes de taille n/b, alors : T(n) = a T �n b � + f(n) 26 / Semestre 8.

Récurrences et diviser pour régner Recherche dichotomique 1 int binary_search (int tab[], int lo , int hi , int target) a = 1 appel, taille n/2, travail local O(1). T(n) = T(n/2) + c. 27 / Semestre 8.

Récurrences et diviser pour régner Déroulement de T(n) = T(n/2) + c n n/2 n/4 1 T(n) = T(n/2) + c = T(n/4) + 2c = . . . = T(1) + c log2 n = Θ(log n) L’arbre a log2 n niveaux, chacun coûtant c. 28 / Semestre 8.

Récurrences et diviser pour régner Tri fusion (merge sort) 1 void merge_sort(int tab[], int lo , int hi) a = 2 appels, taille n/2, fusion en O(n). T(n) = 2 T(n/2) + cn. 29 / Semestre 8.

Récurrences et diviser pour régner Arbre de récursion du tri fusion cn cn/2 cn/4 c c cn/4 c c cn/2 cn/4 c c cn/4 c c coût cn coût cn coût cn Chaque niveau coûte cn au total; il y a log2 n niveaux. ⇒ T(n) = Θ(n log n). 30 / Semestre 8.

Récurrences et diviser pour régner Trace d’une fusion G : 1 3 5 7 D : 2 4 6 8 R : 1 2 3 4 5 6 7 8 On parcourt chaque élément une seule fois ⇒ fusion en O(n). 31 / Semestre 8.

Récurrences et diviser pour régner Méthode de l’arbre de récursion 1. Dessiner l’arbre : chaque nœud représente un appel. 2. Annoter le coût local de chaque nœud. 3. Sommer les coûts par niveau. 4. Compter le nombre de niveaux. 5. Sommer sur tous les niveaux. Exemple : T(n) = 3 T(n/4) + cn2 Niveau k : 3k nœuds, chacun de coût c(n/4k)2. Coût du niveau k : c n2 � 3 16 �k. Série géométrique décroissante ⇒ T(n) = Θ(n2). 32 / Semestre 8.

Récurrences et diviser pour régner Arbre pour T(n) = 3 T(n/4) + cn2 cn2 c(n/4)2 . . . . . . . . . c(n/4)2 . . . . . . . . . c(n/4)2 . . . . . . . . . cn2 3 16 cn2 33 / Semestre 8.

Récurrences et diviser pour régner Théorème maître (forme simplifiée) Theoreme : Master Theorem Pour T(n) = a T(n/b) + Θ(nd) avec a ⩾ 1, b > 1, d ⩾ 0 : T(n) =        Θ(nd) si d > logb a Θ(nd log n) si d = logb a Θ(nlogb a) si d < logb a Cas 1 : le travail local domine les appels récursifs. Cas 2 : travail et récursion contribuent de manière égale. Cas 3 : les feuilles dominent; la récursion coûte plus. 34 / Semestre 8.

Récurrences et diviser pour régner Illustration graphique des trois cas racine feuilles racine domine Cas 1 : d > logb a racine feuilles tous égaux Cas 2 : d = logb a racine feuilles feuilles dominent Cas 3 : d < logb a 35 / Semestre 8.

Récurrences et diviser pour régner Application du théorème maître Algorithme a b d logb a Résultat Dichotomie 1 2 0 0 Θ(log n) (cas 2) Tri fusion 2 2 1 1 Θ(n log n) (cas 2) Karatsuba 3 2 1 1.58 Θ(n1.58) (cas 3) Strassen 7 2 2 2.81 Θ(n2.81) (cas 3) T = 3T(n/4) + n2 3 4 2 0.79 Θ(n2) (cas 1) 36 / Semestre 8.

Récurrences et diviser pour régner Exponentiation rapide 1 long power(long x, int n) 7 return x * power(x, n - 1); 8 } Au pire, réduction de n par 2 tous les 2 appels. T(n) = T(n/2) + c ⇒ Θ(log n). Comparaison : version naïve en Θ(n). 37 / Semestre 8.

Récurrences et diviser pour régner Piège : Fibonacci naïf (rappel) 1 int fib(int n) Récurrence : T(n) = T(n − 1) + T(n − 2) + c. Attention : cette récurrence n’est pas de la forme a T(n/b) + f(n)! Ni dichotomie, ni division par 2 : c’est une croissance exponentielle Θ(φn). 38 / Semestre 8.

Récurrences et diviser pour régner Fibonacci en O(n) : mémorisation 1 int memo[MAX_N] =; 2 int fib_memo(int n) 5 4 3 2 1 2 3 déjà calculé→ O(1) Chaque valeur n’est calculée qu’une fois : Θ(n) en temps, Θ(n) en mémoire. 39 / Semestre 8.

Récurrences et diviser pour régner Quicksort : analyse au pire et en moyenne Pire cas Pivot toujours minimal ou maximal. T(n) = T(n − 1) + cn T(n) = Θ(n2) n n−1 n−2 · · · Cas moyen Pivot partage raisonnablement. T(n) = 2T(n/2) + cn (en espérance) T(n) = Θ(n log n) n n/2 · · · · · · n/2 · · · · · · 40 / Semestre 8.

Récurrences et diviser pour régner Résumé des récurrences vues Récurrence Solution Exemple T(n) = T(n/2) + c Θ(log n) dichotomie T(n) = T(n − 1) + c Θ(n) parcours linéaire T(n) = 2T(n/2) + cn Θ(n log n) tri fusion T(n) = T(n − 1) + cn Θ(n2) quicksort pire cas T(n) = T(n − 1) + T(n − 2) + c Θ(φn) Fibonacci naïf T(n) = T(n/2) + c (exponentiation) Θ(log n) exponentiation rapide 41 / Semestre 8.

Récurrences et diviser pour régner Mini-exercice 1. Écrire la récurrence de la recherche ternaire (diviser par 3). Quelle est sa complexité? Gagne-t-on par rapport à la dichotomie? 2. Un algorithme divise un problème de taille n en 4 sous-problèmes de taille n/2, puis effectue un travail supplémentaire en O(n). Écrire la récurrence et donner sa solution. 3. Pourquoi la mémoïsation transforme-t-elle Fibonacci de Θ(φn) en Θ(n)? 42 / Semestre 8.

Récurrences et diviser pour régner Synthèse de la séance 2 Écrire la récurrence Dessiner l’arbre Théorème maître Θ(·) 43 / Semestre 8.

Fil rouge : Le Jeu Ataxx.

Fil rouge : Le Jeu Ataxx Le jeu Ataxx Definition : Présentation Jeu de plateau à 2 joueurs, grille N × N (typiquement 5 × 5 ou 7 × 7). Jeu combinatoire à somme nulle, information parfaite. Objectif : avoir le plus de pièces à la fin de la partie. État initial (5 × 5) : B B R R Chaque joueur commence avec 2 pièces dans les coins opposés. 45 / Semestre 8.

Fil rouge : Le Jeu Ataxx Ataxx : les deux types de coups 1. Clonage (distance 1) La pièce se duplique sur une case adjacente (8 directions). Le joueur gagne une pièce supplémentaire. B B 2. Saut (distance 2) La pièce saute à une case à distance 2 (chebyshev). La case d’origine est libérée. B B Contamination : après un clonage ou un saut, toutes les pièces adverses adja- centes (distance 1) à la destination sont converties en pièces du joueur courant. 46 / Semestre 8.

Fil rouge : Le Jeu Ataxx Ataxx : contamination illustrée Avant le coup B R R R clone Après clonage en (2,2) B B B B Les 3 pièces rouges adjacentes à la destination sont converties en bleues. Bleu passe de 1 à 4 pièces; Rouge passe de 3 à 0! 47 / Semestre 8.

Fil rouge : Le Jeu Ataxx Ataxx : fin de partie et victoire La partie se termine quand : Le plateau est rempli (plus de case vide), ou Un joueur n’a plus de pièce, ou Le joueur dont c’est le tour n’a aucun coup légal (il passe). Le gagnant est celui qui possède le plus de pièces sur le plateau à la fin de la partie. Propriétés clés pour la recherche : Facteur de branchement moyen b ≈ 8–15 selon la taille du plateau. Profondeur typique : ∼ 30–60 coups pour un plateau 5 × 5. Exploration exhaustive impossible ⇒ minimax avec profondeur limitée + évaluation. 48 / Semestre 8.

Structures équilibrées et coût mémoire.