Théorie des graphes(MAT332)
| Nom du Cours | Semestre du Cours | Cours Théoriques | Travaux Dirigés (TD) | Travaux Pratiques (TP) | Crédit du Cours | ECTS | |
|---|---|---|---|---|---|---|---|
| MAT332 | Théorie des graphes | 6 | 5 | 0 | 0 | 3 | 5 |
| Cours Pré-Requis | |
| Conditions d'Admission au Cours |
| Langue du Cours | |
| Type de Cours | Électif |
| Niveau du Cours | Licence |
| Enseignant(s) du Cours | Serap GÜRER serapgurer@gmail.com (Email) |
| Assistant(e)s du Cours | |
| Objectif du Cours | Ce cours vise à présenter les concepts de base, les sujets et les résultats de la théorie moderne des graphes avec un objectif de techniques applicables notamment aux sciences sociales. |
| Contenus |
Concepts théoriques de base des graphes : chemins et cycles, connectivité, arbres, sous-graphes couvrant, graphes bipartis, cycles hamiltoniens et d'Euler. Algorithmes pour le chemin le plus court et les arbres couvrants. Théorie de l'appariement. Graphiques planaires. Coloration. Flux dans les réseaux, théorème de max-flow min-cut. Graphiques aléatoires d'Erdös-Rényi. Lemme de régularité de Szemerédi. Graphiques infinis. Applications en informatique et aux sciences sociales. |
| Acquis d'Apprentissage du Cours |
A la fin de cours, l'étudiant doit être capable de : 1)connaître quelques classes importantes de problèmes de théorie des graphes ; 2) de formuler et de prouver des théorèmes centraux sur les arbres, l'appariement, la connectivité, la coloration et les graphes planaires ; 3)de décrire et d'appliquer quelques algorithmes de base pour les graphiques ; 4) d'utiliser la théorie des graphes comme outil de modélisation. |
| Méthodes d'Enseignement | |
| Ressources |
Graph theory, Diestel, Reinhard., 4th ed.: Heidelberg: Springer, 2010. Graph Theory with Applications, Bondy.and Murty, North-Holland, 1979 Graph Based Natural Language Processing and Information Retrieval / Rada Mihalcea, Dragomir Radev, Cambridge University Press, 2011. Discrete Mathematics, An Open Introduction, Oscar Levin, at http://discretetext.oscarlevin.com/ Proof Techniques in Graph Theory, Harary, F. , Academic Press, New York, 1969. New Directions in the Theory of Graphs, Harary, F., Academic Press, New York, 1973. |
Intitulés des Sujets Théoriques
| Semaine | Intitulés des Sujets |
|---|---|
| 1 | Concepts Fondamentaux de la Théorie des Graphes |
| 2 | Chemins et cycles |
| 3 | Arbres |
| 4 | Fondements de la théorie des appariements |
| 5 | Algorithmes pour le plus court chemin |
| 6 | Kapsayıcı ağaç algoritmaları |
| 7 | Examen Partiel |
| 8 | Graphes Planaires et Coloration |
| 9 | Graphes Planaires et Coloration |
| 10 | Grands Graphes et Clustering |
| 11 | Grands Graphes et Clustering |
| 12 | Présentations de projets |
| 13 | Théorie des Graphes Appliquée et Modélisation |
| 14 | Théorie des Graphes Appliquée et Modélisation |
Intitulés des Sujets Pratiques
| Semaine | Intitulés des Sujets |
|---|
Contribution à la Note Finale
| Numéro | Frais de Scolarité | |
|---|---|---|
| Contribution du contrôle continu à la note finale | 3 | 60 |
| Contribution de l'examen final à la note finale | 1 | 40 |
| Toplam | 4 | 100 |
Contrôle Continu
| Numéro | Frais de Scolarité | |
|---|---|---|
| Devoir | 0 | 0 |
| Présentation | 1 | 10 |
| Examen partiel (temps de préparation inclu) | 1 | 30 |
| Projet | 1 | 20 |
| Travail de laboratoire | 0 | 0 |
| Autres travaux pratiques | 0 | 0 |
| Quiz | 0 | 0 |
| Devoir/projet de session | 0 | 0 |
| Portefeuille | 0 | 0 |
| Rapport | 0 | 0 |
| Journal d'apprentissage | 0 | 0 |
| Mémoire/projet de fin d'études | 0 | 0 |
| Séminaire | 0 | 0 |
| Autre | 0 | 0 |
| Toplam | 3 | 60 |
| No | Objectifs Pédagogiques du Programme | Contribiton | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | comprend les principes de la méthode hypothético-déductive; s'est interrogé systématiquement sur la pertinence et la justesse des énoncés mathématique qu'il a rencontré ou produit; | X | ||||
| 2 | sait énoncer et utiliser judicieusement les concepts et les résultats des mathématiques de base; | X | ||||
| 3 | maîtrise les techniques de calcul et les algorithmes courants; possède une bonne intelligence de calcul pour les mettre en œuvre; est capable d'identifier les outils pertinents, parmi ceux qu'il connaît, pour la résolution d'un problème, et est capable de juger s’il ne possède pas ces outils; | X | ||||
| 4 | est capable d'exprimer de manière organisée, tant à l'écrit qu'à l'oral, ses idées mathématiques; | X | ||||
| 5 | a réalisé les relations essentielles qui lient entre eux ces concepts et résultats; est capable de passer de l'un à l'autre de divers mode de représentation des objets mathématiques (dessins, formules, énoncés précis, heuristiques, collection d'exemples,...); | X | ||||
| 6 | a poursuivi, en autonomie, une stratégie d'apprentissage guidée; s'est engagé dans des stratégies de résolution d'un problème complexe; | X | ||||
| 7 | a les bases théoriques et pratiques suffisantes en informatique pour pouvoir poursuivre l'apprentissage d'un langage de programmation; | X | ||||
| 8 | s'est interrogé sur la pertinence de la modélisation mathématique et l'usage des outils mathématiques dans les sciences naturelles et dans le monde professionnel; a été sensibilisé à l'évolution historique des concepts mathématiques; | X | ||||
| 9 | a eu l'opportunité de choisir librement certains de ses cours (de mathématiques ou d'autres disciplines) et a, à l'occasion, appris à prendre ses responsabilités et à organiser son projet éducatif par lui-même; | X | ||||
| 10 | a une maîtrise de la langue française et d'une autre langue étrangère suffisante pour pouvoir poursuivre des études ou travailler à l'étranger. | X | ||||
| Activités | Nombre | Durée | Charge totale de Travail |
|---|---|---|---|
| Durée du cours | 14 | 3 | 42 |
| Préparation pour le cours | 14 | 2 | 28 |
| Devoir | 6 | 4 | 24 |
| Présentation | 1 | 1 | 1 |
| Examen partiel (temps de préparation inclu) | 1 | 8 | 8 |
| Projet | 1 | 8 | 8 |
| Laboratoire | 0 | 0 | 0 |
| Autres travaux pratiques | 0 | 0 | 0 |
| Examen final (temps de préparation inclu) | 1 | 12 | 12 |
| Quiz | 0 | 0 | 0 |
| Devoir/projet de session | 0 | 0 | 0 |
| Portefeuille | 0 | 0 | 0 |
| Rapport | 0 | 0 | 0 |
| Journal d'apprentissage | 0 | 0 | 0 |
| Mémoire/projet de fin d'études | 0 | 0 | 0 |
| Séminaire | 0 | 0 | 0 |
| Autre | 0 | 0 | 0 |
| Charge totale de Travail | 123 | ||
| Charge totale de Travail / 25 | 4.92 | ||
| Crédits ECTS | 5 | ||