Algorithmique avancée
Commentaires Composés : Algorithmique avancée. Rechercher de 53 000+ Dissertation Gratuites et Mémoires. . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
3
La récursivité et le paradigme « diviser pour régner » 3.1 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Récursivité simple . . . . . . . . . . . . . . . . . 3.1.3 Récursivité multiple . . . . . . . . . . . . . . . . 3.1.4 Récursivité mutuelle . . . . . . . . . . . . . . . . 3.1.5 Récursivité imbriquée . . . . . . . . . . . . . . . 3.1.6 Principe et dangers de la récursivité . . . . . . . . 3.1.7 Non décidabilité de la terminaison . . . . . . . . . 3.1.8 Importance de l’ordre des appels récursifs . . . . . 3.1.9 Exemple d’algorithme récursif : les tours de Hanoï 3.2 Dérécursivation . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Récursivité terminale . . . . . . . . . . . . . . . . 3.2.2 Récursivité non terminale . . . . . . . . . . . . . 3.2.3 Remarques . . . . . . . . . . . . . . . . . . . . . 3.3 Diviser pour régner . . . . . . . . . . . . . . . . . . . . . 3.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Premier exemple : multiplication naïve de matrices 3.3.3 Analyse des algorithmes « diviser pour régner » . . 3
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
4 3.3.4 3.3.5 4
TABLE DES MATIÈRES Résolution des récurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deuxième exemple : algorithme de Strassen pour la multiplication de matrices . . . . . . . . 25 25 29 29 29 29 30 31 31 31 32 33 33 33 36 37 39 39 39 39 40 42 42 43 44 47 47 51 51 51 51 53 53 54 54 54 55 55 55 57 57 58 60 60 61
Algorithmes de tri 4.1 Tri par fusion . . . . . . . . . . . . . . . 4.1.1 Principe . . . . . . . . . . . . . . 4.1.2 Algorithme . . . . . . . . . . . . 4.1.3 Complexité . . . . . . . . . . . . 4.2 Tri par tas . . . . . . . . . . . . . . . . . 4.2.1 Définition d’un tas . . . . . . . . 4.2.2 Conservation de la structure de tas 4.2.3 Construction d’un tas . . . . . . . 4.2.4 Algorithme du tri par tas . . . . . 4.3 Tri rapide (Quicksort) . . . . . . . . . . . 4.3.1 Principe . . . . . . . . . . . . . . 4.3.2 Algorithme . . . . . . . . . . . . 4.3.3 Complexité . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
5
Structures de données élémentaires 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Piles et files . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Piles . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Files . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Listes chaînées . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Définitions . . . . . . . . . . . . . . . . . . . . 5.3.2 Algorithmes de manipulation des listes chaînées 5.3.3 Comparaison entre tableaux et listes chaînées . . Programmation dynamique 6.1 Multiplication d’une suite de matrices . 6.2 Éléments de programmation dynamique 6.2.1 Sous-structure optimale . . . . 6.2.2 Sous-problèmes superposés . . 6.2.3 Recensement . . . . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
6
. . . . .
. . . . .
. . . . .
. . . . .
...