Seminar SS10

Im kommenden Sommersemester wird es ein Seminar zum Themenbereich Kombinatorik/Optimierung geben, in dem ich einige Themen betreuen werde.

Das Ziel der von mir angebotenen Themen ist es, sich einge der aktuellen Forschungsrichtungen und -methoden der probabilistisch, analytisch oder algorithmisch ausgerichteten Kombinatorik zu erarbeiten. Es ist Teil des Konzepts, dass die Vortragsthemen nicht nur Stoff aus den Diskrete-Mathematik- und Optimierungvorlesung beinhalten. Vielmehr besteht der Reiz dieser Richtung der Mathematik gerade darin, dass Methoden und Ideen aus anderen Teilen der Mathematik zur Anwendung kommen.

Sollten Sie sich entschließen, über eines der Themen einen Vortrag zu halten, so werden Sie sich im Idealfall noch einige Grundlagen (mit meiner Hilfe) aneignen können, die Sie zum Verständnis des ihrem Vortrag zugrundeliegenden Artikels brauchen.

Im Folgende werde ich einige mögliche Themen auflisten.

1. Zählen mit Entropie

Entropie ist ein informationstheoretisches Konzept. Grob gesagt sagt die Entropie eine Zufallsvariable aus, wie groß ihr Informationsgehalt ist, was gleichbedeutend damit ist, wie gut man eine Folge von von unabängigen Zuvallsvariablen, die zu identisch Verteilt sind, komprimieren kann (das ist das berühmte Kodierungstheorem von Shannon).

Entropie hat sich aber als ein wichtiges Werkzeug in verschiedenen Teilen der Mathematik entwickelt, darunter auch die Kombinatorik und algorithmische Mathematik. Hier ein Beispiel.
Theorem. Es sei eine endliche Menge von Punkten in , und die Projektion dieser Menge auf die Koordinatenhyperebene . Dann gilt . Das kann man mit Entropie-Methoden wie folgt beweisen: Es sei ein aus gleichmäßig zufällig gewählter Punkt. Die Entropie von kennt man dann. Nun betrachtet man die Entropien der Projektionen von auf die Koordinatenhyperebenen, und schätzt deren Informationsgehalt ab. So erhält man .

In diesem Bereich können mehrere Vorträge vergeben werden. Eine Einarbeitung in die Basics des Entropiebegriffes ist unerläßlich. (Das zahlt sich aber, wie schon erwähnt, nicht nur für die Diskrete & Algorithmische Mathematik aus). Die Vorträge sollen sich dem diesem Übersichtsartikel orientieren: www.tcs.tifr.res.in/jaikumar/Papers/EntropyAndCounting.pdf

2. Expansion, Eigenwerte und Random Walks in Graphen

Jemand fährt durch eine Stadt. Immer, wenn er an einer Kreuzung ankommt, würfelt er die Straße aus, die er nun weiterfährt. Man kann sich leicht überlegen, dass, wenn er das unendlich lang macht, die Kreuzung, an der man ihn antrifft, gleichverteilt ist (vorausgesetzt, die Stadt ist “zusammenhängend” und nicht “bipartit”). Aber wie schnell konvergiert dieser Prozess gegen die Gleichverteilung? Die Antwort auf diese Frage führt zu einer tiefen Eigenschaften von Graphen, nämlich der Expansion, die wiederum zu tun hat mit Eigenschaften des Spektrums der Adjazenzmatrix (bzw., genauer gesagt, der Laplace-Matrix).

Expansions- oder, allgemeiner, Eigenwertmethoden sind heute aus den Anwendungen von Graphen für Algorithmen nicht mehr wegzudenken. Für algorithmisch Geneigte ist es wohl zur Zeit das Ding.

In einigen Vorträgen können wir die Beziehungen zwischen Expansion, Eigenwerten und Random Walks in Graphen, sowie die Anwendungen behandeln. Die Vorträge werden sich an dem folgenden Übersichtsartikel orientieren: www.ams.org/bull/2006-43-04/S0273-0979-06-01126-8/home.html.

3. Greedy-Algorithmen auf zufälligen Strukturen und Wormald’sche Methode der Differentialgleichungen

Hier handelt es sich um eine elegante Methode, mit der die Eigenschaften von Algorithmen mit zufälliger Eingabe untersucht werden. Als Beispiel möge der folgende randomisierte Greedy-Algorithmus zum Finden einer unabhängigen Menge in einem Graphen dienen. Zu Begin sei . Solange es Ecken in gibt, die zu keiner Ecke in benachbart sind, wähle eine solche zufällig aus, und füge sie zu hinzu.

Das Verhalten dieses Algorithmus auf zufälligen regulären Graphen kann man mit Wormalds Methode analysieren. Es ergibt sich ein System von gewöhnlichen Differentialgleichungen, wobei die Variable, nach der differenziert wird, die “Zeit” im Algorithmus ist. Aus der Lösung des DGl-Systems kann man dann ablesen, wie sich der Algorithmus über die Zeit entwickelt und insbesondere, wann er (mit hoher Wahrscheinlichkeit) terminiert. (Terminiert der Algorithmus nach Schritten, so hat er eine unabhängige Menge der Größe gefunden.)

Allgemeiner formuliert ist Wormalds Methode anwendbar, wenn sich für die bedingten Erwartungen der Beobachtungsvariablen eines (diskreten) Zeitschritts eines stochastischen Prozesses ein System von gewöhnlichen Differentialgleichung aufstellen läßt. Unter gewissen Bedingungen (Lipschitzstetigkeit etc.) kann man dann zeigen, dass sich nicht nur die Erwartungswerte, sondern die Beobachtungsvariablen selber mit hoher Wahrscheinlichkeit wie die Lösung des Differentialgleichungssystems verhalten.

Zu diesem Themenbereich können mehrere Vorträge vergeben werden. Der nicht-kombinatorischen Anteil ist hier Wahrscheinlichkeitstheorie und stochastische Prozesse. Es wird möglicherweise nur um die Anwendung der Methode in Beispielen gehen und nicht um den Beweis der Korrektheit, der w-theoretisch anspruchsvoller ist.

4. Themenbereich Property Testing

Mit dem Begriff Property Testing bezeichnet man das Problem, einen Algorithmus zu finden, der in sublinearer Zeit entscheiden, ob das Eingabeobjekt eine bestimmte Eigenschaft hat, oder weit davon entfernt ist, die Eigenschaft zu haben. Property Testing Algorithmen gibt es zu den verschiedensten Arten von Objekten (z.B. Graphen), wie auch zu den verschiedensten Eigenschaften.

Das Feld hat in den letzten Jahren durch Zusammenhänge zu Quasizufälligkeit große Fortschritte gemacht.

Ich würde gerne zu diesem Themenbereich mehrere Vorträge vergeben, habe mir bisher aber noch nicht genau überlegt, welche.
Eine gute Vorauswahl findet sich hier.

5. Themenbereich fourieranalytische Methoden

Es gibt einige mögliche Vorträge zu analytischen Methoden im weitesten Sinne. (Diesen Abschnitt werde ich vielleicht noch ergänzen.)

Jean Bourgains Paper

Das folgende Paper des Fields-Medaillisten Jean Bourgain gibt einen Beweis für den folgenden Sachverhalt: Ist eine Menge mit positiver oberer Dichte (d.h. ), dann existiert ein , so dass für jedes Punkte existieren, mit . Der Beweis benutzt elementare Fourieranalysis.

http://www.springerlink.com/content/a343g53033872345/?p=a3508dbd5dc74e51a0f17149a73f0cbf&pi=4

Tamar Zieglers Paper

Bourgain beweist das oben beschriebene Resultat, indem er zunächst ein viel stärkeres Theorem beweist, dass im Wesentlichen besagt, dass für geeignete endliche Mengen die Menge isometrische Kopien von enthält, für alle groß genugen .

Dieses Theorem wurde auf höhere Dimensionen verallgemeinert. Der Beweis kommt nicht mehr mit Fourieranalysis aus, er benutzt stattdessen Ergodentheorie. Das Paper findet sich hier:

http://www.springerlink.com/content/bxu1pp8024233891/?p=95774a32b0244e16b7aeecae472e8f8a&pi=13

VL Komb-Opt: Klausur

Liebe Übungsteilnehmerinnen und -Teilnehmer,

Nutzen Sie die Möglichkeit, in den Kommentaren zu diesem Post Ihre (inhaltlichen) Fragen bei der Klausurvorbereitung zu posten.
Natürlich sollten Sie auch Fragen oder andere Kommentare Ihrer Kommilitonen beantworten oder kommentieren.

Schauen Sie also mindestens regelmäßig ‘rein, ob Fragen oder Antworten gepostet wurden, die Ihnen bei der Klausur helfen könnten! Dazu können Sie sich auch automatisch bei jedem neuen Kommentar eine Email schicken lassen, dadurch bleiben Sie immer “dabei”. Vergessen Sie aber nicht, zu kommentieren, wenn Sie etwas wissen!

Viele Grüße

Dirk Oliver Theis

VL-KombOpt: Lösungen zu Blatt 9

Aufgabe 2: Dimension des Matching Polytops

Hier habe ich leider einen groben Fehler ‘reingeschludert: der Graph sollte vollständig sein — sorry!

Hier die Berechnung der Dimension des perfekten Matchingpolytops zu . Ist ungerade, so ist das Polytope leer. Sei also gerade. Im Fall von ist die Dimension 0. Sei nun und gerade.

Zunächst ist die Dimension höchstens , wo der Rang der Gradgleichungsmatrix ist: Das System der Gradgleichungen ist , wobei die Ecken-Kanten-Inzidenzmatrix von . Die Matrix hat Rang , was man sieht, wenn man das Gleichungssystem löst. Für jede Kante muß dann nämlich sein. Setzt man Kanten zu einem ungeraden Kreis zusammen, so erhält man für alle Ecken auf dem Kreis.

Nun müssen wir noch zeigen, dass es außer Linearkombinationen von der Gradgleichungen keine weiteren zulässigen Gleichungen für das Polytop gibt. Dazu benutzen wir Satz 3.19 (bzw. Edmonds Matching-Polytop-Theorem), indem wir zeigen, dass keine der Ungleichungen in der vollständigen Beschreibung des perfekten Matching Polytops insgeheim eine Gleichung ist.

Fangen wir an mit den Ungleichungen . Die entsprechende Gleichung ist nicht zulässig für das Polytop, da es klar ein Matching gibt, das enthält.

Nun zu den Blütenungleichungen . Beachte zunächst, dass für diese Ungleichung gerade zu einer Grad(un-)gleichung wird; genauso für . Sei also , und wähle sowie . Da einen vollständigen Graphen mit gerade vielen Ecken induziert, gibt es in ein perfektes Matching , wobei wir für den Fall erlauben. Genauso gibt es ein (möglicherweise leeres) perfektes Matching in dem Graphen mit Eckenmenge . Nun ist aber ein perfektes Matching in . Mit ist . Somit ist gezeigt, dass die Blütenungleichungen keine impliziten Gleichungen sind.

Aufgabe 3: Blütenfacetten

Auch hier hat sich ein kleiner Fehler eingschlichen: Wie oben schon beobachtet, sind die Blütenungleichungen gerade Grad(un-)gleichungen, wenn oder ist. Somit ist auch mindestens nötig.

Ausserdem beachte man, dass die beiden Ungleichungen und “modulo” der Gradgleichungen identisch sind. (In der VL war das so formuliert: Die beiden haben im von den Gradgleichungen definierten affinen Raum die gleiche Lösungsmenge).

Wie im Hinweis angegeben, suchen wir einen Punkt, der , der alle Schranken , alle Gradgleichungen und alle Blütenungleichungen erfüllt, aber die Blütenungleichung mit der Menge verletzt:

Dazu müssen wir die linke Seite der Blütenungleichung über das Polyeder der übrigen Ungleichungen maximieren. Wir definieren den folgenden Punkt . Sei . Für Kanten setzen wir , für Kanten setzen wir , und für Kanten setzen wir . Offenbar sind die Gradgleichungen erfüllt. Für jede -elementige Teilmenge gilt dann . Genauso hat man für jede -elementige Teilmenge , dass . Für jede Menge mit hat man damit aber . Alle Blütenungleichungen sind also erfüllt. Für selber erhält man aber .

Aufgabe 4: Benachbarte Ecken auf dem Perfekten-Matching-Polytop

Für diese Aufgabe haben wir die eine Richtung schon in der Übung gesehen: Wenn die symmetrische Differenz zwischen und ein Kreis ist, sind die beiden benachbart. Es fehlt die Rückrichtung: Wenn die symmetrische Differenz kein Kreis ist, sind sie nicht benachbart.

Dazu seien und perfekte Matchings, deren symmetrische Differenz aus den eckendisjunkten Kreisen besteht. Man kann nun verschiedene perfekte Matchings konstruieren, indem man für jeden der Kreise entweder nimmt oder . Ist , so bezeichne das entsprechende Matching. Wir rechnen nun nach

Für Kanten, die entweder sowohl in als auch in sind oder die weder in noch in sind, ist die Gleichung offenbar wahr. Eine Kante in einem der Kreise ist in genau der Matchings, also ist ihr Koeffizient auf der linken Seite , genauso wie auf der rechten.

VL-KombOpt: Einige Lösungen zu Blatt 6

Achtung: Beachte die Mitteilung im Kommentar zu Blatt 7

Aufgabe 1: Bipartite Matching als Min-Cost-Flow

Im Teil (b) war noch die Frage nach dem “dualen” Problem. Sowohl über das Min-Cost-Flow, wie auch durch direktes Hinschreiben erhält man die folgende LP-Formulierung: unter den Nebenbedingungen für alle Knoten von und für alle Kanten von . Das duale Programm ist das folgende: unter den Nebenbedingungen für alle . Das duale Problem besteht also darin, eine reele “Knoten--Packung” maximaler “reeler Kardinalität” zu finden. (Generell ist eine (nicht-negativ ganzzahlige mit ) “Knotenpackung” eine Auswahl von Ecken, so dass in jeder Kante nur eine Ecke gewählt wurde — mit anderen Worten, eine unabhängige Menge.)

Aufgabe 2: Level-Max-Flow

Teil (d): Wie bestimmt man in Zeit einen blockierenden Fluß im Level-Netzwerk?

Bequemer Algorithmus: Starte mit Fluß und Restkapaziät . Suche einen -Weg in , der nur Bögen mit benutzt. Existiert keiner, so sind wir fertig. Existiert einer, so erhöhe wie üblich, und verkleinere . Beachte, dass dadurch für einen Bogen die Restkapazität auf 0 fällt.

Es wird höchstens mal ein --Weg gesucht. Der Trick ist, dass man das Suchen eines solchen Weges in Zeit machen kann, denn jeder Knoten in außer hat einen Vorgänger im Level darüber.

Aufgabe 3: Satz von Tutte für Genügsame

(1) Wir zeigen zunächst: Wenn ein perfektes Matching hat, so gilt für jede Eckenmenge , dass höchstens Zusammenhangskomponenten ungerader Kardinalität hat. Spasseshalber zeigen wir das für beliebige Graphen .

Es sei ein perfektes Matching und , und eine ungerade (d.h. ungerade Kardinalität) Zusammenhangskomponente von . Da ein perfektes Matching ist und ungerade, verläuft mindestens eine Kante von zwischen und . Bezeichnet man mit die Endecke dieser Kante in , so hat man, dass die alle verschieden sind, und somit die gewünschte Ungleichung gilt.

(2) Offensichtlich ist, dass, wenn die Bedingung für alle Eckenmengen gilt, sie auch für die einelementigen gilt.

(3) Wir zeigen, dass in Bäumen (mit mindestens einer Kante(!)) folgendes gilt. Hat für jede Ecke der Wald höchstens eine Zusammenhangskomponenten ungerader Kardinalität, so hat ein perfektes Matching.

Aus der Bedingung folgt zunächst, dass gerade viele Ecken hat (wähle für eine Ecke, die zu einem Blatt benachbart ist).

Für die Existenz des perfekten Matching sei ein Matching in , und eine exponierte Ecke von . Da gerade viele Ecken hat, gibt es eine Komponente von mit ungerader Kardinalität. Insbesondere ist kein perfektes Matching von . Sei eine exponierte Ecke von , und der eindeutige -Weg in . Dieser Weg beginnt mit einer Kante und endet mit einer Kante , und zwischen zwei Kanten ist immer mindestens eine Kante . Es gibt also auf einen Teilweg mit der Eigenschaft, dass die erste und die letzte Kante nicht in sind, und auf dem sich ansonsten -Kanten und Nicht--Kanten abwechseln. Ändert man , indem man jede -Kante in aus entfernt und dafür jede Nicht--Kante zu hinzufügt, so erhält man ein Matching mit größerer Kardinalität.

Matchings, die Ecken exponiert lassen, haben also nie maximale Kardinalität. Ein Matching maximaler Kardinalität ist somit ein perfektes Matching.

Es gibt auch einen Beweis ohne augmentierende Wege, aber ich finde den hier eleganter, zumal er von der Augmentierende-Wege-Eigenschaft nur die trivale Richtung benutzt (wenn es einen augmentierenden Weg gibt, ist das Matching nicht kardinalitätsmaximal).

VL Komb-Opt: Programmierprojekt

Ein riesen Lob und Hurra an und über Matthias Walter, der die Datenstrukturen vorbereitet hat, und das gleich in Varianten für drei Entwicklungsumgebungen, aber mit allem Comfort! Und den Text unten hat er auch geschrieben (bis auf die Fehler, die ich reingewürgt habe, natürlich).

Leider konnte ich die nötigen Dateien (Datenstruktur mit Funktionen, Makefiles etc, Testgraphen) noch nicht hochladen, weil das mit WordPress nicht geht und ich keine andere Internetseite habe. Die Sachen kommen in den nächsten Tagen.

Problemstellung

Betrachtet wird das Maximum-Cardinality-Matching-Problem. Ihre Aufgaben sind wie folgt:

1. Implementieren Sie Edmond’s Blossom Shrink Algorithm in C oder C++. Nutzen Sie dafür die bereitgestellte Datenstruktur für eine Adjazenzliste! Ihr Code soll den üblichen Standards entsprechend dokumentiert sein.
2. Vergleichen Sie die theoretische asymptotische Laufzeit der Implementierung mit der aus der Vorlesung.
3. Messen Sie die Laufzeit der Implementierung für die Beispiel-Graphen und vergleichen Sie diese mit den theoretischen Überlegungen.

Graphen & Matchings

Unter dem Link, der später im Kommentar nachgelifert wird, finden Sie eine Sammlung von Graphen, mit denen Sie ihren Code testen können. Dabei werden Graphen mit , und wie folgt kodiert:

…

In den Dateien für das Projekt sind nun immer 2 Graphen hintereinander enthalten: Zunächst der eigentliche Graph, gefolgt vom Matching, welches ebenfalls als Graph aufgefasst ist. Die beiden Knotenzahlen müssen somit gleich sein und die Kantenzahl im Matching-Teil entspricht der Kardinalität dieses.

Hinweis: Sie können in ihrer Implementation nicht davon ausgehen, dass der Eingabegraph zusammenhängend ist!

Quellcode für die Adjazenzliste

Es stehen drei Varianten des zur Verfügung gestellten Codes zur Auswahl: Windows-Nutzer können den DevCpp verwenden, Linux-Nutzer das Makefile-Projekt, und Freunde der Eclipse C/C++ Development Tools kommen auch auf ihre Kosten.

Die entsprechenden Dateien werden in den nächsten Tagen auf Internet zur Verfügung gestellt. Ich schreibe dann einen Kommentar mit den Links.

In den Dateien “graph.h” und “graph.c” ist eine Adjazenzliste implementiert. Dabei wurden statt Listen jedoch dynamische Felder verwendet. Es gibt Routinen zum Erzeugen, Löschen, Ausgeben, Manipulieren, Lesen und Schreiben von Graphen.

Sie müssen diese Datenstruktur in ihrem Algorithmus verwenden!

In der “main.c” ist bereits etwas Code für das Hauptprogramm vorbereitet. Dieser liest oben beschriebene Dateien ein, ruft eine augment-Funktion in der Datei “algorithm.c” auf, die Sie noch mit Leben erfüllen dürfen und schreibt das konstruierte Matching zusammen mit dem Graphen in eine Ausgabe-Datei. Dabei wird u.a. die Laufzeit gemessen. Der Aufruf des Programms sieht wie folgt aus:

./KombOptMatching EINGABE-DATEI AUSGABE-DATEI

Auswertung

Zur Zeitmessung ist die clock-Funktion bereitgestellt. Die damit gemessene Prozessorzeit wird in der Summary-Zeile ausgegeben.

Nutzen Sie diese, um die asymptotische Laufzeit für reale Daten abzuschätzen und mit den theoretischen Überlegungen zu vergleichen.

Quellcode und Auswertung sind bis zum 14. Januar 2010 abzugeben.

Komb-Opt Übungsblatt 3

Aufgabe 4

In Blatt 3 gab es eine kleine Unstimmigkeit: in Aufgabe 4 muss man “-kürzester --Weg” durch “-kürzester --Pfad” ersetzen, da man natürlich nicht davon ausgehen kann, dass ein -kürzester --Pfad mit ungerader Länge überschneidungsfrei ist. Die sinnvollste Variante der Aufgabe würde nach einem kürzesten Kreis (überschneidungsfrei) mit ungerader Länge bei nicht-negativen Kantengewichten fragen.

Aufgabe 3

Hier noch mal die Lösung zur Aufgabe 3.c von Blatt 3, die wir in der Übung nicht beendet haben. Außerdem war in meinen Ausführungen an der Tafel ein Fehler.

Die Frage war nach den zulässigen Basen des linearen Programms

wobei die Inzidenzmatrix ist, und die Einheitsmatrix. Die Koeffizientenmatrix hat Rang , (das ist immer der Fall, wenn man drei Matrize hat ( über , neben ), und das Bild von ist im Bild von enthalten).

Zunächst mal zur Benennung der Spalten: Sowohl deren linke Hälfte als auch die rechte entsprechen gerade Bögen. Eine Menge von Spalten entspricht also zwei Mengen von Bögen , , sagen wir für die linke Hälfte und für die rechte.

Zunächst einmal die Basen, ohne “zulässig”. Damit eine Basis herauskommt, muss sein. Außerdem muss in der unteren Hälfte der Matrix in jeder Zeile mal eine 1 vorkommen, also braucht man . Aber man braucht auch, dass keine Kreise enthält: denn sonst hätte man für die Matrix eine Linearkombination der Null deren Träger (= nicht-null-Koeffizienten-Bögen) in enthalten ist, und was dabei mit dem links unten passiert, könnte man mit den entsprechenden Bögen in der rechten Hälfte der Koeffizientenmatrix reparieren, so dass auch in der unteren Hälfte der Koeffizientenmatrix Null herauskommt. Aus schließt man , und schließlich, dass die Bogenmenge eines aufspannenden Baumes bezeichnet (wir gehen mal davon aus, dass das Netzwerk zusammenhängend ist).

Zusammenfassend haben wir für die Konstruktion einer Basis nur die Freiheit, die Bogenmenge eines Baumes auszuwählen, diese Bögen sowohl in als auch in zu packen, und die übrigen Bögen zwischen und aufzuteilen.

Wann ist eine Basis nun zulässig?

Wenn wir das Gleichungssystem lösen, so sind die Werte der Variablen in der linken Hälfte, die zu gehören, und genauso die Werte der Variablen in der rechten Hälfte , die zu gehören, sofort ablesbar: Sie haben den gleichen Wert, wie die jeweilige rechte Seite in der zugehörigen Zeile der unteren Hälfte der Matrix, also oder .

Was den Rest angeht, so sind die Variablen zu den Bögen im Baum in der linken Hälfte der Matrix dadurch bestimmt, dass die Gleichung

gelten muss, denn hat vollen Spaltenrang. Die Werte der Variablen zu den Bögen in in der rechten Seite der Matrix ergeben sich dann direkt durch die untere Hälfte der Matrix.

Für die Zulässigkeit braucht man , wir müssen also sicherstellen, dass in~(1) ein herauskommt, und dass dieses dann zu einem führt. Letzteres ist äquivalent zu für und für . Puh! Gibt’s eine kurze Lösung für die Aufgabe?!???

Also Frage: Für welche Bäume kann man in die Bögen im Komplement von () auf die obere Schranke setzen, und erhält, wenn man nach löst, ein zwischen und den oberen Schranken?

Dazu überlegen wir uns noch kurz, dass man in dieser Situation den Wert von auf einem Baumbogen folgendermaßen bestimmen kann: Entfernt man aus dem Baum, so erhält man 2 Zusammenhangskomponenten, also eine Bipartition der Knotenmenge, sagen wir mit dem Anfangsknoten (-Inzidenzmatrixeintrag) von in und dem Zielknoten in . Wegen gilt . Ok, das war schneller ausgerechnet als ich dachte. Super. Wenn ich mich nicht irre (was eher wahrscheinlich ist) brauchen wir also für jeden Bogen im Baum die Eigenschaften

wobei die vier Zeilen den vier Fällen entsprechen: oder ; und , ; und , ; und .

Weder die zweite noch die vierte Ungleichung ist erfüllbar (), also entsprechen die zulässigen Basen Bäumen mit der Eigenschaft, dass für jede Kante des Baumes mit den Bezeichnungen wie oben oder oder gilt und ausserdem

gilt, für die beiden Fälle, dass oder ; oder . Stimmts ?

Magdeburger Problem Solving Group

Hier endlich mal ein Post zu unserer Problemlösegruppe.

Das Lösen von Mathe-Problemen in kleinen Gruppen ist eine meiner Top-Fun-Beschäftigungen. Die MD-PSG richtet sich an Studis, die auch Spaß am Lösen schwieriger mathematischer Probleme haben.

Wir treffen uns wöchentlich und grübeln über Probleme, die monatlich im American Mathematical Monthly, einer Publikation der Mathematical Association of America erscheinen. Diese Aufgaben kommen aus allen Bereichen der Mathematik. Obwohl sie nur undergraduate Kentnisse erfordern (Magdeburger Vordiplomkentnisse genügen), liegt ihr Schwierigkeitsgrad (meistens) jenseits von Übungsaufgabenniveau, und die Lösungen erfordern (in der Regel) einige relativ clevere Ideen.

Bei der MD-PSG steht der Fun-Faktor absolut im Fordergrund. Das Angebot zielt nicht auf Bildung eines Hypergenieclubs, sondern richtet sich vielmehr an diejenigen, denen das Grübeln an schwierigen mathematischen Problemen in einer Gruppe Spaß macht.

Die Gruppe betsteht zur Zeit aus ca. 5 Studis, im ca. 4. Semester Mathe/Wirtschaftsmathe/Computermathe.

Am vergangenen Donnerstag haben wir die folgende Aufgabe gelöst: Für jedes n, bestimme das Maximum der Funktion über alle x in der n-dimensionalen (euklidischen) Einheitskugel.
Die Aufgabe entpuppte sich aber als Enttäschung: unsere Lösung besteht in der Beobachtung, dass für das Maximum nur Punkte in Frage kommen, die erfüllen, und für die (bei geeigneter Umnummerierung der Indizes) konstant ist. Wenig beeindruckend.

Ein Problem, mit dem wir uns schon vorletzte Woche beschäftigt haben, und für das wir die Lösung noch nicht kennen ist das folgende: Gibt es zwei ganzzahlige symmetrische 2×2-Matrizen mit der Eigenschaft, dass alle Produkte, die man aus den beiden bilden kann, paarweise verschieden sind?

Wenn Sie Student in Magdeburg sind und Interesse an unserer PSG haben, kontaktieren Sie mich am besten per Email.

VL: Kombinatorische Optimierung

Liebe Übungsteilnehmer,

Auf dieser Seite werde ich Neuigkeiten zur Vorlesung in Form von Kommentaren posten.

Links auf die Übungsblätter finden sich auch in den Kommentaren.

Sie Ihrerseits sind willkommen, Fragen zu stellen und Kommentare abzugeben.

Viel Spaß bei der Vorlesung und den Übungen!

Dirk Oliver Theis

VL: Probabilistic Method

Hallo,

Im Wintersemester 2009/10 biete ich eine Vorlesung über Wahrscheinlichkeitstheoretische Methoden in der Kombinatorik an, oder, auf gut neu-deutsch: Probabilistic Method.

Die Grundidee der Probabilistic Method ist, kombinatorische Fragestellungen, wie sie in verschiedenen Bereichen der Mathematik immer wieder auftauchen, mit wahrscheinlichkeitstheoretischen Methoden anzugehen. Hier ein Beispiel.

Theorem. Eine “typische” natürliche Zahl n hat Primteiler.

Die Formulierung hier ist natürlich informell. (Und die Bedeutung der O-Notation werde ich genau erklären.) Der Beweis dieses Theorems ist eine typische Anwendeung der Methode des zweiten Moments: Man rechnet zunächst, dass die durchschnittliche Zahl der Primteiler ist. Dann berechnet man die Standardabweichung, und kommt auf . Schließlich wendet man die bekannte Chebyschev’she Ungleichung an, um die gewünschte formale Aussage zu erhalten.

Die Intention der Vorlesung liegt darin, die wahrscheinlichkeitstheoretischen Werkzeuge (im obigen Beispiel Chebyshev’sche Ungleichung) zu erlernen, und ihre Anwendung an Beispielen einzuüben.

Die Chebyshev’sche Ungleichung gehört zu den elementareren Werkzeugen, die wir kennenlernen werden. Ein anderes eher einfaches Werkzeug ist das sogenannte Local Lemma. Stellen Sie sich vor, sie sind in der folgenden Situation: Sie wollen die Existenz eines Objekts zeigen, das eine Reihe von unerwünschten Eigenschaften nicht hat. Wenn die Eigenschaften “statistisch” unabhängig wären, würde man einfach argumentieren, dass das Produkt der Wahrscheinlichkeiten (dass nicht eintritt) strikt größer 0 ist. Aber was, wenn das Eintreten eines einige andere wahrscheinlicher macht? Das Local-Lemma gibt eine Antwort auf diese Frage: Unter bestimmten Bedingungen an die Abhängigkeiten und die Wahrscheinlichkeiten der gibt es ein Objekt, das die unerwünschten Eigenschaften nicht hat.

Ein weiterer Bereich sind stochastische Prozesse. Der Höhepunkt dieses Bereichs (und der Vorlesung) ist die elegante Differentialgleichungsmethode nach Wormald. Sie ist anwendbar, wenn sich für die bedingten Erwartungen der Beobachtungsvariablen eines (diskreten) Zeitschritts eines stochastischen Prozesses ein System von gewöhnlichen Differentialgleichung aufstellen läßt. Unter gewissen Bedingungen kann man dann zeigen, dass sich nicht nur die Erwartungswerte, sondern die Beobachtungsvariablen selber “asymptotisch fast überall” wie die Lösung des Differentialgleichungssystems verhalten.

Kenntnis einer einführenden Vorlesung zur Wahrscheinlichkeitstheorie wird vorausgesetzt (und natürich der Grundvorlesungsstoff), aber alles Weitere werde ich in der Vorlesung genau erklären.

-DOT

VL Lineare Optimierung: Klausur

Klausur:

Do 9. Juli, 17:00 Uhr in G16 159/300 Hörsaal H5.

Hier ein “Repetitorium” für die Vorlesung (nützlich auch zur Prüfungsvorbereitung): http://dirkolivertheis.files.wordpress.com/2009/07/repetitorium.pdf.

Die anonymisierten Klausurergebnisse sind hier: http://dirkolivertheis.files.wordpress.com/2009/07/klausur-anonym.pdf

Vielen Dank, dass Sie da waren, es hat Spaß gemacht!

-DOT