Software Engineering
Document Actions

Informatik III - Theoretische Informatik (Vorlesung)

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 und mit ihrer Hilfe werden Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen präzise definiert.

Aktuelles

  • Ein erweitertes Skript mit Kapitel 1-3 ist online.
  • Wegen der geringen Nachfrage werden wir nun doch keine englischsprachige Übungsgruppe anbieten. Übungsgruppe 6 wird trotzdem Fr 9-11Uhr stattfinden aber von Alexander Nutz auf deutsch gehalten werden.
  • Am Freitag, den 23.10. findet die Übungsgruppe 6 nicht statt.
    Studierende aus Gruppe 6, deren Nachnamen mit A-G beginnt, nehmen bitte an Übungsgruppe 4 (Fr 9-11Uhr -- SR 03-006, Geb. 51 -- Björn Sieber) teil.
    Studierende aus Gruppe 6, deren Nachnamen mit H-Z beginnt, nehmen bitte an Übungsgruppe 5 (Fr 9-11Uhr -- SR 00-006, Geb. 51 -- Florian Geißer) teil.
  • Das Kapitel eins und zwei des Skriptes sind (passwortgeschützt) online. Die weiteren Kapitel folgen im Lauf des Semesters.
  • Die Übungsgruppeneinteilung ist online. Erfreulicherweise konnten die Wünsche großteils erfüllt werden. Jeder Student ist in einer Übungsgruppe, welche von ihm mit A oder B bewertet wurde. Die Handschriften konnten teilweise nur schwer entziffert werden. Ich bitte deshalb falsch geschriebene Namen zu entschuldigen.
  • Achtung: Der Übungsbetrieb startet bereits in der ersten Vorlesungswoche.

Übungen

Jeden Montag wird ein Übungsblatt in der Vorlesung ausgelegt und ins Netz gestellt. Dieses muss innerhalb einer Woche von jedem Studenten selbständig bearbeitet und am darauffolgenden Montag zu Beginn der Vorlesung abgegeben 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 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. Abschreiben wird als persönlicher Affront gegen die Dozenten und Übungsgruppenleiter verstanden und so geahndet. Beim abschreiben werden beide Bearbeitungen (die Kopie und das Original) mit 0 Punkten bewertet.

Übungsgruppen

Die Übungsgruppen finden zu den folgenden Terminen statt:

  1. Di 11-13Uhr -- SR 00-031, Geb. 51 -- Björn Buchhold
  2. Mi 9-11Uhr -- SR 00-031, Geb. 51 -- Rebecca Albrecht
  3. Mi 9-11Uhr -- SR 00-034, Geb. 51-- Jan Leike
  4. Fr 9-11Uhr -- SR 03-006, Geb. 51 -- Björn Sieber
  5. Fr 9-11Uhr -- SR 00-006, Geb. 51 -- Florian Geißer
  6. Fr 9-11Uhr --SR 00-031, Geb. 51 -- Alexander Nutz

Die Übungsgruppeneinteilung finden Sie hier.

Leistungsnachweis

Die Prüfung besteht aus einer zweistündigen Klausur die am Ende des Semesters stattfindet (Termin wird noch bekanntgegeben). Um zu dieser Klausur zugelassen zu werden müssen 50% der Punkte aus den Übungen erreicht werden.

Bonuspunkte: Punkte aus den Übungen werden skaliert und zu denen in der Hauptklausur (nicht Nachklausur!) erreichten Punkten addiert. Die Skalierung wird so gewählt, dass 100% der Punkte aus den Übungsaufgaben eine Verbesserung von zwei Notenschritten (z.B. 3.0 -> 2.3) ergeben. (Das bedeutet also insbesondere, dass Übungspunkte zum Bestehen der Hauptklausur helfen können.)

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

Das Skript ist passwortgeschützt hier zugreifbar.  Es wird kapitelweise im Laufe des Semesters zur Verfügung gestellt.

JFLAP

Das in der Vorlesung vorgestellte Programm welches unter anderem Automaten, Operationen auf Automaten und Abläufe von Automaten darstellen kann, ist unter www.jflap.org verfügbar.
Die "finite automata" von JFLAP entsprechen unseren Epsilon-NEAs. JFLAP verwendet das Lambda-Zeichen (statt dem in der Vorlesung verwendeten Epsilon-Zeichen) um das leere Wort darzustellen.

Literatur

  1. I.Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9.
  2. U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Taschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 3-8274-1824-0
  3. 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
  4. 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


  • Instructors: Andreas Podelski | Jochen Hoenicke | Matthias Heizmann
  • Times & Locations: Mon, 14:00 - 16:00, HS 00-036 Geb. 101 | Fri, 14:00 - 16:00, HS 00-036 Geb. 101
  • Tutors: Rebecca Albrecht | Björn Buchhold | Florian Geißer | Jan Leike | Alexander Nutz | Björn Sieber
  • Times & Locations of tutorials: Tue, 11:00 - 13:00, SR 00-031, Geb. 51 | Wed, 9:00 - 11:00, SR 00-031 and 00-034, Geb. 51 | Fri, 9:00 - 11:00, SR 00-031, 00-006, and HS 03-026, Geb. 51