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 25. März 2019 von 12-14 Uhr. Es sind keine Hilfsmittel zugelassen.
Tutorium 3 von René-Maurice Hanne (montags 15:45-17:15 Uhr) findet am 26.11. einmalig nicht statt und wird auf Freitag, den 30.11. um 9:45-11:15 Uhr in SR 301 verschoben!

Tutorium 4 von Markus Himmel (dienstags 8:00-9:30 Uhr) wurde von SR -108 in SR -120 verlegt!

Tutorium 6 von Liran Dattner (dienstags 14:00-15:30 Uhr) wurde von SR -118 in SR -107 verlegt!

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
16.10. Vorlesung 18.10. Vorlesung Aufzeichnung
23.10. Vorlesung Aufzeichnung 25.10. Übung
30.10. Vorlesung Aufzeichnung 01.11.
06.11. Vorlesung Aufzeichnung 08.11. Übung
13.11. Vorlesung Aufzeichnung 15.11. Vorlesung Aufzeichnung
20.11. Übung 22.11. Vorlesung Aufzeichnung
27.11. Vorlesung Aufzeichnung 29.11. Übung
04.12. Vorlesung Aufzeichnung 06.12. Übung
11.12. Vorlesung 13.12. Vorlesung
18.12. Übung 20.12. Vorlesung
08.01. Vorlesung 10.01.
15.01. Übung 17.01. Vorlesung
22.01. Vorlesung 24.01. Übung
29.01. Vorlesung 31.01. Vorlesung
05.02. Übung 07.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 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.
  • Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach

(Veraltetes) Skript

Hier gibt es ein veraltetes Skript zur Vorlesung. Bitte beachten Sie, dass das Skript nicht mehr gepflegt wird.

Ü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 akzeptiert, das heißt, es müssen handschriftliche Lösungen abgegeben werden. Für abgeschriebene Lösungen gibt es auf das gesamte Übungsblatt keine Punkte. Wenn auf mehreren Übungsblättern abgeschrieben wird, werden keine Bonuspunkte vergeben.

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. Die erreichbare Punktzahl pro Übungsblatt ist nicht unbedingt jedes Mal genau dieselbe, obere Schranken auf die Gesamtpunktzahl werden hier im Laufe des Semsters angegeben.

Nur Bonuspunkte, die im WS 18/19 erworben wurden, werden auf die Klausur angerechnet. Bonuspunkte aus zurückliegenden Semestern werden nicht anerkannt. Ebenso gibt es keine Garantie, dass Bonuspunkte aus dem WS 18/19 in späteren TGI-Klausuren anerkannt werden. Studierende, die die Vorlesung bereits gehört, jedoch die Klausur noch nicht geschrieben haben und ihre alten Bonuspunkte nicht mehr anrechnen können, haben die Möglichkeit, sich im WS 18/19 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.

Beschriftung der Übungsblätter

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

Klausur und Klausurvorbereitung

Alte Klausuren