Grundlagen der Theoretischen Informatik

Vorlesung

Mittwoch, 14:00s.t.-16:00, Raum M001
Donnerstags, 14:00s.t.-16:00, Raum M001
  • Viorica Sofronie-Stokkermans <sofronie@uni-koblenz.de>
  • Sprechstunde: Mo, 16:00

  • Übung:

  • Dennis Peuter

  • Folien

    Übungszettel

    Newsgroup: infko.theoinf


    Aktuelles

  • Die Vorlesung am Mittwoch, den 20.06.2018 findet nicht statt.
  • Die Vorlesung am Donnerstag, den 21.06.2018 findet statt.

  • 1. Teilklausur: Freitag, 8.06.2018, 14:30-15:30, D-028

  • Die Vorlesung am Mittwoch, den 6.06.2018 findet im Raum D 239 statt (Question/Answer Session vor der 1. Teilklausur)

    Scheinvergabe:

  • Es werden zwei Teilklausuren geschrieben

    • 1. Teilklausur: Freitag, 8.06.2018, 14:30-15:30, D028
    • Anmeldung zur 1. Teilklausur ist bis zum 4.06.2018, 20:00 Uhr über MeToo möglich.
    • Ab 5.06.2018 Abmeldung per e-mail an sofronie@uni-koblenz.de
    • Themen für die 1. Teilklausur: [themen-tk1.pdf] (aktualisiert am 17.05.2018)
    • 2. Teilklausur: Montag, 6.08.2018, 13:00-14:00, D028
    • Anmeldung bis 29.07.2018 möglich (über KLIPS)
    • Rücktritt bis 30.07.2018 möglich (über KLIPS)
    • Themen für die 2. Teilklausur [themen-tk2.pdf]
    • Question/Answer Session: Freitag, 03.08.2018, 14:00s.t. Raum B 016

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

  • Termin: Freitag, 19.10.2018, 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.