Difference between revisions of "Courses/THEG"
From LRDE
Line 5: | Line 5: | ||
|period=S2, Ing1 |
|period=S2, Ing1 |
||
|audience=Tronc-commun |
|audience=Tronc-commun |
||
+ | |exam type=Partiel |
||
+ | |duration=14h à 24h |
||
|optional course=non |
|optional course=non |
||
|module=Informatique Fondamentale |
|module=Informatique Fondamentale |
||
|prerequisites=ALGO |
|prerequisites=ALGO |
||
− | |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). |
+ | |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=* 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, ...) |
* Vocabulaire (graphe orienté, non-orienté, arbre, cycle, composantes, rayon, diamètre, clique, nombre chromatique, ...) |
||
Line 16: | Line 18: | ||
* Graphes planaires (Formule d'Euler, Théorème de Kuratowsky, Théorème des 4 couleurs) |
* 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). |
* Graphes cordaux (Triangulation, LexBFS, Coloration gloutonne, graphes d'intersection, application à l'allocation de registres). |
||
− | |||
|references=Introduction a l'algorithmique. Thomas H. Cormen. Edition Dunod |
|references=Introduction a l'algorithmique. Thomas H. Cormen. Edition Dunod |
||
Introduction to algorithms. Cormen, Leiserson, Rivest and Stein. |
Introduction to algorithms. Cormen, Leiserson, Rivest and Stein. |
Revision as of 16:46, 1 July 2014
Titre |
Théorie des Graphes |
---|---|
Sigle |
THEG |
Enseignant | |
Période |
S2, Ing1 |
Public |
Tronc-commun |
Contrôle |
Partiel |
Durée |
14h à 24h"hà24h" is not declared as a valid unit of measurement for this property. |
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 |
|
Documentation |
|
Support | |
Journaux |