Grundlagen der Theoretischen Informatik


Vorlesung

Konferenzsystem Big Blue Button (BBB) unter OLAT
  • Viorica Sofronie-Stokkermans <sofronie@@uni-koblenz.de>
  • Sprechstunde: Mo, 16:00

  • Übung:

  • Dennis Peuter, Kevin Weirauch

  • Folien

    Übungszettel

    Diskussionsforum: OLAT


    Aktuelles


    Inhalt

    Die Vorlesung vermittelt die grundlegenden formalen Konzepten der Informatik und
    Verständnis für die prinzipiellen Grenzen des Berechenbaren
    bzgl. prinzipieller Unlösbarkeit oder unhandhabbarer Komplexität.
  • Reguläre Sprachen, endliche Automaten (determiniert und indeterminiert)
  • Kontextfreie Sprachen, indeterminierte Push-Down-Automaten
  • Kontextsensitive Sprachen, indeterminierte linear beschränkte Automaten
  • Rekursiv aufzählbare Sprachen, determinierte und indeterminierte Turing-Maschinen
  • Unentscheidbarkeit des Halteproblems und verwandter Probleme
  • Komplexität und NP-Vollständigkeit des SAT-Problems und verwandter Probleme

  • Literatur

    Katrin Erk, und Lutz Priese (2008).
    Theoretische Informatik: Eine umfassende Einführung.
    3. Auflage.
    Springer-Verlag.

    J. Hopcroft, R. Motwani, and J. Ullman (2002).
    Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
    Pearson.

    U. Schöning (1994).
    Theoretische Informatik: kurzgefasst.
    Spektrum-Verlag.