Titel: Algorithmen und Komplexität
Art: 2V+2Ü
Zuordnung: Theoretische Informatik/Foundations of Computing
CreditPoints: 6
Zeit: Do 9:50h-11:20h (Vorlesung) , Mo 13:45-15:00h (Übung)
Ort: 4.3.01, S4|14 (V), 4.3.01, S4|14 (Ü)
Aktuell:
Kapitel 5 des Skripts über Kolmogorov-Komplexität ist jetzt online.
Die Übung am 2.Juli entfällt.
Inhalt
Die Vorlesung „Algorithmen und Komplexität“ betrachtet
- Algorithmenmodelle (Turing-Maschinen, Quantenalgorithmen,…),
- Ein-/Ausgabeverhalten (Approximationsverfahren, Online-Algorithmen,…), sowie
- Ressourcenkomplexität (parametrisierte Komplexität, Beschreibungslänge,…).
Speziell werden die Themen parametrisierte Komplexität, Approximationsalgorithmen Online-Algorithmen, Quantenalgorithmen,, parallele Algorithmen und Kolmogorov-Komplexität betrachtet.
Skript
Zugriffsgeschützter Absatz: Melden Sie sich an, um diesen Absatz zu sehen.
Übungen
Zugriffsgeschützter Absatz: Melden Sie sich an, um diesen Absatz zu sehen.
Lösungen
Zugriffsgeschützter Absatz: Melden Sie sich an, um diesen Absatz zu sehen.
Literatur
Begleitend zur Vorlesung gibt es ein Skript. Darüber hinaus sind folgende Bücher zum punktuellen Vertiefen zu empfehlen:
- Arora, Barak: Computational Complexity: A Modern Approach, 2007 (auch online erhältlich).
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 2009.
- Motwani, Raghavan: Randomized Algorithms, 1995.
- Hochbaum: Approximation Algorithms for NP-hard Problems,1996.
- Li, Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, 1997.
