% INF5130 — Algorithmique % UQAM — Département d'informatique % Plan de cours — Hiver 2023 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Laforest, Louise PK-4725 Enseignement ------------- Willems, Matthieu PK-4660 Groupes: 010 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 - Résolution des équations de récurrence - Diviser pour régner - Programmation dynamique Après l'intra : - Algorithmes gloutons - Algorithmes randomisés - Algorithmes à retour arrière - Algorithmes sur les graphes - NP-Complétude - Théorie de l'information Modalités d'évaluation ====================== Description sommaire Date de remise Pondération ---------------------- --------------------- ------------- Devoir 1 Vendredi 17 février 15 % Examen intra Lundi 20 février 35% Devoir 2 Vendredi 21 avril 15 % Examen final Lundi 24 avril 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 devoirs). 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. 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. 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.