Friedrich-Schiller-Universität Jena

Name des Moduls	[50050] Automaten und Berechenbarkeit	Bezeichnung des Moduls	FMI-IN0005

Studiengang	[079] - Informatik	ECTS Punkte	9

Arbeitsaufwand für Selbststudium	180	Häufigkeit des Angebotes (Modulturnus)	jedes 2. Semester (ab Wintersemester)
Arbeitsaufwand in Präsenzstunden	90	Dauer des Moduls	1
Arbeitsaufwand Summe (Workload)	270

Modul-Verantwortliche/r	Joachim Giesen
Voraussetzung für die Vergabe von Leistungspunkten (Prüfungsform)	Klausur oder mündliche Prüfung (Festlegung erfolgt zu Beginn des Moduls)
Zusätzliche Informationen zum Modul	LA Informatik: Das Modul wird in die Berechnung der Endnote aufgenommen ab WS 2014/15 verschoben in WS (PO von 2014)
Empfohlene Literatur	U. Schöning: Theoretische Informatik – kurzgefasst, Spektrum Akademischer Verlag.
Voraussetzung für die Zulassung zum Modul	keine
Empfohlene bzw. erwartete Vorkenntnisse	FMI-IN0013 Diskrete Strukturen I FMI-IN0014 Diskrete Strukturen II
Art des Moduls (Pflicht-, Wahlpflicht- oder Wahlmodul)	- 079 LA Gymnasium Informatik: Pflichtmodul - 079 LA Gym (Erweiterung) Informatik: Pflichtmodul - 079 B.A. Informatik: Wahlpflichtmodul - 079 B.Sc. Informatik: Pflichtmodul (Konto A) - 105 B.Sc. Mathematik: Wahlpflichtmodul (Erweiterung: Angewandte Mathematik+Stochastik; Vertiefung: Algorithmik; NF Informatik) - 105 M.Sc. Mathematik (PO-V. 2010): Wahlpflichtmodul (NF Informatik) - 184 B.Sc. Wirtschaftswissenschaften: Wahlpflichtmodul (IMS: Vertiefungsmodule d. FMI) - 276 M.Sc. Wirtschaftsmathematik: Wahlpflichtmodul (Informatik)
Zusammensetzung des Moduls / Lehrformen (V, Ü, S, Praktikum, …)	4 SWS Vorlesung 2 SWS Übung
Inhalte	Formale Sprachen und Automaten (u.a. Chomsky-Hierarchie, Grammatiken, endliche Automaten, Kellerautomaten, Turingmaschinen) Berechenbarkeit (u.a. Berechnungsmodelle und deren Äquivalenz, Entscheidbarkeit und Aufzählbarkeit, Reduktionen, Halteproblem, Postsches Korrespondenzproblem) Theorie der NP-Vollständigkeit
Lern- und Qualifikationsziele	Grundlegende Kenntnisse in Theoretischer Informatik Befähigung zum Einsatz von Modellierungswerkzeugen wie Automaten und Grammatiken Einsicht in die Grenzen der Berechenbarkeit
Voraussetzung für die Zulassung zur Modulprüfung	Übungskriterien, die zum Modulbeginn festgelegt werden