Seminar Theoretische Informatik - Rekursiontheorie
- Seminar, Prof. Dr. Kreitz, Dr. rer. nat. Richter, Di. 10:15-11:45, 3.06.S15
Im Seminar "Theoretische Informatik" werden vertiefende Themen der theoretischen Informatik und angrenzender Bereiche der Mathematik anhand von ausgewählter Literatur besprochen.
Das Thema des SS 2011 ist ein Teilbereich der Berechenbarkeitstheorie und speziell der sogenannten "Rekursionstheorie". Wir werden das Buch "Theory of Recursive Functions and Effective Computability" von H. Rogers besprechen, das einen Schwerpunkt auf das Thema "Grade der Unlösbarkeit" legt. Dieses Thema ist theoretisch anspruchsvoll und deshalb nur für Bachelorstudenten ab dem 5. Fachsemester und Masterstudenten zu empfehlen.
Alle organisatorischen Details werden in der ersten Veranstaltung am 19. April besprochen.
Veranstaltungen
Teilnehmer sollen in ihren Vorträgen die zentralen Begriffe ihres Themas, die zugehörigen Aussagen und deren Konsequenzen ausführlich darstellen und mit Hilfe von Beispielen (und eventuellen Lösungen der Übungsaufgaben) erklären. In den Seminaren soll es vor allem darum gehen, die Zuhörer in das jeweilige Thema einzuführen, weniger darum eine möglichst glatte Präsentation abzuliefern. Das Erstellen von Folien ist nicht unbedingt notwendig, jedoch können vorbereitete Materialien wie Folien oder Handouts auf der Webseite bereitgestellt werden.
Im Anschluss an den Vortrag, ggf. auch während des Vortrags findet eine inhaltliche Diskussion des Themas statt, die von der/dem Vortragenden geleitet wird. Von allen Teilnehmern wird eine aktive Beteiligung an dieser Diskussion erwartet, was voraussetzt, daß auch die Zuhörer die betreffenden Passagen des Textes gelesen haben.
Hier die geplante Verteilung der Vorträge (Änderungen, insbesondere der Termine, vorbehalten):
| Thema |
Kap. |
Vortragende(r) |
Datum |
|---|---|---|---|
| Einführung rekursive Funktionen |
1-5 | C.Kreitz | 10.5.11, 17.5.11 |
| Reduzierbarkeit, kreative Mengen |
6-7 | C.Kreitz |
24.5.11, 31.5.11 |
| truth table reduction, einfache Mengen |
8 | M.Görner | 31.5.11, 7.6.11 |
| Rekursionssatz |
11 | M.Frank | 7.6.11 .... |
| Aufzählbare Mengen als Verband |
12 | E.Richter | 14.6.11 |
| Grade von Unlösbarkeit |
13 | A.Melzer | 21.6.11 |
| Artithmetische Hierarchie |
14-15 | C.Gerlitz/M.Dittmann | 28.6.11, 5.7.11 |
| Analytische Hierarchie |
16 | T.Richter | 12.7.11 |
Leistungsbewertung
Grundlage für die Leistungsbewertung ist hauptsächlich die Qualität der Vorträge. Dabei ist das wichtigste Kriterium, wie verständlich und sorgfältig die Darstellung der entsprechenden Inhalte war. Außerdem gelten die üblichen Regeln wissenschaftlichen Arbeitens wie Fairness und vollständige Quellenangaben. Neben Anwesenheit und Aufmerksamkeit gehört zu einer aktiven Teilnahme auch ein sichtbares Interesse am Thema und die Bereitschaft Fragen zu stellen bzw. zu beantworten. Zugunsten einer umfangreichen Vorbereitung auf die Themen wird auf das Anfertigen einer Ausarbeitung verzichtet.
Literatur
- Hartley Rogers, Jr. : Theory of Recursive Functions and Effective Computability, MIT Press Cambridge, 1967, ISBN:0-262-68052-1
- Notizen zu den Kapiteln 1-7
