Contenu

Cours

Date	Contenus traités dans le cours	Heures
	Introduction Introduction à l’algorithmique Algorithmes et programmes Efficacité des algorithmes	3 heures
	Analyse des algorithmes Calcul asymptotique Baromètres Estimation de l’ordre asymptotique du temps de calcul Estimation de l’ordre asymptotique de la mémoire de travail Notion de temps de calcul amorti	3 heures
	Algorithmes récursifs Règles de conception d’algorithmes récursifs Analyse des algorithmes récursifs et équations de récurrence Preuve de convergence Optimisation des fonctions récursives	3 heures
	Structures de données, opérations élémentaires et efficacité Tableaux Listes Piles et files Arbres Graphes	3 heures
	Recherche par valeur Recherche séquentielle Recherche aléatoire Recherche binaire Hachage Arbres de recherche	3 heures
	Algorithmes de tri Insertion Sélection Quicksort Fusion Heapsort Pigeonnier	4,5 heures
	Techniques de résolution de problèmes d'optimisation Algorithmes gloutons Programmation dynamique Exploration de graphes implicites (backtracking, branch-and-bound) Heuristiques et méta-heuristiques (recuit simulé, algorithmes génétiques)	12 heures
	Problèmes d'optimisation sur des graphes Recherche en largeur et en profondeur Arbres minimaux couvrants Problèmes de plus court chemin Coloration de graphes	4,5 heures
	Algorithmes non-déterministes Déterminisme, approximation et certitude Algorithmes probabilistes numériques Algorithmes de type Monte Carlo Algorithmes de type Las Vegas	3 heures
	Total	39

Note : Tous les cours sont d'une durée de 3 heures 30 minutes par semaine. Les sujets seront peut-être abordés dans un ordre différent de celui indiqué dans le plan de cours.

Laboratoires et travaux pratiques

L'étudiant devra maîtriser le langage de programmation C pour la réalisation des laboratoires.

Date	Description	Heures
	Analyse asymptotique et algorithmes de tri. Implémentation d’algorithmes classiques de tri de données. Mesure de performance par analyse asymptotique théorique et expérimentale.	9 heures
	Structures de données et efficacité Implémentation et analyse d'algorithmes sur des graphes Arbres couvrants minimaux	12 heures
	Algorithmes de recherche par valeur Algorithmes d’exploration de graphes en largeur, en profondeur, etc. Notions d’algorithme optimal et sous optimal en explorant les problèmes du plus court chemin dans un graphe.	15 heures
	Total	36

Utilisation d'outils d'ingénierie

Dans le cadre des laboratoires, les étudiants seront appelés à utiliser le langage C, le système d'exploitation Linux et l'environnement de développement Eclipse.