Institut für Theoretische Informatik, Algorithmik

Theoretische Grundlagen der Informatik

Allgemeines

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
25.10. Vorlesung 27.10. Vorlesung
01.11. – (Allerheiligen) 03.10. Vorlesung
08.11. Übung 10.11. Vorlesung
15.11. Vorlesung 17.11. Übung
22.11. Vorlesung 24.11. Vorlesung
29.11. Übung 01.12. Vorlesung
06.12. Vorlesung 08.12. Übung
13.12. Vorlesung 15.12. Vorlesung
20.12. Übung 22.12. Vorlesung
10.01. Vorlesung 12.01. Vorlesung
17.01. Übung 19.01. Vorlesung
24.01. Vorlesung 26.01. Übung
31.01. Vorlesung 02.02. Vorlesung
07.02. Übung 09.02. Vorlesung
14.02. Vorlesung 16.02. Übung

Änderungen vorbehalten!

Literatur

  • Scott Aaronson, P =?= NP
  • 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
  • Juraj Hromkovic: Theoretical Computer Science, Springer-Verlag Berlin Heidelberg, 2011, ISBN 978-3-642-05729-8.

Veraltetes Skript

Bitte beachten Sie, dass dieses Skript nicht mehr gepflegt wird. Es kann Abweichungen zum aktuellen Stoff der TGI-Vorlesung geben.

Übung, Übungsblätter und Tutorien

Neue Übungsblätter werden voraussichtlich alle zwei Wochen veröffentlicht. Die Abgabe erfolgt online über die Übungsgruppen im ILIAS. Weitere Informationen zum Übungsbetrieb werden im ILIAS-Forum bekanntgegeben.

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 voraussichtlich 7 Übungsblätter mit jeweils ca. 30 Punkten geben. Die genauen Bonuspunktegrenzen werden hier im Laufe des Semesters bekanntgegeben.

Nur Bonuspunkte, die im WS 21/22 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 21/22 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 21/22 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.

Klausur und Klausurvorbereitung

Alte Klausuren

Klausur Lösung
2021/22 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2020/21 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2020/21 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2019/20 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2019/20 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2018/19 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2018/19 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2017/18 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2017/18 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2016/17 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2016/17 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2015/16 Hauptklausur Klausur mit Lösung
2015/16 Nachklausur Klausur mit Lösung
2014/15 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2014/15 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2011/12 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2011/12 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2010/11 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2010/11 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2007/08 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2007/08 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2004/05 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2004/05 Nachklausur Klausur ohne Lösung Klausur mit Lösung
2003/04 Hauptklausur Klausur ohne Lösung Klausur mit Lösung
2003/04 Nachklausur Klausur ohne Lösung Klausur mit Lösung