RCP105 Modélisation, optimisation, complexité et algorithmes (MOCA B1) [T]

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

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

Nombre de crédits enseignements : 6 ECTS

Modalités de validation : Le responsable national relit et valide les sujets proposés par les CRA

Type de la formation : Cours

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.

Bibliographie