Le cours est disponible dans la rubrique Telechargement
Visitez www.ece.fr/~ravaut

Les graphes modélisent de nombreuses situations concrètes où interviennent des objets en interaction.

- Les interconnexions routière, ferroviaire ou aériennes entre différentes agglomérations,

- Les liens entre les composants d'un circuit électronique,

- Le plan d'une ville et de ses rues en sens unique,

Les graphes permettent de manipuler plus facilement des objets et leurs relations avec une représentation graphique naturelle. L'ensemble des techniques et outils mathématiques mis au point en Théorie des Graphes permettent de démontrer facilement des propriétés, d'en déduire des méthodes de résolution, des algorithmes, ...

Quel est le plus court chemin (en distance ou en temps) pour se rendre d'une ville à une autre?

Comment minimiser la longueur totale des connexions d'un circuit?

Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville?

La recherche opérationnelle est une discipline dont le but est de fournir des méthodes pour répondre à un type précis de problème, c'est-à-dire à élaborer une démarche universelle pour un type de problème qui aboutit à la ou les solutions les plus efficaces. La particularité de la recherche opérationnelle est que les méthodes proposées sont des démarches rationnelles basées sur des concepts et outils mathématiques et/ou statistiques.

Généralement, ces méthodes sont employées sur des problèmes tels que leur utilisation "manuelle" devient impossible. C'est pourquoi, du fait qu'elles sont rationnelles, les démarches proposées par la recherche opérationnelle peuvent être traduites en programmes informatiques.

Cette traduction d'une démarche en un programme informatique n'est pas sans difficulté. Tout d'abord, le temps d'exécution du programme résultant et/ou la place occupée dans la mémoire de l'ordinateur peuvent ne pas être acceptables. Ainsi, une méthode en recherche opérationnelle sera jugée sur ces critères de temps et de place. Plus une méthode sera rapide et peu gourmande en mémoire, plus elle sera considérée bonne.

Les ordinateurs ont une structure particulière qui fait que toutes les propriétés des mathématiques traditionnelles ne sont pas toujours respectées. Ainsi, une démarche prouvée fonctionner admirablement en théorie peut s'avérer être complètement inexploitable en pratique. Notamment, les nombres réels dans un ordinateur ne peuvent pas être représentés de manière exacte, ils sont arrondis. On voit donc facilement qu'une répétition excessive d'arrondis dans un calcul peut entraîner des erreurs importantes dans les résultats finaux. Les méthodes employées en recherche opérationnelle doivent prendre en compte ce genre de problème.

Voici les points abordés :

1. Graphes : définitions et modélisation

2. Connexité d'un graphe

3. Recherche du plus court chemin

- Principe de sous-optimalité

- Algorithme de recherche

- Algorithme de recherche en largeur (BFS)

- Algorithme de Dijkstra

4. Les arbres

5. Ordonnancement

6. Recherche du flot maximum