You are here: Home › Teaching › Winter Term 2018/19 › Informatik III (Lecture)

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
 Vorlesung
Instructors Prof. Dr. Andreas Podelski, Dr. Matthias Heizmann, Alexander Nutz
Lecture
 Mittwoch 14:00-16:00 c.t. in Gebäude 101, Raum 00-026
Freitag 14:00-16:00 c.t. in Gebäude 101, Raum 00-026
Exercises
 Mo, 08:00-10:00, c.t., in Gebäude 101 in Raum 00-016 (Johanna)
Mo, 12:00-14:00, c.t., in Gebäude 51 in Raum  00-034 (Lars)
Mo, 12:00-14:00, c.t., in Gebäude 51 in Raum 00-031 (Tim)
Mo, 16:00-18:00, c.t., in Gebäude 101 in Raum 01-009/013 (Jens)
Mi, 10:00-12:00, c.t.,in Gebäude 51 in Raum 00-006 (Jan)
Mi, 10:00-12:00, c.t., in Gebäude 51 in Raum 00-034 (Leonard)
 Exam Hauptklausur: 22.03.2019, 10-12 Uhr s.t., Gebäude 101, Hörsäle 026 und 036, sowie Seminarraum 010/14
Language Deutsch
Course Catalog
 Informatik III (Vorlesung)
Informatik III (Übungen)

Aktuelles

  • 14.04.2019 Die Klausureinsicht findet am Mittwoch den 17.04.2019 zwischen 14 Uhr und 15 Uhr in Raum 00-016 von Gebäude 052 statt.
  • 25.03.2019 Die Klausur ist korrigiert. Sie sollten Ihre Note im Campus Management System der Universität sehen können.
  • 22.03.2019 Wir haben eine Version der heute geschriebenen Klausur mit Lösungen hochgeladen.
  • 10.03.2019 Wir werden am Freitag den 15.03.2019 eine Fragestunde anbieten. Diese findet ab 14:15 in Raum 00-026 von Gebäude 101 (also dem gleichen Hörsaal wie die Vorlesung) statt.
  • 05.03.2019 Die zweite Zwischenklausur ist online. Weitere Informationen stehen auf der ersten Seite der Zwischenklausur. (zweite Zwischenklausur mit Lösungen)
  • 03.02.2019 Die Summe der regulären Punkte aller Übungs- und Vorbereitungsblätter beträgt 221 Punkte. Mit zwei Aufgaben (Vor12A2, Vor14A3) konnten zusätzlich insgesamt 4 Bonuspunkte erziehlt werden aber dies spielt in der folgenden Rechnung keine Rolle. Somit sind alle Teilnehmer, die mindestens 110,5 Punkte (50% von 221 Punkten) erreicht haben und min den Übungsgruppen mindestens ein mal vorgerechnet haben zur Klausur zugelassen. Beachten Sie beim Ermitteln Ihrer Punktzahl, dass jeder Vorlesungsteilnehmer wegen Problemen in Aufgabenstellungen (Vor5A1a, Vor8A2a, Vor13A1a) zusätzlich 2,5 Bonuspunkte erhält. Diese Bonuspunkte sind bei manchen Übungsgruppen bereits auf Ihrem korrigierten Übungsblatt vermerkt.
  • 02.02.2019 Aufgabe 1a von Vorbereitungsblatt 13 enthielt einen Fehler. Wir bitten dies zu entschuldigen und haben uns folgene Regelung überlegt:  i) Die Punktzahl bei dieser Aufgabe bleibt unverändert. ii) Jeder Vorlesungsteilnehmer bekommt einen Bonuspunkt. Dieser wird nicht notwendigerweise vom Tutor auf dem Übungsblatt vermerkt sondern am Semesterende automatisch hinzugefügt. Außerdem haben wir zu diesem Vorbereitsblatt auch die Lösungen veröffentlicht.
  • 23.12.2018 Die Zwischenklausur ist online. Das Bearbeiten der Zwischenklausur ist freiwillig und es können dadurch keine Übungspunkte erziehlt werde. Weitere Informationen stehen auf der ersten Seite der Zwischenklausur. (Zwischenklausur mit Lösungen und Kommentaren)
  • 21.12.2018 Ein in der Zwischenevaluation genannter Wunsch war es das Vorlesungsskript um mehr Beispiele zu erweitern. Das finden guter Beispiele fällt auch mir sehr schwer. Die Beispiele im Skript sind recht sorgfältig ausgewählt, sollen recht klein sein und die Aufmerksamkeit der Leser auf bestimmte wichtige Aspekte des aktuellen Kapitels fokusieren. Wenn ich das Skript nun einfach um "irgendwelche" Beispiele erweitere müssen die Leser mehr Beispiele lesen aber können daraus möglicherweise keine neuen Erkentnisse gewinnen. Außerdem möchte ich im Skript keine Aspekte aufzeigen die schon durch Übungsaufgaben diskutiert wurden. Ich kann aber möglicherweise mit Ihrer Hilfe gute Beispiele finden. Wenn Sie mir sagen welcher Aspekt noch nicht durch Beispiele abgedeckt ist dann kann ich ein entsprechendes Beispiel entwerfen oder Ihnen zumindest erklären durch welches Beispiel (aus Skript oder Übungen) dieser Aspekt bereits abgedeckt ist.
  • 19.12.2018 Bei der Abstimmung zur letzten Vorlesung vor Weihnachten wurden 28 Stimmen abgegeben, Eine Stimme entfiel auf die "normale Vorlesung", 9 Stimmen auf die "Zusammenfassung des bisherigen Vorlesungsstoffes", keine Stimme auf die "Fragestunde", 10 Stimmen auf die "Vorstellung der Forschung des Lehrstuhls" und 8 Stimmen entfielen auf die Spielshow. Wir trafen die folgende Entscheidung: Wir werden zunächst kurz mit der Vorlesung fortfahren und Kapitel 5 abschließen. Dann folgt eine Zusammenfassung des bisherigen Vorlesungsstoffes und anschließend folgt eine Vorstellung des Ultimate Automizer Softwareverifikationswerkzeuges. Es wird gezeigt wie dieses Werkzeug mit Hilfe automatentheoretischer Operationen Fehler in Computerprogrammen findet und Korrektheitsbeweise für Fehlerfreie Computerprogramme generiert.
  • 16.12.2018 Wir freuen uns über die vielen positiven in der Zwischenevaluation aber danken auch für die Kritik und Verbesserungsvorschläge und werden versuchen Ihre Hinweise im  Wir werden versuchen Ihre Hinweise in den weiteren Verlauf der Veranstaltung einfließen zu lassen.
  • Aufgabe 2a von Vorbereitungsblatt 8 war nicht lösbar. Wir bitten dies zu entschuldigen und haben uns folgene Regelung überlegt:  i) Die Punktzahl bei dieser Aufgabe bleibt unverändert. ii) Jeder Vorlesungsteilnehmer bekommt einen halben Bonuspunkt. Dieser wird nicht notwendigerweise vom Tutor auf dem Übungsblatt vermerkt sondern am Semesterende automatisch hinzugefügt. iii) Der halbe Punkt in Aufgabe 2a wird für Lösungen vergeben die eine Ableitung in vier Schritten angeben oder behaupten dass keine Ableitung in drei Schritten existiert (ausnahmsweise keine Begründung erforderlich).
  • Aufgabe 1a von Vorbereitungblatt 5 war nicht lösbar. Wir bitten dies zu entschuldigen und haben uns folgene Regelung überlegt: i) Die Punktzahl bei dieser Aufgabe bleibt unverändert ii) Jeder Vorlesungsteilnehmer bekommt einen Bonuspunkt. Dieser wird nicht notwendigerweise vom Tutor auf dem Übungsblatt vermerkt sondern am Semesterende automatisch hinzugefügt.  iii) Der Punkt in Aufgabe 1a wird nur für die Lösungen vergeben die darlegen warum diese Aufgabe unlösbar ist.
  • Bei der Abstimmung zur Zwischenklausur wurden 80 Stimmen abgegeben, 36 Teilnehmer befürworten eine Zwischenklausur, 44 Teilnehmer sind dagegen. Die Zwischenklausur findet somit nicht statt. Um dennoch die Wünsche der Zwischenklausurbefürworter teilweise zu erfüllen haben wir uns folgende Regelung überlegt: Ungefähr Anfang der Weihnachtspause werden wir die Aufgaben der Zwischenklausur online stellen. Das Bearbeiten dieser ist nicht verpflichtend, wir empfehlen aber sehr diese zu Hause, alleine, vorbereitet und mit dem Zeitdruck einer Klausur zu rechnen. Der Dozent wird jeweils mindestens fünf (möglicherweise nicht mehr!) abgegebene Klausuren korrigieren und die Korrektur in Ilias allen Vorlesungsteilnehmern zur Verfügung stellen. Zu diesem Zweck dürfen Sie Ihre Lösungen bis zum 11.1.2019 elektronisch oder auf Papier beim Dozenten abgeben. Schreiben Sie Ihren Namen höchstens so auf die Lösungen (z.B. gar nicht) dass der Dozent wenig Arbeit in die Annonymisierung investieren muss.
  • Die Übungsgruppeneinteilung erfolgte in der ersten Vorlesungwoche über die Ilias Lernplattform. Anmeldungen die über das HISinOne Campus Management System gemacht wurden spielen hierfür keine Rolle. Sollten sie noch in keiner Übungsgruppe eingeteilt sein dann wenden Sie sich bitte an Alexander Nutz.
  • Die Übungsgruppen starten erst in der zweiten Vorlesungswoche. Da zu diesem Zeitpunkt noch kein Übungsblatt abgegeben wurde, werden die Teilnehmer zusammen mit ihrem Tutor ein spezielles Präsenzübungsblatt bearbeiten und besprechen.
  • Die Übungsaufgaben zur ersten Vorlesungswoche erscheinen vermutlich erst am Freitag.

    Vorlesungsmaterialien

    Wir verwenden das Ilias-System der Universität als Forum. Über diesen Link können Studierende der Veranstaltung beitreten.

    Vorlesungsskript (Das Skript wird kontinuiertlich aktualisiert, typischerweise werde auch nach der Vorlesung noch kleinere Änderungen gemacht.)

    Folien der Einführungsvorlesung (17.10.2018)

    Folien zu Grundbegriffen formaler Sprachen mit Beispiel eines endlichen Automaten (19.10.2018)

    Folien mit Beispiel eines Kellerautomaten (12.12.2018)

    Folien zum Pumping Lemma für kontextfreie Spachen (14.12.2018)

    Folien mit Beispiel einer Turingmaschine (19.12.2018)

    Zwischenklausur

     

    Übungen

    Jede Woche werden hier zwei Aufgabenblätter veröffentlicht. Das Vorbereitungsblatt enthält wenige Aufgaben und dient dazu, den Stoff der kommenden Vorlesungswoche vorzubereiten. Das Übungsblatt ist umfangreicher und dient dazu, den Stoff der aktuellen Vorlesungswoche zu üben.

     

     

    Beide Aufgabenblätter werden von den Studierenden alleine bearbeitet und in der darauffolgenden Woche am Mittwoch vor der Vorlesung in die Briefkästen in Gebäude 51 eingeworfen. 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.

    Leistungsnachweis

    Die Prüfung besteht aus einer zweistündigen Klausur.

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

    Regelmäßige Teilnahme an den Übungen ist Zulassungsvoraussetzung zur Klausur. Die regelmäßige Teilnahme kann daran festgehalten werden, dass mindestens 50 % der Punkte aus den Aufgabenblättern erreicht werden und mindestens einmal in der Übungsgruppe vorgerechnet wird. Die Punkte aus den Aufgabenblättern sind dabei die Summe der Punkte aus Vorbereitungsblättern und Übungsblättern.

    Lernziel

    Studierende sollen lernen, intuitive Konzepte wie Algorithmen, Berechenbarkeit und 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.

    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