[PDF] PLAN DE COURS Les cours seront complété

PLAN DE COURS Hiver 2019 Algorithmique (8INF433) Département d'informatique et de mathématique François Lemieux, Ph.D. Adresse électronique: flemieux@uqac.ca Bureau: P4-5170-1 Téléphone: (418) 545-5011 poste 2419

Département d'informatique et de mathématique 8INF433 - Algorithmique Plan de Cours Hiver 2019 Page 2 de 4 Formule pédagogique Les cours magistraux et les travaux dirigés sont dispensés lors de la période réservée au cours et spécifiée à l'horaire de cours officiel. Les cours seront complétés par des lectures et des exercices. Travaux dirigés Les périodes de travaux dirigés auront lieu tous les jeudi de 14h30 à 15h45. Elles seront utilisées en complément des cours magistraux afin de présenter des exemples et des exercices supplémentaires ainsi que corriger les devoirs et les examens. Insertion du cours dans le programme Le cour s est obligatoire dans le pro gramme de baccalauréat en informati que. Les préala bles sont 8INF259 et (8MAT122 ou 8MAP110 ). Objectifs généraux du cours Acquérir les principes de bases pour la conception et l'analyse d'algorithmes efficaces. Objectifs spécifiques du cours Faire comprendre la notion de complexité du traitement informatique. Étudier les différentes techniques permettant d'analyser l'efficacité des algorithmes. Rendre apte à concevoir des algorithmes efficaces. Contenu du cours L'analyse des algorithmes se fera principalement à l'aide de deux outils mathématiques: la notation asymptotique et la résolution d'équations de récurrence. Nous examinerons aussi différentes techniques permettant de concevoir des algorithmes efficaces. Quelques unes des techniques de conception d'algorithmes que nous verrons seront choisies parmi les sujets suivants: • Les algorithmes voraces • La méthode diviser-pour-régner • La programmation dynamique • Les méthodes probabilistes • La transformation du domaine • Les algorithmes parallèles Modalité d'évaluation Travaux pratiques (4) 60 % Examen final 40 %

Département d'informatique et de mathématique 8INF433 - Algorithmique Plan de Cours Hiver 2019 Page 3 de 4 • Aucune documentation ni matériel électronique n'est permis durant l'examen. • À moins d'avis contraire l'examen final sera le jeudi 25 avril 2019 de 13h00 à 15h30 Présentation et rédaction des travaux Tout travail remis doit être conforme aux exigences de la politique institutionnelle en matière de présentation et rédaction des travaux. Les travaux non conformes ou présentant des déficiences linguistiques devront être repris à l'intérieur d'un délai déterminé par l'enseignant. Cette reprise sera prise en considération au moment de l'attribution de la note. Pénalité pour retard Chacun des devoirs contiendra une date de remise. Les devoirs remis après cette date se verront pénalisés de 10% par journée de retard. Note de passage La note de passage est de à 60 % avec un seuil de 50% dans l'examen final. Évaluation du cours Ce cours sera évalué, conformément à la procédure relative à l'évaluation de la qualité de l'enseignement par les étudiants de premier cycle. Périodes de disponibilité Le professeur sera disponible à son bureau (local) en dehors des heures régulières du cours aux heures suivantes : • Mardi de 9h00 à 11h00 Veuillez noter que le professeur peut être disponible en dehors de ces périodes. Vous êtes invités à passer à son bureau afin de vérifier sa disponibilité ou de prendre rendez-vous. Références T. Cormen, C.E. Leiserson et R.L. Rivest: Algorithmique : cours avec 957 exercices et 158 problèmes, Dunod 2010. G. Brassard et P. Bratley: Algorithmique: conception et analyse, Masson/Presse de l'Université de Montréal, 1987 G. Brassard et P. Bratley: Fundamentals of Algorithmics, Prentice Hall, 1996 1987 E. Horowitz et S. Sahni: Fundamentals of Computer Algorithms, Computer Science Press, 1978.

Département d'informatique et de mathématique 8INF433 - Algorithmique Plan de Cours Hiver 2019 Page 4 de 4 Contenu détaillé Dans la mesure du possible, nous essaierons de suivre le calendrier suivant : SEMAINE DU : SUJETS : 7 janvier : Introduction, présentation du plan de cours et rappels mathématiques 14 janvier : Pseudo-code, temps d'exécution et notation asymptotique 21 janvier : Notation asymptotique, algorithmes élémentaires (Devoir 1 à remettre le 5 février) 28 janvier: Algorithmes voraces 4 février: Résolution d'équations de récurrence 11 février : Résolution d'équations de récurrence (Devoir 2 à remettre le 28 février) 18 février : Algorithmes diviser-pour-régner 25 février : Algorithmes diviser-pour-régner 4 mars : RELÂCHE 11 mars : Programmation dynamique et mémoïsation 18 mars : Programmation dynamique et mémoïsation (Devoir 3 à remettre le 2 avril) 25 mars : Algorithmes probabilistes 1 avril: Algorithmes probabilistes (Devoir 4 à remettre le 16 avril) 8 avril : Introduction à la cryptologie 15 avril : Algorithmes parallèles (si le temps le permet) 22 avril : EXAMEN FINAL (le 25 avril)