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	3 heures
	Techniques de conception d’algorithmes Algorithmes Diviser-pour-conquérir Algorithmes gloutons (Greedy) Programmation dynamique	6 heures
	Exploration de graphes Recherche en largeur et en profondeur Problèmes de plus court chemin	4,5 heures
	Heuristiques Classification des algorithmes Techniques de conception d’algorithmes heuristiques Coloration de graphes Branch-and-bound	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
	Programmation linéaire et méthode du simplexe Modèle linéaire Résolution de problème linéaire Résolution avec les solveurs	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. Les durées indiquées incluent l’examen de mi-session.

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.	12 heures
	Algorithmes de recherche, choix heuristique et calcul de temps amorti Implémentation d’algorithmes classiques de recherche. Optimisation des recherches par heuristiques basées sur le calcul du temps amorti.	12 heures
	Exploration de graphes Implémentation d’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.	12 heures
	Total	36

Utilisation d'outils d'ingénierie

Dans le cadre des laboratoires, les étudiants seront appelés à utiliser des langages de programmation et des environnements de développement logiciel.