Admin CliCours
Télécharger cours algorithmique avancée structures de données élémentaires, tutoriel document algorithme PDF.
1 Introduction
1.1 Qu’est-ce que l’algorithmique ?
1.2 Motivation : calcul de x
1.2.1 Problème
1.2.2 Algorithme trivial
1.2.3 Méthode binaire
1.2.4 Algorithme des facteurs
1.2.5 Algorithme de l’arbre
1.2.6 Et après ?
1.3 Conclusion
2 Complexité et optimalité ; premier algorithme de tri
2.1 Définition de la complexité
2.1.1 Notations de Landau
2.1.2 Complexité
2.1.3 Modèle de machine
2.2 Illustration : cas du tri par insertion
2.2.1 Problématique du tri
2.2.2 Principe du tri par insertion
2.2.3 Algorithme
2.2.4 Exemple
2.2.5 Complexité
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.3.4 Résolution des récurrences
3.3.5 Deuxième exemple : algorithme de Strassen pour la multiplication de matrices
4 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
6 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
7 Algorithmes gloutons
7.1 Location d’une voiture
7.2 Éléments de la stratégie gloutonne
7.2.1 Propriété du choix glouton
7.2.2 Sous-structure optimale
7.3 Fondements théoriques des méthodes gloutonnes
7.3.1 Matroïdes
7.3.2 Algorithmes gloutons sur un matroïde pondéré
8 Graphes et arbres
8.1 Graphes
8.2 Arbres
8.3 Parcours
8.3.1 Parcours des arbres
8.3.2 Parcours des graphes
9 Arbres de recherche et arbres de recherche équilibrés
9.1 Arbres binaires de recherche
9.1.1 Définition
9.1.2 Recherches
9.1.3 Insertion d’un élément
9.1.4 Suppression d’un élément
9.1.5 Complexité
9.2 Arbres rouge et noir
9.2.1 Définition
9.2.2 Rotations
9.2.3 Insertion
9.2.4 Suppression
9.2.5 Complexité
10 Plus courts chemins
10.1 Plus courts chemins à origine unique
10.1.1 Algorithme de Dijkstra
10.1.2 Algorithme de Bellman-Ford
10.2 Plus courts chemins pour tout couple de sommets
10.2.1 Programmation dynamique naïve
10.2.2 Algorithme de Floyd-Warshall
11 NP-complétude
11.1 La classe P
11.1.1 Problèmes abstraits
11.1.2 Codage
11.2 La classe NP
11.2.1 Algorithme de validation
11.2.2 La classe de complexité NP
11.3 NP-complétude
11.3.1 Réductibilité
11.3.2 Définition de la NP-complétude
11.3.3 Exemples de problèmes NP-complets
11.3.4 Preuves de NP-complétude
12 Heuristiques
12.1 Le problème de la couverture de sommet
12.1.1 Heuristique
12.1.2 Exemple d’utilisation
12.1.3 Garantie de performances
12.2 Le problème du voyageur de commerce
12.2.1 Exemple d’utilisation
12.2.2 Garantie de performances
Résumé sur structures de données élémentaires
Chapitre 1 Introduction
1.1 Qu’est-ce que l’algorithmique ?
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 AL-KHAREZMI ou AL-K HW
¯ ARIZM¯ I auteur –entre autres mais ce n’ est pas le plus important– d’un manuel de vulga-risation 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.).
1.2 Motivation : calcul de xn
1.2.1 Problème
Données : un entier naturel n et un réel x. On veut calculer xn.
Moyens : Nous partons de y 1 = x. Nous allons construire une suite de valeurs y 1, …, y m telle que la valeur y k soit obtenue par multiplication de deux puissances de x précédemment calculées : y k = y,u y v, avec 1 u; v < k,k 2 [2; m].
1.2.3 Méthode binaire
Algorithme
1. Écrire n sous forme binaire
2. Remplacer chaque :
– « 1 » par la paire de lettres « SX » ;
– « 0 » par la lettre « S ».
3. Éliminer la paire « SX » la plus à gauche.
4. Résultat : un mode de calcul de xn où
– S signifie « élever au carré » (squaring) ;
– X signifie « multiplier par x ».
Le tout en partant de x.
1.2.5 Algorithme de l’arbre
Le k + 1 e niveau de l’arbre est défini comme suit :
– on suppose que l’on a déjà les k premiers niveaux ;
– on construit le k + 1 e de la gauche vers la droite en ajoutant sous le nœud n les nœuds de valeur n + 1, n + a 1, …,n + a k 1 où 1, a 1, …, ak 1
est le chemin de la racine au nœud n ;
– on supprime tous les nœuds qui dupliquent une valeur déjà obtenue.
Chapitre 2 Complexité et optimalité ; premier algorithme de tri
2.1 Définition de la complexité
2.1.1 Notations de Landau
Quand nous calculerons la complexité d’un algorithme, nous ne calculerons généralement pas sa complexité exacte, mais son ordre de grandeur. Pour ce faire, nous avons besoin de notations asymptotiques.
2.1.3 Modèle de machine
Pour que le résultat de l’analyse d’un algorithme soit pertinent, il faut avoir un modèle de la machine sur laquelle l’algorithme sera implémenté (sous forme de programme). On prendra comme référence un modèle de machine à accès aléatoire (RAM) et à processeur unique, où les instructions sont exécutées l’une après l’autre, sans opérations simultanées.
…….
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours algorithmique avancée structures de données élémentaires (1488 KO) (Cours PDF)
