EC Algorithmique et applications

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

A l’issue du module l’étudiant doit être capable de / d’ :

• expliquer les Algorithmes de Chemin Plus Court (source unique et toute paire de sommets), d’ Arbre Couvrant Minimum et de Flot Maximum pour les graphes
• utiliser les algorithmes sur les graphes et les implanter dans un langage de programmation
• expliquer les methodologies de projet d'algorithme: algorithmes gloutons et programmation dynamique
• expliquer la notion de hashage et la conception d'une fonction d'hachage de qualité, algorithmes de hachage par chainage et par sondage
• expliquer la structure de tas binaire.
• utiliser cette structure pour réaliser la structure de file de priorité et l'algorithme de compression de Huffman
• expliquer les avantages des arbres binaires de recherche équilibrés, les arbres rouges et noirs et les B-arbres

• T. Cormen, C. Lieserson, R. Rivest, C. Stein Introduction à l'algorithmique, ed.Dunod, 2002
• B.W. Kernighan, D.M. Ritchie, Le langage C, Ed. 2ème édition, Dunod, 2000
• Support de cours en forme électronique fourni aux étudiants

• Eléments de programmation en C (structures de contrôle, structures des données statiques et dynamiques, récursivité).
• Structures des données élémentaires (listes chaînes, files, piles).
• Algorithmes de base de tri et de recherche.