[IDS1] - [de] - [Discrete Structures 1]


Discrete Structures 1 [2022 Sommer]
Code
IDS1
Name
Discrete Structures 1
LP
8
Dauer
one semester
Angebotsturnus
every winter semester
Format
Lecture 4 SWS + Exercise course 2 SWS
Arbeitsaufwand
240 h; thereof
90 h lecture
20 h preparation for exam
130 h self-study and working on assignments/projects (optionally in groups)
Verwendbarkeit
B.Sc. Angewandte Informatik
B.Sc. Informatik
B.Sc. Mathematik
Sprache
English
Lehrende
Felix Joos
Prüfungsschema
Lernziele 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
Lerninhalte - 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
Teilnahme-
voraus-
setzungen
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) oder Analysis 1 (MA1)
Vergabe der LP und Modulendnote The module is completed with a graded oral or written exam. The final grade of the module is determined by the grade of the exam. The requirements for the assignment of credits follows the regulations in section modalities for exams.
Nützliche Literatur - 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.