Algorithmique Avancé et Complexité PDF

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 4 Programmation...

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 4 Programmation Dynamique Contenu du chapitre  Le problème de la suite de Fibonacci  La programmation dynamique  Approches en programmation dynamique  Complexité de la programmation dynamique  Exemples classiques de programmation dynamique Chapitre 4 Programmation Dynamique Introduction La programmation dynamique est une méthodologie incontournable en algorithmique, introduite par Richard Bellman dans les années 1950. Conçue pour résoudre des problèmes complexes d’optimisation séquentielle, cette approche repose sur deux concepts fondamentaux : la sous-structure optimale et le chevauchement des sous-problèmes. Grâce à ces propriétés, la programmation dynamique offre une solution systématique et efficace pour transformer des calculs redondants en une approche optimisée et élégante. Dans ce cours, nous allons explorer en détail les fondements théoriques de la programmation dynamique ainsi que ses applications pratiques. Nous aborderons notamment les deux approches classiques : l’approche ascendante (Bottom-Up) et l’approche descendante avec mémoïsation (Top-Down), tout en illustrant ces concepts à travers des exemples concrets comme le problème du sac à dos ou la suite de Fibonacci. L’objectif est de vous familiariser avec cette méthode puissante et de vous montrer comment l’appliquer efficacement à divers problèmes d’optimisation algorithmique. Ce cours met également en lumière les forces et les limites de la programmation dynamique.  Le problème de la suite de Fibonacci Les nombres de Fibonacci sont définis par la relation de récurrence : F(0)= F(1)=1. F(n)=F(n−1)+F(n−2). n∈ N Problème : calculer F(n) pour une valeur donnée de n. On peut dire que le problème P = "calculer F(n)" peut être réalisé en cherchant la solution des deux sous-problèmes P1 = "calculer F(n−1)" et P2 = "calculer F(n−2)" Qui donne la suite : 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765, etc. On prévoit une croissance exponentielle. 1 Chapitre 4 Programmation Dynamique Un algorithme naïf serait par exemple : fibo1(n) If n < 2 return 1 else return fibo1(n-2)+fibo1(n-1)  Relation de récurrence La relation de récurrence pour l'algorithme naïf de Fibonacci est donnée par : T(n)=T(n−1)+T(n−2)+Θ(1) Cela signifie que pour calculer T(n), l'algorithme doit effectuer :  T(n−1) : Le temps nécessaire pour résoudre le problème F(n−1).  T(n−2) : Le temps nécessaire pour résoudre F(n−2).  Θ(1) : Un temps constant pour additionner les résultats des sous-problèmes.  Hypothèse T(n−1)≥T(n−2)  En analysant la structure de l'arbre d'appels récursifs, on observe que T(n−1) correspond au chemin le plus long dans l'arbre d'exécution, car T(n−1) dépend encore d'autres calculs récursifs (comme T(n−2),T(n−3),…).  Par conséquent, il est raisonnable de dire que T(n−1)≥T(n−2), car les appels récursifs dans T(n−1) incluent tous ceux de T(n−2), plus des calculs supplémentaires. Ainsi, la relation devient : T(n)≥2T(n−2)  Résolution simplifiée de la récurrence T(n)≥2T(n−2) On part de la simplification : 2 Chapitre 4 Programmation Dynamique T(n)≥2T(n−2) En appliquant cette relation récursivement, on obtient : T(n)≥2⋅T(n−2) T(n)≥2⋅2⋅T(n−4) =22⋅T(n−4) T(n)≥2k⋅T(n−2k) Le processus s'arrête lorsque n−2k=0, c'est-à-dire k = n/2. À ce moment-là : T(n)≥2n/2⋅T(0) Puisque T(0) est une constante (Θ(1)), cela donne : T(n)≥Θ(2n/2)  Résultat final La solution asymptotique de la récurrence montre que la complexité temporelle de cet algorithme est exponentielle. On écrit donc : T(n)=Θ(2n/2) La complexité exponentielle Θ(2n/2) signifie que le temps d'exécution double pour chaque augmentation de n de 2. Cela rend l'algorithme impraticable pour de grandes valeurs de n, car :  Même pour des valeurs modérées comme n=50, T(n) est déjà astronomique.  L'explosion combinatoire est due au fait que les mêmes sous-problèmes sont recalculés plusieurs fois. Exemple n = 4 Le 4ème nombre de Fibonacci est 5. 3 Chapitre 4 Programmation Dynamique Figure 4.1 : Arbre d’exécution de F(4) L'algorithme naïf de Fibonacci repose sur une définition récursive directe, où chaque nombre est calculé comme la somme des deux nombres précédents. Bien que cette approche semble intuitive, elle est inefficace pour des valeurs élevées de n en raison de : 1. Redondance des calculs : Dans l'algorithme naïf, les mêmes sous-problèmes sont recalculés plusieurs fois. Par exemple, pour calculer F(5), F(4), F(3), etc., sont recalculés de manière répétée, ce qui entraîne une explosion combinatoire. 2. Complexité exponentielle : La complexité temporelle est Θ(2n), ce qui rend l'algorithme inutilisable pour de grandes valeurs de n. Pour surmonter ces limites, nous pouvons introduire une technique d'optimisation appelée mémorisation.  La mémorisation La mémorisation consiste à stocker les résultats des calculs intermédiaires dans une structure de données (par exemple, un tableau). Ainsi, au lieu de recalculer un sous-problème déjà résolu, on le récupère directement à partir de la mémoire, ce qui permet de réduire considérablement la redondance des calculs. 4 Chapitre 4 Programmation Dynamique  Algorithme récursif avec mémorisation Fonction Fib1mem(n) Si mémo[n] est défini Retourner mémo[n] Sinon Si n ≤ 2 F←1 Sinon F ← Fib1mem(n-1) + Fib1mem(n-2) mémo[n] ← F Finsi Finsi Retourner F Fin  Algorithme récursif avec mémorisation (Top-Down)  Complexité temporelle :  Grâce à la mémorisation, chaque F(k) pour k≤n est calculé une seule fois.  Chaque calcul est ensuite récupéré directement depuis mémo en temps O(1).  Le coût total est donc linéaire en fonction de n.  T(n) = O(n)  Avantages de l'algorithme :  Efficacité : Résout les sous-problèmes une seule fois grâce à la mémorisation.  Simplicité : L'implémentation reste intuitive, proche de l'algorithme naïf. 5 Chapitre 4 Programmation Dynamique  Applicable pour de grandes valeurs de n : Contrairement à l'algorithme naïf, cet algorithme peut gérer de grandes valeurs en un temps raisonnable.  Inconvénients potentiels :  Espace mémoire : Si n est très grand, la taille de mémo peut devenir un problème dans des environnements à mémoire limitée.  Récursion : L'algorithme reste récursif, ce qui pourrait poser des problèmes de dépassement de pile (stack overflow) pour des valeurs extrêmement grandes de n.  Approche « du bas vers le haut » (bottom-up)  Cette méthode calcule F(n) en construisant un tableau (fib[]) où chaque case fib[i] contient le ième nombre de Fibonacci.  On commence par les cas de base (fib=1, fib=1) et on utilise une boucle pour calculer fib[i] pour i=3 à n. FONCTION Fib2(n) SI n