50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Einführung in die Informatik IV


[ Art und Inhalt | Die Vorlesung | Die Übung ]
Script Teil 1 "Logik"
Folien zur Vorlesung
Grafiken zu Turingmaschinen
Backtracking

Art und Inhalt
Titel: Einführung in die Informatik IV
Veranstalter: Reischuk
Einordnung: 4. Sem. Diplom-Studiengang + Bachelor
Inhalt:

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
Buchempfehlungen:
  • [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
Klausuren:
  • 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
Aktuelles:

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:

Vorlesung
Veranstalter: Reischuk
Umfang: 4 SWS, 9 ECTS
Termine: Mi. 8.00h-10.00h, Raum T1/Transistorium und Fr. 8.00h-10.00h, H1

Übung
Veranstalter: Reischuk, Arpe
Umfang: 3 SWS
Termine: 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
Projektaufgabe: