Institut für Theoretische Informatik, Algorithmik

Theoretische Grundlagen der Informatik

Allgemeines

  • 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), 14-täglich
  • Klausur: am 13. März 2018 von 14-16 Uhr. Es sind keine Hilfsmittel zugelassen.
  • Nachklausur: am 1. Oktober 2018 von 11-13 Uhr. Es sind keine Hilfsmittel zugelassen.
Die vorläufige Ergebnistabelle für die Nachklausur ist nun online. Die Einsicht findet am 18.10. von 15:45 bis 17:15 Uhr in Raum -107 in Gebäude 50.34 statt. Um die Wartezeiten bei der Klausureinsicht möglichst kurz zu halten, bitten wir Sie, sich an die folgende zeitliche Einteilung nach Hörsälen zu halten.
15:45-16:15 Fasanengarten
16:15-16:45 Benz
16:45-17:15 Daimler
Studenten mit einem “X” in der Spalte “Mündliche Prüfung” melden sich bitte umgehend im Sekretariat sekr [dash] wagner [at] ira [dot] uka [dot] de.

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?

Vorlesungs-/Übungstermine

Dienstags Donnerstags
17.10. Vorlesung 19.10. Vorlesung
24.10. Vorlesung 26.10. Übung
02.11. Vorlesung
07.11. Vorlesung 09.11. Übung
14.11. Vorlesung 16.11. Vorlesung
21.11. Übung 23.11. Vorlesung
28.11. Vorlesung 30.11. Übung
05.12. Vorlesung 07.12. Vorlesung
12.12. Übung 14.12. Vorlesung
19.12. Vorlesung 21.12. Übung
09.01. Vorlesung 11.01. Vorlesung
16.01. Übung 18.01. Vorlesung
23.01. Vorlesung 25.01. Übung
30.01. Vorlesung 01.02. Vorlesung
06.02. Übung 08.02. Vorlesung

Änderungen vorbehalten!

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 Intractability: 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.
  • Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach

Skript

Hier gibt's das Skript zur Vorlesung.

Übung, Übungsblätter und Tutorien

Neue Übungsblätter werden voraussichtlich alle zwei Wochen veröffentlicht. 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 im Tutorium besprochen.

Klausurbonus

Werden mindestens 25% (50%, 75%) der möglichen Gesamtpunktzahl auf allen Übungsblättern erreicht, werden auf die bestandene Klausur 1 (2, 3) Bonuspunkte angerechnet. Es wird 7 Übungsblätter mit jeweils ca. 30 Punkten geben. Die erreichbare Punktzahl pro Übungsblatt ist nicht unbedingt jedes Mal genau dieselbe! Die Bonuspunktegrenzen sind:

  • Bei insgesamt 52 Punkten oder mehr gibt es einen Bonuspunkt.
  • Bei insgesamt 105 Punkten oder mehr gibt es zwei Bonuspunkte.
  • Bei insgesamt 157 Punkten oder mehr gibt es drei Bonuspunkte.

Beschriftung der Übungsblätter

Bitte nutzen Sie den WebInScribe Deckblattgenerator, und heften Sie das Deckblatt an Ihre Abgabe.

Klausur und Klausurvorbereitung

Bitte bringen Sie unbedingt ein offizielles Ausweisdokument (Personalausweis, Reisepass, …) zur Klausur mit!

Hauptklausur

Die Hörsaaleinteilung ist nun online. Bitte überprüfen Sie unbedingt, ob Sie angemeldet sind.
Die vorläufige Ergebnistabelle ist nun online.

Nachklausur

Die Hörsaaleinteilung ist nun online. Bitte überprüfen Sie unbedingt, ob Sie angemeldet sind.

Bitte lernen Sie nicht nur mit den Altklausuren, sondern auch mit den Übungsblättern von diesem und letztem Jahr.

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