Formale Sprachen und Berechenbarkeit

Dozent:innen: apl. Prof. Dr. Luca Doria
Kurs-Nr.: 08.079.050
Kurstyp: Vorlesung/Übung

Voraussetzungen / Organisatorisches

Formale Sprachen und Berechenbarkeit

Inhalt:
Der Kurs führt in die abstrakte Berechenbarkeit und ihre Beziehung zu Sprachen und realen Computern ein.
Er ist ein grundlegendes Thema für die Informatik und Linguistik, da er verschiedene Formen der Berechnung
und Sprachen sowie deren intrinsische Fähigkeiten und Grenzen beschreibt. Verschiedene Berechnungsmodelle
(und die Sprachen, die sie verstehen können) werden anhand von Beispielen und Übungen (im Unterricht und in Übungsstunden)
untersucht.

Organisation:
Der Kurs ist unterteilt in Vorlesungen mit Tafel/Folien und Übungsstunden.

Empfohlene Literatur



Skript (Download-Link wird bereitgestellt)

Weitere Materialien, falls erforderlich (nicht zwingend):
- J. Hopcroft, R. Motwani, J. Ullman: Introduction to Automata Theory, Languages, And Computation
- M. Sipser: Introduction to the Theory of Computation

Inhalt

- Historische Einführung
- Abstrakte Vorstellung von Berechnung und ihre Beziehung zu Sprachen, Computern, Mathematik und Physik.
- Mathematische Werkzeuge
- Boolesche Schaltungen als Rechenwerkzeuge
- Reguläre Sprachen und endliche Automaten
- Kontextfreie Sprachen und Pushdown-Automaten
- Rekursiv aufzählbare Sprachen und Turing-Maschinen
- Berechenbarkeit und die (erweiterte) Church-Turing-These 
- Auf dem Weg zur Komplexitätstheorie
- Energiekosten der Berechnung und Quantum Turing-Maschinen (Einführung)
 

Zusätzliche Informationen

Qualifikationsziele/Lernergebnisse/Kompetenzen

Die Studierenden (Formale Sprachen und Berechenbarkeit)
• verfügen über ein Verständnis für die Grundlagenfragen der Informatik;
• kennen Automaten und formale Sprachen sowie deren Zusammenhänge;
• kennen Verfahren zur Beurteilung der Berechenbarkeit und Entscheidbarkeit;
• können mathematische Methoden zur Klärung von Grundlagenfragen der Informatik anwenden.
Vermittlung der theoretischen Grundlagen der Informatik, Beherrschung der formalen Konzepte

Termine

Datum (Wochentag) Zeit Ort
14.04.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
21.04.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
28.04.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
05.05.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
12.05.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
19.05.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
26.05.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
02.06.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
09.06.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
16.06.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
23.06.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
30.06.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut
07.07.2026 (Dienstag) 10:15 - 11:45 00 212 S 1
1534 - Hörsaalgebäude Sportinstitut