Remerciez-le!

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

Ift2125 Universite ? de Montre ?al De ?partement d ? informatique et de recherche ope ?rationnelle IFT ?? Introduction a l ? algorithmique ?? H Professeur Gilles Brassard Andr ?e ??Aisenstadt brassard iro umontreal ca D ?emonstrateur Hugo C ot ?e coteh ho

Universite ? de Montre ?al De ?partement d ? informatique et de recherche ope ?rationnelle IFT ?? Introduction a l ? algorithmique ?? H Professeur Gilles Brassard 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 probleme donn ?e Parmi plusieurs algorithmes r ?esolvant un m eme probleme lequel choisir Pour illustrer l ? importance de ces questions consid ?erez le probleme du calcul du d ?eterminant Un algorithme classique du a Gauss et Jordan au dix-neuvieme siecle permet de calculer le d ?eterminant d ? une matrice ? 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 premiere 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 Al ? aide de ces m ?ethodes il est possible de pr ?edire la quantit ?e de temps ou de m ?emoire requisea l ? ex ?ecution d ? un algorithme sur des exemplaires de grande taille du problemea r ?esoudre Cette analyse constitue une base de comparaison pour guider le choix de l ? algorithme Le cours IFT 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 premiere m ?ethode trouv ?ee mais pluto t de chercher l ? algorithme le plus e ?cace possible pour r ?esoudre le probl eme auquel vous serez confront ?es E ?valuation 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 Examen ?nal Exercices le vendredi f ?evrier h ?? h AA ?? le mardi avril h ?? h N- pavillon Roger-Gaudry 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 aux examens Horaire lundi h ?? h Z ?? Claire-McNicoll mardi h ?? h AA ?? Premier cours le lundi janvier h Z ?? D ?ebut des TP le vendredi janvier h Z ?? CLivre obligatoire Gilles Brassard