Modélisation, optimisation, complexité et algorithmes
Code UE : RCP105-PAR
- Cours + travaux pratiques
- 6 crédits
- Volume horaire de référence
(+ ou - 10%) : 50 heures
Responsable(s)
Agnes PLATEAU ALFANDARI
Public, conditions d’accès et prérequis
Avoir le niveau Bac+2 ( DPCT du Cnam, DUT, BTS) en informatique.
L'avis des auditeurs
Les dernières réponses à l'enquête d'appréciation pour cet enseignement :
Présence et réussite aux examens
Pour l'année universitaire 2023-2024 :
- Nombre d'inscrits : 180
- Taux de présence à l'évaluation : 74%
- Taux de réussite parmi les présents : 87%
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.
Compétences visées
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.
Assimilation de la notion de complexité des algorithmes.
Modélisation et analyse de systèmes dynamiques concurrents via les réseaux de Petri.
Mots-clés
Contenu
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.
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.
Modalité d'évaluation
Le responsable national relit et valide les sujets proposés par les CCR
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
Chargement du résultat...
Contact
Centre(s) d'enseignement proposant cette formation
-
Paris
- 2026-2027 1er semestre : Formation ouverte et à distance (FOAD)
- 2027-2028 1er semestre : Formation ouverte et à distance (FOAD)
Comment est organisée cette formation ?2026-2027 1er semestre : Formation ouverte et à distance
Dates importantes
- Période des séances du 14/09/2026 au 16/01/2027
- Période d'inscription : du 01/06/2026 à 10:00 au 16/10/2026 à 17:30
- Période de 1ère session d'examen : 01/2027
- Période de 2ème session d'examen : 04/2027
Précision sur la modalité pédagogique
- Une formation ouverte et à distance (FOAD) est une formation dispensée 100% à distance, qui peut être suivie librement, à son rythme.
- Regroupements physiques facultatifs : Aucun
Organisation du déploiement de l'unité
- Délai maximum de réponse à une solicitation : sous 96 heures (Jours ouvrés)
Modes d'animation de la formation
- Organisation d'une séance de démarrage
- Evaluation de la satisfaction
- Hot line technique
Code UE : RCP105-PAR
- Cours + travaux pratiques
- 6 crédits
- Volume horaire de référence
(+ ou - 10%) : 50 heures
Responsable(s)
Agnes PLATEAU ALFANDARI