Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorithmen und Datenstrukturen (Hashing (Ziel bei Hashverfahren: …

- - - - Spezifikation durch Vor- und Nachbedingugne
      - Algorithmen arbeiten auf Daten, die eingelesen und ausgegeben werden. Ein- und Ausgabe werden mittels einer Datenstruktur repräsentiert.
        
        Beschreibung der Repräsentation der Daten
        
        Operationenen zum Erzeugen, Lesen und Ändern von Datenobjekten
      - Operationen und Datenstrukturen werden schrittweise verfeinert, bis sie elementar genug sind, d.h. ihre Realisierung ist einfach!
    - - nicht in Programmiersprache!
      - Ziel ist es einer anderen Person mitzuteilen wie eine Lösung zu einem gegebenem Problem erreicht werden kann
      - Auf Details kann verzichtet werden, wenn deren Realisierung dem Zielpersonenkreis offensichtlich klar ist.
    - - Ein Programm teilt dem Rechner mit wie die Lösung berechnet werden soll
      - Formulierung in einer Programmiersprache
      - Dokumentation ist essentiell, insbesondere Kernel-Funktionen müssen beschrieben werden
  - - - Elementaroperationen zählen
        
        Zuweisungen, Vergleiche, arithmetische Operationen, Verfolgung einer Objektreferenz oder Arrayzugriff
        
        keine Elementaroperationen sind Schleifen und Prozeduraufrufe
      - Vereinfachungsschritt
        
        nur zeitlich dominante Elementaroperationen zälen
        
        T: M -> N
        M ist die Menge aller möglichen Eingaben
        
        T heißt auch Kostenfunktion
        
        nicht dominante Operationen werden nicht berücksichtigt
      - Vereinfachungsschritt
        
        Komplexitätsklasse erstellen
        K_n, wobei n die Größe der Eingabe ist
        
        statt jeder möglichen Eingabe werden jetzt nur noch jeder Komplexitätsklasse Kosten zugeordnet
        
        man geht von besten und schlechtesten Fällen aus
        
        Die Komplexitätsklasse wird dann in Teilklasse unterteilt und für jede Teilklasse wird eine Wahrscheinlichkeit hinzugefügt
      - Vereinfachungsschritt
        
        Konstante aus T_worst, T_best und T_avg weglassen
      - Die O-Notation
        
        f = O(g) ⇔ ∃n_0 ∈ N, c ∈ R+ so dass ∀n ≥ n_0 gilt f(n) ≤ c ⋅ g(n)
        
        Laufzeit eines rekursiven Algorithmus ist durch die Gleichung gegeben.
        n = 2^k - 1
        
        Θ-Notation
        die Menge aller durch f nach unten und oben beschränkter Funktionen und somit die asymptotische untere und obere Schranke ist.
        
        Ω(f(n):
        die Menge aller durch f nach unten beschränkter Funktionen ist und somit die asymptotische untere Schranke ist.
- - - - doppelte Verkettung durch
        prev und succ möglich
      - binäre Suche bei verketteten Listen ist nicht effizient
        Zugriff auf das mittelere Element -> O(n)
        
        Skip-Listen haben einen Suchaufwand von
        O(log n)
        
        es werden mehree Listen erstellt
        die untereste Liste enthält jedes 2. Element
        
        eine perfekte Skip-Liste benötigt gegenüber einer gewühnlichen Liste nur n zusätzliche Referenzen
        
        bei einer perfekten Skipliste, wird beim Suchdurchlauf die while-Schleife nur einmal ausgeführt.
        Man könnte sie auch durch eine if/then Anweisung ersetzen
        
        Nachteile:
        
        wird z.B. vor dem 1. Element eingefügt, ändert sich die Höhe sämtlicher Knoten
        
        Aufwand beim Einfügen im schlimmsten Fall bei Omega(n)
        
        durchschnittlicher Aufwand beim Einfügen und Löschen
        O(log n)
      - Löschvorgang durch Änderung der Referenz
    - - Move-To-Front
        beim Zugriff auf ein Element wird dieses an den Anfang gespeichert
      - Transpose
        Vertausche ein Element nach erfolgreicher Suche mit seinem Vorgänger
      - Frequency Count
        jedes Element bekommt ein Frequency Attribut welches die Zugriffe zählt
  - - - push, pop, top
- - - - D -> h(K) -> Hashtabelle
        auf Schlüssel werden Hashfunktionen ausgeführt und dann in eine HashTabelle abgelegt
      - Wertebereich des Schlüssels = D
      - h(K') -> h(K) = h(K') wird als Synonym bezeichnet.
        Sollen beide in eine Hashtabelle eingefügt werden, kommt es zu einer Kollision
        
        P(Kollisio) = 1 - P(keine Kollision)
        
        1 - P(1) P(2) .... * P(n)
        
        P(i) = Wahrscheinlichkeit, dass der i-te Datensatz in einem freien Behälter abgebildet wird
        
        P(i) = (m-(i-1)) / m = (m-i+1) / m
        
        P(Kollision) = 1 - (m (m-1) (m-2) ... (m-n+1)) / m²
  - - - direkte Verkettung
        
        jedem Eintrag der Hashtabelle wird der Kopf einer Liste on Elementen zugeordnet
  - - - lineares Sondieren
        
        Ist ein Zielfeld bereits belegt, wird das nächste Feld versucht
        
        Löschen eines Elements geschieht durch Lösch-Vermerk
        ansonsten würde der Suchvorgang ncihtmehr funktionieren
        
        bei der erfolglosen Suche muss die komplette Liste durchsucht werden
      - Double Hashing
        
        Es werden zwei Hashfunktionen gewählt, davon hat eine den i Multiplikator, falls eine Zelle belegt ist, steigt i von 0 auf 1 und zählt somit. I erhöhrt sich bis ein freies Feld gefunden wurde
  - - - Nachteil ist, dass zusätzlich dynamischer Speichplatz allokiert werden muss obwohl Teile der
        
        Nachteil beim verkettete Hashing ist, dass zusätzlich Speicherplatz allokiert werden muss, obwohl nicht alle Felder belegt sind
        
        Hybrides Hashing verkettet Überläufer innerhalb der Hashtabelle
        
        pro Hashadresse wird nur ein "Zeiger" benötigt
        
        bei allen Hashingverfahren ist eine passende Wahl der größe wichtig für die Laufzeit
        ist die Liste zu groß, erhöht sich die Laufzeit
        
        Globale Reorganaisation der Hashverfahren
        
        neue Hashfunktion und Umspeicherung der Datensätze
        
        1 more item...
        
        bei dynmaischen Hashverfahren wird die Größe der Hashtabelle ständig angepasst
        
        mit zunehmender Belegung steigt die Wahrscheinlichkeit an Überlaufdatensätzen
        
        1 more item...