Theoretische Grundlagen der Informatik

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Guido Brückner, M.Sc., Dr. Marcel Radermacher
• 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)
  • Vorlesungs- und Übungstermine sind unten im Terminplan angegeben.
  • Die Nachklausur wird am 22.08.2017 stattfinden.
  • Klausuranmeldung ist geöffnet.
  • Vorzeitiges Abmelden von der Klausur ist bis 15.08.2017 online, im Sekretariat und bei den Übungsleitern und am 22.08.2017 direkt vor der Klausur möglich.

• Ilias-Forum
• Vorlesungs Aufzeichnung - Youtube
• Vorlesungs Aufzeichnung - iTunes
• Vorlesungs Aufzeichnung - DIVA

.

• Übung 7 und Vorlesungsfolien online. Folie 13 der Übung wurde korrigiert.
• Wer auf den Übungsblättern insgesamt mindestens 107 Punkte erreicht, bekommt den Klausurbonus.

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?

• 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
• TGI-Skript von Prof. Müller-Quade aus dem WS 13/14.
• Martin Werner: Information und Codierung, VIEWEG TEUBNER, 2008, ISBN 978-3-8348-0232-3.

Änderungen vorbehalten!

Hier gibt's das Skript zur Vorlesung.

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.

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

Falls Sie das Deckblatt nicht ausdrucken können, bitten wir Sie, die Blätter zusammenzuheften und das Deckblatt nach folgendem Muster zu beschriften:

Ein bestandener Übungsschein kann als Bonus auf die Haupt- oder Nachklausur angerechnet werden. Wer auf den Übungsblättern insgesamt mindestens 107 Punkte erreicht, bekommt den Klausurbonus. Dies gilt jedoch nur für Übungsscheine, die im WS 16/17 erworben werden. Übungsscheine aus zurückliegenden Semestern werden nicht anerkannt. Ebenso gibt es keine Garantie, dass Übungsscheine aus dem WS 16/17 in späteren TGI-Klausuren anerkannt werden.
Studierende, die die Vorlesung bereits gehört, jedoch die Klausur noch nicht geschrieben haben und ihren alten Übungsschein nicht mehr anrechnen können, haben die Möglichkeit, sich im WS 16/17 erneut für ein Tutorium einzutragen und die Übungsblätter erneut zu bearbeiten.