Benutzer Diskussion:Jochen Burghardt

Vorlage Literatur

Moin Moin Jochen Burghardt, ich habe gesehen, dass du die Vorlage {{Literatur}} noch mit veralteten Parametern (wie |Monat= ) verwendest. Die Vorlage wurde 2016 modernisiert, es hört nun alles auf |Datum= und auch neue Dinge sind dazugekommen. Wenn du eine lokal gespeicherte Version hast, magst du diese aktualisieren? Vielen Dank im Voraus --Crazy1880 10:25, 25. Aug. 2019 (CEST)

en:Tree traversal

@Jochen Burghardt: Auf deiner englischen Benutzerseite habe ich gelesen, dass Deutsch deine Muttersprache ist. Da es auch meine ist und ich mich in Deutsch schon deutlich leichter tue, wäre es mir lieb, wenn du da beim genannten Artikel mitmachen würdest.

Ich habe dort einige Präzisierungen, für die ich keine satten Belege habe. Dazu gehört eine Präzisierung der Begriffe Pre-, In- und Post-order-Traversierung, die zwar nicht im Widerspruch zu den „Definitionen“ in der Literatur stehen, aber von mir eben auch nicht so dort zu finden sind. Wenn ich die Änderung so hochlade, wie sie ist, dann sehe ich die Gefahr, dass sie als WP:TF revertiert wird. So hätte ich gerne deinen frühen Kommentar plus evtl Verbesserungen, bevor dies passiert. Das könnte bedeuten, dass ich dir die Änderung maile oder dass du in der Lage und willens bist, die evtl hochgeladene Änderung alsbald zu überprüfen.

Ich hänge diese deine Benutzerseite an meine Beobachtungsliste, so dass du hier antworten mögest. Viele Grüße, --Nomen4Omen (Diskussion) 19:14, 6. Mär. 2020 (CET)

@Nomen4Omen: Ich editiere hauptsaechlich die englischen Seiten (wer interessiert sich im deutschen Sprachraum schon fuer Mathematik/Informatik?!) und bin mit den deutschen nicht gut vertraut. "TF" entspricht anscheinend en:WP:OR, richtig? Kommentieren und Verbesserungen vorschlagen mache ich gerne. Allerdings schaue ich diese Seite hier nicht regelmaessig an, und ebensowenig meine deutsche Watchlist (keine Ahnung, wie das hier heisst). Wenn Du mich z.B. auf meiner englichen Diskussionsseite en:User talk:Jochen Burghardt anpingst, kriege ich das i.allg. innerhalb von 24 Std. mit. Es ist mir auch lieber, wenn alle Diskussionen dort ablaufen; das vereinfacht mir ggf. spaeter die Suche.

Allerdings bin ich sicher kein Experte fuer Baumtraversierung und noch weniger fuer Design Patterns (die ich auf der englischen Diskussionsseite erwaehnt habe). - Viele Gruesse - Jochen Burghardt (Diskussion) 19:43, 6. Mär. 2020 (CET)

Nun ja, da ich die Unterhaltung in Deutsch führen wollte, wäre en:User talk:Jochen Burghardt wohl etwas heimlichtuerisch für unsere englischen Freunde. Eine andere Idee wäre, dass ich dir das Zeug auf die hier angebotene E-Mail schicke und du dir die Sache als temporäre Änderung am Artikel anschaust. --Nomen4Omen (Diskussion) 20:43, 6. Mär. 2020 (CET)

@Nomen4Omen: Falls jemand ein Problem mit deutschem Text auf en:User talk:Jochen Burghardt hat, ist er/sie selbst schuld; ausserdem gibt es ja recht gute automatische Uebersetzungsprogramme. Meine E-Mail-Adresse gebe ich nicht so gerne heraus. Du kannst mir aber gerne via Wikipedia weitere E-Mails schicken (eine hab ich bekommen). E-Mail-Diskussionen von Editoren sind auch, soweit ich weiss, nicht gerne gesehen, weil das nicht transparent fuer alle ist. Heute habe ich auch gesehen, dass ich im englischen Wikipedia benachrichtigt werde, wenn Du hier (Benutzer Diskussion:Jochen Burghardt) etwas schreibst. Also dann vielleicht doch am besten hier. Gibt es denn ein Pendant zu {{clarify span}}, mit dem ich Kommentare direkt in den Text schreiben koennte? - Jochen Burghardt (Diskussion) 19:04, 7. Mär. 2020 (CET)

@Jochen Burghardt: Ich verstehe, dass du deine eMail nicht herausgeben möchtest. Andererseits hätte es den Vorteil, dass ich eine kolorierte Datei anhängen könnte, die du irgendwo (bspw. in einer WP-Sandbox) sichtbar machen könntest und mir dann gegenkoloriert und kommentiert zurückschicken könntest.

Apropos Sandbox. Ich habe gerade meine Sandbox User:Nomen4Omen/sandbox (vermutlich dann en:User:Nomen4Omen/sandbox) mit meiner augenblicklichen Version des Artikels gefüllt. Wenn du da rankommst, könntest du u.U. deine Korrekturen auch dort eingeben. Ich habe die Seite in meine Watchlist getan. Wenn das ein Weg für dich ist, dann machen wir das doch so. (Gegen meinen Vorschlag mit dem Attachment ist das nur hinsichtlich der Kolorierung schlechter.)

Fraglos soll das Ergebnis transparent sein, was IMHO nicht bedeutet, dass jede Diskussion öffentlich stattfinden muss. --Nomen4Omen (Diskussion) 20:45, 7. Mär. 2020 (CET)

@Nomen4Omen: Ja, ich kann die Seite sehen und auch schreiben (hab probeweise ein clarify span hinterlassen). Der Text ist aber auf Englisch - wolltest Du nicht die deutsche Seite bearbeiten? Du kannst mir ja das Bild mal per Mail schicken, notfalls schreibe ich Vorschlaege als RGB-Codes auf die Sandbox-Seite. - Jochen Burghardt (Diskussion) 21:07, 7. Mär. 2020 (CET)

@Jochen Burghardt: Hab's gesehen, funzt also. Nee, mir ging es um die englische Seite! (Bei der deutschen wäre wohl am besten ein neuer Artikel. Das evtl später mal.) Welches Bild meinst du? Vorschlaege als RGB-Codes klingen gut! Kenn ich noch nicht. --Nomen4Omen (Diskussion) 21:39, 7. Mär. 2020 (CET)

@Nomen4Omen: Ich meinte Deine "kolorierte Datei". Am Beispiel von File:Filter vs ultrafilter.svg koennte ein Vorschlag sein "besser dieses Dunkelrot (im Englischen: {{color|#800000|dieses Dunkelrot}}, wirkt auf die Vordergrund-/Schrift-Farbe) fuer die dunkelgruenen Knoten (z.B. fuer {1,2,3,4})". Ist das in Deiner Sandbox schon Dein neuer Vorschlag? Wenn ja, welche Teile soll ich mir ansehen? Gibt es eine Fragestellung, auf die ich besonders achten soll? - Jochen Burghardt (Diskussion) 15:21, 8. Mär. 2020 (CET)

1

@Jochen Burghardt: Meine kolorierte Konzeptdatei ist eine Word-Datei, in der ich den Hintergrund verschiedener Abschnitte unterschiedlich markiert habe. Diese Markierung kommt in WP nicht heraus (und soll auch nicht). Wäre aber evtl für unsere Kommunikation u.U. ganz nützlich. Probieren wir es aber erstmal ohne und stattdessen mit verbaler Beschreibung:

1. Mit dem engl. Wort "orbit" für dt. "Umlauf" oder "Parcours" bin ich nicht glücklich. In meinem Lexikon wird "Parcours" ganz nahe bei den Pferdchen gesehen, was ich auch nicht gut fände.
2. Das Wichtigste wohl: Traversal ist klar, aber ich habe nirgendwo eine wirkliche Definition von pre-, in-, post-order traversal gefunden. Und relativ klar ist auch die Benennung der Abschnitte in der rekursiven Prozedur als pre-, in- oder post-order Abschnitt. Dass dann ein Traversal pre-order ist, wenn er keine in- oder post-order Operationen enthält, scheint auch klar – wird aber nirgendwo so gesagt. (In diese Auffassung passen meiner Beobachtung nach alle im Netz zu findenden Zuschreibungen.) Was macht man aber in einem Fall wie copy-traversal, bei dem zwischen allen 2 Zugriffen zu den Kindern (also in allen 3 Abschnitten) echt Wesentliches passiert (so herausgearbeitet in meinem Vorschlag "recursiveDuplicateTree"). [Du selbst hast Dich hier ja mit einer IP-Adresse, die Dich immer wieder revertiert hat, streiten müssen.] Ich versuche herauszuarbeiten, dass ein Traversal pre-order ist, wenn er keine in-, post-order Operationen enthält, in-order eben ohne post-order Operationen und ein post-order Traversal sowohl pre- wie in-order Oparationen haben kann. (N.B.: Alle Traversal jeder Sorte laufen IMMER den vollen Orbit!) Explizit bringe ich auch heraus, dass der copy-traversal "recursiveDuplicateTree" post-order ist, weil er, wenn er beim ersten Berühren des n-ten Knoten abgebrochen wird, keine vollständige Kopie abliefert. (Ein in-order Traversal wäre vollständig, wenn er nach der n-ten in-order Operation abgebrochen wird!) IMHO ist das das einzig mögliche Verständnis dieser Begriffe, aber es fehlt ein Beleg. (Obwohl ich schon Streitereien dazu im Netz gesehen habe.)
3. Die Begriffe pre-, in-, post-order sequentialisation sind dagegen klar und belegbar definiert.
4. Der Abschnitt "Generic tree" scheint genau mein Verständnis zu proklamieren. Er zitiert aber nichts. (Muss es übrigens nicht besser "General tree" heißen?)
5. Den Code für die iterativen pre-, in-, post-order traversals habe ich aus dem Netz, es scheint sich aber nicht um eine "notable source" zu handeln. (Die Vorgänger im existierenden Artikel waren völlig unbelegt!) Ich werde beide wohl rausnehmen.
6. Die bisherige Nebeneinanderstellung links rekursiv vs. rechts iterativ jeweils für pre-, in-, post-order halte ich für witzlos.
7. Bei der begrifflichen Aufspaltung spielt sich wieder das häufig im Netz zu findende Muster ab, da es immer nur eine einzige Operation, die pre-, in- oder post-order ist, gibt.
8. Ich habe hier Code für eine iterative Prozedur, die sowohl pre-, in- wie post-order Operationen unterstützt (ganz ähnlich wie die rekursive Prozedur "recursiveTraversal"), die ich schon gerne reinbringen würde.
9. Sehr nützlich finde ich auch eine (natürlich iterative) Prozedur "inOrderNext", die es gestattet, zum nächsten Knoten in in-order-Reihenfolge fortzuschreiten. Ich habe zwei Belege dafür, aber sie wurde mehrfach aus dem Artikel wieder rausgeschmissen, weil die Quellen dem Reverter nicht notabel genug waren (s. en:talk:tree traversal).
10. Der Einfachheit halber würde ich alle iterativen Code-Beispiele mit parent-Pointer codieren.

Soviel erstmal. --Nomen4Omen (Diskussion) 20:47, 8. Mär. 2020 (CET)

@Nomen4Omen: Mit einer Word-Datei haette ich (unter Linux) sowieso Probleme. Ich steuere mal ein paar Weisheiten aus Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading/MA 1974, ISBN 0-201-00029-6. bei:

1. Orbit o.ae. verwenden sie gar nicht. Es scheint mir auch weniger ein Begriff zu sein, der sich im Code wiederfindet, als eine anschauliche Vorstellung, um Pre/In/Post zu erklaeren. Es wuerde auch genuegen, es zu beschreiben, ohne einen namen zu geben. Z.B. "Imagining an ant starting at the root and walking around the circumference of a full binary tree as close as possible, it would visit each internal node three times: first descending from the parent node, then ascending from the left and then the right child node; cf. picture."
2. Aho et.al. sagen: "Many algorithms which make use of trees often traverse (visit each vertex of) the tree in some order. There are several systematic ways of doing this. Three commonly used traversals are preorder, postorder, and inorder. ... A preorder traversal is defined recursively as follows: 1. visit the root r. 2. Visit in preorder the subtrees with roots v1,...,vk in that order. ..." - Nach meiner Erfahrung aus der Talk-Diskussion scheint mir wichtig, dass der Zugriff auf die Knotendaten gebuendelt an einer einzigen Stelle im Source-Code erfolgen muss (so lese ich Aho's "visit the root"). Ausserhalb dieser Stelle duerfen nur rekursive Aufrufe von traverse stehen.
3. (Nach einer Unterbrechung geht's weiter) - Jochen Burghardt (Diskussion) 10:13, 9. Mär. 2020 (CET)

@Jochen Burghardt: Danke auf jeden Fall.

Zu Deinem 1: Dein Beispiel mit "ant" ist fraglos gut. Ich brauche den Begriff aber mehrmals und hätte dann gern etwas Kürzeres. "circuit" könnte besser sein als "orbit".

Zu Deinem 2: Du meinst sicherlich: Natürlich dürfen bei einem "allgemeinen" Traversal die Zugriffe auf die Knotendaten beliebig zwischen die rekursiven visits der Kinder verteilt sein, aber um als "preorder traversal" zu gelten, darf nach dem Zugriff aufs erste Kind kein Zugriff auf den current node mehr passieren. Das würde ähnlich wie bei mir bedeuten, dass aus einem "allgemeinen" Traversal wie in meinem "recursiveDuplicateTree" durch Verzögern des Zugriffs auf den current node ein post-order traversal gemacht werden kann, bei dem nur nach den Zugriffen auf das letzte Kind am current node etwas gemacht wird:

mynode* recursiveDuplicateTreePostonly(mynode* N)
{
  mynode* copy;
  mynode* copyL;
  mynode* copyR;

  if (N == NULL) return NULL;
  copyL = recursiveDuplicateTreePostonly(N->childL); // access the left child
  copyR = recursiveDuplicateTreePostonly(N->childR); // access the right child

  // Jetzt käme wohl die Bündelung, wie Du sagst:
  copy = (mynode*)malloc(sizeof(* N));      // post-order position
  if (copy == NULL)
  {
    fprintf (stderr, "Out of memory!\n");
    exit (EXIT_FAILURE);
  }
  copy->data = N->data;                      // post-order position
  copy->childL = copyL;                      // post-order position
  copy->childR = copyR;                      // post-order position
  return copy;
}

Wenn das aber iterativ gelöst werden soll, wird es wohl schwierig mit dem Merken und Zuordnen von copyL, copyR.

Wenn ich dann die ganze pre-, in-, post-order traversal Begrifflichkeit etwas herunterhänge, und das Präzisieren vermeide, könnte das durchgehen.

Schade, dass Aho et.al. nur den preorder erwähnen!? Besten Gruß, --Nomen4Omen (Diskussion) 13:08, 9. Mär. 2020 (CET)

@Nomen4Omen: (Bin wieder zurueck)

• "Orbit" heisst wohl "(Planeten-)Bahn" oder "Wirkungsbereich", da finde ich "circumference" ("Peripherie", aber auch "Umfang") oder "border", "boundary" besser (aber noch nicht rightig gut). Wenn man sich den baum als Draufsicht auf ein Gebaeude vorstellt, waere es dessen Aussenmauer ("outer surface"), an der die ant entlanglaeuft. Im Bild File:Sorted binary tree ALL.svg ist sie eingezeichnet, das fand ich ganz gut.
• Aho definiert pre- in-, und post-order; ich war nur zu faul, das alles einzutippen.
• Der Klassiker D.E. Knuth: Fundamental Algorithms (=  The Art of Computer Programming), 2. Auflage, Band 1, Addison Wesley, 1969. hat ein Kap.2.3.1 "traversing binary trees". Dort heisst es "... traversing ... a tree ... is a method of examining the nodes of the tree systematically so that each node is visited exactly once. A complete traversal of the tree gives us a linear arrangement of the nodes, and many algorithms are facilitated if we can talk about the 'next' node following or preceding a given node in such a sequence." Bei Knuth heisst es idiotischerweise "pre-/post-/end-order" statt "pre-/in-/post-order".
• Bei der Diskussion auf en:Talk:Tree_traversal#Tree_duplication_in_pre-_or_in_post-order? hab ich mich ziemlich verheddert, als es darum ging, ob zusaetzliche Parameter oder Rueckgabewerte fuer visit() zugelassen werden sollen. Die wurden benoetigt, um den duplizierten Baum aufzubauen (und nicht, um das Original zu traversieren). - Um dieses Problem zu vermeiden, koennte man sagen, dass Baumduplizieren sich ueberhaupt nicht als einfacher (pre-/in-/post-)Traversierungsalgorithmus darstellen laesst, weil nicht eine Sequenz von Knoten(-daten), sondern ein neuer Baum erzeugt werden soll. (Ich glaube, der Absatz, der das Gegenteil behauptet, hatte ohnehin nie eine Quelle.) Dann liesse sich die klare Definition bzgl. "sequentialization" problemlos zu einer fuer "traversal" verallgemeinern.
• Ich wuerde dazu tendieren, auf die Vorstellung iterativer Versionen ueberhaupt zu verzichten. Soweit sie einen expliziten Stack verwenden, sparen sie keinen Speicherplatz gegenueber der rekursiven Definition. Allenfalls waere(n) der/die Algorithmus(en?) zur Wirbeltraversierung (dieser Link zeigt leider in den Wald...) vorstellenswert, der mit wenigen Extra-Bits auskommt. Und Dein inOrderNext (hab's auf en:Talk:Tree traversal nicht gefunden; sollte es nicht auch besser nextNodeInDepthFirstOrder o.ae. heissen? Es muesste duch unabhaengig von pre/in/post sein, oder?), weil es auch ein Abweichen von der ueblichen Knotenreihenfolge erlaubt (z.B. in for (n=root; n!=NULL; n=inOrderNext(inOrderNext(n))) visit(n);, um erstmal nur jeden zweiten Knoten zu besuchen).

Soweit fuer heute. - Jochen Burghardt (Diskussion) 15:33, 9. Mär. 2020 (CET)

@Jochen Burghardt: Vielen Dank auf jeden Fall. Die Zeichnung in File:Sorted binary tree ALL.svg ist auf jeden Fall gut. Ich habe sie (nach meinem Dafürhalten) in File:Sorted binary tree RGB.svg nur dahingehend zu erweitern versucht, dass die "circumference" in dem Moment, wo man an der entsprechenden Stelle des Knotens vorbeikommt, in der entsprechenden Farbe "aufleuchtet".

pre- in-, und post-order (alleine) ist schon klar! Nicht klar scheint mir pre- in-, und post-order traversal. Sagt Aho was dazu?

Meiner Meinung nach ist klar, dass man die Duplizierung eines Baums per Traversierung machen kann (vielleicht sogar muss). Es kann aber sein (da habe ich kein persönliches Problem damit), dass das (wie Du sagst), kein "einfacher (pre-/in-/post-)Traversierungsalgorithmus" sein kann. Das hängt halt von der Definition von pre- in-, und post-order traversal ab. Im Ggs. dazu klar sind die 3 Begriffe pre-, in-, post-order sequentialization, weil es nur auf das printf ankommt. (Die sind auch sowohl bei File:Sorted binary tree ALL.svg wie File:Sorted binary tree RGB.svg als Bildunterschriften angebracht.)

Genau genommen gibt es bei dem "Advance to the next node" auch 3 Versionen:

(A) Links-vor-Rechts

(A1) preOrderNext

(A2) inOrderNext

(A3) postOrderNext

(B1 bis B3) Das Ganze gespiegelt als Rechts-vor-Links

Am wichtigsten scheint mir inOrderNext zu sein. Wie die Funktion am Ende heißt, ist im Moment egal. Hat man inOrderNext, dann kann man eine traversal-Schleife durch einen ggf. riesigen Baum zerlegen, indem man per (unscharfem) Search einen Knoten direkt ansteuert, danach aber per inOrderNext weitersucht. (Ein unscharfes Search ist m.W. bei 2D-Datenbanken, bei denen eine "Nachbarschaftssuche" betr. die 2 Koordinaten Länge und Breite unterstützt werden soll (bspw. indem sie auf einen nachbarschaftserhaltenden linear geordneten Wert komprimiert werden), unvermeidlich. Am besten evtl. erklärt in Z-Kurve oder Hilbert-Kurve.) Aber auch ohne 2D: Ein inOrderNext-Feature vermeidet die evtl. Problematik einer sonst bei der Traversierung anzutreffenden Rückruffunktion mit ihrer Inversion of Control, indem ganz standardmäßig gedacht und programmiert werden kann. Dabei ist eine volle Traversierung eine volle Schleife. Ferner erlaubt inOrderNext (wie Du erwähnst), eine Schleife an irgendeiner Stelle (wie sonst auch) zu beginnen und anderswo zu beenden, z.B. for (n=search("BWEPRTIZQ"); (n!=NULL) && (n->key <= ("QWEPRTIZB")); n=inOrderNext(n)) actOn(n);. Diese Argumente habe ich in en:User_talk:Nomen4Omen#tree_traversal (bis 9 September 2015 (UTC)) und in en:talk:tree traversal#New section "Non-recursive tree traversal by Iteration" anzubringen versucht und bin damit gescheitert. (Ich weiß nicht, warum er Sedgewick und Pfaff als Quellen abgelehnt hat (s. Tree traversal: Difference between revisions im Abschnitt ====Nonrecursive tree traversal by iteration====).

Für mich ist es keine Frage, dass es sowas gibt; auf jeden Fall bei den Datenbank-Profis. --Nomen4Omen (Diskussion) 18:19, 9. Mär. 2020 (CET)

2

• Bzgl. der Bilder faende ich gut, eine Synthese der beiden Versionen zu erstellen: sowohl die Pfeile als auch die Umrisslinie. Auch finde ich die Vorzeichen im Text schlecht zu lesen, leichter lassen sich nur Ziffern oder Buchstaben als Knotennamen lesen.
• Aho et.al. sagt nicht mehr, als ich abgetippt habe. Ihre Ausfuehrungen wuerde ich in C-Code so verstehen: void traversePreorder(tree *t) { if (t==NULL) return; visit(t); traversePreorder(t->left); traversePreorder(t->right); } und analog fuer in-/post-order. Ich vermute, Aho und auch Knuth denken abstrakt in Graphen und haben sich keine Gedanken ueber Feinheiten gemacht, wie sie bei der Frage "laesst sich Duplizieren als Pre-, In- oder/und Post-order darstellen?" auftreten. Will sagen, sie reden in Wirklichkeit vermutlich nur ueber sequentialization. Deshalb sollten wir uns vielleicht ebenso beschraenken. Zumindest, bis wir eine Quelle gefunden haben, die eine echte Verallgemeinerung zu Traversierung beschreibt (und unter die dann auch das Duplizieren fallen sollte).
• Dein "Advance to the next node" hatte ich erst falsch verstanden, naemlich, dass es den naechsten Knoten auf dem Weg der Ameise liefert, egal, ob er (bei sequentialization) ausgegeben wird oder nicht. Du meinst aber den naechsten, der ausgegeben wird. Klar, dann gibt es die Versionen, die Du beschreibst. Und eigentlich auch klar, dass diese letztere Funktion gebraucht wird, waehrend mein erster Gedanke einer ziemlich trivialen Funktion entsprach. Deine Anwendung mit "Weitersuchen in der Naehe" finde ich ueberzeugend.
• Altenmann, der Dich revertiert hat, ist sehr pingelig, glaube ich; ich hatte auch schon mal eine (fuer mich erfolglose) Diskussion mit ihm. Aber Sedgewick und Pfaff ist doch eine serioese Quelle, das laesst sich nicht bestreiten. Ist denn der Code fuer "Advance to the next node" dort beschrieben, und die Anwendungen? Dann sollten wir es nochmal versuchen. Evtl. zitiert Sedgewick auch ein paar Originalarbeiten, deren Quellen man ebenfalls hinzufuegen koennte (mit etwas Glueck sind welche davon online verfuegbar). Spaetestens wenn alle Aussagen im Abschnitt belegt sind, kann doch wohl keiner mehr meckern.

Gruss - Jochen Burghardt (Diskussion) 21:58, 9. Mär. 2020 (CET)

3

@Jochen Burghardt: Ich habe eine neue Version in die Sandbox. Sie ist nicht fertig. Am wichtigsten ist mir wohl der Abschnitt:

A Bounded-Space Tree Traversal Algorithm

Wenn Du ihn Dir anschauen würdest? Wenn soweit OK, schicke ich ihn an ArXiv?. Die Geschichte mit den pre-, in-, post-order traversals konnte ich wohl lösen mit dem Zitat aus Hirschberg: Die sagen "Standard post-order traversal". Vielen Dank im Voraus und besten Gruß - Nomen4Omen (Diskussion) 22:52, 16. Mär. 2020 (CET)

@Nomen4Omen: Hab ein paar Stellen geaendert, wo ich denke, das Englisch stimmte nicht. (Allerdings kann ich so gut Englisch nicht; und der VHS-Kurs wurde, wie alles, gerade abgesagt). Allgemeine Bemerkungen und Fragen fuege ich hier an:

• Fuer ArXiv solltest Du in einer Einleitung den noetigen Kontext herstellen. Der unterscheidet sich sicher von dem des Wikipedia-Unterabschnitts, weil letztere ja schon auf den vorigen Text aufbaut.
• Den Unterschied zwischen "space" und "cost" verstehe ich nicht. Beides enthaelt den zusaetzlichen Speicheraufwand, einmal informell und einmal als Formel, oder? Zum Zeitaufwand koenntest Du uebrigens auch etwas sagen (vermutlich ueberall O(n)?).
• Welchen Ansatz implementiert der Code so, wie er da steht? Muessen Zeile 21-24 und 47-50 in bestimmten Ansaetzen weggelassen werden? Ohne Zeile 59 wird Zeile 61 unerreichbar, ist das gewollt? Wenn der Code alle 6 Ansaetze zeigen soll, ist es u.U. besser, mit '#ifdef' zu arbeiten. Oder noch besser mit abstrakten Funktionen (z.B. determineChirality, determineParentNode), die in jedem Ansatz unterschiedlich implementiert sind.
• Ich finde den Code sehr schwer zu verstehen. Kannst Du nicht wenigstens ein paar 'goto' einsparen und durch Schleifen ersetzen? Und den uebriggebliebenen Labels suggestievere Namen geben? Ich wuerde auch die Zuweisungen aus den 'if'-Abfragen herausziehen.

Gruss - Jochen Burghardt (Diskussion) 14:56, 17. Mär. 2020 (CET)

4

@Jochen Burghardt: Vielen Dank für Deine Kommentare:

• Das mit der space cost habe ich verbessert. (Eigentlich doppelt gemoppelt, aber ich wollte die genaue Angabe in Wörtern und Bits nicht unterschlagen. Die time cost ist drin gewesen. Vllt am falschen Platz? Du hast Recht: überall O(n).
• Der Code implementiert NUR den Approach 6 und soll NICHT alle approaches zeigen. Die hervorgehobenen Zeilen würden bei anderen approaches anders aussehen. In der jetzigen Version kommt das hoffentlich besser raus. Den einzigen geringfügig ausführlicheren Ausblick mache ich auf Approach 5.
• Zugegeben, der Code ist unangenehm zu lesen. (Das ist aber fast immer so.) Bei den Namen der Labels halte ich mich jetzt an RGB. Darauf könnte ich in der Erläuterung noch hinweisen. Gr ist keine Schleife (oder umfasst alle anderen ??). Bei 'Red' und 'Blu' habe ich passable Versionen mit for-Schleife gefunden (im Moment als Doppel unterhalb der Version ohne for-Schleife). Sie ist aber nicht so gut geprüft wie die erste. Bei 'Red' und 'Blu' sitzen die Ende-Bedingungen an einem Platz, wo in der Schleife noch etwas zu tun wäre, so dass man diese Statements nach oben nehmen muss und hinter diesen Statements in die Schleife reinspringen. Die Zuweisungen in den 'if's habe ich separiert.
• Was ArXiv angeht, stimme ich mit Dir überein. Würde aber gerne den Code noch etwas reifen lassen.

Vielen Dank im Voraus und besten Gruß - Nomen4Omen (Diskussion) 21:29, 18. Mär. 2020 (CET)

Meine Änderungen vom 19.03. betreffen Wording, Belege, Kommentare zum Code vom for-Schleifen-Algorithmus. Ferner habe ich dort ein doppeltes Statement raus. In der Tat finde ich, dass dieser zweite for-Schleifen-Algorithmus leichter zu lesen ist. Beste Grüße - Nomen4Omen (Diskussion) 17:22, 19. Mär. 2020 (CET)

@Jochen Burghardt: Sorry, dass ich erst jetzt bemerkt habe, dass auch die andere for-Schleife zu lang ist. Ich habe jetzt (20.03.) beide durch while-Schleifen ersetzt. Nach meiner Erinnerung gibt es die C-Syntax im Prinzip so, aber sicher bin ich mir nicht (und habe gerade keinen C-Compiler zur Hand). Ich weiß auch nicht, ob man in eine Schleife reinspringen darf. (Schön ist das sicherlich nicht, spart aber viel doppeltes Hinschreiben.) Ich würde mich freuen, wenn Du mir in dieser Hinsicht grünes Licht geben könntest.

Mit vielem Dank im Voraus und mit besten Grüßen - Nomen4Omen (Diskussion) 11:01, 20. Mär. 2020 (CET)

@Nomen4Omen: Ich hab Deinen Code nach 3 Aenderungen durch den gcc uebersetzt bekommen; ich hab sie auf Deiner Seite en:User:Nomen4Omen/sandbox#A_Bounded-Space_Tree_Traversal_Algorithm nachgezogen. Fuer den Compiler muss noch ein "#include <stdio.h>" ganz oben stehen, wegen printf. In Schleifen reinspringen geht offenbar, aber Tony Hoare stuenden bestimmt die Haare zu Berge, wenn er das saehe. Die Entsprechung zu den pre-/in-/post-order-Farben finde ich hilfreich, und auch, dass Du jetzt pro Farbe nur noch einen Label hast.

Fuer die Validierung Deines Algorithmus ist mir noch eingefallen: so irre viele Binaerbaeume der Hoehe 10 (z.B.) gibt es doch gar nicht - Du koenntest sie systematisch alle erzeugen und dann Deinen Algorithmus darauf testen. Wenn Du die keys systematisch benennst und auch sie (statt value) ausgibst, kannst Du leicht berechnen, welches Ergebnis Dein Algorithmus fuer einen generierten Baum liefern muss. Wenn er bis zu dieser Hoehe alles richtig macht, waere ich geneigt zu glauben, dass er generell korrekt arbeitet. Gruss - Jochen Burghardt (Diskussion) 11:33, 20. Mär. 2020 (CET)

Hab mich mit der Anzahl der Baeume vertan. Unter en:Term (logic)#Ground and linear terms steht eine Formel fuer die Anzahl. Mit f₀=1, f₁=2, f₂=1 ergibt sich der Reihe nach θ₀=1, θ₁=4, θ₂=25, θ₃=276, θ₄=76729, θ₅=5887492900. Letzteres ist vielleicht gerade noch so zu schaffen. Na ja, Hoehe 4 (das geht bestimmt noch) ist vielleicht auch ok. - Jochen Burghardt (Diskussion) 14:53, 20. Mär. 2020 (CET)

@Jochen Burghardt: Vielen Dank für Dein Ausprobieren mit gcc. In der neuen Version habe ich mehr Zeilen farblich hinterlegt, weil ich auch den Abstieg herausheben wollte. Dafür hätte ich gerne eine neue Farbe gehabt, also eigentlich insgesamt 3. Aber ich hab's weder zusammen mit <syntaxhighlight> noch mit <div> oder <span> hinbekommen. Es wäre schön gewesen, das RGB irgendwie farblich wieder aufzunehmen. Beim Wiederaufstieg sind die 4 Statements schön zusammen, da würde sich ein Makro anbieten, aber beim Abstieg gibt es 2 Wege (einen aus Green heraus und einen aus Blue) und die sind auch noch in 3 Gruppen zerrissen.

θ₄=76729 wäre natürlich zu schaffen und müsste auch ausreichen. Ich geh an den while-Algorithmus nochmal mit Papier und Bleistift durch. Viele Grüße - Nomen4Omen (Diskussion) 21:23, 20. Mär. 2020 (CET)

Ich hab mal die Tests implementiert und auf der letzten Version ablaufen lassen. Scheint ok zu sein. Wenn Du willst, kann ich Dir die Implementierung zukommen lassen; sie ist teils in C (Testausfuehrung) und teils in Prolog (Testdatengenerierung). Dass in der vorigen Version was nicht stimmte, hab ich auch feststellen koennen. - Gruss Jochen Burghardt (Diskussion) 15:42, 22. Mär. 2020 (CET)

@Jochen Burghardt: Hab vielen Dank! Das ist ja super! Ich schau mal, wo und wie ich einen C-Compiler herbekomme. Aber wichtiger wäre vllt die ArXiv-Geschichte. Es wird eine Einleitung brauchen (Du sagtest es). Da könnte ich doch eine abgekürzte Version von Hirschberg nehmen. Der Algorithmus ist ja auch nach Stoßrichtung und Funktion ganz nahe dabei. - Nomen4Omen (Diskussion) 19:00, 22. Mär. 2020 (CET)

Internal logic

Yeah, but as I wrote, I'm a gnome. == ~~~~ Peter NYC (Diskussion) 12:45, 28. Mär. 2021 (CEST)