| Discrete Structures 1 [2024 SoSe] | ||
|---|---|---|
| Code IDS1 |
Name Discrete Structures 1 |
|
| CP 8 |
Duration one semester |
Offered every winter semester |
| Format Lecture 4 SWS + Exercise course 2 SWS |
Workload 240 h; thereof 90 h lecture 20 h preparation for exam 130 h self-study and working on assignments/projects (optionally in groups) |
Availability B.Sc. Angewandte Informatik B.Sc. Informatik B.Sc. Mathematik |
| Language English |
Lecturer(s) Felix Joos |
Examination scheme |
| Learning objectives | Students - understand several basic graph parameters and the central theorems in these areas - can solve easy problems involving discussed topics - can describe graph algorithms computing discussed graph parameters - know how to use graphs and graph parameters to model real world problems |
|
| Learning content | - Introduction to graph theory terminology - Matchings in graph and hypergraphs - Graph connectivity - Planar graphs - Graph Colouring - Hamilton Cycles - Ramsey Theory - Random graphs - Algebraic Graph constructions (Cayley graphs, Kneser graphs,...) - Algorithms computing discussed graph parameters |
|
| Requirements for participation | recommended are: Einführung in die Praktische Informatik (IPI), Mathematik für Informatiker 1 (IMI1) or Lineare Algebra 1 (MA4), Mathematik für Informatiker 2 (IMI2) or Analysis 1 (MA1) | |
| Requirements for the assignment of credits and final grade | The module is completed with a graded oral or written examination. The final grade of the module is determined by the grade of the examination. The requirements for the assignment of credits follows the regulations in section modalities for examinations. | |
| Useful literature | - Reinhard Diestel Graph Theory, 5th edition, Springer, 2016/17 - Douglas West, Introduction to Graph Theory, Pearson, 2011. - J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008. - Bernhard Korte and Jens Vygen, Combinatorial Optimization, 6th edition, 2018. |
|