Algorithmen und Datenstrukturen 3. Semester

- Medianbestimmung

- Unterschiedlichkeit der Elemente

- Suche in Listen

Blatt: direktes Löschen

Knoten mit einem Nachfolger: Nachfolger mit Vorgänger verbinden, Schlüssel löschen

Knoten mit zwei Nachfolgern: Schlüssel aus Knoten löschen, Schlüssel des Ordnungsnachfolgers / -vorgängers in Knoten eintragen und dessen Knoten löschen (Ordnungsvorgänger: nächstkleinster Wert, Knoten am rechten Ast der linken Seite - Ordnungsnachfolger: nächstgrößter Wert, Knoten am linken Ast der rechten Seite)

Blatt: direktes Löschen

Knoten mit einem Nachfolger: Nachfolger mit Vorgänger verbinden, Schlüssel löschen

Knoten mit zwei Nachfolgern: Schlüssel aus Knoten löschen, Schlüssel des Ordnungsnachfolgers / -vorgängers in Knoten eintragen und dessen Knoten löschen (Ordnungsvorgänger: nächstkleinster Wert, Knoten am rechten Ast der linken Seite - Ordnungsnachfolger: nächstgrößter Wert, Knoten am linken Ast der rechten Seite)

AVL-Bäume, Rot-Schwarz-Bäume --> Rebalancieren eines Baumes

2-3-Bäume / 2-3-4-Bäume, B-Bäume --> mehr als einen Schlüssel pro Knoten erlauben

Höhe des linken Unterbaumes - Höhe des rechten Unterbaumes <= 1 (Betrag)

- Rotation des Unterbaumes mit dem unbalancierten Knoten als Wurzel, der den eingefügten Blatt am nächsten ist

- v = unterster unausbalancierter Knoten (Knoten, bei dem Differenz größer 1 steht)

- Linksrotation, wenn neues Element im rechten Teilbaum von v eingefügt wurde

- Rechtsrotation, wenn neues Element im linken Teilbaum von v eingefügt wurde

- Links-Rechts-Rotation, wenn neues Element im "mittleren" Teilbaum von v eingefügt wurde, also im rechten Ast des linken Teilbaumes (analog Rechts-Links-Rotation)

- Suchbaum

- besitzt 2 oder 3 Kinder je Knoten (bei 3 Kinder sind 2 Schlüssel im Knoten, Schlüssel des mittleren Astes befinden sich zwischen den beiden Schlüsselwerten)

- vollständig höhenbalanciert (alle Blätter auf einer Ebene)

- "2-3-Bäume wachsen an der Wurzel" --> Wurzel wird sozusagen nach oben gedrückt

- Einfügen immer in bereits bestehende Blätter

- sobald Blatt drei Schlüssel enthält, wird mittlerer Schlüssel nach oben gedrückt und die beiden anderen Schlüssel werden in zwei einzelne Knoten aufgespalten und erhalten mittleres Element als Elternknoten

- Binärbaum mit einem Schlüssel pro Knoten

- Vollständigkeit: alle Ebenen vollständig gefüllt, nur in der letzten Ebene dürfen Knoten fehlen (dann aber nur rechts, es wird immer von links aufgefüllt)

- Teilgeordnet: Jeder Knotenschlüssel ist bei einem Max-Heap größer gleich den Schlüsseln seiner Kinder, bei einem Min-Heap entsprechend kleiner gleich (Schlüssel von oben nach unten sortiert, nicht von links nach rechts)

h = log₂ n (abgerundet)

linkes Kind eines Schlüssels an Position j: Position 2j

rechtes Kind von j: 2j + 1

Elternknoten von j: Position j/2 (abgerundet)

Elternknoten belegen die ersten n/2 (abgerundet) Positionen

- Wahl des letzten Elternknotens (unten rechts)

- Heap-Eigenschaft für Teilbaum ab diesem Elternknoten herstellen

- Wiederholung des Schrittes für die vorherigen Elternknoten

Aufwand für Transformation + Aufwand zur Lösung des anderen Problems < Aufwand zur Lösung des originalen Problems

Nutzung von zusätzlichem Speicherplatz zur Verbesserung der Laufzeit

- Eingabeerweiterung: Vorverarbeitung der Eingabe zur Ermittlung von Informationen, mit denen das Problem später effizienter gelöst werden kann

- Vorstrukturierung: Vorverarbeitung der Eingabe, um später schneller auf die Eingabeelemente zugreifen zu können

Es wird für jedes Arrayelement gezählt, wie viele Elemente kleiner sind als das jeweilige Element. Die ermittelte Anzahl wird in ein zweites Array geschrieben, sodass die Position eines Elementes mit der Position der ermittelten Anzahl übereinstimmt. Mittels der Anzahl wird das Array dann aufsteigend sortiert. Das kleinste Element hat 0 Elemente, die kleiner sind und wird damit an Arrayindex 0 gesetzt. Das zweitkleinste Elemente hat ein kleineres Element und kommt damit an den Index 1.

Beim Zeichenketten-Vergleich wird jedes Zeichen des Suchmusters mit einem Zeichen des Textes verglichen. Sobald ein Dismatch auftritt, wird das Suchmuster verschoben und das Vergleichen wird erneut begonnen. Der Horspool-Algorithmus verschiebt das Suchmuster jedoch nicht jedes Mal um 1. Wenn der Dismatch durch ein Zeichen im Text auftrat, der im Suchmuster gar nicht auftritt, kann das Suchmuster gleich um die Suchmusterlänge verschoben werden, da das Zeichen sonst immer zu einem Dismatch führen würde. Existiert das Zeichen im Suchmuster, wird dieses um die am weitesten rechts befindliche Position des Zeichens im Suchmuster verschoben. Dafür wird zu Beginn eine Shift-Tabelle angelegt, in der für jedes Zeichen des Suchmusters die Position des ersten Vorkommens von rechts angegeben wird.

Abbildung der n Schlüssel einer potenziell sehr großen Schlüsselmenge K mittels einer Hashfunktion auf eine Hashtabelle der Größe m

Bsp: h(k) = k mod m

Es ist also möglich, dass 2 Schlüssel auf die gleiche Position abgebildet werden (Kollision).

Open Hashing:

- mehrere Schlüssel pro Zelle in der Hashtabelle

- Zelle = Kopf einer verketteten Liste aller auf sie abgebildeten Schlüssel

Closed Hashing:

- nur ein Schlüssel pro Zelle möglich, daher dürfen nicht mehr Schlüssel als Zellen existieren

- Suchen einer anderen Zelle bei Kollision (verschiedene Verfahren möglich, z.B. lineares Sondieren - nächste Zelle testen)

- Baum der Ordnung m >= 2

- Wurzel = Blatt oder Knoten mit 2 bis m Kindern

- alle anderen Knoten: zwischen m/2 (aufgerundet) und m Kinder

- vollständig balanciert

B-Bäume sind besonders geeignet für die Suche auf Datenbeständen, die aufgrund ihrer Größe auf externen Speichermedien abgelegt werden müssen. Bei B-Bäumen werden pro Knoten relativ viele Schlüssel gespeichert, da dadurch die Knotenzahl und die Höhe des Baums stark sinken. Eine geringere Höhe bedeutet weniger (zeitlich sehr teure) Zugriffe auf externe Speichermedien. Da von externen Speichern typischerweise blockweise gelesen wird, erhöht die größere Schlüsselzahl pro Knoten nicht die Anzahl der notwendigen Zugriffe, solange ein Knoten noch in einen Block passt. Die Ordnung eines B-Baums (und damit die maximale Schlüsselzahl) wird daher meist so festgelegt, dass ein Block möglichst vollständig gefüllt wird.

Problemklasse --> Lösungsidee --> (Formalisierung/Beweis) --> Algorithmus --> (Programmierung) --> Programm --> (Compilierung/Interpretation) --> Computer

- finit (statisch): Beschreibung des Algorithmus besitzt endliche Länge

- finit (dynamisch): zu jedem Zeitpunkt nur endlich viel Speicher benötigt

- effektiv: jeder Algorithmusschritt ist tatsächlich ausführbar

- reproduzierbar: unabhängig von einer speziellen Implementierung

- terminierend: nach endlich vielen Schritten wird für jede Eingabe ein Ergebnis geliefert

- korrekt

- deterministisch: Verfahrensablauf zu jedem Zeitpunkt fest vorgeschrieben

- determiniert: gleiche Eingaben führen immer zum gleichen Ergebnis

- effizient: sparsamer Umgang mit Ressourcen

1.) Problem verstehen

2.) Entscheidung über Computer-Ressourcen, exakte oder Näherungslösung, Algorithmen-Design-Technik

3.) Algorithmusentwurf

4.) Beweis der Korrektheit (von hier möglicherweise Zurückgehen zu 2. oder 3. erforderlich)

5.) Analyse des Algorithmus' (von hier möglicherweise Zurückgehen zu 2. oder 3. erforderlich)

6.) Implementierung des Algorithmus

- Brute Force

- Decrease-and-Conquer

- Divide-and-Conquer

- Transform-and-Conquer

- Space and Time Tradeoffs

- Dynamic Programming

- Greedy Technique

- Iterative Improvement

- Backtracking

- Branch and Bound

Organisationsform von Daten im Speicher zur Vereinfachung und zur Steigerung der Effizienz von Algorithmen

Menge von Werten und zugeordneten Operationen, die unabhängig von ihrer Implementierung spezifiziert sind.

Vorteile:

- größere Verständlichkeit durch Abstraktion

- Austauschbarkeit der Implementierungen

- Wiederverwendbarkeit

Name

Schnittstelle (Operation 1, Operation 2, ...)

Invariante: relevante, stets (während der Durchführung der Operation darf sie kurz verletzt werden) geltende Eigenschaft, z.B. Sortiertheit der Elemente

- Erzeugung (eines leeren Exemplars)

- Sondierende Operationen (Sondierung des Zustands, ohne ihn zu verändern)

- Verändernde Operationen

- Erschaffende Operationen (Erschaffung eines weiteren Exemplars aus einem oder mehreren bestehenden Exemplaren)

- Zerstörung (Speicherfreigabe)

Vorbedingung: Eigenschaft, die vor Ausführung der Operation gelten muss

Nachbedingung: Eigenschaft, die nach Ausführung der Operation zugesichert wird

Zustand einer Datenstruktur: zur Beschreibung der Wirkung einer Operation

- Linare Datenstrukturen: Arrays, einfach und doppelt verkettete Listen

- Graphen: als Adjazenzmatrizen oder -listen

- Bäume: Binärbäume, n-äre Bäume

- Sequenz von n Elementen des gleichen Datentyps

- Ablage in zusammenhängenden Hauptspeicherbereichen

- Zugriff auf Elemente über Index

- Hauptvorteil: Elementzugriff in konstanter Zeit

- Hauptnachteil: feste Größe

- Folge von beliebig vielen Listenelementen bestehend aus Datenfeld und Next-Zeiger

- Ablage der Elemente verteilt im Hauptspeicher

- Zugriff auf Liste erfolgt über Head-Zeiger

- Listenende durch leeren Next-Zeiger (null) markiert

- Hauptvorteil: flexibles Wachsen (oder Schrumpfen)

- Hauptnachteil: größerer Speicherbedarf durch Zeiger, langsamer

- wie einfach verkettete Liste, zusätzlich noch Zeiger auf vorheriges Listenelement

- Prev-Zeiger des ersten Elementes ist null

- Hauptvorteil: teilweise effizientere Operationen als einfach verkettete Liste

- Hauptnachteil: noch größerer Speicherbedarf als einfach verkettete Liste

informell: Punkte (Knoten) in der Ebene, die durch Liniensegmente (Kanten) verbunden sein können.

formell: Graph G (V,E) mit V= {v₁, v₂, ... , v_n} als nicht-leere, endliche Menge von Knoten und E= {e₁, e₂, ... , e_n} als endliche Menge von Kanten der Form (v_i, v_j)

ungerichtete Kanten = Linien, kein Unterschied zwischen Kante (u,v) und (v,u) - u und v sind benachbart (adjazent)

gerichtete Kanten = Pfeile, Unterschied zwischen (u,v) und (v,u) - für (u,v) ist v adjezent zu u

Schleife: Kante von einem Knoten auf sich selbst, nach Definition erlaubt

Mehrfachkanten: mehrere Kanten zwischen denselben Knoten, nach Definition nicht erlaubt, falls benötigt --> Erweiterung zu Multigraphen

vollständiger Graph: alle erlaubten Kanten vorhanden

dichter Graph: nur wenige fehlende Kanten

lichter Graph: nur wenige Kanten vorhanden

- boolesche n x n Matrix

- Wert an (i,j) besagt, ob Kante von i nach j existiert

- jeder Knoten besitzt eine verkettete Liste

- Listenelemente sind die zum Knoten adjazenten Knoten