Informatik III

• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Martin Holzer, Dipl.-Math. Steffen Mecke, Frank Schulz, Dipl.-Math. Silke Wagner
• Vorlesung: wöchentlich mittwochs 11:30-13:00 Uhr und freitags 11:30-13:00 im HS am Forum
• Übung: wöchentlich donnerstags 11:30-13:00 im HS am Forum
• Newsgroup: uka.info3

Im Gegensatz zu anderen Grundstudiumsvorlesungen werden hier Themen behandelt, die weiter von den Anwendungen entfernt sind. Es geht um prinzipielle Fragestellungen, d.h. Fragen, die zum Beispiel 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?

Deterministische und nicht deterministische endliche Automaten, Turing-Maschinen, Berechenbarkeit, Church'sche These, Sprachen, P und NP, NP-vollständige Probleme, Grammatiken, Chomsky-Hierarchie …

Die Newsgroup uka.info3 dient der Diskussion von inhaltlichen und organisatorischen Fragen zur Vorlesung, Übung und den Tutorien in Informatik III an der Universität Karlsruhe im Wintersemester 03/04. Wir begrüßen es, wenn Studenten ihre Probleme in der Newsgroup untereinander lösen. Zur technischen Verwendung des Newsservers der Universität siehe http://news.rz.uni-karlsruhe.de.

• Skript
• zum Pumping-Lemma (PDF)
• zum Äquivalenzklassenautomaten (PDF)
• Musteraufgaben zur Klausurvorbereitung… (PDF)
• … und deren Lösungen (PDF)
• Musterklausur… (PDF)
• … Lösungen zur Musterklausur (PDF)
• 1. Klausur mit Lösungen (PDF)
• 2. Klausur mit Lösungen (PDF)

Vorlesung und große Übung können Lehrmaterial nur präsentieren. Tutorien machen es verständlicher und helfen bei individuellen Problemen. Aber allein die Übungsblätter zwingen zur tatsächlichen Auseinandersetzung mit dem Material. Sie zeigen Euch und uns, was verstanden wurde, und wo Lücken bestehen.

Wir raten dringend, die Übungsblätter selbstständig und kontinuierlich zu bearbeiten. Fremde Lösungen als die Eigenen auszugeben ist nicht nur unehrlich. Durch Abschreiben schadet Ihr allein Euch selbst - spätestens in der Klausur müsst Ihr selbstständig arbeiten.

Die im Folgenden gegebenen Informationen können sich noch im Detail ändern, beabsichtigt ist jedoch Folgendes:

Jedes Übungsblatt hat zwei Sorten von Aufgaben. Rechnerübungen wird es nicht geben. Der erste Teil beschäftigt sich überwiegend mit dem Stoff der Vorlesung in der Woche der Ausgabe. Diese Aufgaben werden eine Woche später in der großen Übung am Donnerstag besprochen.

Der zweite Teil befasst sich überwiegend mit dem Stoff der Vorwoche. Diese Aufgaben sollten eine Woche nach der Ausgabe, am Donnerstag bis 14 Uhr in den mit 'Informatik III' beschrifteten Einwurfschlitz im Keller des Informatikgebäudes eingeworfen werden. Die Blätter sind zusammenzuheften, oben rechts mit der Nummer des Tutoriums zu versehen und sollten außerdem Namen und dem Namen der Vorlesung ('Informatik III') enthalten. Das ganze sollte etwa so aussehen:

Sie werden dann von den Tutoren korrigiert und in den Tutorien der Folgewoche zurückgegeben und besprochen. Die Abgabe kann und soll in Zweiergruppen erfolgen. Beide Teammitglieder sollten dann in einem Tutorium sein.

Die bearbeiteten Aufgaben werden mit Punkten bewertet. Für jedes Übungsblatt können etwa gleich viele Punkte erreicht werden. Wer am Ende des Semesters mindestens 50% der Punkte erhalten hat und darüber hinaus aktiv an den Tutorien teilgenommen und mindestens einmal seine Lösung vorgeführt hat, bekommt auf die Note der bei uns bestandenen Klausur einen Bonus von 0,3. Eine ohne diesen Bonus nicht bestandene Klausur kann dadurch jedoch nicht noch als bestanden gewertet werden.

Die Newsgroup uka.info3 dient der Diskussion von inhaltlichen und organisatorischen Fragen zur Vorlesung, Übung und den Tutorien in Informatik III an der Universität Karlsruhe im Wintersemester 03/04. Wir begrüßen es, wenn Studenten ihre Probleme in der Newsgroup untereinander lösen. Zur technischen Verwendung des Newsservers der Universität siehe http://news.rz.uni-karlsruhe.de.

• 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