Université Lyon 1
Université de Lyon
Arqus
Accueil  >>  Master  >>  Informatique  >>  M2 Image, développement et technologie 3D  >>  Algorithmique pour l'optimisation
  • Domaine : Masters du domaine SCIENCES, TECHNOLOGIES, SANTE
  • Diplôme : Master
  • Mention : Informatique
  • Parcours : M2 Image, développement et technologie 3D
  • Unité d'enseignement : Algorithmique pour l'optimisation
Nombre de crédits de l'UE : 3
Code APOGEE : INF1203M
UE Libre pour ce parcours
UE valable pour le semestre 1 de ce parcours
    Responsabilité de l'UE :
PIERRON THEO
 theo.pierronuniv-lyon1.fr
 nicolas.bousquetuniv-lyon1.fr
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
Travaux Pratiques (TP)
0 h
Durée de projet en autonomie de l'étudiant (PRJ)
0 h
Durée du stage
0 h
Effectifs Cours magistraux (CM)
210 étudiants
Travaux dirigés (TD)
35 étudiants
Travaux pratiques (TP)
18 étudiants

* Ces horaires sont donnés à titre indicatif.

    Compétences attestées (transversales, spécifiques) :
Non rédigé
    Programme de l'UE / Thématiques abordées :
Le cours s’intéresse aux méthodes d'optimisation combinatoire, qui est la partie de la recherche opérationnelle qui traite des problèmes d'optimisation dans un domaine discret et en l'absence d'incertitude. Il s'agit alors de trouver une solution optimale parmi un nombre fini mais très grand de solutions, ce qui rend ces problèmes difficiles du point de vue de la complexité des calculs.

Nous abordons plusieurs techniques algorithmiques pour faire face à cette complexité de calcul: algorithmes probabilistes, algorithmes d'approximation, algorithmes exponentiels exacts (par la méthode du branching ou de la programmation dynamique), complexité paramétrée ainsi que programmation linéaire et en nombres entiers.

Nous donnons des exemples de mise en œuvre de ces techniques sur des problèmes classiques d'optimisation combinatoire qui servent à modéliser et résoudre de nombreux problèmes rencontrés en pratique: flot maximum, coupe minimum, stable maximum dans les graphes, voyageur de commerce, équilibrage de charges, sac à dos, sélection de k centres, couverture par les sommets des arêtes d'un graphe.
    Liste des autres Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 24/10/2022
SELECT * FROM parcours INNER JOIN ue_parcours ON PAR_ID_FK=PAR_ID INNER JOIN mention ON MEN_ID = PAR_MENTION_FK WHERE PAR_ACTIVATE = 0 AND UE_ID_FK='26118' ORDER BY UE_ID_FK ASC, PAR_ID_FK ASC