% INF5130 — Algorithmique % UQAM — Département d'informatique % Plan de cours — Automne 2019 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Laforest, Louise PK-4725 poste 7790 Description du cours ==================== Objectifs --------- Le cours vise à initier les étudiant.e.s aux principes de base de la conception et de l'analyse des algorithmes séquentiels. À la fin du cours, l'étudiant-e devrait être capable : - de connaître les algorithmes de base de l'informatique ; - d'analyser la complexité et l'efficacité de différents types d'algorithmes ; - de connaître les grands principes de la conception des algorithmes et de pouvoir les appliquer ; - de comprendre la notion de problème NP-complet; - de comprendre la théorie de l'information. Sommaire du contenu ------------------- Introduction à la théorie de l'information. Entropie, information mutuelle et conditionnelle. Codes de longueur fixe/variable, théorème fondamental du codage de source. Détection et correction d'erreurs, distance de Hamming, codes linéaires. Rappels sur la notation asymptotique. Complexité temporelle et spatiale, analyse probabiliste. Équations de récurrence et théorème fondamental. Algorithmes de force brute et voraces. Principe «diviser pour régner». Programmation dynamique. Algorithmes randomisés. Algorithmes à retour arrière. Méthode de séparation et d'évaluation progressive (Branch-and- bound). Heuristiques. Machine de Turing : le problème de l'arrêt, la question P=NP. Réductions et NP-complétude. Modalité d'enseignement ----------------------- Ce cours comporte une séance obligatoire de laboratoire (2 heures). Préalables académiques ---------------------- INF3105 - Structures de données et algorithmes Contenu du cours ================ Avant l'intra : - Présentation du cours, problèmes et algorithmes - Complexité des algorithmes - Rappels mathématiques et théorème général - Diviser pour régner - Programmation dynamique - Algorithmes gloutons Après l'intra : - Algorithmes randomisés - Algorithmes à retour arrière - Méthode de séparation et d'évaluation progressive (Branch-and- bound) - Heuristiques - NP-Complétude - Théorie de l'information Modalités d'évaluation ====================== Description sommaire Date Pondération ---------------------- ---------------------- ------------- Devoir 1 Vendredi 25 octobre 15 % Examen intra Lundi 28 octobre 35% Devoir 2 Vendredi 13 décembre 15 % Examen final Lundi 16 décembre 35% Les examens sont individuels et les devoirs seront faits en équipes comportant au plus deux étudiants. Les devoirs devront être remis de façon électronique via moodle et une pénalité sera appliquée en cas de remise en retard (détails sur chaque énoncé de devoir). L'utilisation de documentation papier personnelle (notes de cours, manuels) est permise aux examens. Une moyenne inférieure à 50 % aux examens entraîne l'échec au cours peu importe les résultats obtenus pour les devoirs. L'utilisation de livres et de documentation personnelle est permise aux examens. Les calculatrices, téléphones cellulaires, ordinateurs portables et appareils électroniques sont strictement interdits durant les examens. En cas de plagiat ou de fraude, la sanction peut aller de la note zéro pour le travail ou l'examen, jusqu'à l'exclusion de l'université. Les règlements concernant le plagiat seront strictement appliqués. Pour plus de renseignements, consultez le site suivant : Médiagraphie ============ - Site web du cours sur moodle : - Cormen, T., Leiserson, C., Rivest, R., Stein, C. -- Algorithmique (3ème édition) -- Dunod (2010). - Cormen, T. -- Algorithmes - Notions de base -- Dunod (2013). - Neapolitan, R. et Naimipour, K. -- Foundations of Algorithms Using Java Pseudocode -- Jones and Bartlett Publishers, 2004. - Weiss, M.A. -- Data Structures and Algorithm Analysis in C++ (3ème édition) -- Addison Wesley, 2006. - Levitin, A. -- Introduction to The Design and Analysis of Algorithms (2ème édition) -- Addison Wesley, 2007. - Aho, A.V., Hopcroft, J.E., Ullman, J.D. -- Data Structures and Algorithms -- Addison-Wesley, 1983. - 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, K.H. -- Discrete Mathematics and its Applications -- 1995 (version révisée en 1999). - Sedgewick, R. -- Algorithms (2e edition) -- Addison-Wesley, 1988.