- Unité d'enseignement : Algorithmique pour l'optimisation
Nombre de crédits de l'UE : 3
Code APOGEE : INF1203M
Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
15 h
* 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.
Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 24/10/2022
SELECT MEN_ID, `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`, `PAR_ID` 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 `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`
