Universität Ulm ,
Fakultät für Informatik
, Abteilung Theoretische Informatik
Ankündigung einer Lehrveranstaltung für das Hauptstudium im SS97
TITEL
Komplexitätstheorie
TYP
Vorlesung (4V + 2 Ü)
Zuordnung zu Kernfächern oder Vertiefungsgebieten:
Kernfach: Theoretische und mathematische Methoden der Informatik
Vertiefungsgebiet: Theoretische Informatik
Veranstalter
Prof. Dr. Uwe Schöning
Inhalt
Wie misst man die Komplexität eines algorithmischen Problems, eines Algorithmus oder einer Datenstruktur? Es sollen die Grundlagen dieser Fragestellungen besprochen werden. Einige Stichwörter zum Inhalt:
- Platz- und Zeitkomplexität
- vollständige Probleme
- das P-NP-Problem
- Zufalls-Algorithmen und Klassen
- Komplexitätstheoretische Begründung der Zufälligkeit
- parallele Algorithmen und Klassen
- Kommunikationskomplexität
- Anwendungen in der Kryptographie
Voraussetzungen
Theoretische Informatik II
Literatur
Vorlesungsskript
Computation Complexity von L. Lovász / P. Gács
Erhältlich über: Uni-Paderborn oder Kopiervorlage erhältlich
Geplante Folgeveranstaltungen
Thematische Ergänzungen/Fortsetzungen sind die Vorlesungen Algorithmen, Kryptographie, Schaltkreistheorie und andere Spezialvorlesungen