Theoretische Informatik 1+2 (SoSe 2021)

ACHTUNG!!! Das Modul “Theoretische Informatik 1 (THI1)” mit 5 CP aus dem Masterstudiengang Informatik entspricht NICHT dem Modul “Theoretische Informatik 1 (B-GL1)” aus dem Bachelorstudiengang Informatik PO 2011, daher nicht dem Modul BaM-AFI-2.

Das Modul B-GL1 des B.Sc. Informatik PO 2011 wurde im WS 2019/20 zum letzten Mal angeboten.

Dieses Semester findet die Kommunikation mehr denn je über diese Webseite und E-Mails statt.
Bitte schauen Sie regelmäßig hier vorbei, und verwenden Sie Ihre studentische E-Mail-Adresse (…@stud.uni-frankfurt.de), wenn Sie uns E-Mails schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen.

Aktuelles

Der KLAUSURTERMIN wird höchstwahrscheinlich der Dienstag 27. Juli sein. Wir warten auf Bestätigung des Termins von der Uni-Verwaltung. Erst dann wird auch die Uhrzeit feststehen. Eine Altklausur ist erreichbar auf der Webseite der Altklausuren. Wir raten davon ab, beim Lernen ausschließlich (oder gar nicht) auf die Übungsaufgaben zu fokussieren.

Übung 4 ist online (Abgabe am 17.5., aktualisiert am 11.05.): LaTeX-Codeschnipsel mit den Aufgabenstellungen.

Die Fragestunde am 13.5. fällt wegen Feiertag aus. Die nächste Fragestunde findet am Donnerstag 20.5. um 13:00 Uhr statt. Das Tutorium mit Conrad Schecker wird auf den 14.5. um 15:00 Uhr (s.t.) verschoben.

Den Zugang zum digitalen Klassenraum finden Sie im Moodle


Vorlesung

Die Vorlesungen und Übungen werden in elektronischer Form stattfinden.

  • Die Vorlesungen werden von StudiumDigitale aufgezeichnet und online gestellt (sie werden nicht “live gestreamt”).

  • Eine Fragerunde (maximal 60 Min.) zu der Vorlesung findet jeden Donnerstag um 13:00 Uhr in Form eines Video-Meetings statt. Bitte beachten Sie, dass manche kleine Fragen aus dem Stoff erst während der Fragerunde im Detail diskutiert werden. Die Fragerunde wird aufgezeichnet, und später an der gleichen Adresse in BigBlueButton (unten) abrufbar.
  • Anschließend, um 14:15, findet ebenfalls dort die Übung statt.
    Den Zugang zu diesen Meetings finden Sie unter Moodle.
  • Bitte melden Sie sich für die Teilnahme an den Übungen per E-Mail bei Mario Holldack an. Geben Sie dabei Ihren (vollständigen) Namen und Ihre Matrikelnummer an. Geben Sie auch Ihre studentische E-Mail-Adresse an, falls Sie für die Anmeldung eine andere E-Mail-Adresse verwenden.
    Nur wer zu den Übungen angemeldet ist, wird seine/ihre Übungsblätter abgeben können.
    Mit Vorrechnen in den Übungen können Übungspunkte erworben werden (siehe unten).
    Die Teilnahme an den Übungen wird sehr empfohlen! Eine Plusnote zur Klausur kann erworben werden (siehe unten).

  • Für manche Inhalte dieser Seite benötigen Sie Zugangsdaten. Diese erhalten Sie über Moodle.
    Sollten Sie noch keinen HRZ-Account haben, melden Sie sich bitte bei Mario Holldack.
  • Hier können Sie sich mit dem digitalen Klassenraum vertraut machen.

Teilnahmevoraussetzungen:

  • Im Master: keine.

  • Im Bachelor PO-2019: 25 CP aus den Basismodulen. Diejenigen, die das Modul B-GeA-1 früher belegt hatten, dürfen nur noch B-GeA-12, (oder B-GeA-2) belegen.

  • Im Bachelor PO-2011: das Modul Diskrete Modellierung (B-MOD). Im Bachelor PO11 enfällt die 8CP Variante, es gibt aber die Möglichkeit die 5 CP (APX1) oder 10 CP Variante (APX12) zu belegen.

ACHTUNG!!! Das Modul “Theoretische Informatik 1 (THI1)” mit 5 CP aus dem Masterstudiengang Informatik entspricht NICHT dem Modul “Theoretische Informatik 1 (B-GL1)” aus dem Bachelorstudiengang Informatik PO 2011, daher nicht dem Modul BaM-AFI-2.

Den Zugangslink zum virtuellen Ingo-Wegener-Lernzentrum finden Sie auf OLAT.

Dr. Annamaria Kovacs

Donnerstag 13:00 - 14:00

Übungsbetrieb

Mario Holldack, Conrad Schecker

Donnerstag 14:00 - 16:00

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden wurde.

Es besteht die Möglichkeit, durch Vorrechnen in den Tutorien Bonuspunkte zu erwerben, welche zu den erworbenen Übungspunkten hinzuaddiert werden. Dabei gelten die folgenden Regeln:

  • Pro Übungsblatt wird der Bonus höchstens einmal pro Person vergeben.
  • Beim ersten Vorrechnen gibt es 5 Bonuspunkte.
  • Beim zweiten Vorrechnen gibt es 4 Bonuspunkte.
  • Beim dritten Vorrechnen gibt es 3 Bonuspunkte.
  • Beim vierten Vorrechnen gibt es 2 Bonuspunkte.
  • Jedes weitere Vorrechnen gibt 1 Bonuspunkt.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Hinweise zu den Übungsabgaben

  • Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
  • Die Abgabefrist für ein Blatt endet jeweils 10 Tage später, am Montag um 12:00 Uhr.
  • Da es eine Online-Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.

Zu Online-Abgabe:

  • Die Abgabe wird Ihnen automatisch zugeordnet; bitte vermerken Sie trotzdem Ihren Namen und Ihre Matrikelnummer darauf.
  • Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
  • Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
    • Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
    • Zur Not können Sie Scans oder Bilder zu einer PDF zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.

Inhalt

Die Veranstaltung befasst sich mit abstrakten Rechnermodellen und Fragen der Berechenbarkeit; kurz: Was (welche Sprache) ist mit Maschinen überhaupt berechenbar, und welche Fähigkeiten braucht eine Maschine theoretisch, um eine gegebene Sprache zu berechnen. Wir fangen mit den einfachsten Sprachen und Maschinen (reguläre Sprachen und endliche Automaten) an, und schliessen im THI2 mit algorithmisch unentscheidbaren Fragen der Prädikatenlogik. Neben der Bedeutung von Automaten und Formalen Sprachen für die theoretische Informatik, bieten die betrachteten Maschinen und Grammatiken Modellierungsmöglichkeiten für Hardware- und Softwareteilen in verschiedensten Bereichen der Informatik, vom Compilerbau, bis hin zu Text Algorithmen.

THI1

  • endliche Automaten (Deterministisch, Nichtdeterministisch, Zweiwege-Automaten, Probabilistische Automaten), reguläre Sprachen
  • Kontextfreie Grammatiken, Kellerautomaten
  • Entscheidungsprobleme für kontextfreie Grammatiken

THI2

  • Speicherplatzkomplexität (Sublogarithmisch, Logarithmisch, NL-Vollständigkeit, PSPACE-Vollständigkeit, Chomsky-Hierarchie)
  • Schaltkreise und Parallelisierbarkeit
  • P-Vollständigkeit
  • Prädikatenlogik, (un-)Entscheidbarkeit, Gödelscher Unvollständigkeitssatz

Literatur

Eher zum Teil 1:

  • U. Schöning: Theoretische Informatik - kurzgefasst
  • J.E. Hopcroft, J.D. Ullman, R. Motwani: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
  • J. Shallit, A second course in Formal Languages and Automata Theory
  • I. Wegener, Theoretische Informatik

Eher zum Teil 2:

  • Sanjeev Arora und Boaz Barak: Computational Complexity, a modern approach

Leistungsnachweise

Klausur (90 Min für 5 CP; 180 Min für 10 CP) oder mündliche Prüfung.

Materialien

Skript

  • Es steht das Skript von Herrn Prof. Dr. Georg Schnitger zum Download bereit, an dem sich diese Veranstaltung orientiert.

Videoaufzeichnungen

Videos zur Vorlesung stehen hier zur Verfügung.
Hinweis: Die Videos befinden sich auf Mediasite, der Videomanagement-Plattform der Goethe-Universität. Der Login erfolgt über den HRZ-Account.

Wie kann man im Vorlesungsvideo zeitliche Sprünge machen? indem man unten rechts auf das Icon klickt, und das Video im neuen Pop-Up Fenster schaut. In diesem lässt es sich hin-und-her springen.

Handschriftliches Skript

Theoretische Informatik 1

Theoretische Informatik 2

Folien

Theoretische Informatik 1

Übungen

Theoretische Informatik 1

Theoretische Informatik 2

LaTeX

Nützliches

Klausuren und Prüfungsmaterial

Anlaufstellen und Telefonnummern für Unterstützung in psychosozial schwierigen Situationen wie etwa Prüfungen:

  • Offene Sprechstunde der psychosozialen Beratung der Goethe-Universität,
    www.studentenwerkfrankfurt.de/beratung-service/psychosozialberatung
    wegen Corona zurzeit nur telefonisch: Dienstag und Donnerstag 15-17 Uhr unter 069-798-34922

  • Telefonseelsorge, www.telefonseelsorge.de
    rund um die Uhr unter 0800-111-0-111 oder 0800-111-0-222

  • Psychosozialer Krisendienst Frankfurt, www.bsf-frankfurt.de/krisendienst
    9 Uhr bis 1 Uhr nachts durchgängig unter 069-611375

Diese Nummern sind auch zu finden auf der Webseite des Gleichstellungsrates des FB 12:
www.uni-frankfurt.de/43691360/Gleichstellungsrat