Links to
Staff
Staff Overview
Professors
Secretary
- Elisa Merkel-Weißer
Contact
- Rooms • Phone • Mail
Research assistants
Technical staff
- Jens Heinrichs
Winter semester 2020

Institute for Theoretical Computer Science

SS 2006 – Einführung in die Informatik IV

Deutsch | English

Uni Lübeck › › Courses › SS 2006 › Einführung in die Informatik IV

[ Type and Content | Lecture | Exercise ]

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:	Skript – Teil 1 Skript – Teil 2 Skript – Teil 3 Skript – Teil 4 Skript – Teil 5 Skript – Teil 6 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:	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.