Perlen der Informatik (WS 2008/09)

TU München - Fakultät für Informatik
Software- and Systems Engineering Research Group

Vorlesung | Wintersemester 2008/09
Perlen der Informatik
Prof. Tobias Nipkow

Bereich:	Spezialvorlesung im Grundstudium: 2 Std. (+2Ü)
Zeit und Ort:	Fr. 10:15 - 11:45, Raum: MI 00.07.11
Beginn:	17.10.2008
Übungstermin:	Mi. 14:15 - 15:45, Raum: MI 01.11.018 ("Konrad Zuse"), Begin: 22.10.2008
Tutor:	Dr. Stefan Berghofer
Mailingliste:	https://mailmanbroy.informatik.tu-muenchen.de/mailman/listinfo/perlen08

News:

Am 17.12.2008 und 21.1.2009 findet die Übung im Raum MI 00.11.038 ("John von Neumann") statt.

Inhalt:

In der Vorlesung werden ausgewählte Themen aus verschiedenen Bereichen der (hauptsächlich theoretischen) Informatik angesprochen:

Berechenbarkeit und Entscheidbarkeit
Hilberts 10. Problem
Komplexität: P und NP
Prolog

Ziel der Vorlesung ist es, in enger Interaktion mit den teilnehmenden Studierenden bereits zu einem sehr frühen Stadium einen Bezug zu aktuellen Forschungsthemen herzustellen. Eine aktive und engagierte Mitarbeit ist unbedingte Teilnahmevoraussetzung.

Voraussetzungen: keine

Literatur:

Skript
Uwe Schöning. Theoretische Informatik kurzgefasst.
Uwe Schöning. Perlen der Informatik.
Uwe Schöning. Logik für Informatiker.
Christos Papadimitriou. Computational Complexity.
W. F. Clocksin and C. S. Mellish. Programming in Prolog. Springer-Verlag, New York, Third, Revised and Extended edition, 1987
L. Sterling and E. Shapiro. The Art of Prolog. MIT Press, Cambridge, Massachusetts, 1986.

Übungsblätter

Hinweise zu ML

Die Binaries für den PolyML Compiler finden Sie hier (für x86-Linux). Er kann mit
polyml
gestartet werden.
Beispielprogramme können mit dem use Befehl eingelesen werden, also z.B.
use "blatt1.ML";
Der Compiler kann mit <CTRL>-d wieder verlassen werden.
Kurzeinführung in ML
ML-Buch von Robert Harper

Hinweise zu Prolog

Zum Arbeiten mit Prolog empfiehlt sich das frei erhältliche SWI-Prolog System. Es wird nach der Installation mit pl gestartet und mit CTRL-d beendet.
Unter SWI-Prolog kann die Größe der ausgegebenen Ausdrücke mit
```
  set_prolog_flag(toplevel_print_options, [max_depth(<Tiefe>)]).
```
verändert werden.
Prolog-Files (die mit dem Suffix .pl enden müssen) können mittels
```
  [<Filename>].
```
geladen werden, wobei <Filename> den Filename ohne das Suffix .pl bezeichnet, z.B.
```
  [einfuehrung].
```
Weitere Hinweise sind in der Einführung zu finden (siehe auch das dazugehörige Prolog-File).