Veranstaltungsart und -inhalt

• 1. Quantenalgorithmen (Quantum Computing)

  Ein Impuls für die explosive Entwicklung des Quantum Computing gab es 1994 Peter Shor, der entdeckte, dass man mit Hilfe von Quantenalgorithmen effizient große Zahlen faktorisieren kann! Die besten heute bekannten konventionellen Algorithmen benötigen zum Faktorisieren einer Zahl exponentiell viel Zeit. Hat z.B. die Zahl N eine Dezimaldarstellung mit 65 bzw. 400 Ziffern, dann braucht der konventionelle Algorithmus 89 Tage bzw. etwa 10^10 Jahre. Dies ist das Alter des Universums! Es wird vermutet, dass es keinen (konventionellen) Algorithmus gibt, der effizient große Zahlen faktorisiert. Dies würde bedeuten, dass das RSA-System mit konventionellen Rechnern nicht zu brechen wäre. Der Shor-Algorithmus braucht nur 3 (statt 10^10) Jahre, um eine Zahl mit 400 Ziffern zu faktorisieren!

  In diesem Bereich diskutieren wir die wichtigsten Konzepte und Methoden des Quantum Computing (u.a. den berühmten Algorithmus von Peter Shor), Suche in Datenbanken, Quantenkryptographie und Quantennetzwerke.

• 2. Algorithmische Spieltheorie

  Um das Internet und seine Möglichkeiten zu verstehen und analysieren, verwenden Informatiker Konzepte und Methoden aus Wirtschaft und Spieltheorie. In den letzten zehn Jahren hat sich die Forschung intensiv mit folgenden Fragen beschäftigt: Welche spieltheoretische Werkzeuge anwendbar für die Computersysteme sind? Wie weit ist die Leistung eines Systems von Optimalität durch den Konflikt der Interessen der Nutzer und Administratoren entfernt? Wie können wir ein System entwerfen, dessen Leistung robust in Bezug auf die potenziellen Interessenkonflikte innerhalb des Systems ist?

  In diesem Teil werden wir einige der grundlegenden Probleme an der Schnittstelle von Informatik und Spieltheorie, mit dem Schwerpunkt auf Algorithmen und Komplexität diskutieren u.a. Algorithmen für die Gleichgewichte, die Komplexität der Gleichgewichte und Fixpunkte, das Lernen in Spielen, und der Preis der Anarchie.

• Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000
• Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (eds.): Algorithmic Game Theory, Cambridge University Press, September 2007

Seminar