Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Universit´ e de Montr´ eal D´ epartement d’informatique et de recherche op´ era

Universit´ e de Montr´ eal D´ epartement d’informatique et de recherche op´ erationnelle IFT 2125 — Introduction ` a l’algorithmique — H17 Professeur : Gilles Brassard, 2215 Andr´ e –Aisenstadt, brassard@iro.umontreal.ca D´ emonstrateur : Hugo Cˆ ot´ e, coteh@hotmail.fr Site web du cours : http://www.iro.umontreal.ca/~brassard/cours/algo Objectifs : Comment d´ evelopper un algorithme eﬃcace pour r´ esoudre un probl` eme donn´ e ? Parmi plusieurs algorithmes r´ esolvant un mˆ eme probl` eme, lequel choisir ? Pour illustrer l’importance de ces questions, consid´ erez le probl` eme du calcul du d´ eterminant. Un algo- rithme classique, dˆ u ` a Gauss et Jordan au dix-neuvi` eme si` ecle, permet de calculer le d´ eter- minant d’une matrice 20 × 20 en une fraction de seconde sur un ordinateur contemporain. Un autre algorithme tout aussi classique, bas´ e sur la d´ eﬁnition r´ ecursive du d´ eterminant, prendrait des milliers d’ann´ ees pour arriver au mˆ eme r´ esultat ! L’algorithmique propose des r´ eponses ` a ces questions. Pour la premi` ere, il y a un ensemble de techniques g´ en´ erales de conception d’algorithmes. Nous ´ etudierons par exemple l’approche vorace, la technique diviser-pour-r´ egner, la programmation dynamique et l’approche probabiliste. Pour la seconde question, l’algorithmique oﬀre des techniques d’analyse de l’eﬃcacit´ e d’algorithmes bas´ ees principalement sur la r´ esolution de r´ ecurrences et les notations asymptotiques. ` A l’aide de ces m´ ethodes, il est possible de pr´ edire la quan- tit´ e de temps ou de m´ emoire requise ` a l’ex´ ecution d’un algorithme sur des exemplaires de grande taille du probl` eme ` a r´ esoudre. Cette analyse constitue une base de comparaison pour guider le choix de l’algorithme. Le cours IFT 2125 vous permettra d’apprendre ` a concevoir des algorithmes, d’analyser l’eﬃcacit´ e de ceux-ci et de vous familiariser avec des techniques math´ ematiques pertinentes. Vous d´ evelopperez le r´ eﬂexe de ne pas vous contenter de la premi` ere m´ ethode trouv´ ee mais plutˆ ot de chercher l’algorithme le plus eﬃcace possible pour r´ esoudre le probl` eme auquel vous serez confront´ es. ´ Evaluation : Le cours ne demande pas de programmation. Il y aura un examen partiel, un examen ﬁnal cumulatif et un certain nombre d’exercices th´ eoriques. Examen partiel 30% (le vendredi 17 f´ evrier, 10h30 – 12h20, AA–1360) Examen ﬁnal 40% (le mardi 18 avril, 12h30 – 15h20, N-615, pavillon Roger-Gaudry) Exercices 30% (exercices th´ eoriques r´ eguliers) C’est un bar` eme avec seuil : Pour que les exercices comptent dans la note ﬁnale, vous devez obtenir une moyenne pond´ er´ ee d’au moins 40% aux examens. Horaire : lundi 14h30 –15h20, Z–330, Claire-McNicoll ; mardi 12h30 –14h20, AA–1177. Premier cours : le lundi 9 janvier, 14h30, Z–330. D´ ebut des TP : le vendredi 13 janvier, 10h30, Z–330. Livre obligatoire : Gilles Brassard et Paul Bratley, Fundamentals of Algorithmics, Prentice-Hall, 1996. Note : Certaines sections du livre correspondent ` a des sujets que vous devriez d´ ej` a bien connaˆ ıtre. Celles-ci sont indiqu´ ees ci-dessous comme lecture libre et il incombera ` a chacun de s’assurer de la maˆ ıtrise de cette mati` ere, qui pourra faire l’objet de questions aux examens mˆ eme si elle n’a pas ´ et´ e vue en classe. Si n´ ecessaire, quelques-unes de ces notions pourront ˆ etre survol´ ees en d´ emonstration. Autres livres utiles : Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction to Algorithms, 3e ´ edition, MIT Press, 2009. Alfred V. Aho, John E. Hopcroft et Jeﬀrey 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 et quelque peu sp´ eculatif du cours : ⋄Semaine 1 : 9 et 10 janvier. Motivations : §§1.1, 1.2, Chapitre 2 ; Savez-vous multiplier ? : §7.1 ; Notation asymptotique : §3.1. [Lecture libre : §§1.3–1.7 (sauf §1.7.4) ; §3.2, §3.3.] ⋄Semaine 2 : 16 et 17 janvier. Notation asymptotique (suite) : §§3.4–3.6 ; R´ esolution de r´ ecurrences : §4.7. [Lecture libre : §§4.1 – 4.5.] ⋄Semaine 3 : 23 et 24 janvier. R´ esolution de r´ ecurrences (suite) : §4.7. ⋄Semaine 4 : 30 et 31 janvier. Algorithmes voraces: §§6.1, 6.2, 6.4, 6.5. [Lecture libre: §§5.1 – 5.5, 5.7, §6.3.] ⋄Semaine 5 : 6 et 7 f´ evrier. Diviser-pour-r´ egner : §7.1 (rappel), §§7.2–7.4. ⋄Semaine 6 : 13 et 14 f´ evrier. Diviser-pour-r´ egner (suite) : §§7.5–7.7 ; Cryptographie : §7.8. ⋄Semaine 7 : 20 et 21 f´ evrier. Programmation dynamique : §§8.1–8.4. [Lecture libre : §8.5.] ⋄Semaine 8 : 6 et 7 mars. Programmation dynamique (suite) : §§8.6–8.8. Graphes de jeu : §9.1. ⋄Semaine 9 : 13 et 14 mars. Parcours de graphes : §§9.2–9.5. ⋄Semaine 10 : 20 et 21 mars. Graphes implicites et retour arri` ere : §9.6. ⋄Semaine 11 : 27 et 28 mars. Algorithmes probabilistes : §§10.1–10.5. ⋄Semaine 12 : 3 et 4 avril. Algorithmes probabilistes (suite) : §§10.6, 10.7. ⋄Semaine 13 : 10 et 11 avril. Introduction ` a la complexit´ e du calcul : §§12.1, 12.2, 12.4. uploads/Litterature/ ift2125.pdf