MENUMENU
MENUMENU

Theoretische Informatik und Mathematische Logik (DLBITIML01)

Kursnummer:

DLBITIML01

Kursname:

Theoretische Informatik und Mathematische Logik

Gesamtstunden:

150 h

ECTS Punkte:

5 ECTS

Kurstyp: Pflicht

Kursangebot: WS, SS

Course Duration: Minimaldauer 1 Semester

Zugangsvoraussetzungen:

Algorithmen, Datenstrukturen und Programmiersprachen (DLBIADPS)

Kurskoordinator(en) / Dozenten / Lektoren:

Siehe aktuelle Liste der Tutoren im Learning Management System

Bezüge zu anderen Modulen:

Siehe Modulbeschreibung

Beschreibung des Kurses:

Theoretische Informatik und mathematische Logik beschreiben die theoretischen Grundlagen des Faches Informatik. Dabei handelt es sich aber nicht um „reine Theorie“, sondern diese Grundlagen werden in vielen Teilbereichen der Informatik praktisch angewendet. Dazu gehören beispielsweise die Formulierung von Bedingungen in SQL-Abfragen oder anderen Programmen auf Basis von Aussagen- und Prädikatenlogik, die Nutzung endlicher Automaten zur Spezifikation von Systemen mit Zustandsübergangsdiagrammen, und die Modellierung von Geschäft- und anderen Prozessen mit Petri-Netzen. Darüber hinaus analysieren theoretische Informatik und mathematische Logik die Grenzen der Informatik und der Berechenbarkeit, die unabhängig von den verwendeten Technologien und Algorithmen nicht überschritten werden können.

Kursziele:

Nach erfolgreichem Abschluss des Kurses sind die Studierenden in der Lage,

  • aussagenlogische und prädikatenlogische Zusammenhänge zu formulieren und in Programmiersprachen zu übertragen.
  • endliche Automaten und reguläre Ausdrücke zur Beschreibung fachlicher Sachverhalte anzuwenden.
  • die Chomsky-Hierarchie zu erläutern.
  • Grenzen der Beweisbarkeit und der Berechenbarkeit zu benennen.
  • die Aussage und die Relevanz des P=NP-Problems zu erläutern.
  • Petri-Netze zur Beschreibung fachlicher Sachverhalte anzuwenden.

Lehrmethoden:

Die Lehrmaterialien enthalten Skripte, Video-Vorlesungen, Übungen, Podcasts, (Online-) Tutorien und Fallstudien. Sie sind so strukturiert, dass Studierende sie in freier Ortswahl und zeitlich unabhängig bearbeiten können.

Inhalte des Kurses:

1. Aussagenlogik

1.1 Grundbegriffe

1.2 Interpretation und Erfüllbarkeit

1.3 Normalformen

1.4 Indirekter Beweis und Resolution

1.5 Vollständigkeit

2. Prädikatenlogik

2.1 Grundbegriffe

2.2 Vollständigkeit und Unvollständigkeit

2.3 Logik-Programmierung mit Prolog

3. Endliche Automaten und reguläre Ausdrücke

3.1 Grundbegriffe der endlichen Automaten

3.2 Reguläre Ausdrücke

3.3 Praxisanwendungen

4. Formale Sprachen und Grammatiken

4.1 Grundbegriffe

4.2 Die Chomsky-Hierarchie

4.3 Reguläre Sprachen

4.4 Kontextfreie Sprachen

4.5 Kontextsensitive Sprachen

5. Berechenbarkeit und Turing-Maschinen

5.1 Modelle der Berechenbarkeit

5.2 Turing-Maschinen

5.3 Rekursive Funktionen

5.4 Berechenbarkeit und Entscheidbarkeit

5.5 Das Halteproblem

6. Komplexitätstheorie

6.1 Grundbegriffe

6.2 Komplexitätsklassen

6.3 P=NP?

7. Petri-Netze

7.1 Grundbegriffe von Graphen und Petri-Netzen

7.2 Invarianten, Lebendigkeit und Sicherheit

7.3 Prozessmodellierung und -analyse mit Petri-Netzen

8. Anwendungen der mathematischen Logik und der theoretischen Informatik

8.1 Parser und Compiler

8.2 Programmverifikation

8.3 Künstliche Intelligenz

Literatur:

  • Dewdney, A.K. (1995): Der Turing Omnibus. Eine Reise durch die Informatik mit 66 Stationen. Springer, Berlin Heidelberg New York.
  • Erk, K./Priese, L. (2008): Theoretische Informatik. 3. Auflage. Springer eXamen.press, Berlin Heidelberg.
  • Priese, L./Wimmerl, H. (2008): Petri-Netze. 2. Auflage. Springer eXamen.press, Berlin Heidelberg.
  • Schöning, U. (2000): Logik für Informatiker. 5. Auflage. Spektrum Verlag, Heidelberg Berlin.
  • Schöning, U. (2008): Ideen der Informatik. Grundlegende Modelle und Konzepte der Theoretischen Informatik, 3. Auflage. Oldenbourg, München.

Prüfungszugangsvoraussetzung:

  • Kursabhängig: Begleitende Online-Lernkontrolle (max. 15 Minuten je Lektion, bestanden / nicht bestanden)
  • Kursevaluation

Prüfungsleistung:

Klausur, 90 Min.

Zeitaufwand Studierende (in Std.): 150

Selbststudium (in Std.): 90
Selbstüberprüfung (in Std.): 30
Tutorien (in Std.): 30