Seminar über Computeralgebra, Darstellungstheorie und Kombinatorik

Sommersemester 2012

Prof. Dr. Peter Bürgisser

Termin: Freitag, 9:15 - 10:45 Uhr im E2.304

Beginn: Freitag, 13. April 2012

Interessenten für Vorträge sollen sich bitte bald mit mir in Verbindung setzen. Email: pbuerg "at" math.upb.de

Die Themen werden nach dem Prinzip first come first serve vergeben.

Vorträge

Datum Titel Betreuer
13.4. Ein kombinatorischer Algorithmus zur Berechnung der Determinante Ikenmeyer
20.4. Kettenbrüche und diophantische Approximation Bürgisser
27.4. Schnelle lineare Algebra Bürgisser
18.5. Eine untere Schranke zur Berechnungskomplexität der nichtkommutativen Determinante Mengel
25.5. Die Sätze von Kirchhoff und Fisher, Kasteleyn und Temperley Mengel
1.6. Primzahltests Bürgisser
8.6. Tableau Straightening und irreduzible Darstellungen der allgemeinen linearen Gruppe Ikenmeyer
15.6. Symmetrische Polynome Ikenmeyer
22.6. Satz von Wedderburn Bürgisser
6.7. Der Stabilisator der Determinante Ikenmeyer

Themen

Kettenbrüche und diophantische Approximation (schon vergeben)

Kettenbrüche sind ein klassisches System zur Darstellung reeller Zahlen und werden mit einer Variante von Euklids Algorithmus berechnet. Sie liefern Bestapproximationen von reellen Zahlen durch Brüche. Kettenbrüche haben Anwendungen in der Zahlentheorie und Kryptographie aber auch in der Theorie dynamischer Systeme.
Quellen:

Schnelle lineare Algebra (schon vergeben)

Hier geht es um Wiedemanns Algorithms, mit dem ein quadratisches lineares Gleichungssystem Ax=b effizient gelöst werden kann, sofern das Matrix-Vektor Produkt effizient berechnet werden kann (z.B. weil A dünn besetzt ist). Dazu verwendet man die Theorie linear rekurrenter Folgen.
Quellen:

Primzahltests (schon vergeben)

Der Miller-Rabin Primalitätstest und seine Erweiterungen sollen diskutiert werden, möglicherweise bis hin zum AKS Test.
Quellen:

Symmetrische Polynome (schon vergeben)

Symmetrische Polynome sind omnipräsent in der Mathematik. Es sollen verschiedene Basen konstruiert und beschrieben werden, wie diese umgerechnet werden.
Quellen:

Satz von Wedderburn (schon vergeben)

Dieser fundamentale Struktursatz besagt, dass jede halbeinfache Algebra über einem Körper isomorph zu einem endlichen Produkt von Matrixringen über Divisionsalgebren ist. Dieses Thema schliesst an die Vorlesung über Darstellungstheorie an.
Quellen:

Tableau Straightening und irreduzible Darstellungen der allgemeinen linearen Gruppe (schon vergeben)

In diesem Vortrag soll ein kombinatorischer Zugang zu den irreduziblen Darstellungen der allgemeinen linearen Gruppe vorgestellt werden. Ein wichtiger Bestandteil ist der sogenannte "Straightening Algorithmus", mit welchem man zu Tableaux gehörige Vektoren als Linearkombination von zu Semistandardtableaux gehörigen Vektoren darstellen kann.
Quellen:

Algorithmische Nutzung von Inklusion-Exklusion

Das Prinzip der Inklusion-Exklusion ist eine grundlegende Technik in vielen Teilen der Mathematik. Hier soll vorgestellt werden, wie mit seiner Hilfe Algorithmen zum Zählen diskreter Objekte entwickelt werden können, deren Laufzeit schneller ist als naives vollständiges Enumerieren der Objekte.
Quellen:

Ein kombinatorischer Algorithmus zur Berechnung der Determinante (schon vergeben)

In diesem Vortrag soll eine Arbeit von Mahajan und Vinay vorgestellt werden, in welcher eine kombinatorische Charakterisierung der Determinante eingeführt wird. Diese Charakterisierung liefert einen einfachen, kombinatorischen Algorithmus zur Determinantenberechnung, welcher nicht auf linearer Algebra basiert und auch keine Divisionen erfordert.
Quellen:

Eine untere Schranke zur Berechnungskomplexität der nichtkommutativen Determinante (schon vergeben)

Schnelle Algorithmen zur Berechnung der Determinante nutzen die Kommutativität der Multiplikation in Körpern. Es soll gezeigt werden, dass wenn diese nicht gegeben ist, die Berechnung der Determinante schwer wird.
Quellen:

Die Sätze von Kirchhoff und Fisher, Kasteleyn und Temperley (schon vergeben)

Bei diesem Thema sollen zwei bekannte Algorithmen vorgestellt werden: Der Algorithmus von Kirchhoff ermöglicht es in beliebigen Graphen die Anzahl der Spannbäume zu berechnen. Mit dem Algorithmus von Fisher, Kasteleyn und Temperley lassen sich perfekte Matchings in planaren Graphen zählen. Beide Verfahren reduzieren dabei das Problem auf die Berechnung einer Determinante.
Quellen:

Der Stabilisator der Determinante (schon vergeben)

In der Geometrischen Komplexitätstheorie spielt der Stabilisator des Determinantenpolynoms eine große Rolle. Dieser wurde bereits 1897 von Frobenius bestimmt. Im Vortrag soll dieser Satz von Frobenius vorgestellt und bewiesen werden.
Quellen:

Falls die Bücher in der Bibliothek ausgeliehen sind, können wir Fotokopien der relevanten Abschnitte abgeben. Bitte bei Stefan Mengel oder Christian Ikenmeyer melden.