Théorie Algorithmique des Graphes (IFT-66525)

Hiver 2006
Département d'informatique

Horaire: Mercredi, 15h30 -- 18h20

Local: PLT-2569

Nombre de crédits: 3

Professeur: François Laviolette
Courriel:Francois.Laviolette@ift.ulaval.ca
Bureau: Adrien-Pouliot, 3982
Téléphone: (418) 656-2131 Poste 12976

                   

Plan de cours


Aides à la prise de notes et exercices

Devoir #1


Devoir #2

Résumé

Dans ce cours, nous traiterons de plusieurs sujets importants de la théorie des graphes et d'applications qui en découlent. Vous utilisez déjà abondamment les graphes (plus spécifiquement les arbres) dans à peu près tout ce que vous faites. Il serait intéressant d'étudier les différentes propriétés qu'ont ces objets et ce qu'on peut en dire. J'ai volontairement choisi d'étudier des sujets qui s'énoncent simplement:

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é. Ce cours pourra aussi être une bonne occasion d'apprendre à bien rédiger une démonstration, ce qui fait souvent défaut lorsqu'on en vient à écrire un premier article scientifique. En effet, la théorie des graphes est un sujet en or pour cet apprentissage et elle ne nécéssite presque pas de connaissances préalables.


Bibliographie