Public concerné et conditions d’accès
Avoir le niveau Bac+2 ( DPCT du Cnam, DUT, BTS) en informatique.
Finalités de l’unité d’enseignement
Objectifs pédagogiques :
Présenter des concepts, des méthodes et démarches indispensables pour de futurs ingénieurs chargés de conception et développement informatiques.
Capacité et compétences acquises :
Organisation
Description des heures d’enseignements
Cours : 60 heures
Modalités de validation :
Examen final
Contenu de la formation
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 -
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. Chemins (algorithmes de FORD, DIJKSTRA, FLOYD). Ordonnancements (méthodes PERT et MPM). Flot maximal. Flot maximal à coût minimal. Arbres optimauxClasses P, NP - Equivalence et réductions entre problèmes - Problèmes NP-complets, NP-difficiles - Théorème de COOK. 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.
Bibliographie
|
Auteur |
Titre |
|
Pr. R. FAURE |
Précis de recherche opérationnelle (Dunod). |
|
Groupe ROSEAUX |
Exercices et problèmes résolus de R.O., tomes 1 et 2 (Masson). |
Code :