Magdeburger Problem Solving Group

Posted November 1, 2009 by dirkolivertheis
Categories: Problem Solving Group, Teaching

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 x\mapsto \min_{k<l} \lvert x_k-x_l\rvert ü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 \sum_k x_k = 0 erfüllen, und für die (bei geeigneter Umnummerierung der Indizes) x_{k+1} - x_k 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

Posted October 12, 2009 by dirkolivertheis
Categories: Komb. Opt. WS09/10, Teaching

Liebe Übungsteilnehmer,

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

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

Viel Spaß bei der Vorlesung und den Übungen!

Dirk Oliver Theis

VL: Probabilistic Method

Posted July 16, 2009 by dirkolivertheis
Categories: Prob. Meth. WS09/10, Teaching

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 \log\log n + O(\sqrt(\log\log n)) 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 \log\log n + O(1) ist. Dann berechnet man die Standardabweichung, und kommt auf O(\sqrt{\log\log n}) +O(1). 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 A_1,\dots,A_n nicht hat. Wenn die Eigenschaften “statistisch” unabhängig wären, würde man einfach argumentieren, dass das Produkt der Wahrscheinlichkeiten 1-Pr(A_j) (dass A_j nicht eintritt) strikt größer 0 ist. Aber was, wenn das Eintreten eines A_j einige andere A_i wahrscheinlicher macht? Das Local-Lemma gibt eine Antwort auf diese Frage: Unter bestimmten Bedingungen an die Abhängigkeiten und die Wahrscheinlichkeiten der A_j 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

Posted June 25, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

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

VL Lineare Optimierung: Übungsblatt 12

Posted June 24, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Liebe Übungsteilnehmer,

Hier das Übungsblatt Nr. 12 mit Musterlösungen: http://dirkolivertheis.files.wordpress.com/2009/07/blatt12.pdf. Das war das letzte Übungsblatt, das für den Schein relevant ist.

In dieser Version mit den Lösungen sind im Vergleich zu der ausgeteilten Version die (mir bekannten) Tippfehler (*seufz*) berichtigt. Sorry!

DOT

VL Lineare Optimierung: Übungsblatt 11

Posted June 11, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Liebe Übungsteilnehmer,

Hier das Blatt 11: http://dirkolivertheis.files.wordpress.com/2009/06/blatt111.pdf.

Leider ist diesmal keine herausfordernde Aufgabe dabei: Aufgabe 11.1 ist nur rechnen (ok, für viele ist das eine Herausforderung — mich z.B.); bei Aufgabe 11.2 übt man lediglich das Gedächtnis (was war noch gleich Cramer’sche Regel bzw. Hadamard’sche Ungleichung?); die Herausforderung bei Aufgabe 11.3 besteht im Verstehen der Definition (obwohl man etwas Phantasie braucht, um Beispiele für (c) und (e) zu finden); Aufgabe 11.4 ist auch nicht schwer.

Hier ist meine eigene Lösung: http://dirkolivertheis.files.wordpress.com/2009/06/blatt112.pdf. Achtung Änderung in der Aufgabenstellung: Bei Aufgabe 3 habe ich zusätzliche Bedingungen gefordert, um einige triviale Lösungen für die gesuchten Beispiele auszuschließen.

Viel Spass!

DOT

VL Lineare Optimierung: Übungsblatt 10

Posted June 10, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Liebe Übungsteilnehmer,

Hier kommt Blatt 10:
http://dirkolivertheis.files.wordpress.com/2009/06/blatt101.pdf

Viel Spass!

Und hier sind die Lösungen:
http://dirkolivertheis.files.wordpress.com/2009/06/blatt103.pdf.

Nachtrag vom 18.06.: In den Lösungen zu 10.4 bzw 10.5(b) und 10.3 waren kleine Denkfehler, die jetzt berichtigt sind.

DOT

VL Lineare Optimierung: Übungsblatt 9

Posted June 3, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Liebe Übungsteilnehmer,

Hier der Zettel 9: http://dirkolivertheis.files.wordpress.com/2009/06/blatt091.pdf

Diese Links sollten Ihnen helfen:
http://en.wikipedia.org/wiki/Positive-definite_matrix und http://en.wikipedia.org/wiki/Zero-sum_game#Solution. Achtung: das LP zu den Nullsummenspielen ist nicht das gleiche wie in der VL (funktioniert aber auch).

Und hier sind die Lösungen: http://dirkolivertheis.files.wordpress.com/2009/06/blatt092.pdf.

Viel Spass,
DOT

Announcement: Vorlesung von Klaus Trümper

Posted May 28, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Am Mo 6. und Di 7. Juli wird Klaus Trümper zwei Einführungsvorlesungen in die sogenannte Matroid-theorie geben. Matroide sind in der Kombinatorik, besonders mit Blick auf Optimierungsanwendungen (von Greedy-Algorithmen zu Flüssen) wichtige gleichzeitige Abstraktionen von Matrizen und Graphen. Trümper ist einer der weltweit herausragenden Experten auf dem Gebiet und es ist super toll, dass er diese Vorlesungen bei uns hält!

Die beiden Vorlesungen sind so gehalten, dass jeder, der Lineare Algebra I gehört hat und weiss, was in einem Graphen ein Kreis und ein Baum ist, üppig vorbereitet ist. Anders formuliert: jeder Teilnehmer der VL Lineare Optimierung bringt die nötigen Voraussetzungen mit, um von Trümpers VLs zu profitieren! (Man sollte allerdings gut ausgeschlafen haben.)

Allen Hörerinnen und Hörern, die sich für diskrete/algorithmische Mathematik interessieren, sowie denjenigen, die einen Blick über den Tellerrand werfen möchten, ist dieser Einführungskurs sehr empfohlen!

DOT

VL Lineare Optimierung: Übungsblatt 8

Posted May 20, 2009 by dirkolivertheis
Categories: Lin-Opt-SS09

Liebe Übungsteilnehmer,

Hier steht das Blatt 8 mit Musterlösungen:
http://dirkolivertheis.files.wordpress.com/2009/06/blatt08.pdf. Ihre Kommentare und Anregungen wurden schon berücksichtigt. Insbesondere werden (b) und (c) in Aufgabe 4 leichter, wenn man in der ganzen Aufgabe nicht mit Matchings arbeitet, die nicht unbedingt perfekt sein müssen.

Viel Spass mit dem Zettel!

DOT