Titre: Algorithmique avancée
Auteurs: Frédéric Vivien
Ecole/Université: IUP2
Résumé: Définition 1 (Algorithme). Un algorithme est suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution d’un problème. Historique : Le mot « algorithme » provient de la forme latine (Algorismus) du nom du mathématicien arabe ALKHAREZMI ou AL-KHW¯ARIZM¯I auteur –entre autres mais ce n’ est pas le plus important– d’un manuel de vulgarisation sur le calcul décimal positionnel indien (v. 830) expliquant son utilisation et, surtout, la manipulation des différents algorithmes permettant de réaliser les opérations arithmétiques classiques (addition, soustraction, multiplication, division, extraction de racines carrées, règle de trois, etc.). Double problématique de l’algorithmique
1. Trouver une méthode de résolution (exacte ou approchée) du problème.
– Soient trois nombres réels a, b et c, quelles sont les solutions de l’équation ax2 +bx+c ? (Résultat bien connu.)
– Soient cinq nombres réels a, b, c, d et e, quelles sont les solutions de l’équation ax5+bx4+cx3+dx2+ex+ f ? (Pas de méthode générale, cf. la théorie de GALOIS.)
2. Trouver une méthode efficace.
Savoir résoudre un problème est une chose, le résoudre efficacement en est une autre, comme nous allons le voir à la section 1.2. C’est quoi les Différences entre algorithmes et programmes ? Un programme est la réalisation (l’implémentation) d’un algorithme au moyen d’un langage donné (sur une architecture donnée). Il s’agit de la mise en oeuvre du principe. Par exemple, lors de la programmation on s’occupera parfois explicitement de la gestion de la mémoire (allocation dynamique en C) qui est un problème d’implémentation ignoré au niveau algorithmique.
Extrait du sommaire:
1 Introduction 9
1.1 Qu’est-ce que l’algorithmique ? 9
1.2 Motivation : calcul de xn 9
1.2.1 Problème 9
1.2.2 Algorithme trivial 10
1.2.3 Méthode binaire 10
1.2.4 Algorithme des facteurs 11
1.2.5 Algorithme de l’arbre 12
1.2.6 Et après ? 12
1.3 Conclusion 12
2 Complexité et optimalité ; premier algorithme de tri 13
2.1 Définition de la complexité 13
2.1.1 Notations de Landau 13
2.1.2 Complexité 13
2.1.3 Modèle de machine 14
2.2 Illustration : cas du tri par insertion 14
2.2.1 Problématique du tri 14
2.2.2 Principe du tri par insertion 14
2.2.3 Algorithme 14
2.2.4 Exemple 14
2.2.5 Complexité 15
3 La récursivité et le paradigme « diviser pour régner » 17
3.1 Récursivité 17
3.1.1 Définition 17
3.1.2 Récursivité simple 17
3.1.3 Récursivité multiple 17
3.1.4 Récursivité mutuelle 18
3.1.5 Récursivité imbriquée 18
3.1.6 Principe et dangers de la récursivité 18
3.1.7 Non décidabilité de la terminaison 19
3.1.8 Importance de l’ordre des appels récursifs 19
3.1.9 Exemple d’algorithme récursif : les tours de Hanoï 20
3.2 Dérécursivation 21
3.2.1 Récursivité terminale 21
3.2.2 Récursivité non terminale 22
3.2.3 Remarques 23
3.3 Diviser pour régner 23
3.3.1 Principe 23
3.3.2 Premier exemple : multiplication naïve de matrices 24
3.3.3 Analyse des algorithmes « diviser pour régner » 24
3.3.4 Résolution des récurrences 25
3.3.5 Deuxième exemple : algorithme de Strassen pour la multiplication de matrices 25
4 Algorithmes de tri 29
4.1 Tri par fusion 29
4.1.1 Principe 29
4.1.2 Algorithme 29
4.1.3 Complexité 30
4.2 Tri par tas 31
4.2.1 Définition d’un tas 31
4.2.2 Conservation de la structure de tas 31
4.2.3 Construction d’un tas 32
4.2.4 Algorithme du tri par tas 33
4.3 Tri rapide (Quicksort) 33
4.3.1 Principe 33
4.3.2 Algorithme 36
4.3.3 Complexité 37
5 Structures de données élémentaires 39
5.1 Introduction 39
5.2 Piles et files 39
5.2.1 Piles 39
5.2.2 Files 40
5.3 Listes chaînées 42
5.3.1 Définitions 42
5.3.2 Algorithmes de manipulation des listes chaînées 43
5.3.3 Comparaison entre tableaux et listes chaînées 44
6 Programmation dynamique 47
6.1 Multiplication d’une suite de matrices 47
6.2 éléments de programmation dynamique 51
6.2.1 Sous-structure optimale 51
6.2.2 Sous-problèmes superposés 51
6.2.3 Recensement 51
7 Algorithmes gloutons 53
7.1 Location d’une voiture 53
7.2 éléments de la stratégie gloutonne 54
7.2.1 Propriété du choix glouton 54
7.2.2 Sous-structure optimale 54
7.3 Fondements théoriques des méthodes gloutonnes 55
7.3.1 Matroïdes 55
7.3.2 Algorithmes gloutons sur un matroïde pondéré 55
8 Graphes et arbres 57
8.1 Graphes 57
8.2 Arbres 58
8.3 Parcours 60
8.3.1 Parcours des arbres 60
8.3.2 Parcours des graphes 61
9 Arbres de recherche et arbres de recherche équilibrés 63
9.1 Arbres binaires de recherche 63
9.1.1 Définition 63
9.1.2 Recherches 63
9.1.3 Insertion d’unélément 64
9.1.4 Suppression d’unélément 64
9.1.5 Complexité 66
9.2 Arbres rouge et noir 66
9.2.1 Définition 66
9.2.2 Rotations 67
9.2.3 Insertion 67
9.2.4 Suppression 67
9.2.5 Complexité 69
10 Plus courts chemins 75
10.1 Plus courts chemins à origine unique 75
10.1.1 Algorithme de Dijkstra 75
10.1.2 Algorithme de Bellman-Ford 76
10.2 Plus courts chemins pour tout couple de sommets 78
10.2.1 Programmation dynamique naïve 79
10.2.2 Algorithme de Floyd-Warshall 79
11 NP-complétude 83
11.1 La classe P 83
11.1.1 Problèmes abstraits 83
11.1.2 Codage 84
11.2 La classe NP 84
11.2.1 Algorithme de validation 84
11.2.2 La classe de complexité NP 85
11.3 NP-complétude 85
11.3.1 Réductibilité 85
11.3.2 Définition de la NP-complétude 86
11.3.3 Exemples de problèmes NP-complets 86
11.3.4 Preuves de NP-complétude 87
12 Heuristiques 89
12.1 Le problème de la couverture de sommet 89
12.1.1 Heuristique 90
12.1.2 Exemple d’utilisation 90
12.1.3 Garantie de performances 90
12.2 Le problème du voyageur de commerce 91
12.2.1 Exemple d’utilisation 91
12.2.2 Garantie de performances 91
Ondelettes et traitement du signal et d’image 24
Télécharger le fichier PDF: Algorithmique avancée