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
17.10. Vorlesung 19.10. Vorlesung
24.10. Vorlesung 26.10. Übung
02.11. Vorlesung
07.11. Vorlesung 09.11. Übung
14.11. Vorlesung 16.11. Vorlesung
21.11. Übung 23.11. Vorlesung
28.11. Vorlesung 30.11. Übung
05.12. Vorlesung 07.12. Vorlesung
12.12. Übung 14.12. Vorlesung
19.12. Vorlesung 21.12. Übung
09.01. Vorlesung 11.01. Vorlesung
16.01. Übung 18.01. Vorlesung
23.01. Vorlesung 25.01. Übung
30.01. Vorlesung 01.02. Vorlesung
06.02. Übung 08.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.

Skript

Hier gibt's das Skript zur Vorlesung.

Übung, Übungsblätter und Tutorien

Neue Übungsblätter werden voraussichtlich zu jeder Übung 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.

Übungsblätter Lösungsvorschläge
Übungsblatt 1

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 jedes Mal genau dieselbe, obere Schranken auf die Gesamtpunktzahl werden hier im Laufe des Semsters angegeben.

Beschriftung der Übungsblätter

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

Klausur und Klausurvorbereitung

Alte Klausuren (Informatik III, Haupt-/Nachklausur 10/11)

Klausur Lösung
2016/17 Hauptklausur 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