Module im Bereich: Mathematik / Theoretische Informatik

• Grundlagen der Theoretischen Informatik
• 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:

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: