Intégrer La Prépa des INP
Intégrer une école
S'inscrire
Livret d'accueil
École / Prépa
ENSEIRB-MATMECA
Code interne
EI6IF106
Description
Après une brève introduction des graphes, ce cours présente des problèmes sur les graphes admettant une solution algorithmique efficace. L'étude de ces solutions sera l'occasion d'exhiber des propriétés classiques en Théorie des Graphes.
Introduction
Exemples de problèmes
Définitions générales
Chemins et arbres
Problèmes de parcours
Une solution gloutonne pour l'arbre couvrant minimal
Parcours en largeur
Le problème du plus court chemin
Parcours en profondeur
Autres problèmes
Le problème du flot maximal
Le problème du couplage maximum
Heures d'enseignement
- CICours Intégré40h
- TITravaux Individuels21h
Pré-requis obligatoires
Modules [[m:IF101]] et [[m:IF102]]
Syllabus
I. Introduction - Exemples de problèmes - Définitions générales - Chemins et arbres II. Problèmes de parcours - Une solution gloutonne pour l'arbre couvrant minimal - Parcours en largeur - Le problème du plus court chemin - Parcours en profondeur III. Autres problèmes - Le problème du flot maximal - Le problème du couplage maximum
Bibliographie
Des notes de cours imprimés et en ligne.
Introduction à l'algorithmique, T. Cormen et al., Dunod~(1994).
Modalités de contrôle des connaissances
Évaluation initiale / Session principale - Épreuves
| Type d'évaluation | Nature de l'épreuve | Durée (en minutes) | Nombre d'épreuves | Coefficient de l'épreuve | Note éliminatoire de l'épreuve | Remarques |
|---|---|---|---|---|---|---|
| Contrôle Continu Intégral | Contrôle Continu | 1 |