Art und Inhalt

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.

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

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

• Skript – Teil 1
• Skript – Teil 2
• Skript – Teil 3
• Skript – Teil 4
• Skript – Teil 5
• Skript – Teil 6

Vorlesung

Übung

• Zeit und Ort: Mo, 14 – 16, und Do, 11 – 12, Seminarraum Informatik 4
• Tutor: Sebastian Riemann ("Sebastian.Riemann" at "informatik.uni-luebeck.de")

• Zeit und Ort: Mo, 14 – 16, und Do, 11 – 12, Seminarraum Informatik 2+3
• Tutor: Hauke Nagel ("Hauke.Nagel" at "informatik.uni-luebeck.de")

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

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

• Projektaufgabe 1
  Abgabe: Montag, 08.05.2006, in der Übung
• Projektaufgabe 1 – Testeingaben, Modul 1
  Führen Sie Ihr Modul 1 auf diesen Testeingaben aus, und notieren Sie die Ergebnisse!
• Projektaufgabe 1 – Testeingaben, Modul 3 (korrigiert)
  Führen Sie Ihr Modul 3 auf diesen Testeingaben aus, und notieren Sie die Ergebnisse!
• Projektaufgabe 1 – Testeingaben, Performance
  Messen Sie die Laufzeit von Modul 3 unter diesen Testeingaben und notieren Sie die Ausgabe!
• Projektaufgabe 2
  Abgabe: Montag, 07.07.2006, in der Übung
• Projektaufgabe 2 – Testeingaben

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