Fachrat Informatik - Forum

Quoted

Original von Tara
Wie komme ich bei Übung 8 Aufgabe 1 auf die mittleren Zugriffszahlen für erfolgreiche und nicht erfolgreiche Suche? Möglichst einfach bitte.

http://forum.fsinf-hannover.de/thread.ph…=989&boardid=16 kennst Du schon?

Quoted

Original von Tara
Das hilft mir leider auch nicht wirklich weiter. Bin nur ich so blöd?

Sicherlich nur etwas nervös

Ich versuche einmal, Dir das zu erklären:

Gesucht ist die mittlere Anzahl von Zugriffen für die *nicht erfolgreiche Suche*, man sucht also Elemente, die gar nicht in der Tabelle enthalten sind.
Wann kann ich nun sagen, dass ein Element auf gar keinen Fall in der Tabelle sein kann?

1. Im Laufe meiner Suche finde ich eine leere Position. Dann hätte das Element ja dort sein müssen! Also kann es nicht in der Tabelle sein.
2. Im Laufe der Suche kehre ich an meinen Ausgangspunkt zurück. Dann kann ich mit der Suche auch aufhören, weil ich ab da ja wieder dieselbe Reihe von Tabellenplätzen absuchen würde. Also kann das Element nicht in der Tabelle sein.

Nun suche ich also ein solches Element, welches nicht in der Tabelle sein soll. Ich kenne dieses Element aber gar nicht (es kann ja alles mögliche sein). Aus Sicht des *double hashings* (worum es ja hier geht) ist allerdings nur interessant, welche Hashwerte meine Hashfunktionen h1 und h2 liefern, das eigentliche Element ist nicht so wichtig.
Ich überlege also, welche Werte h1 und h2 so liefern können: Bei einer Tabelle der Länge 7 ist ja
h1 in {0,...,6} und
h2 in {1,...,6}
Ich nehme nun an, dass jede *Kombination* von Werten
(h1,h2) gleich wahrscheinlich auftritt (bei genügend vielen Elementen ist das keine unvernünftige Annahme). Ich untersuche jede Kombination, indem ich die Anzahl der Tabellenzugriffe zähle, bis entweder Fall 1 oder 2 auftreten. Das ist eine Menge Arbeit, schließlich haben wir es hier mit 7*6=42 Kombinationen zu tun, also erledigt das am besten ein Programm. (In einer Klausur wäre die Tabelle natürlich kleiner oder einfacher zu untersuchen.)

Schließlich teile ich die aufsummierte Anzahl durch die Gesamtzahl der Kombinationen (hier 42), wir hatten ja Gleichverteilung angenommen.

Ich hoffe, das hilft Dir weiter.

Grüße,

Niklas

Hab auch noch ein Problem:

Wenn ich einen gerichteten Graphen habe, z.B.:

Knoten: {u, v, w, x, y, z}
Kanten: (u,x), (u,v), (x,v), (v,y), (y,z), (w,z), (w,y), (x,v)
und soll nun einen Tiefendurchlauf von u aus machen, bekomme ich:
u, v, y, x, z - aber was ist mit w??? Es führt kein Weg zu w? Wie wird dieser Knoten notiert? Kann aus dem entsprechenden Algorithmus nicht erkennen, was in so einem Fall passiert…
Kann mir jemand helfen?

Danke!

Quoted

Original von BlaueMotte
Wenn ich einen gerichteten Graphen habe, z.B.:

Knoten: {u, v, w, x, y, z}
Kanten: (u,x), (u,v), (x,v), (v,y), (y,z), (w,z), (w,y), (x,v)
und soll nun einen Tiefendurchlauf von u aus machen, bekomme ich:
u, v, y, x, z - aber was ist mit w??? Es führt kein Weg zu w? Wie wird dieser Knoten notiert? Kann aus dem entsprechenden Algorithmus nicht erkennen, was in so einem Fall passiert…

Auf Seite 116 im Skript steht etwas zu diesem Fall:

"Gegeben sei ein gerichteter Graph G = (V, E). Beide Algorithmen gehen von einem Startknoten s aus und besuchen alle von s erreichbaren Knoten. Sind dann noch nicht alle Knoten in V besucht worden, wird ein neuer, noch nicht besuchter Startknoten gewählt und das Verfahren beginnt von vorne."

Danke, Joachim!!!

Genau nach so einem Satz habe ich gesucht. Muss ihn wohl überlesen haben...

Quoted

Original von Tara
Mit dem Radixsort komm ich gar nicht klar
Also da sind 2 Zeiger die von Außen nach Innen wandern, ja?
Wenn ich z.B. hab:
001 100 110 010 000
Dann beginn ich bei dem 2. Bit (von vorne?) und vertausche:
- 001 100 000 010 110
Dann nach dem ersten Bit:
-001 010 000 100 110
Das ist ja nun nicht wirklich sortiert.

"Die Bits sind von Rechts nach Links numeriert". Eine 6 Bit Zahl hat ganz links das 5te Bit, welches am "schwersten wiegt", ganz rechts das 0te.

Es laufen 2 Zeiger von links und von rechts aufeinander zu und es wird anfangs nach dem linkesten Bit sortiert. Also wird getauscht, wenn der linke Zeiger einen Eintrag mit gesetztem Bit (1) und der rechte entsprechend einen Eintrag mit einem gelöschten Bit (0) findet. Danach entsprechend weiter bis die Zeiger sich treffen.

Du hast in den einzelnen Mengen, über die die Zeiger laufen also nach jedem Durchlauf alle Einträge, bei denen das untersuchte Bit gelöscht ist links und alle Einträge, bei denen das untersuchte Bit gesetzt ist rechts stehen.
Dann macht man auf den beiden Mengen und dem nächsten Bit weiter.

Quoted

Original von Tara
Also da sind 2 Zeiger die von Außen nach Innen wandern, ja?
Wenn ich z.B. hab:
001 100 110 010 000
Dann beginn ich bei dem 2. Bit (von vorne?) und vertausche:
- 001 100 000 010 110
Dann nach dem ersten Bit:
-001 010 000 100 110
Das ist ja nun nicht wirklich sortiert.

Die "Zwei-Zeiger-Methode" wird in einer ähnlichen Form auch bei Quicksort verwendet. Vielleicht hilft Dir diese Beschreibung:

http://www.wikiservice.at/dse/wiki.cgi?QuickSort
(Unterpunkt "Partitionierung" -- die roten Elemente wären dann z. B. die Einsen und die blauen die Nullen, das Einsetzen eines Pivots am Ende entfällt bei Radixsort natürlich)

Ich habe auch mal eine Frage:

Ich habe hier die Kopie der Aufgaben, die in der letzten Übungswoche besprochen wurden, liegen und erkenne schwach (schlechte Qualität), dass es eine zweite Aufgabe gibt, die bei uns nicht besprochen wurde.

Aufgabenstellung laut Zettel:

ADT Liste, rotate, einfach verkettet, Modifikation für O(1)

Wäre nett, wenn mir einer erläutern könnte, was es damit auf sich hat, sprich:
Was ist gefragt (habe nur eine Vermutung, vielleicht fehlt es bei der aber an etwas) und wie wird gelöst?

Quoted

by the Minister: Wäre nett, wenn mir einer erläutern könnte, was es damit auf sich hat, sprich:

Hi, die Aufgabe war:

ADT Liste, implementiert als einfach Verkettung. Schreiben Sie eine Methode rotate, die das erste Element als letzes Element anordnet, das zweite als erstes, .. usw..

Lösung:
void rotate()
{
position p=first();
Element e = getElement(p);
remove(p);
p=last();
add Element(e,p)
}


Und: wer sich noch was zu CountingSort anschauen möchte, sollte sich dieses Applet man ansehen: http://www.cs.cf.ac.uk/user/C.L.Mumford/…untingSort.html

Gemach!

Versteh ich nicht ganz.
Einfache Verkettung = Lineare Verkettung?

Dann würd ich doch den Zeiger vom ersten ins null lenken und den vom letzten Element auf das erste zeigen lassen ?!?
Und das dann immer in der Runde.
Oder wie Du, stimmt, erstes Objekt "tempen", "deleten" und hinten dran"inserten".

Bei Dir müsste es aber heissen "add Element (e,p)"

Quoted

Bei Dir müsste es aber heissen "add Element (e,p)"

Jo, war ein Tippfehler. Thx. Habs oben auch korrigiert.

Quoted

Dann würd ich doch den Zeiger vom ersten ins null lenken und den vom letzten Element auf das erste zeigen lassen ?!?

Genau, kann man so auch machen. Wurde in unserer Übung auch kurz angesprochen, afair.
So wäre das dann:

{
last --> next = frist;
first = first --> next;
}

Jedoch werden in der Lsg die ich gepostet habe, halt die Methoden des ADT Liste verwendet.

Quoted

Original von cowhen
Und: wer sich noch was zu CountingSort anschauen möchte, sollte sich dieses Applet man ansehen: http://www.cs.cf.ac.uk/user/C.L.Mumford/…untingSort.html

das hier ist auch ganz lustig:
http://www.informatik.fh-hamburg.de/~owsnicki/sort/sort.html

ich habe da noch eine frage: welche sortierverfahren wurden in der vorlesung behandeln? könnte die mal jemand kurz aufzählen?

danke.

Ich habe jetzt nach dem Klausurstress meine alte Pascal Programme aus den Schulzeiten rausgefunden und siehe da, haben wir in der Schule Buble-Sort, Sortieren durch Einfügen und Auswählen programmiert. Es ist ganz lustig zu sehen, wie diese Verfahren, zumindestens Anschaulich, arbeiten. Hier ist der Link wo man sowohl den Quelltext als auch eine Ausführbare Datei herunterladen kann. Viel Spaß damit!!!
mfg
MAX