Refreshers Courses (MAN)

dernière modif : le 15/07/2021 à 22:35:30
Titre : Refreshers Courses (MAN)
Section : MISE_A_NIVEAU
Ects : 0
Responsable : Amélie Lambert (CNAM/CEDRIC)
Intervenants :
Agnès Plateau-Alfandari (CNAM/CEDRIC/OC)
José Néto (Telecom SudParis / SAMOVAR)
Objectif : Etre capable de suivre les cours du master RO
Prérequis : aucun
Saisons d'ouvertures : 2021-2022; 2020-2021;
Modalités de contrôle :
Contenu :

Complexité des algorithmes (lundi matin) :

  • Définition d'un algorithme, évaluation des algorithmes, complexité des algorithmes.

Probabilités et chaînes de Markov (lundi et mardi après-midi)

  • Séance 1 : Probabilité d’une expérience aléatoire, dénombrement, variables aléatoires.
  • Séance 2 : Processus aléatoires (markoviens, stationnaires, poisson, naissance, naissance et mort), les chaînes de Markov (Définition, matrice associée à une chaîne de Markov, matrice stochastique, graphe associé à une chaîne de Markov, distribution limite dans une chaîne de Markov).

Graphes (mardi matin et mercredi matin et après-midi)

  • Séance 1 : (Notions de base – Arbres)
    Graphes orienté et non orienté, représentations matricielles, sous-graphe, graphe partiel, graphe complet, clique, stable.
  • Séance 2 : (Problèmes de plus courts chemins)
    Algorithmes de plus courts chemins: Moore- Dijkstra, Bellman-Ford et Bellman.
  • Séance 3 : (Flots dans les réseaux)
    Problème de transport, propriétés des coupes dans un graphe, graphe d'écart, algorithme de Ford & Fulkerson, extensions.

Programmation linéaire (jeudi matin et après-midi)

  • Séance 1 : rappels sur la forme générale d'un PL, les égalités linéaires, convexité et solutions de base, caractérisation des bases et solutions de base optimales, changement de bases, algorithme du simplexe.
  • Séance 2 : problèmes soulevés par la dégénérescence, initialisation de l'algorithme du simplexe (résolution en 2 phases avec la méthode des variables artificielles), notion de dualité.

Méthode de séparation et d'évaluation (Branch and Bound)

et programmation dynamique (vendredi matin)

  • Séance 1 : Procédures Branch & Bound : généralités et définitions, concepts de séparation et d’ évaluation, algorithme de séparation et évaluation, illustration sur le problème du sac à dos.
  • Séance 2 : Programmation dynamique déterministe illustrée sur le problème du sac à dos.

Modèles stochastiques (vendredi après-midi)

  • Partie 1 : Espérance conditionnelle d’un couple de variables aléatoires (espace de probabilités, variables aléatoires, couple de variables aléatoires – cas discret.
  • Partie 2 : Optimisation continue : optimisation sans contraintes, optimisation sous contraintes d’égalité et d’inégalité, conditions d’optimialité.
Bibliographie :