• Votre sélection est vide.

    Enregistrez les diplômes, parcours ou enseignements de votre choix.

Algorithmique de graphes

  • Composante

    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


Lire plus

Pré-requis obligatoires

Modules [[m:IF101]] et [[m:IF102]]

Lire plus

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

Lire plus

Bibliographie

Des notes de cours imprimés et en ligne.
Introduction à l'algorithmique, T. Cormen et al., Dunod~(1994).

Lire plus

Modalités de contrôle des connaissances

Évaluation initiale / Session principale - Épreuves

Type d'évaluationNature de l'épreuveDurée (en minutes)Nombre d'épreuvesCoefficient de l'épreuveNote éliminatoire de l'épreuveRemarques
Contrôle Continu IntégralContrôle Continu1