Modélisation, optimisation, complexité et algorithmes (MOCA B1)

Contenu Graphes non valués
Concepts de base de la théorie des graphes.
Connexité, forte connexité, mise en ordre.
Fermeture transitive. Algorithme de Roy -Warshall                                                   Parcours des graphes ( en largeur, en profondeur) : applications notamment à la connexité et à la forte connexité (algorithme de TARJAN).

Optimisation dans les graphes valués
Chemins (algorithmes de Ford, Dijkstra,  Floyd).                                     Ordonnancements (méthodes PERT et MPM) et problèmes d'atelier
Flot maximal (Ford Fulkerson) Flot maximal à coût minimal (Busacker-Cowen)
Arbres optimaux (Krsukal, Prim)

Introduction à la complexité des algorithmes et notions de complexité des problèmes                                                                                                                       Classes P, NP - Équivalence et réductions entre problèmes - Problèmes NP-complets, NP-difficiles - Théorème de COOK.
Réseaux de Petri (RdP)
Caractéristiques des RdP - exemples de modélisation de systèmes à événements discrets.
Analyse qualitative - Graphe des marquages accessibles, arborescence de Karp et Miller. Équation d'état - Semi-flots (invariant de places) - propriétés comportementales (finitude , vivacité), analyse structurelle - Etude de cas 
Au second semestre, les UEs NFP 103, RCP 103, RCP 104 et RCP 106 font suite à cet enseignement
Modalités de l'évaluation Examen écrit . Le professeur, responsable national pour cette U.E., procède à la vérification et à la validation des sujets d'examen proposés par les CRA.
Bibliographie

• Groupe ROSEAUX : Exercices et problèmes résolus de R.O., tomes 1 et 2 (Masson).