Diskussion:Topologische Sortierung

Diskussion aus Wikipedia:Review:

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)

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)