Formations en Informatique de Lille
Portail pédagogique
Vous êtes ici : FIL > Portail > Master Info > Machine Learning > ACT
Algorithmique et ComplexiTé (UE: ACT)
Informations Générales
Responsable Bilel Derbel, Sophie Tison, Marie-Émilie Voge
Semestre S1
Enseignement Obligatoire -- Présentiel
UEs pré-requises
Modalités d’évaluation Contrôle continu -voir moodle
Bloc de compétences Algorithmique
Répartition horaire CM CTD TD TP à distance total
Heures encadrées 12 18 18 48
Travail Personnel 48

Objectifs

Le but de l'algorithmique peut être résumé en " trouver un "bon" algorithme " pour un problème donné. Cela soulève de nombreuses questions:

  • Existe-t-il un algorithme pour résoudre le problème? ( calculabilité, indécidabilité)
  • Le problème est-il un "classique"? (modélisation, reformulation, connaissances)
  • Comment concevoir un algorithme? (algorithmes corrects par construction, paradigmes)
  • L'algorithme apporte-t-il bien la réponse au problème donné? ( correction des algorithmes)
  • Que dire des ressources utilisées par l'algorithme? (analyse d'algorithmes)
  • L'algorithme est-il "raisonnablement" efficace? Pourrait-on faire mieux? Que dire des ressources minima nécessaires pour résoudre le problème? Peut-on espérer avoir un algorithme "rapide" exact? Le problème est-il "dur"? (complexité des problèmes)
  • Que faire face à un problème dur?

L'objectif du cours est de préparer à répondre à ces questions difficiles, d'entraîner au "computational thinking", donc de développer les compétences suivantes :

  • analyser un problème - modélisation, reformulation, réduction, complexité
  • concevoir une solution algorithmique appropriée, exacte ou approchée, en utilisant à bon escient les structures et paradigmes classiques- programmation dynamique, algorithme glouton, recherche exhaustive ou/et les méthodes heuristiques, ...
  • analyser cette solution - correction, garantie, complexité

Équipe pédagogique

N. Berveglieri, M. Bilasco, B.Derbel, P. Fortin, S. Tison, M-E. Voge

Plus d'informations sont disponibles sur la page Moodle du Cours qui sera la page de référence du cours pour la mise à disposition de ressources.

Programme succinct

Le cours comporte trois parties:
  • Paradigmes classiques de conception d'algorithmes (programmation dynamique, diviser et régner, algorithmes gloutons, backtracking, ...) (resp. S. Tison)
  • Complexité de problèmes: classes P, NP et EXPTime; réductions polynomiales; problèmes NP-durs. (resp/ M.-E. Voge)
  • Algorithmique avancée: Quelques méthodes pour résoudre de manière exacte ou approchée des problèmes NP-durs (Branch-and-Bound, algorithmes probabilistes, heuristiques, méta-heuristiques, ...) (resp. B. Derbel).
  • Le cours sera éventuellement complété par une séance sur éthique et algorithmes.

Compétences

  • maîtriser plusieurs notions de complexité des algorithmes,
  • connaître des paradigmes classiques d'algorithmes et savoir les mettre en oeuvre,
  • comprendre la notion de la complexité d’un problème et les principales classes de complexité,<
  • concevoir des réductions polynomiales entre problèmes,
  • trouver des bornes inférieures et supérieures pour la complexité des problèmes,
  • mettre en oeuvre des heuristiques pour résoudre des problèmes difficiles.