"Musterlösung" zu unserem kleinen Übungszettel

Ein kleines Vorwort

Okay, ihr hattet nun ein wenig Zeit, euch mit unserem Übungszettel zu beschäftigen, ein paar haben uns ihre Lösungsansätze mitgeteilt, und mehr oder weniger gut abgeschnitten.
Jetzt seit ihr bestimmt schon gespannt, was für Lösungen sich die "Profis" ausgedacht haben, als sie euch den Übungszettel aufgehalst haben.

Davor nur noch ein kurzes Wort:
Obwohl wir es versucht haben, ist unser Übungszettel nicht repräsentativ für alles, was euch während eines Informatik-Studiums begegnen könnte. Unser zwei Aufgaben könnte man grob in die Kategorie Theoretische Informatik stecken. Neben dieser werdet ihr aber auch Veranstaltungen aus den Bereichen Praktische Informatik, Technische Informatik und Mathematik besuchen.
Trotz viel überlegens und recherchierens ist es uns aber nicht gelungen euch passende Aufgabe, die keine Kenntnisse vorraussetzen, aus diesen Teilbereichen zu präsentieren.

Es ist nicht schlimm, wenn ihr nicht gleich auf die Ideale Lösung gekommen seid. Immerhin haben wir, die wir uns den Übungszettel ausgedacht haben, ja einen kleinen Vorsprung. Der Übungszettel sollte euch lediglich mehr oder weniger typische Probleme der Informatik zeigen, damit ihr wisst, auf was ihr euch einlasst, bevor ihr euch zum Studium meldet.
Man könnte sogar sagen, es nicht wirklich schlimm, wenn euch (noch) kein Lösungsansatz eingefallen ist, den während des Studiums werdet ihr natürlich noch betreut, wisst, wem ihr Fragen stellen könnt, und wo ihr in der Bibliothek nach dem passenden Buch suchen müsst.

Nicht zuletzt war es auch der erste Übungszettel dieser Art, den wir entworfen haben. Da kann es auch durchaus sein, dass wir uns da sehr verschätzt haben.
Wenn ihr uns sagt, was wir an ihm verbessern können, geloben wir Besserung :-)

Oh, und noch als letztes: Da sich der Autor geistig irgendwie noch im Urlaub befindet, kann es durchaus sein, dass er den ein oder anderen Bug in die nachfolgende Musterlösung gebaut hat. Kritisches Lesen ist daher angesagt, und im Zweifelsfall eine Mail an den Autor.

Lösung zu Aufgabe 1

Die Triviale Lösung: Dumpfes Vergleichen

Auf die triviale Lösung jeden Spieler aus Team 1 mit jedem Spieler aus Team 2 zu vergleichen ist wohl jeder gekommen. Wie viele Vergleiche man dazu benötigt ist nicht genau zu sagen. Mit Glück findet sich das gleich große Paar mit dem ersten Vergleich, mit Pech erst mit dem allerletzten Vergleich. Ich benötige also irgendetwas zwischen 1 (best case) und n · N (worst case).
Das ist natürlich ein ziemlicher Unterschied, und der Einfachheit halber beschränkt man sich oft auf das Betrachten der Worst-case-Szenarios.

Eine bessere Lösung: Vorsortieren und dann durchgehen

Eine intuitive Methode wäre natürlich, die Spieler beider Teams nach ihrer Grösse zu sortieren, was man mit (n + N) · log₂ (n + N) Vergleichen erledigen kann.
Um nun keinen mit langwierigen Erklärungen zu Sortieralgorithmen zu langweilen, sei der Interessierte Leser auf die Seite des Karl-Liebknecht-Gymnasium Frankfurt/Oder oder einfach auf Google verwiesen.
Für diese Aufgabe ist es ohnehin egal, mit welcher Methode die Spieler sortiert werden. Wichtig ist lediglich, dass man x Personen mit x · log₂ x Vergleichen nach ihrer Grösse sortieren kann.

Hat man nun die n + N Spieler beider Teams sortiert, so kann man nun recht einfach jeweils zwei daraus vergleichen und sich von unten nach oben hangeln. Das wären dann noch einmal n + N -1 Vergleiche.
Insgesamt benötigt diese Methode also (n + N) · log₂ (n + N) + (n + N -1) Vergleiche. Ja, man könnte jetzt einwenden, dass man doch nur Spieler Vergleichen muss, die nicht im selben Team sind. Dadurch würden wir jedoch keine Verbesserung erreich, weil wir in jedem Fall feststellen müssen, ob zwei benachbarte Spieler einem unterschiedlichen Team angehören, bevor wir ihre Grösse vergleichen.
Deshalb verschieben wir diesen Vergleich der Teams der jeweiligen Spieler nach hinten, wenn wir ein gleichgrosses Paar gefunden haben. Und da wir mit Sicherheit nicht mehr dieser Team internen Vergleiche als Team-Mitglieder geben wird, lassen wir sie mal ganz unauffällig unter den Tisch fallen, da sie sich ohnehin nicht stärker auswirken können, als das, was wir ohnehin schon vergleichen.

Was noch übrig bliebe, wäre der mathematisch korrekte Beweis, dass wir damit tatsächlich eine Verbesserung erzielt haben, das also n · N > (n + N) · log₂ (n + N) + (n + N -1). Dazu würden wir den Satz von l'Hospital anwenden.
Diese mathematische Spitzfindigkeit ersparen wir aber dem Leser (vor allem weil der Autor nicht weiss, auf welche mathematischen Kentnisse der Leser er aufbauen kann). Wem es nicht glaubhaft erscheint, dass diese Methode wirklich schneller ist, der hat die Wahl dem Autor zu vertrauen, oder ihn anzumailen auf die Gefahr hin von der mathematischen Keule erschlagen zu werden.

Bliebe noch die Frage, ob es nicht noch besser geht, immerhin haben wir die Tatsache, dass Team 1 weniger Spieler als Team 2 hat noch gar nicht berücksichtigt. Natürlich haben dies nicht ohne Grund so ausgedacht, so dass man die Antwort lautet: Ja, es geht noch schneller.

Die elegante Methode: Die wenigen sortieren, die vielen suchen

Die uns bisher bekannte, schnellste Methode dieses kleine Problem zu lösen ist recht einfach: Zunächst sortieren wir die n Spieler des kleineren Team 1. Wie schon erwähnt, kann kann man das mit n · log₂ n Vergleichen erledigen.
Anschliessend schnappen wir uns je einen der N Spieler aus dem unsortierten Team 2, und fangen an, jemanden mit gleicher Grösse im sortierten Team 1 zu suchen.
In der Praxis wäre es natürlich am einfachsten jeden Spieler aus Team 2 an all Spielern aus Team 1 vorbei zu führen. Das nennt sich lineares Suchen, und ist theoretisch mit n Vergleichen (immernoch worst case) recht langsam.

Für Rechner ist binäres Suchen weitaus schneller, auch wenn man es sich wohl bei diesem Beispiel anders Vorstellen würde.
Beim binären Suchen vergleichen wir den ersten Spieler aus Team 2 zuerst mit dem mittlersten Spieler aus Team 1. Ist er kleiner, so vergleichen wir den Spieler aus Team 2 als nächstes mit dem mittlersten Spieler der Hälfte mit den kleineren Spielern aus Team 1; ist er grösser, so vergleichen wir ihn als nächstes mit dem mittlersten Spieler der Hälfte mit den grossen Spielern aus Team 1.
Dieses halbieren wiederholen wir solange, bis wir entweder jemanden mit gleicher Grösse gefunden haben (erfolgreiche Suche, alles fertig und alle zufrieden), oder bis wir festgestellt haben, dass der Spieler aus Team 2 genau zwischen zwei benachbarten Spielern aus Team 1 liegt. In diesem Fall der erfolglosen Suche machen wir mit dem nächsten Spieler aus Team 2 weiter.

Wie lange dauert nun dieses binäre Suchen? Es benötigt log₂ n Vergleiche. Mit jedem Vergleich wird die Restmenge halbiert. Und wie oft kann ich eine Zahl x halbieren, bis sie ≤1 ist? log₂ x mal.

Insgesamt benötigt diese Methode also n · log₂ n + N · log₂ n Vergleiche (Team 1 sortieren, mit jedem aus Team 2 in Team 1 binär Suchen)
Und wieder gilt: Das sind weniger Vergleiche als bei den Methoden davor, dem interessierten erklärt der Autor dies gerne per Email, dem desinteressierten ersparen wir die Mathematik (mit dem Hinweis, dass er sich früher oder später aber mit so etwas beschäftigen muss).

Lösung zu Aufgabe 2

Die konservative Methode: Minimale Heuristik

Wir wollen möglichst viele Leute einladen, und dürfen keinen zwei Personen einladen, die mit einer Kante verbunden sind? Dann ist der erste Ansatz, immer die Person einzuladen, von der die wenigsten Kanten ausgehen. Diese Person wird die wenigstens anderen Personen versperren; man muss dann nur die Kanten der ausgewählten Person folgen und die Nachbarn der ausgewählten Person (sowie deren Kanten) aus dem Graphen streichen.

Das hört sich einfach an, liese sich bestimmt auch einfach programmieren. Auf den Beispielgraphen angewandt sähe der Verlauf dieses Verfahren so aus:

Zuerst werden Salerio, Salarino und Solanio eingeladen, und Porzia, Antonio und Shylock gestrichen (an dieser Stelle sehen wir übrigens, dass da wohl eine gewisse Form von Willkür im Spiel ist, den eigentlich können wir natürlich nicht alle drei gleichzeitig auswählen, sondern müssten uns für eine Person entscheiden, aber dafür haben wir keine Kriterien festgelegt).
Als viertes wird Jessica eingeladen, und Tubal gestrichen.
Jetzt wird Lanzelot eingeladen, und Arragon und Leonardo gestrichen.
Als letztes kann entweder Nerissa, Graziano, Gobbo oder Balthasar eingeladen werden.

Der Graph ist komplett abgearbeitet worden und das Verfahren beendet. Bliebe noch die Frage nach der Geschwindigkeit. Diese hängt sehr davon ab, wie der Graph im Computer abgebildet und das Verfahren selbst programmiert wurde, vor allem aber vom Graphen selbst (wieviele Kanten, wieviele Knoten). Die genauere Betrachtung ersparen wir dem Leser mit der bereits bekannten Argumentation, und weil das angewandte Verfahren ohnehin nicht die optimale Lösung liefert ;)

In der Tat hat es für den rechten Teil des Graphen um Jessica herum das optimale Ergebnis geliefert, im linken Teil hat es jedoch versagt, den statt Lanzelot und eine weitere Person aus dem unteren Viereck des Graphen einzuladen, wäre es günstiger gewesen, Arragon, Leonardo und Nerissa (oder Balthasar) einzuladen.

Die wirre Methode: Negative maximale Heuristik (oder so ähnlich)

Okay, wenn das nicht funktioniert, dann probieren wir es doch einmal anders herum: Wir streichen einfach die Person, von der die meisten Kanten ausgehen, samt ihrer Kanten aus dem Graph, und das solange, bis wir nur noch isolierte "Inseln" von höchstens zwei Personen vorliegen haben. Aus diesen Zweierpaaren können wir eine zufällig einladen, und die andere steichen.
Natürlich spielt auch bei dieser Methode eine gewisse Willkür mit. Ein möglicher Ablauf dieser Methode auf den Beispielgraph angewandt könnte so aussehen:

Streiche Gobbo
Streiche Graziano
Streiche Jessica
Streiche Lanzelot

Damit liegen nur noch die gewollten Inseln vor, eingeladen werden könnten Nerissa, Arragon und Leonardo (und damit hätten wir tatsächlich aus dem linken teil des Graphen ein optimales Ergebnis erzielt, wenn auch nur zufällig), stellen jedoch für den rechten Teil des Graphen fest, das Jessica gestrichen wurde, obwohl sie Bestandteil der optimalen Lösung ist.
Und damit fällt auch dieser erste Ansatz (vorerst?) in die Kategorie "Netter Versuch".

Die Methode für die optimale Lösung: Brute Force

Der Leser wird sich nun fragen, gibt es denn keine Methode, mit der sich absolut immer ein optimales Ergebnis erzielen lässt? Wenn man so fragt, so lautet die Antwort: Ja, es gibt (mindestens) eine Methode, die für jeden beliebigen Graphen eine optimale Lösung für das sogenannte Independent Set Problem liefert: Brute Force, mit brutaler Gewalt.
Dazu müsste man lediglich alle möglichen Kombinationen eingeladener Personen durchgehen, überprüfen, ob sie tatsächlich eine zulässige Lösung sind, und ob diese Lösung besser ist, als die beste bisher gefundene.
Okay, ihr könnt euch sicherlich schon denken, dass diese Lösung irgendeinen Haken haben muss, und der heisst Laufzeit. Überlegt einmal, wieviele unterschiedliche Mengen eingeladener Gäste es geben kann: 2ⁿ! Oder mit anderen Worten: Mit jeder Person, die zusätzlich in diesen Bekanntenkreis-Graphen aufgenommen wird, verdoppelt sich der zu leistende Arbeitsaufwand!

Also müsste die richtige Frage, die sich der Leser stellen sollte, eigentlich heissen: Gibt es denn keine Verfahrensweise, die für das Independent Set Problem in akzeptabel geringer Zeit immer die optimale Lösung liefert? Und die Antwort lautet: Nein, ein solches Verfahren ist derzeit nicht bekannt, weshalb es eigentlich etwas unfair war, euch mit diesem Problem zu konfrontieren, aber so wisst wisst ihr jetzt wenigstens vier Dinge:

Mit einfachen Lösungen kann man manche Probleme lösen, mir etwas mehr Nachdenken sogar mit einem akzeptablen Zeitaufwand
Manche Probleme lassen sich mit Computern nur in geringem Umfang mit geringem Zeitaufwand lösen, während sie bei grossen Eingabemengen einfach zu viel Zeit benötigen
Obwohl in der Informatik schon viel geforscht wurde, gibt es noch vieles zu tun und zu entdecken
Der Autor kann nicht mehr zählen.

Nachwort

Jetzt bleibt mir nur noch übrig euch für die Geduld zu danken, die ihr bei diesem kleinen Ausflug in die Informatik aufbringen musstet.
Vielleicht sehen wir uns ja einmal auf der Orientierungseinheit, wenn wir von der Studierendenvertretung die Erstsemester in den Studienalltag einführen.
Wer es bis dahin nicht aushalten kann, der kann ja einen kleinen Blick in die (nicht ganz aktuelle) Onlineausgabe der "Dont Panic!" werfen, diese Zeitschrift drücken wir den Ersties zur OE immer in die Hand.
Und Ihr wisst ja: Wenn ihr noch Fragen habt, dann mailt uns einfach!