Grundlagen der Theoretischen Informatik

Vorlesung

  • Viorica Sofronie-Stokkermans <sofronie@@uni-koblenz.de>
  • Sprechstunde: Mo, 16:00

  • Übung:

  • Dennis Peuter

  • Folien

    Übungszettel

    Newsgroup: infko.theoinf


    Aktuelles


    Scheinvergabe:

  • Es werden zwei Teilklausuren geschrieben

  • Schein bei 50% der insgesamt in den beiden Teilklausuren zu erzielenden Punkte
  • Wiederholung einzelner Teilklausuren nicht möglich
  • Nachklausur:

  • Termin: Montag, 7.10.2019, 13:00s.t.-15:00 (120 min), Raum D 028
  • Nachklausur hat gleichen "Wert" wie alle Teilklausuren zusammen; 120 Minuten Dauer
  • Schein bei 50% der Punkte in der Nachklausur

  • 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.


    @