« October 2018 »
October
MoTuWeThFrSaSu
1234567
891011121314
15161718192021
22232425262728
293031
Uni-Logo
You are here: Home Teaching Winter Term 2018/19 Informatik III (Lecture)
Document Actions

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 werden noch bekanntgegeben
Language Deutsch
Course Catalog
Informatik III (Vorlesung)
Informatik III (Übungen)

Aktuelles

  • 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)

     

    Übungen

    Jede Woche werden hier zwei Aufgabenblätter veröffentlicht. Das Voreitungsblatt 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.

     

    Abgabe

     
    24.10.2018
    Übungsblatt 01 Vorbreitungsblatt 01

     

    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.

    Nach der Winterpause (genauer Termin wird noch bekanntgegeben) 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 voraussichtlich 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
    Personal tools