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)
Exemples et applications.
Optimisation dans les graphes valués
Chemins (algorithmes de FORD, DIJKSTRA, FLOYD).
Ordonnancements (méthodes PERT et MPM).
Flot maximal. Flot maximal à coût minimal.
Arbres optimaux
Notions de complexité des algorithmes et des problèmes
Classes P, NP - Equivalence et réductions entre problèmes - Problèmes NP-complets, NP-difficiles - Théorème de COOK.
Réseaux de Petri (RdP)
Définitions, exemples de modé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 - Comportement d'un RdP (bornage, vivacité), analyse structurelle - Modélisation et validation de systèmes informatiques distribués -
Secrétariat : Mme Martella accès Algéco bureau 11 Tel 01 40 27 22 67
email : martella@Cnam. fr
Cet enseignement est également assuré en journée (ICPJ).
Au second semestre le cours MOCA B2 fait suite à cet enseignement. |
