Unregelmäßige Module 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 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 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 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 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 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 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 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: