...dann ist es vielleicht dochmal angebracht, ein wenig Ordnung zu schaffen. Muss wohl ab und zu sein. Mal sehen, was ich so alles finde...

In der Tat habe ich mich bei der Suche nach der Lösung des Sockenproblems viel zu früh auf eine Modellierung festgelegt. Als wir heute im Dekanat darüber diskutierten kam Prof. Madlener (Grundlagen der Informatik, formale Methoden) vorbei und fand meinen Graphenansatz "nett, aber übertrieben". Stattdessen schlug er folgende Lösung vor:

Man entscheidet sich für ein einziges Unterscheidungskriterium (Farbe, Farbton, Länge, Breite, Muster, Musterung, etc.) und bildet Haufen mit Socken, die hinsichtlich dieses Kriteriums gleich sind. Ist der Haufen groß genug wählt man ein neues Unterscheidungskriterium oder unterscheidet genauer und unterteilt diesen Haufen nochmals auf die gleiche Art in kleinere (man wendet das Verfahren also rekursiv an); bei kleinen Haufen kann man dann einfach passende Socken zusammenfügen.

Ich habe das ganze mal ausprobiert und damit in deutlich weniger als einer halben Stunde meinen Sockenhaufen in 42 passende Sockenpaare und 10 unzuteilbare Einzelsocken umwandeln können. Verglichen mit meine bisherigen Sockensortierzeiten eine fantastische Verbesserung. Probleme treten nur bei schwer unterscheidbaren Socken auf, hierbei ist das größte Problem, ein sinnvolles Entscheidungskriterium zu formulieren.

Insgesamt bin ich mit dieser Lösung sehr zufrieden.

Kalle (Informatik, Liste "Rauchfreie Uni") hat für's StuPa Schilder im Stil der Zigarettenpackungswarnungen gebastelt. Corinna (EIT, Liste "Binford 2004", Raucherin) fühlt sich von den Slogans "Rauchen macht hässlich", "Rauchen macht dumm", "Raucher stinken" und "Rauchen ist doof" persönlich beleidigt. Fabian (Vertreter FS Informatik) unterstützt Kalle. Marc (Mathe, Liste "Fachschaftsliste Mathematik") meint, dass "Nicht-Rauchen macht dumm" auch gilt, weil auch Nicht-Raucher altern und Altern macht dumm (und wer braucht schon Kausalität). Die Präsidentin Uli (Liste "Kunterbunt") fühlt sich vom Rascheln der Schilder gestört. Ich (Informatik, Liste "Kategorischer Imperativ") halte das Argument "fühle mich gestört" für nicht zulässig: Die Frisur des einen Fabians und der Bart des anderen Fabians (Liste "Kunterbunt") muss ich ja schließlich auch erdulden. Nach rund fünf Minuten Diskussion verbleiben wir ohne Ergebnis.

Manchmal diskutieren wir aber auch sinnvolle Sachen.

Für die theoretisch Interessierten:
Früher oder später lernen Infotiker im Grundstudium eine cantoreske Aufzählung der rationalen Zahlen ("alle Zahlen, die weniger krank sind als π oder e") kennen, und die meisten finden es nicht schön, dass jede Zahl (modulo Kürzen) unendlich oft vorkommt. Bei Lambda the Ultimate hab ich diese schöne Lösung entdeckt. Ich find das cool, und weil ich gut gelaunt bin werde ich Problem und Lösung auf Nachfrage gern erklären.

Wie ich gerade erfahren habe war eine Zeit lang der jetzige deutsche Meister im Chili Essen in einer meiner Übungsgruppen:

"Florian Faust hingegen ist äußerst souverän. Als sei die Schale vor ihm mit Grießbrei gefüllt, häuft er die rote Masse auf seinen Löffel und isst und isst. 446 Gramm schafft er, 30 Gramm mehr als der Zweitplatzierte und 418 Gramm mehr als der Letzte."

Was ich für Leute kenne... So eine Meisterschaft muss man ja eigentlich auf der nächsten Vollversammlung mitteilen. [Update: Hier, die letzten drei Bilder.]

...statt der Socken, dringender und irgendwie auch notwendig: Lernen. Wusstet Ihr, dass man die Klasse der Patternsprachen anhand von TEXT im Limes erlernen kann? Und das sogar schnell? Jaja, PAT ist in Poly-LIM-TEXT. Ich liebe meinen Elfenbeinturm.

Zur Zeit beschäftigt mich folgendes Problem:

Man betrachte eine Schublade S mit n schwarzen einzelnen Socken S_i, 1≤i≤n. Die Socken sind zwar wie gesagt allesamt schwarz, allerdings bestehen doch erkennbare Unterschiede, z.B. in Musterung, Länge, Grad der Verwaschenheit u.ä. Um das ganze zu formalisieren benötigen wir eine Ähnlichkeitsprädikat f, das ermittelt, ob sich zwei Socken genug ähneln, um als tragbares Paar bezeichnet werden zu können (In der Praxis wird f meist durch Nebeneinanderhalten und Anstarren der beiden Parametersocken bestimmt und ist damit selbst für einen festen Modegeschmack leider nicht wohldefiniert, da das Ergebnis z.B. von Beleuchtung und Tagesform abhängt). Der Einfachheit halber nehmen wir allerdings an, dass f(S_i,S_j) innerhalb einer gewissen Zeitspanne auch bei mehrmaliger Berechnung das gleiche Ergebnis liefert.

Erschwerend kommt hinzu, dass nicht zu jedem S_i ein S_j mit f(S_i,S_j) existiert (das Problem der verschwindenden Socken, allgemein bekannt), außerdem ist f nicht transitiv (aus f(S_i,S_j) und f(S_j,S_k) folgt nicht immer f(S_i,S_k)) - es können also keine disjunkten Äquivalenzklassen gebildet werden, stattdessen muss man mit schwammigeren Äquivalenzmengen Vorlieb nehmen.

Gesucht ist nun ein Algorithmus, der mit möglichst wenig Verwendungen von f möglichst viele Paare S_i, S_j mit f(S_i,S_j) aus S entfernt ("in die andere Schublade legt") und dabei möglichst wenige Socken in S verbleiben lässt (Natürlich müsste man an dem formalen Unterbau dieser Aufgabenstellung noch ein wenig arbeiten, ein wenig exakter werden und die passenden Quellen zitieren; um die Idee zu skizzieren sollte das erstmal langen).

Meiner oberflächlichen Recherche nach beschäftigen sich die meisten Arbeiten auf diesen Gebiet mit disjunkten und damit zerlegbaren Mengen von Socken ("Sock Selection Problem"), leider haben wir es bei dem vorgestellten Problem mit einem Haufen sich wirr überschneidender Teilmengen zu tun, fast so wie ein Wäschestapel in dem Katzen gespielt haben. Ich müsste mir mal ein wenig Zeit nehmen und ausführlich über das Problem nachdenken. Ganz unanbhängig davon: Dr. Seuss, Fox in Socks Matching Game.

Nur zwei Tage nach der öffentlichen Verbreitung meiner Gmail-Adresse haben die Spamsatanisten zugeschlagen. Milagros Corbett spammt für Spamdienste und ist damit der erste, der diesen Blog nach Adressen durchsucht hat. Da kommt man sich ja fast bedeutend vor.