50 years Univerity of Lübeck

Institute for Theoretical Computer Science

SS 2006 – Einführung in die Informatik IV



Type and Content

Title: Einführung in die Informatik IV
Actual:

Bei der Einsichtnahme der Informatik IV Klausur habe ich eine gewisse Nachfrage nach einer zusätzlichen Übung zur Vorbereitung auf die nächste Informatik IV Klausur bemerkt. Da ich diese Übung nicht für jede einzelne Studentgruppe separat abhalten möchte, bitte ich hiermit darum, bei Intresse an so einer Übung, eine Email an mich zu senden. Ich werde dann einen geeigneten Termin wählen und rechtzeitig an alle Interessierten weitergeben.

Host: Reischuk
Classification: Diplom-Studiengang 4. Semester Pflicht
Bachelor-Studiengang 4. Semester Pflicht
Conentent:

Modellierung, Analyse und Lösung algorithmischer Probleme:

Algorithmische Komplexität:

  • Komplexitätsmaße
  • Komplexitätsklassen
  • NP-Vollständigkeit
  • Erfüllbarkeitsprobleme der Logik
  • diskrete Optimierungsprobleme

Formale Sprachen:

Formale Grammatiken: reguläre Sprachen und Ausdrücke, kontextfreie und kontextsensitive Sprachen, Chomsky Hierarchie, Pumping Lemma, Wortprobleme

Maschinenmodelle: endliche Automaten, Turing-Maschinen, Registermaschinen, Determinismus, Nichtdeterminismus, Reduktion zwischen Problemen, Simulation, Entscheidbarkeit, Aufzählbarkeit

Literature:
  • [HU94] J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Add.Wesley 1994
  • [Ha78] M. Harrison: Introduction to Formal Language. Theory. Add.Wesley 1978
  • [Sa98] J. Savage: Models of Computation. Add.Wesley 1998
  • [Re98] R. Reischuk: Komplexitätstheorie, Band I: Grundlagen, Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus.Teubner 1998
  • [GJ79] M. Garey, D. Johnson: Computers and Intractability. Freeman, 1979
  • [KT05] J. Kleinberg, E. Tardoz: Algorithmen Design. Add. Wesley 2005
Vorlesungsskript: Beipiele für dynamisches Programmieren

Lecture

Host: Reischuk
Hours: 4 SWS, 9 ECTS
Dates: Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr. 8.00h-10.00h, H1
Erste Vorlesung: Mittwoch, 05.04.2006

Exercise

Host: Reischuk, Hundt
Hours: 3 SWS
Dates: Erste Übungsstunde: Donnerstag, 06.04.2006
Einteilung in Übungsgruppen erfolgt am Ende der ersten Vorlesung.

Gruppe 1
  • Zeit und Ort: Mo, 14 – 16, und Do, 11 – 12, Seminarraum Informatik 4
  • Tutor: Sebastian Riemann ("Sebastian.Riemann" at "informatik.uni-luebeck.de")
Gruppe 2
  • Zeit und Ort: Mo, 14 – 16, und Do, 11 – 12, Seminarraum Informatik 2+3
  • Tutor: Hauke Nagel ("Hauke.Nagel" at "informatik.uni-luebeck.de")
Gruppe 3
  • Zeit und Ort: Mo, 14 – 16, und Fr, 13 – 14, ITCS Seminarraum 21. 2. OG Geb. 64
  • Tutor: Raphael Maas ("Maas" at "informatik.uni-luebeck.de")
Übungsblätter:
  • Übungsblatt 0
    keine Abgabe, Besprechung in den Übungsgruppen
  • Übungsblatt 1
    Abgabe: Donnerstag, 13.04.2006, in der Übung
  • Übungsblatt 2
    Abgabe: Donnerstag, 20.04.2006, bzw. Freitag, 21.04.2006, in der Übung
  • Übungsblatt 3
    Abgabe: Donnerstag, 27.04.2006, bzw. Freitag, 28.04.2006, in der Übung
  • Übungsblatt 4
    Abgabe: Donnerstag, 04.05.2006, bzw. Freitag, 05.05.2006, in der Übung
  • Übungsblatt 5
    Abgabe: Donnerstag, 11.05.2006, bzw. Freitag, 12.05.2006, in der Übung
  • Übungsblatt 6
    Abgabe: Donnerstag, 18.05.2006, bzw. Freitag, 19.05.2006, in der Übung
  • Übungsblatt 7
    Abgabe: Freitag, 26.05.2006, in der Vorlesung bzw. in der Übung
  • Übungsblatt 8
    Abgabe: Donnerstag, 01.06.2006, bzw. Freitag, 02.06.2006, in der Übung
  • Übungsblatt 9
    Abgabe: Donnerstag, 08.06.2006, bzw. Freitag, 09.06.2006, in der Übung
  • Übungsblatt 10
    Abgabe: Donnerstag, 15.06.2006, bzw. Freitag, 16.06.2006, in der Übung
  • Übungsblatt 11
    Abgabe: Donnerstag, 22.06.2006, bzw. Freitag, 23.06.2006, in der Übung
  • Übungsblatt 12
    Abgabe: Donnerstag, 29.06.2006, bzw. Freitag, 30.06.2006, in der Übung
  • Übungsblatt 13
    Abgabe: Donnerstag, 06.07.2006, bzw. Freitag, 07.07.2006, in der Übung
  • Übungsblatt 14
    Abgabe: Donnerstag, 13.07.2006, bzw. Freitag, 14.07.2006, in der Übung
  • Übungsblatt 15
    Abgabe: Donnerstag, 20.07.2006, bzw. Freitag, 21.07.2006, in der Übung
Projektaufgaben:
  • Testen Sie Ihre Module 1,2 und 3 jeweils mit den Graphen G1, G2 und G3.
  • Wenden Sie Modul 4 auf G2 und G3 an und verwenden Sie dafür die angegebenen Knotenindizes s und t.
  • Berechnen Sie mit Hilfe Ihres Moduls 5 spannende Bäume für G4 und G5 und die zugehörigen Kostenfunktionen.
  • Bestimmen Sie durch Anwendung Ihres Moduls 6 ob G4 und G5 bipartite Graphen sind.
  • Berechnen Sie die Erreichbarkeitsmatrix M für den Graphen G1 unter Verwendung von Modul 7.