Art und Inhalt |
| Title: |
Modul: Computational Complexity |
| Lecturer: |
Prof. Dr. Rüdiger Reischuk |
| Classification: |
Master Entrepreneurship in digitalen Technologien, Vertiefungsmodul, 2. und/oder 3 Fachsemester
Master Informatik, Vertiefungsmodul, 2. und/oder 3. Fachsemester
|
| Content: |
- Strukturelle und deskriptive Komplexitätstheorie
- Kommunikationskomplexität
- Schaltkreiskomplexität
- Algorithmische Spieltheorie
- Nichtstandardberechnungsmodelle
|
| Competence: |
- Tieferes Verständnis der Konzepte und Methoden des Algorithmenentwurfs und der Komplexitätsanalyse
- Fähigkeit, algorithmische Probleme bezüglich ihrer Komplexität einzuordnen und daraus Lösungsmethoden abzuleiten
- Fähigkeit, komplexe Problemstellungen adäquat formal modellieren zu können
- Bedeutung von unteren Komplexitätsschranken für reale
Probleme verstehen
|
| Literature: |
- R. Reischuk: Einführung in die Komplexitätstheorie - Teubner, 1990
- S. Arora, B. Barak: Computational Complexity - Cambridge UP 2009
- C. Papadimitriou: Computational Complexity - Addison-Wesley, 1994
|
Lecture |
| Lecturer: |
Prof. Dr. Rüdiger Reischuk |
| Umfang: |
2 SWS, ECTS-Credits: 4 |
| Dates: |
Thu. 10:00h–12:00h, Seminarroom Cook & Karp
|
Exercise |
| Assistent: |
Max Bannach M.Sc. |
| Umfang: |
2 SWS |
| Dates: |
Wed. 09:00 – 10:00, ITCS seminar room 2021
|
