Préparation en algorithmique
Notes de révision
Voici des notes de révision sur les parties 3 et 4 du programme (complexité et preuves de programmes).
Voici des notes de révision, sur les parties 2 et 6 du programme (schémas algorithmiques classiques et algorithmes de graphes).
Contenu
Issu du rapport officiel.
Programme : Algorithmique fondamentale
Cette partie insiste sur les notions de preuve et de complexité des algorithmes. Elle est relativement indépendante de tout langage de programmation, mais le candidat doit être capable de mettre en oeuvre sur machine les structures de données et les algorithmes étudiés.
- Structures de données. Types abstraits : définition des tableaux, listes, piles, files, arbres, graphes (orientés et non orientés), ensembles, dictionnaires, file de priorité. Interface abstraite et implantation (implémentation) concrète.
- Schémas algorithmiques classiques : approche gloutonne, diviser pour régner, programmation dynamique. Exemples : algorithme de Dijkstra, tri-fusion, plus longue sous-séquence commune.
- Complexité. Analyse des algorithmes : relations de comparaison O, &Theta et &Omega. Analyse dans le pire cas. Exemple d'analyse en moyenne : recherche d'un élément dans un tableau.
- Preuve d'algorithmes : correction, terminaison. Méthodes de base : assertions, pré-post conditions, invariants et variants de boucles, logique de Hoare, induction structurelle.
- Algorithmes de tri et de recherche. Méthodes de tri par comparaison (tri-fusion, tri-tas, tri rapide), arbre de décision et borne inférieure du tri par comparaisons. Méthodes de recherche séquentielle et dichotomique. Arbres binaires de recherche. Arbres équilibrés : définition, relation entre la taille et la hauteur, maintien de l'équilibre.
- Algorithmes de graphes. Parcours de graphes : algorithmes de parcours en largeur, en profondeur, algorithme de Dijkstra. Arbres couvrants : algorithmes de Prim et de Kruskal. Fermeture transitive.
Leçons
- Leçon 901
- Structures de données : exemples et applications.
- Leçon 902
- Diviser pour régner : exemples et applications.
- Leçon 903
- Exemples d'algorithmes de tri. Complexité.
- Leçon 906
- Programmation dynamique : exemples et applications.
- Leçon 907
- Algorithmique du texte : exemples et applications.
- Leçon 921
- Algorithmique de recherche et structures de données associées.
- Leçon 925
- Graphes : représentations et algorithmes.
- Leçon 926
- Analyse des algorithmes : complexité. Exemples.
- Leçon 927
- Exemples de preuve d'algorithme : correction, terminaison.
- Leçon 904
- Problèmes NP-complets : exemples.
Bibliographie
Quelques ouvrages recommandés pour préparer vos leçons et développements.
- [AU93]
- Alfred V. Aho et Jeffrey D. Ullman. Concepts fondamentaux de l'informatique. W. H. Freeman, 1993.
- [BBC92]
- Danièle Beauquier, Jean Berstel, et Philippe Chrétienne. Eléments d'algorithmique. Masson, 1992.
- [CLRS04]
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein. Introduction à l'algorithmique : Cours et exercices (2ème édition). Dunod, 2004.
- [GSF87a,GSF87b]
- Marie-Claude Gaudel, Michèle Soria et Christine Froidevaux. Types de données et algorithmes (1 et 2). INRIA, 1987.
- [DPV06]
- Sanjoy Dasgupta, Christos Papadimitriou et Umesh V. Vazirani. Algorithms. Ce livre n'est pas encore paru (à ma connaissance) mais il peut être intéressant d'y jeter un oeil pendant votre préparation, en particulier pour son excellent chapitre sur la programmation dynamique.