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

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

Originalfassung Englisch
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
  • 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
Modulveran­staltung Lehrveranstaltungs­form Veranstaltungs­titel SWS Workload Präsenz Workload Vor- / Nach­bereitung Workload selbstge­staltete Arbeit Workload Prüfung incl. Vorbereitung 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 Teilnahme­voraussetzungen Angebots­rhythmus Anwesenheits­pflicht Gewicht an Modulnote in %
LV 1 Sommersemester Nein %
LV 2 Sommersemester Nein %
LV 3 Sommersemester Nein %