Seminar über "Algebraische Algorithmen"

Voraussetzung (sinnvoll, nicht zwingend): Teilnahme an der Vorlesung im Sommersemester 2007 Scheinbedingung: Ausarbeitung eines Referats samt Vortrag von ca. 60 min Länge Einordnung: B/D

Anhand einzelner Textbuchkapitel und Originalarbeiten sollen Inhalte der Vorlesung im SS07 vertieft und weiterführende Fragestellungen behandelt werden. Dabei sollen insbesondere auch Themen der Algebraischen Komplexitätstheorie bearbeitet werden.

• 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
• Blum-Shub-Smale-Modell und Komplexitätsklassen über Ringen

Termine

Zeit: Blockveranstaltung am Ende des WS 2007/2008 (nach Vereinbarung). Vorbesprechung am 10. August 2007, 11.00 - 12.00 Uhr, Pohligstr. 1, Raum 616. In diesem Rahmen werden auch die Themen vergeben.

Sonstiges: Weitere Termine und Informationen werden rechtzeitig im WWW angekündigt werden.

Einordnung und Scheinvergabe

Einordnung: B/D.

Literatur

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.
• M. Kaplan, Computeralgebra, Springer-Verlag, 2005.
• U. Schoening, Algorithmik, Spektrum-Verlag, 2001.
• A. Salomaa, Public-Key Cryptography, Springer-Verlag, 1996.
• P. Buergisser, Completeness and Reduction in Algebraic complexity theory, Springer-Verlag, 2000.
• P. Buergisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.
• Blum, Shub, Tucker, Smale, Computing over the reals, 1999.
• J. Koebler, U. Schoening, J. Toran, The graph isomorphism problem: its structural complexity, Birkhaeuser, 1993.

Weitere spezielle Literatur insbesondere Originalarbeiten werden im Rahmen der Vorbesprechung (s.o.) angegeben werden.