Algorithmus der Woche

• » Startseite
• » aktueller Algorithmus
• » Liste der Algorithmen

Informationen

• » Infoflyer Presse
• » Infoflyer Schule
• » Download Logo

Gimmicks für's Klassenzimmer

• » Visuelle Kryptographie

Links

• » Informatikjahr
• » Fakultätentag Informatik

Intern

• » Für Autoren
• » Für Organisatoren
• » Buchprojekt

Sonstiges

• » Impressum
• » Gästebuch
• » Haftung

Wie soll ich das nur alles schaffen? Es sind zwar Ferien aber ich muss noch die Mathehausaufgaben machen. Dann ist da noch der Deutschaufsatz zu schreiben, wofür ich aber auch noch das Buch über die Geschichte der Informatik aus der Bibliothek holen und ein wenig im Internet recherchieren muss. Dabei fällt mir ein, dass auch der Computer nach der letzten LAN-Party noch nicht wieder aufgebaut und angeschlossen ist. Ganz nebenbei bemerkt dürften die Aufgabenblätter für die Mathehausaufgaben auch noch nicht ausgedruckt sein und in meiner Emailbox auf dem GMX-Emailserver schlummern. Dann ist heute abend auch noch eine Party, für die ich noch einen Sampler zusammenstellen und brennen wollte. Natürlich muss auf diese CD auch der neue Song von Placebo, den ich mir noch bei iTunes kaufen wollte. Als ob das noch nicht genug wäre hat mich meine Mutter zum Müllraustragen, Schuheputzen und Abwaschen eingeteilt und das, obwohl ich für die Party ja auch noch einen Kasten Cola aus dem Supermarkt aus der Stadt holen muss. Glücklicher Weise liegt der Supermarkt auf dem Weg zur Bibliothekt und das Spühlmittel zum Abwaschen ist ja ohnehin alle. Aber was erledige ich nun zuerst?

Hm, das Nacheinanderabarbeiten aller Punkte auf meiner ToDo-Liste macht offensichtlich keinen Sinn. Schließlich kann ich die CD erst brennen, wenn ich alle Songs habe und die bekomme ich nur zusammen, wenn mein Rechner aufgebaut und ans Internet angeschlossen ist. Irgendwie bestehen also Abhängikeiten zwischen den einzelnen Aufgaben und noch nicht alle Teilaufgaben sind bisher aufgelistet. Darum nehme ich mir also einen Stift und vervollständige zuerst einmal meine ToDo-Liste. Bevor ich abwaschen kann, muss ich Spülmittel kaufen. Deshalb zeichne ich einen Pfeil von "Spülmittel kaufen" zu "Abwaschen". Das Spülmittel bekomme ich nur in der Stadt, weshalb ich einen Pfeil von "In die Stadt fahren" zu "Spülmittel kaufen" zeichne usw.

Mann, da wird einem erst mal richtig bewußt, was noch alles zu tun ist, aber womit fange ich denn nun an? Ein Pfeil zeigt an, dass irgendetwas nur dann erledigt werden kann, wenn zuvor etwas anderes erledigt wurde. Also kann ich nur mit etwas anfangen, auf das kein Pfeil zeigt. Zur Auswahl stehen in meinem Fall demnach:

• Müll rausbringen
• Schuhe putzen
• Computer aufbauen
• In die Stadt fahren

Eigentlich ist es ja egal, welche dieser vier Aufgaben ich als erstes in Angriff nehme. Aber ich bin mal nett und bringe den Müll raus, putze dann die Schuhe und baue erst anschließend den Computer auf. Nachdem ich das alles erledigt habe, kann ich meinen Aufgabenübersicht korrigieren und die erledigten Aufgaben abstreichen. Dadurch fallen natürlich auch etwaige Pfeile, die von erledigten Aufgaben ausgehen (hier von "Computer aufbauen" nach "Computer ins Netz bringen"), weg.

Natürlich wäre es übersichtlicher, wenn ich einen Bleistift verwendet hätte, dann könnte ich die gestrichenen Pfeile und Aufgaben einfach ausraddieren. Nun, der Computer steht und ich kann meine Aufgabenliste ja auch elektronisch abarbeiten. Ich zeichne mir das ganze also mit einem Graphikprogramm ab, wobei mir einfällt, dass Informatiker, wie mein Bruder, die Struktur meiner Aufgabenliste als Graph bezeichnen. Die zu erledigenden Aufgaben werden durch Knoten in einem Graph dargestellt und die Abhängigkeiten werden zu gerichteten Kanten zwischen Knoten. Gerichtet bedeutet hier, dass die Lesereihenfolge (in Pfeilrichting) festgelegt ist. Ist es in dem Graph möglich, ausgehend von einem Knoten durch Nachzeichnen (ohne absetzen des Stiftes) der Kanten in Pfeilrichtung wieder beim Ausgangsknoten anzukommen, so wird dieser Graph zyklisch genannt - es gibt dann einen Kreis (auch Zyklus genannt) in dem Graphen.

Doch was könnte ich als nächstes tun? Nun, an der Tatsache, dass ich jetzt in die Stadt fahren könnte hat sich nichts geändert. Da ich aber den Computer inzwischen aufgebaut habe, kann ich ihn jetzt auch ins Netz bringen. Schließlich habe ich den einzigen Abhängigkeitspfeil, der auf die Aufgabe "Computer ins Netz bringen" gezeigt hat, soeben "gelöscht". Alle anderen Aufgaben können noch nicht erledigt werden. Da ich aber gerade am Rechner sitze, bringe ich ihn auch gleich ins Netz.
Dadurch ändert sich mein ToDo-Graph erneut.

Nun könnte ich immer noch in die Stadt fahren, die Internet-Recherche für den Deutschaufsatz machen, den Placebo-Song kaufen oder aber meine Mathehausaufgaben ausdrucken ...

So, gleich geht es zur Party und ich wollte nur ganz kurz zusammenfassen, in welcher Reihenfolge ich meine Aufgaben heute erledigt habe:

1. Müll rausgebracht
2. Schuhe geputzt
3. Computer aufgebaut
4. Computer ins Netz gebracht
5. Placebo-Song gekauft
6. Party-Sampler gebrannt
7. In die Stadt gefahren
8. Spülmittel gekauft
9. Cola gekauft
10. Buch aus der Bibo geholt
11. Abgewaschen
12. Internet-Recherche erledigt
13. Deutschaufsatz geschrieben
14. Aufgabenblatt gedruckt
15. Mathehausaufgaben gemacht

Nach jeder erledigten Aufgabe habe ich den entsprechenden Eintrag in meinem ToDo-Graph nebst der von dem Eintrag ausgehenden Pfeile entfernt, was dazu führte, dass alle Knoten des Graphs nach und nach entfernt wurden. Ich habe die Einzelschritte gespeichert (von links nach rechts und von oben nach unten zu lesen). Du kannst ein Vorschaubild anklicken, um die entsprechende Abbildung zu vergrößern.

Mein großer Bruder, der Informatik studiert, hat mich gerade darüber aufgekärt, dass mein Vorgehen "topologisches Sortieren" genannt wird. Er hat mir auch die folgende Algorithmenbeschreibung geschenkt:

Der Algorithmus TopSort gibt die Knoten eines gerichteten Graphes in topologischer Reihenfolge aus. Der Graph G=(V,E) besteht hierbei aus der Menge der enthaltenen Knoten V und der Kantenmenge E der Form (Knoten1, Knoten2), wobei die Abhängigkeit von Knoten1 nach Knoten2 geht und beide Knoten auch in V vorhanden sein müssen.

Der Algorithmus erkennt auch, ob ein Graph zyklische Abhängigkeiten enthält. Derartige zyklische Graphen lassen sich nicht topologisch sortieren, daher muss bei jedem Schritt geprüft werden, ob auch tatsächlich ein Knoten entfernt wurde. Ist dies einmal nicht der Fall, so bricht der Algorithmus automatisch ab.

Das oben verwendete Beispiel verdeutlich auch ein wesentliches Problem von Computern. Sie arbeiten normalerweise "stupide" ihre Arbeitsschritte ab. Ziel von TopSort ist es, EINE mögliche topologische Sortierung zu finden. Eine so bestimmte gültige topologische Sortierung wäre z.B. auch:

• ...
• In die Stadt gefahren
• Spümittel gekauft
• Abgewaschen
• ...
• Cola gekauft
• ...

Hätten wir nicht nach dem "in die Stadt fahren" alle Einkäufe erledigt, dann hätten wir das Problem, dass wir später noch einmal in die Stadt fahren müssen, aber diese Information wurde dann ja schon aus dem Graph entfernt. Ein klein wenig Organisationstalent gehört also neben dem algorithmischen Abarbeiten einer Aufgabenliste auch noch dazu, wenn man seinen Alltag planen will.