Institut für Theoretische Informatik, Algorithmik

Theoretische Grundlagen der Informatik

Allgemeines

Nachklausur

  • 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.

Hauptklausur

  • 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.

Aktuelles

  • 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.

Inhalt der theoretischen Informatik

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?

Literatur

  • 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
  • Martin Werner: Information und Codierung, VIEWEG TEUBNER, 2008, ISBN 978-3-8348-0232-3.

Vorlesungs-/Übungstermine

Dienstags Donnerstags
21.10. Vorlesung Folien 23.10. Vorlesung Folien
28.10. Vorlesung Folien 30.10. Vorlesung Folien
04.11. Übung 06.11. Vorlesung Folien
11.11. Vorlesung Folien 13.11. Vorlesung Folien
18.11. Übung 20.11. Vorlesung Folien
25.11. Vorlesung Folien 27.11. Übung
02.12. 04.12. Vorlesung Folien
09.12. Vorlesung Folien 11.12. Übung
16.12. Vorlesung Folien 18.12. Vorlesung Folien
23.12.
Weihnachtsferien
08.01. Übung
13.01. Vorlesung Folien 15.01. Vorlesung Folien
20.01. Übung 22.01. Vorlesung Folien
27.01. Vorlesung Folien 29.01. Übung
03.02. Vorlesung Folien 05.02. Vorlesung Folien
10.02. Vorlesung 12.02. Übung

Änderungen vorbehalten!

Skript

Hier gibt's das Skript zur Vorlesung.

Übung, Übungsblätter und Tutorien

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.

Übungsblatt Ausgabe Abgabe bis Besprechung
Blatt 121.10.1410.11.14, 11:00 Uhr 18.11.14
Blatt 2 10.11.1424.11.14, 11:00 Uhr27.11.14
Blatt 3 24.11.1401.12.14, 11:00 Uhr11.12.14
Blatt 4 01.12.1415.12.14, 11:00 Uhr08.01.15
Blatt 5 15.12.1412.01.15, 11:00 Uhr20.01.15
Blatt 612.01.1526.01.15, 11:00 Uhr29.01.15
Blatt 726.01.1509.02.15, 11:00 Uhr12.02.15

Tutorieneinteilung über WebInScribe

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

Beschriftung der Übungsblätter

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:

[Tacker] Theoretische Grundlagen der Informatik Tut.nr.
Übungsblatt n Name1, Vorname1 (Matrikelnummer1)
Name2, Vorname2 (Matrikelnummer2)

Klausurbonus

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.

Klausur und Klausurvorbereitung

Alte Klausuren (Informatik III, Haupt-/Nachklausur 10/11)