0
01 44 78 60 50

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é.
Modélisation et analyse de systèmes dynamiques concurrents.

Méthodes de validation :

Le responsable national relit et valide les sujets proposés par les CRA

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é (algorithme de TARJAN).
Chemins (algorithmes de Ford, Dijkstra,  Floyd).
Ordonnancements (méthodes PERT et MPM et problèmes d'atelier)
Flot maximal (Ford Fulkerson) Flot à coût minimal (Busacker-Cowen)
Arbres optimaux (Kruskal, Prim)
Introduction à la complexité des algorithmes et des problèmes
Classes P, NP - Équivalence et réductions entre problèmes - Problèmes NP-complets, NP-difficiles - Théorème de COOK.

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é), propriétés spécifiques ( introduction  a la logique temporelle linéaire) -
Etude de cas 


Au second semestre, les UE NFP 103 (applications concurrentes), RCP 103 (evaluation de performances) font suite à cet enseignement.

Bibliographie :
  • Coordinators: HADDAD Serge, KORDON Fabrice, PETRUCCI Laure: Méthodes formelles pour les systèmes répartis et coopératifs Traité IC2, série Informatique et Systèmes d'Information
  • Douglas West: Introduction to Graph Theory

Cette UE apparaît dans les diplômes et certificats suivants :

Code UE RCP105
Crédits 6 ECTS
Volume horaire 45 Heures
Informations, Orientation & Inscription

Prochaines sessions de formation

Filtres :
Centre de formation Semestre
2022/2023 		Jours de
formation		 Modalité Tarif    
FOAD Ile-de-France Semestre 2   Pour une demande d'inscription,
contactez le centre

Date de début des cours (*) :

  • 27/02/2023

* Les dates fournies sont d'ordre général à toutes les formations.
  Les cours pour cette formation peuvent potentiellement commencer un peu plus tard dans le semestre.

Ajouter au panier
Contacter le centre
    • FOAD Ile-de-France
      Semestre 2
      Cours hors région  
Légende :
Date de début de cours :
  • Île-de-France :
    • 1er semestre et annuel : 26/09/2022
    • 2e semestre : 27/02/2023
  • Paris :
    • 1er semestre et annuel : 19/09/2022
    • 2e semestre : 06/02/2023

Les dates fournies sont d'ordre général à toutes les formations. Les cours pour cette formation peuvent potentiellement commencer un peu plus tard dans le semestre.

Tarif :

Seul le financement à titre individuel est proposé à l'inscription en ligne. Si vous souhaitez financer votre formation par votre entreprise, vous devez demander un devis auprès de nos centres Tarifs en vigueur depuis le 17 juin 2020.

Annuel :

Il s'étend de fin septembre / début octobre à début juillet (dates indicatives, renseignez-vous auprès de votre centre).

Semestre 1 :

Il s'étend de fin septembre / début octobre à fin janvier / début février (dates indicatives, renseignez-vous auprès de votre centre).

Semestre 2 :

Il s'étend de fin février / début mars à début juillet (dates indicatives, renseignez-vous auprès de votre centre).

Cours du soir :

Les cours commencent le plus souvent à 18h30 dans les centres.

  Cours en journée :

Se renseigner auprès du centre pour connaître les horaires.

Cours en ligne :

Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant. Des regroupements peuvent être proposés dont certains sont obligatoires.

  Classe virtuelle :

L'enseignant à distance intervient en direct et en visioconférence sur la plateforme d'e-learning. Il complète son intervention par des activités interactives (exercices échanges…)

  Cours en ligne hybride :

Cette modalité propose une majorité de cours en ligne tuteurés et des regroupements en présentiel obligatoires.

  Cours hybrides :

Cette modalité mixe des cours en présentiel (en cours du soir ou en journée) et des cours en ligne.

  Cours en ligne organisés par un autre
centre CNAM Régional :

Les cours sont diffusés sous forme de séances numériques via une plateforme d'e-learning animées et tutorées par un enseignant.

En savoir plus sur nos modalités
Recherche en cours