Université Lyon 1
Arqus
Accueil  >>  Master  >>  Bio-informatique  >>  M2 Bio-informatique moléculaire: méthodes et analyses  >>  Graphes, Complexité, Combinatoire
  • Domaine : Masters du domaine SCIENCES ET TECHNOLOGIES
  • Diplôme : Master
  • Mention : Bio-informatique
  • Parcours : M2 Bio-informatique moléculaire: méthodes et analyses
  • Unité d'enseignement : Graphes, Complexité, Combinatoire
Nombre de crédits de l'UE : 3
Code APOGEE : INF2352M
UE Libre pour ce parcours
UE valable pour le semestre 1 de ce parcours
    Responsabilité de l'UE :
KHEDDOUCI HAMAMACHE
 hamamache.kheddouciuniv-lyon1.fr
04.72.69.21.74
NDIAYE SAMBA NDOJH
 samba-ndojh.ndiayeuniv-lyon1.fr
    Type d'enseignement
Nb heures *
Cours Magistraux (CM)
15 h
Travaux Dirigés (TD)
3 h
Travaux Pratiques (TP)
12 h
Durée de projet en autonomie (PRJ)
0 h
Durée du stage
0 h
Effectif Cours magistraux (CM)
210 étudiants
Effectif Travaux dirigés (TD)
35 étudiants
Effectif 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 :
Dans cette UE, nous nous attaquerons à l’étude des problèmes difficiles d’optimisation dont la résolution se heurte à une explosion du nombre de combinaisons à explorer. Plusieurs types de problèmes seront passés en revue tels que les problèmes de satisfaction de contraintes (SAT et CSP), ainsi que des problèmes d’optimisation sur des graphes (colorations, dominations, stabilité, recherche de sous-graphes, etc). Une partie du cours sera également consacrée à l’étude de la complexité et la classification de ces problèmes en classes NP-Complet, NP-difficile, etc. De même, nous verrons les différentes approches de résolution de ces problèmes proposées dans la littérature.
    Liste des autres Parcours / Spécialité / Filière / Option utilisant cette UE :
Date de la dernière mise-à-jour : 17/04/2018
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='16818' ORDER BY `MEN_DIP_ABREVIATION`, `MEN_TITLE`, `PAR_TITLE`