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

ACT - ALgorithmes et ComplexiTé

Responsable

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

Equipe pédagogique

Charles Bouillaguet, Pierre Fortin, Thibault Raffaillac, Sophie Tison, Marie-Emilie Voge, Carlos Zubiaga Pena

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
dernière modification : 04/09/2018 à 14:19:04

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
dernière 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 S. Tison sophie.tison@univ-lille1.fr
1 TP Mercredi 15h50-17h20 S. Tison sophie.tison@univ-lille1.fr
2 TD Vendredi 8h30-10h C.Bouillaguet/ P. Fortin charles.bouillaguet@univ-lille1.fr
2 TP Vendredi 10h20-11h50 C.Bouillaguet /P. Fortin charles.bouillaguet@univ-lille1.fr
3 TD Mardi 10h20-11h50 M-É.Voge marie-emilie.voge@univ-lille1.fr
3 TP Jeudi 8h30-10h M-É.Voge marie-emilie.voge@univ-lille1.fr
4 TD Lundi 10h15-11h45 Carlos Zubiaga
4 TP Lundi 15h20-16h50 Carlos Zubiaga
5 TD Lundi 10h15-11h45 Lucien Mousin lucien.mousin@univ-lille1.fr
4 TP Lundi 15h20-16h50 Lucien Mousin lucien.mousin@univ-lille1.fr
Sophie Tison
dernière modification : 14/09/2018 à 11:07:13
Séance Cours TD TP Remarque
0 36 du 03/09 au 09/09 Présentation et Rappels . Résumé Un QCM de révision est disponible sur moodle (Clef: M1ACT2018) ( version pdf)
La plate-forme d'entraînement à l'algorithmique du FIL est ouverte, et est accessible à l'extérieur du campus via le vpn.
1 37 du 10/09 au 16/09 Diviser pour régner Rappels Le sujet de TP pour les prochaines séances, à rendre pour la semaine du 1er octobre. Des jeux de données pour tester , avec la valeur attendue dans le nom du fichier .
Pas de Tps cette semaine.
2 38 du 17/09 au 23/09 Programmation Dynamique , Résumé Diviser pour régner Diviser pour régner
3 39 du 24/09 au 29/09 Programmation Dynamique Programmation Dynamique Diviser pour régner
4 40 du 1/10 au 7/10 Algorithmes gloutons Programmation Dynamique Programmation Dynamique
5 41 du 8/10 au 14/10 Complexité des problèmes Algorithmes gloutons Programmation Dynamique
6 42 du 13/10 au 18/10 La classe NP Révisions Programmation Dynamique
7 43 du 20/10 au 25/10 DS La classe NP Rendu TPs 1 et 2. Interruption pédagogique
44 du 27/10 au 01/11 interruption pédagogique d'automne
8 45 du 3/11 au 08/11 Réductions polynomiales. Problèmes NP-durs. Réductions polynomiales. Problèmes NP-durs. La classe NP
9 46 du 10/11 au 15/11 Heuristiques Réductions polynomiales. Problèmes NP-durs. La classe NP mardi 11 novembre férié
10 47 du 17/11 au 22/11 Méta-Heuristiques. Heuristiques Heuristiques
11 48 du 24/11 au 29/11 Bilan Révisions Heuristiques
12 49 du 01/12 au 06/12 Révisions Heuristiques
13 50 du 08/12 au 13/12 Rendu TPs 3 et 4
14 51 du 15/12 au 20/12
Sophie Tison
dernière modification : 26/09/2018 à 13:43:51

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)/2).

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
dernière modification : 05/12/2017 à 15:43:15

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 quatriè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
dernière modification : 03/09/2018 à 15:13:46