Vous êtes ici : FIL > Portail > Master Informatique > M1S1 > ACT

Algorithmes et ComplexiTé

Sophie Tison, Bât. M3, 3ème étage, bureau 328

Equipe pédagogique

Charles Bouillaguet,Yoann Dufresne, Pierre Fortin, Samuel Hym, Sophie Tison, Marie-Emilie Voge

Volume horaire

Cet enseignement obligatoire a lieu au premier semestre du Master1. Il est organisé sur douze semaines, en une séance hebdomadaire de cours d'une durée d'1h, une séance hebdomadaire de Travaux Dirigés d'une durée de 1h30 et une séance hebdomadaire de TP d'une durée de 1h30

Crédits

5 ECTS
Sophie Tison
dernire modification : 09/09/2015 08:43:37

Objectifs

Le but de l'algorithmique peut être résumé par: trouver un "bon" algorithme pour un problème donné. Cela soulève de nombreuses questions:
  1. Existe-t-il un algorithme pour résoudre le problème? ( calculabilité, indécidabilité).
  2. Le problème est-il un "classique"? (modélisation, reformulation, connaissances).
  3. Comment concevoir un algorithme? (algorithmes corrects par construction, paradigmes)
  4. L'algorithme apporte-t-il bien la réponse au problème donné? ( orrection des algorithmes)
  5. Que dire des ressources utilisées par l'algorithme? (analyse d'algorithmes)
  6. L'algorithme est-il "raisonnablement" efficace? Pourrait-on faire mieux? Que dire des ressources minima nécessaires pour résoudre le problème? (complexité des problèmes)
  7. Peut-on espérer avoir un algorithme "rapide" exact? Le problème est-il "dur"? (NP-dureté)
  8. Que faire face à un problème dur?
L'objectif du cours est de préparer les étudiants à répondre à ces questions difficiles, de les entraîner au "computational thinking". A l'issue de ce module, les étudiants doivent être donc capables:
  1. d'analyser un problème - modélisation, reformulation, complexité, réduction.
  2. de concevoir une solution algorithmique appropriée, exacte ou approchée, en particulier en utilisant à bon escient les structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive, heuristique, ...-
  3. d'analyser cette solution -correction, complexité, efficacité, ... .

Contenu

  1. Rappels sur les notions de complexité et correction d'algorithmes.
  2. Paradigmes classiques de conception d'algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, ...).
  3. Complexité de problèmes, Classes P, NP et EXPTime, Réductions polynomiales, NP-dureté.
  4. Quelques méthodes "avancées" pour résoudre de manière exacte ou approchée des problèmes NP-durs (Branch-and-Bound, algorithmes probabilistes, heuristiques, méta-heuristiques, ...)

Bibliographie

Il y a de nombreuses ressources en ligne sur le domaine. Il y a également de nombreux livres excellents sur l'algorithmique et la complexité, par exemple:
  1. Introduction à l'algorithmique, par Thomas H. Cormen, Charles Leiserson, Ronald Rivest, (Editions Dunod, disponible à la BU), livre référence en algorithmique
  2. Algorithms, par Robert Sedgewick et Kevin Wayne, qui se présente comme essential information that every serious programmer needs to know about algorithms and data structures avec un site associé à la quatrième édition
  3. Algorithm Design Manual, avec beaucoup d'applications concrètes, par Steven Skiena dont le site contient de nombreuses ressources en ligne
  4. Algorithm Design, par John Kleinberg et Eva Tardos (Editions Addison Wesley 2005) qui est aussi tourné vers les applications (voir le site associé )
  5. A guide to Algorithm Design, par Anne Benoit, Yves Robert et Frédéric Vivien, (Editions CRC Press) avec de nombreux exercices corrigés
  6. Sur l'aspect "algorithmic pattern", par Bruno R. Preiss, Data Structures and Algorithms with object-oriented design patterns in Java, disponible sur le Web.
Sophie Tison
dernire modification : 26/08/2014 10:53:35
Gpe Nature Horaire Salle Enseignant e-mail
Cours Lundi 9h-10h M1-Amphi Painlevé S.Tison sophie.tison@univ-lille1.fr
1 TD Lundi 10h15-11h45 M5-A4 S. Tison sophie.tison@univ-lille1.fr
1 TP Mercredi 15h50-17h20 M5-A11 S. Tison sophie.tison@univ-lille1.fr
2 TD Vendredi 8h30-10h M5-A7 P.Fortin/C.Bouillaguet charles.bouillaguet@univ-lille1.fr
2 TP Vendredi 10h20-11h50 M5-A12 P.Fortin/C.Bouillaguet charles.bouillaguet@univ-lille1.fr
3 TD Mardi 10h20-11h50 M5-A13 M-É.Voge marie-emilie.voge@univ-lille1.fr
3 TP Jeudi 8h30-10h M5-A7 M-É.Voge marie-emilie.voge@univ-lille1.fr
4 TD Lundi 10h15-11h45 M5-A9 Y. Dufresne yoann.dufresne@ed.univ-lille1.fr
4 TP Lundi 15h20-16h50 M5-A14 Y. Dufresne yoann.dufresne@ed.univ-lille1.fr
5 TD Lundi 10h15-11h45 SUP-109 Samuel Hym samuel.hym@univ-lille1.fr
4 TP Lundi 15h20-16h50 M5-A16 Samuel Hym samuel.hym@univ-lille1.fr
Sophie Tison
dernire modification : 12/09/2016 11:11:56
Un petit QCM est à votre disposition sur Moodle.
Séance Cours TD TP Remarque
1 du 05/09 au 10/09
2 du 12/09 au 17/09 Lundi 12 septembre 13h30-14h30, M1, Amphi Painlevé: Présentation du cours et de ses objectifs.

Mardi 13 septembre 15h20-16h50, M1, Amphi Painlevé: Rapppels sur la complexité et correction des algorithmes.
Pas de TD.
Un petit QCM est à votre disposition sur Moodle.
Pas de TP
  • festival MIX CITE jeudi 15 septembre
3 du 19/09 au 24/09 Diviser pour régner Rappels. Diviser pour régner. Le sujet , quelques jeux de données De nombreux quizzes sur "Computer Science Quizzes for Geeks !".
4 du 26/09 au 01/10 Programmation Dynamique Diviser pour régner Diviser pour régner (le sujet a été enrichi).
5 du 03/10 au 08/10 Programmation Dynamique (fin) Programmation Dynamique Programmation Dynamique
6 du 10/10 au 15/10 Algorithmes gloutons , résumé de cours Programmation Dynamique Programmation Dynamique
7 du 17/10 au 22/10 Reporté. Programmation Dynamique Programmation Dynamique. Recette TPs 1 et 2. La correction du petit QCM de rentrée est à votre disposition sur Moodle.
8 du 24/10 au 05/11 Complexité des Problèmes , résumé de cours Algorithmes gloutons
quelques exercices corrigés
Recette des Tps1 et 2. Devoir surveillé le 24/10 de 14h à 15h en amphi Pailevé. Le corrigé du DS.
interruption pédagogique d'automne du 27/10 au 02/11 inclus
9 du 7/11 au 12/11 La classe NP Complexité des problèmes, les classes P et NP La classe NP, les réductions. Le sujet , quelques jeux de données , une proposition sommaire d'architecture de code vendredi 11 novembre férié
10 du 14/11 au 19/11 Les réductions polynomiales, les propriétés NP-dures. Les réductions polynomiales, les propriétés NP-dures.
quelques exercices corrigés
La classe NP, les réductions (cf semaine précédente).
11 du 21/11 au 26/11 Les propriétés NP-dures (fin). Les réductions polynomiales, les propriétés NP-dures. La classe NP, les réductions (cf semaine précédente). Pour ceux qui ont fini, voici le dernier sujet de TP
12 du 28/11 au 03/12 Heuristiques Heuristiques Heuristiques
13 du 05/12 au 10/12 Méta-heuristiques Heuristiques
quelques exercices corrigés
Heuristiques
14 du 13/12 au 17/12 Pas de cours Révisions Recette des TPs 3 et 4
Sophie Tison
dernire modification : 25/12/2016 19:16:06

L'évaluation s'eefectue selon une procédure de contrôle continu et un examen en fin de semestre. Le contrôle continu sera basé sur:

  • TP : une note sur 20 de Travaux Pratiques attribuée par l'enseignant de Travaux Pratiques.
  • DS : une note sur 20 d'un devoir surveillé en milieu de semestre.
La note de contrôle continu (CC) sera CC=(2*TP+DS)/3, majoré éventuellement d'un Bonus donné par l'enseigant de TD/TP (devoirs maison, …)

La note finale sur 20 (N) sera N=sup(EX,(EX+CC)).

Pour la seconde session, la note de Contrôle Continu est conservée. Seule la note d'examen est remplacée par la note obtenue lors de la seconde session.

L'unité acquise apporte 5 ECTS.

Sophie Tison
dernire modification : 02/09/2016 11:07:05

Les résumés de cours et les transparents de cours, les sujets de TD et de TP seront mis sur le semainier au fur et à mesure. Une copie papier des résumés de cours sera distribuée en amphi lors du cours.

Annales

Voici quelques annales de ACT dont c'est la troisième année sous cette forme et de l'ancienne UE AAC assez proche dans le contenu (attention, le programme a évolué et certaines notions au programme d'AAC ne le sont pas pour ACT):
Sophie Tison
dernire modification :