RCP105 - Modélisation, optimisation, complexité et algorithmes (MOCA B1) [ 6 crédits ]

Public Concerné

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

Finalité 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

Modélisation et optimisation par les graphes
Assimilation de la notion de complexité.
Modélisation du parallélisme et de la synchronisation à l'aide des réseaux de Pétri , validation d'un système.

Organisation

6Crédits

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.

Accès à PLEIAD

ACTUS-PRESSE

CNAM et entreprises

Préinscription en ligne

Documents à télécharger

l’alternance en vidéos