Seminar über Computeralgebra, Darstellungstheorie und Kombinatorik

Sommersemester 2012

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:

von zur Gathen und Gerhard, Moderne Computeralgebra, §4.6
Hardy and Wright, Theory of Numbers, Kapitel X

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:

von zur Gathen und Gerhard, Moderne Computeralgebra, Kapitel 12

Primzahltests (schon vergeben)

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

von zur Gathen und Gerhard, Moderne Computeralgebra, §18.4
Dietzfelbinger, Primality Testing in Polynomial Time

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:

Stanley, Enumerative Combinatorics, Vol II, §7.1 - §7.7

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:

Wüstholz, Algebra, §22
Lorenz, Einführung in die Algebra II, §29.1-3

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:

Fulton, "Young Tableaux", Kap. 8.1 und 8.2

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:

Husfeldt, Invitation to Algorithmic Uses of Inclusion-Exclusion

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:

Mahajan, Vinay, 1997, "Determinant: Combinatorics, Algorithms and Complexity" Chicago Journal of Theoretical Computer Science

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:

Nisan, Lower Bounds for Non-Commutative Computation

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:

Jerrum, Counting, sampling and integrating: algorithms and complexity, Kapitel 1

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:

Frobenius, 1897, "Über die Darstellung der endlichen Gruppe durch lineare Substitutionen" Paragraph 7, Satz I
Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, Berlin, Seite 994-1015

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.