P3: ## und treeordered mit flatten

jack_90
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 29. Sep 2009 22:38
Wohnort: Darmstadt
Kontaktdaten:

P3: ## und treeordered mit flatten

Beitrag von jack_90 »

Hi,
wir haben beide genannten Funktionen mithilfe der flatten Funktion implementiert.
Jetzt hängen wir leider an den Beweisen der jeweils ersten Lemmas.
Frage hierzu:
Macht es überhaupt Sinn die Funktionen mithilfe von flatten zu realisieren oder erschwert das nur den Beweis?
EiSE Tutor WS 12/13

erna
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 9. Dez 2009 15:05

Re: P3: ## und treeordered mit flatten

Beitrag von erna »

Das war auch unser erster Gedanke aber nach nach Tagen der Verzweiflung haben wir es anders probiert.
Durch diese Implementierung ist der Beweisbaum des ersten Hilflemmas und des Hauptlemma ziemlich gleich.

Ich würde dir davon abraten

AlexanderF
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 140
Registriert: 2. Mai 2010 17:55

Re: P3: ## und treeordered mit flatten

Beitrag von AlexanderF »

erna hat geschrieben:Das war auch unser erster Gedanke aber nach nach Tagen der Verzweiflung haben wir es anders probiert.
Durch diese Implementierung ist der Beweisbaum des ersten Hilflemmas und des Hauptlemma ziemlich gleich.

Ich würde dir davon abraten
Das sehe ich genau so,
zwar war mir auch offensichtlich, dass,
wenn flatten(atree) geordnet ist, auch der atree geordnet sein musste (in dem in der Aufgabe angegebenen Sinn),
aber, dann würde sich das Hilfslemma "flattening keeps ordered" von selbst erledigen,
und, wie erna schon sagte, das Lemma "treesort(k) is ordered tree" wäre praktisch gleich treesort sorts,

ich denke, dass es wirklich so gemeint ist, dass man treeordered so definieren soll, wie es auch in der Aufgabe angegeben ist:
als "für alle inneren Knoten des Baums gilt: alle Zahlen im linken Teilbaum sind kleiner
oder gleich, alle im rechten Teilbaum größer oder gleich dem Datum des inneren Knotens",

und das Hauptlemma dann über "treesort(k) is ordered tree" und "flattening keeps ordered" beweisen soll.

edit:
und bei ## genauso, also nicht einfach flatten und dann #,
sondern ## ohne flatten definieren
weil sich sonst das Lemma "n ## t = n # flatten(t)" auch von selbst erledigen würde und die anderen beiden Lemmas gleich wären.

jack_90
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 29. Sep 2009 22:38
Wohnort: Darmstadt
Kontaktdaten:

Re: P3: ## und treeordered mit flatten

Beitrag von jack_90 »

erna hat geschrieben:Durch diese Implementierung ist der Beweisbaum des ersten Hilflemmas und des Hauptlemma ziemlich gleich.
Das war mir auch aufgefallen. Wir haben es jetzt auch anders gelöst. Die treeordered Methode wird dadurch natürlich ziemlich hässlich.
Danke für euren Input.
EiSE Tutor WS 12/13

Antworten

Zurück zu „Archiv“