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

Unité d'enseignement du Cnam

Prérequi200s

Avoir le niveau Bac+2 ( DPCT du Cnam, DUT, BTS) en informatique.

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 et sa complexité.
Parcours des graphes ( en largeur, en profondeur)
- Exemples et 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).
Flot maximal. Flot maximal à coût minimal.
Arbres optimaux
Complexité des algorithmes et notions de complexité 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 à événements discrets, systèmes concurrents, propriétés comportementales
équation d'état - Graphe des marquages accessibles, arborescence de KARP et MILLER. EQUATION FONDAMENTALE et Semi-flots (invariant de places) - Comportement d'un RdP (bornage, vivacité), analyse structurelle - ETUDE DE CAS : Modélisation et validation de systèmes informatiques distribués -
Cet enseignement est également assuré en journée (ICPJ).
Au second semestre le cours MOCA B2 fait suite à cet enseignement.

Projet ou mémoire

Cette UE comporte 30h de cours et 30h de travaux dirigés.Les travaux dirigés , indissociables du cours, doivent être précédés par un travail personnel.

Fiche mise à jour le 11/07/2011

- Les inscriptions sont permanentes
- Début de la formation : A compter de l'inscription
- Durée de la formation : 6 mois

Objectifs

Conservatoire national des Arts et Métiers

La fiche détaillée du partenaire

http://formation.cnam.fr/zaffiche_ue_externe.php?code_formation=RCP105

CONSERVATOIRE NATIONAL DES ARTS ET METIERS ACADEMIE * CNAM

Centre régional du Cnam - La Réunion Adresse CRA du Cnam de la Réunion 18 rue Claude Chappe ZAC 2000 BP 274 97827 Le Port Cedex Voir le site tél : 02.62.42.28.37 Contact(s) CENTRE RÉGIONAL DU CNAM - LA RÉUNION