Module im Bereich: Mathematik / Theoretische Informatik

• Grundlagen der Theoretischen Informatik
• Introduction to the Theory of Computation
• Grundlagen der Theoretischen Informatik II
• Introduction to the Theory of Computation II
• Mathematik M5d
• Mathematics M5e

Grundlagen der Theoretischen Informatik

Winter

(engl. Introduction to the Theory of Computation )

Modulnummer: FIN-INF-110105

Kürzel GThI

CP 5

Semester Winter

Fachsem. ab 3.

Dauer 1 Semester

Sprache deutsch

Niveau Bachelor

Link zum LSF:	LSF
Zugang beschränkt:	false
Verantwortung:	Prof. Dr. Stefan Schirra
Dozent:in:	Prof. Dr. Stefan Schirra
Lehrveranstaltungen:	Vorlesung Grundlagen der Theoretischen Informatik Übung Grundlagen der Theoretischen Informatik
Verwendbarkeit:	- B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. INF: Aufbaumodule (SPO 2027) - B.Sc. CV: Mathematik / Theoretische Informatik - B.Sc. CV: Computervisualistik Pflicht (SPO 2027) - B.Sc. INGINF: Mathematik / Theoretische Informatik - B.Sc. INGINF: Ingenieurinformatik Pflicht (SPO 2027) - B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht - B.Sc. WIF: Informatik Wahlpflicht (SPO 2027) - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)

Angestrebte Lernergebnisse:

• Grundlagen von Automatentheorie und formalen Sprachen zur Problemlösung
• Fähigkeit, Probleme hinsichtlich Berechenbarkeit und Komplexität einordnen zu können

Inhalt:

• Einführung in Formale Sprachen (reguläre und kontextfreie Sprachen, Grammatiken),
• elementare Automatentheorie (endliche Automaten, Kellerautomaten),
• Berechnungsmodelle und Churchsche These,
• Entscheidbarkeit und Semi-Entscheidbarkeit,
• Komplexitätsklassen P und NP, NP-Vollständigkeit

Arbeitsaufwand:

• 70h Präsenzzeit
• 80h selbstständige Arbeit

Prüfungsvorleistungen:	Studien-/Prüfungsleistungen:	Lehrform / SWS:
Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren (siehe moodle und Vorlesung) und mindestens einmal erfolgreich eine eigene Lösung präsentieren	Klausur 120 Minuten (schriftliche Prüfung)	Vorlesung (3 SWS ) Übung (2 SWS)

Voraussetzungen nach Prüfungsordnung:	Empfohlene Voraussetzungen:
keine

Medienformen:	Literatur:
	Hopcroft, Motwani, Ullmann; Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie Lewis, Papadimitriou; Elements of the Theory of Computation Sipser; Theory of Computation.

Hinweise:

Introduction to the Theory of Computation

Winter

(in German: Grundlagen der Theoretischen Informatik )

Module-ID: FIN-INF-110493

Abbreviation

Credit Points 5

Semester Winter

Term

Duration 1 Semester

Language english

Level Bachelor

Link:	LSF
Limited accessability:
Responsibility:	Tetiana Lavynska
Lecturer:	Tetiana Lavynska
Classes:	Lecture Introduction to the Theory of Computation Exercise Introduction to the Theory of Computation
Applicability in curriculum:	- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)

Intended learning outcomes:

• Basics of automata theory and formal languages for problem solving
• Ability to classify problems in terms of predictability and complexity

Content:

• Introduction to Formal Languages (regular and context-free languages, grammars),
• elementary automata theory (finite automata, basement automata),
• Computational models and Church's thesis,
• Decidability and semi-decidability,
• Complexity classes : P and NP, NP-completeness

Workload:
70h contact hours + 80h self study

Pre-examination requirements:	Type of examination:	Teaching method / lecture hours per week (SWS):
Exam preparation: Successful participation in the exercises (see lecture)	Written exam 120 minutes	Lecture (3 SWS) Exercise (2 SWS)

Prerequisites according to examination regulations:	Recommended prerequisites:
none

Media:	Literature:
	Hopcroft, Motwani, Ullmann; Einführung in der Automatentheorie, Formale Sprachen und Komplexitätstheorie Lewis, Papadimitriou; Elements of the Theory of Computation Sipser; Theory of Computation.

Comments:

Grundlagen der Theoretischen Informatik II

Sommer

(engl. Introduction to the Theory of Computation II )

Modulnummer: FIN-INF-110118

Kürzel GThI 2

CP 5

Semester Sommer

Fachsem. ab 4.

Dauer 1 Semester

Sprache deutsch

Niveau Bachelor

Link zum LSF:	LSF
Zugang beschränkt:	false
Verantwortung:	Prof. Dr. Stefan Schirra
Dozent:in:	Prof. Dr. Stefan Schirra
Lehrveranstaltungen:	Vorlesung Grundlagen der Theoretischen Informatik II Übung Grundlagen der Theoretischen Informatik II
Verwendbarkeit:	- B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. INF: Aufbaumodule (SPO 2027) - B.Sc. CV: Informatik - Wahlpflicht - B.Sc. CV: Computervisualistik Wahlpflicht (SPO 2027) - B.Sc. INGINF: Informatik - Wahlpflicht - B.Sc. INGINF: Informatik Wahlpflicht (SPO 2027) - B.Sc. WIF: Verstehen und Gestalten - Wahlpflicht - B.Sc. WIF: Informatik Wahlpflicht (SPO 2027) - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)

Angestrebte Lernergebnisse:
Die Studierenden haben erweiterte Fähigkeiten, komplexe Probleme hinsichtlich Berechenbarkeit und Komplexität beurteilen und klassifizieren zu können.

Inhalt:

• Weiterführendes zu Formalen Sprachen und Automatentheorie (Abschlusseigenschaften, deterministische Kellerautomaten, Zustandsminimierung endlicher Automaten),
• Äquivalenz verschiedener Berechnungsmodelle (beispielsweise Turingmaschinen, Registermaschinen, primitiv rekursive und mu-rekursive Funktionen, Grammatiken),
• weitere unentscheidbare und NP-vollständige Probleme.

Arbeitsaufwand:
56h Präsenzzeit 94h selbstständige Arbeit (Bearbeiten der Übungsaufgaben Nachbereitung der Vorlesungen)

Prüfungsvorleistungen:	Studien-/Prüfungsleistungen:	Lehrform / SWS:
Erfolgreiche Teilnahme an den Übungen, d.h. für je 4 aufeinanderfolgende Übungsblätter 50% der Aufgaben erfolgreich votieren	Klausur 120 Min (schriftliche Prüfung)	Vorlesung (2 SWS) Übung (2 SWS)

Voraussetzungen nach Prüfungsordnung:	Empfohlene Voraussetzungen:
keine	Grundlagen der Theoretischen Informatik

Medienformen:	Literatur:
	Sipser; Theory of Computation Kozen; Automata and Computability

Hinweise:
Auch dieses Modul ist zwei Lehrstühlen zugeordnet, die es abwechselnd bedienen

Introduction to the Theory of Computation II

Summer

(in German: Grundlagen der Theoretischen Informatik II )

Module-ID: FIN-INF-110494

Abbreviation

Credit Points 5

Semester Summer

Term

Duration 1 Semester

Language english

Level Bachelor

Link:	LSF
Limited accessability:
Responsibility:	Tetiana Lavynska
Lecturer:	Tetiana Lavynska
Classes:	Lecture Introduction to the Theory of Computation II Exercise Introduction to the Theory of Computation II
Applicability in curriculum:	- B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Aufbaumodule (SPO 2027)

Intended learning outcomes:
Students have advanced skills in assessing and classifying complex problems in terms of calculability and complexity.

Content:

• Further information on formal languages and automata theory (closure properties, deterministic basement automata, state minimization of finite automata),
• equivalence of different computational models (e.g. Turing machines, register machines, primitive recursive and mu-recursive functions, grammars),
• further undecidable and NP-complete problems.

Workload:
56h contact hours + 94h self study (working on the exercises and following up on the lectures)

Pre-examination requirements:	Type of examination:	Teaching method / lecture hours per week (SWS):
Exam admission prerequisites: Successful participation in the exercises (see lecture)	Written exam 120 min	Lecture (2 SWS) Exercise (2 SWS)

Prerequisites according to examination regulations:	Recommended prerequisites:
none	Introduction to the Theory of Computation

Media:	Literature:
	Sipser; Theory of Computation Kozen; Automata and Computability

Comments:

Mathematik M5d

Sommer

(engl. Mathematics M5d )

Modulnummer: FMA-INF-501329

Link zum LSF:	(Angeboten wenn im LSF)
Verantwortung:	Prof. Dr. Thomas Kahle
Dozent:in:	, Prof. Dr. Thomas Kahle
Lehrveranstaltungen:	Vorlesung Mathematik M5d Globalübung Mathematik M5d Gruppenübung Mathematik M5d

Leistungspkt. 5

Semester Sommer

Fachsem.

Dauer 1 Semester

Sprache deutsch

Niveau Bachelor

Ziele und Kompetenzen:
Die Studierenden erlangen auf Verständnis beruhende Vertrautheit mit den für fachwissenschaftliche Module in der Informatik relevanten mathematischen Konzepten und Methoden. Sie erwerben technische Fähigkeiten im Umgang mit diesen, insbesondere unter Verwendung fachspezifischer Beispiele. Thematische Schwerpunkte des Moduls sind diskrete und algebraische Strukturen sowie algorithmische Aspekte.

Inhalt:

• Algebraische Strukturen
• Kombinatorik und Graphen
• Grundlagen der Optimierung
• Numerische Lösungsverfahren
• Geometrische Methoden

Arbeitsaufwand:

	Präsenszeit	Selbststudium
Vorlesung	3 SWS / 42 h	66 h
Globalübung	2 SWS / 28 h
Gruppenübung	1 SWS / 14 h

Voraussetzungen für die Teilnahme:	Prüfungsvorleistung:	Prüfungsleistung:

Verwendbarkeit:

- B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. INF: Mathematik (SPO 2027) - B.Sc. CV: Mathematik / Theoretische Informatik - B.Sc. CV: Mathematik (SPO 2027) - B.Sc. INGINF: Mathematik / Theoretische Informatik - B.Sc. INGINF: Mathematik (SPO 2027) - B.Sc. WIF: Verstehen - Pflicht - B.Sc. WIF: Mathematik (SPO 2027) - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Mathematik (SPO 2027)

Verwendbarkeit andere Fakultäten:

Hinweise:

Mathematics M5e

Summer

(engl. Mathematics M5e )

Module-ID: FMA-INF-5013292

Link:	(Angeboten wenn im LSF)
Responsibility:	Prof. Dr. Thomas Kahle
Lecturer:	, Prof. Dr. Thomas Kahle
Classes:	Lecture Mathematics M5e Global tutorial Mathematics M5e Group tutorial Mathematics M5e

Credit Points 5

Semester Summer

Term

Duration 1 Semester

Language english

Level Bachelor

Goals and qualifications:
The students acquire comprehension of and familiarity with concepts and methods that
are relevant for subject-specific classes in computer science. They develop technical skills by applying those methods, in particular to subject-specific examples. The topical focus of the module is on discrete and algebraic structures, and algorithmic aspects.

Content:

• Algebraic structures
• Combinatorics, graphs
• Foundations of Optimization
• Numerical solving
• Geometric methods

Workload:

	In class	self-study
Lecture	3 SWS / 42 h	66 h
Global tutorial	2 SWS / 28 h
Group tutorial	1 SWS / 14 h

Prerequisites for participation:	Pre-examination requirements:	Type of examination:

Applicability in curriculum:

- B.Sc. INF: Mathematik / Theoretische Informatik - B.Sc. INF: Mathematik (SPO 2027) - B.Sc. CV: Mathematik / Theoretische Informatik - B.Sc. CV: Mathematik (SPO 2027) - B.Sc. INGINF: Mathematik / Theoretische Informatik - B.Sc. INGINF: Mathematik (SPO 2027) - B.Sc. WIF: Verstehen - Pflicht - B.Sc. WIF: Mathematik (SPO 2027) - B.Sc. INF (bilingual): Mathematik / Theoretische Informatik - B.Sc. INF (bilingual): Mathematik (SPO 2027)

Comments: