In der Vorlesung werden grundlegende Begriffe, Prinzipien und Methoden aus der
Algorithmentheorie und der Komplexitätstheorie behandelt. Die Vorlesung wird
durch Übungen begleitet. Zu den behandelten Themen gehören:
| • | Begriff des Algorithmus und des Kalküls |
| • | Turingmaschinen und Registermaschinen |
| • | Partiell Rekursive Funktionen |
| • | Churchsche Hypothese und Äquivalenzsätze |
| • | Kleenesche Normaltheoreme |
| • | berechenbare Numerierungen |
| • | Rekursiv aufzählbare und entscheidbare Mengen |
| • | Halteproblem |
| • | Elemente der Komplexitätstheorie |
Vorlesung: (Andreas Maletti) Donnerstag 17:15 - 18:45, Hs 5 (ab 12.04)
| • Übung a: | Dienstag | 9:15 - 11:45 (A-Woche), | SG 3-11 (ab 10.04.) | Grabolle |
| • Übung b: | Dienstag | 9:15 - 11:45 (B-Woche), | SG 3-11 (ab 17.04.) | Grabolle |
| • Übung c: | Mittwoch | 9:15 - 11:45 (A-Woche), | SG 3-14 (ab 11.04.) | Schulze |
| • Übung d: | Mittwoch | 9:15 - 11:45 (B-Woche), | SG 3-14 (ab 18.04.) | Schulze |
| • Übung e: | Donnerstag | 9:15 - 11:45 (A-Woche), | SG 3-14 (ab 12.04.) | Grabolle |
| • Übung f: | Donnerstag | 9:15 - 11:45 (B-Woche), | SG 3-14 (ab 19.04.) | Grabolle |
A-Wochen: ab Montag 09.04. / 23.04. / 07.05. / 21.05. / 04.06. / 02.07. / 16.07.
B-Wochen: ab Montag 16.04. / 30.04. / 14.05. / 28.05. / 11.06. / 09.07. / 24.07.