Formations en Informatique de Lille
Portail pédagogique
Vous êtes ici : FIL > Portail > Master Info > Machine Learning > ACA
Algorithmique et complexité avancée (UE: ACA)
Informations Générales
Responsable Sylvain Salvati
Semestre S2
Enseignement Obligatoire -- Présentiel
UEs pré-requises ACT
Modalités d’évaluation CC+CT
Structure ECTS
Élément de cours Algorithmique et complexité avancée
Unité d’enseignement ACA 6
Bloc de compétence Algorithmique
Répartition horaire CM CTD TD TP à distance total
Heures encadrées 12 12 24
Heures Projet
Travail Personnel 24
Stage

dernière modification : 09/11/2021 à 07:44:01

Objectifs

L’objectif du cours est de permettre aux étudiants de maîtriser une boîte à outils de méthodes variées pour faire face aux problèmes difficiles. Il s’agit également de bien comprendre le type de compromis que font ses méthodes afin de pouvoir évaluer dans quelles circonstances il est possible de les utiliser. Enfin l’évocation de la théorie de la complexité permettra aux étudiants de comprendre les limites de ces approches.

Programme succinct

Lorsque l’on cherche à résoudre un problème difficile (au sens de la complexité), il peut être intéressant de faire des compromis entre la qualité de la solution trouvée et les ressources de calcul utilisées pour la trouver. On parle alors d’algorithme d’approximation. Il est également possible de cherche à avoir une bonne solution avec une forte probabilité ou une utilisation d’un faible nombre de ressources de calcul avec une forte probabilité. L’utilisation du hasard permet également de trouver des solutions ayant de bonne propriété.

Ce cours se propose de présenter les principales façons de construire des algorithmes d’approximation comme: les algorithmes gloutons, la recherche locale, la relaxation convexe, les méthodes primal-dual, ou encore l’échantillonnage aléatoire. Le cours abordera de nombreux problèmes d’approximation comme la couverture de graphes par sommets, le problèmes de Knapsack,…

Concernant les algorithmes probabilistes, le cours présentera les principaux types d’algorithmes comme Las Vegas et Monte Carlo. Une analyse de l’exemple historique du test de primalité de Miller-Rabin sera présentée ainsi que quelques exemples de chaque types d’algorithme probabiliste pour des problèmes de graphes classiques.

Une attention particulière sera portée à la démonstration des qualités des solutions trouvée pas les algorithmes. Il s’agit de pouvoir offrir des garanties sur le fonctionnement des algorithmes d’approximation ou sur les résultats des algorithmes probabilistes.

Enfin, les lien avec la théorie de la complexité, en particulier des classes PTAS, APX pour les problèmes d’approximation, ZPP et BPP pour les algorithmes probabilistes, seront évoqués au fil du cours pour que les étudiants soient en mesure de comprendre des limites de ces méthodes.

Compétences

  • de trouver des compromis sur les qualités des solutions d’un problème en fonction du contexte pour mettre en oeuvre des algorithmes pratiques
  • de connaître les principales méthodes d’approximation,
  • d’utiliser le hasard dans des algorithmes pour qu’ils soient plus performants.


dernière modification : 09/11/2021 à 07:44:01