Livret pédagogique numérique 2024/2025
| 1I2AB2 | Algorithmique avancée | Informatique (formation initiale sous statut étudiant) | S6 | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Cours : 15 h | TD : 14 h | TP : 14 h | Projet : 0 h | Total : 43 h | |||||
| Responsable : Loick Lhote | |||||||||
| 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. Bloc compétence : Concevoir une solution perenne dans le domaine du génie logiciel -> Niveau 3 : Formaliser et modéliser un problème à l’aide d’outils mathématiques et algorithmiques. -> Niveau 1 : Trouver une information pertinente dans la littérature scientifique et technique puis l’évaluer et l'exploiter. |
|
| 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 )