Institut für Theoretische Informatik, Algorithmik

Theoretische Grundlagen der Informatik

Allgemeines

  • Übungsleitung: Laura Merker, Jonas Sauer
  • Termine: zunächst
    • mittwochs um 8:00-9:30 Uhr im Carl-Benz-HS (10.21) und
    • donnerstags um 12:00-13:30 Uhr im Fritz-Haller-HS (HS 37, 20.40)
  • Hauptklausur: am 6. April 2022 von 8:00-10:00 Uhr
In der Vorlesung und Übung wird ab sofort jedes Mal eine 2G-Kontrolle über die KONKIT-Box erfolgen, die bisher schon zur Kontaktnachverfolgung genutzt wurde. Laden Sie dazu bitte Ihren Impf- oder Genesennachweis auf Ihre KIT-Card [1]. Registrieren Sie sich wie üblich mit der KIT-Card an der KONKIT-Box. Wenn Ihr Nachweis gültig ist, wird die Box blau aufleuchten. Bitte beachten Sie, dass wir ausschließlich 2G-Nachweise über die KONKIT-Box akzeptieren. Nachweise per App oder auf Papier nehmen wir nicht entgegen.

Da wir die Registrierung kontrollieren müssen, bitten wir Sie, pünktlich zu erscheinen. Betreten Sie den Hörsaal frühestens 20 Minuten vor Vorlesungsbeginn (also 7:40 bzw. 11:40). Ab Beginn der Vorlesung können wir Sie nicht mehr hereinlassen.

[1] https://www.kon.kit.edu/3g-kontrolle.php

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

Mittwochs Donnerstags
20.10. Vorlesung 21.10. Vorlesung
27.10. Vorlesung 28.10. Übung
03.11. Vorlesung 04.11. Vorlesung
10.11. Übung 11.11. Vorlesung
17.11. Vorlesung 18.11. Vorlesung
24.11. Übung 25.11. Vorlesung
01.12. Übung 02.12. Vorlesung
08.12. Vorlesung 09.12. Übung
15.12. Vorlesung 16.12. Vorlesung
22.12. Übung 23.12. Vorlesung
12.01. Vorlesung 13.01. Vorlesung
19.01. Übung 20.01. Vorlesung
26.01. 27.01. Übung
02.02. Vorlesung 03.02. Vorlesung
09.02. Übung 10.02. Vorlesung

Ä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 befinden sich im ILIAS-Forum.

Übungsblätter Lösungsvorschläge
Übungsblatt 1 Lösungsvorschlag
Übungsblatt 2 (Update 8.11.) Lösungsvorschlag (Update 25.11.)
Übungsblatt 3 (Update 23.11.) Lösungsvorschlag
Übungsblatt 4

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