Theoretische Grundlagen der Informatik

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Dr. Torsten Ueckerdt, Guido Brückner, M.Sc.
• 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.
• ILIAS

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?

Änderungen vorbehalten!

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

Hier gibt's das Skript zur Vorlesung.

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.

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.

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

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