You are here: Home Teaching Winter Term 2013/2014 Informatik III

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 und mit ihrer Hilfe werden Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen präzise definiert.
Course Type
Lecture
Classes
Tuesday 16:00-18:00 c.t. in building 101 - SR 00-010/14 (MMR)
Thursday 16:00-18:00 c.t. in building 101 - SR 00-010/14 (MMR)
Exercises
Monday 14:00-16:00 c.t. in building 52 - SR 02-017 (Julian Jarecki)
Monday 18:00-20:00 c.t. in building 101 - SR 00-010/14 (Tobias Seufert)
Monday 18:00-20:00 c.t. in building 101 - SR 01-009/13 (Betim Musa)
Friday 16:00-18:00 c.t. in building 101 -  SR 01-009/13 (Sabine Rogg)
 Exam Friday 28 February 2014, 14:00-16:00 in building 101 - 026 & 036
Language German
Instructors
Prof. Dr. Andreas Podelski, Matthias Heizmann, Alexander Nutz, Christian Schilling

Aktuelles

 

  • Die Nachklausur findet am 10. September um 9:00 Uhr in Gebäude 101 (026 und 036) statt. Erneut ist als Hilfsmittel ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen. Bitte vergessen Sie nicht, Ihre UniCard (oder Vergleichbares) mitzubringen.
  • Die Klausurnoten wurden an das Prüfungsamt gemeldet. Am Montag, den 17.3.2014, von 14 Uhr bis 16 Uhr kann die Klausur in Raum 00-016 in Gebäude 52 eingesehen werden. Bitte bringen Sie dazu Ihre UniCard mit.
  • Bitte beachten Sie, dass die Klausur bereits um 14:00 Uhr (s.t.) beginnt. Bitte vergessen Sie nicht, Ihre UniCard (oder Vergleichbares) mitzubringen.
  • Die Zulassungsvoraussetzung wurde von 50 % (97 Punkte) auf 48 % (93 Punkte) gesenkt.
  • Korrigierte Übungsblätter (z.B. Übungsblatt 14) können im Büro von Alexander Nutz und Matthias Heizmann abgeholt werden.
  • Für die Prüfung ist als Hilfsmittel ein DIN A4-Zettel (beidseitig beschrieben) mit beliebigem Inhalt zugelassen.
  • Die Probeklausur und ein Lösungsvorschlag zu Übungsblatt 14 sind online.
  • Am Dienstag, den 25.2.2014, wird von 14 Uhr (s.t.) bis 16 Uhr eine Fragestunde im Hinblick auf die Klausur angeboten. Diese findet im Hörsaal 00-036 in Gebäude 101 statt. Damit wir uns auf Ihre Fragen vorbereiten können, bitten wir Sie, diese im Vorfeld per E-Mail an die Assistenten zu senden.
  • Am Dienstag, den 11.2.2014, wird in der Vorlesung die "Probeklausur" besprochen.
  • Das Tutorat am Freitag, den 14.2.2014, findet nicht mehr statt.
  • Am Donnerstag, den 6.2.2014, wird in der Vorlesung eine "Probeklausur" angeboten. Dazu werden Ihnen einige Aufgaben in Stil einer Klausur gestellt, die Sie bearbeiten sollen. Die Bearbeitung wird nicht korrigiert oder bewertet. Die Teilnahme ist freiwillig. Wir planen, die "Probeklausur" am Dienstag, den 11.2.2014, in der Vorlesung zu besprechen.
  • Ein Lösungsvorschlag zu Übungsblatt 8 ist online. In den Tutoraten im neuen Jahr wird bereits Übungsblatt 9 besprochen.
  • Die Übungsaufgaben und Lösungsskizzen der Präsenzaufgaben aus der Vorlesung vom 21.11.2013 sind online.
  • Am Donnerstag, den 21.11.2013, wird in der Vorlesung eine Wiederholung des bisherigen Stoffs angeboten. Dazu werden Ihnen im ersten Teil einige Aufgaben gestellt, die Sie bearbeiten sollen. Die Bearbeitung wird nicht korrigiert oder bewertet. Anschließend werden wir die Aufgaben besprechen und auf etwaige Fragen eingehen. Sollten Sie bereits vorher Fragen zu Vorlesung oder Übungsbetrieb haben, schicken Sie bitte eine E-Mail mit diesen an die Assistenten.
  • Der Link zum Vorlesungsmitschrieb ist unten angegeben.
  • Die Einteilung der Übungsgruppen ist online.
  • Der Übungsbetrieb beginnt bereits in der ersten Vorlesungswoche -- allerdings erst ab Freitag, d.h. am Montag den 21.10.2013 finden noch keine Übungen statt.

 

Übungen

 

Jeden Donnerstag wird ein Übungsblatt hier ins Netz gestellt.

Dieses muss von jedem Studenten selbständig bearbeitet und am darauffolgenden Dienstag 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 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 Zulassungsvorraussetzung zur Klausur.  Die regelmäßige Teilnahme kann daran festgehalten werden, dass mindestens 50 % 48 % der Punkte aus den Übungen erreicht werden und mindestens einmal im Tutorium 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

 

Das Skript ist passwortgeschützt hier zugreifbar.

Zusätzlich wurde hier freundlicherweise ein Mitschrieb von Teilnehmern der Vorlesung erstellt und soll als Ergänzung zu obigem Skript dienen. Wir übernehmen keine Garantie auf Korrektheit oder Vollständigkeit.

 

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