Berechenbarkeit und Komplexität


Prof. Dr. Stefan Näher

Vorlesung im Grundstudium über 2 SWS mit Übungen über 2 SWS


Inhalt

Die Theorie der Berechenbarkeit kann als die älteste Disziplin der Informatik betrachtet werden. Ihr Ausgangspunkt ist die alte Frage, welche Probleme lösbar (oder berechenbar) sind und welche nicht. Um dies zu klären, muss zunächst der intuitive Begriff des Algorithmus formalisiert werden. Wir werden mehrere Konkretisierungen des intuitiven Algorithmenbegriffs kennenlernen und beweisen, dass sie alle im Wesentlichen die gleiche Leistungsfähigkeit haben. Schließlich werden wir beweisen, dass es Probleme (und sogar praktisch relevante) gibt, die algorithmisch nicht lösbar sind. Im zweiten Teil der Vorlesung beschäftigen wir uns mit der Frage, welche Probleme nicht nur prinzipiell, sondern auch praktisch lösbar sind. Dazu wird die realistische Forderung erhoben, dass nur ein bestimmter Aufwand (Rechenzeit, Speicherplatz, ...) zur Lösung des Problems eingesetzt werden kann. Wir werden Komplexitätsklassen (wie z. B. P und NP) einführen und untersuchen, welche Probleme zu den schwersten innerhalb einer gegebenen Klasse zählen.


Termine

Vorlesung:
Montag, 10-12 Uhr, HS 1
Übung:
Gruppe 1: Dienstag, 12-14 Uhr, E 45
Gruppe 2: Mittwoch, 10-12 Uhr, E 45


Literatur

[Meinel]
Meinel
Script zur Vorlesung "Berechenbarkeit und Komplexität"
Online-Script



Last modified on 2002-09-26
Email: Matthias Bäsken