« October 2017 »
October
MoTuWeThFrSaSu
1
2345678
9101112131415
16171819202122
23242526272829
3031
Uni-Logo
You are here: Home Teaching Winter Term 2017/18 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, 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
Voraussichtlich:
Di, 12:00-14:00 c.t. (Jan)
Mi, 10:00-12:00 c.t. in Gebäude 52, Raum 02-017 (Claus)
Mi, 12:00-14:00 c.t. (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 Wird noch bekanntgegeben.
Language Deutsch
Course Catalog
Informatik III (Vorlesung)
Informatik III (Übungen)

Aktuelles

  • Die Aufteilung auf die Übungsgruppen ist vorläufig abgeschlossen. Wir werden voraussichtlich die beiden zusätzlichen Termine verwenden (s.o., definitive Zusage aber erst am Montag, nachdem wir die Räume offiziell erhalten haben).
    Bitte beachten Sie, dass 20 Studenten nicht an der Umfrage teilgenommen haben und daher auch nicht in die Verteilung eingeflossen sind. Falls wir diese Studenten in den nächsten Tagen noch auf die Tutorate verteilen müssen, kann es sein, dass wir nochmals einige von den bereits eingeteilten Studenten bitten, die Übungsgruppe zu wechseln, sofern eine gleichwertige Präferenz angegeben wurde.
  • Wir werden die Übungstermine aus dem Vorlesungsverzeichnis übernehmen (außer dem Dienstagsstermin), aber die Gruppen neu aufteilen (auf insgesamt fünf Gruppen, vorläufige Aufteilung s.o.). Bitte nehmen Sie dazu bis Freitag, 20. Oktober, um 18 Uhr an der Umfrage im Ilias-System teil. Wir planen die Gruppeneinteilung am Samstag vorzunehmen.

    Update: Es gibt zwei neue Optionen für einen Tutoratstermin: Dienstag und Mittwoch jeweils von 12 Uhr bis 14 Uhr. Sollten wir einen dieser Ausweichtermine benötigen, können wir entsprechend noch keine definitiven Zusagen am Samstag machen.

  • Der Übungsbetrieb beginnt bereits in der ersten Vorlesungswoche. Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche mit Anwesenheitsübungen. Das erste reguläre Übungsblatt wird in der zweiten Vorlesungswoche abgegeben und in der dritten Vorlesungswoche besprochen.

Vorlesungsmaterial

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.

Folien der Einführunsvorlesung

Vorlesungsskript

Übungsblatt
 Abgabe
Blatt 1
 27. Oktober (s. aber Fußnote auf dem Übungsblatt)

Ü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 wird eine Zwischenklausur geschrieben. Diese wird korrigiert und wie ca. drei Übungsblätter gezählt.

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.

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