Contactez-nous

Mise à niveau

Mis à jour le

Responsable(s) : Mme Safia KEDAD SIDHOUM

  • Cours
Code Cnam : US331N

Envie d'en savoir plus sur cette formation ?

Afin d’obtenir les tarifs, le calendrier de la formation, en distanciel, en présentiel, le lieu de la formation et un contact, remplissez les critères suivants :

Afficher le centre adapté à mes besoins

Afin d’obtenir les tarifs, le calendrier de la formation et le lieu de la formation, remplissez les critères suivants :

Présentation

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

Prérequis

Aucun

Objectifs

Etre capable de suivre les cours du master MPRO (M2)

Compétences et débouchés

Parcours

Informations pratiques

Contact

Programme

Contenu

Complexité des algorithmes :

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

Probabilités et chaînes de Markov

  • 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

  • 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

  • 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 et programmation dynamique

  • 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

  • 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é.