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

ACT - ALgorithmes et ComplexiTé

Responsable

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

Equipe pédagogique

Nicolas Berveglieri, Bilel Derbel, Pierre Fortin, 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
dernière modification : 02/09/2019 à 16:08:10

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. Paradigmes classiques de conception d'algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, ...).
  2. Complexité de problèmes, Classes P, NP et EXPTime, Réductions polynomiales, NP-dureté.
  3. 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, ...)
  4. Le cours sera complété par une ou deux séances : décidabilité, éthique des algorithmes, ...
Sophie Tison
dernière modification : 02/09/2019 à 16:06:05
Gpe Nature Horaire Salle Enseignant e-mail
Cours Lundi 9h-10h M5-Amphi Bachus S.Tison sophie.tison@univ-lille1.fr
1 TD Lundi 10h15-11h45 M5-A1 S. Tison sophie.tison@univ-lille.fr
1 TP Mercredi 13h50-15h M5-A13 S. Tison sophie.tison@univ-lille.fr
2 TD Vendredi 8h30-10h M5-A7 P. Fortin pierre.fortin@univ-lille.fr
2 TP Vendredi 10h20-11h50 M5-A12 P. Fortin pierre.fortin@univ-lille.fr
3 TD Mardi 10h20-11h50 M5-A1 M-É.Voge marie-emilie.voge@univ-lille.fr
3 TP Jeudi 8h30-10h M5-A13 M-É.Voge marie-emilie.voge@univ-lille.fr
4 TD Jeudi 8h30-10h Bilel Derbel bilel.derbel@univ-lille.fr
4 TP Lundi 15h20-16h50 M5-A11 Bilel Derbel bilel.derbel@univ-lille.fr
5 TD Lundi 10h15-11h45 M5-A9 Nicolas Berveglieri Nicolas Berveglieri@univ-lille.fr
5 TP Lundi 15h20-16h50 M5-A14 Nicolas Berveglieri Nicolas Berveglieri@univ-lille.fr
Sophie Tison
dernière modification : 02/09/2019 à 21:09:04
Séance Cours TD TP Remarque
1 du 09/09 au 14/09 Présentation, Rappels.
Résumé.
Rappels d'analyse d'algorithmes. Rappels. Echauffement sur quelques algorithmes. Tests Cible. Tests Equilibre. Nouvelle version de Tests pour Allumer, l'ancienne était erronnée. La plate-forme d'entraînement à l'algorithmique du FIL est ouverte, et est accessible à l'extérieur du campus via le vpn.
Festival MIX CITE jeudi 12 septembre après-midi
2 du 16/09 au 21/09 Diviser pour régner. Diviser pour régner. TP Diviser pour régner. Tests TP.
3 du 23/09 au 28/09
Programmation dynamique.
Résumé.
Programmation dynamique. TP Diviser pour régner. Pour aller plus loin programmation dynamique et évaluation paresseuse en Haskell, voir par exemple ce blog.
4 du 30/09 au 05/10
Programmation dynamique.
Programmation dynamique. TP Programmation dynamique. Quleques jeux de données pour tester.
5 du 07/10 au 12/10
Algorithmes gloutons exacts.
Résumé.
Algorithmes gloutons exacts. TP Programmation dynamique. Si vous avez 15 minutes, vous pouvez répondre en ligne à des questions sur des aspects variés de l'informatique et participer à ce concours
6 du 14/10 au 19/10
La classe NP.
Résumé.
Révisions. TP Programmation dynamique.
7 du 21/10 au 26/10 DS La classe NP TPs partie 1: recette.
du 28/10 au 02/11 interruption pédagogique automne
8 du 4/11 au 09/11 Réductions polynomiales. Réductions polynomiales. TP NP
9 du 11/11 au 16/11 Pas de cours (jour férié). Réductions polynomiales. Réductions polynomiales. lundi 11 novembre férié
10 du 18/11 au 23/11 Heuristiques. Heuristiques TP Heuristiques
12 du 25/11 au 30/11 Mariages stables. Ethique des algorithmes. Révisions. TP Heuristiques
12 du 02/12 au 09/12 Décidabilité. TP Heuristiques
13 du 10/12 au 14/12 TBD. Recette TPs.
14 du 16/12 au 21/12
Sophie Tison
dernière modification : 13/10/2019 à 19:41:52

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.

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. Programmation efficace, par Christoph Durr et Jill-Jenn Vie, Editions Ellipses, qui est plutôt une préparation aux concours de programmation.

Annales

Voici quelques annales de ACT:
Sophie Tison
dernière modification : 26/11/2018 à 16:24:34