AlgoDat

Algorithmus

Definition

  • präzise
  • endlich
  • Elementaroperation
  • Ausführungsorgan
  • Abbildung

Eigenschaften

Abstrahierung/abstrakt

Löst Problemklasse (Parameter)

Statische Finitheit/statisch finit

Beschreibung endlich
(muss)

Dynamische Finitheit/dynamisch finit

Resourcen endlich
(muss)

Terminierung/terminiert

Laufzeit endlich

Determinismus/deterministisch

Gleiche Bedingungen ⇒ Gleicher Ablauf
(Gegenteil ist theoretisches Konstrukt)

Determiniertheit/determiniert

Gleiche Bedingungen ⇒ Gleiches Ergebniss

  • terminiert + deterministisch ⇒ determiniertheit
  • terminiert + nicht deterministisch ⇒ determiniertheit oder nicht determinierend

Effizienz

(Komplexität)

  • Laufzeit
  • Resourcen

Laufzeitanalyse

Elementaroperationen pro Eingabegröße

Bäume

AVL-Bäume

AVL wenn:

  • Binär
  • $bal(T) \in \{-1, 0, 1\}$

$bal(t) = H(t_r) - H(t_l)$ (Rechts vor links)


(Von wiki)

Ein C++ code sagt mehr als tausend Worte.

http://209.237.84.181:7600/index.php/AVL_Trees

http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html

Ebene n -2 +2
Ebene n+1 Linke Seite Rechte Seite (Diese seite muss existieren, da sie ja auch die schwerere ist)
-1 0 +1 -1 0 +1
Aktion Einfach Einfach Doppelt Doppelt Einfach Einfach
Unterschiedliche Vorzeichen
⇒ Doppelrotation

Nach den Regeln im Script rotieren

B-Baum

Einfügen

  • Auf unterster Ebene.

Wenn Blatt voll ⇒ Teilen

  • größe $n \cdot 2+1$ mit neuem Element ⇒ Es gibt ein mittleres Element
  • Mittleres Element bei parent inserten
    • an der Stelle wo der link nach unten ging
    • alter link löschen
    • neue links zum mittleren Element zum linken/rechten neuen Blatt
    • ggf. parent teilen


(Aus den Wiki commons)

B*

m ist ein vielfaches von 3

Optimaler B-Baum

In diesem Beispiel ist das Gewicht des BAuemes 48 (nicht zwangsweise optimal)

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module9/module9.html

http://de.wikipedia.org/wiki/Bellman-Algorithmus

http://de.wikipedia.org/wiki/Gewichteter_bin%C3%A4rer_Suchbaum

  • Von unten nach oben zusamenbauen
  • Ein Baum aus einem element ist bereiz optimal
  • Beim zusammenschlus zweier knoten muss der root so ausprobiert werden das der neue auch wieder optimal ist.

NEU

Monotonieverhalten: Werden zwei Bäume gemerged und sie haben die selbe wurzel, so ist sie auch die Wurzel der vereinigung.

Die Wurzel de gemergen liegt zwischen den Wurzeln der teilbäume (inklusiv ihnen).

Angeblich kann man bei Optimalen Binärbäumen mit warscheinlichkeiten für erfolglose suchen nicht so einfach addieren … nochmal in der VL nachschauen.

Hash

Schlüssel/key – Hash Funktion –> Addresse (m-Stück)

Kardinalität: card(K) = Anzahl möglicher Schlüssel

Addresse = Bucket addresse

Es gibt m buckets

Ein bucket kann b Schlüssel fassen

Perfektes hashing = eine addresse nicht mehr als b mal.

Erwünschte eigenschaften:

  • Surjektivität: Jede speicherzelle soll verwendet werden
  • Gleichmäsige verteilung
  • Effiziente berechnung
  • Randomisierung: Nichtzufällige Schlüssel –> Zufällige Addressen

ORD(c) für Zeichen: a=1, b=2, …

Divisionsmethode b=1

k mod m mit m prim und m > 2 sonst keine Randomisierung.

- Aufeinanderfolgende Schlüssel ⇒ Aufeinanderfolgende Adressen

Middle-Square-Methode b=1

k² und x ziffern aus der mitte des Ergebnisses rausziehen.

- 0-Blöcke am anfang oder am ende ⇒ Nicht gleichmäsig verteilt

Kolisionsstrategie

Offenes Hashverfahren

Ein extra heap um daten zu speichern. Hashtable nur als einstiegspunkt in andere Datenstrukturen.

Direkte Verkettung

Jede adresse = Linked list

Geschlossene Hashverfahren

Alle Daten werden nur in der hash table gespeichert.

Direkte Verkettung mit Verschmelzen
  • Linked list in der hash table.
  • Nächstes freies feld vom ende suchen.
  • Wenn „mein“ feld bereits mit nachvolger eines anderen hashes belegt … egal hänge dich an das ende seiner liste.
Offene Addressierung (rehashing)

Verschiedene Hashfunktionen der reihe nach durchprobieren bis eine eine freie stelle findet.

  • lineares sondieren: $h_i(k) = (h(k) + 1) \bmod m$
    • - Löschen nicht direkt möglich ⇒ „Gelöscht“ Markierung

foo

http://www.dgp.toronto.edu/~jstewart/270/9798s/Laffra/DijkstraApplet.html

Übung 8, prüfen der split bedingung entweder nur nach dem einfügen oder so lange splitten bis es passt (ersteres ist einfacher).

users/skruppy/ext/uni/2/algodat.txt · Zuletzt geändert: 2012/06/26 12:16 von 88.66.198.26