Anmelden

Modulbeschreibung

Skip Navigation LinksTHUDEModulbeschreibung

Theoretische Informatik

Inhalt

  • Grundbegriffe der Graphentheorie

  • Formale Sprachen

  • Deterministische und nichtdeterministische endliche Automaten

  • Reguläre Ausdrücke und reguläre Sprachen

  • Kontextfreie Grammatiken

  • Kellerautomaten

  • Effiziente Top-Down-Syntaxanalyse

  • Berechenbarkeit, Church'sche These

  • Unentscheidbare Probleme

  • Einführung in die Prädikatenlogik

Lernergebnisse

Nach erfolgreichem Abschluss des Moduls können die Studierenden

Fachkompetenz

  • grundlegende Begriffe aus der Graphentheorie, der Logik, den formalen Sprachen, der Automatentheorie und der Berechenbarkeitstheorie erklären

  • wichtige Beschreibungs-, Analyse- und Beweisverfahren aus dem Bereich der formalen Sprachen erläutern und anwenden

  • wesentliche Eigenschaften verschiedener Sprach- und Automatenklassen erläutern

  • prinzipielle Grenzen für die Berechenbarkeit und Entscheidbarkeit benennen

Methodenkompetenz

  • typische Problemklassen in Anwendungsproblemen erkennen und mit den behandelten Beschreibungsmethoden formalisieren, um sie einer systematischen Problemlösung zuzuführen

  • anhand formaler Beschreibungen Eigenschaften der beschriebenen Systeme nachweisen

ECTS

5 Punkte

Studien- und Prüfungsleistungen

Prüfungsleistungen:
  • Theoretische Informatik (90 min, Klausur)
Studienleistungen:
  • Theoretische Informatik (Hausarbeit)

Lehr- und Lernformen

  • Theoretische Informatik (3 SWS, Vorlesung)
  • Theoretische Informatik (1 SWS, Übung)

Studiengänge

  • Data Science in der Medizin(DSM) - Wahlpflichtmodul
  • Elektrotechnik und Informationstechnik(ET) - Wahlpflichtmodul
  • Computer Science International Bachelor(ICS) - Pflichtmodul
  • Informatik(INF) - Pflichtmodul

Modulverantwortliche

Prof. Dr.-Ing. Georg Schied

Dozenten

Prof. Dr.-Ing. Georg Schied

Literatur

Socher. Theoretische Grundlagen der Informatik. Hanser Verlag, 2007. ISBN 978-3446412606.
Hoffmann. Theoretische Informatik. Hanser Verlag, 2009. ISBN 978-3446415119.
Hopcorft, Motwani. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison- Wesley, 2002. ISBN 978-3827370204.
Sipser. Introduction to the Theory of Computation. Thomson, 2005. ISBN 978-0619217648.
Tittmann. Graphentheorie. Fachbuchverlag, Leipzig, 2003. ISBN 978-3446223431.
Aho, Lam, Sethi. Compiler. Pearson Studium, 2008. ISBN 978-3827370976.

Quicklinks