Spickzettel Algorithmen

Jetzt loslegen. Gratis!
oder registrieren mit Ihrer E-Mail-Adresse
Rocket clouds
Spickzettel Algorithmen von Mind Map: Spickzettel Algorithmen

1. 1 Knoten und 2 binären Suchbäumen (linker u. rechter Teilbaum

2. Hinweise

2.1. Formeln

3. 01: Grundlagen

3.1. Algorithmusbegriff

3.1.1. Definition

3.1.2. Eigenschaften

3.2. Analyse

3.2.1. Datenstrukturen

3.2.2. Darstellung von Algorithmen

3.2.3. Abstraktionsebenen

3.3. Korrektheit

3.3.1. Bedingungen

3.3.2. Beweise

3.4. Laufzeit

3.4.1. Abstraktionsschritte

3.4.2. O-Notation

3.4.2.1. Dominierung

3.4.3. Analyse von Schleifen

4. 02: Rekursion

4.1. Prinzip

4.1.1. Abbruchkriterium

4.1.2. divide and conquer

4.2. lineare Rekursion

4.3. Rekurrente Relationen

4.3.1. Berechnung

4.3.1.1. Relation 1

4.3.1.1.1. Gleichung

4.3.1.1.2. Exakte Laufzeit

4.3.1.2. Relation 2

4.3.1.2.1. Gleichung

4.3.1.2.2. Exakte Laufzeit

4.3.1.3. Relation 3

4.3.1.3.1. Gleichung

4.3.1.3.2. Exakte Laufzeit

4.3.1.4. Relation 4

4.3.1.4.1. Gleichung

4.3.1.4.2. Exakte Laufzeit

4.3.1.5. Relation 5

4.3.1.5.1. Gleichung

4.3.1.5.2. Exakte Laufzeit

4.4. Iteration

5. 03: Elementare Sortierverfahren

5.1. Klassifikation

5.1.1. Effizienz

5.1.1.1. Primitive Sortierverfahren

5.1.1.2. Elementare Sortierverfahren

5.1.1.3. Höhere Sortierverfahren

5.1.1.4. Spezialisierte Verfahren

5.1.1.5. Spezialfälle

5.1.2. Stabilität

5.1.2.1. Stabil

5.1.2.2. Instabil

5.1.3. Intern/Extern

5.1.3.1. Intern

5.1.3.2. Extern

5.1.4. Allgemein/Spezialisiert

5.1.4.1. Allgemein

5.1.4.2. Spezialisiert

5.1.5. Speicherverbrauch

5.2. Voraussetzungen

5.2.1. Lineare Suche

5.2.2. Binäre Suche

5.3. Sortierverfahren (Beispiele)

5.3.1. BogoSort

5.3.1.1. Algorithmus

5.3.1.2. Effizienz

5.3.2. BubbleSort

5.3.2.1. Algorithmus

5.3.2.2. Effizienz

5.3.3. SelectionSort

5.3.3.1. Algorithmus

5.3.3.2. Effizienz

5.3.4. InsertionSort

5.3.4.1. Algorithmus

5.3.4.2. Effizienz

5.3.5. MergeSort

5.3.5.1. Algorithmus

5.3.5.2. Effizienz

5.3.6. ShellSort

5.3.6.1. Algorithmus

5.3.6.2. Effizienz

6. 04: Rekursive Sortierverfahren

6.1. allgemeine Vorgehensweise

6.2. Quick-Sort

6.2.1. Idee

6.2.1.1. Devide&Conquer

6.2.2. Pivot-Element

6.2.2.1. Kleinstes

6.2.2.2. Größtes

6.2.2.3. Zufällig

6.2.2.4. Median of Three

6.2.3. Effizienz

6.2.3.1. Best Case

6.2.3.2. Average Case

6.2.3.3. Worst Case

6.2.4. Verbesserungsmöglichkeit

6.2.5. Instabil

6.2.6. Vor-/Nachteile

6.2.7. Implementierung(Java)

6.3. Merge-Sort

6.3.1. Idee

6.3.2. Effizienz

6.3.3. Stabil

6.3.4. Vor-/Nachteile

6.3.5. Algorithmus

6.3.6. Implementierung(Java)

6.4. Optimalitätssatz

6.4.1. Satz

6.4.2. Ausnahmen

7. 05: Elementare Datenstrukturen

7.1. Abstrakter Datentyp

7.1.1. Signatur

7.1.2. Algebra

7.1.2.1. Modelle

7.2. Mathematik

7.2.1. Datentyp (Algebra)

7.2.1.1. Signatur

7.2.1.1.1. Sorten

7.2.1.1.2. Operationen

7.2.1.2. Algebra

7.2.1.2.1. Trägermenge

7.2.1.2.2. Funktionen

7.3. Algorithmik

7.3.1. Datenstruktur

7.3.1.1. Objekte der Trägermengen

7.3.1.2. Operationen

7.4. Programmierung

7.4.1. Typ, Modul, Klasse, ...

7.4.1.1. Beispiel: Modula-2

7.4.1.2. Beispiel: C++

7.4.1.3. Beispiel: Java

7.4.1.4. Konkrete Datentypen

7.4.1.5. Abstrakte Datentypen

7.5. Behälter

7.5.1. Stack

7.5.2. Queue

7.5.3. Verkettete Listen

7.5.3.1. Einfach verkettete Liste

7.5.3.2. Doppelt verkettete Liste

7.5.3.3. Adaptive Listen

7.5.3.4. Geordnete Listen mit Skip Listen

8. 06:Bäume

8.1. Behälter und ihre Merkmale

8.1.1. Array

8.1.2. Menge

8.1.3. Stack

8.1.4. Queue

8.1.5. Baum

8.1.6. Liste

8.2. Hierarchien

8.2.1. Wurzel

8.2.2. Knoten

8.2.3. Kanten

8.2.4. Blatt

8.2.5. (innerer Knoten)

8.3. Begrifflichkeiten

8.3.1. Pfad

8.3.2. Tiefe

8.3.3. Grad

8.4. Binärbäume

8.4.1. Definition

8.4.2. Tiefe

8.4.3. Knoten

8.4.4. Kanten

8.4.5. Implementierung

8.4.5.1. Knotenanzahl(Java)

8.4.6. Operationen

8.4.6.1. isEmpty(B)

8.4.6.2. height(B)

8.4.6.3. contains(B,E)

8.4.7. Vollständiger Baum

8.4.8. (Max)Heap

8.4.8.1. insertHeap(Char c)

8.4.8.2. upHead(Char c)

8.4.8.3. getNext()

8.4.8.4. Aufwand

8.4.8.4.1. insert

8.4.8.4.2. getNext

8.5. Traversierungen

8.5.1. Preorder

8.5.1.1. Implementierung(C)

8.5.2. Inorder

8.5.2.1. Implementierung(C)

8.5.3. Postorder

8.5.3.1. Implementierung(C)

8.5.4. Levelorder (etagenweise)

8.5.4.1. Implementierung(C)

8.6. Suchbäume

8.6.1. Binär

8.6.1.1. Aufbau entweder

8.6.1.1.1. leer

8.6.1.2. Ordnungsrelation über Knoten (Schlüssel)

8.6.1.3. linkter Teilbaum ≤ Wurzel rechter Teilbaum > Wurzel

8.6.1.4. Vergleich von Knoten

8.6.1.4.1. V1: expliziter Schlüssel (keine Duplikate)

8.6.1.4.2. V2: Ordnungsrelation für Datentyp

8.6.1.5. Datenstruktur

8.6.1.5.1. Knoten { int wert; Knoten links; Knoten rechts; }

8.6.1.6. Suche

8.6.1.7. Einfügen

8.6.1.7.1. Step 1: Position im Baum ermitteln

8.6.1.7.2. Step 2: Neuen Knoten anlegen

8.6.1.7.3. Step 3: Neuen Knoten in gefundene Position aus Step 1 einhängen

8.6.1.8. Löschen

8.6.1.8.1. Step 1: Element im Baum suchen

8.6.1.8.2. Step 2: Element löschen

8.6.1.9. Balance

8.6.1.9.1. Balance abhängig von Reinfolge der eingefügten Elemente (worst case sieht Baum aus wie eine Liste)

8.6.1.9.2. Löschen ändert ebenfalls die Form des Baums

8.6.2. Balanciert

8.6.2.1. Binärbaum hat

8.6.2.1.1. max 2^(k-1)-1 Knoten der Tiefe < k

8.6.2.1.2. max 2^k-1 Knoten der Tiefe ≤ k

8.6.2.1.3. d.h. max 2^k-1 Knoten

8.6.2.2. Ein Baum ist balanciert falls alle Schichten bis auf die unterste voll besetzt sind

8.6.2.3. Suche in O(log(N)) da gilt: #Vergleiche ≤ Tiefe des Baumes

8.6.2.4. Problem

8.6.2.4.1. Einfügen und Löschen zerstören Balance

8.6.2.4.2. Ausgleich von Balance aufwendig

8.6.2.5. Lösung

8.6.2.5.1. Schwäche Balance ab

8.6.2.5.2. ggf. Reorganisierung nach Einfügen/Löschen

8.6.2.5.3. Beispiele: AVL- und Rot-Schwarz-Bäume

8.6.3. AVL

8.6.3.1. Adelson-Velski und Landis (1962)

8.6.3.2. Tiefe des linken und rechten Teilbaums unterscheiden sich um max. 1

8.6.3.3. Balance-Zahl b(k) = Tiefe(links(k)) - Tiefe(rechts(k))

8.6.3.4. ∀ Knoten: b(k) ∈ {-1, 0, 1}

8.6.3.5. Zerstörung durch

8.6.3.5.1. Löschen

8.6.3.5.2. Einfügen

8.6.3.6. Wiederherstellung durch Rotation

8.6.3.6.1. Lokale Reorganisation

8.6.3.6.2. Enthält Suchbaum-Ordnung

8.6.3.6.3. Wiederherstellung durch einfache oder doppelte Rotation

8.6.3.7. Analyse

8.6.3.7.1. Satz: Ein AVL-Baum mit N Knoten hat die maximale Tiefe log2N

8.6.3.7.2. Suchen, Einfügen und Löschen in O()

8.6.3.7.3. n(t) = Mindest-Knotenanzahl bei Tiefe t

8.6.3.8. Zusammenfassung

8.6.3.8.1. i.A. besser balanciert als binäre Suchbäume => schnellere Suche

8.6.3.8.2. lokale Reorganisation notwendig

8.6.4. 2-3-4

8.6.4.1. Im gegensatz zu Binärbäumen lassen sich 3-, 4, ..., n-Knoten definieren

8.6.4.1.1. 3-Knoten enthalten zwei Schlüssel und drei Verweise

8.6.4.1.2. 4-Knoten enthalten drei Schlüssel und vier Verweise

8.6.4.1.3. n-Knoten enthalten (n-1) Schlüssel und n Verweise

8.6.5. Rot-Schwarz

8.6.5.1. Motivation

8.6.5.1.1. Verwaltung mehrerer Schlüssel pro Knoten ist aufwendig

8.6.5.1.2. RBT: 2-3-4-Baum als Binärbaum

8.6.5.1.3. Nutzung vorhandener Methoden

8.6.5.1.4. Alternative zu AVL-Bäumen

8.6.5.2. Prinzip

8.6.5.2.1. Knoten haben zusätzliches Feld color (red/black)

8.6.5.3. Regeln

8.6.5.3.1. Jeder Knoten ist entweder rot oder schwarz

8.6.5.3.2. Jeder Blattknoten (Null-Knoten) ist per Definition schwarz

8.6.5.3.3. Die Kinder jedes roten Knotens sind schwarz

8.6.5.3.4. Für jeden Knoten k gilt jeder Pfad von k zu einem Blatt enthält die gleiche Anzahl schwarzer Knoten (vgl. "Schwarzhöhe")

8.6.5.3.5. Die Schwarzhöhe bh(t) eines RBT t ist die Schwarzhöhe seiner Wurzel

8.6.5.4. Zusammenfassung

8.6.5.4.1. Alle Operationen logarithmisch in der Höhe des RBT

8.6.5.4.2. Laufzeitverhalten ähnlich zu AVL-Bäumen

8.6.5.4.3. Implementierung: "R. Sedgewick: Algorithmen"

9. 08: Hashing

9.1. Hash-Funktionen

9.1.1. Auftretende Anomalien

9.1.1.1. Kollisionen

9.1.1.2. Leerstellen

9.1.2. Anforderungen

9.1.3. Typische Hash-Funktionen

9.1.3.1. String

9.1.3.2. Integer

9.1.3.3. Float

9.2. Hashing mit Verkettung

9.2.1. Aufwand

9.3. Hashing mit offener Adressierung

9.3.1. Speichern

9.3.2. Sondierungsfolgen

9.3.3. Löschen

9.3.4. Wahrscheinlichkeit von Kollisionen

9.3.5. Aufwand

9.4. Dynamische Hash-Verfahren

9.4.1. Globale Reorganisation

9.4.2. Dynamisches Hashing

10. 09: Graphen

10.1. Arten

10.1.1. zyklisch

10.1.2. (un)gerichtet

10.1.2.1. Zusammenhang

10.1.2.2. Baum

10.1.2.2.1. Aufspannender Baum

10.1.3. bewertet

10.1.3.1. Wege

10.1.4. Teilgraphen

10.2. Algorithmen

10.2.1. Warshall

10.2.2. Floyd

10.2.3. Dijkstra

10.2.4. Prim

10.2.5. Kruskal

10.2.6. Suchalgorithmen

10.2.6.1. Breitensuche

10.2.6.2. Tiefensuche

10.3. Anwendung

10.3.1. Soziale Netzwerke

10.3.2. Rechnernetze

10.3.3. Routenplanung

10.4. Implementierungsarten

10.4.1. Adjazenzmatrix

10.4.2. Adjazenzlisten-Array

10.4.3. Liste von Listen

10.5. Pfade

11. 10: Kompression

11.1. Lauflängenkodierung

11.1.1. Redundanzen auflösen

11.1.1.1. Schlecht für Text

11.1.1.2. Gut für Binärdaten

11.2. Textkompression

11.2.1. ASCII & Unicode

11.2.2. Morsealphabet

11.2.3. Präfixcodes

11.2.3.1. Huffman Codes

11.2.3.1.1. Algorithmus

11.2.3.1.2. Platzeinsparung

11.2.3.1.3. fester Huffman-Code

11.2.3.1.4. individueller Huffman-Code

11.2.3.1.5. dynamic Huffman-Code

11.3. Kompressionsrate

11.3.1. Kompressionsrate

11.3.2. Platzeinsparung

11.4. Weitere Verfahren

11.4.1. LZW Algorithmus

11.4.2. PKArc/ PKUnArc

11.4.3. WinZip/PKZip...

12. 11: Textsuche

12.1. Zeichenketten

12.1.1. Problemstellung

12.2. Naiver Algorithmus

12.2.1. Pseudocode

12.2.2. Komplexitätbetrachtung

12.2.2.1. best case

12.2.2.2. avg case

12.2.2.3. worst case

12.3. Knuth-Morris-Pratt Algorithmus

12.3.1. Pseudocode

12.3.2. Aufbau des NextArrays

12.3.3. Komplexitätsbetrachtung

12.3.3.1. initNextArray

12.3.3.2. suche

12.4. Boyer-Moore-Sunday Algorithmus

12.4.1. Pseudocode

12.4.2. Aufbau des lastArrays

12.4.3. Komplexitätsbetrachtung

12.4.3.1. best case

12.4.3.2. avg case

12.4.3.3. worst case

12.5. Rabin-Karp Algorithmus

12.5.1. HashBerechnung

12.5.2. Komplexitätsbetrachtung

12.5.2.1. avg case

12.5.2.2. worst case