Modélisation, optimisation, complexité et algorithmes
Code UE : RCP105-MPY
- 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
-
Midi-Pyrénées
- 2026-2027 2nd semestre : Formation hybride soir ou samedi
Comment est organisée cette formation ?2026-2027 2nd semestre : Formation hybride soir ou samedi
Dates importantes
- Période des séances du 01/02/2027 au 30/07/2027
- Période d'inscription : du 01/05/2026 à 08:00 au 31/07/2027 à 08:00
- Période de 1ère session d'examen : 06/2027
- Période de 2ème session d'examen : 09/2027
Précision sur la modalité pédagogique
- Une formation hybride est une formation qui combine des enseignements en présentiel selon un planning défini et des enseignements à distance avec ou sans planning défini.
Code UE : RCP105-MPY
- Cours + travaux pratiques
- 6 crédits
- Volume horaire de référence
(+ ou - 10%) : 50 heures
Responsable(s)
Agnes PLATEAU ALFANDARI