[{"command":"insert","method":null,"selector":".course-modal-ajax-placeholder-950875","data":"\u003Cdiv class=\u0022container content-rte\u0022\u003E\n  \u003Cdiv class=\u0022row\u0022\u003E\n    \u003Cdiv class=\u0022box col-md-6 bg-primary text-white\u0022\u003E\n      \u003Ch2 class=\u0022h1 text-left\u0022\u003E  [M1 DiPaQ] Graphes et algorithmes\n\u003C\/h2\u003E\n                  \u003Cdiv class=\u0022field-spacing\u0022\u003E\n        \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EECTS :\n          3\n        \u003C\/div\u003E\n      \u003C\/div\u003E\n                  \u003Cdiv class=\u0022field-spacing\u0022\u003E\n        \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ESemestre calendaire :\n          Semestre 1\n        \u003C\/div\u003E\n      \u003C\/div\u003E\n            \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ED\u00e9tail du volume horaire\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                          \u003Cspan class=\u0022field__label h4 mt-5 \u0022\u003ECours magistraux :\u003C\/span\u003E\n                                      \u003Cspan\u003E10.5\u003C\/span\u003E\n                      \u003C\/div\u003E\n                                              \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                          \u003Cspan class=\u0022field__label h4 mt-5 \u0022\u003ETravaux dirig\u00e9s :\u003C\/span\u003E\n                                      \u003Cspan\u003E10.5\u003C\/span\u003E\n                      \u003C\/div\u003E\n                                                            \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ELangue d\u0026#039;enseignement\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003EAnglais\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EEnseignement \u00e0 distance\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003Enon\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n      \u003C\/div\u003E\n    \u003Cdiv class=\u0022box col-md-6\u0022\u003E\n            \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EPr\u00e9requis\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EPrerequisites:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EWe will recall the important notions about the structure of a graph in the first session; it will be important to\u0026nbsp;be familiar with them for the next sessions.\u003C\/li\u003E\n\u003Cli\u003EStudents should know what an algorithm is, how to prove that it is correct, and how to compute its complexity, in\u0026nbsp;time and in space. They should be able to use classical algorithmic strategies, such as greedy algorithms and dynamic programming. Cf. Cormen Introduction to Algorithms if needed:\u0026nbsp;[https:\/\/edutechlearners.com\/download\/Introduction_to_algorithms-3rd%20Edition.pdf](https:\/\/edutechlearners.com\/download\/Introduction_to_algorithms-3rd Edition.pdf)\u003C\/li\u003E\n\u003Cli\u003EStudents should be familiar with the most classical data structures and know how to use them: static\/dynamic arrays, (doubly) linked lists, binary search trees, hashmaps, ...\u003C\/li\u003E\n\u003Cli\u003EStudents should be able to articulate and formalize a reasoning. There will be an important focus on the quality of\u0026nbsp;formulation during the course.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EProgramme \/ plan \/ contenus\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ECourse program, plan, content:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003ETotal duration:\u003C\/strong\u003E 21 hours (6 sessions \u00d7 3.5 hours + 3h exam session). Each chapter lasts between 1 and 2 sessions. The first 6 sessions are composed of lectures and exercise sessions, and the 7th is dedicated to the exam.\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cstrong\u003EChapter 1:\u003C\/strong\u003E\u0026nbsp;\u003Cstrong\u003EGraph Theory basics.\u003C\/strong\u003E Introduction of basic structural notions on graphs: (induced) subgraphs, minors, heredity, ...; of classical graph parameters: radius, diameter, minimum\/maximum degree, degeneracy, maximum average degree, clique\/independence number, Hall ratio, ...; and of some relations linking those parameters. Focus on trees (rooted or not, characterisation), and on graph traversal (Breadth-First Search, Depth-First Search) and their structural properties.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EChapter 2: Graph Coloring.\u003C\/strong\u003E\u0026nbsp;The Graph Coloring Problem is used as an archetypal example of a hard problem on graphs, and several approaches are considered to attack it: analysis of a Greedy Algorithm depending on the ordering of the input, presentation of Brooks\u2019 Theorem, of perfect elimination orderings (illustrated with interval graphs).\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EChapter 3:\u0026nbsp;Complexity.\u003C\/strong\u003E Time complexity analysis of sequential algorithms, presentation of the notion of NP-hardness, and of Fixed-Parameter-Tractable (FPT) algorithms. Introduction of the LOCAL model for distributed algorithms and the notion of round complexity.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EChapter 4: Matchings.\u003C\/strong\u003E Introduction of Hall\u2019s Theorem, Berge\u2019s Theorem, and K\u00f6nig\u2019s Theorem. Presentation of the Hungarian Method, and of proper edge-colorings of graphs.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ESession 7 (Exam):\u003C\/strong\u003E\u0026nbsp;3h written exam.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EObjectifs d\u0026#039;apprentissage\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ELearning objectives:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003EAt the end of this course, students will be able to prove structural properties on graphs, and use them in order to solve\u0026nbsp;advanced problems on graphs, including (but not restricting to) algorithmic ones. To that end, they will have to understand and be able to apply a subset of methods\u0026nbsp;that are classical in Graph Theory.\u003C\/p\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EOrganisation g\u00e9n\u00e9rale et modalit\u00e9s p\u00e9dagogiques\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EGeneral course organization and teaching modalities:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EThe course combines\u0026nbsp;\u003Cstrong\u003Electures\u003C\/strong\u003E\u0026nbsp;introducing theoretical concepts with\u0026nbsp;\u003Cstrong\u003Eexercise sessions\u003C\/strong\u003E\u0026nbsp;that allow students to apply and test their comprehension of these concepts in various contexts.\u003C\/li\u003E\n\u003Cli\u003EEach 3.5-hour session blends approximately 60% lecture and 40% exercises.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n                \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EComp\u00e9tences\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003ECompetencies gained in the course:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cp\u003EUpon successful completion, students will have acquired the following competencies:\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003E\u003Cstrong\u003ETechnical competence:\u003C\/strong\u003E\u0026nbsp;Ability to derive and leverage structural graph properties in order to design algorithms to solve hard problems on graphs.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EAnalytical competence:\u003C\/strong\u003E\u0026nbsp;Capacity to analyze the theoretical performances of an algorithm, including its validity, precision, and complexity.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003EPractical competence:\u003C\/strong\u003E\u0026nbsp;Proficiency in formal reasoning and providing a clear presentation thereof.\u003C\/li\u003E\n\u003Cli\u003E\u003Cstrong\u003ETransferable skills:\u003C\/strong\u003E\u0026nbsp;Experience in making a valid chain of thoughts. Abilities in the redaction and the presentation of formal arguments, in the form of a research document.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003EBibliographie\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003E\u003Cp\u003E\u003Cstrong\u003EBibliography:\u003C\/strong\u003E\u003C\/p\u003E\n\u003Cul\u003E\n\u003Cli\u003EBondy, J. A., \u0026amp; Murty, U. S. R. (1976). Graph theory with applications (Vol. 290). London: Macmillan.\u003C\/li\u003E\n\u003Cli\u003EDiestel, R. (2025). Graph theory (Vol. 173). Springer Nature.\u003C\/li\u003E\n\u003C\/ul\u003E\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n        \u003Cdiv class=\u0022field-spacing\u0022\u003E\n      \u003Cdiv class=\u0022field__label h3 dash\u0022\u003ENature de l\u0026#039;\u00e9valuation\u003C\/div\u003E\n                        \u003Cdiv class=\u0022mt-5 text-justify\u0022\u003E\n                                      \u003Cspan\u003EEvaluation Continue non Int\u00e9grale\u003C\/span\u003E\n                      \u003C\/div\u003E\n                  \u003C\/div\u003E\n      \u003C\/div\u003E\n  \u003C\/div\u003E\n\u003C\/div\u003E\n","settings":null}]