====== Theoretische Grundlagen der Informatik ====== ===== Allgemeines ===== **Dozent**: Marvin Künnemann **Übungsleitung**: Geri Gokaj, Julian Stieß **Termine (21.10. bis 15.02.)**: * **dienstags** von **11:30 - 13:00** im Christian-Gerthsen-Hörsaal (30.21) * **donnerstags** von **11:30 - 13:00** im Christian-Gerthsen-Hörsaal (30.21) Den zugehörigen ILIAS-Kurs finden Sie [[https://ilias.studium.kit.edu/goto.php?target=crs_2480166&client_id=produktiv|hier.]] ===== 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? ===== Tutorien ===== Die Tutorien finden wöchentlich beginnend mit dem 28.10. statt. Für die Anmeldung nutzen wir den SignMeUp-Service des KIT, der Anmeldezeitraum läuft von **Dienstag, 22.10.2024 18:00 Uhr** bis **Donnerstag, 24.10.2024 18:00 Uhr**. Genauere Informationen finden Sie unter [[https://www.informatik.kit.edu/tutorieneinteilung/|https://www.informatik.kit.edu/tutorieneinteilung/]] Alles weitere für den Übungsbetrieb wird über den ILIAS-Kurs organisiert. ===== Vorlesungs-/Übungstermine ===== //Änderungen sind vorbehalten// ^ Dienstags ^ ^ Donnerstags ^ ^ | **22.10** | Vorlesung | **24.10** | Vorlesung | | **29.10** | Vorlesung | **31.10** | Übung | | **05.11** | Vorlesung | **07.11** | Vorlesung | | **12.11** | Übung | **14.11** | Vorlesung | | **19.11** | Vorlesung | **21.11** | Übung | | **26.11** | Vorlesung | **28.11** | Vorlesung | | **03.12** | Übung | **05.12** | Vorlesung | | **10.12** | Vorlesung | **12.12** | Übung | | **17.12** | Vorlesung | **19.12** | Weihnachts-Vorlesung | | **24.12** | //Winterferien// | **26.12** | //Winterferien// | | **31.12** | //Winterferien// | **02.01** | //Winterferien// | | **07.01** | Übung | **09.01** | Vorlesung | | **14.01** | Vorlesung | **16.01** | Übung | | **21.01** | Vorlesung | **23.01** | Vorlesung | | **28.01** | Übung | **30.01** | Vorlesung | | **04.02** | Vorlesung | **06.02** | Übung | | **11.02** | Vorlesung | **13.02** | Vorlesung | ===== Literatur ===== * Scott Aaronson, [[https://www.scottaaronson.com/papers/pnp.pdf|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: [[https://link.springer.com/book/10.1007%2F978-3-8348-9550-9|Information und Codierung]], VIEWEG TEUBNER, 2008, ISBN 978-3-8348-0232-3. * Sanjeev Arora und Boaz Barak: [[http://theory.cs.princeton.edu/complexity/book.pdf|Computational Complexity: A Modern Approach]] * Juraj Hromkovic: Theoretical Computer Science, Springer-Verlag Berlin Heidelberg, 2011, ISBN 978-3-642-05729-8. ==== Veraltetes Skript ==== * [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_skript_ws11.pdf|Veraltetes TGI Skript (WS11/12]] 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-Kurs bekanntgegeben. === Klausurbonus === **Nur Bonuspunkte, die im WS 24/25 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 24/25 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 24/25 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten. ==== Klausur und Klausurvorbereitung ==== Hier finden Sie eine Sammlung alte Klausuren, die Sie für Ihre Klausurvorbereitung nutzen können. ^ ^ Klausur ^ Lösung ^ | 2023/24 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2023/tgi/klausur1-ws2324_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2023/tgi/klausur1-ws2324_mit_lsg.pdf|Klausur mit Lösung]] | | 2022/23 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2022/tgi/klausur2ws2223_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2022/tgi/klausur2ws2223_mit_lsg.pdf|Klausur mit Lösung]] | | 2022/23 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2022/tgi/klausur1ws2223_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2022/tgi/klausur1ws2223.pdf|Klausur mit Lösung]] | | 2021/22 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2021/tgi/klausur2ws2122_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2021/tgi/klausur2ws2122_mit_lsg.pdf|Klausur mit Lösung]] | | 2021/22 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2021/tgi/klausur1ws2122_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2021/tgi/klausur1ws2122.pdf|Klausur mit Lösung]] | | 2020/21 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2020/tgi/klausur2ws2021_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2020/tgi/klausur2ws2021.pdf|Klausur mit Lösung]] | | 2020/21 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2020/tgi/klausur1ws2021_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2020/tgi/klausur1ws2021.pdf|Klausur mit Lösung]] | | 2019/20 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2019/tgi/klausur2ws1920_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2019/tgi/klausur2ws1920.pdf|Klausur mit Lösung]] | | 2019/20 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2019/tgi/klausur1ws1920_ohne_lsg.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2019/tgi/klausur1ws1920.pdf|Klausur mit Lösung]] | | 2018/19 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2018/tgi/klausur2ws1819_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2018/tgi/klausur2ws1819.pdf|Klausur mit Lösung]] | | 2018/19 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2018/tgi/klausur1ws1819_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2018/tgi/klausur1ws1819.pdf|Klausur mit Lösung]] | | 2017/18 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur2ws1718_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur2ws1718.pdf|Klausur mit Lösung]] | | 2017/18 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur1ws1718_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur1ws1718.pdf|Klausur mit Lösung]] | | 2016/17 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur2ws1617_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur2ws1617.pdf|Klausur mit Lösung]] | | 2016/17 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2017/tgi/klausur1ws1617_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2016/klausur1ws1617.pdf|Klausur mit Lösung]] | | 2015/16 Hauptklausur | | [[http://algo2.iti.kit.edu/documents/tgi-2015/TGI_WS1516_Hauptklausur_Loesung.pdf|Klausur mit Lösung]] | | 2015/16 Nachklausur | | [[http://algo2.iti.kit.edu/documents/Loesungsvorschlag%20Theoretische%20Grundlagen%20Informatik%2019082016.pdf|Klausur mit Lösung]] | | 2014/15 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2016/klausur1ws1415.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2016/loesung1ws1415.pdf|Klausur mit Lösung]] | | 2014/15 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2016/klausur2ws1415.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2016/loesung2ws1415.pdf|Klausur mit Lösung]] | | 2011/12 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_hauptklausur_1112.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_hauptklausur_1112_muloe.pdf|Klausur mit Lösung]] | | 2011/12 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_nachklausur_1112.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi_nachklausur_1112_muloe.pdf|Klausur mit Lösung]] | | 2010/11 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/hauptklausur2011.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/musterloesunghauptklausur2011.pdf|Klausur mit Lösung]] | | 2010/11 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi1011_nachklausur.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2011/tgi/tgi1011_nachklausur_mit_loesung.pdf|Klausur mit Lösung]] | | 2007/08 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/infoiii_ws0708_klausur1_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/infoiii_ws0708_klausur1_mit_loesung.pdf|Klausur mit Lösung]] | | 2007/08 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/infoiii_ws0708_klausur2_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/infoiii_ws0708_klausur2_mit_loesung.pdf|Klausur mit Lösung]] | | 2004/05 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/info3_ws0405_klausur1_ohne_loesung.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/info3_ws0405_klausur1_mit_loesung.pdf|Klausur mit Lösung]] | | 2004/05 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur2_0405.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur2_0405_loesung.pdf|Klausur mit Lösung]] | | 2003/04 Hauptklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur1_0304.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur1_0304_loesung.pdf|Klausur mit Lösung]] | | 2003/04 Nachklausur | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur2_0304.pdf|Klausur ohne Lösung]] | [[https://i11www.iti.kit.edu/_media/teaching/winter2010/tgi/klausur2_0304_loesung.pdf|Klausur mit Lösung]] |