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).
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 activité est contributoire dans:
- Maîtrise en génie électrique
- Maîtrise en informatique
- Maîtrise en informatique - intelligence artificielle
- Maîtrise en biochimie - avec mémoire
- Maîtrise en génie électrique - avec mémoire
- Maîtrise en informatique - avec mémoire
- Maîtrise en microbiologie - avec mémoire
- Diplôme d'études supérieures spécialisées en intelligence artificielle
- Doctorat en biochimie
- Doctorat en génie électrique
- Doctorat en informatique
- Doctorat en microbiologie
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
Automne 2014 – 1 section offerte
NRC 89927 Capacité maximale: 20 étudiants