Grundlagen der Theoretischen Informatik



Klausuren SoSe 2020:


Informationen zur Klausur am Montag, den 12.10.2020

Informationen zu Präsenzprüfungen unter COVID-19 Beschränkungen Zum Ablauf der Klausur Es sind keine Hilfsmittel erlaubt. Am Platz erlaubt sind:
  • Etwas zu trinken
  • Etwas zu essen
  • Schreibgeräte (dokumentenecht, also beispielsweise keine Bleistifte und keine Frixion-Stifte)
  • Studierendenausweis.
  • Insbesondere sind wir angehalten darauf hinzuweisen, dass Mobiltelefone / Smartphones und Smartwatches etc. sowohl ausgeschaltet als auch außerhalb Ihrer Reichweite, d.h. nicht mit am Platz, sein sollen. Wenn Sie keinen Rucksack / keine Tasche dabei haben, um diese Geräte abzulegen, verwahren wir sie für die Dauer der Klausur.

    Finden wir etwas am Platz, was nicht freigegeben ist, werten wir das als Täuschungsversuch, mit allen entsprechenden Konsequenzen.

    Weitere Anmerkungen


    Virtuelle Treffen (Folien; Termin + Konferenzsystem; Datum Updates)

    Allgemeine Details zur Organisation der Vorlesung sind unter Aktuelles zu finden.


    Bitte um Feedback: 26.05.2020 - 7.06.2020

    Wir bitten Sie um eine kurze Rückmeldung zur Umsetzung dieser Veranstaltung.
    Die Rückmeldung erfolgt anonym, die Ergebnisse können nur von den Dozenten
    eingesehen werden.

    Feedback "Grundlagen der theoretischen Informatik"

    Um Ihre Stimme abgeben zu können müssen Sie zur
    Olat Gruppe "Grundlagen der theoretischen Informatik" angemeldet sein.


    Vorlesung

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

  • Übung:

  • Dennis Peuter

  • Folien

    Übungszettel

    Newsgroup: infko.theoinf


    Aktuelles


    Scheinvergabe:

  • Klausur: Montag, 3.08.2020
  • D 028: 16:00-18:00
  • Question/Answer Session: Donnerstag, 16.07.2020, in der Vorlesung
  • Anmeldung: KLIPS
  • Themen: themen-gti.pdf
  • Nachklausur:

  • Termin: Montag, 12.10.2020, 12:00s.t.-14:00 (120 min), Raum D 028

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


    @