# Unregelmäßige Module # Algorithm Engineering (in German: Algorithm Engineering - )
##### **Module-ID:** **FIN-INF-120259**
**Link:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Algorithm+Engineering&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Algorithm Engineering")
**Responsibility:**Prof. Dr. Stefan Schirra
**Lecturer:**Prof. Dr. Stefan Schirra
**Classes:**- Lecture *Algorithm Engineering*
**Applicability in curriculum:**
**Abbreviation** AlgEng **Credit Points** 6 **Semester** Summer **Term** ab 1. **Duration** 1 Semester **Language** english **Level** Master
**Intended learning outcomes:** Students learn how to conduct experimental work in algorithmic computer science. They understand how to bridge the gap between theoretical research and practice by methods of Algorithm Engineering which combine design, analysis, implementation and experiments. **Content:** - Realistic computer models - C++ software libraries - algorithm design paradigms - certifying algorithms - literate programming - designing and conducting experiments - case studies in algorithm engineering - implementation project **Workload:** - 56 h lecture - 124 h independent work
**Type of examination:****Teaching method / lecture hours per week (SWS):**
Oral examination Lecture 4 SWS
**Prerequisites according to examination regulations:****Recommended prerequisites:**
none Basic knowledge of algorithms and data structures
**Media:****Literature:**
- Müller-Hannemann, Schirra (eds): Algorithm Engineering, Springer LNCS 5971 - C. McGeoch: Algorithm Engineering
**Comments:** Wird vermutlich nicht mehr angeboten werden # Computational Geometry (in German: Computational Geometry - )
##### **Module-ID:** **FIN-INF-102201**
**Link:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Computational+Geometry&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Computational Geometry")
**Responsibility:**Prof. Dr. Stefan Schirra
**Lecturer:**Prof. Dr. Stefan Schirra
**Classes:**Lectures and exercises *Computational Geometry*
**Applicability in curriculum:**
**Abbreviation** CompGeom **Credit Points** 6 **Semester** Summer **Term** ab 1. **Duration** 1 Semester **Language** english **Level** Master
**Intended learning outcomes:** Students know how to design and analyze algorithms for advanced geometric problems. They understand the basics of combinatorial and algebraic geometry. **Content:** - basics in combinatorial geometry - basics in algebraic geometry - duality - algorithm design paradigms **Workload:** 56 h classroom + 124 h independent work
**Type of examination:****Teaching method / lecture hours per week (SWS):**
Oral exam - Lecture/Exercises (4 SWS)
**Prerequisites according to examination regulations:****Recommended prerequisites:**
keine Basics in algorithmic geometry (for example, bachelor modul Grundzüge der Algorithmischen Geometrie)
**Media:****Literature:**
- de Bergm Cheong, van Kreveld, Overmars; Computational Geometry - Devadoss, O'Rourke; Computational Geometry
**Comments:** # Geometric Data Structures (in German: Geometric Data Structures - )
##### **Module-ID:** **FIN-INF-102206**
**Link:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Geometric+Data+Structures&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Geometric Data Structures")
**Responsibility:**Prof. Dr. Stefan Schirra
**Lecturer:**Prof. Dr. Stefan Schirra
**Classes:**- Lecture *Geometric Data Structures* - Exercises *Geometric Data Structures*
**Applicability in curriculum:**
**Abbreviation** GeomDS **Credit Points** 6 **Semester** Summer **Term** ab 1. **Duration** 1 Semester **Language** english **Level** Master
**Intended learning outcomes:** Students learn how to design, analyze and apply data structures for geometric problems. **Content:** - heap data structures, - balanced binary search trees, - self-organizing data structures, - amortized analysis, - interval, range and segment trees, - augmented data structures, - quad-trees, - fractional cascading, - point location data structures, - persistent data structures, - making data structures dynamic. **Workload:** 56h in presence + 124h self-study
**Type of examination:****Teaching method / lecture hours per week (SWS):**
oral exam - Lecture (3SWS) - Exercises (1SWS)
**Prerequisites according to examination regulations:****Recommended prerequisites:**
keine Basics in algorithmics
**Media:****Literature:**
- Samet: Foundations of Multidimensional and Metric Data Structures. - Zachmann, Langetepe: Geometric Data Structures for Computer Graphics. - Mehta, Sahmi: Handbook of Data Structures and Applications - Morin: Open Data Structures: An Introduction
**Comments:** # Grundlagen der Theoretischen Informatik III (engl. Introduction to the Theory of Computation III)
##### **Modulnummer: FIN-INF-110464**
**Link zum LSF:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik+III&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik III")
**Verantwortung:**Prof. Dr. Stefan Schirra
**Dozent:in:**Prof. Dr. Stefan Schirra
**Lehrveranstaltungen:**- Vorlesung *Grundlagen der Theoretischen Informatik III* - Übung *Grundlagen der Theoretischen Informatik III*
**Verwendbarkeit:**
**Kürzel** GThI 3 **CP** 6 **Semester** Winter **Fachsem.** ab 1. **Dauer** 1 Semester **Sprache** deutsch **Niveau** Master
**Angestrebte Lernergebnisse:** Studierende lernen, formale Sprachen in die Chomsky-Hierarchie einzuordnen und beurteilen zu können. Sie verstehen algebraische Zugänge zu Formalen Sprachen. Ferner lernen sie Optionen kennen, mit schweren Problemem umzugehen, und diese anzuwenden. **Inhalt:** - Weiteres zu regulären und kontextfreien Sprachen, - Kleene Algebren, - Exakte Exponentialzeitalgorithmen, - Algorithmen für spezielle Graphklassen, - Festparameterhandhabbarkeit, - Approximationsalgorithmen und Nichatapproximierbarkeit - Elementare Komplexitätstheorie. **Arbeitsaufwand:** 56h Präsenzzeit + 124h selbstständige Arbeit
**Studien-/Prüfungsleistungen:****Lehrform / SWS:**
Klausur 120 Minuten - Vorlesung (3 SWS) - Übung (1 SWS)
**Voraussetzungen nach Prüfungsordnung:****Empfohlene Voraussetzungen:**
keine Grundlagen der Theoretischen Informatik I + II (Bachelor)
**Medienformen:****Literatur:**
- Sipser; Theory of Computation - Kozen; Automata and Computability - Shallit; A Second Course on Automata and Computability Theory
**Hinweise:** # Grundlagen der Theoretischen Informatik III (engl. Introduction to the Theory of Computation III)
##### **Modulnummer: FIN-INF-110464**
**Link zum LSF:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Grundlagen+der+Theoretischen+Informatik+III&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Grundlagen der Theoretischen Informatik III")
**Verantwortung:**Prof. Dr. Stefan Schirra
**Dozent:in:**Prof. Dr. Stefan Schirra
**Lehrveranstaltungen:**Vorlesung *Grundlagen der Theoretischen Informatik III*Übung *Grundlagen der Theoretischen Informatik III*
**Verwendbarkeit:**
**Kürzel** GThI 3 **CP** 6 **Semester** Winter **Fachsem.** ab 5. **Dauer** 1 Semester **Sprache** deutsch **Niveau** Master
**Angestrebte Lernergebnisse:** Studierende lernen, formale Sprachen in die Chomsky-Hierarchie einzuordnen und beurteilen zu können. Sie verstehen algebraische Zugänge zu Formalen Sprachen. Ferner lernen sie Optionen kennen, mit schweren Problemem umzugehen, und diese anzuwenden. **Inhalt:** - Weiteres zu regulären und kontextfreien Sprachen, - Kleene Algebren, - Exakte Exponentialzeitalgorithmen, - Algorithmen für spezielle Graphklassen, - Festparameterhandhabbarkeit, - Approximationsalgorithmen und Nichatapproximierbarkeit - Elementare Komplexitätstheorie. **Arbeitsaufwand:** ?
**Studien-/Prüfungsleistungen:****Lehrform / SWS:**
? Vorlesung (3SWS) Übung (1SWS)
**Voraussetzungen nach Prüfungsordnung:****Empfohlene Voraussetzungen:**
keine
**Medienformen:****Literatur:**
**Hinweise:** Da es genau die gleiche Veranstaltung ist, gibt es auch keine Unterschiede zur Masterveranstaltung gleichen Namens. # Robust Geometric Computing (in German: Robust Geometric Computing - )
##### **Module-ID:** **FIN-INF-102216**
**Link:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Robust+Geometric+Computing&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Robust Geometric Computing")
**Responsibility:**Prof. Dr. Stefan Schirra
**Lecturer:**Prof. Dr. Stefan Schirra
**Classes:**- Lecture Robust Geometric Computing - Exercises Robust Geometric Computing
**Applicability in curriculum:**
**Abbreviation** RGC **Credit Points** 6 **Semester** Winter **Term** ab 1. **Duration** 1 Semester **Language** english **Level** Master
**Intended learning outcomes:** Students understand robustness and numerical precision issues in the implementation of geometric algorithms and know methods how to deals with these problems, for example, by exact decisions or verified geometric computing **Content:** - basics of floating-point arithmetic - error analysis - floating-point filters and interval arithmetic - software number types with arbitrary precision - geometric filters - computing with algebraic numbers **Workload:** Präsenzzeiten: 3 SWS Vorlesung 1 SWS Frontalübungen und praktische Übungen Selbstständige Arbeit: Bearbeiten der Übungen und Nachbereitung der Vorlesungen 180h = 4 SWS = 56h Präsenzzeit + 124h selbstständige Arbeit
**Type of examination:****Teaching method / lecture hours per week (SWS):**
participation in the implementation project oral exam Lecture (3 SWS) Exercises (1 SWS)
**Prerequisites according to examination regulations:****Recommended prerequisites:**
keine C++ programming language
**Media:****Literature:**
Boissonnat (Ed.); Effective Computational Geometry Mehlhorn, Yap; Robust Geometric Computation (draft)
**Comments:** # Topics in Algorithmics (in German: Topics in Algorithmics - )
##### **Module-ID:** **FIN-INF-120263**
**Link:**[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Topics+in+Algorithmics&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Topics in Algorithmics")
**Responsibility:**Prof. Dr. Stefan Schirra
**Lecturer:**Prof. Dr. Stefan Schirra
**Classes:**Lecture/Exercises Topics in Algorithmics
**Applicability in curriculum:**
**Abbreviation** TinA **Credit Points** 6 **Semester** Summer **Term** ab 1. **Duration** 1 Semester **Language** english **Level** Master
**Intended learning outcomes:** Students know how to find efficient algorithmic solutions or understand that no such solutions (are likely to) exist. **Content:** Varying content in (theoretical) algorithmics, e.g. advanced graph algorithms, algorithmic motion planning, advanced data structures, comouter algebra, computational group theory) **Workload:** Präsenzzeiten: 4 SWS Vorlesung + Übung Selbstständige Arbeit: Bearbeiten der Übungen und Nachbereitung der Vorlesungen, Vorbereiten der Präsentation 180h = 4 SWS = 56h Präsenzzeit + 124h selbstständige Arbeit
**Type of examination:****Teaching method / lecture hours per week (SWS):**
oral exam Lecture/Exeercises (4 SWS)
**Prerequisites according to examination regulations:****Recommended prerequisites:**
keine Basics in algorithms and data structures and analysis of algorithms.
**Media:****Literature:**
**Comments:**