BIN303: Theoretische Informatik

Lernpfad Informatisches Denken und Konzepte

BIN303: Theoretische Informatik

Kurzporträt BIN303: Theoretische Informatik
Worum geht es? Das Modul fragt nach den formalen Grundlagen des Rechnens. Die Studierenden beschäftigen sich mit Automaten, formalen Sprachen, Grammatiken, Berechenbarkeit und Komplexität. Dabei geht es darum, Probleme präzise zu beschreiben und ihre Lösbarkeit oder ihren Aufwand fachlich zu begründen.
Wofür braucht man es? Theoretische Informatik hilft, Grenzen und Möglichkeiten algorithmischer Problemlösung zu verstehen. Die Kompetenzen sind wichtig für Compilerbau, Sprachverarbeitung, Verifikation, Sicherheitsfragen, Algorithmik und wissenschaftliche Argumentation. Sie schützen auch davor, für grundsätzlich unlösbare oder praktisch zu teure Probleme ungeeignete Lösungen zu erwarten.
Wieso ist es interessant? Das Modul zeigt, dass Informatik nicht nur aus Programmieren besteht, sondern auch aus Aussagen darüber, was überhaupt berechenbar ist. Manche einfache Fragen führen zu tiefen theoretischen Grenzen. Wer diese Grenzen versteht, kann technische Problemstellungen klarer einordnen und bessere Entscheidungen treffen.
Modulverantwortung

Prof. Dr. Christoph Dalitz

Lehrperson(en)
  • Prof. Dr. Christoph Dalitz
  • Prof. Dr. Jochen Rethmann
Verwendbarkeit

Bachelor Informatik

Fächergruppe

Informatik

Modultyp
Pflicht
Sprache

Deutsch

Angebot

Wintersemester

Dauer

1 Semester

Credits

5 ECTS

Benotung

Deutsche Notenskala 1-5

SWS

2 V | 2 Ü | - P | - S

Workload
Präsenzstudium: 45 Std. Selbststudium: 90 Std.
Engl. Titel

Theoretical Computer Science

Empfohlene Voraussetzungen
  • BIN301: Logik, Diskrete Strukturen und Lineare Algebra: Beweistechniken, Kombinatorik, Binärdarstellung, Logarithmen.
  • BIN302: Algorithmen und Datenstrukturen: einfache Algorithmen, Sortieren, Suchen, Laufzeiten.
Lernergebnisse / Kompetenzen
WAS

Mit erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage, grundlegende Fragen der Problemlösung mit Computern und von Sprachen formal zu beschreiben und dafür Lösungen zu entwickeln oder nachzuweisen, dass sie nicht lösbar oder vermutlich nicht effizient lösbar sind.

WOMIT

Die Studierenden erreichen dieses Lernergebnis, indem sie

  • die Einteilung von Problemen in Komplexitäts- und Berechenbarkeitsklassen erklären,
  • für ein nichtberechenbares Problem dessen Nichtberechenbarkeit beweisen,
  • Zugehörigkeiten zu einer Komplexitätsklasse beweisen,
  • Laufzeitanalysen für Entscheidungsprobleme durchführen,
  • einfache Probleme mit Automaten und formalen Sprachen modellieren,
  • die Kategorie einer formalen Sprache erkennen und nachweisen.
WOZU

Die Studierenden nutzen diese Kompetenzen, um IT-Systeme zu entwickeln, in denen Benutzereingaben oder maschinenlesbare Daten verarbeitet werden. Ferner vermeiden sie durch die erworbenen Kompetenzen sinnlose oder falsche Lösungen für nicht lösbare oder nicht effizient lösbare Probleme und können am wissenschaftlichen Diskurs über die Komplexität von Problemen teilnehmen.

Inhalte
  • Berechenbarkeit und Turingmaschinen
  • Komplexitätsklassen und die P != NP-Frage
  • Grammatiken und Chomsky-Hierarchie
  • Automatentheorie und ihr Bezug zu Grammatiken
Prüfungsvorleistung

Keine angegeben.

Prüfungsleistung

Klausurarbeit (90 Minuten).

Literatur
  • Michael Sipser: Introduction to the Theory of Computation. 3. Auflage, Cengage Learning, 2014.
  • Alexander Asteroth; Christel Baier: Theoretische Informatik: Einführung in Berechenbarkeit, Komplexität und formale Sprachen. Pearson Studium, 2019.
  • John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 3. Auflage, Pearson, 2007.