Cours 2019-2020

Théorie des graphes [SMATB254]

  • 3 crédits
  • 30h+22.5h
  • 1er quadrimestre
Langue d'enseignement: Français

Acquis d'apprentissage

Développer l'aptitude mathématique dans le cadre de l'algorithmique liée à la théorie des graphes et dans la modélisation du comportement dynamique de systèmes discrets. Ce cours introduit à l'analyse de la complexité théorique des algorithmes . L'intérêt du cours réside dans l'énorme potentiel de modélisation constitué par les graphes.

Contenu

Graphes connexes, eulériens et bipartis Plus court chemin Arbres et connectivite Graphes hamiltoniens Mariages, couplages et couvertures Coloriages d'arêtes Cliques, ensembles indépendants et l'impossible désordre Coloriages de sommets Graphes planaires Flots et coupes P, N P et N P-complétude Grands et très grands graphes

Disciplines

Théorie des graphes
Mathématiques
Théorie de l'information

Pré-requis

Mathématiques pour l'économie et la gestion 1 [ECGEB150] et Algèbre (1re partie) [INFOB123]

Co-requis

Les unités d’enseignement d’une des propositions suivantes:

  1. Analyse mathématique [INFOB227]
  2. Algèbre et géométrie analytique [SMATB107] et Analyse réelle I [SMATB103]

Mode d'évaluation

En raison des mesures prises dans la lutte contre la propagation du covid-19 et de celles mises en place au niveau de l'UNamur, les modalités d'évaluation font l'objet de modification pour être adaptées à la situation. Les modalités d'évaluation qui sont ainsi d'application pour la période d'évaluation de fin de troisième quadrimestre (seconde session) sont communiquées par l'enseignant, aux étudiants, via WebCampus pour chaque unité d'enseignement

Modalites d'interrogation aux examens :

- en 1ère session, l'examen est écrit, il comporte des questions de théorie et des exercices.

- en 2ème session, l'examen est identique à celui de la 1ère.

Sources, références et supports éventuels

Syllabus disponible sur Webcampus

Langue d'enseignement

Français

Lieu de l'activité

NAMUR

Faculté organisatrice

Faculté des sciences
Rue de Bruxelles, 61
5000 NAMUR

Cycle

Etudes de 1er cycle