Ferienübungsblatt

Moderator: AI 2

m_flaig
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Ferienübungsblatt

Beitrag von m_flaig »

msssm hat geschrieben: In der Antwort steht aber nur, dass man alles, was zur Lösung benötigt wird, angegeben bekommt.
Daraus kann man hingegen nicht ableiten, dass man gewisse grundlegende Methoden wie Collections.sort() nicht benutzen kann.
Hallo,

sollte es eine Aufgabe geben, in der Sie explizit etwas sortieren müssen, so wäre ein einfacher Aufruf von Collections.sort() etwas dürftig und würde auf keinen Fall zu voller Punktzahl führen.
Ich hoffe, dies beantwortet die Frage nun :-)

VG,
M.Flaig

Goelz_M
Erstie
Erstie
Beiträge: 16
Registriert: 20. Okt 2013 11:38

Re: Ferienübungsblatt

Beitrag von Goelz_M »

Kein Thema :lol: :mrgreen:

msssm
Neuling
Neuling
Beiträge: 3
Registriert: 28. Aug 2014 17:20

Re: Ferienübungsblatt

Beitrag von msssm »

Danke m_flaig,

eine letzte Frage hätte ich dann in dem Fall noch:

Reicht es, wenn man einen Sortieralgorithmus vom Programmcode hinschreiben kann, oder ist es notwendig, alle drei uns bekannten Algorithmen einwandfrei coden zu können?
Ich gehe davon aus, dass man bei allen drei wissen sollte, was nach einer Iteration/ einem Rekursionsschritt ungefähr gemacht wird.

Gruß
msssm

m_flaig
Moderator
Moderator
Beiträge: 272
Registriert: 27. Sep 2009 14:02

Re: Ferienübungsblatt

Beitrag von m_flaig »

Hallo,

Sie sollten den Ablauf / die Vorgehensweise der drei Algorithmen kennen und erklären können.
msssm hat geschrieben: Ich gehe davon aus, dass man bei allen drei wissen sollte, was nach einer Iteration/ einem Rekursionsschritt ungefähr gemacht wird.
Nicht nur ungefähr ;-)
Zur Übung, siehe z.B. Aufgabe 1.1 des Ferienübungsblatts.

Viele Grüße,
Maximilian Flaig

SvenF
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2014 19:45

Re: Ferienübungsblatt

Beitrag von SvenF »

Hallo,

Habe noch eine kleine Frage zur Aufgabe 3
Wenn ich einen "Pfad" reduziere, sodass ich nur noch einen linken also kleineren Nachfolger habe, so muss ich doch den Baum umschreiben, sodass alle Blätter auf gleicher Höhe liegen.

konkret, nach entfernen der 500 muss ich den rechten Teil so umformen, dass das Blatt nicht leer stehen bleibt oder? :roll:

um kurze aufklärung wäre ich dankbar,
Mein Gedanke habe ich mal im Anhang visualisiert.

Mfg
Sven
Dateianhänge
Visualierung
Visualierung
Ferienblatt aufg 3 Baum.jpg (48.48 KiB) 1898 mal betrachtet

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von SophiaLi1 »

Hey,
Du hast das Löschen der 500 schon falsch gemacht. Der Baum nach diesem Vorgang sieht ganz anders aus bzw. kannst du nicht einfach die 500 raus löschen und dir dann überlegen, was du mit einem leeren Blatt machen könntest.

VG

SvenF
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2014 19:45

Re: Ferienübungsblatt

Beitrag von SvenF »

Hmm ok, stimmt, ich muss ja die Knoten erst bearbeiten, sodass mein pointer darauf zu greifen und löschen kann.

Das würde für das Löschen der 500 doch bedeuten, dass das Blatt der 500 erweitert werden muss.
Da die 400 die einzige möglichkeit ist das Blatt zu erweitern, ohne die < und > logik zu zerstören, muss ich den Baum komplett um bauen bzw. rotieren oder?

Konkret würde die 180 die Wurzel position einnehmen und die 200 den kleinsten Wert der Rechten hälfte einnehmen, also den links von 300. Dann kann ich die 350 zur 400 rotieren und mit der 400 die 500 erweitern, um diese nun zu löschen oder ist da immer noch ein Denkfehler drin :oops:
Dateianhänge
ca. so
ca. so
Zwischenablage01.jpg (17.36 KiB) 1885 mal betrachtet

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von SophiaLi1 »

Ich würde dir zuerst einen Merge auf der Wurzel vorschlagen.

Viele Grüße

SvenF
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2014 19:45

Re: Ferienübungsblatt

Beitrag von SvenF »

SophiaLi1 hat geschrieben:Ich würde dir zuerst einen Merge auf der Wurzel vorschlagen.

Viele Grüße
ok, das staucht natürlich meinen Baum, aber ist die Lösung von mir eben falsche oder nur komplizierter? :?:
Weil wenn ich die Wurzel zu einer 100,200,400 Wurzel merge, dann kann ich die 500 doch immer noch nicht einfach weglöschen ohne sie aufzufüllen vorher

Benutzeravatar
SophiaLi1
Moderator
Moderator
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Ferienübungsblatt

Beitrag von SophiaLi1 »

SvenF hat geschrieben: Weil wenn ich die Wurzel zu einer 100,200,400 Wurzel merge, dann kann ich die 500 doch immer noch nicht einfach weglöschen ohne sie aufzufüllen vorher
Das stimmt, danach ist noch ein Zwischenschritt notwendig.
SvenF hat geschrieben: aber ist die Lösung von mir eben falsche oder nur komplizierter? :?:
Kannst du mir bitte deine Lösung kurz und präzise als Satz sagen? Ich kenne im Moment keine einzige Operation (keine einzige, d.h. nicht keine Operationenfolge), mit der man in einem Schritt die 180 in die Wurzel bekommt. Wobei du ja schon das Problem hast, dass du mit dem Pointer gar nicht auf die Wurzel kommst, wenn du keinen Merge ausführst.

TobiTobske
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 15. Jan 2014 20:50

Re: Ferienübungsblatt

Beitrag von TobiTobske »

Hallo, ich habe eine Frage zur Aufgabe 2 (Hashtable).
Wenn ich das richtig sehe, ist die Hashfunktion ja nur bis zum zweiten "Einfügungsversuch" definiert. Mein Problem ist, dass ich die Zahlen 21 und 33 selbst nach dem zweiten Versuch nicht in die Table einfügen kann, weil die Indizes an der Stelle schon belegt sind.
Hab ich mich da irgendwo vertan oder stimmt das? Und was macht man in so einem Fall? Eigentlich bräuchte man ja jetzt einen dritten Versuch, der aber nicht in der Hashfunktion definiert ist...

Danke schonmal für eure Hilfe.

SvenF
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2014 19:45

Re: Ferienübungsblatt

Beitrag von SvenF »

Jap, da hast du recht, ich habe auch eine operationsfolge ausgeführt (ist das eig. legal :?: ) um das Ding so umzubauen, habe mir nochmal das Video und die Folien angeschaut :idea:

Danke für den Tip mit der Wurzel, stand auf der berühmten Leitung :oops: :roll:

Viele GRüße

SvenF
Erstie
Erstie
Beiträge: 11
Registriert: 18. Mai 2014 19:45

Re: Ferienübungsblatt

Beitrag von SvenF »

Hallo TobiTobske,

So wie ich es verstanden habe existiert dafür die Formel die da als erstes Steht.

F(i,nmax,k,)=(F1(nmax,kK)+(i-1)*F2(nmax,k) mod Nmax

i ist die Zahl des Versuches, also i=4 bei dem vierten zuweisungs Versuch. K ist deine Zahl und der Rest ist ja selbst erklärend.

Habe auch teil den 5. Versuch gebraucht, da jenach Anfang manche plätze schon belegt sind. :mrgreen:

Ich habe somit erhalten:
0 1 2 3 4 5 6 7 8 9 10 11 12
68 21 52 29 17 7 73 87 49 11 33

5 und 6 sind leer bei mir

TobiTobske
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 15. Jan 2014 20:50

Re: Ferienübungsblatt

Beitrag von TobiTobske »

Hey, danke für eure Antworten, das ging ja schnell :D
SvenF hat geschrieben: i ist die Zahl des Versuches, also i=4 bei dem vierten zuweisungs Versuch. K ist deine Zahl und der Rest ist ja selbst erklärend.
Aber ist es nicht eigentlich so gedacht, dass es für jeden Versuch i eine Funktion F(i) geben sollte? Sprich, dass die Funktionen sich ein wenig mit den i's ändern, um eine möglichst zufällige Verteilung zu erzielen?

Und nun nochmal zu meiner anderen Frage, die mir noch zum Verständnis sehr helfen würde: Angenommen, in der Klausur komme ich auf den Fall, dass ich auch nach dem zweiten Durchlauf der HashFunktion den Wert nicht einspeichern kann, weil sie eben nur endlich definiert ist. Kann ich dann davon ausgehen, dass ich mich verrechnet habe oder kann sowas in der Praxis durchaus vorkommen und der Wert wird dann einfach nicht gespeichert? (Sowas ließe sich doch durch linear bzw. quadratic probing relativ leicht verhindern?!)
Zuletzt geändert von TobiTobske am 1. Sep 2014 16:46, insgesamt 1-mal geändert.

Benutzeravatar
import java.noob
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 2. Mär 2014 12:28

Re: Ferienübungsblatt

Beitrag von import java.noob »

Hi,

die Reihenfolge der HashTabelle erscheint mir bei dir nicht richtig.

die Funktion kann man ja in eine umschreiben => F(i,Nmax,k) = (k mod Nmax + (i-1) (k+(k mod Nmax))) mod Nmax
d.h. der hintere Teil fällt beim ersten Versuch grundsätzlich weg (1-1 = 0), daher bleibt beim ersten Versuch

F(i,Nmax,k) = (k mod Nmax) mod Nmax

Wenn man jetzt den ersten Wert einsetzt (52) folgt das 52 an nullter Stelle sein muss (52/13 = 4 Rest = 0)/13 = 0 Rest 0

Wenn man das jetzt weiter so macht komme ich auf:

0 1 2 3 4 5 6 7 8 9 10 11 12
52 87 33 29 17 7 73 68 49 11 21

Wäre super wenn mal jemand das bestätigen oder widerlegen kann

Antworten

Zurück zu „AI 2“