 |  |  |  |  |
| | |
||||
| MATH0249-1 | Théorie des graphes
[ english version ]
| |||||
| ||||||
| Durée : | 30h Th, 30h Pr | |||||
| ||||||
| Crédits/ECTS : |
| |||||
| ||||||
| Titulaire(s) : | Michel Rigo | |||||
| ||||||
| ||||||
| Aperçu général : | La théorie des graphes est une branche des mathématiques discrètes. Elle permet la formalisation de divers problèmes et structures et trouve en particulier de nombreuses applications en recherche opérationnelle (problèmes de transport, de tournées,...), en informatique (réseau, routage, télécommunications,...), en combinatoire, en théorie des groupes, en théorie des langages formels, ... Dans ce cours, on s'attachera à présenter quelques notions fondamentales de la théorie des graphes d'un point de vue théorique. Néanmoins, on mettra aussi en lumière certaines considérations algorithmiques. | |||||
| ||||||
| Objectif du cours : | Après avoir présenter les différentes classes de graphes (orientés ou non, multi-graphes, graphes pondérés), le cours aborde plusieurs thèmes classiques dont :
| |||||
| ||||||
| Pré-requis : | Notions de base en algèbre linéaire. Connaissance d'un langage de programmation impératif. | |||||
| ||||||
| Organisation : | Le cours est consacré principalement aux aspects théoriques des graphes. Les séances de répétition permettent de présenter la résolution d'exercices mais aussi l'illustration et la concrétisation des concepts et des algorithmes vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. | |||||
| ||||||
| Notes de cours : | Des notes de cours seront distribuées aux étudiants lors du premier cours. | |||||
| ||||||
| Evaluation : | L'examen en session comporte une partie orale et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. Il est à noter qu'un travail réalisé durant l'année académique et consistant en l'implementation de divers algorithmes de graphes pourra également intervenir dans la cote finale de l'examen. Un tel travail inclut la réalisation d'un rapport écrit ainsi que sa présentation orale. Les modalités d'un tel travail seront précisées en cours d'année par un affichage aux valves. | |||||
| ||||||
| Contacts : | M. Rigo Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be | |||||
| ||||||
| Remarques : | Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ | |||||
| ||||||
ULg : Administration de l'Enseignement et des Etudiants - Affaires Académiques
Responsable de l'information : Monique Marcourt, direction A.E.E.
Date de validité des données : 27/02/2006
Réalisation SEGI