| WWU Münster Mathematik: Logik |
Wintersemester 2004/2005
| Veranstalter: | Prof. Dr. W. Pohlers, Zi. 810 (Sekretariat Frau Pfeifer, Zi. 811),
Ch. Duchhardt, Zi. 812, Tel. 83-33766 |
| Zeit der Vorlesung: | Montag und Donnerstag 13-15 Uhr, M2 (getauscht) |
| Beginn: | Die erste Vorlesung findet am Montag, den 11.10. statt. |
| Belegnummern: | Vorlesung: 102.499, Übungen: 102.503 |
| Inhalt: | Das Anliegen der Vorlesung ist eine Einführung in die Grundlagen der Theorie der
Berechenbarkeit und des deduktiven Schließens. Wir beginnen mit dem Studium des Begriffes der 'Berechenbarkeit'. Das geschieht zunächst mit Hilfe eines abstrakten Maschinenbegriffes an Hand dessen wir den Begriff des Algorithmus präzisieren. Wir kommen dann zu einer mathematisch präzisierten Beschreibung berechenbarer Funktionen an Hand derer wir die Theorie der Berechenbarkeit entwickeln. Wir führen die Notationen 'Turingmaschine', 'Registermaschine' und 'primitiv rekursive und mu-rekursive Funktionen' ein und studieren deren Zusammenhang. Zielpunkte sind der 'Normalformensatz' von Kleene, der 'Rekursionssatz' und der 'Satz von Rice'. Im zweiten Teil studieren wir den Begriff der 'formalen Ableitbarkeit' der auf der Stufe des logischen Schließens, dem Begriff der Berechenbarkeit entspricht. Wir kommen so zu einer Einführung in die Theorie der Prädikatenlogik der ersten Stufe. Zielpunkte sind hier der Vollständigkeitssatz, der besagt, dass sich logisches Schließen kalkülisieren lässt, und die Unentscheidbarkeit der Prädikatenlogik, die besagt, dass die logische Gültigkeit einer Aussage nicht maschinell entschieden werden kann. |
| Literatur: | - W. Pohlers, T. Glaß: 'An Introduction to Mathematical Logic', Skript, Münster, 1992
(Link siehe unten), - W. Pohlers: Handbuch der Informatik, Mathematische Grundlagen der Informatik, Oldenbourg, 1993 (Link siehe unten), - H. Rogers, Jr.: Theory of Recursive Functions and Effective Computability, MacGraw Hill, 1967. |
| Übungen: | Mittwoch, 9-11, SR 8 bei Dirk Schröder, Mittwoch, 11-13, SR 8 bei Arthur Penkala, Mittwoch, 13-15, SR 8 bei Benjamin Claverie und Mittwoch, 15-17, SR 8 bei Benjamin Claverie. |
| Übungsschein: | Einen Übungsschein erhält man durch: - aktive Teilnahme an den Übungen (u.a. mehrfaches Vorrechnen), - das Erlangen von mindestens 50% der möglichen Punkte aus den Übungsaufgaben, - das Bestehen der Abschlußklausur. |
| Aufgaben: | Die Aufgaben werden jeweils montags in der Vorlesung ausgegeben, die Lösungen können
dann bis zum folgenden Montag, 13:15 Uhr, in die Briefkästen 86-89 geworfen werden. Bis zu zwei Teilnehmer dürfen zusammen abgeben, wobei jeder einen relevanten Teil verantworten (insbesondere vorrechnen können) muss. Die regelmäßige Beteiligung jedes Gruppenmitglieds muss auch an der Handschrift auf den abgegebenen Zetteln erkennbar sein. |
| Tutorium: | Findet (mehr oder weniger regelmäßig) dienstags zwischen 17 und 19 Uhr statt (M1). |
| Klausur: | Am Dienstag, den 8.2.05, von 9-12 Uhr. |
| Nachklausur: | Findet am 16.4.05 (der erste Samstag im Semester), 9-12 Uhr, im M3 statt. Arthur Penkala bietet dazu eine Reihe von Fragestunden an. Die nächste findet statt am Dienstag, 12.4., 17 Uhr (ct), 8. Stock. |
| Anmeldung: | Diplom-Informatiker müssen sich zur Klausur und zur Nachklausur anmelden: Sekretariat Frau Pfeifer, Zi. 811. |
| Bei Problemen: | Sprechen Sie die Veranstalter an oder schicken Sie eine Email an Christoph Duchhardt. |
Hier gehts zum Eintrag der
Vorlesung bzw. der Übungen im Vorlesungsverzeichnis.
Zum Herunterladen:
 |
Ein Skript zur (gesamten) Vorlesung (W. Pohlers, T. Glaß: An Introduction to Mathematical Logic), |
|
ein Buch zur Berechenbarkeitstheorie (W. Pohlers: Handbuch der Informatik, Mathematische Grundlagen der Informatik) |
|
und ein möglichst aktuelles Skript zur Vorlesung als pdf-Dateil oder als ps-Datei , das simultan zur Vorlesung fortgeschrieben wird, und daher eine fortwährende Baustelle darstellt. |
|
Der Merkzettel zu den Übungen als ps-Datei oder als pdf-Datei. |
|
Die Knobelaufgabe mit der Spottdrossel als ps-Datei oder als pdf-Datei. |
|
Sämtliche Übungszettel als ps-Datei oder als pdf-Datei. |
|
Der Bogen zur Klausurvorbereitung als ps-Datei oder als pdf-Datei. |
 |
Falls es noch jemanden interessiert: Ein Lösungsvorschlag für die Chomsky-Sprachen-Aufgabe als ps-Datei oder als pdf-Datei. |
