Modulcode:	infBL_B-01a
Englische Bezeichnung:	Computations and Logic - Computations Part
Modulverantwortliche(r):	Prof. Dr. Thomas Wilke
Turnus:	jedes Jahr im WS (WS23/24)
Präsenzzeiten:	2V 1Ü
ECTS:	4
Workload:	30 Std. Vorlesung, 15 Std. Präsenzübung, 75 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-A (BSc Inf (21))
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Das Modul beantwortet die drei folgenden, grundlegenden Fragen:

• Wie sieht ein einfaches, algorithmisch zugängliches Computermodell aus und wo sind dessen Grenzen?
• Was können Computer leisten und was nicht und wie verschaffen wir uns Gewissheit darüber?

Lernziele:

Abkürzungen

• SST = subsequential transducer
• DFA = deterministic finite-state automaton
• NFA = non-deterministic finite-state automaton
• TM = Turing machine

Die Lernziele gliedern sich in die folgenden grundlegenden Fragen der theoretischen Informatik:

Wie sieht ein einfaches, algorithmisch zugängliches Computermodell aus und wo sind dessen Grenzen?

Die Studierenden

• realisieren Funktionen als SSTs, beschreiben formale Sprachen durch DFAs und NFAs
• beschreiben die Semantik von SSTs mathematisch präzise und beweisen die Korrektheit einfacher SSTs
• erklären und wenden grundlegende Konstruktionen und Algorithmen für SSTs an (Produkt, Determinisierung, Minimierung)
• entwickeln eigene einfache Konstruktionen und Algorithmen für SSTs und beweisen deren Korrektheit
• beweisen durch Anwendung eines einfachen Kriteriums, dass Funktionen nicht durch SSTs berechnet werden können

Was können Computer leisten und was nicht und wie verschaffen wir uns Gewissheit darüber?

Die Studierenden

• realisieren Algorithmen als TMs
• beschreiben Berechnungen von TMs mathematisch präzise und beweisen die Korrektheit einfacher TMs
• erklären die Funktionsweise einer universellen TM
• bestimmen in einfachen Fällen, ob ein Problem entscheidbar, aufzählbar oder co-aufzählbar ist
• führen mathematisch präzise Unentscheidbarkeitsbeweise in einfachen Fällen durch

Lehrinhalte:

Wie sieht ein einfaches, algorithmisch zugängliches Computermodell aus und wo sind dessen Grenzen?

• Funktionen als Abstraktion des Ein-Ausgabe-Verhaltens von Computern
• subsequential transducer (SST) als einfaches Berechnungsmodell
• algorithmische Eigenschaften von SSTs
  
  • Wortproblem, Halteproblem, Leerheitsproblem, Universalitätsproblem entscheidbar
  • unter Komposition und weiteren Operationen abgeschlossen
• deterministischer endlicher Automat (DFA) als Spezialfall (zur Beschreibung des Definitionsbereichs)
• nicht-deterministischer endlicher Automat (NFA) als Spezialfall (zur Beschreibung des Wertebereichs)
• Determinisierung und Minimierung als Beispiele für komplizierte Algorithmen
• Cut-and-Paste-Techniken für endliche Zustandsräume

Was können Computer leisten und was nicht und wie verschaffen wir uns Gewissheit darüber?

• Turingmaschine als idealisiertes Modell eines Computers
• Berechnungen und berechnete Funktion als Semantik
• Church-Turing-These zur Veranschaulichung der Bedeutung des Modells
• Beispiele für komplizierte berechenbare Funktionen und nicht berechenbare Funktionen
• Kodierungen von TM als Möglichkeit, TM als Eingaben zu akzeptieren und zu verarbeiten
• Universelle TM, Analogie zum Interpreter
• Entscheidbarkeit einer Menge als Spezialfall der Berechenbarkeit
• Entscheidbarkeit, Aufzählbarkeit, Co-Aufzählbarkeit und Zusammenhänge
• Halteproblem als fundamentales Beispiel für Unentscheidbarkeit
• Reduktionen als Mittel zum Vergleich
• Weitere Beispiele für die genannten Klassen, mit und ohne Beweise

Weitere Voraussetzungen:

Prüfungsleistung:

Klausur, als Vorleistungen müssen Hausaufgaben (Übungsaufgaben) erfolgreich bearbeitet werden.

Lehr- und Lernmethoden:

Vorlesung, Arbeits- und Fragestunden, Selbststudium.

Verwendbarkeit:

Dieses Modul wird ist kein offizieller Bestandteil eine Prüfungsordnung. Es ist insbesondere für die Umsetzung von Übergangsregelungen zur FPO 2021, bzw. dem ab dem Sommersemester 2023 gelesenen Modul infBL-01a: Berechungen und Logik.

Außerdem wird das Modul im Rahmen der Anmeldung zur Teilnahme am Modul infBL-01a: Berechungen und Logik verwendet.

Literatur:

• Schöning, U. (1992). Theoretische Informatik-kurz gefasst. BI Wissenschaftsverlag.

Verweise:

Kommentar: