Informatik III

Die Vorlesung gibt eine Einführung in die Theoretische Informatik. Sie führt in die Themen Endliche Automaten, Formale Sprachen und Grammatiken ein und liefert mehrere äquivalente präzise Fassungen des Berechenbarkeitsbegriffs. Es schließt sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Behandelt werden abstrakte Modelle von Maschinen und Sprachen, mit deren Hilfe Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen präzise definiert werden.

Course Type	Lecture
Classes	Dienstag 16:00-18:00 c.t. in Gebäude 101 - SR 00-036 Donnerstag 16:00-18:00 c.t. in Gebäude 101 - SR 00-036
Exercises	Mittwoch 14:00-16:00 c.t. in Gebäude 51 - HS 03-026 Mittwoch 14:00-16:00 c.t. in Gebäude 101 - SR 01-009/13 Mittwoch 16:00-18:00 c.t. in Gebäude 51 - HS 00-031 Freitag 10:00-12:00 c.t. in Gebäude 101 - SR 00-010/14
Exam	Freitag, 27. Februar 2015, 14 Uhr
Language	German
Instructors	Prof. Dr. Andreas Podelski, Matthias Heizmann, Alexander Nutz, Christian Schilling

Aktuelles

Die Noten für die Nachklausur wurden an das Prüfungsamt übermittelt. Die Nachklausur kann am Freitag, den 25 September 2015, zwischen 14 Uhr und 15 Uhr im Raum 052-00-016 eingesehen werden.
Nachklausur: Die Nachklausur findet am 10.09.2015 um 9 Uhr (s.t.) im Seminarraum 010/14 in Gebäude 101 statt. Bitte erscheinen Sie pünktlich zur Klausur und bringen Ihren Studierendenausweis ("Unicard") mit. Als Hilfsmittel ist ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen.
Die Noten wurden an das Prüfungsamt übermittelt. Die Klausur kann am Mittwoch, den 1. April 2015, zwischen 14 Uhr und 16 Uhr im Raum 052-00-016 eingesehen werden.
Bitte erscheinen Sie pünktlich zur Klausur und bringen Ihren Studierendenausweis ("Unicard") mit.
Die Zulassungen wurden an das Prüfungsamt übermittelt. Wir haben die nötige Grenze auf 47 % (= 85 Punkte) gesenkt.
Eine Probeklausur wurde veröffentlicht.
Die Vorlesungsnotizen wurden veröffentlicht. Viele Teile davon sind einfache Kopien aus dem Skript.
Am 18.12. entfällt die Vorlesung zugunsten der zu dieser Zeit stattfindenden Weihnachtsvorlesung. Am 23.12. (aktualisiert, hier stand fälschlicherweise 22.12.) entfällt die Vorlesung ebenfalls.
Wir haben eines der Freitagstutorate auf Mittwoch von 16-18 Uhr verlegt. Eine neue Einteilung unter besserer Berücksichtigung Ihrer Präferenzen ist hier verlinkt. Die neue Einteilung gilt ab nächster Woche (27.10.), diese Woche finden noch beide Freitagstutorate statt. Falls Sie immer noch wechseln wollen, sprechen Sie das am besten mit den beteiligten Tutoren ab.
Die Übungsgruppeneinteilung steht hier online. Leider gibt es zu viele Studierende, die für beide Freitagstermine "passt nicht" eingetragen haben. Wir bitten die Studierenden, bei denen es zur Not geht, in die Freitagstermine zu wechseln, so dass die, bei denen es gar nicht geht, Platz in einem Mittwochstutorat bekommen. Wenn Sie wechseln, schicken Sie diesbezüglich bitte eine E-Mail an Alexander Nutz (nutz@info...). Falls zu viele Studenten auf keinen Fall an einem Freitagstermin können, können wir uns um einen dritten Mittwochstermin bemühen. Vermutlich wäre der dann aber aus Raumbelegungsgründen zu einer ungünstigen Uhrzeit.
Der Übungsbetrieb beginnt bereits in der ersten Vorlesungswoche.

Übungen

Jeden Dienstag wird ein Übungsblatt hier ins Netz gestellt.

Dieses muss von jedem Studenten selbstständig bearbeitet und am darauffolgenden Montag bis spätestens 16:00 Uhr in die Briefkästen in Geb. 51 eingeworfen werden. Die abgegebenen Lösungen werden von den Tutoren mit Punkten bewertet und in den Übungsgruppen besprochen.

Die Übungsgruppe soll auch dazu dienen, Fragen aus der Vorlesung zu klären und den Vorlesungsstoff mit dem Tutor und den anderen Teilnehmern zu diskutieren. Eine regelmäßige Teilnahme an den Übungen ist verpflichtend und wichtig für das Verständnis der Vorlesung.

Wir empfehlen ausdrücklich beim Bearbeiten der Übungsaufgaben Lösungsansätze mit Kommilitonen zu besprechen und Lerngruppen zu bilden. Die Lösung muss aber von jedem Studenten selbstständig aufgeschrieben werden.

Leistungsnachweis

Die Prüfung besteht aus einer zweistündigen Klausur, die am Ende des Semesters stattfindet.

Regelmäßige Teilnahme an den Übungen ist Zulassungsvoraussetzung zur Klausur. Die regelmäßige Teilnahme kann daran festgehalten werden, dass mindestens 50 % 47 % der Punkte aus den Übungen erreicht werden und mindestens einmal in der Übungsgruppe vorgerechnet wird.

Als Hilfsmittel ist ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen.

Lernziel

Studierende sollen lernen, intuitive Konzepte wie Algorithmen, Berechenbarkeit, Komplexität formal und präzise zu fassen und ihre grundsätzliche Bedeutung für die Lösbarkeit von Problemen mit Hilfe von Rechnern erkennen zu können. Sie sollen Methoden zur Klassifikation von Problemen in verschiedene Komplexitätsklassen verstehen. Sie sollen Techniken, wie z.B. Reduktionstechniken, zur Einschätzung der Komplexität von Problemen beherrschen und anwenden können. Ferner sollen sie formale Sprachen und (endliche) Automaten als präzise Werkzeuge zur formalen Beschreibung von Sprachen und Prozessen einsetzen können.

Skript und Vorlesungsnotizen

Das Skript ist passwortgeschützt hier zugreifbar.

Vorlesungsnotizen:

Kontextfreie Sprachen Teil 1, Teil 2, Teil 3

Literatur

I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9
U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Taschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-1824-0
H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-8
J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3