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)

Kamel BARKAOUI

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 :

Fiche synthétique au format PDF

Présence et réussite aux examens

Pour l'année universitaire 2020-2021 :

Nombre d'inscrits : 209
Taux de présence à l'évaluation : 83%
Taux de réussite à l'évaluation : 82%

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

Mots-clés

Informatique - Réseaux informatiques

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é (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.

Modalité d'évaluation

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

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

Chargement du résultat...

Intitulé de la formation	Type	Modalité(s)	Lieu(x)
Intitulé de la formation Licence informatique	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x) À la carte	Lieu(x) Auvergne - Rhône-Alpes, Bourgogne - Franche-Comté, Bretagne, Centre - Val de Loire, Grand-Est, Ile-de-France (sans Paris), Liban, Midi-Pyrénées, Nouvelle-Aquitaine, Occitanie, Paris, Pays de la Loire, Provence-Alpes-Côte d'Azur	Entrée Niveau 4 (Bac)
Intitulé de la formation Licence informatique	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x) Alternance	Lieu(x) Auvergne - Rhône-Alpes, Bourgogne - Franche-Comté, Centre - Val de Loire, Hauts-de-France, Ile-de-France (sans Paris), Martinique, Midi-Pyrénées, Normandie, Nouvelle-Aquitaine, Occitanie, Pays de la Loire, Provence-Alpes-Côte d'Azur	Entrée Niveau 4 (Bac)
Intitulé de la formation Master Réseaux et Objets Connectés	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x) À la carte	Lieu(x) Paris, Pays de la Loire	Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Licence (L3) générale Informatique en alternance	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x) Alternance	Lieu(x) CFA Ile-de-France, Grand-Est, Liban	Entrée Niveau 4 (Bac)
Intitulé de la formation 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	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x)	Lieu(x)	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Master Sécurité informatique, cybersécurité et cybermenaces	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x)	Lieu(x)	Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Ingénieur en informatique. Architecture et intégration des systèmes et des logiciels	Type Diplôme d'ingénieur	Lieu(x) Alternance	Lieu(x) Midi-Pyrénées	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Ingénieur en informatique. Architecture et intégration des systèmes et des logiciels	Type Diplôme d'ingénieur	Lieu(x) À la carte	Lieu(x) Bretagne, Grand-Est, Liban, Midi-Pyrénées, Nouvelle-Aquitaine, Paris, Pays de la Loire	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Informatique modélisation optimisation	Type Diplôme d'ingénieur	Lieu(x) Alternance	Lieu(x) Midi-Pyrénées	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Informatique modélisation optimisation	Type Diplôme d'ingénieur	Lieu(x) Package	Lieu(x) Grand-Est	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Informatique modélisation optimisation	Type Diplôme d'ingénieur	Lieu(x) À la carte	Lieu(x) Centre - Val de Loire, Paris, Pays de la Loire	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Informatique, réseaux, systèmes et multimédia	Type Diplôme d'ingénieur	Lieu(x) À la carte	Lieu(x) Bretagne, Centre - Val de Loire, Grand-Est, Ile-de-France (sans Paris), Liban, Midi-Pyrénées, Nouvelle-Aquitaine, Occitanie, Paris, Pays de la Loire, Provence-Alpes-Côte d'Azur	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Ingénieur informatique - systèmes d'information et business intelligence	Type Diplôme d'ingénieur	Lieu(x) Package	Lieu(x) Hauts-de-France	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Ingénieur informatique - systèmes d'information et business intelligence	Type Diplôme d'ingénieur	Lieu(x) À la carte	Lieu(x) Centre - Val de Loire, Grand-Est, Ile-de-France (sans Paris), Midi-Pyrénées, Nouvelle-Aquitaine, Occitanie, Paris, Pays de la Loire, Provence-Alpes-Côte d'Azur	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Diplôme d'ingénieur Spécialité informatique Parcours Cybersécurité	Type Diplôme d'ingénieur	Lieu(x) Alternance	Lieu(x) Occitanie	Entrée Niveau 5 (Bac+2)
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) Bretagne, Grand-Est, Midi-Pyrénées, Nouvelle-Aquitaine, Paris, Pays de la Loire, Provence-Alpes-Côte d'Azur	Entrée Niveau 5 (Bac+2)
Intitulé de la formation Master Sciences, technologies, santé mention Informatique Parcours Traitement de l'information et exploitation des données	Type Diplôme national (DEUST, licence, master, doctorat, diplôme d'Etat)	Lieu(x) À la carte	Lieu(x) Paris	Entrée Niveau 6 (Bac+3 et 4)
Intitulé de la formation Architecte infrastructure Réseaux et Systèmes	Type Diplôme d'établissement	Lieu(x) À la carte	Lieu(x) Ile-de-France (sans Paris), Pays de la Loire	Entrée Sans niveau spécifique
Intitulé de la formation Chef de projet maîtrise d’œuvre informatique	Type Diplôme d'établissement	Lieu(x) À la carte	Lieu(x) Pays de la Loire	Entrée Sans niveau spécifique
Intitulé de la formation Architecte en cybersécurité	Type Diplôme d'établissement	Lieu(x) À la carte	Lieu(x) Pays de la Loire	Entrée Sans niveau spécifique
Intitulé de la formation	Type	Modalité(s)	Lieu(x)

Contact

EPN05 - Informatique
2 rue Conté
75003 Paris
Tel :01 40 27 22 58
Swathi Rajaselvam

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
  - Centre Cnam Paris
    - 2022-2023 1er semestre : FOAD 100%
    Comment est organisée cette formation ?
    Organisation de la modalité FOAD 100%
    Planning
    1er semestre
    Date de démarrage : 19/09/2022
    Date limite d'inscription : 02/11/2022
    Date de 1ère session d'examen : 23/01/2023
    Date de 2ème session d'examen : 24/04/2023
    Précision sur la modalité pédagogique
    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
    Ressources mises à disposition sur l'Espace Numérique de Formation
    :
- Grand Est
  - Grand Est
    Comment est organisée cette formation ?
    Organisation de la modalité FOAD 100%
    Planning
    1er semestre
    Date de démarrage : 13/10/2022
    Date limite d'inscription : 01/09/2023
    Date de 1ère session d'examen : 13/02/2023
    Date de 2ème session d'examen : 04/09/2023
    2ème semestre
    Date de démarrage : 02/03/2023
    Date limite d'inscription : 01/06/2023
    Date de 1ère session d'examen : 05/06/2023
    Date de 2ème session d'examen : 04/09/2023
    Précision sur la modalité pédagogique
    Regroupements physiques facultatifs : Aucun
    Organisation du déploiement de l'unité
    Nombre d'élèves maximum à distance par classe : 35
    Nombre d'heures d'enseignement par élève : 25
    Délai maximum de réponse à une solicitation : sous 96 heures (Jours ouvrés)
    Modes d'animation de la formation
    Forum
    Messagerie intégrée à la plateforme
    Visioconférence
    Outils numériques de travail collaboratif
    Organisation d'une séance de démarrage
    Evaluation de la satisfaction
    Hot line technique
    Ressources mises à disposition sur l'Espace Numérique de Formation
    Documents de cours
    Enregistrement de cours
    Documents d'exercices, études de cas ou autres activités pédagogiques
    Bibliographie et Webographie
    Modalité de contrôle de l'acquisition des compétences et des connaissances (validation de l'UE)
    Examens présentiels dans un centre habilité
    :
- Languedoc-Roussillon
  - Languedoc-Roussillon
    - Année 2022 / 2023 : Présentiel jour
- Midi-Pyrénées
  - Toulouse
    - 2022-2023 2nd semestre : Présentiel soir ou samedi

Modélisation, optimisation, complexité et algorithmes

Code UE : RCP105

Responsable(s)

Public, conditions d’accès et prérequis

L'avis des auditeurs

Présence et réussite aux examens

Objectifs pédagogiques

Compétences visées

Mots-clés

Contenu

Modalité d'évaluation

Bibliographie

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

Rechercher une formation

Type(s) de formation

Type(s) de diplôme

Niveau d'entrée

Contact

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

Organisation de la modalité FOAD 100%

Planning

1er semestre

Précision sur la modalité pédagogique

Organisation du déploiement de l'unité

Modes d'animation de la formation

Ressources mises à disposition sur l'Espace Numérique de Formation

Organisation de la modalité FOAD 100%

Planning

1er semestre

2ème semestre

Précision sur la modalité pédagogique

Organisation du déploiement de l'unité

Modes d'animation de la formation

Ressources mises à disposition sur l'Espace Numérique de Formation

Modalité de contrôle de l'acquisition des compétences et des connaissances (validation de l'UE)

Code UE : RCP105

Responsable(s)

Dans la même rubrique