Modélisation, Optimisation, Complexité et Algorithmes (Moca B1)

Graphes non valués
Concepts de base de la théorie des graphes
. Connexité,forte connexité, mise en ordre
. Fermeture transitive
. Algorithme deROY-WARSHALL
. Parcours des graphes ( en largeur, en profondeur)

Exemples et applications
. Optimisation dans les graphes valués

Chemins (algorithmesde FORD, DIJKSTRA, FLOYD)
. Ordonnancements (méthodes PERT et MPM)
. Flotmaximal
. Flot maximal à coût minimal
. Arbres optimaux Notions decomplexité des algorithmes et des problèmes

Classes P, NP
- Equivalence etréductions entre problèmes
- Problèmes NP-complets, NP-difficiles
- Théorème de COOK
. Réseaux de Petri (RdP)

Définitions, exemples demodélisation de systèmes à evenements discrets, systèmes concurrents,propriétés comportementales équation d'état
- Graphe des marquages accessibles, arborescence de KARP et MILLER
. Semi-flots
- Comportementd'un RdP (bornage, vivacité), analyse structurelle
- Modélisation etvalidation de systèmes informatiques distribués
- Cet enseignement est également assuré en journée (ICPJ). Au secondsemestre le cours MOCA B2 fait suite à cet enseignement.