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

Settings

Menu type

Color scheme

Menu color

Input color

Module summary
Module name Theory of efficient algorithms
Internal number INFM110SE
Coordinator Prof. Dr. Heiko Körner
Extent 7 ECTS points / 5 Contact hours
Semester All semesters
Pre-requisites with regard to content none
Pre-requisites according to the examination regulations none
Competencies The three courses in this module teach the design of efficient algorithms in theory and practice. By presenting numerous examples of numerical and graph theory problems, students will learn typical methods for their solution and also how to implement them. Techniques for proving the correctness of an algorithm will be presented. Also, methods for analysing their computational complexity will be given. Moreover, this module attaches importance to modeling and simulation methods. These algorithms are used in many areas of research and industry and enable a computer-assisted design of processes. Therefore, students are introduced to numerical algorithms for interpolation and approximation of mathematical models. The students will implement several corresponding technical problems with parallelized programs on modern high performance computers.
Assessment Written/verbal Exam 120/20 Min. (graded)

Course Graph Algorithms
Internal number INFM111SE.a	Type/mode Lecture
Lecturer Prof. Dr. Heiko Körner	Language of instruction German
Extent (ECTS/SWS) 3/2	Assessment Module exam
Content 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.
Recommended reading 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.
Comments Classical lecture. Several exercises deepen the field of study and are discussed in the classroom if desired.

Course Modeling and Simulation
Internal number INFM111SE.b	Type/mode Lecture
Lecturer Prof. Dr. Britta Nestler	Language of instruction German
Extent (ECTS/SWS) 2/2	Assessment Module exam
Content
Recommended reading

Course Modeling and Simulation Exercise
Internal number INFM112SE	Type/mode Exercise
Lecturer Prof. Dr. Britta Nestler	Language of instruction German
Extent (ECTS/SWS) 2/1	Assessment Exercise 1 Semester (not graded)
Content
Recommended reading