INF.00882.08 - Automaten und Berechenbarkeit (Vollständige Modulbeschreibung)

INF.00882.08	10 CP
Modulbezeichnung	Automaten und Berechenbarkeit
Modulcode	INF.00882.08
Semester der erstmaligen Durchführung
Fachbereich/Institut	Institut für Informatik
Verwendet in Studiengängen / Semestern	Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Akkreditierungsfassung gültig ab SS 2021 > Informatik (mindestens 10 LP) Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2007/08 - SS 2012) > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2012/13 - SS 2016) > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2016/17 - SS 2018) > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2018/19 - WS 2022/23) > Informatik mehr... Informatik (180 LP) (Bachelor) > Informatik Informatik180, Akkreditierungsfassung gültig ab SS 2021 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, Akkreditierungsfassung (WS 2006/07 - SS 2012) > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, Akkreditierungsfassung (WS 2012/13 - SS 2016) > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, Akkreditierungsfassung (WS 2016/17 - SS 2018) > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, Akkreditierungsfassung (WS 2018/19 - WS 2022/23) > Pflichtmodule Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Akkreditierungsfassung gültig ab WS 2012/13 > Pflichtmodule Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) (ELF, WLF) (Lehramt) > Informatik Inform (Gymnasium) (ELF, WLF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Akkreditierungsfassung gültig ab WS 2012/13 > Pflichtmodule Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Akkreditierungsfassung gültig ab WS 2012/13 > Pflichtmodule Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Akkreditierungsfassung (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Akkreditierungsfassung (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Akkreditierungsfassung (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Akkreditierungsfassung (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Akkreditierungsfassung (WS 2007/08 - WS 2015/16) > Pflichtmodule Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Akkreditierungsfassung gültig ab WS 2019/20 > Anwendungsfach Informatik Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Akkreditierungsfassung (WS 2013/14 - SS 2022) > Anwendungsfach Informatik Mathematik mit Anwendungsfach (180 LP) (Bachelor) > Mathematik Mathematik m. Anw.fach180, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Anwendungsfach Informatik Physik und Digitale Technologien (180 LP) (Bachelor) > Physik Physik u. Dig. Tech. 180, Akkreditierungsfassung gültig ab WS 2019/20 > Wahlobligatorische Ergänzungsfächer
Modulverantwortliche/r
Weitere verantwortliche Personen	apl. Prof. Dr. Klaus Reinhardt
Teilnahmevoraussetzungen	Modul "Mathematische Grundlagen der Informatik und Konzepte der Modellierung" (Besuch)
Kompetenzziele	Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben: Sie können Sprachen mit Automaten, Grammatiken und Regulären Ausdrücken formalisieren. Sie können von einer Formalisierungsmethode zu einer anderen übersetzen und die Korrektheit beweisen. Die dabei verwendeten Konstruktionen können sie an Beispielen durchführen und mathematisch allgemein formalisieren. Sie können Sprachen in der Chomsky-Hierarchie klassifizieren und Nichtzugehörigkeiten zu Klassen beweisen. Sie kennen die Grenzen der Machbarkeit bezüglich der Berechenbarkeit und Komplexität und können Vollständigkeiten beweisen.
Modulinhalte	Abstrakte Spezifikation und Verifikation sind grundlegende intellektuelle Fähigkeiten eines Informatikers. Daher ist es für angehende Informatiker unerlässlich, die Fähigkeit zum logischen Denken, zur Abstraktion sowie Verständnis für kausale Zusammenhänge zu entwickeln. Demgemäß werde in dieser Vorlesung an Hand abstrakter Berechnungsmodelle deren Fähigkeiten und Grenzen analysiert. Basis und Methode dieser Analyse sind Verifikations- (Beweis-)verfahren, wie sie in der Mathematik, insbesondere der mathematischen Logik entwickelt wurden. Ein wesentlicher Bestandteil des Moduls sind daher das Vorstellen von Beweisverfahren in der Vorlesung und deren selbständiges Üben durch die Teilnehmer. Die Gegenstände an Hand derer dies erfolgen soll sind der Informatik entnommen, es werden in der Vorlesung die folgenden Gebiete behandelt. Endliche Automaten und reguläre Sprachen Kellerautomaten und kontextfreie Sprachen Algorithmenbegriffe: Turing-Maschinen, partiell-rekursive Funktionen Berechenbarkeitstheorie, unentscheidbare Probleme Effiziente Algorithmen, P-NP-Problem Chomsky-Hierarchie formaler Sprachen
Lehrveranstaltungsformen	Vorlesung (4 SWS) Übung (2 SWS) Kursus
Unterrichtsprachen	Deutsch, Englisch
Dauer in Semestern	1 Semester Semester
Angebotsrhythmus Modul	jedes Sommersemester
Aufnahmekapazität Modul	unbegrenzt
Prüfungsebene
Credit-Points	10 CP
Modulabschlussnote	LV 1: %; LV 2: %; LV 3: %.
Faktor der Modulnote für die Endnote des Studiengangs	1

Modulveranstaltung	Lehrveranstaltungsform	Veranstaltungstitel	SWS	Workload selbstgestaltete Arbeit	Workload Summe
LV 1	Vorlesung	Vorlesung	4		0
LV 2	Übung	Übung	2		0
LV 3	Kursus	Bearbeiten der Übungsausgaben			0
Workload modulbezogen				300	300
Workload Modul insgesamt					300

Prüfung	Prüfungsvorleistung	Prüfungsform
LV 1
LV 2
LV 3
Gesamtmodul	Korrekte Bearbeitung der theoretischen Übungsaufgaben in Höhe von mindestens 60% der maximal erreichbaren Punkte, 5 Kurzvorträge über Lösungen von Übungsaufgaben	mündl. Prüfung oder Klausur
Wiederholungsprüfung

Regularien	Angebotsrhythmus	Anwesenheitspflicht	Gewicht an Modulnote in %
LV 1	Sommersemester	Nein	%
LV 2	Sommersemester	Nein	%
LV 3	Sommersemester	Nein	%