Inhalt

Fortgeschrittene Themen des Algorithmenentwurfs mit wechselnden Schwerpunkten. Der Inhalt ist nicht im Vorhinein bestimmt, sondern wird in jedem Semester neu festgelegt.

Themen für dieses Semester:

-- Komplexitätsklasse PSPACE mit Beispielen

-- Schnelle Fouriertransformation

-- Schnelle Zahlenmultiplikation

-- Kryptographie und RSA-Algorithmus

-- Approximationsalgorithmen

-- FPT (fixed parameter tractability)

-- Algorithmen für Quantencomputer (bei mindestens 2-3 an diesen Vorträgen interessierten Teilnehmern)

Zielgruppe

Master-Studierende der Informatik oder Mathematik

Empfohlene Vorkenntnisse

Vorlesung "Höhere Algorithmik" oder vergleichbare Veranstaltung

Literatur

Cormen/Leisersonj/Rivest/Stein, Introduction to Algorithms

Kleinberg/Tardos, Algorithm Design

Knuth, The Art of Computer Programming, Vol. 2

Nielsen/Chuang, Quantum Computation and Quantum Information

und Originalarbeiten

Themenvergabe und Termine

Themen werden in der ersten Sitzung (Di 16.10., 14 hct) vergeben und die Vorträge (70 Min.) finden in den Monaten November, Dezember 2018, sowie eventuell 1. Häfte Januar 2019 statt. Dies geschieht zu den regulären Terminen (Di 14 - 16 ) mit möglicherweise einigen Sonderterminen.

Es ist keine längere Seminararbeit anzufertigen, sondern lediglich eine 4-seitige Inhaltsangabe, die zu kopieren und vor dem Vortrag an die Teilnehmer zu verteilen ist.

Schedule

Each participant will give two 70-minute lectures (blackboard or beamer or both) with subsequent discussions.

Tue Oct. 30 and Tue Nov. 6, 14:15 Room 210, Arnimallee 3-5
Simon Auch:     Complexity, Classes P and NP

Sat Dec. 1, 10:15 and 11:50, Room 055, Takustr. 9
Theresa Kiszler:    The Fast Fourier-Transform

Sat Dec. 1, 14:15 and 15:50, Room 055, Takustr. 9
Mara Kortenkamp:   Public-Key Cryptosystems and RSA

Sat Dec. 8, 10:15 and 11:50, Room 055, Takustr. 9
Ece Asimet Sanin:    Quantum Computing 1

Sat Dec. 8, 14:15 and 15:50, Room 055, Takustr. 9
Felix Oertel:             Quantum Computing 2