Klausur

Hast du die Tree sort Aufgabe gelöst?

Nein
59
87%
Ja
9
13%
 
Abstimmungen insgesamt: 68

pandiz
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 7. Jul 2006 15:32

Klausur

Beitrag 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.

Benutzeravatar
Rinderhack
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 151
Registriert: 17. Okt 2005 20:13
Wohnort: Großostheim
Kontaktdaten:

Beitrag 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!
Zuletzt geändert von Rinderhack am 27. Sep 2007 13:48, insgesamt 1-mal geändert.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag 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

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Beitrag 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?

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

die umfrage ist mist!
ich hab was hingeschrieben, gelöst ist sie aber nicht...

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Re: Klausur

Beitrag 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...
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

jm1035
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 28. Okt 2005 09:26

Beitrag 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.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag 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.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag 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.

Benutzeravatar
Skylo
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 149
Registriert: 7. Nov 2006 20:08
Wohnort: Darmstadt (Woogsviertel)
Kontaktdaten:

Beitrag 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!
Junge, geh kacken! Echt jetzt!

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag 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.

kdw
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 7. Feb 2006 10:46

Beitrag 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.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Beitrag 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 ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Rinderhack
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 151
Registriert: 17. Okt 2005 20:13
Wohnort: Großostheim
Kontaktdaten:

Beitrag 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? ^^

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag 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.

Antworten

Zurück zu „Archiv“