|
|
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 |
| 6 Cré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.
|
|
|
|
