Module Theory of efficient algorithms, Computer Science (Master) (ER 7)

English language
Compact font

Color scheme

Module summary

Theory of efficient algorithms

INFM110SE

Prof. Dr. Heiko Körner

/

All semesters

none

none

The module deals with the design of efficient algorithms in theory and practice. Students learn proof techniques for graph-theoretical problems in order to show the correctness of algorithms with exact logical conclusions. To the end, they analyze runtimes of procedures and apply suitable analysis techniques. Using the example of numerical problems such as the interpolation and approximation of mathematical models, students also independently design solution methods and then implement them.

The iteration methods are implemented by the students for specific technical problems and parallelized for use on modern high-performance computers.

After completing the module, students will be able to analyze and evaluate algorithms theoretically, but also to apply modeling and simulation methods for the computer-aided design of process sequences in practice.

Written/verbal Exam 120/20 Min. (graded)
Course Graph Algorithms

INFM111SE.a

Lecture

Prof. Dr. Heiko Körner

German

3/2

90 hours in total, including 30 hours of contact study.

Module exam

This couse gives an overview of some basic graph algorithms and their applications. The students learn to apply further algorithms and how to implement them. Furthermore, techniques for proving the correctness and complexity of algorithms are thoroughly studied.

After a brief theoretical introduction to graphs some fundamental algorithms like depth first search and breadth first search are presented. Other algorithms deal with the detection of strongly connected components, topological sorting and the calculation of shortest paths. Efficient tests concerning the existence of circuits in a graph are also discussed.

For this course some basic knowledge of programming and the safe handling of the O-calculus are necessary. Furthermore, the participant is assumed to be familiar with inductive proofs. Both topics are handled in an appendix of the lecture notes.

The substance of the lecture will be discussed at the blackboard. Lecture notes containing the complete material are also available. Lecture notes, exercises and their solutions are available online.

 

Literature: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2001, ISBN 0-262-03293-7.

Classical lecture. Several exercises deepen the field of study and are discussed in the classroom if desired.

Course Modeling and Simulation

INFM111SE.b

Lecture

Prof. Dr. Britta Nestler

German

2/2

60 hours in total, including 30 hours of contact study.

Module exam

Course Modeling and Simulation Exercise

INFM112SE

Exercise

Prof. Dr. Britta Nestler

German

2/1

60 hours in total, including 15 hours of contact study.

Exercise 1 Semester (not graded)