Theoretische Grundlagen der Informatik

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Dr. Andrea Kappes , Dr. Tanja Hartmann
  ab 10.02.2012 ist Andrea Schumm nicht in Karlsruhe, Anfragen bitte an Tanja Hartmann
• Vorlesung: 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)
• Übung: in der Regel vierzehntägig donnerstags im Wechsel mit der Vorlesung
• Sondertermine:
  • Di. 15. November 2011: Übung ausnahmsweise dienstags
  • Do. 17. November 2011: Veranstaltung zeitlich verschoben auf 12.15 - 13.45 Uhr
    (wegen Überschneidung mit Uni für Einsteiger)
  • Do. 15. Dezember 2011: Vorlesung fällt aus
  • Do. 09. Februar 2012: Wunschübung zum Abschluss (siehe Aktuelles)
• Klausur: 22. Februar 2012 (Hauptklausur) um 14:00 Uhr, 12. April 2012 (Nachklausur) um 08:00 Uhr. Die Anmeldung zur Hauptklausur ist vom 18.01.2012 bis zum 08.02.2012 möglich. Für den Übungsschein ist keine Anmeldung erforderlich.
  

Die Anmeldung zur Nachklausur ist vom 14.03.2012 bis zum 03.04.2012 möglich. Für den Übungsschein ist keine Anmeldung erforderlich.

• Mündliche Nachprüfungen: 29. Mai 2012 ab 9.00 Uhr
  

Die Anmeldung zur Mündliche Nachprüfung muss bis zum 21. Mai im Sekretariat, Raum 321 (Frau Beckert/Frau Sauer) erfolgen.

• Forum: Forum zur Vorlesung
• Übersicht der Übungstermine:
  Do. 3.11., Di. 15.11., Do. 24.11., Do. 8.12., Do. 22.12., Do. 19.1., Do. 2.2.

3. Mai
Bekanngabe des Termins für die mündlichen Nachprüfungen. Die mündlichen Nachprüfungen finden am 29. Mai 2012 ab 9.00 Uhr statt. Anmeldung bis zum 21. Mai im Sekretariat, Raum 321.
19. April
Die Klausurergebnisse der Nachklausur gibts hier.
10. April
Die Anmeldelisten mit Raum sind nun verfügbar. Alle, die auf der vorigen Liste vom 07. April stehen, sollten nun in dieser Liste ihren Platz finden. Falls nicht, meldet Euch bitte schnellstmöglich!
07. April
ACHTUNG Die Anmeldungslisten zur zweiten Klausur am 12. April gibts hier. Bitte prüft ob Ihr richtig angemeldet seid! Wer nicht auf dieser Liste steht kann nicht mitschreiben! Die Hörsaalverteilung wird noch bekannt gegeben.
29. März
Eintragung der Noten ist abgeschlossen. Alle Noten der Hauptklausur sollten nun im Studienportal zu sehen sein. Bitte prüft, ob Eure Note richtig eingetragen wurde! Diejenigen, die die Nachklausur mitschreiben möchten, haben noch bis Dienstag, den 03. April 2012 Zeit, sich anzumelden! Eine erneute Anmeldung ist auch nötig, wenn Ihr die Hauptklausur mitgeschrieben habt und durchgefallen seid!
15. März
Aktualisierung der Info zur Klausureinsicht (jetzt mit Raum), siehe Klausurergebnisliste.
14. März
Die Anmeldung zur Nachklausur ist ab sofort bis zum 03. April 2012 möglich!
Die Klausurergebnisse der Hauptklausur gibts hier (jetzt auch sortiert!).
21. Februar
Hinweise zum Klausurablauf gibts hier.
20. Februar
Korrektur in Lösung zu Aufgabe 4 in Übung 4!!! Siehe Abschnitt zu Übungen.
16. Februar
ACHTUNG Die Anmeldungslisten zur ersten Klausur am 22. Februar gibts hier. Bitte prüft ob Ihr richtig angemeldet seid! Wer nicht auf dieser Liste steht kann nicht mitschreiben! Daimler-HS entspricht HMO, Benz-HS entspricht HMU.
14. Februar
Die Liste derer, die den Übungsschein bestanden haben gibts hier.
09. Februar
Uhrzeiten für Klausurtermine stehen fest (siehe oben). Räume werden noch bekannt gegeben.
09. Februar
ACHTUNG!!! Betrifft alle, die heute in der Übung waren: Kleine aber wichtige Änderung in Pumpinglemma-Folien!! Aktuell bereits in den Folien geändert!
06. Februar
Da ein Punkt auf dem 7. Übungsblatt aus der Bewertung herausgenommen wurde, haben wir die Bestehensgrenze für den Klausurbonus auf 90 Punkte gesenkt.
06. Februar
Am Donnerstag (09.02.2012) findet eine abschließende Wunschübung statt. Fragen und Vorschläge zu Themen, die hier wiederholt werden sollen, können per Mail (tanja.hartmann(at)kit.edu) eingereicht werden.
24. Januar
Bitte entschuldigt das erhöhte Spamaufkommen im Forum in den letzten Tagen. Das Forum ist inzwischen bereinigt.
Eintrag zur Definition der Chomsky-Hierarchie im Forum.
16. Januar
Die Anmeldung zur Hauptklausur ist vom 18.01.2012 bis zum 08.02.2012 möglich. Für den Übungsschein ist keine Anmeldung erforderlich.
9. Januar
Tutorium von Stefan Altmayer am 6.2. findet ausnahmsweise in Seminarraum -120 (Informatik-Hauptgebäude statt.
13. Dezember
Nachtrag zur 4. Übung, siehe Abschnitt zur Übung.
6. Dezember
Die Vorlesung am Donnerstag, den 15. Dezember sowie die Tutorien am Freitag, den 23. Dezember fallen aus! Studenten in Freitagstutorien können stattdessen die Tutorien am 22.12., 9.1. oder 10.1. besuchen (gleicher Stoff). Termine dazu siehe Webinscribe-Homepage
24. November
Bitte bezüglich Beschriftung der Übungsblätter!!! Details siehe Abschnitt zu Übungsblättern.
14. November
Erinnerung: Die Vorlesung am 17. November ist erst um 12.15 Uhr!
11. November
Achtung! Fehler auf 3. Übungsblatt, siehe Abschnitt zu Übungsblättern.
7. November
Rechenfehler bei Aufgabe 3 auf den Folien zu Blatt 1 korrigiert (ändert nichts am Ergebnis).
3. November
Das zweite Übungsblatt ist online, Abgabe ist am 10.November.
20. Oktober
Das erste Übungsblatt ist online, Abgabe ist am 3.November.

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≤

Hier gibt's das Skript zur Vorlesung.

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 zweite Ü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.) Ausgedruckte oder kopierte Lösungsblätter werden NICHT akzeptieren, das heißt, die Blätter müssen handschriftlich 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.

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:

Nochmalige Bitte!!! Bitte schreibt die Nummer des Tutoriums, dem Ihr per WebInScribe zugeteilt wurdet, groß und deutlich unterscheidbar von der Nummer des Übungsblattes auf die erste Seite Eurer Abgabe. Die jeweilige Nummer zum Namen Eures Tutors findet Ihr hier.
Vielen Dank für Eure Mitarbeit!

Die Liste derer, die den Übungsschein bestanden haben gibts hier.

Der WebInScribe-Server nimmt in der Zeit von Di. 18.10. 18:00 Uhr bis Do. 20.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. Das Ergebnis der Einteilung kann ab Freitag 21.10. ca. 12:00 Uhr hier eingesehen werden. Weitere Informationen und Hinweise zur Nutzung von WebInScribe gibts als Merkblatt zum Download.

Ein bestandener Übungsschein kann als Bonus auf die Haupt- oder Nachklausur angerechnet werden. Dies gilt jedoch nur für Übungsscheine, die im WS 11/12 erworben werden. Übungsscheine aus zurückliegenden Semestern werden nicht anerkannt. Ebenso gibt es keine Garantie, dass Übungsscheine aus dem WS 11/12 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 11/12 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.

Änderungen vorbehalten!

Vorlesungsfolien kapitelweise:

Endliche Automaten und reguläre Ausdrücke
Turing-Maschine, Berechenbarkeit
Komplexitätsklassen-Teil 1
Komplexitätsklassen-Teil 2

Fehler in den Vorlesungsfolien, die bekannt, aber noch nicht korrigiert sind:

1. Beim Foliensatz „Komplexitätsklassen-Teil 2“ sind bei der Problemdefinition von Integer Programming die Variablen x_1,.., x_n aus Z, eigentlich sollen diese aber aus N_0 sein. Die Version im Skript sowie die Folien zur Vorlesung am 13.12. sind dagegen korrekt.