Difference between revisions of "Courses/THEG"

Revision as of 12:15, 13 June 2014

Titre	Théorie des Graphes
Sigle	THEG
Enseignant	Alexandre Duret-Lutz
Période	S2, Ing1
Public	Tronc-commun
Contrôle
Durée
Optionnel	non
Module	Informatique Fondamentale
Prérequis	ALGO
Objectifs	L'objectif du cours est triple. Il s'agit d'une part d'introduire le vocabulaire de la théorie des graphes et d'illustrer sont vaste champ d'applications. D'autre part ce cours prolonge le cours d'algorithmique en étudiant la complexité de chaque algorithme présenté (dont certains utilisant de la programmation dynamique). Enfin ce cours relie les graphes à la théorie des groupes (abordée brièvement en classes préparatoires).
Plan	Histoire de la théorie des graphes et applications diverses (Ponts de Königsberg, calcul de résistance dans un circuit, démonstration de la formule des alcanes, formule de Cayley) Vocabulaire (graphe orienté, non-orienté, arbre, cycle, composantes, rayon, diamètre, clique, nombre chromatique, ...) Représentation et codage des graphes (listes et matrices d'ajacence) Calculs de plus courts chemins (Dijkstra, Bellman-Ford, Floyd-Warshall,...). Lien avec la théorie des groupes (Plus court chemin = calcul d'une puissance de matrice) Graphes planaires (Formule d'Euler, Théorème de Kuratowsky, Théorème des 4 couleurs) Graphes cordaux (Triangulation, LexBFS, Coloration gloutonne, graphes d'intersection, application à l'allocation de registres).
Documentation	Introduction a l'algorithmique. Thomas H. Cormen. Edition Dunod Introduction to algorithms. Cormen, Leiserson, Rivest and Stein.
Support
Journaux

@@ Line 8: / Line 8: @@
 |module=Informatique Fondamentale
 |prerequisites=ALGO
-|objectives=Étude des algorithmes sur les graphes.  Ce cours possède des liens forts avec le cours d'algorithmique (calculs de complexité, algorithmes programmation dynamique) ainsi qu'avec la théorie des groupes.
+|objectives=L'objectif du cours est triple. Il s'agit d'une part d'introduire le vocabulaire de la théorie des graphes et d'illustrer sont vaste champ d'applications. D'autre part ce cours prolonge le cours d'algorithmique en étudiant la complexité de chaque algorithme présenté (dont certains utilisant de la programmation dynamique). Enfin ce cours relie les graphes à la théorie des groupes (abordée brièvement en classes préparatoires).
+|content=* Histoire de la théorie des graphes et applications diverses (Ponts de Königsberg, calcul de résistance dans un circuit, démonstration de la formule des alcanes, formule de Cayley)
-|content=* Représentation et codage des graphes
+* Vocabulaire (graphe orienté, non-orienté, arbre, cycle, composantes, rayon, diamètre, clique, nombre chromatique, ...)
-* Parcours de graphe
+* Représentation et codage des graphes (listes et matrices d'ajacence)
-* Plus court chemin
+* Calculs de plus courts chemins (Dijkstra, Bellman-Ford, Floyd-Warshall,...).
-* Arbres couvrants de poids minimums
+* Lien avec la théorie des groupes (Plus court chemin = calcul d'une puissance de matrice)
-* Concept de flot, flot maximum
+* Graphes planaires (Formule d'Euler, Théorème de Kuratowsky, Théorème des 4 couleurs)
-* Lien avec la théorie des groupes.
+* Graphes cordaux (Triangulation, LexBFS, Coloration gloutonne, graphes d'intersection, application à l'allocation de registres).
 |references=Introduction a l'algorithmique. Thomas H. Cormen. Edition Dunod
 Introduction to algorithms.  Cormen, Leiserson, Rivest and Stein.

Difference between revisions of "Courses/THEG"

From LRDE

Revision as of 12:15, 13 June 2014