Accueil - Connexion

Algorithmique avancee

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 )