Seite 1 von 5

Klausur

Verfasst: 27. Sep 2007 13:16
von pandiz
Hat jemand die Tree-Sort Aufgabe gelöst?

Wurde Tree-Sort überhaupt in der Vorlesung erklärt?

Ehrlich gesagt habe ich sehr ernst gelernt und habe nicht nur die Übungen, sondern auch etwa 7-8 alte Klausuren mehrmals durchgerechnet. Dabei bin ich auf keine einzige Aufgabe gestossen, die Tree-Sort beinhaltet.

Dass auch spezifische Fragen gestellt werden, kann ich verstehen, dann aber bitte zu einem Thema womit man sich während des Semesters (Vorlesung + Praktika + Übung) gründlich beschäftigt hat.

Wo waren die B-Bäume (und aller deren Variationen), Hasching (und alle dessen Variationen), Suchbäume etc? Stattdessen stellt man eine Tree-Sort Aufgabe, die noch knapp auf 20% der Gesamtpunkte beträgt. Damit kann man vom Anfang an höchstens 80% der Punkte erreichen.

Es ist einfach ärgerlich, dass nach so viel Mühe und aufgewendete Zeit, bei der Klausur man einfach nicht die Möglichket bekommt, die gelernten Sachen zu zeigen.

Verfasst: 27. Sep 2007 13:42
von Rinderhack
Was ist denn TreeSort eigentlich? soll das Heapsort sein, wenn ja bin ich jetzt tief-traurig, denn dann wärs machbar gewesen!
Hatte es jedenfalls auch das Erste mal gehört und mich sonst auch vernünftig vorbereitet...

und man durfte ja auch keine Fragen stellen, sehr mies!

Verfasst: 27. Sep 2007 13:47
von Christoph B
Joa, wenn ich mich recht entsinne haben wir Treesort nur in zusammenhang mit heapsort besprochen :/
Und das keine dicken "Basteln Sie einen AVL Baum / B-Baum zusammen" Aufgaben gekommen sind hat mich auch sehr enttäuscht :O

Verfasst: 27. Sep 2007 13:47
von Wang Tang
Ne, Treesort is was anderes als Heapsort, keine Sorge. Z.B. hat TreeSort im worst case n^2, HeapSort hat stabil nlogn.
Siehe dazu Folie 12 (Sortieren) Seite 27. Das einzige was ich gefunden habe zu TreeSort. Im Härder und im Waldschmidt stehts auch nciht drin, jedenfalls nicht bei den Sortieralgorithmen.

Edit: Gibts die nächste GDI1/2-Klausur eigentlich schon wieder im Frühjahr?

Verfasst: 27. Sep 2007 13:57
von Maradatscha
die umfrage ist mist!
ich hab was hingeschrieben, gelöst ist sie aber nicht...

Re: Klausur

Verfasst: 27. Sep 2007 14:04
von Red*Star
pandiz hat geschrieben:Wurde Tree-Sort überhaupt in der Vorlesung erklärt?
Keine Ahnung, ich war da nicht da - aber in den Folien wird es auf jeden Fall /erwähnt/ (und eine Erklärung wird so ein bisschen angerissen, auf Folie 27 aus dem Kapitel "Sortieralgorithmen").
pandiz hat geschrieben:Wo waren die B-Bäume (und aller deren Variationen), Hasching (und alle dessen Variationen), Suchbäume etc?
Mit ein bisschen Nachdenken kommt man darauf, dass zumindest die B-Bäume in der Treesort-Aufgabe stecken könnten ;). Beim Hashing bin ich froh, dass es nicht bzw. kaum drankam, denn das geht mir gehörig auf den Sss...enkel. Aber das ist nur meine persönliche Meinung.
pandiz hat geschrieben:Es ist einfach ärgerlich, dass nach so viel Mühe und aufgewendete Zeit, bei der Klausur man einfach nicht die Möglichket bekommt, die gelernten Sachen zu zeigen.
Ärgerlich: Ja. Auch ich "hätte lieber gezeigt, was ich gelernt habe"... aber so ist das nun mal, es kommt, wie es so oft kommt: Nämlich anders als man denkt. Auch ich habe nur die ersten beiden Teilaufgaben der TreeSort-Aufgabe gemacht (und wahrscheinlich ist die b. absolut falsch, aber was soll's).

Sieh es doch mal positiv: Du weißt jetzt durch das Lernen bestens über die Themen der GdI2 Bescheid. Dass in einer Klausur per se nicht alles drankommen kann, ist klar, aber du lernst ja auch nicht für die Klausur, sondern dafür, dass du später mal dein Brot mit dem verdienen kannst, was du in diesen Jahren an Wissen und Erfahrung gesammelt hast.
In dieser Klausur war halt so einiges Improvisationstalent gefragt. In der Praxis wird man auch nie mit Problemstellungen konfrontiert, die genau das widerspiegeln, was man schon weiß (ok, der Vergleich hinkt etwas, das gebe ich zu :D).

Was ich mir persönlich gewünscht hätte, wäre mehr Zeit. Dieser Druck, der gemacht wird, ist doch sowas von schwachsinnig... mal ehrlich: Anstatt dass man ein Erfolgserlebnis hat, wenn man nach einigem Nachdenken auf die Lösung von (z.B.) der TreeSort-Aufgabe kommt (und damit nicht nur den Korrekteuren, sondern auch sich selbst zeigt, dass man etwas drauf hat), hat man wegen Zeitmangels überhaupt nicht die Gelegenheit dazu. Naja. Vielleicht nur mein Problem als Nicht-Hektiker...

Verfasst: 27. Sep 2007 14:16
von jm1035
http://www2.di.informatik.tu-darmstadt. ... tieren.pdf
Folie 27
Ich verstehe hier Treesort so definiert: Bau einen binären Suchbaum aus den Elementen, gib die Inorder des Baumes aus.

Und so hab ich die Aufgabe auch bearbeitet...in der Hoffnung, dass ich das auch richtig verstanden hab.

Verfasst: 27. Sep 2007 14:36
von MisterD123
binären suchbaum bzw avl-baum, dann haste auch worst case nlogn.

und ansonsten, mein lösungsvorschlag für die ersten zwei wäre:
a) b*baum benutzen wegen weniger externspeicherzugriffen nötig
b) f=(int)((p-8)/(s+4)) rechnet schlüsselgröße und seitengröße zusammen um den fanout der inneren knoten zu bestimmen, der hängt nämlich von diesen beiden werten ab. ein weiterer eventuell wichtiger wert die größe der eigenltichen datensätze weil die die anzahl der werte in den blattknoten mitbestimmt, man brauch mehr blätter wenn da weniger reinpassen und der ganze innere baum wird etwas größer.
bei der c hab ich dann aber auch keine idee mehr ^^ worst case wäre vermutlich irgendwie sowas das ne komplette seite an daten auf den ganzen baum aufgeteilt würde, sprich das man (anzahl der datensätze pro seite) knoten durch den ganzen baum ansprechen müsste, also (multipliziert mit der höhe des baumes) zugriffe, aber wie man das irgendwie formulieren soll war mir dann zu zeitaufwändig auszudenken, dafür dass ich doch relativ stark vermute dasses nicht die richtige lösung ist =) Ich hätte bei so nem Externspeicherding sowieso kein Treesort sondern Mergesort benutzt, der erscheint mir deutlich besser für so nen fall. Treesort is irgendwie "uncool" find ich.
was die d) war hab ich vergessen, aber die war wieder lösbar, das weiß ich noch.

Verfasst: 27. Sep 2007 15:12
von HolgerF
d) war die Erklärung, warum vergleichsbasierte Suchverfahren mit nlgn begrenzt sind, das war das, was ich im Skript mal überflogen habe, mir aber zu doof war *g* Sowas rächt sich halt doch.

Ansonsten, ja, diese letzte Aufgabe fand ich auch eher unglücklich, da bin ich sehr gespannt, wie die in der Endabrechnung ausfällt. Ich hab zwar abgesehen von der d) auch hier überall was stehen, aber sicherlich nicht alles ganz richtig.

Verfasst: 27. Sep 2007 15:47
von Skylo
also ich wusst garnich was die von mir wollten und als ich wieder am Laptop saß und sah das EINE Folie von Treesort war hab ich echt gedacht:
WAS EINE VERARSCHUNG!

* B-Bäume
* Digitale Suchbäume
* Heaps
* Hashing... alles gelernt und gekonnt!

(Alte Klausuren getestet)

Aber sowas is doch ne reine Schickane das man extra was dran nimmt was kaum behandelt wird, niemals in der Übung und in der Vorlesung nur kurz angesprochen.

Mein Spickzettel kann nich alle blöden Folien beinhalten.

Wenn es daran nun gescheitert sein sollte (obwohl ich glaube das der Rest gut war) dann werd ich mich auf jeden Fall beschweren. Ach auch so find ichs UNFAIR!

GRRR! Ich hab keinen Anfang bekommen und 18 PUNKTE (18%) sind futsch!

Verfasst: 27. Sep 2007 16:23
von banshee
ging mir ähnlich. ich wusste zwar dunkel was Treesort ist, aber irgendwie richtig damit umgehen konnte ich nicht. Dementsprechend maximal 2/18 oder sowas.

Die Klausur hat einfach perfekt die beiden Kapitel getroffen, in denen ich noch Lücken hatte: Sortieren und Geometrische Datenstrukturen. Naja mal gucken, was rauskommt.

Wie sollte das eigentlich mit dem 2d-tree und 2d-trie gehen? Wenn man da eine Linie durch eins der Kreuze gezeichnet hat, war doch das andere auch genau auf der Linie drauf und man konnte es keinem Quadranten zuordnen.

Verfasst: 27. Sep 2007 16:34
von kdw
Was mich so ärgert: Hätte da gestanden "Sortieren sie das irgendwie mit einem Baum ihrer Wahl", ich glaube ich hätte die Aufgabe hinbekommen. Da da aber stand: "Benutzen sie das Verfahren TreeSort, das wir ausführlich in der Vorlesung besprochen haben" (so hab ich das zumindest gelesen) hab ich erst mal ganz lang versucht mich zu erinnern, was wir da gemacht hatten, mir ist nichts eingefallen, und dann hab ichs ganz gelassen.

Gruß,
kdw

P.S.: Ich glaube ja, dass der Veranstalter das deswegen gemacht hat, weil in den Vorlesungen zur guten Klausurvorbereitung wohl der Satz fiel, dass man aus der Breite der Darstellung eines Themas keineswegs auf seine Wichtigkeit für die Klausur schließen könne. Und das war jetzt zur Demonstration.

Verfasst: 27. Sep 2007 17:06
von oren78
Also die Klausur nenne ich einfach mal einen gelungenen Racheakt an all die Studenten (insbesondere Diplomer), die es dazu gebracht haben das der Gallenbacher sein letzten Auftritt an der TUD hatte... gut gemacht ;-)

Verfasst: 27. Sep 2007 18:05
von Rinderhack
naja die Klausur war ok, nur die letzte Aufgabe...

wie kein Gallenbacher mehr nächstes Semester?
d.h. nicht nachschreiben und warten im Zweifelsfall lohnt? ^^

Verfasst: 27. Sep 2007 19:11
von banshee
wird es eigentlich eine mulö zur klausur geben?

weil die aufgabe würde mich wirklich interessieren. schon allein welche datenstruktur man benutzt? (hohler) b-baum?!

oder die priorityQueue hab ich auch nicht hinbekommen. hab zwar schön alle funktionen gemacht und dann die prioritäten mit binärer suche in ein array sortiert aber bei der pop() methode ist mir dann aufgefallen, dass wenn ich das größte element rausnehme ich das ganze array verschieben müsste, was dann ja O(n) wäre.

auf papier zu coden ist sowieso kacke, ich hab mehr durchgestrichenes als text.