Unregelmäßige Module

Algorithm Engineering
Computational Geometry
Geometric Data Structures
Grundlagen der Theoretischen Informatik III
Grundlagen der Theoretischen Informatik III
Robust Geometric Computing
Topics in Algorithmics

Algorithm Engineering

(in German: Algorithm Engineering - )

Module-ID: FIN-INF-120259

Link:	LSF
Responsibility:	Prof. Dr. Stefan Schirra
Lecturer:	Prof. Dr. Stefan Schirra
Classes:	Lecture Algorithm Engineering
Applicability in curriculum:

Abbreviation

AlgEng

Credit Points

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
Responsibility:	Prof. Dr. Stefan Schirra
Lecturer:	Prof. Dr. Stefan Schirra
Classes:	Lectures and exercises Computational Geometry
Applicability in curriculum:

Abbreviation

CompGeom

Credit Points

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
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

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
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

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
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

Semester

Winter

Fachsem.

ab 5.

Dauer

1 Semester

Sprache

deutsch

Niveau

Master

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
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

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
Responsibility:	Prof. Dr. Stefan Schirra
Lecturer:	Prof. Dr. Stefan Schirra
Classes:	Lecture/Exercises Topics in Algorithmics
Applicability in curriculum:

Abbreviation

TinA

Credit Points

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: