You are here: Home Teaching Winter Term 2017/18 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, Christian Schilling
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
Di, 12:00-14:00 c.t. in Gebäude 101, Raum 01-018 (Jan)
Mi, 10:00-12:00 c.t. in Gebäude 52, Raum 02-017 (Claus)
Mi, 12:00-14:00 c.t. in Gebäude 101, Raum 01-016 (Marc)
Do, 14:00-16:00 c.t. in Gebäude 51, Raum 00-031 (Jacob)
Fr, 10:00-12:00 c.t. in Gebäude 52, Raum 02-017 (Saskia)
 Exam Zwischenklausur: 10.01.2018, 14-16 Uhr
Hauptklausur: 22.03.2018, 10-12 Uhr s.t., Gebäude 101, Hörsäle 026 und 036
Nachklausur: 18.09.2018, 10-12 Uhr s.t., Gebäude 101, Hörsaal 026
Language Deutsch
Course Catalog
Informatik III (Vorlesung)
Informatik III (Übungen)

Aktuelles

  • Die Noten für die Nachklausur wurden an das Prüfungsamt übermittelt.
  • Der Termin für die Nachklausur wurde bekanntgegeben (s.o.).
  • Wir bieten einen weiteren Termin für die Klausureinsicht an: Dienstag, den 17. April, zwischen 8:30 und 10:30 Uhr in Raum 052-00-022 oder 052-00-016 (je nach Verfügbarkeit). Bitte bringen Sie wieder Ihre UniCard mit.
  • Die Klausureinsicht wird am Montag, den 9. April, zwischen 16 und 18 Uhr in Raum 052-00-016 stattfinden. Bitte bringen Sie dazu Ihre UniCard mit.
  • Am Freitag, 16. März, um 14 Uhr c.t. in Gebäude 101, SR 00-010/014 bieten die Tutoren eine offene Fragestunde an. Sie können Fragen vorab in Ilias stellen, damit sich die Tutoren besser vorbereiten können.
  • Die Zwischenklausur wurde veröffentlicht.
  • Die Termine für die Zwischenklausur und die Hauptklausur wurden bekanntgegeben (s.o.).

Vorlesungsmaterialien

Wir verwenden das Ilias-System der Universität als Forum. Über diesen Link können Studenten der Veranstaltung beitreten. Es gibt dort außerdem Untergruppen für jedes Tutorat.

Vorlesungsskript

Folien der Einführunsvorlesung

Beispiel eines Kellerautomaten (Folien aus Vorlesung vom 1.12.2017)

Beispiele aus der Vorlesung im Webinterface der Ultimate Automatenbibliothek

Rückblick auf den Vorlesungsabschnitt zu Automatentheorie (Folien aus Vorlesung vom 20.12.2017)

Beispiele für Turingmaschinen (Folien aus Vorlesungen vom 20.12.2017 und 10.1.2018)

Fragestunde (Folien vom 22.12.2017)

Zwischenklausur

Übungsblatt
 Abgabe
Blatt 1
 27. Oktober
Blatt 2
3. November
Blatt 3
10. November
Blatt 4
17. November
Blatt 5
24. November
Blatt 6
1. Dezember
Blatt 7
8. Dezember
Blatt 8
15. Dezember
Blatt 9 22. Dezember
Blatt 10
12. Januar
Blatt 11
19. Januar
Blatt 12
26. Januar
Blatt 13
2. Februar
Blatt 14
9. Februar

Übungen

Jede Woche wird ein Übungsblatt hier bereitgestellt (voraussichtlich am Samstag).

Dieses wird von jedem Studenten in Zweiergruppen (erwünscht) oder alleine bearbeitet und in der darauffolgenden Woche am Freitag 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 Übungen erreicht werden und mindestens einmal in der Übungsgruppe vorgerechnet wird.

Nach der Winterpause (am 10.01.2018 um 14-16 Uhr) wird eine 40 minütige Zwischenklausur geschrieben. Diese wird korrigiert und bepunktet. Die Punkte werden dabei wie Übungspunkte behandelt. In der Zwischenklausur wird es ungefähr so viele Punkte wie auf drei Übungsblättern geben.

Einziges erlaubtes Hilfsmittel ist wie in der Hauptklausur ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem handschriftlichen Inhalt

 

Der für die Zwischenklausur relevante Vorlesungsstoff sind die Kapitel 1-4 des Vorlesungsskripts (Kapitel 5 und 6 sind also nicht mehr relevant für die Zwischenklausur).

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