Accueil - Connexion

Algorithmique avancée

1I2AB2 Algorithmique avancée Informatique S6
Cours : 15 h TD : 14 h TP : 14 h Projet : 0 h Total : 43 h
Responsable : Christine Porquet
Pré-requis
Cours "Programmation et langage C"
Cours "Bases de l'algorithmique"
Cours "Outils de développement logiciel"
Objectifs de l'enseignement
- Approfondir les bases de l'algorithmique vues au 1er semestre en étudiant les types de données arbres et graphes et les principaux algorithmes permettant de les manipuler.
- Donner des notions d'informatique théorique sur l'indécidabilité et la complexité des problèmes.
Programme détaillé
- Étude des algorithmes de recherche / insertion / suppression dans les arbres binaires de recherche, les arbres équilibrés, les arbres-B et les arbres n-aires.
- Représentation des ensembles disjoints dynamiques par forêt d'arbres.
- Étude des algorithmes de base sur les graphes orientés et non orientés : parcours usuels, composantes connexes et fortement connexes, arbre couvrant de poids minimal(algorithmes de Prim et de Kruskal, recherche du plus court chemin (algorithme de Moore-Dijkstra).
Tous les algorithmes sont analysés et comparés du point de vue de leur complexité.
- Notions d'informatique théorique: indécidabilité des problèmes, machines de Turing, complexité des problèmes, exemples de problèmes NP-complets.
Applications (TD ou TP)
Exemples de TD/TP :
- Parcours d'arbre binaire de recherche en profondeur et en largeur.
- Vérificateur orthographique (manipulation d'arbre n-aire).
- Parcours de graphe en profondeur et en largeur.
- Marquage topologique de graphe.
- Ordonnancement de tâches par la méthode MPM.
Compétences acquises
- Maîtrise des principaux types abstraits de données et de leur implantation en langage C.
- Maîtrise des algorithmes sur les arbres avec analyse de leur complexité.
- Maîtrise de quelques algorithmes sur les graphes.
- Connaissances sur les catégories de problèmes insolubles en un temps raisonnable.
Bibliographie
- Introduction à l'algorithmique. T. Cormen et al., Dunod (1994)
- Types de données et algorithmes. C. Froidevaux et al., Mc Graw-Hill (1990)
- Algorithmes et structures de données en langage C. L. Ammeraal, InterEditions (1996)
- Algorithmes de graphes. P. Lacomme et al., Eyrolles (2003)
- Programmation en langage C. 3ème édition. S. Kochan, Pearson Education (2005)
- Le langage C, norme Ansi. B. Kernigham, Dunod (2000)

© 2018 - ENSICAEN ( Mentions Légales - Crédits )