Algorithmen und Datenstrukturen 3. Semester

f₁(n) = O(g(n)) und f₂(n) = O(h(n))

Summenformel: f₁(n) + f₂(n) = O( max(g(n), h(n)) )

Produktregel: f₁(n) * f₂(n) = O(g(n)*h(n))

O(1) = konstant

O(log n) = logarithmisch

O(n) = linear

O(n * log n) = überlogarithmisch

O(n²) = quadratisch

O(n³) = kubisch

O(kⁿ) = exponentiell

O(n!) = faktoriell

- Identifizierung des Parameters n, der die Eingabegröße darstellt

- Basisoperation ermitteln

- best, worst und average case für Eingabe der Größe n bestimmen

- Erstellung einer Summenformel für die Ausführungsanzahl der Basisoperation

- Vereinfachung der Summenformel (Regeln und Formeln nutzen)

- relativ schlichter Ansatz, direkt auf Problembeschreibung und Definition der beteiligten Konzepte basierend

- "mit Kanonen auf Spatzen schießen"

Vorteile:

- breites Einsatzfeld

- einfach zu entwerfen

- Vergleichsmaßstab für komplexere Algorithmen

Nachteile:

- liefert selten den effizientesten Algorithmus

- für einige Probleme unakzeptabel langsam

a[0] wird im ersten Durchlauf mit den folgenden Elementen eines Arrays verglichen. Sobald sich ein kleineres Element findet, vergleicht man die folgenden Elemente mit diesem. Hat sich am Ende des Arrays kein kleineres Element gefunden, wird das in einer Variablen gespeicherte Element an die erste Stelle gesetzt.

Das kleinste Element des nächsten Durchlaufs wird dann entsprechend an die zweite Stelle gesetzt - anders ausgedrückt: das im unsortierten Arrayteil gefundene kleinste Element wird immer an die letzte Position des sortierten Arrayteils gesetzt.

Das erste Element des unsortierten Arrayteils wird mit allen folgenden Elementen verglichen und gegebenenfalls getauscht, wenn es größer als eins dieser Elemente sein sollte. Damit steigen die jeweils größten Elemente jedes Durchlaufs wie Blasen zum Ende des Arrays auf.

Suche nach einem Element mit speziellen Eigenschaften aus einer kombinatorischen Menge von Objekten

Methode:

- systematische Generierung aller in Frage kommenden Elemente

- Betrachten aller potentiellen Lösungen nacheinander: Verwerfen ungültiger Lösungen, bisher beste gültige Lösung merken

- Lösung(en) ausgeben

Hoher Zeitaufwand, daher nur für sehr kleine Problemgrößen anwendbar.

Besuch aller Graphen-Knoten:

- kommt man bei einem Knoten mit einem unbesuchten Nachbarn vorbei, geht man zunächst zu diesem weiter - hat der ebenfalls unbesuchte Nachbarn, geht man gleich zu einem von denen, usw.

- backtracking: sind alle Nachbarn eines Knoten besucht, geht man zum Knoten davor zurück

- Nutzung eines Stacks: Ein Knoten wird auf den Stack gepackt, wenn er das erste mal besucht wird und wieder heruntergenommen, sobald man alle Nachbarn von ihm besucht hat

Besuch aller Graphen-Knoten:

- Abarbeitung aller unbesuchten Nachbarn des aktuellen Knotens, anschließend gleiches Verfahren mit den Nachbarn der nun bekannten Nachbar-Knoten

Nutzung einer Queue:

- Einreihung eines Knotens in die Queue, sobald er das erste mal entdeckt wird und Löschen des Knotens aus der Queue, sobald alle seine Nachbarn überprüft wurden

DFS: zwei Knotenordnungen, eine Einfüge-Ordnung auf den Stack und eine Lösch-Ordnung vom Stack

BFS: eine Knotenordnung, da Einfüge- und Lösch-Ordnung in der Queue identisch sind

- Reduzierung des Problems auf ein kleineres, gleichartiges Problem

- Lösen des kleineren Problems durch bottom-up oder top-down-Ansatz

- Erweitern der gefundenen Lösung zur Lösung für das größere Problem

- Reduktion des Problems um Konstante (z.B. Insertionsort)

- Reduktion um konstanten Faktor (z.B. binäre Suche)

- Reduktion um variable Größe (z.B. euklidischer Algorithmus)

bottom up: Man nimmt sich das erste Element eines Arrays. Dieses ist für sich allein schon sortiert, weshalb man anschließend das nächste Element nimmt und dieses entsprechend vor oder hinter dem ersten Element einsortiert. Ebenso wird mit den nächsten Elementen verfahren, bis das gesamte Array sortiert ist.

Directed Acyclic Graph: gerichteter Graph ohne Zyklen, zur Modellierung von Problemen mit Abhängigkeiten/Vorbedingungen

lineare Anordnung der Knoten, sodass die Startknoten aller Kanten vor den jeweiligen Endknoten liegen

topologisches Sortieren bei einem DAG möglich

- bei einer Tiefensuche entspricht umgekehrte Löschreihenfolge vom Stack der topologischen Sortierung

- bei einer Breitensuche ist Einordnungsreihenfolge in Queue eine Lösung

- Voraussetzung: sortiertes Array

- mittlerer Eintrag wird mit Suchschlüssel verglichen, ist der Eintrag kleiner als der Suchschlüssel, wird entsprechend mit dem mittleren Eintrag der rechten Hälfte fortgefahren, andernfalls mit der linken Hälfte

- dies wird gemacht, solange der Schlüssel nicht gefunden wurde bzw. bis keine Halbierung des Suchraums mehr möglich ist

- Teilung des gegebenen Problems in mehrere kleine, gleichartige Problem-Exemplare

- rekursives Lösen der kleineren Problem-Exemplare

- Kombination der Lösungen für die kleinen Problem-Exemplare zur Lösung des großen Problems

- Teilung eines Arrays A in zwei gleichgroße Arrays B und C durch Kopieren der einen Hälfte der Elemente in B und der anderen Hälfte in C

- Rekursion: gleiches Verfahren mit B und C, bis die Arrays nur noch je ein Element enthalten (in der Implementierung ist es auch schon bottom-up möglich)

- Sortieren der Arrays, indem die Elemente von je zwei Arrays miteinander verglichen und entsprechend in ein gemeinsames Array sortiert werden (aus je zwei Arrays mit einem Element wird dann ein Array mit 2 Elementen)

- die nun entstandenen Arrays werden auch jeweils in Paaren sortiert, indem jeweils die vorderen Elemente miteinander verglichen und in der richtigen Sortierung in ein neues Array gespeichert werden

- Wiederholung, bis das ursprüngliche Array sortiert wurde

- kein wahlfreier Zugriff nötig

- gut geeignet zur Sortierung verketteter Listen

- gut geeignet zur Sortierung von Daten auf externen Speichermedien

- Wahl eines Pivotelementes p (Partitionselement), z.B. das erste Element

- Verschiebung der restlichen Elemente, sodass alle größeren Elemente rechts von p stehen und alle kleineren Elemente links von p

- Tausch des Pivotelementes mit dem letzten Element der linken Seite --> Pivotelement hat nun schon richtige Position im Array

- rekursive Bearbeitung der beiden Unterarrays (Wahl neuer Pivotelemente)

- Pivotelement = erstes Element eines Arrays

- Nutzung von 2 Zählvariablen l und r: l durchläuft die Arrayelemente von links (Beginn: Pivotelement) und r von rechts (Beginn: Index außerhalb des Arrays)

- Schleife: l wird solange um 1 erhöht, bis man auf ein Element trifft, das größer gleich dem Pivotelement ist (erst erhöhen, dann Überprüfung)

- Schleife: r wird solange um 1 erniedrigt, bis man auf ein Element trifft, das kleiner gleich dem Pivotelement ist

- die beiden gefundenen Elemente werden getauscht

- Wiederholung der Schritte, bis l größer gleich r ist

- da Schleifenabbruchbedingung erst am Ende der Schleife überprüft wird, findet ein falscher Swap statt --> der wird nach Abbruch der Schleife wieder zurückgetauscht

- das Pivotelement wird dann mit dem Element getauscht, dass sich an der Position von r befindet (äußerstes Element der linken Seite)

a < b^d, dann T(n) e Groß-Theta(n^d)

a = b^d, dann T(n) e Groß-Theta(n^d  * log n)

a > b^d, dann T(n) e Groß-Theta(n^{log_b a})

Ebenso für Groß-O

Vereinfachung: Transformation in einfachere Form desselben Problems

Änderung der Darstellung

Problemreduktion: Transformation in anderen Problemtyp mit bereits bekannten algorithmischen Lösungen

- 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)