Formations

Modélisation, optimisation, complexité et algorithmes

Code UE : RCP105

  • Cours + travaux pratiques
  • 6 crédits
  • Volume horaire de référence
    (+ ou - 10%) : 50 heures

Responsable(s)

Agnes PLATEAU ALFANDARI

École du numérique et de l'IA

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.

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.

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...
Patientez
Intitulé de la formation
Type
Modalité(s)
Lieu(x)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Cybersécurité
Type Diplôme d'ingénieur
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Centre - Val de Loire, Grand-Est, Madagascar, Nouvelle-Aquitaine, Occitanie, Paris, Pays de la Loire
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) Parcours Cybersécurité
Type RNCP - Titre à finalité professionnelle
Lieu(x) Alternance
Lieu(x) Martinique
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Titre RNCP Niveau 6 Concepteur intégrateur d'infrastructures informatiques (systèmes et réseaux, applicatives, ou de sécurité) Parcours Cybersécurité
Type RNCP - Titre à finalité professionnelle
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Madagascar, Occitanie, Paris
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Intelligence Artificielle et Optimisation
Type Diplôme d'ingénieur
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Madagascar, Occitanie
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Architecture et ingénierie des systèmes et logiciels (AISL) (AISL)
Type Diplôme d'ingénieur
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Grand-Est, Liban, Madagascar, Nouvelle-Aquitaine, Occitanie
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Informatique, réseaux et systèmes mobiles
Type Diplôme d'ingénieur
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Grand-Est, Ile-de-France (sans Paris), Liban, Madagascar, Nouvelle-Aquitaine, Occitanie
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Systèmes d'information et business Intelligence
Type Diplôme d'ingénieur
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Centre - Val de Loire, Grand-Est, Ile-de-France (sans Paris), Madagascar, Nouvelle-Aquitaine, Occitanie
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Expérience interactive (EI)
Type Diplôme d'ingénieur
Lieu(x)
Lieu(x)
Entrée Niveau 5 (Bac+2)
Intitulé de la formation 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
Type RNCP - Titre à finalité professionnelle
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Grand-Est, Madagascar, Paris
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Licence informatique Parcours Informatique générale
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Centre - Val de Loire, Grand-Est, Ile-de-France (sans Paris), Madagascar, Nouvelle-Aquitaine, Occitanie, Paris, Pays de la Loire
Entrée Niveau 4 (Bac)
Intitulé de la formation Licence informatique Parcours Informatique générale
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) Alternance
Lieu(x) Auvergne - Rhône-Alpes, Grand-Est, Hauts-de-France, Ile-de-France (sans Paris), Normandie, Nouvelle-Aquitaine
Entrée Niveau 4 (Bac)
Intitulé de la formation Licence professionnelleloitation en HTT
Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)
Lieu(x) À la carte
Lieu(x) Madagascar
Entrée Niveau 4 (Bac)
Intitulé de la formation 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
Type RNCP - Titre à finalité professionnelle
Lieu(x) À la carte
Lieu(x) Auvergne - Rhône-Alpes, Bretagne, Grand-Est, Paris
Entrée Niveau 5 (Bac+2)
Intitulé de la formation Type Modalité(s) Lieu(x)

Contact

EPN05- Informatique
2 rue Conté 33.1.14A
75003 Paris
Sanaz MANSOURI

Voir le calendrier, le tarif, les conditions d'accessibilité et les modalités d'inscription dans le(s) centre(s) d'enseignement qui propose(nt) cette formation.

UE

    • Paris
      • 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
    • Grand Est
      • Grand Est
        • 2026-2027 1er semestre : Formation ouverte et à distance (FOAD)
        • 2026-2027 2nd 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 19/10/2026 au 10/09/2027
        • Période d'inscription : du 01/07/2026 à 00:00 au 31/08/2027 à 00:00
        • Date de 1ère session d'examen : 12/02/2027
        • Date de 2ème session d'examen : 10/09/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é

        • Nombre d'heures d'enseignement par élève : 15
        • 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
        2026-2027 2nd semestre : Formation ouverte et à distance

        Dates importantes

        • Période des séances du 15/02/2027 au 09/09/2027
        • Période d'inscription : du 01/07/2026 à 00:00 au 31/08/2027 à 00:00
        • Date de 1ère session d'examen : 16/06/2027
        • Date de 2ème session d'examen : 09/09/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é

        • Nombre d'heures d'enseignement par élève : 15
        • 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
    • Midi-Pyrénées
      • 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.