50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Einführung in die Informatik IV


[ Type and Content | Lecture | Exercise ]
Script Teil 1 "Logik"
Folien zur Vorlesung
Grafiken zu Turingmaschinen
Backtracking

Type and Content
Title: Einführung in die Informatik IV
Lecturer: Reischuk
Classification: 4. Sem. Diplom-Studiengang + Bachelor
Content:

Modellierung, Analyse und Lösung algorithmischer Probleme:

Maschinenmodelle, Turing-Maschinen, Registermaschinen, Formale Grammatiken, Determinismus, Nichtdeterminismus, Probabilismus, Reduktion zwischen Problemen, Simulation

Algorithmische Komplexität:

Komplexitätsmaße, Komplexitätsklassen, untere Schranken, Zeit- und Platzhierarchien, NP-Vollständigkeit, Erfüllbarkeitsprobleme der Logik, diskrete Optimierungsprobleme

Formale Sprachen:

Normalformen, kontextfreie und kontextsensitive Sprachen, Comsky Hierarchie, reguläre Sprachen, reguläre Ausdrücke, endliche Automaten, Pumping Lemma, Wortprobleme
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
Written test:
  • Bachelorklausur
    Zeit und Ort: Fr, 15.07.2005, 8.15 - 9.45 Uhr, H 1 (Turmgebäude)
  • Vordiplomsklausur Informatik III/IV
    Zeit und Ort: Mi, 14.09.2005, 9.00 - 12.00 Uhr, Z 1/2 (Zentralklinikum)
  • Bachelor-Wiederholungsklausur
    Zeit und Ort: Mi, 14.09.2005, 9.00 - 10.30 Uhr, Z 3 (Zentralklinikum)

Erlaubte Hilfsmittel bei Vordiplomsklausur und Bachelor-Wiederholungsklausur:

Schreibwerkzeug sowie ein beidseitig ausschließlich mit Informatik IV-relevantem Inhalt handbeschriebenes DIN A4-Blatt
Actual:

Erlaubte Hilfsmittel bei Vordiplomsklausur und Bachelor-Wiederholungsklausur:

Schreibwerkzeug sowie ein beidseitig ausschließlich mit Informatik IV-relevantem Inhalt handbeschriebenes DIN A4-Blatt


Zusatzübung: Mittwoch, 31.08.2005, 14-16 Uhr, Seminarraum 2/3 (Cook/Karp)


Klausureinsicht Bachelorklausur und Probeklausur vom 15.07.2005: Mittwoch, 10.08.2005, 14-15 Uhr, Seminarraum ITCS (Geb. 64, Raum 3.021)


Anmeldung zur Bachelor-Wiederholungsklausur bis Mittwoch, 07.09.2005, im Sekretariat des ITCS (Frau Mamat) oder per Mail bei Jan Arpe


Es gibt noch mehr Übungsaufgaben zur Vorbereitung auf die Klausuren am 14.09.2005.


Anmeldung zur Bachelorklausur bis Mittwoch, 13.07.2005, im Sekretariat des ITCS (Frau Mamat)


Achtung Raumänderung: Aufgrund von Berufungsvorträgen findet die Übung der Gruppe 2 am Montag, 30.05.2005, im PC-Labor des Instituts für Medizinische Informatik statt (PC-Labor IMI, Haus 64, 1. Stock, Raum 35, s. Raumplan 1. Stock)


Info IV-Abend: Donnerstag, 21.04.2005, ab 20 Uhr im Alten Zolln
Vorlesungsskript:

Lecture
Lecturer: Reischuk
Hours: 4 SWS, 9 ECTS
Dates: Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr. 8.00h-10.00h, H1

Exercise
Lecturer: Reischuk, Arpe
Hours: 3 SWS
Dates: Erste Übungsstunde: Donnerstag, 07.04.2005
Einteilung in Übungsgruppen erfolgt am Ende der ersten Vorlesung.
Gruppe 1: Mo. 14 -16 h + Do. 11-12 h Seminarraum Informatik 4 (Minsky), Tutor: Michael Elberfeld
Gruppe 2 : Mo. 14-16 h + Do. 11-12 h Seminarraum 2+3 (Cook + Karp m. geöffneter Trennwand), Tutor: Raphael Maas
Gruppe 3: Mo. 14-16 h ITCS-Seminarraum 21, 2. OG. Geb. 64, Do. 11-12 h R3, Tutor: Johannes Textor
Übungsblätter:
  • Übungsblatt 0: .pdf
    keine Abgabe, Besprechung in den Übungsgruppen
  • Übungsblatt 1: .pdf
    Abgabe: Donnerstag, 21.04.2005, in der Übung
  • Übungsblatt 2: .pdf, Eingabedatei zu Aufgabe 2: bb4.txt
    Abgabe: Donnerstag, 28.04.2005, in der Übung
  • 1. Projektaufgabe - Teil A - : .pdf
    Abgabe: Montag, 09.05.2005, in der Übung
  • Übungsblatt 3: .pdf
    Abgabe: Mittwoch, 04.05.2005, in der Vorlesung
  • Übungsblatt 4: .pdf, Turingmaschine zu Aufgabe 2: 4-TM.jff
    Abgabe: Donnerstag, 12.05.2005, in der Übung
  • Übungsblatt 5: .pdf
    Abgabe: Donnerstag, 19.05.2005, in der Übung
  • 1. Projektaufgabe - Teil B - : .pdf
    Testdateien: Test_PA1.tar enthält 10 Dateien mit Zielformeln und Prämissen
    Abgabe: Donnerstag, 02.06.2005, in der Übung
  • Übungsblatt 6: .pdf
    Abgabe: Donnerstag, 26.05.2005, in der Übung
  • Übungsblatt 7: .pdf
    Abgabe: Donnerstag, 02.06.2005, in der Übung
  • Übungsblatt 8: .pdf
    Abgabe: Donnerstag, 09.06.2005, in der Übung
  • Übungsblatt 9: .pdf
    Abgabe: Donnerstag, 16.06.2005, in der Übung
  • Übungsblatt 10: .pdf
    Abgabe: Donnerstag, 23.06.2005, in der Übung
  • Übungsblatt 11: .pdf
    Abgabe: Donnerstag, 30.06.2005, in der Übung
  • 2. Projektaufgabe: .pdf
    Testdateien: TestSAT1 TestSAT2 TestSAT3 TestSAT4
    Benchmark-Dateien SATCompX: SATComp1 SATComp2 SATComp3 SATComp4 SATComp5 SATComp6
    alle Dateien als .tar-File
    Abgabe: Bachelorstudenten: Montag, 11.07.2005, Diplomstudenten: Donnerstag, 14.07.2005
  • Übungsblatt 12: .pdf
    Abgabe: Donnerstag, 07.07.2005, in der Übung
  • Aufgabensammlung: .pdf
  • Aufgabensammlung II: .pdf
Projects: