Département d'informatique et de recherche opérationnelle

IFT 2121 --- H98
Introduction à l'algorithmique

Professeur: Claude Crépeau, 3347 André--Aisenstadt
Début des cours: le lundi 5 janvier 1998
Début des TPs: le vendredi 9 janvier 1998
Horaire: cours lundi 11:30-13:30, mercredi 11:30-12:30, TPs vendredi 08:30-10:30

Objectifs: Comment développer un algorithme efficace pour résoudre un problème donné? Parmi plusieurs algorithmes résolvant un même problème, lequel choisir? Pour illustrer l'importance de ces questions, considérez le problème du calcul du déterminant d'une matrice. Un algorithme classique, dû à Gauss et Jordan, peut calculer le déterminant d'une matrice 20x20 en moins d'un dixième de seconde sur un ordinateur contemporain. Un autre algorithme tout aussi classique, basé sur la définition récursive du déterminant, prendrait dix millions d'années pour arriver au même résultat sur le même ordinateur!

L'algorithmique propose des réponses à ces questions. Pour la première, il y a un ensemble de techniques générales de conception d'algorithmes. Nous étudierons par exemple l'approche vorace, la technique diviser-pour-régner, la programmation dynamique et l'approche probabiliste. Pour la seconde question, l'algorithmique offre des techniques d'analyse de l'efficacité d'algorithmes basées principalement sur la résolution de récurrences et les notations asymptotiques. À l'aide de ces méthodes, il est possible de prédire la quantité de temps ou de mémoire requise à l'exécution d'un algorithme sur des exemplaires de grande taille du problème à résoudre. (C'est ainsi que nous pouvons prédire qu'il faudrait des millions d'années pour calculer un déterminant par le «mauvais» algorithme.) Cette analyse constitue une base de comparaison pour guider le choix d'algorithme.

Le cours IFT 2121 permettra à l'étudiante d'apprendre à concevoir des algorithmes, d'analyser l'efficacité de ceux-ci et de se familiariser avec des techniques mathématiques pertinentes. Elle développera le réflexe de ne pas se contenter de la première méthode trouvée mais plutôt de chercher l'algorithme le plus efficace possible pour résoudre le problème auquel elle sera confrontée.

évaluation:
Le cours ne demande pas de programmation. Il y aura un examen intra, un examen final et un certain nombre d'exercices théoriques. L'évaluation durant le cours se fera avec des notes numériques; la conversion en notation littérale se fera sur la note cumulative finale.

Barème (avec seuil):
Examen intra: 25%
Examen final: 35%
Exercices: 40%

Le seuil: Pour que les exercices comptent dans la note finale, vous devez obtenir une moyenne pondérée d'au moins 40% aux examens.

Livre obligatoire: Gilles Brassard et Paul Bratley, Fundamentals of Algorithmics, Prentice-Hall, 1996.
(La version française originale Algorithmique: conception et analyse, Masson, 1987, ne répond plus entièrement aux besoins du cours.)
Note: Certaines sections du livre correspondent à des sujets que l'étudiant devrait déjà bien connaître. Celles-ci sont indiquées ci-dessous comme lecture libre et il incombera à chacun de s'assurer qu'il maîtrise bien la matière. Si nécessaire, quelques unes de ces notions pourront être survolées en démonstration.

Autres livres utiles: Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction to Algorithms, MIT Press, 1990. Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.

Plan approximatif du cours: