Portail nationalFormations hybrides

Optimisation Combinatoire Avancée

Code UE : US336B

  • Cours
  • 2 crédits

Responsable(s)

Safia KEDAD SIDHOUM

Public, conditions d’accès et prérequis

Notions de base en programmation linéaire et en graphes

Objectifs pédagogiques

Former les étudiants aux notions et outils fondamentaux de l'optimisation combinatoire théorique. Leur donner en particulier les connaissances élémentaires sur les fonctions sous-modulaires, qui jouent un rôle central en économie et en machine learning. Présenter quelques-uns des grands défis actuels de l'optimisation combinatoire (questions ouvertes, conjectures).

Compétences visées

  • Capacité à mettre en place des algorithmes avancés d'optimisation combinatoire
  • Capacité à identifier des structures exploitables dans des problèmes combinatoires
  • Compréhension de certains enjeux de l'optimisation combinatoire actuelle et de ses applications en économie et au machine learning.

Contenu

  • Matroïdes et fonctions sous-modulaires : définitions, premières propriétés, exemples
  • Optimiser avec les matroïdes : algorithme glouton
  • Minimiser une fonction sous-modulaire (algorithme de Schrijver)
  • Sous-modularité, convexité, concavité (extension de Lovász, difficulté de la maximisation)
  • Intersection de matroïdes (théorème d'Edmonds), polymatroïdes

Modalité d'évaluation

  • Examen final

Cette UE apparaît dans les diplômes et certificats suivants

Chargement du résultat...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Recherche opérationnelle
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Package
Lieu(x) Paris
Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

Recherche opérationnelle
2D4P20, 33-1-10, 2 rue Conté
75003 Paris
Tel :01 40 27 22 67
secretariat.ro@cnam.fr
Voir le site

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

Enseignement non encore programmé