• Dozentin: Prof. Dr. Dorothea Wagner
• Übungsleiter: Marco Gaertler, Martin Holzer, 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 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?

Deterministische und nicht-deterministische endliche Automaten, Sprachen, Turing-Maschinen, Berechenbarkeit, Church'sche These, 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)
• zur Nerod-Relation (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. Allein die Übungsblätter zwingen zur tatsächlichen Auseinandersetzung mit dem Stoff: Sie zeigen Euch und uns, was verstanden wurde und wo noch Lücken bestehen, und bieten die Möglichkeit einer gezielten Vorbereitung auf die Klausur. Wir raten daher dringend, die Übungsblätter kontinuierlich zu bearbeiten.

Jedes Übungsblatt besteht aus zwei Sorten von Aufgaben: Der erste Teil beschäftigt sich überwiegend mit dem Vorlesungsstoff der laufenden Woche. Diese Aufgaben werden in der darauffolgenden Woche in der großen Übung besprochen.

Der zweite Teil befasst sich hauptsächlich mit dem Stoff der Vorwoche. Diese Aufgaben sollen schriftlich bearbeitet und bis Donnerstag eine Woche nach Ausgabe, 14 Uhr, in den mit „Informatik III“ beschrifteten Einwurfschlitz im Keller des Informatik-Hauptgebäudes (50.34) eingeworfen werden. Die Bearbeitung und Abgabe der Aufgaben kann und soll dabei in Zweiergruppen erfolgen! (Wichtig: Dazu ist bitte darauf zu achten, dass beide Studenten im selben Tutorium sind.) Die Aufgaben werden von den Tutoren korrigiert und in den Tutorien der Folgewoche zurückgegeben und besprochen.

Um den Übungsleitern und Tutoren das Leben etwas zu erleichtern und um zu verhindern, dass Teile der Ausarbeitung an der falschen Adresse landen oder verlorengehen, bitten wir Euch, die Blätter zusammenzuheften und das Deckblatt nach folgendem Muster zu beschriften:

Für jedes Übungsblatt können insgesamt etwa gleich viele Punkte erreicht werden. Wer am Ende des Semesters mindestens 50 % der erreichbaren Punkte erhalten hat, aktiv an den Tutorien teilgenommen und dabei 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.)

…sind hier nicht mehr.

• 2005-04-12: 2. Klausur — Notenliste; Einteilung Einsicht
  Die Notenliste zur Nachklausur befindet sich hier. Zur Erinnerung: Die persönliche Klausur-ID kann auch auf der Studiseite (hinter dem Login) ersehen werden. Für die Klausureinsicht morgen, Mittwoch, 13. April (in Raum SR 301) haben wir folgende Einteilung vorgesehen mit der herzlichen Bitte, diese nach Möglichkeit (sofern der Stundenplan dies zulässt) einzuhalten:

• 2005-04-08: 2. Klausur — Einsicht
  Die Einsicht zur Nachklausur findet am Mittwoch, 13. April, von 14-17 Uhr im SR 301 (Info-Hauptbau) statt. Eine genauere Zeiteinteilung wird (zusammen mit den Klausurergebnissen) voraussichtlich kommenden Montag bekanntgegeben werden.
• 2005-04-06: 2. Klausur — Lösung
  Der Aufgabentext der 2. Klausur ist unter der Rubrik Materialien — Sonstiges bereitgestellt; eine Lösung folgt in Kürze.
• 2005-03-30: Hörsaalzuteilung; Klausurablauf
  Die für die Nachklausur (2. Klausur WS 2004/05) gültige Hörsaaleinteilung hängt aus (Stellwand im Foyer des Info-Hauptbaus und am schwarzen Brett des Lehrstuhls) und kann auch hier eingesehen werden. Bei Problemen, die Klausuranmeldung betreffend (Matrikelnummer taucht trotz abgegebener Anmeldung nicht auf der Liste auf), bitte Mail an Marco Gaertler. Einige Vorabhinweise zum Ablauf der Klausur sind hier zu finden.
• 2005-03-14: Übungsscheine
  Diejenigen Studenten, die nach der neuen Prüfungsordnung studieren und einen Nachweis über erfolgreiche Teilnahme an den Übungen (Übungsschein) benötigen, mögen sich bitte im Sekretariat (Raum 321) melden.
• 2005-03-14: Zweite Klausureinsicht
  Um die Wartezeiten erträglich zu halten, haben wir für den zweiten Klausureinsichtstermin am Donnerstag, 17. März, (im SR 301, Info-Hauptbau) folgende Zeiteinteilung vorgesehen:

• 2005-03-08: Mündliche Nachprüfungen; Anmeldung
  Für mündliche Nachprüfungen stehen an folgenden Tagen Termine zur Verfügung. Die betreffenden Studenten können sich hierzu ab sofort im Sekretariat (Raum 321) anmelden. Studenten, die aus studientechnischen Gründen (z. B. angestrebter Uniwechsel o. ä.) einen Termin am 16. März benötigen, bitte zeitig melden!

• 2005-03-07: 1. Klausur — Notenliste
  Die Notenliste mit Punktzahl befindet sich hier. Zur Erinnerung: Die persönliche Klausur-ID kann auch auf der Studiseite (hinter dem Login) ersehen werden.

• 2005-03-04: Klausur — vorläufige Notenliste
  Die Notenliste der Hauptklausur kann hier abgerufen werden (ohne Gewähr). Die verbindlichen Listen werden am kommenden Montag (07.03.) ausgehängt.
• 2005-03-03: Klausureinsichtstermine
  Zur ersten Klausur bieten wir zwei Einsichtstermine an: Mittwoch, 9. März, und Donnerstag, 17. März, jeweils im SR 301 des Info-Hauptgebäudes (Gebäude 50.34).
  Zu beachten: Aus logistischen Gründen werden am 9. März bevorzugt Studenten zur Klausureinsicht vorgelassen, die die Klausur nicht bestanden haben. Um allzu lange Wartezeiten zu vermeiden, haben wir weiterhin folgende Zeiteinteilung vorgesehen. Die Einteilung für den Einsichtstermin 17. März wird noch bekanntgegeben werden.

• 2005-03-01: 2. Klausur; Anmeldung
  Die zweite Klausur (Nachtermin) findet am Dienstag, 5. April 2005, um 16.00 Uhr statt.
  Die Anmeldung hierzu ist ab sofort bis 29. März 2005 möglich: Dazu bitte den Prüfungsschein in den Briefkasten am schwarzen Brett schräg gegenüber dem Sekretariat von Prof. Wagner (Raum 321) einwerfen. Abmeldungen können bis kurz vor Beginn der Klausur — im Sekretariat oder im entsprechenden Hörsaal — erfolgen.
  Hinweise: Zur Klausur sind keine Hilfsmittel zugelassen. Wichtig: es ist der Studentenausweis mitzubringen. Die Hörsaalbelegung wird noch bekanntgegeben werden.
• 2005-02-28: Klausur — Lösung
  In der Rubrik „Material - Sonstiges“ gibt es die Klausur (Haupttermin) mit Lösung zum Runterladen.
• 2005-02-23: Hörsaaleinteilung
  Die für die Klausur gültige Hörsaaleinteilung kann auch hier eingesehen werden.
• 2005-02-16: Hörsaalzuteilung; Klausurablauf
  Die Hörsaaleinteilung wird bis spätestens Montag, 21. Februar, bekanntgegeben sein: in schriftlicher Form an der entsprechenden Stellwand im Foyer des Info-Hauptbaus und am schwarzen Brett des Lehrstuhls sowie elektronisch abrufbar über die Studiseiten (hinter dem Login). Bei Problemen, die Klausuranmeldung betreffend (Matrikelnummer taucht trotz abgegebener Anmeldung nicht auf der Liste auf), bitte Mail an Martin Holzer.
  Einige Vorabhinweise zum Ablauf der Klausur sind hier zu finden.
• 2005-01-24: Korrektur ÜB 12, Aufgabe 5 (d)
  In Aufgabe 5 des aktuellen Übungsblattes hat sich beim regulären Ausdruck ein Fehler eingeschlichen: hierbei ist der letzte Sternchen-Ausdruck zu streichen, also: ((ab u ba)* c (ab u ba)* c)+.
• 2005-01-12: Klausur; Anmeldung
  Die erste Klausur (Haupttermin) findet am Donnerstag, 24. Februar 2005, um 11:00 Uhr statt.
  Die Anmeldung hierzu ist bis 17. Februar 2005 möglich: Dazu bitte den Prüfungsschein in den Briefkasten am schwarzen Brett gegenüber dem Sekretariat von Prof. Wagner (Info-Hauptgebäude, Raum 321) einwerfen. Abmeldungen können bis kurz vor Beginn der Klausur — im Sekretariat oder im entsprechenden Hörsaal — erfolgen.
  Hinweise: Zur Klausur sind keine Hilfsmittel zugelassen. Wichtig: es ist der Studentenausweis mitzubringen! Die Hörsaalbelegung wird noch bekanntgegeben werden.
• 2005-01-10: Tausch Vorlesung/Übung
  Diese Woche wird der Termin für die große Übung mit dem der Freitagsvorlesung getauscht: am 13. Januar findet also Vorlesung und am 14. Januar Übung statt.
• 2004-12-17: Termine: Übungsblatt 10, Vorlesung am 07. Januar
  Das Übungsblatt 10 wird regulär am 23. Dezember herausgegeben werden; Abgabetermin ist der 13. Januar.
  Die Vorlesung am Freitag, 07. Januar, findet ebenfalls regulär statt.
• 2004-12-16: Abgabe Übungsblatt 9
  Die Abgabefrist der Lösungen für Übungsblatt 9 ist nicht — wie üblich — donnerstags, sondern ist aus organisatorischen Gründen auf Mittwoch, 22. Dezember, 14:00 Uhr (bitte pünktlich abgeben!) vorverlegt worden.
• 2004-11-15: Ergänzungsblatt Nerode-Relation
  Unter der Rubrik Sonstiges Material ist ein Ergänzungsblatt zur Nerode-Relation eingestellt.
• 2004-11-12: Tausch Vorlesung/Übung
  Wir möchten jetzt schon folgende Stundenplanänderung bekanntgeben: In der ersten Dezemberwoche werden die Termine für die Übung und die Freitagsvorlesung getauscht werden; am 2. Dezember findet also Vorlesung und am 3. Dezember Übung statt.
• 2004-10-29: Login wieder aktiviert
  Der Login auf diesen Seiten müsste jetzt ohne Probleme wieder möglich sein.
• 2004-10-27: Fehler beim Login
  Beim Versuch, sich einzuloggen, gab es einige Probleme. Für diese Panne möchten wir uns herzlich entschuldigen! Wir haben einstweilen die Login-Funktion deaktiviert und werden Bescheid geben, sobald die Sache zuverlässig funktioniert.
• 2004-10-26: Login; Passwörter; persönliche Daten
  Ab sofort ist der Login auf diesen Seiten möglich. Das Passwort für die 'Nachzügler' ist der Nachname (großgeschrieben!), für alle anderen das Passwort für WebInScribe.
  Wir möchten alle Studenten bitten, sich so bald wie möglich ein erstes Mal einzuloggen, um mit der Funktionalität vertraut zu werden und ggf. das Passwort zu ändern. (Sollte das WebInScribe-Passwort nicht mehr verfügbar sein — wir hoffen, dass dies die absolute Ausnahme darstellt — bitte Mail an Martin Holzer.)
  Wichtig: Bitte überprüft die Korrektheit Eures Namens auf Eurer persönlichen Seite (erscheint nach dem Login); diese Daten werden auch für Klausurorganisation sowie Weiterleitung an das Prüfungsamt verwendet! Sollten nur Vor- und Nachname vertauscht sein, so kann dies selbsttätig mit dem entsprechenden Button korrigiert werden; bei Tippfehlern oder anderen Problemen bitte Mail an Martin Holzer.
• 2004-10-26: Tutorieneinteilung Nachzügler
  Das Ergebnis der nachträglichen Tutorieneinteilung befindet sich hier.
• 2004-10-21: Erstes Übungsblatt; erste Tutorien
  Das erste Übungsblatt kann ab sofort heruntergeladen werden. Abgabe ist am 28. Oktober, an dem auch die erste Übung stattfindet. Die ersten Tutorien finden dann in der ersten Novemberwoche statt. Da der 01.11. (Mo) ein Feiertag ist, bitten wir diejenigen, die in eines der Montagstutorien eingeteilt sind, auf ihre Übungszettel ihre reguläre Tutoriumsnr. zu schreiben, sich aber zur Besprechung der Aufgaben in eines der anderen Tutorien zu setzen. Die Übungszettel werden dann am darauffolgenden Montag (8.11.) von den jeweiligen Tutoren ausgegeben.
• 2004-10-20: Passwort
  Wichtig: Das Passwort für WebInScribe wird auch als initiales Passwort für diese Seiten verwendet werden, daher bitte gut aufbewahren! Der Login sollte ab Anfang kommender Woche möglich sein.
• 2004-10-19: Erste Vorlesung und Übung
  Die erste Vorlesung findet Mittwoch, 20. Oktober, im Forum statt; die erste Übung am Donnerstag, 28. Oktober, ebenfalls im Forum.
• 2004-10-19: Tutorieninformationen aktualisiert
  Die Informationen zu den Tutorien auf diesen Seiten sind nun auf dem neuesten Stand. Es hat sich folgende kleine Änderung ergeben: die Tutoren Henning Groenda und Chris Rathfelder haben die Tutorien 6 (jetzt Rathfelder) und 17 (jetzt Groenda) getauscht.
• 2004-10-15: Tutorienanmeldung und Lerngruppen
  Aktuelle Informationen zur Anmeldung zu den Tutorien per WebInScribe verfügbar. Denkt bitte daran, dass die Bearbeitung und Abgabe der Übungsaufgaben in Zweiergruppen (nicht mehr als zwei Personen pro Gruppe bei der Abgabe!) ausdrücklich erwünscht ist, und nutzt hierfür unbedingt die Funktionalität von WebInScribe zur Lerngruppenbildung (Merkblatt).
• 2004-10-14: Informatik-III-Seiten
  Diese Seiten zur Lehrveranstaltung Informatik III im WS 2004/05 befinden sich gerade im Aufbau. In den kommenden Tagen werden weitere Informationen, insbesondere zu Anmeldung (WebInScribe), Tutorien und wichtigen Terminen, bereitgestellt 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