# Discrete Structures

## Module IN0015

This Module is offered by TUM Department of Informatics.

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.

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, KV-diagram, countable and uncountable sets, Cantor's Theorem

- relations: join, transitive hull, relational algebra

- functions: basic properties, composition, inverse

2) Fundamentals of Propositional Logic and First-Order Logic:

- Propositional Logic:

- syntax and semantics

- truth tables and their connection to KV-diagrams

- equivalence laws

- CNF, DNF, normalization procedure, equisatisfiability

- SAT-procedure: 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

- Stirling-numbers 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: Gale-Shapley'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, KV-diagram, countable and uncountable sets, Cantor's Theorem

- relations: join, transitive hull, relational algebra

- functions: basic properties, composition, inverse

2) Fundamentals of Propositional Logic and First-Order Logic:

- Propositional Logic:

- syntax and semantics

- truth tables and their connection to KV-diagrams

- equivalence laws

- CNF, DNF, normalization procedure, equisatisfiability

- SAT-procedure: 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

- Stirling-numbers 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: Gale-Shapley'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

#### Learning and Teaching Methods

The module consists of lectures and tutorials. During the lectures students are asked to solve small exercises online. Students also receive weekly assignments, whose solution is discussed in the tutorials.

#### 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, McGraw-Hill, 1995

M. Aigner: Diskrete Mathematik, Vieweg, 1999 (3rd Edition)

- R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley, 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, Spektrum-Verlag, 2000 (5. Auflage)

- K.H. Rosen: Discrete Mathematics And Its Applications, McGraw-Hill, 1995

M. Aigner: Diskrete Mathematik, Vieweg, 1999 (3rd Edition)

- R.L. Graham, D.E. Knuth, O. Patashnik: Concrete Mathematics: a Foundation for Computer Science, Addison-Wesley, 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, Spektrum-Verlag, 2000 (5. Auflage)

### Module Exam

#### Description of exams and course work

Students are assessed by means of a written 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.