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, Lucien Mousin, Thibault Raffaillac, 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

dernière modification : 28/09/2017 à 09:21:49

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.

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 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 C.Bouillaguet charles.bouillaguet@univ-lille1.fr
2 TP Vendredi 10h20-11h50 M5-A12 C.Bouillaguet charles.bouillaguet@univ-lille1.fr
3 TD Mardi 10h20-11h50 M5-A9 M-É.Voge marie-emilie.voge@univ-lille1.fr
3 TP Jeudi 8h30-10h M5-A13 M-É.Voge marie-emilie.voge@univ-lille1.fr
4 TD Lundi 10h15-11h45 M5-A9 T. Raffaillac thibault.raffaillac@inria.fr
4 TP Lundi 15h20-16h50 M5-A11 T. Raffaillac thibault.raffaillac@inria.fr
5 TD Lundi 10h15-11h45 SUP-109 Lucien Mousin lucien.mousin@univ-lille1.fr
4 TP Lundi 15h20-16h50 M5-A16 Lucien Mousin lucien.mousin@univ-lille1.fr

dernière modification : 31/08/2017 à 17:39:01
Séance Cours TD TP Remarque
1 du 04/09 au 09/09 Lundi 4 septembre 13h30-14h30, M1, Amphi Galois: Présentation du cours et de ses objectifs.

Mardi 5 septembre 15h20-16h50, M1, Amphi Galois: Rapppels sur la complexité et correction des algorithmes. Résumé.
Un QCM est disponible sur moodle La plate-forme d'entraînement à l'algorithmique du FIL est ouverte, et est accessible à l'extérieur du campus via le vpn.
2 du 11/09 au 16/09 Diviser pour régner. Rappels. Diviser pour régner. Jeux de données pour tests. festival MIX CITE jeudi 14 septembre
3 du 18/09 au 23/09 Programmation Dynamique . Résumé de cours. Diviser pour régner. Diviser pour régner. Quelques éléments de correction de la feuille de TD.
4 du 25/09 au 30/09 Programmation Dynamique. Programmation Dynamique. Programmation Dynamique. Quelques éléments de correction de la feuille de TD.
5 du 0é/10 au 07/10 Programmation dynamique (fin). Programmation Dynamique. Programmation Dynamique.
6 du 09/10 au 14/10 Algorithmes gloutons , résumé de cours. Algorithmes gloutons. Programmation Dynamique. Quelques éléments de correction de la feuille de TD.
7 du 16/10 au 21/10 Complexité des Problèmes. Complexité de Problèmes , résumé de cours. Révisions Partie 1. Evaluation série 1 de TPs.
8 du 23/10 au 28/10 DS Complexité des Problèmes. Evaluation série 1 de TPs.
du 30/10 au 04/11 interruption pédagogique automne
9 du 6/11 au 11/11 La classe NP. La classe NP. La classe NP , Quelques données, Quelques données du problème Sum. samedi 11 novembre férié
10 du 13/11 au 18/11 La classe NP. Réductions Polynomiales. La classe NP, les réductions polynomiales. La classe NP. Quelques éléments de correction de la feuille de TD.
11 du 20/11 au 25/11 Problèmes NP-durs. Heuristiques. La classe NP, les réductions polynomiales. La classe NP. Pour ceux qui ont fini le TP3, voici le dernier TP sur les heuristiques.
12 du 27/11 au 02/12 Heuristiques. Heuristiques., Heuristiques. Quelques éléments de correction de la feuille de TD.
13 du 04/12 au 09/12 Pas de cours. Heursitiques ou/et révisions. TP heuristiques.
14 du 12/12 au 16/12 Pas de cours. TBD selon les groupes. TBD selon les groupes.
15 du 18/12 au 22/12 Pas de cours. TBD selon les groupes. TBD selon les groupes.

dernière modification : 04/01/2018 à 21:34:53

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.


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):

dernière modification :