Modélisation, optimisation, complexité et algorithmes
RCP105
Objectifs pédagogiques :
Présenter des concepts, des méthodes de base indispensables pour de futurs ingénieurs chargés de la conception et développement en informatique.
Public et conditions d'accès :
Avoir le niveau Bac+2 ( DPCT du Cnam, DUT, BTS) en informatique.
Compétences :
Modélisation et optimisation par les graphes
Assimilation de la notion de complexité des algorithmes.
Modélisation et analyse de systèmes dynamiques concurrents via les réseaux de Petri.
Méthodes de validation :
Le responsable national relit et valide les sujets proposés par les CCR
Contenu de la formation :
Algorithmes de Graphes
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) : applications notamment à la connexité et à la forte connexité.
Chemins (algorithmes de Ford, Dijkstra, Floyd).
Ordonnancements (méthodes MPM)
Flot maximal (Ford Fulkerson) Flot à coût minimal (Busacker-Cowen)
Arbres optimaux (Kruskal, Prim)
Introduction à la complexité des algorithmes
Réseaux de Petri (RdP)
Systèmes concurrents, formalisme des réseaux de Petri , exemples de modélisation de systèmes dynamiques à événements discrets.
Analyse comportementale : Graphe des marquages accessibles, arborescence de Karp et Miller.
Équation d'état - Semi-flots (invariant de places) analyse structurelle -
Propriétés génériques (finitude, sûreté, vivacité),
Au second semestre, les UE RCP106 et RCP104 font suite à cet enseignement.
Bibliographie :
- Coordinators: Robert Faure, Bernard Lemaire, Christophe Picouleau: Précis de recherche opérationnelle
- Douglas West: Introduction to Graph Theory
Cette UE apparaît dans les diplômes et certificats suivants :
- LP15701A : Licence professionnelle Métiers de l'informatique : conception, développement et test de logiciels parcours Chef de Projet Développement, Sécurité et Exploitation en HTT
- CRN0801A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Systèmes et réseaux
- CRN0802A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Systèmes d'information
- CYC9106A : Diplôme d'ingénieur Spécialité informatique parcours Cybersécurité
- CYC9102A : Diplôme d'ingénieur Spécialité informatique parcours Intelligence Artificielle et Optimisation
- CYC9105A : Diplôme d'ingénieur Spécialité informatique parcours Informatique systèmes d'information
- CYC9104A : Diplôme d'ingénieur Spécialité informatique parcours Informatique, réseaux, systèmes et multimédia
- CYC9101A : Diplôme d'ingénieur Spécialité informatique parcours Architecture et ingénierie des systèmes et des logiciels (AISL)
- LG02501A : Licence Sciences technologies santé mention informatique parcours Informatique générale
- CRN0803A : Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) parcours Cybersécurité
