Diskussion:Topologische Sortierung

Dieser Artikel war am 21. Juli 2005 der Artikel des Tages.

Diskussion aus Wikipedia:Review:

Schnittregel und Gentzenscher Hauptsatz im "siehe auch"

Kann mir mal jemand erklären, was die mit dem Lemma zu tun haben? -- Andreas Tanner 22:30, 14. Dez. 2009 (CET)

Länge des Artikels ein Desaster

Mal im Ernst ist das hier ein Witz oder ein Spielplatz? Es darf doch wohl nicht wahr sein dass der Artikel so gigantisch ist, ich wollte gerade beim Lernen mal das nachschlagen und wurde ERschlagen von diesem Artikel, wenn ich schon sehe wie riesig die Diskussionsseite ist, dann glaube ich, dass hier leute am Werk sind die sonst nix zu tun haben. Beschränkt euch mal AUF DAS WESENTLICHE, das ist hier keine Buch zum Thema Topologische Sortierung! (nicht signierter Beitrag von 95.223.157.35 (Diskussion | Beiträge) 03:58, 24. Jul 2009 (CEST))

Jo, zustimm, den englischen Wiki versteht man viel besser, nämlich weil er auf mathematische Formensprache verzichtet. Außerdem wird dort neben dem Algo nach Lasser auch der viel effizientere rekursive Algo gezeigt.

-- ErfinderDesRades 00:32, 26. Dez. 2010 (CET)

Ich denke der Abschnitt Beispiele und das Programmierbeispiel in Perl sollten komplett raus. Erstens ist das anfangs gegebene Beispiel mit der Reihenfolge der Kleidung bereits ein Beispiel und zweitens sind alle sprachen spezifischen Codebeispiele hier völlig fehl am Platz, es muss nur der Pseudocode angegeben werden, alles andere ist unprofessionell für eine Enzyklopädie.

--Samleans 21:19, 6. Jan. 2011 (CET)

Anfang

Der Name "topologische Sortierung" leitet sich von den griechischen Worten τόπος (tópos = Ort/Platz) und λόγος (lógos = eigentlich Wort, im weiteren Sinn Lehre von ...) ab, hat aber nichts mit der mathematischen Disziplin Topologie zu tun.

Ich finde es unschön, wenn ein Artikel damit beginnt, zu erklären, was etwas nicht ist. Die Ethymologie des Begriffs Topologie hilft zum Verständnis leider auch nichts. Dass der (komplizierte) griechische Begriff Logos noch dazu unscharf und unvollständig übersetzt ist, killt diesen Anfang. Sorry wegen der Kritik, aber in den Artikel ist offensichtlich sehr viel Arbeit geflossen. Er hat einen sehr guten Anfang verdient. Die Behelfs-Erklärungen, die dem ersten Absatz folgen, ersetzen eine klare, präzise und konzise Definition leider nicht. Grüße, Matthias

Topologisches Sortieren, 6. Juli

Ist das genügend und einigermaßen verständlich? --Hubi

Mir ist nicht ganz klar, warum man die Socken vor der Hose anziehen muss :-)

Ok, im Ernst, ich finde es verständlich (bin aber auch kein Computerlaie). Kleiner Tipp: Im Beispiel mit der Rekursion wäre es – da ohnehin Pseudocode – vielleicht sinnvoll, jeden Aufruf explizit mit "call" einzuleiten, dann ist es vielleicht auch für Leute ohne Programmierkenntnisse klarer, was das darstellen soll (das ist aber natürlich nur eine Vermutung, da ich definitiv Programmierkenntnisse habe).

Der Abschnitt "Repräsentation im Rechner" könnte für Nichtprogrammierer evtll. auch etwas kryptisch sein.

Der Begriff "Halbordnung" sollte m.E. irgendwo im Artikel auftauchen.

Insgesamt aber: Schön gemacht! --Ce 17:31, 6. Jul 2004 (CEST)

So, Halbordnung ist drin und "Repräsentation im Rechner" geändert und ergänzt --Hubi 14:12, 7. Jul 2004 (CEST)

Ich würde in der Einleitung noch erwähnen, worum (um welche Anwendungsgebiete etc.) es in dem Artikel eigentlich geht, "Beziehungen zwischen Objekten" sind sehr abstrakt, bzw. allgemein-unspezifisch. Grüße, Root axs 18:27, 6. Jul 2004 (CEST)

Ja, aber eigentlich geht's genau darum, das Objekt ist das unwichtigste, wichtig ist nur, dass irgendeine Art von Beziehung existiert, die zyklenfrei ist. Die Anwendungsgebiete sind also unbegrenzt. --Hubi 08:35, 7. Jul 2004 (CEST)

Habe den Artikel eben bisschen überarbeitet. Allerdings nicht inhaltlich, sondern nur durch TeX-Formatierungen und Wikilinks. Frage zum letzten Abschnitt "Kategorien": Sind damit Kategorien in der herkömmlichen Bedeutung des Wortes gemeint, wie die in der Wikipedia, oder etwa Objekte der mathematischen Kategorientheorie? Besser erklären! --Langec 20:21, 6. Jul 2004 (CEST)

Ursprünglich ging ich davon aus, dass das Kategoriensystem der Wikipedia auf ein hierarchisches System hinausläuft, so dass dies ein gutes Beispiel ist. Da dies anscheinend nicht zwingend und nicht mal das Beste System ist, habe ich den Abschnitt allgemeiner formuliert und ergänzt. --Hubi 08:30, 7. Jul 2004 (CEST)

Ich habe den Zusammenhang zur Topologie noch nicht so ganz verstanden. Vielleicht könnte der Artikel um einen Hinweis auf typisch topologische Eigenschaften ergänzt werden (vgl. Topologie (Mathematik)). Welche Verformungen werden betrachtet, und welche Eigenschaften bleiben dabei erhalten? --Sledge 17:11, 11. Jul 2004 (CEST)

Auf diesen Punkt ist ja schon im Artikel eingegangen worden. Trotzdem störe ich mich noch ein wenig an dem "eher" in dem dritten Satz, dass sich ja auf die Diskussionseite bezieht und ein "als" im Artikel schuldig bleibt. Ich denke ich bin mal mutig und versuche mich gleich mal an einer Umformulierung. --Sledge 19:07, 14. Jul 2004 (CEST)

Ich habe das nun mal umformuliert, aber je länger ich mir das jetzt anschaue, um so mehr zweifle ich daran, ob die Erläuterung überhaupt noch notwendig ist. Jetzt wo klar gesagt wird, dass es sich beim topologischen Sortieren um einen Algorithmus handelt, ist die Gefahr "topologisch" im streng mathematischen Sinne zu interpretieren gar nicht mehr so groß. Was sagt ihr dazu? Kann man den dritten Satz weglassen? Wiederholt sich die Erläuterung gar? Ich lasse es erst mal stehen und wirken... --Sledge 19:26, 14. Jul 2004 (CEST)

Na ja, es ist nicht nur ein Algorithmus (auch Graphentheorie spielt eine Rolle, und es ist ein Ordnungsproblem). Das als war eher implizit (als normales Sortieren), das eher kann aber raus. Ich bin für drin lassen. --Hubi 07:44, 15. Jul 2004 (CEST)

Darstellung als gerichteter Graph

Ich vermute, dass bei der Darstellung der ersten beiden Graphen des Artikels folgender Fehler vorliegt:

Es sollte kein Relationspfeil von Socken zu Hose gezeichnet werden.

Begründung:

1. Die vier Paare der Anziehrelation definieren keine Beziehung zu dem Element Socken.
2. Die Beschreibung unter dem zweiten Graphen "Dass die Socken hier allein stehen, stört nicht. Sie können an einer beliebigen Stelle eingeordnet werden." legt nahe, dass tatsächlich keine Beziehung zu dem Element Socken definiert werden soll.
3. Wie bereits von Ce am 6. Juli angemerkt ist die Beziehung "Socken vor Hose" nicht sehr anschaulich.

--Sledge 16:35, 11. Jul 2004 (CEST)

Du hast eine alte Version der Bilder und eine neue Version des Artikels. Die Socken habe ich um die Zeit deines Kommentars überall entfernt. --Hubi 10:56, 12. Jul 2004 (CEST)

Stimmt genau, die Bilder hatten bei mir einen anderen Stand als der Text. Erst nach einem expliziten Refresh habe ich nun die korrekten Bilder gesehen, danke für den Hinweis. Sieht so aus, als ob ich mich etwas intensiver mit den Cache-Funktionen meines Browsers auseinander setzen sollte. --Sledge 21:28, 12. Jul 2004 (CEST)

Mathematische Ordnungsrelation

Ich möchte die folgenden beiden Verbesserungsvorschläge zur Diskussion stellen:

1. Der Relation R sollte ein Name gegeben werden, der in diesem Zusammenhang eindeutig ist und eine Diskussion des Themas vereinfacht (z.B. „topologische Sortierung“). Damit liegt dann eine unmissverständliche Begriffsdefinition vor.
2. Die angegebene Formel für die Irreflexivität passt nicht ganz zu dem erläuternden Text hinter der Formel. Ich würde die Formel eher so übersetzen „a steht mit a in der Relation nicht R“. Da dann aber noch zu klären ist was denn „nicht R“ bedeutet, möchte ich vorschlagen, die Erläuterung beizubelassen und die Formel wie folgt zu ändern: $\neg (aRa)$

--Sledge 17:43, 11. Jul 2004 (CEST)

Ursprünglich war dort R, was dann in TeX übersetzt wurde (nicht von mir). $a\neg Ra$ ist für mich kein wohlgeformter Satz der Formalen Logik, dein Vorschlag aber schon. Daher halte ich deine Form auch für besser. Deine Übersetzung halte ich für nicht so gut. --Hubi 10:56, 12. Jul 2004 (CEST)

Hm, ja, die Form $a\neg Ra$ habe ich verbrochen. Ich hab jetzt noch mal nachgeguckt; ich habe mich nicht ganz richtig ans erste Semester erinnert. Wir haben immer $a(\neg R)a$ geschrieben, eben als Kurzform für $\neg (aRa)$. --Langec 12:57, 12. Jul 2004 (CEST)

Die Form $a(\neg R)a$ ist zwar viel besser, aber immer noch nicht so ganz wohlgeformt, d.h. mein formaler Formelverifyer würde mir das um die Öhren hauen, vergleiche $a(\neg <)a$ :-) --Hubi 14:23, 12. Jul 2004 (CEST)

Ich habe ja nicht behauptet, dass $a(\neg R)a$ überhaupt keinen Sinn macht. Es ist nur so, dass dies eine ganz andere (bei geeigneter Definition von $\neg R$ aber äquivalente) Aussage als $\neg (aRa)$ ist. Mein Vorschlag war, die Aussage zu vereinfachen, indem man darauf verzichtet eine neue Relation $\neg R$ einzuführen.

Eine mögliche Definition für $\neg R$ wäre z.B.:

Def. Negation einer Relation.

Seien $A$ und $B$ Mengen und $R\subseteq A\times B$. Dann heißt

$\neg R:=\lbrace x\in A\times B|x\notin R\rbrace$

die Negation von $R$.

--Sledge 15:10, 12. Jul 2004 (CEST)

Ja, ich glaub wir liegen eh auf einer Linie. Warum eine ungewöhnliche, wenn auch nicht verbotene Notation einsetzen, wenn's die normale auch tut. --Hubi 15:48, 12. Jul 2004 (CEST)

Ok, ich denke der zweite Vorschlag ist ausreichend diskutiert und ja bereits im Artikel berücksichtigt worden. Bei dem ersten Vorschlag liegt vermutlich ein Missverständnis meinerseits vor. Ich bin davon ausgegangen, dass der Absatz auf eine mathematische Begriffsbestimmung hinausläuft, möglicherweise ist er jedoch nur als kurzer Exkurs in die Mengenlehre gedacht.

Vielleicht kann man dem Leser ein wenig mehr Orientierung an die Hand geben, wenn man an prominenter Stelle erläutert, welcher Gegenstand in dem Artikel denn überhaupt beschrieben wird. Will sagen: Beschreibt Topologisches Sortieren nun einen Begriff der Mengenlehre oder Graphentheorie oder vielmehr einen Algorithmus? Wird eine Tätigkeit erforscht, die es schon seit Jahrtausenden gibt oder ist es etwas völlig neues?

Ein anderer Leser mag vielleicht nicht solche Probleme haben. Dieser Tipp beruht natürlich auf meinem ganz persönlichen Eindruck, aber den wolltest Du ja hören, sonst hättest Du den Artikel ja nicht ins Wikipedia gestellt ;-) --Sledge 22:21, 12. Jul 2004 (CEST)

---

Ich möchte mal einen Vorschlag für eine Begriffsdefinition machen. Den folgenden Abschnitt würde ich gerne unter "Die topologisch Sortierte Menge" einfügen, möchte jedoch zunächst ein erstes Feedback abwarten. Es wäre wichtig zu wissen, ob ihr dieses Begriffsverständnis teilt.

Defintion in den Artikel übernommen --Sledge 11:49, 17. Jul 2004 (CEST)

Mangelhafter Beispielalgorithmus

Ich hoffe ich bin da nicht zu penibel, aber der geschilderte Algorithmus hängt sich so leider auf jeden Fall bei der Berechnung der Vorgängerzahlen auf, falls der Graph zyklisch ist.

Nein, für jedes Element wird die endliche Liste (!) der Nachfolger (linear) durchlaufen. Die Elementliste ist ebenfalls linear. Das gilt auch für zyklische Graphen, wie man leicht mit dem Perl-Programm ausprobieren kann. --Hubi 16:20, 29. Sep 2006 (CEST)

Anwendungsprogramm in Perl, C?

In der Diskussion zu den exzellenten kam die Frage auf, ob man nicht ein Beispielprogramm in den Artikel stellen sollte. Ich hab mal ein Programm in C (86 Zeilen, keine Fehlerüberprüfung) und eines in Perl (46 Zeilen) erstellt, jeweils incl. Einlesen, Anwendung ähnlich tsort. Eigentlich meine ich, das das nicht nötig ist. (nur wenig getestet) --Hubi 14:30, 14. Jul 2004 (CEST)

So, mit Kommentaren, die dem Programm gut getan haben und Initialisierung aller Variablen ist es jetzt etwas länger. Eigentlich könnte es so schon in den Artikel. Kürzer und halbwegs verständlich krieg ich's nicht hin. --Hubi 18:26, 14. Jul 2004 (CEST)

logos

Ich hab' mal gerade in meinem Griechischwörterbuch nachgeschlagen: logos (λόγος) heißt dort: Logos (was auch immer das sein mag), Wort, Sprache, Rede, Grund oder Vernunft. Das Wort λόγος im Zusammenhang mit Lehre konnte ich nicht finden (was aber kein Grund sein muss, dass es nicht stimmt, das Wörterbuch taugt einfach nix). Topos (τόπος) ist korrekt übersetzt.--Berni 16:19, 16. Jul 2004 (CEST)

Die Übersetzung stammt aus dem Wikipedia-Artikel Topologie, naja vielleicht Rede = Lehre (?), aber ich bin natürlich auch kein Übersetzungsguru. --Hubi 16:35, 16. Jul 2004 (CEST)

Versuch eines Anfangs, falls der Artikel in "Topolische Sortierung" umbenannt wird

Bei den Exzellenten-Kandidaten ist soeben die Idee aufgekommen, den Artikel umzubenennen. Um mir darüber klar zu werden, was ich besser finde, versuche ich hier mal den Anfang des Artikel aufzuschreiben, für den Fall dass dieser umbenannt wird:

Unter einer topologischen Sortierung versteht man eine sortierte Menge, bei der die Sortierreihenfolge von einem weniger starken Kriterium -- einer Halbordnung -- abhängt, als dies bei der (gewöhnlichen) Sortierung der Fall ist, wo eine Totalordnung vorausgesetzt werden muss. Dies führt dazu, dass in der Regel zu einer gegebenen Menge und einem gegebenen Sortierkriterium mehrere topologische Sortierungen existieren.

Kommentar von meinem Bruder: "Das versteht keine Sau." Na gut, noch ein Versuch:

Hat man eine Menge von Daten (oder Gegenständen) gegeben, z.B. Aufgaben in einem Projekt, so ist es oftmals notwendig, diese zu sortieren und eine feste Reihenfolge festzulegen. Dabei hängt die Reihenfolge in der Regel von einem bestimmten Kriterium ab, z.B. Aufgabe A muss vor Aufgabe B erledigt werden. Eine derart sortierte Menge nennt man topologische Sortierung.

Es kann durchaus sein, dass es zu einer gegebenen Menge und einem Sortierkriterium mehrere topologische Sortierungen gibt, wenn beispielsweise Aufgabe B und Aufgabe C unabhängig voneinander ausgeführt werden können. Es ist dann egal ob zuerst Aufgabe B und dann Aufgabe C ausgeführt wird, oder anderstrum. Gibt es nur eine Möglichkeit, die Daten bezüglich des Kriteriums zu sortieren, so erhält man eine (gewöhnliche) Sortierung.

Das bedeutet, anderst, als dies die Bezeichnungen vermuten lassen, dass jede Sortierung eine topologische Sortierung ist, aber eine topologische Sortierung nicht unbedingt eine Sortierung sein muss.

Der Name "topologische Sortierung" leitet sich von der mathematischen Disziplin Topologie, der Lehre vom Raum/Ort ab (τόπος (tópos) = Ort/Platz, λόγος (lógos) = Lehre).

Die topologische Sortierung ist bei vielen Anwendungen der Informatik ein wichtiges Konzept. Bereits 19?? wurde deshalb von ??? ein Algorithmus entwickelt, mit dem eine topologische Sortierung erstellt werden kann. Des Weiteren spielt die topologische Sortierung in der Graphentheorie bei der Untersuchung von Graphen auf Zyklenfreiheit eine große Rolle.

Das hat mein Bruder jetzt verstanden. Oma hab' ich leider keine zur Hand. ;-) --Berni 18:22, 16. Jul 2004 (CEST)

Hmm, dafür habe ich es nun nicht verstanden :-(

Also mal konkret: Den ersten Absatz vom zweiten Versuch finde ich ganz gut. Er deckt sich auch mit der formalen Beschreibung, die ich weiter oben gegeben habe (Menge + schwache Sortierung = topologische Sortierung). Was ich allerdings nicht verstehe, ist die Aussage: "dass in der Regel zu einer gegebenen Menge und einem gegebenen Sortierkriterium mehrere topologische Sortierungen existieren", die in ähnlicher Form in beiden Ansätzen vorkommt.

Ursache für mein Unverständnis ist vermutlich, dass wir uns noch nicht auf eine klare Begriffsdefinition für eine topologische Sortierung geeinigt haben (vgl. z.B. den Vorschlag weiter oben). Oft ist nicht klar, ob im Zusammenhang mit der topologischen Sortierung nun von einer strengen Halbordnung oder von einem Algorithmus die Rede ist.

Nach meinem Verständnis ist es doch so, dass das gegebene Sortierkriterium genau die strenge Halbordnung definiert, die im Zusammenhang mit einer topologischen Sortierung stets erwähnt wird. Nach meinem Vorschlag ist diese strenge Halbordnung die topologische Sortierung. Insbesondere legt damit die Menge und das "Sortierkriterium" die topologische Sortierung eindeutig fest. Was nicht eindeutig ist, ist die Erweiterung zu einer strengen Totalordnung. Diese hängt von der Art des gewählten Algorithmus ab, der leider ebenfalls eine topologische Sortierung genannt wird. --Sledge 19:57, 16. Jul 2004 (CEST)

Ich beziehe mich auf die Definition im Buch von Ottmann/Widmayer. Dort steht: "Eine topologische Sortierung eines Digraphen G=(V,E) ist eine Abbildung ord: V → {1,...,n} mit n=|V|, sodass mit (v,w) ∈ E auch ord(v)<ord(w) gilt." Aus dem nachfolgenden Text lässt sich dann schließen, dass die Abbildung bijektiv sein soll, auch wenn es nicht dabei steht.

Ich habe mir jetzt mal die Mühe gemacht, die ersten 20 Treffer bei Google durchzusehen. Durchweg wird der Begriff in der gleichen Bedeutung benutzt. Gelegentlich steht das mit dem bijektiv auch noch dabei.

Von daher denke ich, dass wir diese Bedeutung benutzen sollten, und nicht die, die du oben vorgeschlagen hast (auch wenn ich intuitiv wohl auch deine Definition benutzt hätte, oder sowas in der Richtung).

Umgangssprachlich bedeutet die Definition von Ottmann/Widmayer übrigens, dass eine topologische Sortierung eine Durchnummerierung der Knoten ist, also eine sortierte Menge.--Berni 22:53, 16. Jul 2004 (CEST)

Zusatz: Es ist also weder eine Halbordnung noch ein Algorithmus. Algorithmen zur Erzeugung von topologischen Sortierungen werden aber oft auch als Topologische Sortierung bezeichnet.--Berni 22:55, 16. Jul 2004 (CEST)

Ok, ich glaube dann habe ich den Zusammenhang nun verstanden. Wenn also $M$ unsere zu sortierende Menge ist, und die strenge Halbordnung $R\subseteq M\times M$ unsere schwache Sortierbeziehung, dann ist $(M,R)$ ein Digraph. Falls nun ein Algorithmus eine $R$-verträgliche, topologische Sortierung für $M$ findet, so liefert er damit genau die Abbildung ord, die im Sinne von Ottmann/Widmayer eine topologische Sortierung ist.

Damit wird offenbar das Ergebnis eines (topologischen) Sortierprozesses topologische Sortierung genannt, und nicht wie von mir vermutet die schwache Sortierung selbst, die ja ein Startparameter des Prozesses ist.

Das einzige, was ich noch nicht ganz verstehe ist, warum Ottmann/Widmayer eine topologische Sortierung nur für endliche Graphen einführen. Die erwähnte Abbildung ord impliziert ja auch eine strenge Totalordnung (vgl. Anmerkungen über transitive Hülle). Andererseits impliziert eine strenge Totalordnung auf einer endlichen Menge auch die gesuchte Abbildung ord:

$ord(1):=min_{R}M,ord(i):=min_{R}(M\setminus ord^{-1}(\lbrace 1,...,i-1\rbrace ))f.a.\ i=2,...,n$

Daher sehe ich keinen Grund, warum man eine topologische Sortierung nicht gleich mit einer strengen Totalordnung identifizieren sollte. Dann besteht auch keine Notwendigkeit mehr eine endliche Knotenmenge vorauszusetzen (obwohl das aus praktischen Erwägungen für den Algorithmus natürlich immer noch nötig sein kann). --Sledge 00:28, 17. Jul 2004 (CEST)

Ich denke, das liegt einfach daran, dass Ottmann/Widmayer sich in ihrem Buch nur mit endlichen Strukturen beschäftigen, da dies in der Praxis die einzig relevanten sind. Das klärt dann, warum sie sich auf endliche Graphen beschränken. ich stimme dir zu, dass man sie so, wie du das machst, auch auf unendliche Graphen erweitern kann. Was für Auswirkungen dies auf Aussagen über topologische Sortierung hat, weiss ich allerdings nicht. Kann man dann noch auf Zyklenfreiheit testen? Ich vermute nicht, zumindest nicht in endlicher Zeit.--Berni 10:54, 17. Jul 2004 (CEST)

Also ich halte eine Verallgemeinerung nicht für weiter schlimm. Die Auswirkungen auf die bisherigen Aussagen des Artikels sind minimal. Man muss lediglich sagen, dass sie nur für eine endliche Knotenmenge gelten, wenn man sich nicht sicher ist, dass sie auch für eine unendliche Knotenmenge gelten. --Sledge 11:37, 17. Jul 2004 (CEST)

Das mit der Verallgemeinerung würde ich so lösen, wie wir das schon in einigen anderen Artikeln gemacht haben: Zuerst im Artikel nur die endliche Version benutzen und dann einen Abschnitt "Verallgemeinerung" oder so ähnlich. Das hat den Vorteil, das die Leute, die eher an der praktischen Seite interessiert sind und die Leute, die nahezu keine Vorkenntnisse haben, nicht gleich mit komplizierten Sachverhalten überschüttet werden.--Berni 17:51, 18. Jul 2004 (CEST)

Ich finde den dritten Satz der neuen Einleitung immer noch etwas unglücklich formuliert. Es ist nicht ganz klar, ob mit der topologischen Sortierung nun die "feste Reihenfolge" oder das "bestimmte Kriterium" gemeint ist. Mißverständnisse wie diese haben aber zu meinem gescheiterten, ersten mathematischen Definitionsversuch geführt. Ich versuche mich mal an einer Korrektur. --Sledge 16:34, 18. Jul 2004 (CEST)

So wie ich den Begriff inzwischen verstehe, weder noch. Der Begriff wird tatsächlich so benutzt, dass es sich bei einer topologischen Sortierung um eine Menge mit einer totalen Ordnung, die eine gegebene partielle Ordnung respektiert, handelt. Eine Reihenfolge hebt nur eine Ordnung, ein Kriterium im Grunde genommen auch. Ich bin mit dem Anfang aber immernoch nicht zufrieden und tendiere inzwischen wieder dazu, den Artikel zurück zu ändern in "topologisches Sortieren". Die (englische) Originalliteratur benutzt den Begriff "topological sorting", was erst mal beides sein kann. Es wird aber als Aktivität benutzt.--Berni 17:51, 18. Jul 2004 (CEST)

Den folgenden Abschnitt der neuen Einleitung habe ich nicht verstanden:

"Das bedeutet, anders als dies die Bezeichnungen vermuten lassen, dass jede Sortierung eine topologische Sortierung ist, aber eine topologische Sortierung nicht unbedingt eine Sortierung sein muss."

Möglicherweise liegt das daran, dass der Begriff der Sortierung unklar ist. Nach meiner Vorstellung, ist eine Sortierung eine strenge Totalordnung, also das, was in der Einleitung mit "fester Reihenfolge" beschrieben wird. Nach dieser Vorstellung ist aber eine topologische Sortierung immer auch eine Sortierung. Sie hat halt nur die zusätzliche Eigenschaft, dass sie bestimmte vorgegebene Kritierien erfüllt (z.B. Aufgabe A vor B).

Vielleicht kann mir ja jemand mit diesem Mißverständnis helfen, oder mich in der Absicht den entsprechenden Abschnitt zu streichen bestärken. --Sledge 17:11, 18. Jul 2004 (CEST)

Ich habe das so verstanden: Eine Sortierung ist das Ergebnis eines Sortierprozesses bzgl. einer Totalordnung und eine topologische Sortierung ist das Ergebnis eines Sortierprozesses bzgl. einer partiellen Ordnung. Ich gebe die aber Recht, der Begriff Sortierung ist eher ungebräuchlich. Vielleicht bekommen wir das doch noch etwas besser hin. --Berni 17:31, 18. Jul 2004 (CEST)

Hmm, was ist denn "das Ergebnis eines Sortierprozesses"? Ist das nicht eine (strenge) Totalordnung? Ferner ist mir aufgefallen, dass es gar nicht notwendig ist, eine partielle Ordnung vorauszusetzen, um eine topologische Sortierung durchzuführen. So bilden die Kleidungsstückpaare aus dem ersten Beispiel ja gerade keine partielle Ordnung. --Sledge 14:55, 20. Jul 2004 (CEST)

Also, im Computer bedeutet das, dass die Anordnung der Elemente in der Datenstruktur (also die Ordnung, die durch diese Datenstruktur induziert wird) mit der vorgegebenen Ordnung übereinstimmt.

Beispiel: Die Liste U = ( 2, 5, 1, 8, 3 ) ist bezüglich der normalen Ordnung ganzer Zahlen ("kleiner als") unsortiert, die Liste S = ( 1, 2, 3, 5, 8 ) ist sortiert. Das Ergebnis des Sortierens der unsortierten Liste U ist die sortierte Liste S.

Natürlich gilt die Totalordnung der ganzen Zahlen auch in der unsortierten Liste, sie stimmt aber nicht mit der durch die Datenstruktur induzierten Ordnung ("steht früher in der Liste") überein.

Was die partielle Ordnung angeht, die erhält man durch transitiven Abschluss der durch die angegebenen Paare gegebenen Relation (davon handelt der letzte Absatz im Abschnitt "Die zu sortierende Menge"). Wenn dieser transitive Abschluss keine Halbordnung liefert (also ein Zyklus existiert), dann lässt sich die Menge nicht topologisch sortieren. --Ce 17:06, 20. Jul 2004 (CEST)

Dazu braucht man aber den transitiven Abschluss nicht. Wenn nämlich die ursprüngliche Relation keinen Zyklus enthält, so enthält der transitive Abschluss auch keinen. Das liegt daran, dass durch den transitiven Abschluss ja genau die Paare hinzukommen, die ich auch durch Wege verbinden kann. Man erhält also höchstens kürzere Zykel, aber keine neuen. --Sledge 17:24, 20. Jul 2004 (CEST)

Was den Begriff der Sortierung angeht, so glaube ich, dass unsere Vorstellungen mit "sortierter Liste" und "strenger Totalordnung" in etwa übereinstimmen. Trotzdem hat mir das noch nicht geholfen, die oben zitierte Aussage aus dem Artikel zu verstehen. Ist es wirklich schlimm, wenn wir den Satz "Das bedeutet, anders als dies die Bezeichnungen vermuten lassen, ..." erst mal mal wieder aus dem Artikel herausnehmen? Zumindest bis wir eine bessere Formulierung gefunden haben? --Sledge 18:51, 20. Jul 2004 (CEST)

Ich bin dafür, dass wir in drin lassen, bis wir was besseres haben. Das motiviert schon mehr :-) Und zudem finde ich, dass der Artikel darauf aufmerksam machen sollte, dass da was ungewöhnlich ist.--Berni 21:46, 20. Jul 2004 (CEST)

Hmm, irgendwie bin ich nicht so begeistert von der Idee, dass die Passage nur so als "Lesezeichen" stehen bleibt. Für einen Hinweis, dass da noch ein Punkt offen ist, ist die Diskussionsseite doch viel besser geeignet. Ich glaube auch nicht, dass der Artikel den Status "exzellent" verdient, solange da eine falsche - na, ich sage mal lieber vorsichtiger "unbegründete" - Aussage stehen bleibt. Es macht vermutlich auch nicht viel Sinn, den Abschnitt wechselseitig zu Löschen und wieder einzufügen.

Da ich noch nicht so lange bei Wikipedia bin, kenne ich leider nicht die Mechanismen, die es gibt um so ein Problem zu lösen. Da ich das Problem aber eigentlich für ausreichend diskutiert halte, würde ich so etwas wie eine Abstimmung vorschlagen. Wie kann man denn so eine Abstimmung durchführen, und vor allem für ein breiteres Interesse sorgen um etwas mehr als drei Stimmen zu mobilisieren? Macht so etwas wie eine Abstimmung überhaupt Sinn, wenn jeder beliebig viele Benutzeraccounts anlegen kann? --Sledge 11:09, 21. Jul 2004 (CEST)

Im Grunde genommen sollte man das so lösen, dass man eine Version schreibt, die allen gefällt, bzw. mit der zumindest alle Leben können. In sofern taugen beide Varianten nichts. Mein Problem in dem Zusammenhang ist, dass ich übermorgen in Ferien fahre und deshalb nicht genügend Zeit habe, um mich des Problems anzunehmen.

Abstimmung halte ich für wenig sinnvoll. Das mit den beliebig vielen Accounts ist zwar beim Abstimmen möglich, ich denke aber, dass hier kaum jemand in der Richtung bescheißt.

Weiter denke ich, dass der Artikel es in diesem Anlauf nicht schaffen wird, in die Exzellenten zu kommen (ich bin zumindest immernoch dagegen). Dafür fehlt ihm noch einiges. Er ist aber durch den Aufenthalt bei den Kandidaten schon deutlich besser geworden.--Berni 11:25, 21. Jul 2004 (CEST)

Also ich werde mit der gegenwärtigen Einleitung auch nicht so richtig glücklich:

1. Daten (oder Gegenständen) - also gleich von Daten zu sprechen ist mir zu computerlastig. Topologisch sortiert werden Objekte, die in Beziehung zueinander stehen. Die geklammerte Gegenstände helfen auch nicht viel.
2. z.B. Aufgaben ... - Aufgaben sind (für mich) weder Daten noch Gegenstände im eigentlichen Sinn.
3. Die Erweiterung dieser Kriterien zu einer festen Reihenfolge nennt man topologische Sortierung - wie, die Erweiterung? oder die Kriterien? Oder nur die erweiterten Kriterien? Warum nicht: "Hat man eine bestimmte Reihenfolge gefunden, so nennt man diese topologische Sortierung.
4. Gibt es nur eine Möglichkeit, die Daten bezüglich des Kriteriums zu sortieren, so erhält man eine (gewöhnliche) Sortierung. Was ist eine gewöhnliche Sortierung? Später spricht der Artikel von Ordnung. In Mathematikbüchern, die ich kenne, finde ich keine Definition von Sortierung, nur Halbordnung, totale Ordnung etc. Sortieren im eigentlichen Sinne heißt eine Ordnung festlegen (siehe Wikipedia-Artikel Sortierung). Das kann also eine normale Sortierung (nach Eigenschaften, Vergleich beliebiger Objekte a priori möglich, vollständige Beziehungen), oder eine topologische Sortierung (nach Beziehungen, a priori ist nur ein Teil der Objekte in Beziehung) sein.
5. Gibt es nur eine Möglichkeit, die Daten bezüglich des Kriteriums zu sortieren, so erhält man eine (gewöhnliche) Sortierung. - Halte ich für falsch, denn wenn auf A folgt B und auf B folgt C festgelegt ist, stehen A und C nicht a priori in Beziehung, ich muss also topologisch sortieren, obwohl nur eine Möglichkeit der Sortierung existiert.
6. Das bedeutet, anders als dies die Bezeichnungen vermuten lassen, dass jede Sortierung eine topologische Sortierung ist, aber eine topologische Sortierung nicht unbedingt eine Sortierung sein muss. - Irgendwie, obwohl es nicht genau passt, erinnert mich das an Katze/Perserkatze/gewöhnliche Katze/Raubkatze, indem der Begriff Katze umgangssprachlich auch für gewöhnliche Katze verwendet wird. Eine Perserkatze ist eine ungewöhnliche gewöhnliche Katze, eine Raubkatze ist keine Katze i.e.S. usw. Fasst man den Begriff Sortierung umgangssprachlich auf, so gibt er wenig Sinn, da topologisch Sortieren ebenso wie Einsortieren (die Post in Postfächer) auch unter "Sortieren" fallen. Dass ein A mit der Eigenschaft x kein gewöhnliches A, vielleicht gar kein A mehr ist, braucht man der Oma mE nicht zu verklickern.

Da Berni in den (verdienten) Urlaub geht, schlage ich vor, den Artikel erst nach seiner Rückkehr ins Review (Mitte August oder einfach selbst machen) zu nehmen (wo er hingehört).

--Hubi 15:12, 21. Jul 2004 (CEST)

Zu 1. und 2. Hier ist das Problem, einen Begriff zu finden, der alles umfasst. Du benutzt Objekt, ich Ding. In beiden Fällen denke ich aber zuerst einmal an Gegenstände. Ich hab' noch keine Lösung für das Problem.

Zu 3. Meine Originalversion lautete: Eine derart sortierte Menge nennt man topologische Sortierung. Das kommt deiner Beschreibung sehr nahe. Irgendwer hat das dann "verbessert".

Zu 4. Hier benötige ich einen Begriff für das, was man üblicherweise als Sortierung bezeichnet (also das, was Quicksort und konsorten machen). Da ich hierfür keinen speziellen Begriff kannte, hab' ich diese Sortierung als gewöhnliche Sortierung bezeichnet. Du verwendest den Begriff natürliche Sortierung. Vermutlich ist das das, was ich suche.

Zu 5. Da hast du recht. Der Abschnitt soll die topologische Sortierung von der natürlichen abgrenzen.

Zu 6. Meines Wissens haben Adjektive in der Umgangssprache (und auch in der Regel in Fachsprachen) einschränkende bedeutung. Das heißt, wenn ich von den Eigenschaften eines Hauses spreche, dann beziehe ich mich auf mehr Objekte, als wenn ich von den Eigenschaften eines kleinen Hauses spreche. Hier liegt der Fall umgekehrt, was ungewöhnlich ist und verdient deshalb meiner Meinung nach Aufmerksamkeit.

Die Idee mit dem Review nach meinem Urlaub finde ich gut. Allerdings wird das wohl eher September werden.--Berni 16:15, 21. Jul 2004 (CEST)

Zu 1&2: Naja, ich glaube ihr habt schon gemerkt, dass ich eher der Fan einer formalen als einer umgangssprachlichen Beschreibung bin. Daher wird es euch wahrscheinlich auch nicht überraschen, dass ich hier "Element" vorschlage. Ich gebe aber zu, dass das kein sehr umgangssprachlicher Terminus ist.

Zu 3: Das mit der Erweiterung habe ich geschrieben und hatte da die formale Beschreibung im Kopf - btw: wie findet ihr eigentlich die formale Beschreibung? Können wir uns auf die angegebene formale Definition einigen?

Bei der aktuellen Beschreibung fehlt mir noch der Bezug zu den Kriterien, welche die gesuchte Reihenfolge ja berücksichtigen muss. Ich versuche mich mal an einer Verbesserung die nicht zu formal klingt.

Zu 4&5: Das mit der Sortierung habe ich auch noch nicht so ganz verstanden. Für mich ist eine Sortierung einfach eine strenge Totalordnung. Was Berni mit Sortierung meint ist formal vielleicht so etwas wie ein Paar von Relationen, wobei erstere beliebig ist und letztere stets eine strenge Totalordnung ist, welche erstere enthält. Sozusagen Vorher/Nachher. Eine gewöhnliche Sortierung ist dann vielleicht der Spezialfall, dass die erste Relation eine strenge Totalordnung ist. Ich bin mir aber nicht so sicher, ob es wirklich das ist was er meint.

Zu 6: Das mit der einschränkenden Bedeutung von Adjektiven sehe ich auch so. Nur habe ich nicht verstanden, warum das hier nicht gilt. Nach meiner Vorstellung ist eine Sortierung eine strenge Totalordnung und eine topologische Sortierung eine spezielle strenge Totalordnung, nämlich eine welche bestimmten vorgegebenen Kriterien genügt.

Den guten Urlaubswünschen schließe ich mich jedenfalls an! --Sledge 21:45, 21. Jul 2004 (CEST)

Ich hab mal Daten/Gegenstände zu Dinge geändert, da ich Aufgaben auch als Dinge anzusehen bereit bin, jedoch nicht als Gegenstände. Zu topologische Sortierung/gewöhnliche Sortierung habe ich jetzt einfach mal das Kritierium vorgegebene Beziehung für alle Paare eingefügt. Damit wird mE klar, wann TS=S und damit explizit auch, dass manchmal TS != S ist. Allerdings ist dies nicht exakt die vorhergehende Aussage, man kann sie aber wohl rausinterpretieren. --Hubi 17:33, 21. Jul 2004 (CEST)

So, ich glaube diese Einrücktiefe ist richtig, um auf Bernies Kommentar von 11:25 Uhr zu antworten (Hilft das eigentlich wirklich noch zur Orientierung? Ich bin kurz davor das mit den Einrückungen aufzugeben :-)

Zur Abstimmung: Ich habe da nochmal drüber nachgedacht, und denke, dass Du da recht hast, und zwar was das Schummeln angeht, als auch was die Nützlichkeit zur Problemlösung angeht. Das Schummeln passt nicht zu den sehr erwachsenen und sachlichen Diskussionen die ich hier beobachtet habe, und eine Abstimmung führt letztlich nur zu einer Lösung welche die Mehrheit bevorzugt und nicht notwendigerweise zu einer die richtig ist.

Zu den "exzellenten": Da dieses der erste größere Artikel ist, an dem ich mitwirke, fehlt mir zwar etwas die Vergleichsmöglichkeit, aber nach meinem Geschmack ist noch viel zu viel "Bewegung" in dem Artikel um überhaupt eine zutreffende Beurteilung abzugeben. Ich begrüße daher die Idee mit dem Review. --Sledge 21:04, 21. Jul 2004 (CEST)

Zur Abstimmung: Konsens (ggf. Kompromiss) ist besser als eine Abstimmung, wenn es wie hier um Inhalte geht. Du hast recht was die Skepsis gegenüber dem Ergebnis bei Abstimmungen angeht.

Zum Adjektiv: Man kann die topologische Sortierung als Verallgemeinerung der Sortierung ansehen, ähnlich wie eine komplexe Zahl eine verallgemeinerte Zahl ist. Bei der normalen Sortierung sind Kriterien a priori festgelegt, ich kann also wählen, ob ich topologisch (Topsort) oder gewöhnlich (Quicksort) sortiere - mit demselben Ergebnis. Topologisch sortieren kann man darüberhinaus, wenn nicht alle Kriterien vorher feststehen, es ist also allgemeiner. (Ich kann ganz im Sinne des Sophismus aber auch das Gegenteil zeigen, wie du es getan hast). Das Adjektiv "verallgemeinert" (verallgemeinerte Zahl) zeigt schon, dass das mit der Einschränkung nicht immer stimmt.

Vorher stand: Die Erweiterung ... nennt man topologische Sortierung. Dies war durch die ungünstige Satzkonstruktion missverständlich. Jetzt ist es besser. --Hubi 08:44, 22. Jul 2004 (CEST)

Der Hinweis mit dem Sophismus ist zwar ganz interessant, aber unberechtigt. Selbstverständlich sind beide Schlußfolgerungen korrekt, in dem Sinne, als von verschiedenen Vorraussetzungen auf verschiedene Ergebnisse geschlossen wird. Das ist ja gerade das Problem bei einer Definition, dass man nicht sagen kann sie wäre richtig oder falsch. Man kann halt nur sagen, dass sie sich für die eine oder andere Aussage mehr oder weniger eignet.

Mit dem Definitionsversuch von "21:45, 21. Jul 2004 (CEST) - Zu 4&5" habe ich mich vermutlich der Vorstellung von einer topologischen Sortierung als Verallgemeinerung einer Sortierung etwas angenähert. Letztlich macht es keinen Sinn über diese Aussage zu diskutieren, ohne eine formale Definition für eine Sortierung zu liefern. Mit meinem Vorschlag "Sortierung = strenge Totalordnung" und der Definition von topologischer Sortierung aus dem Artikel ist es trivial zu beweisen, dass jede topologische Sortierung eine Sortierung ist. Die gegenteilige Aussage stimmt unter diesen Vorraussetzungen jedenfalls nicht, und bleibt eine alternative, formale Definition schuldig. --Sledge 12:16, 22. Jul 2004 (CEST)

Wenn alle Kriterien vorher vorhanden sind -> normale/topologische Sortierung. Wenn Kriterien nur teilweise vorhanden sind -> topologische Sortierung. Wo fehlt da was an formaler Definition? Versteh ich nicht. --Hubi 14:44, 22. Jul 2004 (CEST)

Zur Definition von Sortierung

Um hier etwas Ordnung (no pun intended) und vor allem Navigierbarkeit in die Diskussionsseite zu bringen, habe ich jetzt einmal eine neue Überschrift für dieses Thema angefügt.

Sortierung = strenge Totalordnung entspricht irgendwie nicht ganz dem, was ich unter Sortierung verstehe. Wenn ich z.B. eine Liste mit Namen habe (wobei Namensgleichheit hier ausgeschlossen sein soll), dann existiert eine Totalordnung (nämlich die alphabetische Ordnung der Namen) unabhängig davon, ob die Liste sortiert ist oder nicht. Genauso ist bei meinem früheren Beispiel die Liste U = ( 2, 5, 1, 8, 3 ) definitiv nicht sortiert, obwohl eine totale Ordnung auf den ganzen Zahlen existiert.

Der Punkt ist, dass wir es bei der Sortierung immer mit zwei Ordnungen zu tun haben. Eine davon ist durch das Problem gegeben (Totalordnung der ganzen Zahlen, Halbordnung der Abhängigkeiten beim Anziehen, ...), die andere durch etwas, was man vielleicht allgemein äußere Struktur nennen könnte (Reihenfolge in der Liste, zeitliche Reihenfolge der Vorgänge, ...). Sortierung liegt m.E. vor, wenn die "Problemordnung" eine Teilmenge der "Strukturordnung" ist. Beispielsweise sind die Namen im Telefonbuch sortiert, da die alphabetische Ordnung (eine strenge schwache Ordnung, da Namensgleichheit auftreten kann) mit der "Leserichtungsordnung" übereinstimmt (Namen, die im Alphabet weiter vorne stehen, kommen auch früher im Telefonbuch).

Die Aufgabe des Sortierens ist nun, eine "Strukturordnung" herzustellen, die eine Obermenge der "Problemordnung" ist.

Vielleicht ist ein Begriff, der hier evtll. weiterhelfen könnte, der der Reihenfolge. Das, was ich oben mit "Strukturordnung" wiedergegeben habe, kann man eigentlich immer auch mit "Reihenfolge" bezeichnen. Das Telefonbuch enthält die Namen in alphabetischer Reihenfolge, und die Kleider werden in einer bestimmten Reihenfolge angezogen. --Ce 13:37, 22. Jul 2004 (CEST)

Wir sollten auch Sortieren (Finden einer Reihenfolge) von Sortierung (Eigenschaften einer gegegenen Reihenfolge) unterscheiden - wenn man den Begriff Sortierung so verstehen will. Ich zitiere nochmal aus der Einleitung der vorigen Version: Das bedeutet, anders als dies die Bezeichnungen vermuten lassen, dass jede Sortierung eine topologische Sortierung ist, aber eine topologische Sortierung nicht unbedingt eine Sortierung sein muss. und Sledge: Mit ... der Definition ... ist es trivial zu beweisen, dass jede topologische Sortierung eine Sortierung ist. Das genaue Gegenteil. Allerdings geht ersteres mehr von "Sortieren", also Quicksort/Topsort aus, wobei Topsort stets ausführbar ist, auch wenn Quicksort versagt (Topsort(d.h.topologische Sortierung)!=Quicksort(d.h.Sortieren), eigentlich trivial), Sledge mehr vom Ergebnis, das stets eine Totalordnung ist (topologische Sortierung=Totalordnung(d.h.Sortierung n. Def.), auch trivial).

Für mich ist Sortieren eine fast alltägliche Tätigkeit, Sortierung eher ein gestelztes Kunstwort. --Hubi 14:44, 22. Jul 2004 (CEST)

Der Kernpunkt bei mir war ein anderer. Insbesondere ist m.E tolopogische Sortierung ungleich Totalordnung (und allgemein eine Sortierung keine Ordnung). Vielmehr geht es dabei um die Relation zweier Ordnungen, wobei eine davon eine Art "innere Ordnung" ist. Insbesondere kann eine Menge niemals sortiert sein, weil eine Menge keine "innere Ordnung" hat: Die Menge { 1, 2 } ist identisch mit der Menge { 2, 1 }. Allerdings kann eine Menge durchaus geordnet sein, wenn auf ihren Elementen eine Ordnung definiert ist.

Vielleicht ist die folgende Definition treffend:

Sei $M$ eine Menge, $R$ eine Relation auf dieser Menge, $N$ eine Menge, die gleichmächtig mit $M$ ist, und $T$ eine Totalordnung auf $N$. Eine Sortierung ist dann eine Bijektion $s:N\mapsto M$, so dass für die durch s induzierte Ordnung $T_{s}=\{(a,b)\in M\times M:(s^{-1}(a),s^{-1}(b))\in T\}$ eine Obermenge von $R$ ist.

Beim Anziehen wäre $N$ eine Untermenge der Zeitpunkte mit der Totalordnung "früher als", und $s$ würde angeben, welches Kleidungsstück zu diesem Zeitpunkt angezogen wurde. Und im Computer wäre $N$ z.B. die Indexmenge, und $s$ wäre die Funktion, die angibt, welches Element an welchem Platz sitzt. --Ce 15:22, 22. Jul 2004 (CEST)

Ja, und wenn es eine echte Obermenge ist, ist die Sortierung auf jeden Fall eine topologische, ist R mit T äquivalent, eine gewöhnliche oder eine topologische, ganz nach Belieben (wenn ich's richtig verstanden habe). Damit bin ich aber wieder bei Wenn alle Kriterien vorher feststehen, ist die topologische mit der gewöhnlichen Sortierung identisch, sonst nicht. So in etwa steht's im Artikel. --Hubi 16:04, 22. Jul 2004 (CEST)

Ok, die Definition von Ce2 sieht ja schon der Definition von Ottmann/Widmayer mit ihrer Abbildung ord recht ähnlich. Ich versuche mich auch noch mal an einer gleichwertigen Definition, die sich an der schon mehrfach genannten Vorstellung mit dem Relationenpaar orientiert:

Sei $M$ eine Menge und $R,T\subseteq M\times M$ Relationen auf $M$.

Das Paar $(R,T)$ heißt genau dann eine topologische Sortierung von $M$, wenn $R\subseteq T$ und $T$ eine strenge Totalordnung ist.

Lemma/Def: Ist $R$ eine strenge Totalordnung, so gibt es nur eine einzige topologische Sortierung $(R,T)$ von $M$ (nämlich $T=R$). Diese topologische Sortierung nennt man (gewöhnliche) Sortierung.

Lemma: Jede Sortierung ist eine topologische Sortierung.

Diese Definition ist vielleicht einfacher, weil man keine zweite Menge einführt, mit der man $M$ "abzählen" muss. --Sledge 17:07, 22. Jul 2004 (CEST)

Hinweis: Das folgende ist eine Antwort an Hubi; der Beitrag von Sledge war hier ein Bearbeitungskonflikt.

Du hast es nicht richtig verstanden. Mein Kernpunkt war: Eine Ordnung ist nie eine Sortierung, und eine Sortierung ist nie eine Ordnung.

In meinem Definitionsversuch ist $s$ die Sortierung, und nicht $T_{s}$. Also nocheinmal die Kurzfassung obiger Definition (mit Verwendung von "$<$" für die Totalordnung):

Eine Sortierung ist eine Bijektion $s$ einer totalgeordneten Menge N auf eine Menge M mit vorgegebener Relation R, so dass für alle Paare $(a,b)$ mit $s(a)Rs(b)$ gilt: $a<b$.

Übrigens ist Deine Aussage auch falsch, denn schon bei einer strengen schwachen Ordnung funktionieren Algorithmen wie Quicksort wunderbar. Insofern kann $R$ durchaus eine Teilmenge von $T_{s}$ sein, ohne dass man zu einem topologischen Sortieralgorithmus greifen müsste.

Die erwähnte Aussage ist vom Prinzip her richtig (ich habe sie bis jetzt auch nicht angezweifelt), aber bei genauerer Betrachtung stimmt sie nicht ganz, und zwar genau deshalb, weil die traditionellen Sortieralgorithmen eben nicht eine Totalordnung, sondern nur eine strenge schwache Ordnung voraussetzen. Deshalb gibt es auch die Unterscheidung zwischen stabilen und instabilen Sortieralgorithmen: die stabilen Algorithmen lassen die bezüglich der Ordnung äquivalenten Elemente in derselben Reihenfolge (das bedeutet insbesondere auch, dass vorher eine Reihenfolge festgelegt gewesen sein muss; es muss also schon vor dem Sortieren eine Bijektion $s':N\mapsto M$ gegeben haben, die allerdings nicht unbedingt eine Sortierung war), die instabilen Sortieralgorithmen machen diese Zusicherung nicht. Beispiel: Sortieren wir nach dem ersten Element von Zahlenpaaren, und ist die ursprüngliche Liste ((2,2) (2,1) (1,2)), dann liefert ein stabiler Sortieralgorithmus wie Mergesort immer die Liste ((1,2) (2,2) (2,1)), während ein instabiler Sortieralgorithmus wie Quicksort genausogut ((1,1) (2,1) (2,2)) zurückliefern kann. Hier sind die beiden Paare (2,1) und (2,2) bezüglich der Sortierordnung (erstes Element von a < erstes Element von b) äquivalent (beide haben 2 als erstes Element). --Ce 17:14, 22. Jul 2004 (CEST)

Gerade gesehen: Wenn ich das richtig verstehe, dann ist meine Abbildung s genau das ord von Ottmann/Widmayer, außer dass ich eine beliebige totalgeordnete Menge N zulasse, während Ottmann/Widmayer hierfür die Menge der ganzen Zahlen von 1 bis #(M) nehmen (was automatisch eine Beschränkung auf endliche M impliziert). Oder habe ich da einen subtilen Unterschied zwischen den Definitionen übersehen? --Ce 17:20, 22. Jul 2004 (CEST)

Also ich sehe da keinen großen Unterschied, außer das sich Ottmann/Widmayer auf eine endliche Trägermenge beschränken, was im Rahmen einer Definition meines Erachtens überflüssig ist. Dennoch halte ich die Definition mit der Abbildung für unnötig kompliziert. Letztlich interessieren wir uns doch für die durch ord bzw. s von der total geordneten Indexmenge auf die zu sortierende Menge transportierte Ordnung. Das finden einer entsprechenden Abbildung ord oder s ist auch nicht viel einfacher, als wenn ich gleich M=N und s=id annehme und eine strenge Totalordnung auf M suche.

Letztlich brauchen wir uns aber auch nicht auf eine bestimmte Definition festlegen, ich habe schon häufig Kombinationen von Satz und Definition gesehen, wo einfach die Äquivalenz von bestimmten Aussagen bewiesen wurde, und der Leser damit jede dieser Aussagen als Definition für seinen Begriff heranziehen konnte. --Sledge 20:32, 22. Jul 2004 (CEST)

Dann ist für Dich also das Sortieren bei Vorliegen einer Totalordnung eine Nulloperation (da man ja dann nicht lange nach einer Totalordnung suchen muss)? Schon seltsam, dass dann alle mir bekannten Algorithmen dafür im Durchschnitt mindestens O(n log n) brauchen :-)

Schau Dir nochmal meine Beispiele an. Die Funktion sagt Dir, welches Element auf welchem Platz sitzt. Es ist der Unterschied zwischen der totalgeordneten, aber unsortierten Liste (1 4 2 16 8) und der totalgeordneten und sortierten Liste (1 2 4 8 16), der interessiert. Die Ordnung existiert schon vor der Sortierung, und operiert auf der Menge, die man gleichwertig als {1, 2, 4, 8, 16}, {1, 4, 2, 16, 8} oder {2^n: n in Z geschnitten [0,4]} schreiben kann. Eine Reihenfolge ist hier nicht vorhanden.

Oder anders ausgedrückt: Die strenge Totalordnung ist die Menge T = {(1,2), (1,4), (1,8), (1,16), (2,4), (2,8), (2,16), (4,8), (4,16), (8,16)}, während die Sortierung durch die Menge S = {(1,1), (2,2), (3,4), (4,8), (5,16)} gegeben ist. T besagt: "1 ist kleiner als 2, 1 ist kleiner als 4, ..., 8 ist kleiner als 16". Das ist eine Ordnung. S besagt: "An Platz 1 steht die 1, an Platz 2 steht die 2, an Platz 3 steht die 4, an Platz 4 steht die 8, an Platz 5 steht die 16". Das ist eine Sortierung. --Ce 22:05, 22. Jul 2004 (CEST)

"zu Nulloperation": Hehe, ich habe ja nicht behauptet, dass es durch setzen von s=id schneller geht. Ich benutze halt nur meine Menge M selbst als Indexmenge. Anstatt eine Funktion zu konstruieren, welche eine bekannte totale Ordnung von dieser Indexmenge auf meine Menge M transportiert, konstruiere ich gleich meine totale Ordnung auf M. In beiden Fällen ist natürlich etwas zu tun.

"zu den Beispielen": Ich denke schon, dass ich verstanden habe, was die "Sortierfunktion" tut. Ich finde es halt nur nicht so interessant ;-)

Ich sehe schon ein, dass bei einer Fokussierung auf den Algorithmus auch die Sortierfunktion im Mittelpunkt des Interesses steht. Persönlich halte ich den Algorithmus aber nur für ein Mittel zum Zweck, und der ist es, eine strenge Totalordnung zu finden. Es ist ja gerade nicht so, dass eine totale Ordnung auf M schon in jedem Fall vor der Sortierung bekannt ist. Bei hinreichend allgemeinen Vorbedingungen haben wir ja schon festgestellt, dass es auch mehrere strenge Totalordnungen auf M geben kann, welche diese Vorbedingungen erfüllen. Bei ungeeigneten Vorbedingungen gibt es gar keine.

Wie ich schon angedeutet habe, finde ich es aber eigentlich auch nicht so wichtig welche der beiden hier vorgestellten Definitionen wir nun benutzen, da sie in dieser Form das gleiche bedeuten. Es ist wohl mehr eine Frage der Betonung als des Inhalts. Allerdings sollten sich die Definitionen eignen um unseren Hauptsatz über topologische Sortierungen und azyklische Digraphen zu formulieren. Soweit ich das einschätzen kann, tun das sowohl die beiden neuen Definitionen als auch die alte, welche noch im Artikel steht. Letztere passte halt nur nicht um den Satz "Jede Sortierung ist eine topologische Sortierung" zu formulieren. Ob hierzu die Definition mit der Abbildung geeignet ist, muss ich mir noch mal überlegen. --Sledge 00:28, 23. Jul 2004 (CEST)

Ordnung und Sortierung habe ich nicht gleichgesetzt. Mein Fehler war wohl, dass ich für eine gewöhnliche Sortierung eine Totalordnung vorrausgesetzt habe (strenge schwache Ordnung genügt). Für topologische Sortierung muss man eine strenge Ordnung vorraussetzen. Eine gewöhnliche (instabile) Sortierung kann auch mit einer reflexiven Totalordnung ausgeführt werden. In der ersten Definition von Sortierung ist ja auch keine "strenge" Totalordnung T vorrausgesetzt, daher braucht T_s und die Teilmenge R auch nicht streng sein. Daher ist weder jede gewöhnliche Sortierung (auch) eine topologische noch jede topologische Sortierung eine gewöhnliche Sortierung. --Hubi 08:03, 23. Jul 2004 (CEST)

Entschuldigung, aber ich habe im Moment wirklich Probleme der Diskussion zu folgen. Wieso muss man für eine topologische Sortierung jetzt eine strenge Ordnung vorraussetzen? Dank unserem Hauptsatz wissen wir doch schon, das es aussreicht eine beliebige Relation zu haben, deren Digraph azyklisch ist. --Sledge 10:14, 23. Jul 2004 (CEST)

Wenn ich die Ursache für eventuelle Verwirrungen sein sollte, bitte ich, dies zu entschuldigen. Für mich ist Ce's Definition die allgemeine Definition von Sortierung, die von Sledge und im Artikel die für topologische Sortierung. Beide halte ich für korrekt, obwohl mir die Definition von Sortierung als Abbildung besser gefällt. Erstere setzt keine strenge Totalordnung vorraus, letztere schon. (Ich bin aber in der Sortiertheorie nicht so drin, möglicherweise kann man die strenge Ordnung auch einfach folgern?). Streng Azyklisch impliziert azyklisch streng, denn Graph 5 im Artikel repräsentiert eine reflexive Beziehung, was ja durch streng ausgeschlossen wird. Für mich stellt sich's jetzt so dar:

1. Setzen wir in der Sortierung für T noch streng vorraus, erhalten wir eine Def. für die topologische Sortierung. Dann kann T_s auch nur noch streng sein und R als Teilmenge davon ebenfalls.
2. Hat R schon bestimmte Eigenschaften, also strenge schwache Ordnung (<), nicht streng, aber lineare Odnung (<=), so handelt es sich um eine gewöhnliche Sortierung (?).

Damit schränkt der Begriff topologisch als auch der Begriff gewöhnlich die allgemeine Definiton von Sortierung ein. - Alles von einem Laien (mir) --Hubi 11:44, 24. Jul 2004 (CEST)

Ach so, Du meintest die strenge Totalordnung von Ce's Indexmenge, die man voraussetzen muss? Dann habe ich das glaube ich verstanden. Bevor wir jetzt weitere Aussagen hierzu untersuchen, bin ich dafür, dass wir uns auf eine gemeinsame Definition einigen. Ich habe bisher drei Definitionen gezählt, die meines Erachtens alle einen Sinn ergeben, aber unterschiedliche Akzente setzen. Nun möchte ich das folgende Vorgehen vorschlagen:

1. Ich stelle die verschiedenen Definitionen noch einmal vor, und gebe ihnen einen Namen.
2. Zu den verschiedenen Definitionen werden pro und contra Argumente gesammelt.
3. Die Argumente werden diskutiert und eine Definition als "Hauptdefinition" ausgewählt (möglichst als Konsens).
4. Die Hauptdefinition wird in den Artikel übernommen.
5. Die übrigen Definitionen können als Satz oder alternative Definition an einer untergeordneten Stelle des Artikels erwähnt werden.

Die pro und contra Einträge sind nicht im Sinne einer Abstimmung zu werten. Jeder kann beliebige viele pro und contra Argumente beitragen. Da die Argumente unterschiedlich schwer wiegen können, sagt auch die Anzahl der Argumente nicht viel über die Qualität einer Definition aus.

Ich denke, dass dieses Vorgehen im Sinne von Ce ist, der diesen Abschnitt erzeugt hat. --Sledge 13:36, 24. Jul 2004 (CEST)

Noch einmal zur normalen Sortierung: Die Algorithmen der STL setzen alle eine strenge (alsi irreflexive) Ordnung voraus. Das ist für totale Ordnungen irrelevant (wegen der Trichotomie), aber für allgemeine strenge schwache Ordnungen nicht (wenn $a=b$, dann gilt sowohl $a\leq b$ als auch $b\leq a$, für äquivalente $a,b$ mit $a\neq b$ hingegen gilt weder $a\leq b$ noch $b\leq a$). --Ce 22:27, 25. Jul 2004 (CEST)

---

Alternative Definitionen für eine topologische Sortierung (in der Reihenfolge wie sie in die Diskussion eingeführt wurden):

Relationenerweiterung

Sei $M$ eine Menge und $R\subseteq M\times M$. Eine Menge $T\subseteq M\times M$ heißt genau dann eine topologische Sortierung von $M$ für $R$, wenn $T$ eine strenge Totalordnung auf $M$ ist und $R\subseteq T$ gilt.

Hinweis: Das ist die Definition, wie sie aktuell im Artikel steht.

Sortierfunktion

Sei $M$ eine Menge und $R\subseteq M\times M$. Sei $I$ eine Menge und $S$ eine strenge Totalordnung auf $I$.

Eine Abbildung $t:I\to M$ heißt genau dann eine topologische Sortierung von $M$ für $R$ bzgl. der mit $S$ geordneten Indexmenge $I$, wenn jede der folgenden Bedingungen gilt:

• $t$ ist eine Bijektion
• $\forall a,b\in M:(a,b)\in R\Rightarrow (t^{-1}(a),t^{-1}(b))\in S$

Hinweis: Das ist die etwas umformulierte Definition von Ce bzw. die verallgemeinerte Definition von Ottmann/Widmayer. Das $I$ und $M$ gleich mächtig sind, habe ich weggelassen, da das schon aus $t$ ist Bijektion folgt.

Relationenpaar

Sei $M$ eine Menge und $R,T\subseteq M\times M$ Relationen auf $M$.

Das Paar $(R,T)$ heißt genau dann eine topologische Sortierung von $M$, wenn $R\subseteq T$ und $T$ eine strenge Totalordnung ist.

Hinweis: Das ist die, sich an dem Relationenpaar (Vorher/Nachher) orientierende Definition.

---

Pro und Contra Argumente:

Pro: Relationenerweiterung

1. Einfache, verallgemeinerte Definition mit wenigen mathematischen Objekten. --Sledge 13:45, 24. Jul 2004 (CEST)

Contra: Relationenerweiterung

1. Wenn die in Form von Paaren vorgegebene Relation bereits eine Totalordnung darstellt, dann wäre die Operation mathematisch eine Nulloperation. Das entspricht aber nicht der Realität des Algorithmus, der in diesem Fall maximale Rechenzeit benötigt. --Ce 22:12, 25. Jul 2004 (CEST)

Pro: Sortierfunktion

1. Analogie: "Sortierfunktion" und "Sortieralgorithmus" --Sledge 13:48, 24. Jul 2004 (CEST)
2. Ist die am häufigsten zitierte Definition. --Sledge 17:39, 6. Aug 2004 (CEST)

Contra: Sortierfunktion

1. Der Bezug auf eine Indexmenge erschwert die Formulierung von Beweisen und Sätzen. So kann man z.B. nicht mehr uneingeschrängt behaupten, dass durch eine strenge Totalordnung R die topologische Sortierung t schon eindeutig festgelegt ist. Vielmehr gilt das nur für eine ganz bestimmte Indexmenge und eine ganz bestimmte strenge Totalordnung S auf dieser Indexmenge. --Sledge 14:43, 27. Jul 2004 (CEST)

Pro: Relationenpaar

1. Fokussierung auf Startkritierium und gewünschtes Ergebnis (Vorher/Nachher). --Sledge 13:52, 24. Jul 2004 (CEST)

---

Diskussion der Argumente

Fragen und Diskussionen zu den oben aufgezählten Argumenten bitte hier stellen/führen:

Ich habe mal die Argumente oben durchnummeriert, damit man sie hier besser zitieren kann. --Sledge 00:26, 26. Jul 2004 (CEST)

Das erste Contra-Argument zur Relationenerweiterung habe ich nicht verstanden. Von einer Operation ist in der Definition doch gar nicht die Rede. Die Definition beschreibt lediglich, wann man eine Menge topologische Sortierung nennen kann. Wie man so eine Menge konstruiert, wie lange das dauert und ob und wann es so eine Menge überhaupt gibt, ist nicht Gegenstand der Definition.

Ist vielleicht genau dieser fehlende Bezug zum Konstruktionsprozess das eigentliche Contra Argument? --Sledge 00:26, 26. Jul 2004 (CEST)

Was ich meinte, ist die Tatsache, dass nach dieser Definition bereits die ursprünglich angegebene Relation die topologische Sortierung wäre. Das Finden der topologischen Sortierung müsste also prinzipiell in Nullzeit implementierbar sein (die Implementierung einer Nulloperation, die mehr als Nullzeit beansprucht, ist einfach ineffizient). Das ist aber offensichtlich nicht der Fall. --Ce 16:54, 27. Jul 2004 (CEST)

Naja, das Finden der topologischen Sortierung ist tatsächlich in Nullzeit möglich, wenn ein Algorithmus festgestellt hat, dass die Startrelation schon eine strenge Totalordnung ist. Er braucht dann nämlich einfach nur abzubrechen, und die Startrelation als Ergebnis zu präsentieren. Das Eigentliche Problem dürfte sein, dass der Algorithmus nicht in Nullzeit entscheiden kann, ob die Startrelation schon eine strenge Totalordnung ist. Vermutlich ist es auch nicht sinnvoll, Zeit für die Überprüfung jeder Startrelation aufzuwenden, nur um sich in diesem einen Spezialfall das Suchen zu ersparen. --Sledge 19:22, 27. Jul 2004 (CEST)

Zum Argument 1 contra Sortierfunktion: Hier hast Du einen guten Punkt. Bei Ottmann/Widmayer existiert dieses Problem nicht, weil Indexmenge und Ordnung explizit angegeben sind; allerdings schränkt das die Allgemeinheit ein. Man kann sich natürlich aus der Affäre ziehen, indem man Äquivalenzklassen von Indexmengen betrachtet, aber das wird dann unnötig kompliziert. Wenn man aber betrachtet, worin all die Indexmengen äquivalent sein müssen, dann ist dies gerade die induzierte Totalordnung auf der sortierten Menge. Insofern tendiere ich jetzt eher zur Alternative 3, ohne mich hierin aber schon endgültig festlegen zu wollen. --Ce 17:09, 27. Jul 2004 (CEST)

Ja, in der Tat scheint die Definition über das Relationenpaar zur Zeit am wenigsten Probleme zu bereiten. Zudem ist sie eher noch kürzer und pregnanter als die erste. --Sledge 19:26, 27. Jul 2004 (CEST)

Ok, jetzt habe ich das eigentlich naheliegenste getan: Mal geschaut, wie denn sonst so die topologische Sortierung definiert wird: Anscheinend immer über eine Funktion ord, die allerdings nicht von der Indexmenge zur sortierten Menge geht, sondern gerade umgekehrt, siehe z.B. [1], [2], [3], [4] --Ce 17:26, 6. Aug 2004 (CEST)

Ich habe diesen Hinweis mal als zweites Argument "Pro: Sortierfunktion" aufgenommen und gebe zu, dass es natürlich schwer wiegt. Letztlich ist Wikipedia ja eine Enzyklopädie und soll den aktuellen Wissensstand darstellen. Ziel des Artikels ist es nicht, einen Forschungsbeitrag zu leisten oder zu zeigen wie man es besser macht. Wenn ich die Idee einer Enzyklopädie richtig verstanden habe, ist es lediglich das Ziel zu beschreiben, wie die aktuelle Lehrmeinung zu dem Thema aussieht - und wenn da halt diese Sortierfunktion propagiert wird, so kann das in dem Artikel wohl nicht ignoriert werden. Möglicherweise muss, was die Kardinalität der Sortiermenge angeht auch "zurückgerudert" werden. Quellen für eine Erweiterung der Theorie auf unendliche Mengen habe ich jedenfalls noch nicht gesehen. Außerdem bin ich bin mir nicht mehr so sicher, ob die Definitionen für unendliche Mengen wirklich alle äquivalent sind. --Sledge 18:03, 6. Aug 2004 (CEST)

Zusammenhang mit Netzplantechnik

Wenn ich das richtig verstehe ist eine reale Anwendung die Netzplantechnik. Dies sollte im Artikel als Anwednungsgebier erwähnt werden. -- tsor 11:44, 18. Jul 2004 (CEST)

Ja, da hast du recht. Die einleitenden Sätze benutzen dieses Beispiel ja bereits. --Berni 17:29, 18. Jul 2004 (CEST)

Mathematische Beschreibung des Problems

In den Absätzen Die zu sortierende Menge und Die topologisch sortierte Menge wird folgende Behauptung aufgestellt bzw. benutzt:

"Die zu sortierenden Objekte müssen bezüglich der Beziehung teilweise angeordnet werden können, damit sie topologisch sortierbar sind."

Ich vermute, dass diese Behauptung falsch ist. Zumindest ist sie aber nicht unmittelbar einsichtig oder begründet. Ich schlage vor, die Absätze erst einmal in die Diskussion zu verschieben und zu überprüfen. Da der Artikel schon das Prädikat "Exzellent" trägt, möchte ich die zweifelhafte Aussage nicht so lange ungeprüft im Artikel stehen lassen. Daher werden ich die Absätze heute Abend verschieben, sofern bis dahin keine gegenteiligen Wortmeldungen vorliegen. --Sledge 15:10, 30. Jul 2004 (CEST)

Unter der Annahme, dass "teilweise angeordnet" bedeutet, dass es eine strenge Teilordnung gibt, ist der Satz richtig. Wie weiter unten erklärt, erhält man die Teilordnung durch transitiven Abschluß der übergebenen Relation; der transitive Abschluß ergibt dann und nur dann eine strenge Teilordnung, wenn die anfangs gegebene Relation keine Zyklen enthält. --Ce 16:44, 30. Jul 2004 (CEST)

Ohje, da hast Du recht. Ich habe den ersten Satz, irrtümlicher Weise, wohl als Voraussetzung gelesen "Die ... Objekte müssen ... teilweise angeordnet sein, ..." sozusagen. Mit der naheliegenden Interpretation "teilweise angeordnet" = "strenge Halbordnung" ist der Satz wohl zweifellos richtig. Nimm' es mir bitte nicht übel, wenn ich jetzt von einem Extrem ins andere gerate, aber ich würde sogar sagen etwas zu zweifellos. Eine Aussage jeder der vorgestellten Definitionen ist ja gerade:

"Die zu sortierenden Objekte müssen bezüglich der Beziehung in einer strengen Totalordnung angeordnet werden können, damit sie topologisch sortierbar sind."

Damit ist der Satz ja lediglich eine schwächere Version der Definition (unabhängig davon welcher Vorschlag zum Zuge kommt).

Ich hoffe, dass mir diese Kritik nicht als übertrieben kleinlich ausgelegt wird, aber wir reden ja nun über einen "exzellenten" Artikel, da sollte man schon jedes Wort auf die Waagschale legen können.

Gerne würde ich meiner Kritik noch eine konstruktive Note geben, aber ich weiss noch nicht so recht, wie man das umformulieren kann. Vielleicht könnte man in den betroffenen Absätzen, in Vorbereitung auf die Definition, einfach Eigenschaften des vorliegenden Beispiels untersuchen und auf Verallgemeinerungen verzichten. --Sledge 22:48, 30. Jul 2004 (CEST)

Für die Verwendung des Algorithmus als Zyklendetektor ist es schon wichtig, dass ein Fehlschlagen des Algorithmus zwingend das Vorliegen eines Zyklus bedingt. Wenn es Fälle gäbe, in denen die Relation zu einer Teilordnung, aber nicht zu einer Totalordnung erweitert werden kann, dann könnte man aus dem Fehlschlagen des Algorithmus (der ja eine Totalordnung sucht) nicht schließen, dass Zyklen vorhanden sind (weil aus der Unmöglichkeit einer Totalordnung nicht auf die Unmöglichkeit einer Teilordnung geschlossen werden könnte).

Dabei fällt mir auf: Gilt die Aussage, dass jede Teilordnung zu einer Totalordnung erweitert werden kann, eigentlich auch für unendliche Mengen? --Ce 17:15, 6. Aug 2004 (CEST)

Die Antwort auf die letzte Frage ist vermutlich "Ja". Für eine entsprechende Formulierung mit "streng" genügt es z.Z., dass für jede strenge Halbordnung H auf M, die transitive Hülle $T:=\cap \{R\subseteq M\times M|H\subseteq R\wedge R\,\operatorname {transitiv} \}$ eine strenge Totalordnung ist, welche H enthält. Dazu sage ich mal vorsichtig: "Das sieht mir beweisbar aus."

Vielleicht ist das ein Thema für meinen Erzeugnis-Artikel. Ich lass mir das nochmal durch den Kopf gehen. Jedenfalls vielen Dank für die Anregung. --Sledge 00:14, 7. Aug 2004 (CEST)

Moment mal: Die Halbordnung selbst ist ja auch schon transitiv (das ist eines ihrer Axiome!), und damit ist die T=H (da H gerade so ein R ist, jedes solche R aber H als Teilmenge hat, gibt die Schnittmenge gerade H). (Ich nehme an, dass Halbordnung=Teilordnung; wenn nicht, bitte ich um Aufklärung!) --Ce 18:46, 7. Aug 2004 (CEST)

Tja, da habe ich mich wohl vergallopiert. Wie gut, dass ich meine Vermutung halbwegs vorsichtig formuliert habe :-/

Ob eine "trichotomische Hülle" Sinn macht weis ich nicht, kann man eine Eigenschaft mit einer Disjuktion denn im Sinne einer Hülle "verkleinern"? Eine Implikation wie bei der Transitivität kann ich doch auch als Disjunktion darstellen. Wie gesagt lasse ich mich darüber vielleicht noch an anderer Stelle aus. Das ist vermutlich besser als wenn ich mich hier zur nächsten wagemutigen Behauptung hinreißen lasse. --Sledge 22:59, 7. Aug 2004 (CEST)

Das Problem ist, dass hier keine Eindeutigkeit herrscht. Es gibt viele Möglichkeiten, eine Halbordnung "trichotomisch zu ergänzen", wobei einige davon keine Ordnungsrelation mehr darstellen.

Beispiel: Sei $M=\{a,b,c,d\}$ und $H=\{(a,b),(a,c),(a,d),(c,d)\}$. Dann ist eine mögliche erweiterte Relation mit Trichotomie $R'=\{(a,b),(a,c),(a,d),(b,c),(c,d),(d,b)\}$, das ist aber definitiv keine Ordnung (die letzten drei Elemente bilden einen Zyklus).

Die Frage ist, ob man eine strenge Halbordnung so zu einer Trichotomie erweitern kann, dass das Resultat immer noch eine Halbordnung (und somit eine Totalordnung) ist. Für endliche Mengen ist das immer möglich, aber nicht eindeutig. Für unendliche Mengen ist das eben die Frage.

Noch ein Punkt: Der Schnitt zweier verschiedener Trichotomien ist niemals selbst eine Trichotomie. --Ce 11:00, 9. Aug 2004 (CEST)

Zeitverhältnis/Komplexität

Der folgende Absatz ist zwar sehr anschaulich erklärt, aber sachlich falsch:

"Die Komplexität des Algorithmus beschreibt das zeitliche Verhalten bei großen Datenmengen, genauer das Verhältnis der Ausführungsdauern bei Vergrößerung der Eingabedaten, zum Beispiel von 10.000 auf 100.000 Einträge (Faktor 10). Beträgt das Zeitverhältnis etwa 10, so ist die Zeitabhängigkeit linear (O(n)), bei etwa 100 dagegen quadratisch (O(n^2)). Die Ausführungsdauer kann auch unabhängig von der Datenmenge, also konstant sein (O(1))."

Es ist nicht möglich, die Komplexität mit zwei "Messwerten" zu approximieren. Insbesondere geht der Abschitt nicht darauf ein, dass die Funktionen aus O(n) bzw. O(n^2) mitunter recht große konstante Terme haben können. Ich würde es gerne korrigieren, aber weiß leider nicht, wie ich das allgemeinverständlich ausdrücken kann, ohne groß in Formalien abzuschweifen.--82.83.218.107 13:59, 21. Jul 2005 (CEST)

Ich habe den Absatz mal versucht zu korrigieren. Meiner Meinung nach sind jetzt keine sachlich falschen Aussagen mehr vorhanden. Ein paar Dinge sind noch etwas durcheinander, weil ich die viele Arbeit desjenigen, der den Absatz ursprünglich verfasst hatte nicht zerstören wollte. Die grundlegend falschen Informationen sind nun aber glaube ich entfernt. Wenn sich jemand dazu berufen fühlt noch mehr klarheit reinzubringen ... -- Vvs 23:56, 27. Jul 2006 (CEST)

Ich finde die Erklärung der O-Notation hier fehl am Platz. Mir ging es so, dass ich erst mal zu dem Abschnitt runtergescrollt hatte, wo ziemlich bald was von O(N²) steht, was ich bei einem flüchtigen Lesen als die Komplexität des Algorithmus angenommen hatte. Erst auf den zweiten Blick wurde mir klar, dass das nur die einleitende Definition der Notation handelt. Da würde ich diese anschauliche Beschreibung doch lieber im Artikel Landau-Symbole sehen, und hier einen Verweis da hin. Ich sehe auch ein Problem darin, die Unterscheidung zwischen dünnen und dichten Graphen synonym zu verwenden mit Agerage Case und Worst Case. Es gibt bestimmt genug Szenarien, wo dichte Graphen der Average Case sind. Werde das später noch etwas umbauen, wenn ich dazu komme. -- Martin von Gagern 09:12, 2. Aug 2006 (CEST)

Ja. Du hast Recht. Ich hab Worst und Average Case benutzt, weil ich "normale Probleme" und "es kann aber auch vorkommen" noch schlechter fand und mir nichts besseres eingefallen ist. Ich denke auch der komplette Absatz sollte eigentlich radikal zusammengestrichen werden. So ist er m.E. viel zu lang und enthält zu viel BlaBla, wenn einem die Landau-Symbole schon klar sind. Vvs 01:15, 3. Aug 2006 (CEST) --

Nach reichlich zwei Jahren sind die Fehler nun immer noch drin: "Average case" wird falsch verwendet, Zeitkomplexität nicht korrekt erklärt (ist auch hier fehl am Platz s. Martin von Gagern). Auch der unsignierte Kommentar am Ende ist berechtigt, sowie die beiden (bzgl. Tiefensuche) und von Norro! Ergo: Dies IST definitiv kein exzellenter Artikel. Mein Eindruck: Ein einfaches Problem wird viel Aufwand verkompliziert dargestellt. Was haltet Ihr denn von dieser Darstellung? (Sorry, ich habe keine Erfahrung als Wikipedia-Autor - daher nur der Kommentar hier ...) --91.6.4.34 22:35, 6. Jan. 2009 (CET)

Tiefensuche

Warum ist kein Hinweis auf die Tiefensuche/DFS enthalten? Jedes bessere Buch verweist bei Topologischen Sortieren auf DFS. --88.72.226.101 10:45, 12. Sep 2006 (CEST)

Weiteres Beispiel für Topologische Sortierung

Ich habe ein weiteres Beispiel für eine topologische Sortierung. Und zwar die Ermittlung der Einfüge-Reihenfolge bei Tabellen mit referentieller Integrität. Das Besondere an diesem Beispiel ist, dass die Lösung mit einer nicht imperativen Sprache ermittelt wird, nämlich mit der Abfragensprache SQL. Es ist ein Beispiel aus der Praxis, dass man in vielen Software-Projekten lösen muss.

Da ich einen sehr großen Respekt vor einem exzellenten Artikel habe, will ich nicht gleich darin Erweiterungen aufnehmen. Statt dessen habe ich mein Beispiel erst mal ganz bescheiden unter 'Siehe auch' eingetragen. Ich will es dem Autor dieses Artikels überlassen, es bei diesem Link zu belassen oder meinen Beitrag als 4. Beispiel in den Artikel aufzunehmen. 10:57 23. Feb. 2007

Pseudocode

Hi. Ich bin soeben auf den Artikel gestoßen und bin sehr verwundert, keinen Pseudocode zu finden. Meines Erachtens muss ein Artikel (auf jeden Fall ein exzellenter) zu einem Algorithmus bzw. ein Artikel, der sich maßgeblich um einen Algorithmus dreht, diesen als Pseudocode darstellen. Ein Beispiel in Perl ist evtl. auch hilfreich, kann aber Pseudocode hinsichtlich Lesbarkeit und Nutzen nicht ersetzen. Kann das einer von euch Profis erledigen? :) Gruß, --norro 10:50, 16. Feb. 2008 (CET)

Zeitverhalten (Komplexität)

Dieser Abschnitt ist sehr problematisch. Der skizzierte Algorithmus kann laut dem Standard-Lehrbuch von Cormen/Leiserson/Rivest, exercise 23.4-5 in O(n+m) worst-case implementiert werden. Andere Teile des Abschnitts leiden unter einer verkümmerten Kenntnis von Datenstrukturen: für die Suche nach vorgängerlosen Elementen in konstanter Zeit braucht man z.B. eine Hashtabelle oder ein Array, keine Liste. Schliesslich sind die Sätze mit "im Schnitt" fragwürdig: ein gegebenes Element hat eine konstante Anzahl von Beziehungen, Punkt. Die Behauptung "und verringert die Vorgängerzahl von im Schnitt m/n Nachfolgern" ist nicht belegbar, und es fehlt die worst-case-Angabe an dieser Stelle.

Dass der worst case bei der Suche mittels einer Hashtabelle in konstanter Zeit (O(1)) bewerkstelligt werden kann, ist mir neu. Meines Erachtens ist der worst case hier immer noch O(n). Damit ist die Kritik gegenstandslos. Liste und (unsortiertes) Array unterscheiden sich nicht grundlegend bei der Suchzeit, ebenfalls O(n). Und wieso hat ein gegebenes Element eine konstante Anzahl von Beziehungen? Die Graphen im Artikel beweisen doch das Gegenteil. Fazit: Reiner Quatsch (muss es leider so hart sagen). -- Hubi 20:41, 1. Sep. 2009 (CEST)

IMO kein Quatsch.

Mir hat man auch beigebracht, dass TOP-Sort in ${\mathcal {O}}(n+m)$ liegt

Beweis:

1  int c=1;
1  for all $v\in V$ // n Stück
2    berechne Eingrad // Jede Kante trägt zu genau einem Eingrad bei, also unagbhängig vom Knoten insgesamt m Betrachtungen
3    if (Eingrad(v) == 0)
4      Speicher v in einer Struktur TMP 
5  while (TMP != $\emptyset$) // Noch mal n-Stück
6    v= TMP.pop()
7    $\Phi (v)$ = c++
8    for all outegdes a // Wie beim Eingrad: wieder m-Stück
9       if( -- Eingrad( a.target() )==0 )
10        TMP.insert( a.target() )
11 if(--c==number of nodes)
11   return $\Phi$
12 else 
13   return "Graph enthält Kreis"

Auch wennich mich jetzt beliebt wie Fußpilz mache, aber ich fürchte, der viele Fleiß mit dem Artikel war in der algorithmischen Betrachtung umsonst, weil einfach nicht optimal. In der Methode wird jeder Knoten und jede Kante zwei mal betrachtet. Korrektheit kann man auch leicht zeigen. --goiken 18:32, 23. Feb. 2010 (CET)

Kandidatur Topologische Sortierung

Der Artikel wurde im Juli 2004 als exzellenter Artikel ausgezeichnet. Hauptkritikpunkt ist, dass hier ein Artikel über einen Algorithmus diesen nicht als Pseudocode zeigt, sondern als Perlscript. Einen Algorithmus als Pseudocode zu hinterlegen ist in der Informatik das Standardmittel und damit für einen Exzellenten Pflicht. Ich habe dies vor ca. anderthalb Jahren auf der Diskussionsseite angemerkt, seitdem keine Reaktion. Die drei Hauptautoren Hubi, Sledge und Ce2 sind inaktiv. Dazu kommt, dass sich der Artikel aus einem Wust an verschieden formatierten, unübersichtlichen Beispielen aufbaut. Fehlende Einzelnachweise und die schlechte Formatierung rechne ich der frühen Auszeichnung aus dem Jahr 2004 zu, einen Algorithmus nicht als Pseudocode zu hinterlegen, macht den Artikel aber im Kern unvollständig und ist hier der Hauptgrund für die Abwahl. Meines Erachtens

•  Lesenswert norro ^wdw 11:24, 30. Aug. 2009 (CEST)

Frage als Uneingeweihter: Wie viel Aufwand wäre es denn, den Algorithmus als Pseudocode darzustellen bzw. das Perlscript entsprechend zu transformieren und in dem Artikel zu ergänzen? Wäre doch - wenn ich dich richtig verstehe - eine sehr gute Erweiterung zum bisherigen Artikel, warum macht es also niemand? Stellt natürlich deine grundsätzliche Kritik nicht in Frage. -- Achim Raschka 11:35, 30. Aug. 2009 (CEST)

Ich glaube, der Aufwand ist durchaus überschaubar. Ich kann es allerdings nicht selbst und mein Hinweis wird seit anderthalb Jahren nicht umgesetzt. Ein Review kommt wegen der drei inaktiven Hauptautoren nicht in Frage. Deshalb hier die Abwahl, weil sich eine Verbesserung nicht abzeichnet. Diese wäre natürlich die bessere Alternative zur Abwahl. Gruß, norro ^wdw 14:26, 30. Aug. 2009 (CEST)

„Ziemlich überschaubar“ ist noch nett ausgedrückt, das ist im Cormen ein Dreizeiler: DFS auf Graphen anwenden um finishing times zu berechnen, wann immer ein Vertex „fertig“ ist, diesen an den Anfang der linearen Ergebnisliste packen, die Liste am Schluß zurückgeben. ${\mathcal {O}}(n^{2})$ worst case ist übrigens schlicht falsch, besagter Algorithmus läuft für DAG $(V,E)$ in $\Theta (|V|+|E|)$. Für Exzellenz würd ich auch durchaus beispielsweise Dinge wie 10.1145/1187436.1210590 drinhaben wollen. Viele Grüße, —mnh·∇· 15:06, 30. Aug. 2009 (CEST)

Wenn es so einfach ist, frage ich mich, warum es nicht bereits jemand gemacht hat. Leider ist Pseudocode nicht exakt definiert (siehe den dortigen Arikel). Ich finde es vermessen, hier zu bemängeln, dass ein Algorithmus nicht in "Pseudocode" dargestellt ist. Und depth first search auf finishing elements anwenden, als Dreizeiler. Das ist ja auf Anhieb für jeden auch superverständlich -- Hubi 20:05, 1. Sep. 2009 (CEST)

Über die derzeitige Qualität des Artikels äußere ich mich hier nicht, aber so wird's garantiert nicht besser. -- Hubi 20:05, 1. Sep. 2009 (CEST)

Büdde, als korrekt bewiesener Pseudocode für statische topologische Sortierung aus'm Cormen (wohl zu kurz für Schöpfungshöhe, auch nicht ganz 1:1):

Topological-Sort(G):

1. call DFS(G) to compute finishing times for the vertices
2. if vertex finished, insert it onto the front of a linked list
3. return the linked list

DFS ist ein üblicher Algorithmus, das Verfahren in diesem Artikel nochmal ausführlich darzustellen fänd ich deplaziert. Viele Grüße, —mnh·∇· 20:42, 1. Sep. 2009 (CEST)

Jetzt auch mal gelesen, statt nur durchgescrollt, ich tu' mir das ja bei Infoartikeln nur selten an. Here's why:

mathematische Beschreibung: Sorry, aber mal ganz böse gefragt: an wen richtet sich der Abschnitt eigentlich? Offenbar nicht an Fachkundige, denen muss nach dem ersten Semester keiner mehr „als DAG darstellbar <=> topologisch sortierbar“ über drei Abschnitte erklären. Anders gefragt: Was nutzt dem mathematisch komplett ungeschulten Leser die mathematische Modellierung? Viel Text um Grundlagen, zum Beispiel ist auch der gesamte Exkurs um „x R y“ vs „x < y“ einfach überflüssig.

Algorithmus+Laufzeit: Meh. Sehr meh. Keine Lust, das Gebastel genauer zu analysieren, es wirkt vage wie ein ineffizientes DFS. Antik. Geht schneller und eleganter (s. Cormen 2001), damit ist das auch der Laufzeit-Abschnitt unbrauchbar. (Zur Verdeutlichung |V| := 1000, |E| := 1500. |V|^2 = 1.000.000, |V|+|E| = 2500 worst case. Oops.)

Perlscript: überflüssig.

Beispiele: tsort überflüssig, unixoides Werkzeug das so sortieren kann, aber kein eigentliches Beispiel für einen Einsatzzweck.

Fehlend: DTO-Lösungen, siehe [5] (gleiche wie oben) und die Paper zu den anderen Algos, auch [6] (oder [7]) und [8], sowie Spezialvarianten [9], [10], eventuell auch interessant (nicht gelesen, mir beim Googeln aber gerade vor die Füße gehüpft): [11].

Fazit: Brummli. —mnh·∇· 05:47, 31. Aug. 2009 (CEST)

Das Programm ist doch völlig überflüssig, egal in welcher Sprache. --Pjacobi 22:11, 6. Sep. 2009 (CEST)

Vielleicht mag mal jemand in die Einleitung schreiben, dass es sich um einen Begriff aus der Informatik handelt. --Zipferlak 20:37, 8. Sep. 2009 (CEST)

Nochmal ich: Wer kann bitte die Exzellenz-Diskussion von Juli 2004 verlinken ? --Zipferlak 16:38, 9. Sep. 2009 (CEST)

Büdde. Viele Grüße, —mnh·∇· 17:19, 9. Sep. 2009 (CEST)

Merci. --Zipferlak 17:24, 9. Sep. 2009 (CEST)

Auswertung: Der Artikel wurde aufgrund der genannten Mängel und mangels Beteilgung an der Diskussion aus den exzellenten Artiekln entfernt. -- Achim Raschka 07:46, 13. Sep. 2009 (CEST)

Name hat nichts mit Topologie zu tun

Seid ihr euch da sicher? Ich halte das für wenig wahrscheinlich, dass sich diese Bezeichnung unabhängig aus τόπος und λόγος entwickelt haben soll. Ein besonders großer inhaltlicher Bezug besteht in der Tat nicht, aber vom Namen her? --Chricho ¹ ² ³ 17:35, 30. Jul. 2012 (CEST)

Es scheint in der Tat keinen wirklich offensichtlichen Grund zu geben, warum man das so genannt hat. hier orakeln einige Leute dieser Frage hinterher, aber deren Theorien überzeugen mich alle nicht so recht. --goiken 19:49, 30. Jul. 2012 (CEST)

Ich habe mir da auch so etwas wie die obere Antwort gedacht, dass man Topologie und Graphentheorie nicht so getrennt hat. Siehe auch der Artikel Topologie (Mathematik), der bei der historischen Beschreibung mit einem Beispiel anfängt, das heute der Graphentheorie zugerechnet würde. --Chricho ¹ ² ³ 20:32, 30. Jul. 2012 (CEST)

Das hat ganz sicher mit Topologie zu tun: Alexandroff-Topologie und Halbordnung (englisch)(nicht signierter Beitrag von 46.237.199.236 (Diskussion) 11:33, 18. Jun. 2014 (CEST))

Die Frage ist, was es etymologisch damit zu tun hat. Ich vermute weniger, dass es von so einem formalen Zusammenhang kommt, sondern wohl eher aus der historischen Einheit von Topologie und Graphentheorie. --Chricho ¹ ² ³ 09:44, 18. Jun. 2014 (CEST)