Art und Inhalt |
| Title: |
Algorithm, Logic, Complexity |
| Lecturer: |
Prof. Dr. Rüdiger Reischuk, Prof. Dr. Maciej Liskiewicz |
| Classification: |
Master Entrepreneurship in digitalen Technologien, Vertiefungsmodul, 2. und/oder 3 Fachsemester
Master Informatik, Vertiefungsmodul, 2. und/oder 3. Fachsemester
Dieses Modul besteht aus Vorlesung und Seminar:
Seminar 2 SWS wahlweise:
im Sommersemeser 2016 "Computing beyond Turing", Fr. 10-12h
oder
im Wintersemester 2016 Oberseminar Theoretische Informatik
Prüfung mündlich Ende des SoSe 2016 oder WS 2016, Termine nach individueller Vereinbarung |
| Content: |
- Problemreduktion und Maschinensimulation
- Komplexitätsklassen-Hierarchie
- Beweissysteme
- Schaltkreiskomplexität
- Kommunikationskomplexität
- Algorithmisches Lernen
- Algorithmische Spieletheorie
- 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
- M.J. Kearns, V.V. Vazirani: An Introduction to Computational Learning Theory - MIT Press, 1997
- T.M. Mitchell: Machine Learning - WCB McGraw-Hill, 1997
- D. Kozen: Theory of Computation - Springer, 2006
|
Lecture |
| Lecturer |
Prof. Dr. Rüdiger Reischuk, , Prof. Dr. Maciej Liskiewicz |
| Credits |
4 SWS |
| Hours |
|
Exercises |
| Assistent |
Max Bannach M.Sc. |
| Credits |
2 SWS |
| Hours |
|
