% INF7440 — Conception et analyse des algorithmes % UQAM — Département d'informatique % Plan de cours — Automne 2020 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Blondin Massé, Alexandre PK-4525 Groupes: 040 Description du cours ==================== Rappels sur l'analyse des algorithmes: notations asymptotiques, types d'analyse (pire cas, cas moyen), équations de récurrence et techniques de résolution. Stratégies de conception d'algorithmes séquentiels (diviser pour régner, programmation dynamique, algorithmes voraces): algorithmes déterministes d'exploration d'espaces combinatoires (marche arrière, avec séparation et évaluation progressive). Sujets divers: Algorithmes parallèles , algorithmes probabilistes (méthode Monte-Carlo, chaînes de Markov), heuristiques et algorithmes d'approximation pour problèmes difficiles. Objectif du cours ================= Le cours vise à initier les étudiant(e)s aux principes de base de la conception et de l'analyse des algorithmes. À la fin du cours, l'étudiant(e) devrait être en mesure - d'analyser la complexité et l'efficacité de différents types d'algorithmes; - de choisir les structures de données appropriées selon le contexte; - de concevoir des algorithmes en appliquant les principales stratégies de conception; - d'expliquer et de justifier sa démarche autant à l'oral qu'à l'écrit. Contenu du cours ================ Thèmes abordés, dans l'ordre : - Chapitre 0: Présentation du cours - Chapitre 1: Algorithmes - Chapitre 2: Structures de données - Chapitre 3: Diviser pour régner - Chapitre 4: Programmation dynamique - Chapitre 5: Graphes - Chapitre 6: NP-complétude - Chapitre 7: Séparation et évaluation progressive - Chapitre 8: À déterminer Modalités d'évaluation ====================== DESCRIPTION DATE PONDÉRATION ------------- ----------------------- ------------- Devoir 1 Vendredi 25 septembre 15% Devoir 2 Vendredi 23 octobre 15% Devoir 3 Vendredi 27 novembre 15% Devoir 4 Vendredi 18 décembre 15% Quiz 1 Jeudi 1er octobre 5% Quiz 2 Jeudi 5 novembre 5% Quiz 3 Jeudi 3 décembre 5% Examen oral Jeudi 10 décembre 25% Toutes les évaluations doivent être complétées de façon individuelle. Les devoirs devront être rédigés à l'ordinateur et remis par l'intermédiaire de la plateforme [GitLab](https://gitlab.info.uqam.ca/) du département. Les détails plus précis concernant leur remise seront précisés dans chacun des énoncés. Les quiz se dérouleront sur [Moodle](https://www.moodle2.uqam.ca/). Chaque quiz durera environ une heure et devra être complété à l'intérieur d'une plage de 24 heures. Chaque étudiant.e aura une version différente générée aléatoirement. L'examen oral se déroulera le 10 décembre par l'intermédiaire du logiciel [Zoom](https://uqam.zoom.us/). Il durera au moins 30 minutes par étudiant.e. et portera sur l'ensemble de la matière. Une note inférieure à 50 % dans l'examen oral entraînera un échec au cours, peu importe les résultats obtenus dans les autres composantes de l'évaluation. Les règlements concernant le plagiat seront strictement appliqués. Pour plus de renseignements, consultez le site suivant : Médiagraphie ============ - Site web du cours: - - Cormen, T., Leiserson, C., Rivest, R., Stein, C. - *Introduction à l'algorithmique (3ème édition)* - Dunod (2009). - Knuth, D.E. - *Algorithmes* - CSLI Publications, 2011. - Aho, A.V., Hopcroft, J.E., Ullman, J.D. - *Data Structures and Algorithms* - Addison-Wesley, 1983. - Neapolitan, R. et Naimipour, K. - *Foundations of Algorithms Using Java Pseudocode* - Jones and Bartlett Publishers, 2004. - Motwani, R. et Raghavan, P. - *Randomized Algorithms* - Cambridge University Press, 2006. - Weiss, M.A. - *Data Structures and Algorithm Analysis in C++ (3ème édition)* - Addison Wesley, 2006. - Goodrich, M.,T., Tamassia, R. - *Algorithm Design - Foundations, Analysis, and Internet Examples* - Wiley, 2002. - Levitin, A. - *Introduction to The Design and Analysis of Algorithms (2ème édition)* - Addison Wesley, 2007. - Casanova, H., Legrand, A., Robert Y. - *Parallel Algorithms* - CRC Press, 2009. - Lacomme, P., Prins, C., Sevaux, M. - *Algorithmes de graphes (2ème édition)* - Eyrolles, 2003 - Aho, A.V., Ullman, J.D. - *Foundations of Computer Science* - Computer Science Press, 1992. - Baase, S. - *Computer Algorithms: Introduction to the Design and Analysis of Algorithms - (3e édition)*, Addison-Wesley, 2000. - Brassard, G., Bratley, P. - *Fundamentals of Algorithmics* - Prentice-Hall, 1996. - Brassard, G., Bratley, P. - *Algorithmique: conception et analyse* - Masson, 1987. - Goodrich, M.T. and Tamassia, T. - *Data Structures and Algorithms in Java* - John Wiley & Sons, 1998. - Graham, R.L., Knuth, D.E., Patashnik, O. - *Concrete Mathematics: a Foundation for Computer Science* - Addison-Wesley, 1994. - Harel, D. - *Algorithmics, The Spirit of Computing* - Addison-Wesley, 1987. - Johnsonbaugh R. and Schaefer, M. - Algorithms - Pearson Education, 2004. - Moret, B.M.E. - *Towards a discipline of experimental algorithmics. In Proc. 5th DIMACS Challenge, volume DIMACS Monographs 59, pages 197-213* - American Mathematical Society, 2002. - Rosen, Kenneth H. -- Mathématiques discrètes -- 2e édition, Chenelière/McGraw-Hill, 2001. - Sedgewick, R. - *Algorithms (2e edition)* - Addison-Wesley, 1988.