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.

Theoretische Informatik 1+2 (WiSe 2023)

Aktuelles

Die Klausurthemen sind online.

Die Klausur findet am Di. 5.3.2024 im Magnus Hörsaal um 9:00 Uhr statt. Die Klausuranmeldung ist ab sofort möglich. Bitte dabei den Modulnamen beachten.

Statt Zweitklausur werden wahrscheinlich mündliche Prüfungen stattfinden (ausser wenn hohes Interesse an einer zweiten Klausur bestehen wird).

Die Bonusnoten sind online.

Bitte nicht nur aus den Vorlesungsfolien lernen! Neben dem handschriftlichen und Schnitger Skript, wird dringend empfohlen, in den entsprechenden Buchkapiteln nachzulesen! Insbesondere enthalten Moore-Mertens, Schöning, Wegener, Arora-Barak kostbare Texte.

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 10:00 - 12:00 in SR11
Donnerstag 12:00 - 14:00 in SR11

Übungsbetrieb

Dr. Hung Tran

Donnerstag 14:00 - 16:00 in SR 11

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 und in der Übung mindestens einmal vorgerechnet wurde.

Sie werden Ihre Lösungen nur als PDF über SAP abgeben können. Das PDF darf handschriftliche Lösungen enthalten, aber Sie können insgesamt nur eine Datei einreichen.

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:

Eher zum Teil 2:

  • Sanjeev Arora und Boaz Barak: Computational Complexity, a modern approach
  • Lecture Notes von Prof. Roland Meyer, TU Braunschweig Complexity
  • Jean Gallier und Jocelyn Quaintance: Proofs, Computability, Undecidability, Complexity, And the Lambda Calculus. An Introduction. (online)

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.

Handschriftliches Skript

Theoretische Informatik 1

Woche 1

Woche 2

Woche 3

Woche 4

Woche 5

Woche 6

Woche 7

Woche 8.1

Theoretische Informatik 2

Woche 8.2

Woche 9

Woche 10

Woche 11

Woche 12

Woche 13

Woche 14

Woche 15

Folien

Theoretische Informatik 1

Einführung

Minimierung

Reguläre Sprachen

Kontextfreie Sprachen

Theoretische Informatik 2

Parsing Quelle 1 Quelle 2

Speicherkomplexität

Parallelisierbarkeit

Logik

Übungen

Stylefiles zum Kompilieren der Tex-Dateien.

Theoretische Informatik 1

Übungsblatt 1 TEX Datei

Übungsblatt 2 TEX Datei

Übungsblatt 3 TEX Datei

Übungsblatt 4 TEX Datei

Übungsblatt 5 TEX Datei

Übungsblatt 6 TEX Datei

Übungsblatt 7 TEX Datei

Theoretische Informatik 2

Übungsblatt 8 TEX Datei

Übungsblatt 9 TEX Datei

Übungsblatt 10 TEX Datei

Übungsblatt 11 TEX Datei

Übungsblatt 12 TEX Datei

Übungsblatt 13 TEX Datei

LaTeX

Nützliches

Klausuren und Prüfungsmaterial