INF 444 A : Recherche opérationnelle et graphes


Retour
Imprimer la fiche programme
Code analytique: EDOINFMA2
Responsable  :    
Programmé en UV2 MAJ INF

Présentation :

La recherche opérationnelle vise essentiellement à élaborer des
outils d'aide à la décision. L'optimisation, au sein d'un univers
fini, en est sans conteste un parangon. La théorie des graphes --
dans ce contexte -- fournit une panoplie remarquablement efficace de
modèles et d'algorithmes permettant de résoudre des problèmes que
posent, inévitablement, une carrière d'ingénieur dés lors qu'elle
n'est pas seulement dévolue au commerce (et encore...).

Objectifs (obsolète):

Ce module a pour ambition d'éclairer la recherche opérationnelle à l'aide de la
théorie des graphes et de traiter trois problèmes fondamentaux :
- la conception de rÈseaux,
- le transport de l'information sur des rÈseaux,
- l'affectation de ressources.

Pré-requis :

aucun

Liens :

réseaux, algorithmique.

Volume horaire : 18h


Contenu détaillé :

Cours 1 : (3h) De la recherche opérationnelle aux graphes
Définitions générales et applications de la théorie des graphes à la
recherche opérationnelle.

Cours 2 : (3h) Arbres
Ce cours traitera des arbres de la théorie des graphes. On verra en
particulier leur utilité pour la construction de réseaux. Les points
abordés seront :
- définition et propriétés des arbres,
- théorème de Cayley,
- arbres couvrants minimaux d'un graphe,
- algorithme de Kruskal.

Travaux Dirigés 1 : (3h) Arbres couvrants
On abordera dans ce TD deux algorithmes de recherche d'arbre
couvrant, l'un pour les graphes non orienté (algorithme de Prim),
l'autre pour les graphes orientés (algorithme de Dijkstra).

Nous aborderons aussi les problËmes de parcours dans un graphe.

Travaux Dirigés 2 : (3h) Programmation dynamique
La programmation dynamique sera abordée par le biais de l'algorithme
de Bellmann pour la recherche d'un arbre couvrant d'un graphe orienté.

Nous l'utiliserons ensuite pour l'alignement de deux séquences
(distance d'édition).

Cours 3 : (3h) Réseaux de transports
Problèmes de maximisation de flots dans un réseau de transport. On
verra le lien entre ce problème et la programmation linéaire.

Travaux Dirigés 3 : (1h30) flots
Algorithme de Ford et Fulkerson.

Cours 4 : (1h30) programmation linéaire
Introduction et définition, idée de l'algorithme du simplexe et lien
avec l'algorithme de Ford et Fulkerson (dualité entre maximisation du
flot et programmation linéaire).

Travaux personnels encadrés :

aucun


Année 2006/2007
Dernière mise à jour le 12-JUL-06
Validation par le responsable de programme le


IMT Atlantique
Campus de Brest
Technopôle Brest-Iroise
CS 83818
29238 Brest Cedex 3
France

Tél  +33 (0)2 29 00 11 11
Fax +33 (0)2 29 00 10 00