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
  • Modes 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 2024 – 1 section offerte

NRC 15908 Capacité maximale: 30 étudiants

Plage horaire

    • Type: En classe
    • Dates: Du 15 jan. 2024 au 26 avr. 2024
    • Journée: Lundi
    • Horaire: De 12h30 à 15h20
    • Pavillon: Adrien-Pouliot
    • Local: 2504

Hiver 2018 – 1 section offerte

NRC 10058 Capacité maximale: 30 étudiants