Objectifs du module :
- Analyser la complexité des algorithmes.
- Apprendre les structures des données arborescentes et leur application pour la mémorisation et recherche efficace d’information.
- Apprendre les notions et les algorithmes fondamentaux sur les graphes et leur application aux problèmes d’ordonnancement et d’optimisation.
Plan :
Complexité des Algorithmes :
- Introduction à l’étude de la complexité temporelle des algorithmes
- Notion de complexité asymptotique, ordre de croissance de fonctions, borne inférieure et supérieure des temps d’exécution.
- Analyse de simples algorithmes récursifs et résolution des relations de récurrence.
- Cas d’étude : analyse des algorithmes de tri et de recherche dans un tableau.
- Détermination d’une borne inférieure pour les algorithmes de tri basés sur comparaison
Les Graphes et leurs applications :
- Introduction aux graphes et leur utilisation pour modéliser des problèmes d’optimisation et d’ordonnancement.
- Représentation des graphes par listes d’adjacences et par matrices d’adjacences
- Algorithmes de parcours : parcours en largeur et en profondeur.
- Applications des algorithmes de parcours : recherche d’un circuit dans un graphe orienté et tri topologique
- Algorithmes de plus court chemin (PCC) dans un graphe pondéré et sa résolution : algorithmes de Dijkstra et de Bellman-Ford, algorithme de PCC dans un graphe orienté acyclique.
- Implémentation en C des algorithmes de parcours, tri topologique et de PCC
Les structures arborescentes et leurs applications
- Les arbres binaires de recherche.
- Les arbres équilibrés : les arbres AVL
- Le tas (heap) et applications : algorithme de tri et files de priorité.
- Les arbres n-aires
- Les arbres lexicographiques