Aller au contenu principal

IFT-7012 Théorie algorithmique des graphes

Ce cours aborde des sujets tels la connexité dans un graphe (problèmes du flot maximum, de la dualité min-max, de couplage parfait, etc.), la planarité d'un graphe (formule d'Euler, théorème de Kuratowski, graphe dual), le coloriage d'un graphe (coloriages entiers et fractionnaires des sommets ou des arêtes, graphes de Kneiser), les problèmes de transversales d'un graphe (parcours eulériens, cycles hamiltoniens, graphes de DeBruijn, etc.) et la notion de marche aléatoire sur un graphe (chaînes de Markov, existence de la distribution limite, « mixing time », etc.). Plusieurs problèmes sur les graphes ont d'élégantes solutions, d'autres évidemment sont NP-complets; une partie de ce cours portera donc sur la théorie de la complexité (problèmes NP et NP-complets, théorème de Cook, algorithmes de réductions).

3 Crédits

Cycles du cours

  • Deuxième cycle
  • Troisième cycle

Mode d'enseignement

  • Régulier

Responsables

  • Faculté des sciences et de génie
  • Département d'informatique et de génie logiciel

Restrictions à l'inscription

Cycle d'études

Doit être inscrit à:

  • Deuxième cycle
  • Troisième cycle

Certaines sections de cours peuvent comporter des restrictions additionnelles.

Cette page constitue la description officielle de cette activité. L'Université Laval se réserve le droit de modifier l'activité sans préavis. Tous les horaires indiqués sont sujets à changement.

Répartition hebdomadaire

  • 3h Cours
  • 0h Laboratoire ou travaux pratiques
  • 6h Travail personnel
  • 9h Total

Horaire

Pour vous inscrire, accédez à monPortail.

Hiver 2018 – 1 section offerte

NRC 10058 Capacité maximale: 30 étudiants

Plage horaire

    • Type: En classe
    • Dates: Du 15 janv. 2018 au 27 avr. 2018
    • Journée: Jeudi
    • Horaire: De 9h30 à 12h20
    • Pavillon: Adrien-Pouliot
    • Local: 2546

Automne 2014 – 1 section offerte

NRC 89927 Capacité maximale: 20 étudiants