Discrete Structures
Module IN0015
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
Module version of WS 2015/6 (current)
There are historic module descriptions of this module. A module description is valid until replaced by a newer one.
Whether the module’s courses are offered during a specific semester is listed in the section Courses, Learning and Teaching Methods and Literature below.
available module versions  

WS 2015/6  SS 2012 
Basic Information
IN0015 is a semester module in German language at Bachelor’s level which is offered in winter semester.
This Module is included in the following catalogues within the study programs in physics.
 Further Modules from Other Disciplines
Total workload  Contact hours  Credits (ECTS) 

240 h  90 h  8 CP 
Content, Learning Outcome and Preconditions
Content
The lecture introduces elementary concepts and important areas of discrete mathematics that are relevant for informatics students. It covers the following five topics:
1) Basic concepts of sets, relations and functions:
 sets: basic operations, equivalence laws, KVdiagram, countable and uncountable sets, Cantor's Theorem
 relations: join, transitive hull, relational algebra
 functions: basic properties, composition, inverse
2) Fundamentals of Propositional Logic and FirstOrder Logic:
 Propositional Logic:
 syntax and semantics
 truth tables and their connection to KVdiagrams
 equivalence laws
 CNF, DNF, normalization procedure, equisatisfiability
 SATprocedure: DPLL, resolution, proof of correctness
 modelling with propositional logic
 Predicate Logic:
 syntax and semantics
 equivalence laws
 modelling with predicate logic
3) Basics of combinatorics:
 counting principles
 drawing of balls from urns: variations, permutations, combinations
 binomial coefficients: symmetry, identities of Pascal and Vandermonde
 distribution problems
 Stirlingnumbers of the first and second kind
 ordered and unordered partition functions
 application: load distribution
4) Basics of graph theory:
 basic definitions
 trees
 Euler and Hamilton circuits: Euler's theorem, theorems of Dirac and Ore
 planar graphs: Euler's polyhedron formula, Kuratowski's theorem
 matchings: marriage theorem, augmenting paths
 matchings with preferences: GaleShapley's theorem
5) Algebraic basics:
 basic definitions: algebra, group, ring, field
 groups:
 order: Lagrange's theorem, generator, group exponent
 cyclic groups
 basics of number theory: largest common divisor, extended euclidean
algorithm, Euler's phi function
 multiplicative groups of integers modulo n
 RSA
1) Basic concepts of sets, relations and functions:
 sets: basic operations, equivalence laws, KVdiagram, countable and uncountable sets, Cantor's Theorem
 relations: join, transitive hull, relational algebra
 functions: basic properties, composition, inverse
2) Fundamentals of Propositional Logic and FirstOrder Logic:
 Propositional Logic:
 syntax and semantics
 truth tables and their connection to KVdiagrams
 equivalence laws
 CNF, DNF, normalization procedure, equisatisfiability
 SATprocedure: DPLL, resolution, proof of correctness
 modelling with propositional logic
 Predicate Logic:
 syntax and semantics
 equivalence laws
 modelling with predicate logic
3) Basics of combinatorics:
 counting principles
 drawing of balls from urns: variations, permutations, combinations
 binomial coefficients: symmetry, identities of Pascal and Vandermonde
 distribution problems
 Stirlingnumbers of the first and second kind
 ordered and unordered partition functions
 application: load distribution
4) Basics of graph theory:
 basic definitions
 trees
 Euler and Hamilton circuits: Euler's theorem, theorems of Dirac and Ore
 planar graphs: Euler's polyhedron formula, Kuratowski's theorem
 matchings: marriage theorem, augmenting paths
 matchings with preferences: GaleShapley's theorem
5) Algebraic basics:
 basic definitions: algebra, group, ring, field
 groups:
 order: Lagrange's theorem, generator, group exponent
 cyclic groups
 basics of number theory: largest common divisor, extended euclidean
algorithm, Euler's phi function
 multiplicative groups of integers modulo n
 RSA
Learning Outcome
On successful completion of the module, students will be able to
 understand the elementary vocabulary of discrete mathematics and use logic, algebraic und algorithmic calculi,
 solve combinatoric problems,
 model and solve problems using graph theory, and
 do a quantitive analysis of the efficiency of algorithms.
 understand the elementary vocabulary of discrete mathematics and use logic, algebraic und algorithmic calculi,
 solve combinatoric problems,
 model and solve problems using graph theory, and
 do a quantitive analysis of the efficiency of algorithms.
Preconditions
none
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
WS 2022/3
WS 2021/2
WS 2020/1
WS 2019/20
WS 2018/9
WS 2017/8
WS 2016/7
WS 2015/6
WS 2014/5
WS 2013/4
WS 2012/3
Type  SWS  Title  Lecturer(s)  Dates  Links 

VO  4  Discrete Structures (IN0015)  Räcke, H. 
Tue, 14:15–15:45, Interims I 101 Tue, 14:15–15:45, MW 2001 Thu, 10:15–11:45, MW 0001 Thu, 10:15–11:45, Interims I 101 

UE  2  Discrete Structures, Exercise Session (IN0015), Mon, Tue 
Friedrich, T.
Hofherr, F.
Zabrodin, R.
Responsible/Coordination: Räcke, H. 
dates in groups  
UE  2  Discrete Structures, Exercise Session (IN0015), Mon, Tue 
Friedrich, T.
Hofherr, F.
Zabrodin, R.
Responsible/Coordination: Räcke, H. 
dates in groups  
UE  2  Discrete Structures, Exercise Session (IN0015), Wed, Thu, Fri 
Friedrich, T.
Hofherr, F.
Zabrodin, R.
Responsible/Coordination: Räcke, H. 
dates in groups  
UE  2  Discrete Structures, Exercise Session (IN0015), Wed, Thu, Fri 
Friedrich, T.
Hofherr, F.
Zabrodin, R.
Responsible/Coordination: Räcke, H. 
dates in groups  
UE  2  Discrete Structures, Exercise Session (IN0015), Wed, Thu, Fri 
Friedrich, T.
Hofherr, F.
Zabrodin, R.
Responsible/Coordination: Räcke, H. 
dates in groups 
Learning and Teaching Methods
The module consists of lectures and exercises. During the lectures students are asked to solve small exercises online. Students also receive weekly assignments, whose solution is discussed in the exercises.
Media
Slide show, blackboard, written assignments.
Literature
 A. Steger: Diskrete Strukturen, Band 1: Kombinatorik, Graphentheorie, Algebra, Springer, 2001
 K.H. Rosen: Discrete Mathematics And Its Applications, McGrawHill, 1995
M. Aigner: Diskrete Mathematik, Vieweg, 1999 (3rd Edition)
 R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, AddisonWesley, 1994
 D. Gries, F.B. Schneider: A Logical Approach to Discrete Math, Springer, 1993
 D.L. Kreher, D.R. Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, 1999
 S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003
 Schöning, Uwe: Logik für Informatiker, SpektrumVerlag, 2000 (5. Auflage)
 K.H. Rosen: Discrete Mathematics And Its Applications, McGrawHill, 1995
M. Aigner: Diskrete Mathematik, Vieweg, 1999 (3rd Edition)
 R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, AddisonWesley, 1994
 D. Gries, F.B. Schneider: A Logical Approach to Discrete Math, Springer, 1993
 D.L. Kreher, D.R. Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search, CRC Press, 1999
 S. Pemmaraju, S. Skiena: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003
 Schöning, Uwe: Logik für Informatiker, SpektrumVerlag, 2000 (5. Auflage)
Module Exam
Description of exams and course work
Students are assessed by means of a written 120  180 minutes exam consisting of a list of exercises.
Some exercises test if the student can correctly use the mathematical vocabulary about sets, relations, logic, graphs and other mathematical objects introduced in the lectures. Further exercises test if the student is able to select the right logical, combinatorial, graph theoretical, or algebraic technique for the solution of a specific problem, and can apply it correctly.
Some exercises test if the student can correctly use the mathematical vocabulary about sets, relations, logic, graphs and other mathematical objects introduced in the lectures. Further exercises test if the student is able to select the right logical, combinatorial, graph theoretical, or algebraic technique for the solution of a specific problem, and can apply it correctly.
Exam Repetition
The exam may be repeated at the end of the semester.