Seminar über "Algebraische Algorithmen/Komplexitätstheorie"

Beschreibung

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Vorlesung im SS05 vertieft und weiterführende Fragestellungen behandelt werden. Dabei sollen insbesondere auch Themen der Algebraischen Komplexitätstheorie bearbeitet werden. (Einige) mögliche Themen sind:

• Einführung in die Algebraische Komplexitätstheorie
• (Komplexitätsresultate für) kryptographische Verfahren
• Graphisomorphieproblem
• Primzahltest und Faktorisierung
• Einführung in die Computeralgebra
• Diskrete Fourier-Transformation: Algorithmik u. Anwendungen
• ...

Termine

Blockveranstaltung am Ende des WS 2005/06, nach Vereinbarung. Bei Fragen wenden Sie sich bitte an Stefan Porschen.

Vorbesprechung

Eine Vorbesprechung findet statt am 12. August 2005, 11.00 - 12.00 Uhr, Pohligstr. 1, Raum 616. In diesem Rahmen werden auch die Themen vergeben.

Voraussetzungen und Scheinerwerb

Voraussetzung (sinnvoll, nicht zwingend): Teilnahme an der Vorlesung im SS 2005. Scheinbedingung: Ausarbeitung eines Referats samt Vortrag (überwiegend mit Tafelanschrieb) von ca. 60 min Länge. Einordnung: B/D.

Weitere Termine und Informationen werden rechtzeitig an dieser Stelle im WWW angekündigt werden.

Literatur

Allgemeine Literatur (Textbücher):

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.
• M. Kaplan, Computeralgebra, Springer-Verlag, 2005.
• U. Schöning, Algorithmik, Spektrum-Verlag, 2001.
• A. Salomaa, Public-Key Cryptography, Springer-Verlag, 1996.
• P. Bürgisser, Completeness and Reduction in Algebraic complexity theory, Springer-Verlag, 2000.
• P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.
• J. Köbler, U. Schöning, J. Toran, The graph isomorphism problem: its structural complexity, Birkhäuser, 1993.