Vorlesung "Theoretische informatik II"

INLP02 - 4.1.11 V2 b In c CV InsMSc CVMSc WIMSc - KLIPS
Jun.-Prof. Dr. Bernhard Beckert

INLP02 - 4.1.12 Ü2 b In c CV InsMSc CVMSc WIMSc
Ulrich Koch

Aktuelles

14.03.08: Die 2. Teilklausur mit Musterlösung steht auf der Webseite zur Verfügung. Die Ergebnisse sind per Email versandt.
18.02.08: Die Musterlösung zum 12. Übungsblatt und Material zur Definition der Fakultätsfunktion im Lambda-Kalkül stehen zur Verfügung.
13.02.07: Die Ergebnisse der Evaluation finden sich hier: Details in Evali
13.02.08: Die Folien zur gestrigen Vorlesung stehen zur Verfügung
13.02.08: Das 12. Übungsblatt und die Musterlösung zum 11. Übungsblatt stehen zur Verfügung.
06.02.08: Bitte beteiligen Sie sich an der Vorlesungsevaluation: evali
06.02.08: Die Folien zur gestrigen Vorlesung stehen zur Verfügung
04.02.08: Das 11. Übungsblatt steht zur Verfügung.
03.02.08: Ergebnis der Evaluation im Rahmen des Lehrpreiswettbewerbs des Landes Rheinland-Pfalz: PDF. Die Evaluation des Fachbereichs läuft noch, hier teilnehmen: evali
30.01.08: Die Musterlösungen zum 9. und 10. Übungsblatt stehen zur Verfügung
29.01.08: Die Folien zur heutigen Vorlesung stehen zur Verfügung
25.01.08: Achtung! Neuer Klausurtermin: Die 2. Teilklausur ist auf Donnerstag, den 28.02.08, 10 Uhr c.t., Raum D028, verschoben (um zu vermeiden, dass sie am gleichen Tag wie die Klausur "CV-Integration" stattfindet).
25.01.08: Das 10. Übungsblatt steht zur Verfügung.
25.01.08: Die Folien zur Vorlesung am 22.01. stehen zur Verfügung
18.01.08: Das 9. Übungsblatt steht zur Verfügung.
13.01.08: Das 8. Übungsblatt steht zur Verfügung.
09.01.08: Die Musterlösung zum 7. Übungsblatt steht zur Verfügung
09.01.08: Die Folien zur gestrigen Vorlesung stehen zur Verfügung
04.01.08: Das 7. Übungsblatt steht zur Verfügung.
03.01.08: Die 2. Teilklausur findet Dienstag, 19.02.08, 14 Uhr c.t., Raum D028, statt. Dazu muss man sich nicht gesondert anmelden, sondern es gelten alle als angemeldet, die sich zur 1. Teilklausur angemeldet hatten.
03.01.08: Die Nachklausur findet am Dienstag, 25.03.08, 14 Uhr c.t., Raum E011, statt. Dazu kann man sich über MeToo bis Sonntag, den 23.03.08 anmelden.
03.01.08: Die Klausureinsicht zur 1. Teilklausur findet am Dienstag, dem 8.1.08, nach der Vorlesung (16 Uhr) in meinem Büro (B218) statt.
18.12.07: Die Folien zur heutigen Vorlesung stehen zur Verfügung
15.12.07: Mangels Beteiligung findet ab sofort die 2. Übungsgruppe um 18 Uhr nicht mehr statt.
15.12.07: Die 1. Teilklausur mit Musterlösung steht auf der Webseite zur Verfügung. Die Ergebnisse werden Anfang der kommenden Woche per Email versandt.
15.12.07: Die Musterlösung zum 6. Übungsblatt steht zur Verfügung
05.12.07: Die erste Teilklausur findet am Dienstag, dem 11.12.07, um 14 Uhr s.t., im Hörsaal E011 statt.
05.12.07: Das 6. Übungsblatt steht zur Verfügung.
05.12.07: Die Musterlösung zum 5. Übungsblatt steht zur Verfügung
05.12.07: Die Folien zur gestrigen Vorlesung stehen zur Verfügung
05.12.07: Zwei Dateien zum in der Übung vorgestellten Beweis, dass die Berechnung der Fibonacci-Zahlen primitiv rekursiv ist, stehen zur Verfügung
28.11.07: Die erste Teilklausur findet am Dienstag, dem 11.12.07, um 14 Uhr s.t. statt (der Raum wird noch bekannt gegeben). Zu den Teilklausuren können Sie sich bis Sonntag, dem 09.12.07, unter MeToo anmelden (und auch wieder abmelden): MeToo-Anmeldung

Frühere aktuelle Informationen

Inhalt

Die Vorlesung vermittelt vertieftes Verständnis formaler Konzepte und der beweisbaren Grenzen des Berechenbaren.

Literatur

Grundlage der Vorlesung ist folgendes Buch:

cover
Katrin Erk, Lutz Priese.
Theoretische Informatik: Eine umfassende Einführung.
2. Auflage. Springer-Verlag, 2002.

Folien

Die Folien werden jeweils nach der Vorlesung hier zur Verfügung gestellt.

Vollständige Foliensätze zu den Vorlesungsteilen

Teil I: Einführung bildschirm - druck - 4 on 1
(die Folien zu "Wiederholung: Turing-Maschinen und Turing-Berechenbarkeit" sind ein Auszug der Folien zu diesen Themen aus Theoretische Informatik I)
Teil II: Registermaschinen bildschirm - druck - 4 on 1
Teil III: Rekursive Funktionen bildschirm - druck - 4 on 1
Teil IV: Lambda-Kalkül bildschirm - druck - 4 on 1
Teil V: Komplexitätstheorie bildschirm - druck - 4 on 1
Teil VI: Berechenbarkeit bildschirm - druck - 4 on 1

Folien zu den einzelnen Vorlesungen

23.10.07 bildschirm - druck - 4 on 1
30.10.07 bildschirm - druck - 4 on 1
06.11.07 bildschirm - druck - 4 on 1
13.11.07 bildschirm - druck - 4 on 1
20.11.07 bildschirm - druck - 4 on 1
27.11.07 bildschirm - druck - 4 on 1
04.12.07 bildschirm - druck - 4 on 1
18.12.07 bildschirm - druck - 4 on 1
08.01.08 bildschirm - druck - 4 on 1
15.01.08 keine Folien (nur Tafel benutzt) - Material dazu
22.01.08 bildschirm - druck - 4 on 1
29.01.08 bildschirm - druck - 4 on 1
05.02.08 bildschirm - druck - 4 on 1
12.02.08 bildschirm - druck - 4 on 1

Übungsblätter

Jede Woche erscheint ein Übungsblatt (hier im Web). Die Aufgaben werden in den Übungen der darauffolgenden Woche besprochen.

1. Übungsblatt (wird in den Übungen am 07.11. besprochen) - Musterlösung, Hinweise zur Umsetzung von LOOP-Programmen in Java/C/C++
2. Übungsblatt (wird in den Übungen am 14.11. besprochen) - Musterlösung, Ergänzung zu Registermaschinen
3. Übungsblatt (wird in den Übungen am 21.11. besprochen) - Musterlösung, Implementierung einiger primitiv rekursiver Funktionen in Haskell: PR.hs, vorl20071113.hs, sqrt2.hs
4. Übungsblatt (wird in den Übungen am 28.11. besprochen) - Musterlösung, Dateien zum in der Übung vorgestellten Beweis, dass die Berechnung der Fibonacci-Zahlen primitiv rekursiv ist: fib-pr.pdf, fib.hs
5. Übungsblatt (wird in den Übungen am 05.12. besprochen) - Musterlösung, zuBlatt5.hs
6. Übungsblatt (wird in den Übungen am 12.12. besprochen) - Musterlösung
7. Übungsblatt (wird in den Übungen am 09.01. besprochen) - Musterlösung
8. Übungsblatt (wird in der Übung am 16.01. besprochen) - Musterlösung, Funktion pred in Haskell: pred.hs
9. Übungsblatt (wird in der Übung am 23.01. besprochen) - Musterlösung
10. Übungsblatt (wird in der Übung am 30.01. besprochen) - Musterlösung
11. Übungsblatt (wird in der Übung am 06.02. besprochen) - Musterlösung
12. Übungsblatt (wird in der Übung am 13.02. besprochen) - Musterlösung

Die Lösungen können - müssen aber nicht - schriftlich abgegeben werden. Das birgt die Gefahr in sich, dass sich die Studenten nicht mit den Aufgaben beschäftigen, sondern im schlimmsten Falle lediglich in der nächsten Übung die Lösungen unverstanden abschreiben. Das führt nicht zum Erfolg! Bitte lösen Sie die Aufgaben selbständig, am besten in kleinen(!) Lerngruppen von zwei, allenfalls drei Teilnehmern. So sind Sie für die Klausuren gut vorbereitet.

Scheinerwerb (Klausuren)

Teilklausuren während des Semesters

Während des Semesters gibt es zwei kurze Teilklausuren (von je 45 Minuten Dauer plus 10 Minuten Einlesezeit). Diese finden statt:
- Dienstag, 11.12.07, 14 Uhr c.t., Raum E011
  1. Teilklausur mit Musterlösung
- Donnerstag, 28.02.08, 10 Uhr c.t., Raum D028 (Achtung: Neuer Termin!)
  2. Teilklausur mit Musterlösung
Zu den Teilklausuren kann man sich bis Sonntag, den 09.12. über MeToo anmelden (und auch wieder abmelden). Die Anmeldung ist verbindlich (Nichtteilnahme trotz Anmeldung = 0 Punkte). Sie gilt für beide Teilklausuren zusammen.
Wer 50% der insgesamt in den beiden Teilklausuren zu erzielenden Punkte erreicht, hat die Prüfung insgesamt bestanden und erhät den Schein. Die Note richtet sich nach der insgesamt erreichten Punktzahl.
Die Wiederholung einzelner Teilklausuren ist nicht möglich. Ein Freiversuch kann nur für alle Teilklausuren zusammen gesetzt werden.
Zu den Klausuren sind keine Hilfsmittel (wie Bücher oder Skripten) zugelassen.

Nachklausur zum Ende der Semesters

Am Ende des Semesters (Ende März 2008) findet eine Nachklausur statt:
Dienstag, 25.03.08, 14 Uhr c.t., Raum E011
Nachklausur mit Musterlösung
Zu dieser kann man sich über MeToo bis Sonntag, den 23.03.08 anmelden.
Die Nachklausur hat den gleichen "Wert" wie die beiden Teilklausuren zusammen (90 Minuten Dauer). Wer sie besteht, bekommt den Schein. Die Note richtet sich dann nach der in der Nachklausur erzielten Punktzahl.
Achtung: Die Anmeldung zu und Teilnahme an der ersten Prüfung (also den Teilklausuren während des Semesters) ist Voraussetzung für die Teilnahme an der Nachklausur. Nur wer diese nicht bestanden oder einen Freiversuch gesetzt hat, darf an der Nachklausur teilnehmen. Außerdem darf an der Nachklausur teilnehmen, wer an einer Prüfung zu "Theoretische Informatik II" in frühren Semestern teilgenommen und diese nicht bestanden oder einen Freiversuch gesetzt hat.

Zeit und Ort

Vorlesung

Dienstags, 14 Uhr c.t., Raum B016

Die Vorlesung beginnt in der ersten Vorlesungswoche. Sie findet erstmals am 23.10.07 statt.

Übung

Gruppe A: Mittwochs, 16 Uhr c.t., Raum E112
Gruppe B: Mittwochs, 18 Uhr s.t., Raum B013 - findet nicht mehr statt

Die Übung beginnt in der zweiten Vorlesungswoche.
Bitte melden Sie sich zu den beiden Übungsgruppen unter MeToo an (bis Sonntag, den 28.10.07).

Newsgroup

Newsgroup zur Vorlesung: infko.theoinf

Bernhard Beckert