Art und Inhalt |
| Titel: |
Algorithmik, Logik und Komplexität |
| Veranstalter: |
Prof. Dr. Rüdiger Reischuk, Prof. Dr. Maciej Liskiewicz |
| Einordnung: |
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 |
| Lehrinhalte: |
- Problemreduktion und Maschinensimulation
- Komplexitätsklassen-Hierarchie
- Beweissysteme
- Schaltkreiskomplexität
- Kommunikationskomplexität
- Algorithmisches Lernen
- Algorithmische Spieletheorie
- Nichtstandardberechnungsmodelle
|
| Qualifikationsziele: |
- 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
|
| Buchempfehlungen: |
- 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
|
Vorlesung |
| Dozent |
Prof. Dr. Rüdiger Reischuk, , Prof. Dr. Maciej Liskiewicz |
| Umfang |
4 SWS |
| Termine |
Di 14:00 – 16:00, Seminarraum ITCS 2021, Do. 10:00 – 12:00, Seminarraum Cook/Karp
|
Übung |
| Assistent |
Max Bannach M.Sc. |
| Umfang |
2 SWS |
| Termine |
Di 10:30 – 10:00, Seminarraum ITCS 2021
|
