Theoretische Informatik 1+2 (SoSe 2025)

Aktuelles

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 10:15 - 12:00 Uhr im Magnus-Hörsaal (Informatikgebäude)

Donnerstag 12:15 - 14:00 Uhr in H8 (Hörsaaltrakt Bockenheim)

Übungsbetrieb

Conrad Schecker (schecker@em.uni-frankfurt.de)

Donnerstag 14:15 - 16:00 Uhr in SR 11 (Informatikgebäude)

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch selbstständiges Lösen der Übungsaufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch die erfolgreiche Teilnahme am Übungsbetrieb 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 und im Tutorium mindestens einmal pro Vorlesungsteil vorgerechnet wurde.

• Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
• Die Abgabefrist für ein Übungsblatt endet am Samstag in der darauffolgenden Woche um 12:00 Uhr.
• Die Abgabe erfolgt online über einen individuellen Link, den Sie nach erfolgter Anmeldung erhalten haben.
• Die Zuordnung der Abgaben erfolgt automatisch. Dennoch schadet es nicht, Namen oder Matrikelnummer darauf zu vermerken.
• Wir nehmen Abgaben in Form von einer PDF-Datei mit maximal 10MB entgegen. Schwer lesbare Abgaben werden nicht bewertet.
  • Gut lesbare und kleine Dateien erhält man bei der Verwendung von LaTeX. Wir bieten auch eine LaTeX-Vorlage an.
  • Alternativ können Sie auch Scans oder Bilder zu einer PDF-Datei 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.
• Laden Sie Ihre Lösung nicht in letzter Minute hoch. Ein reibungsloser Ablauf kann ansonsten nicht garantiert werden.
• Vergewissern Sie sich, die korrekte Datei hochgeladen zu haben.

Plagiate und KI-Tools

Es wird empfohlen, in Gruppen über die Aufgaben zu diskutieren, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Zur Lösung der Aufgaben ist es nicht nötig, externe Quellen zu verwenden, sofern nicht anders angegeben. Sollten dennoch Quellen verwendet werden, die nicht von uns bereitgestellt wurden, sind diese nach den Regeln der guten wissenschaftlichen Praxis anzugeben. Insbesondere ist die Eigenleistung eindeutig zu kennzeichnen, denn nur diese wird bewertet. Die Verwendung von KI-Tools ist untersagt. Abgaben, die plagiierte, kopierte oder nicht selbstständig erarbeitete Lösungen enthalten, werden für jeden Betroffenen mit 0 Punkten bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Aktive Beteiligung am Tutorium

Eine Bonifikation für die Prüfung wird nur bei aktiver Beteiligung am Tutorium gewährt, daher muss für jeden Vorlesungsteil mindestens einmal vorgerechnet werden. Darüber hinaus können Bonuspunkte durch freiwilliges Vorrechnen gesammelt werden. Dieser Bonus wird pro Person höchstens einmal pro Übungsblatt vergeben. Beim ersten freiwilligen Vorrechnen gibt es 3 Bonuspunkte und beim zweiten freiwilligen Vorrechnen gibt es 2 Bonuspunkte. Danach gibt es für jedes weitere freiwillige Vorrechnen einen Bonuspunkt.

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 befassen uns am Ende des zweiten Teils 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 Software in verschiedensten Bereichen der Informatik, vom Compilerbau bis hin zu Text-Algorithmen.

Die Veranstaltung besteht aus zwei Teilen.

Theoretische Informatik 1 (THI1):

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

Theoretische Informatik 2 (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

• G. Schnitger: Skript zur Vorlesung: Theoretische Informatik 2
• M. Sipser: Introduction to the Theory of Computation
• Christopher Moore, Stephan Mertens: The Nature of Computation, Kapitel 7 und 8, S. 351–449, Oxford University Press, 2011

Eher zu THI1:

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

Eher zu THI2:

• S. Arora und B. Barak: Computational Complexity, a modern approach
• J. Gallier und J. Quaintance: Proofs, Computability, Undecidability, Complexity, And the Lambda Calculus. An Introduction. Webseite von Jean Gallier

Teilnahmevoraussetzungen

• Bachelor (PO2019): 25CP aus den Basismodulen.
• Master (PO2019): keine.

Empfohlene Voraussetzungen für Bachelorstudierende: Basisveranstaltungen Diskrete Modellierung und Algorithmen und Datenstrukturen 1.

Leistungsnachweis

Je nach Teilnehmerzahl eine 180-minütige Klausur (90-minütig, falls entweder nur THI1 oder nur THI2 geprüft wird) oder mündliche Prüfungen.

Materialien

Skript

Die Veranstaltung orientiert sich am Skript von Herrn Prof. Dr. Georg Schnitger.

Handschriftliches Skript

Theoretische Informatik 1 (THI1):

• Woche 1

Theoretische Informatik 2 (THI2):

Folien

Theoretische Informatik 1 (THI1):

• Einführung

Theoretische Informatik 2 (THI2):

Übungen

Theoretische Informatik 1 (THI1):

• Übungsblatt 1. Abgabe bis 03.05.2025, 12:00 Uhr.

Theoretische Informatik 2 (THI2):

LaTeX

• LaTeX-Vorlage
• LaTeX-Cheat-Sheet

Prüfungsvorbereitung

Weiteres Material folgt.