Algorithmen_Skript 3

Front 1

Für das Suchen des kleinsten / größten Elements in einer unsortierten Liste muss einmal...

Back 1

über die gesamte Liste iteriert
werden

Front 2

Um das zweitkleinste / zweitgrößte Elemente zu finden, muss...

Back 2

das kleinste / größte ausgeschlossen und in der restlichen Liste weiter gesucht werden. Hierfür sind insgesamt n+n-1 Iterationen erforderlich.

Front 3

Welcher Komplexität ist die Berechnung des Medians in einer unsortierten Liste?

Back 3

O(n2)

Front 4

Sortiert man zunächst die Liste mit Hilfe des Algorithmus
Sortieren durch Einfügen und bestimmt dann den Median als
mittleres Element, ist die Komplexität...

Back 4

O(n*log(n))

Front 5

Zählen Sie die Suchverfahren auf

Back 5

- Sequenzielle Suche
- Binäre Suche in sortierten Listen
- Fibonaccit-Suche in sortierten Listen
- Exponentielle Suche in sortierten Listen
- Interpolationssuche

Front 6

Was passiert bei Fibonacci-Suche?

Back 6

Bei der Fibonacci-Folge werden iterativ jeweils die beiden
letzten Elemente addiert, um das folgende zu berechnen:
F(0) = 1, F(1) = 1, F(i) = F(i-1) + F(i-2)
- Besteht eine Liste aus N = F(i) (z.B. F(12) = 89) Elementen,
wird zunächst das Element an der Position F(i-1) (F(11) = 55)
betrachtet.
- Ist der gesuchte Wert kleiner, wird an der Stelle F(i-1)-F(i-3)
(F(11)-F(9)=55-21).
- Ist der gesuchte Wert dann größer, wird er mit dem Wert an
der Stelle F(i-2)+F(i-4) (F(10)+(F8) = 34+13 = 47)
verglichen.
- …

Front 7

welche ist die Voraussetztung für die exponentiellen Suche und wie funktioniert diese?

Back 7

Ist die Suchliste sehr lang und kennt man nicht die genaue Größe, so wird der Suchbereich mit exponentiell wachsenden Schritten erweitert, bis man den Bereich festgelegt hat, in dem der gesuchte Wert liegt.

-Man prüft in der ersten Iteration, ob der gesuchte Wert im Bereich der ersten i Positionen liegt. Ist der Suchwert größer
wird geprüft, ober zwischen i+1 und 2i liegt usw.

- Damit wachsen die Interwalle exponentiell an, was dazu führt, dass der Suchbereich vergleichsweise schnell gefunden wird.
Innerhalb des Suchbereichs kann der Suchwert mit der Fibonacci- oder der binären Suche gefunden werden.

Front 8

Wie funktionert die Interpolationssuche?

Back 8

- Ist die Größe der Elemente innerhalb einer Liste ähnlich
verteilt, so ist es nachteilhaft, von der Mitte des Suchbereichs
aus zu suchen, wenn der gesuchte Wert eher klein / groß ist.
- Bei der binären Suche wird jeweils der Bereich vom l-ten bis
zum r-ten Element von der mittleren Position m=l+0,5(r-l)
aus durchsucht.
- Bei der Interpolationssuche wird die 0,5 ersetzt. Die Position,
mit der der gesuchte Wert k verglichen wird ist:
m = l + (k-a(l)) / (a(r)-a(l)) * (r-l)

Front 9

Was passiert beim Hashverfahren?

Back 9

- Bei den bisher betrachteten Listen erfolgte die Speicherung der innerhalb einer Elemente Liste jeweils an einer bestimmten Position.
- Diese Position bestimmte sich zufällig oder es wurde das Element bzw. sein Schlüssel einsortiert.
- Bei einem Hashverfahren wird die Speicherposition aus dem Wert des Elements bzw. seines Schlüssels berechnet.
- Besteht eine Hashtabelle aus m Elementen mit den Indizes
0,..,m-1, so ist eine Funktion zu definieren, die aus einem Element / Schlüssel einen Wert zwischen 0 und m-1 berechnet.

Front 10

Nennen Sie bitte die wesentliche Operationen beim Hashverfahren

Back 10

Suchen , Einfügen und Entfernen

Front 11

Bei den Operationtn Suchen, Einfügen und Entfernen wird davon ausgegangen...

Back 11

- Es wird meist davon usgegangen, dass anfangs die Elemente eingefügt und anschließend weitgehend nur nach Elementen
gesucht wird.
- Es wird angenommen, dass der Entfernen-Operator nur selten
zur Anwendung kommt.
- Daraus ergibt sich, dass das Suchen und Einfügen sehr
effizient erfolgen und beu der Umsetzung nicht das Entfernen
fokussiert werden sollte.

Hint 11

Beispiel

- Gegeben sei eine Hashtabelle mit 37 Elementen (mit den
Indizes 0 bis 36) und eine Liste von Elementen:
L = {812,732,123,328,453,532}
- Mit Hilfe des Modulo-Operators lässt sich eine einfache Hash-
Funktion h bestimmen:
812 Mod 37 = 35
732 Mod 37 = 29
123 Mod 37 = 12
328 Mod 37 = 32
453 Mod 37 = 9
532 Mod 37 = 14

Front 12

Beschreiben Sie die Hashfunktion

Back 12

Grundsätzlich ist es möglich, dass für unterschiedliche
Elemente die Funktion dieselben Ergebnisse liefert:
h(k) = h(k‘)
h(37) = h(74) = 0
- Diese Elemente bezeichnet man als Synonyme.
- Solche Synonyme führen zu Adresskollisionen, da an
derselben Position mehrere Elemente gespeichert werden
sollen.
- Adresskollisionen müssen gesondert behandelt werden.
- Eine Hashfunktion sollte zu möglichst wenigen
Adresskollisionen führen.
- Adresskollisionen sollten möglichst effizient aufgelöst werden
können.

Front 13

Welches Hashverfahren wird als "halb dynamisch" bezeichnet?

Back 13

Ist die Größe der Hashtabelle (=m) fix, so können nicht mehr
als m Elemente kollisionsfrei gespeichert werden. Ein solches Hashverfahren wird als halb dynamisch bezeichnet.

Front 14

Bei den dynamischen Verfahren kann die Größe der Hashtabelle...

Back 14

in Sprüngen verändert werden.

Front 15

Was ist ein Belegungsfaktor?

Back 15

Der Quotient aus Anzahl der belegten Positionen (=n) und
Gesamtgröße der Hashtabelle (=m) wird als Belegunsfaktor
bezeichnet:
Alpha = n / m

Front 16

Wie läuft Bearbeitung von
Adresskollisionen in Hashtabellen ab?

Back 16

- Wird in einer Hashtabelle an der Position i das Element k
gespeichert und soll ein weiteres Element eingefügt werden,
für das gilt h(k‘) = h(k) = i, dann muss k‘, der sogenannte
Überläufer, an einer anderen Position gespeichert werden.
- Eine einfache Möglichkeit ist es, die Überläufer als eine Liste
außerhalb der Hashtabelle zu speichern. Der Ausgangspunkt
der Liste ist jeweils das Element, welches in der Hashtabelle
eingefügt wird. Die Überläufer werden mit ihren jeweiligen
Vorgängern verkettet.
- Beim Ordered Hashing wird die Liste der Überläufer sortiert.
Dies führt zu einem höheren Aufwand beim Einfügen und
Löschen, beschleunigt aber das Suchen.

Hint 16

Front 17

Was passiert bei offenen Hashverfahren?

Back 17

- Bei offenen Hashverfahren werden Überläufer innerhalb der
Hashtabelle gespeichert.
- Ist eine Position belegt, so wird das Element an die nächste
freie Stelle der Hashtabelle gespeichert.
- Für jede Position wird eine eigene Folge, die sogenannte
Sondierungsfolge, definiert, innerhalb derer die nächste freie
Stelle gesucht wird.
- Das Entfernen eines Elements ist dann problematisch, wenn
es zu dem Element nachfolgende Überläufer gibt. Da das zu
löschende Element Ausgangspunkt für die Sondierungsfolge
ist, wird das Element in der Regel nicht wirklich gelöscht,
sondern als gelöscht markiert.

Front 18

Offenes Hashverfahren: Nennen Sie die Operationen

Back 18

-Sondierungsfunktion

-Einfügen eines Elements/Schlüssels k

- Suchen nach Element/Schlüssel k

- Entfernen eines Elements/Schlüssels k

Front 19

Beschreiben Sie die Sondierungsfunktion

Back 19

Sondierungsfunktion:
Sei s(j k) eine j,Funktion von j und k so, dass
(h(k)−s(j,k)) mod m für j = 0,1, . . ., m−1, eine
Sondierungsfolge bildet, d. h. eine Permutation aller
Hashadressen. Es sei stets noch mindestens ein Platz in der
Hashtabelle frei.

Front 20

Beschreiben Sie das Einfügen eines Elements/Schlüssels k

Back 20

Es gilt, dass k nicht schon in der Hashtabelle t vorkommt.
Beginne mit Hashadresse i = h(k).
Solange t[i] belegt ist, mache mit j=0,…,m-1 weiter bei i =
(h(k)−s( j, k)) mod m.
Trage k bei t[i] ein.

Front 21

Beschreiben Sie das Suchen nach Element/Schlüssel k

Back 21

Beginne mit Hashadresse i = h(k).
Solange k nicht in t[i] gespeichert ist und t[i] nicht frei ist,
suche weiter bei i = (h(k)−s( j, k)) mod m, für
aufsteigende Werte von j.
Falls t[i] belegt ist, wurde k gefunden; sonst war die Suche
erfolglos.

Front 22

Beschreiben Sie das Entfernen eines Elements/Schlüssels k

Back 22

Suche nach k.
Verläuft die Suche erfolgreich und ist i die Adresse, an der k
gefunden wird, dann markiere t[i] als entfernt; sonst kommt
k nicht in t vor und kann auch nicht entfernt werden.

Front 23

Wie sieht die Funktion Lineares Sondieren aus?

Back 23

- Sondierungsfunktion: s(j,k) = j
- ergibt Damit sich:
(h(k)−s( j, k)) mod m = (h(k) – j) mod m
- Falls an der Position h(k) ein Element existiert werden mit
aufsteigendem j die Positionen
h(k)−1,h(k)−2,...,0,m−1,...,h(k)+1
durchsucht.

Hint 23

- Größe der Hashtabelle m = 7
- h(k) = k mod 7
- s(j,k) = j
- L = {12, 53, 5, 15, 2, 19}
- h(12) = 5, h(53) =4,
- h(5) = 5  Position 5 ist belegt,
- Gehe zu Position (5–1) mod 7 = 4  Position 4 belegt
- Gehe zu Position (5–2) mod 7 = 3  Position 3 frei
- h(15) = 1, h(2) = 2
- H(19) = 5  Erhöhe j bis freie Stelle gefunden
 j = 5, füge an Position 0 ein.

Front 24

Beschreiben Sie Quadratisches Sondieren

Back 24

- Beim quadratischen Sondieren wird verhindert, dass
Häufungen Hash-Werte die innerhalb der Hash Umgebung der
entsprechenden Positionen mit zu vielen Überläufern gefüllt
wird.
- Die Sondierungsfolge des Elements k lautet:
h(k),h(k)+1,h(k)−1,h(k)+4,h(k)−4,...
- Die Sondierungsfunktion ist dann:
s(j,k) = (j/2)2 (−1)j
- Wenn m eine Primzahl der Form 4i+3 ist, dann ist garantiert,
dass die Sondierungsfolge eine Permutation der
Hashadressen 0 bis m−1 ist.
- m = 19, h(k) = 10 ->
10,11,9,14,6,0,1,7,13,16,4,8,12,2,18,17,3,15,5