Theoretische Grundlagen der Informatik

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Dr. Benjamin Niedermann , Dr. Franziska Wegner
• Termine: in der Regel
  • dienstags um 11.30-13.00 Uhr im Gerthsen-HS (30.21) und
  • donnerstags um 11.30-13.00 Uhr im Gerthsen-HS (30.21)
  • Vorlesungs- und Übungstermine sind unten im Terminplan angegeben.
• Klausur: Termine (Termin für Nachklausur wird rechtzeitig bekannt gegeben.)
• Forum: Link
• Vorlesungsaufzeichnung: YouTube Kanal oder iTunes U Kanal
• WebInScribe: Link

• Termine für die Einsicht stehen auf der Ergebnisliste.
• Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang (mit Matrikelnummer) im Foyer und vor unserem Sekretariat.

• Hier die Klausur zum Herunterladen: Klausur und Lösung

• Termine für die Einsicht stehen auf der Ergebnisliste.
• Die Ergebnisse sind da. Außerdem gibt es jeweils einen Aushang (mit Matrikelnummer) im Foyer und vor unserem Sekretariat.

• Hier die Klausur zum Herunterladen: Klausur und Lösung

• 02.04. Die Hörsaaleinteilung für die Hauptklausur ist nun online: Einteilung. Falls ihr euch für die Klausur angemeldet habt, bitte überprüft ob ihr auch in der Liste eingetragen seid. Falls ihr wider Erwarten nicht in der Liste eingetragen seid, dann schreibt bitte eine Mail an uns Übungsleiter.
• 27.02. Anmeldung zur Nachklausur: Die Anmeldung zur Nachklausur ist nun im Studierendenportal freigeschalten. Anmeldeschluss ist der 01.04.2015. Der Anmeldeschluss am 01.04.2015 gilt auch, wenn die Anmeldung nicht online über das Studierendenportal erfolgt (zum Beispiel für Schülerstudenten). Eine Anmeldung zur Nachklausur nach dem 01.04.2015 ist nicht mehr möglich.
• 16.02. Die Hörsaaleinteilung für die Hauptklausur ist nun online: Einteilung. Falls ihr euch für die Klausur angemeldet habt, bitte überprüft ob ihr auch in der Liste eingetragen seid. Falls ihr wider Erwarten nicht in der Liste eingetragen seid, dann schreibt bitte eine Mail an uns Übungsleiter.
• 12.02. Übgunsblatt 7: Durch die Updates der Aufgabe 1 des 7ten Übungsblatt kam es zu einigen Problemen mit Aufgabe 1. Wir haben uns deshalb dazu entschieden die Teilaufgaben e-f) aus der Bewertung zu nehmen. Dementsprechend liegt die Bestehensgrenze für den Klausurbonus nun bei 96 Punkten.
• 05.02. Übungsblatt 7: Es befindet sich ein Fehler im Übungsblatt 7 Aufgabe 1. Der Automat hatte einen falschen Übergang: Statt o, Z_1 → Z_0 Z_1 muss es heißen o, Z_1 → Z_1 Z_0. Das aktualisierte Übungsblatt befindet sich auf der Homepage.
• 26.01. Klausurbonus: Wer mindestens 99 Punkte auf den Übungsblättern erreicht hat, erhält den Klausurbonus.
• 19.01. Fehler in Übungsblatt 6: Die Aufgabenstellung von Aufgabe 6, Übungsblatt 6 hat einen kleinen Fehler. Die Grammatik ist nicht wie behauptet in Chomsky-Normalform. Die Aufgabenstellung ist nun korrigiert und das aktualisierte Übungsblatt ist online.
• 22.12. Anmeldung zur Hauptklausur: Die Anmeldung zur Hauptklausur ist nun im Studierendenportal freigeschalten. Anmeldeschluss ist der 13.02.15. Der Anmeldeschluss am 13.02.15 gilt auch, wenn die Anmeldung nicht online über das Studierendenportal erfolgt (zum Beispiel für Schülerstudenten). Eine Anmeldung zur Hauptklausur nach dem 13.02.15 ist nicht mehr möglich.
• 15.12. Dauerhafter Tutoriumsausfall: Studenten, die in das Tutorium von Tobias Stolzmann (Tutorium 18 und 20) gehen, werden gebeten sich für das restliche Semester ein anderes Tutorium zu suchen, da diese komplett wegen Krankheit ausfallen. Die Abgabe der Übungsblätter erfolgen jedoch weiterhin an das jeweilige Tutorium 18 oder 20. Die Übungsblätter können dann in etwa 2,5 Wochen nach der Abgabe bei uns abgeholt werden.
• 15.12. Tutanden von Jan Jacob (Tutorium 11) bringen bitte ihr erstes Übungsblatt noch einmal bei ihm vorbei bzw. melden sich bei ihm.
• 15.12. Tutorium von Jérôme Urhausen wird auf den 22.12. vorverlegt (Raum 301 und Uhrzeit 17.30 Uhr).

• 10.12. Temporärer Tutoriumsausfall: Studenten, die in das Tutorium von Tobias Stolzmann gehen, werden gebeten sich für die Tutorien am 11.12 ein anderes Tutorium zu suchen, da diese wegen Krankheit ausfallen.

• 25.11. Temporärer Tutoriumsausfall: Studenten, die in das Tutorium von Tobias Stolzmann gehen, werden gebeten sich für die Tutorien am 27.11 und 04.12 ein anderes Tutorium zu suchen, da diese wegen Krankheit ausfallen.

• 20.11.: Übungsblatt 1, Aufgabe 6d: Aufgabe 6d) ist leider nicht so eindeutig formuliert, wie wir es uns zuerst erhofft haben. Wir haben inzwischen auch die Tutoren darauf aufmerksam gemacht, dass die Aufgabe nicht eindeutig formuliert ist. Solltet ihr bei dieser Teilaufgabe Punkte für eure Interpretation von L4 abgezogen bekommen haben, obwohl ihr der Meinung seid, dass ihr sie richtig interpretiert habt, so geht bitte noch einmal zu eurem Tutor mit eurer Abgabe, damit er sich noch einmal diese Teilaufgabe anschauen kann.

• 11.11.: Temporäre Raumänderungen von Tutorien: Aufgrund einer Konferenz der Informatikfachschaften werden einige Tutorien im Zeitraum 12.11.14-14.11.14 in andere Räume verlegt. Die genauen Raumänderungen sind in der folgenden pdf-Datei aufgelistet: Raumänderungen

• 03.11.: Raumverlegung von Tutorium 21: Das Tutorium 21, gehalten von Stefan Rettenmayr, findet nun immer in Raum -107 (Informatik-Hauptgebäude 50.34) statt. Tag und Uhrzeit haben sich nicht geändert.

• 24.10.: Verlängerung der Bearbeitungszeit von Übungsblatt 1. Damit der Stoff, der in Übungsblatt 1 behandelt wird, in allen Tutorien besprochen werden kann, wurde die Abgabe des 1. Übungsblatts auf Montag, den 10. November verschoben. Das Übungsblatt wird in der zweiten Übung am 18. November besprochen. Der Ab- und Ausgabetag der Übungsblätter ist immer Montags.

• Ein Forum für Fragen und Diskussionen steht nun zur Verfügung.

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?

• 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
• TGI-Skript von Prof. Müller-Quade aus dem WS 13/14.
• Martin Werner: Information und Codierung, VIEWEG TEUBNER, 2008, ISBN 978-3-8348-0232-3.

Änderungen vorbehalten!

Hier gibt's das Skript zur Vorlesung.

Neue Übungsblätter werden voraussichtlich immer zweiwöchentlich dienstags auf die Homepage gestellt. Die Aufgaben sollen schriftlich bearbeitet und die handschriftlichen Lösungen in den mit „Theoretische Grundlagen der Informatik“ beschrifteten Einwurfschlitz im Keller des Informatik-Hauptgebäudes (50.34) eingeworfen werden. Es gilt 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.) Ausgedruckte oder kopierte Lösungsblätter werden NICHT akzeptieren, das heißt, es müssen handschriftliche Lösungen abgegeben werden. Für abgeschriebene Lösungen gibt es keine Punkte!!!
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.

Der WebInScribe-Server nimmt in der Zeit von Di. 21.10. 18:00 Uhr bis Do. 23.10. 18:00 Uhr Einträge entgegen. Zur Nutzung des Systems benötigt man einen studentischen Rechenzentrums-Account („uXXXX“). Wer (noch) keinen RZ-Account hat, kann unter webinscribe@ira.uka.de einen WebInScribe-Zugang erhalten. Weitere Informationen und Hinweise zur Nutzung von WebInScribe gibts als Merkblatt zum Download. WebInScribe

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:

Ein bestandener Übungsschein kann als Bonus auf die Haupt- oder Nachklausur angerechnet werden. Dies gilt jedoch nur für Übungsscheine, die im WS 14/15 erworben werden. Übungsscheine aus zurückliegenden Semestern werden nicht anerkannt. Ebenso gibt es keine Garantie, dass Übungsscheine aus dem WS 14/15 in späteren TGI-Klausuren anerkannt werden.
Studierende, die die Vorlesung bereits gehört, jedoch die Klausur noch nicht geschrieben haben und ihren alten Übungsschein nicht mehr anrechnen können, haben die Möglichkeit, sich im WS 14/15 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.