1IAG2 | Algorithmique avancee | Informatique - Apprentissage | S6 | ||||||
---|---|---|---|---|---|---|---|---|---|
Cours : 15 h | TD : 14 h | TP : 14 h | Projet : 0 h | Total : 43 h | |||||
Responsable : Christine Porquet |
Pré-requis | |
---|---|
Cours "Introduction à la programmation" Cours "Bases de l'algorithmique" Cours "Outils de développement logiciel" |
|
Objectifs de l'enseignement | |
Le cours approfondit 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. | |
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). |
|
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. |
|
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) |
© 2024 - ENSICAEN ( Mentions Légales - Crédits )