Theoretische Grundlagen der Informatik

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Dr. Reinhard Bauer, Dr. Andrea Kappes
• Vorlesung: wöchentlich dienstags 11:30-13:00 Uhr, 14-tägig donnerstags 11:30-13:00 im Gerthsen HS
• Übung: 14-tägig donnerstags 11:30-13:00 im Gerthsen HS
• Forum: Forum zur Vorlesung
• Klausur: Termine

• Es hat sich herausgestellt, dass das Modul TGI nicht richtig in der Selbstbedienungsfunktion für Studierende abgebildet ist. Dies hat zur Folge, dass das Modul bei manchen Studenten fälschlicherweise als nicht bestanden gekennzeichnet ist. Der Fehler wird bald behoben.

• Findet sich hier und hier.

• Mündliche Prüfungen finden am 11. Mai 2011 statt
• Für eine genaue Terminabsprache bitte baldmöglichst mit Dr. Reinhard Bauer in Verbindung setzen
• Anmeldeschluss: 29. April 2011

• Die Ergebnisse der Nachklausur finden sich hier und im Foyer des Informatik-Hauptgebäudes. Bitte beachten: Die hier veröffentlichten Ergebnisse sind vorläufig und ohne Gewähr. Relevant sind nur die Ergebnisse wie nach Klausureinsicht in die Selbstbedienungsfunktion für Studierende eingetragen.
• Am Ende der Datei ist der zugehörige Notenschlüssel zu finden

• Die Klausureinsichten für die Nachklausur finden Donnerstag, 21.04.2011 von 13.30 Uhr bis 15 Uhr in Raum -120 und Donnerstag, 28.04.2011 von 11.30 Uhr bis 13.00 Uhr in Raum 301 im Informatik-Hauptgebäude statt

• Um die Wartezeiten zu verkürzen bitten wir euch zu folgenden Zeiten zu kommen:

• Der Termin der Nachklausur findet sich hier.
• Die Klausuranmeldung ist in der Selbstbedienungsfunktion für Studierende freigeschaltet.
• Studierende der Informatik und der Informationswirtschaft melden sich direkt durch die Selbstbedienungsfunktion für Studierende an.
• Für Mathematik-Studenten mit Nebenfach Informatik gelten folgende Regeln:
  • Studenten des Bachelor/Master Studiengangs melden sich über die Selbstbedienungsfunktion an.
  • Diplom-Studenten benötigen eine Zulassung und melden sich direkt bei den Übungsleitern an.
• Falls Sie die Prüfung als Nebenfächler belegen, schreiben Sie bitte noch zusätzlich eine eMail mit Namen, Studiengang und Martikelnummer an Dr. Reinhard Bauer.
• Studierende anderer Studienrichtungen kontaktieren bitte einen Übungsleiter.
• Anmeldebeginn der Nachklausur ist der 07.03.2011.
• Anmeldeschluss der Nachklausur ist der 30.03.2011.
• Am 31.03.2011 wird auf dieser Homepage eine Teilnehmerliste veröffentlicht. Überprüfen Sie bitte, ob Sie auf dieser Liste stehen, da Sie sonst nicht an der Klausur teilnehmen können.
• Die Anmeldeliste mit Platz- und Raumzuteilung findet sich hier. Hinweise zum Klausurablauf gibt es hier.

• Die Ergebnisse der Hauptklausur finden sich hier.
• Klausur und zugehörige Musterlösung finden sich hier und hier

• Die Klausureinsichten für die Hauptklausur finden Montag, 28.02.2011 und Donnerstag, 03. 03.2011, jeweils 14-16 Uhr in Raum 301 im Informatik-Hauptgebäude statt
• Um die Wartezeiten zu verkürzen bitten wir euch zu folgenden Zeiten zu kommen:

Wir haben einige Anfragen bezüglich der für die Klausur relevanten Themen bekommen und jede Anfrage pauschal damit beantwortet, dass der gesamte in Vorlesung und Übung behandelte Stoff klausurrelevant ist. Dies bedeutet natürlich nicht, dass jedes Thema auch tatsächlich in der Klausur behandelt wird. Aus Platz- und Zeitgründen kann nicht der komplette Stoff abgeprüft werden. Das Vorlesungsskript beinhaltet mehr Erklärungen als die Vorlesungsfolien. Allerdings enthält es auch Themen, die in der Vorlesung nicht behandelt wurden. Klausurrelevant ist nur der in Vorlesung/Übung behandelte Stoff. Dies gilt insbesondere für das Skript von Prof. Müller-Quade. Uneindeutigkeiten zwischen Vorlesung und Übung oder Lehrbüchern versuchen wir in der Klausur zu vermeiden. Im Zweifelsfall gelten Definitionen immer wie in der Vorlesung eingeführt.

• Die Klausurbonusliste befindet sich hier
• Abmeldung von der Hauptklausur ist noch am 21. Februar bei den Übungsleitern, sowie am 22. Februar direkt vor der Klausur im entsprechenden Hörsaal möglich.
• Klausurablauf

• Die Anmeldelisten werden am Montag, 14.02.2011 auf der Homepage veröffentlicht und im Informatik-Hauptgebäude ausgehängt. (Hier stand früher Montag, der 08.02.2011. Bitte entschuldigt den Fehler.)
• Die Liste mit den erreichten Punkten der Übungsblätter wird am 17.02.2011 auf der Homepage veröffentlicht und im Informatik-Hauptgebäude ausgehängt
• Abmeldung von der Klausur ist möglich bei Dr. Reinhard Bauer, Dr. Andrea Kappes, Zimmer 307 im Informatik-Hauptgebäude sowie kurz vor Beginn der Klausur in den Hörsäälen.
• Klausureinsicht, Termin 1: Montag, 28. Februar 2011, Raum 301, Info-Bau
• Klausureinsicht, Termin 2: Donnerstag, 03. März 2011, Raum 301, Info-Bau
• Anmeldebeginn Nachklausur: Freitag, 04. März 2001.
• Die Anmeldeliste/Hörsaalverteilung findet sich hier.

• Der Termin der Nachklausur findet sich hier.
• Die Klausuranmeldung ist in der Selbstbedienungsfunktion für Studierende freigeschaltet.
• Studierende der Informatik und der Informationswirtschaft melden sich direkt durch die Selbstbedienungsfunktion für Studierende an.
• Für Mathematik-Studenten mit Nebenfach Informatik gelten folgende Regeln:
  • Studenten des Bachelor/Master Studiengangs melden sich über die Selbstbedienungsfunktion an.
  • Diplom-Studenten benötigen eine Zulassung und melden sich direkt bei den Übungsleitern an.
• Falls Sie die Prüfung als Nebenfächler belegen, schreiben Sie bitte noch zusätzlich eine eMail mit Namen, Studiengang und Martikelnummer an Dr. Reinhard Bauer.
• Studierende anderer Studienrichtungen kontaktieren bitte einen Übungsleiter.
• Anmeldeschluss ist der 04.02.2011.
• Am 08.02.2011 wird auf dieser Homepage eine Teilnehmerliste veröffentlicht. Überprüfen Sie bitte, ob Sie auf dieser Liste stehen, da Sie sonst nicht an der Klausur teilnehmen können.

28. Januar
Anmerkung zu Übungsblatt 6, Aufgabe 5c) : Hier ist es nicht nötig, genau das Verfahren aus dem Skript zu verwenden, es ist auch möglich, in geschickter Reihenfolge die Regeln (i) und (ii) zu benutzen, um die Grammatik direkt in Greibach-Normalform zu überführen.
27. Januar
In Übungsblatt 6, Aufgabe 2 wurde Grammatik G mit Grammatik G3 vertauscht. Die aktualisierte Version ist online.
25. Januar
Die Folien zum ICPC-Praktikum finden sich hier.
20. Januar
Die Folien mit den Informationen zum Proseminar: „Die P ≠ NP-Vermutung“ finden sich hier.
11. Januar
Alte Klausuren sind online.
20. Dezember
Vom 23.12. 2010 bis einschließlich 12.1. 2011 finden keine Tutorien statt. Die ersten Tutorien im neuen Jahr sind also am Donnerstag, den 13. Januar.
20. Dezember
In der Übung am 16. Dezember kam die Frage auf, ob bei der Integer Programming-Aufgabe die Bedingung Ex ≤1-Vektor nicht weggelassen werden kann, da das von Ax ≤ 1-Vektor abgedeckt ist (s. Übungsfolien). Das stimmt, falls die leere Menge nicht in S ist. Selbst wenn S_i die leere Menge ist, ist es aber in Ordnung, die Bedingung Ex ≤ 1-Vektor wegzulassen, das Integer Program bleibt korrekt. In dem Fall könnte zwar x_i eine beliebige natürliche Zahl sein, das ändert aber nichts an der Lösbarkeit.
14. Dezember
Der vorläufige Termin für die Nachklausur ist der 11. April 2011 um 14 Uhr. Sollte es gravierende Gründe dafür geben, dass dieser Termin nicht machbar ist (Kollision mit einer anderen Klausur), dann geben Sie uns bis spätestens Sonntag den 19. Dezember per Email an die Übungsleiter Bescheid.
19. November
Anmerkung zur Übung am 18. November: In der Übung wurde bei Teilaufgabe 6 a) nur eine Richtung gezeigt, die andere (leichte) Richtung ist mittlerweile auf den Übungsfolien ergänzt worden.
18. November
Anmerkung: Die Übung am 18.11.2010 findet erst um 12:30 - 14:00 Uhr statt! Wir bitten die sehr kurzfristige Änderung zu entschuldigen!
9. November
Anmerkung zur Übung am 4. November: In der Übung wurde die Frage gestellt, ob die vorkommenden Automaten epsilon-loops (also epsilon-Übergange von einem Zustand in sich selbst) enthalten. Nach Definition des NEA müssen NEAs nicht zwingend solche Übergänge enthalten, können aber.
5. November:
Anmerkung zum 2. Übungsblatt: Auf der ersten Version des Übungsblattes war bei Aufgabe 1 die Zustandsmenge mit {A, B, C, D} angegeben, gemeint ist natürlich die Zustandsmenge {A, B, C, D, E, F, G}. Der Abschnitt zu Turing-Maschinen mit mehreren Bändern aus dem Skript ist recht kurz. Eine nähere Erläuterung zu k-Band-Turing-Maschinen findet sich hier und auf der aktualisierten Version des Übungsblattes.
4. November:
Der Klausurtermin für die Hauptklausur steht fest, siehe Seiten der Fakultät!
28. Oktober:
Das erste Übungsblatt ist ab jetzt auf der Homepage abrufbar. Abgabe ist am 4.November.
26. Oktober:
Wegen Upgrade war das Forum eine Zeitlang nicht erreichbar. Mittlerweile sollte wieder alles funktionieren.

Im Gegensatz zu anderen Grundstudiumsvorlesungen werden in der theoretischen Informatik Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d. h. Fragen, die unabhängig von „Programmierungsaspekten“ oder „konkreten Rechnern“ sind: Gibt es Aufgaben, die von einem Rechner — unabhängig von der Art der Programmierung beziehungsweise von physikalischen und elektronischen Beschränkungen — nicht gelöst werden können? Welche Aufgaben können prinzipiell effizient (in vernünftiger Rechenzeit, mit vernünftigem Speicherplatzbedarf) gelöst werden?

Deterministische und nicht-deterministische endliche Automaten, Sprachen, Turing-Maschinen, Berechenbarkeit, Church'sche These, P und NP, NP-vollständige Probleme, Grammatiken, Chomsky-Hierarchie …

Folgende Fehler in den Folien sind bekannt, aber noch nicht korrigiert:

• In Kapitel 4 - Teil 1, Folie 131/133, Informell ausgedrückt. Hier soll stehen: Pi gehört zu NP, falls Pi folgende Eigenschaft hat: Ist die Antwort bei Eingabe eines Beispiel I von Pi ja, dann kann die Korrektheit eines Beweises (Zeugen) dafür in polynomieller Zeit überprüft werden.
• Kapitel 5, Folien 71/239 und 72/239 . Hier hat sich ein Fehler im Rechenbeispiel eingeschlichen.

Änderungen vorbehalten!

Skript (vorläufig)

Neue Übungsblätter werden voraussichtlich immer zweiwöchentlich donnerstags auf die Homepage gestellt. Die Aufgaben sollen schriftlich bearbeitet und bis Donnerstag zwei Wochen nach Ausgabe, 11 Uhr, in den mit „Theoretische Grundlagen der Informatik“ beschrifteten Einwurfschlitz im Keller des Informatik-Hauptgebäudes (50.34) eingeworfen werden. Zusätzlich ist noch die Abgabe im Hörsaal bis zu Beginn der Übung möglich. Ausnahme: Das erste Übungsblatt hat weniger Aufgaben und muss bereits nach einer Woche abgegeben werden. Im Zweifelsfall gilt immer der Abgabetermin, der direkt auf dem Übungsblatt steht. Die Bearbeitung und Abgabe der Aufgaben kann dabei in Zweiergruppen erfolgen! (Wichtig: Dazu ist bitte darauf zu achten, dass beide Studenten im selben Tutorium sind.) Wichtig ist auch, dass wir keine ausgedruckten oder kopierten Blätter akzeptieren, das heißt, die Blätter müssen handschriftlich abgegeben werden. Die Aufgaben werden von den Tutoren korrigiert und in den Tutorien der Folgewochen zurückgegeben. Die Lösungen zu den Übungsblättern werden in der Übung besprochen.

Um den Übungsleitern und Tutoren das Leben etwas zu erleichtern und um zu verhindern, dass Teile der Ausarbeitung an der falschen Adresse landen oder verlorengehen, bitten wir Euch, die Blätter zusammenzuheften und das Deckblatt nach folgendem Muster zu beschriften:

• Der schweigsame König, der gerne Schweinebraten aß
• Der verfressene König
• Wikipedia zum Erfüllbarkeitsproblem (SAT)
• Wikipedia zu Stephen Cook
• Wikipedia zu Graphenfärbung
• Folien zu Graphenfärbung und Sudoku
• Folien zu Map-Labeling
• Artikel zu Map Labeling aus der Zeit
• Artikel zu Map Labeling im bulletin
• TGI-Skript Müller-Quade

• Ingo Wegener, Theoretische Informatik, B.G. Teubner Verlag Stuttgart, 1993
• Uwe Schöning, Theoretische Informatik - kurzgefasst, Hochschultaschenbuch, Spektrum Akademischer Verlag, 1997
• R. Garey und D. S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, The MIT press, 1997, 2001.
• Alexander Asteroth, Christel Baier, Theoretische Informatik: eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen, Pearson Studium, 2002, ISBN 3-8273-7033-7≤