zusammenfassung-dsal-datenstrukturen-algorithmen.pdf

lOMoARcPSD|25609453 Zusammenfassung DSAL Datenstrukturen Algorithmen Algorithmen und Datenstrukturen (Rheinisch-Westfälische Technische Hochschule Aachen) Scanne, um auf Studo...

lOMoARcPSD|25609453 Zusammenfassung DSAL Datenstrukturen Algorithmen Algorithmen und Datenstrukturen (Rheinisch-Westfälische Technische Hochschule Aachen) Scanne, um auf Studocu zu öffnen Studocu wird von keiner Universität gesponsert oder unterstützt. Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 DSAL Komplexität von Algorithmen Laufzeit ist keine Zahl sondern eine Funktion N ⇒ N O­Notation g = O(f ) ≈ g wächst langsammer als f g = Ω(f ) ≈ g wächst schneller als f g = Θ(f ) ≈ g wächst so schnell als f Falls f (n) = 0 für endliche n: ∣g(n)∣ O(f ) = g : N ⇒ R∣ lim sup ∣f (n)∣ existiert n→∞ ∣g(n)∣ Ω(f ) = g : N ⇒ R∣ lim sup ∣f (n)∣ ≠0 n→∞ ∣g(n)∣ ∣g(n)∣ Θ(f ) = g : N ⇒ R∣ lim sup ∣f (n)∣ ≠ 0 und ∣f (n)∣ existiert n→∞ Weitere Regeln: Konstanten kann man weglassen O(f (n)) + O(g(n)) = 0(∣f (n)∣ + ∣g(n)∣) 0(f (n) + g(n)) = O(f (n)) + O(g(n)) O(f (n))O(g(n)) = O(f (n)g(n)) O(f (n)g(n)) = f (n)O(g(n)) ∑nk=1 O(f (k)) = O(nf (n)) falls ∣f (n)∣ monoton steigt f (O(1)) = O(1) Listen Operations Laufzeit append() Θ(1) delete()* Θ(1) delete() Θ(n) find() Θ(n) insert() Θ(1n direktes Löschen eines Knotens, nicht über Schlüssel Suchen und Sortieren Suche liniare Suche Im Mittel (n + 1)/2 Vergleiche Sentinel­Technik Sentinel = Wächter. Man hängt am Ende der Liste das gesuchte Element. Dies ist dafür da um zu verhindern, dass immer geschaut werden muss, ob man am Ende der Liste angekommen ist. Somit kann man die if durch eine whileschleife ersetzten und hat mehr speed. Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 binäre Suche Im Mittel log(n) + O(1) Vergleiche mit einer Laufzeit von O(log n). Bäume binäre Suchbäume Äußere Knoten extern, innere Knoten intern. Die mittlere Höhe beträgt O(log n). Einfügen, Löschen und Suchen benötigen bei einem Suchbaum Höhe h O(h) Zeit. Löschen Blatt, kann durch Zeigerverbiegen gelöscht werden Der Knoten hat kein linkes Kind, durch kopieren oder Zeigerverbiegen Der Knoten ein ein linkes Kind, finde den größten Knoten im linken Unterbaum, kopiere seinen Inhalt an die Stelle des zu löschenende Knotens optimale Suchbäume w und e Tabellen AVL­Bäume Die Höhen des rechten und linken Unterbaums jedes Knotens unterscheiden sich höchstens um 1. Zudem ist die Höhe zwischen Fh und 2h − 1 viele Knoten. Einfügen und löschen in einem AVL­Baum benötigt O(log n) Schritte. Treaps Suchbaumeigenschaft: alle Knoten links kleiner als Wurzel alle Knoten rechts größer als Wurzel Heapeigenschaft: Alle Knoten in beiden Teilbäumen größer als Wurzel Jeder Knoten Jeder Knoten hat einen Schlüssel und eine Priorität. Gibt es n Schlüssel mit paarweise verschiedenen Prioritäten, so gibt es genau einen Treap. Löschen: Der Knoten wird runterrotiert, bis es ein Blatt ist und dann entfernt. Einfügen: Knoten als Blatt einfügen und zur richtigen Position rotieren. Einfügen, Suchen und Löschen braucht im Mittel O(log n) Schritte, falls die Prioritäten im ausreichend großen Bereich liegen. Treaps sind sehr schnell. Splay­Bäume Nur amortisiert effizient. Um einen Knoten hochzusplayen gibt es zig, zag, zig­zig, zig­zag, zag­zig und zag­zag. zick: Rotation um Rechts zack: Rotation um Links Suchen: Normale suche, die Suche Endet im Knoten x mit Schlüssel k oder in x− oder x+. Der gefundene Knoten wird dan hochgesplayd und schau nach, ob k in der Wurzel ist. Einfügen: Normales Einfügen und dann den neue nKnoten hochzusplayen. Löschen: Suche nach k und schaue ob es in der Wurzel ist. Den größten Knoten im linken Teilbaum hochsplayen und k löschen Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 Alle Operationen sind amotisiert O(n log n) Amotisierte Analyse Eine Datenstruktur wird durch Operationen verändert. Das Problem ist, wenn die Zeit t dafür stark schwakt. Dafür erstellt man eine Potentialfunktion Φ (a,b) ­ Bäume Jeder Knoten hat höchsten b Kinder, jeder Knoten außer der Wurzel hat mindestens a Kinder. Außerdem haben alle Blätter die gleiche Tiefe. Als Suchhilfe hat jeder Knoten mit m Kindern m − 1 Schlüssel. Es gilt: a ≥ 2 und b ≥ 2a − 1. Einfügen: Neues Blat tan richtiger Stelle einfügen, wenn der Elternknoten mehr als b Kinder hat gibt es ein Problem, dann aufteilen in Knoten mit ⌊(b + 1)/2⌋ und ⌈(b + 1)/2⌉ Kindern. Das könnte den Vater überfüllen. Löschen: Blatt mit Schlüssel entfernen, wenn Elternknoten weniger als a Kinder hat, dann Knoten vereinigen. Dieser muss dann wieder geteilt werden. Tries In vergleichsbasierten Suchbäumen wird nicht in die Schlüssel geschaut. Ein Tree entspricht die ite Verzweigung dem iten Zeichen des Schlüssels, wie z.B. AAB, AABAAB, AABB, ABA, ABB. Hashing Wir möchte gerne eine injektive Funktion haben, was jedoch nicht so einfach möglich ist. Wir verwenden dshalb einfache Hashfunktionen, die in der Praxis genau so gut sind wie die unversellen. Es muss darauf geachtet werden, dass die Schlüssel möglichst gleichmäßig und unabhänig voneinander verteilt werden. Die Hashtabelle hat m Positionen. Jede Position besteht aus einer verketteten Liste. Die Operationen sind zwar einfach, jedoch wird viel Speicher verschwendet. Skip­Lists Schlüssel nach größe in vielen Listen geometrisch verteilt. Man sucht von oben nach unten. Operationen: O(log n), SPeicherverbraucht O(n) Sortierte Sortiertes Binärer AVL­ Splay­ Skip­ Min­ Liste Array Treap Hashtable Liste Array Suchbaum Baum Tree Liste Heap Random N N N N N N N J J J N Einfügen 1 n 1 n n log n log n log n log n 1 n Suchen n n n log n n log n log n log n log n 1 n Löschen n n n n n log n log n log n log n 1 n Minimum n 1 n 1 n log n log n log n 1 n 1 Maximum n 1 n 1 n log n log n log n log n n n Sort. n log n log n log n n n n n n n n log n Aus. n n n Sortieren Insertions Sort es werden wiederholt Elemente in ein bereits sortiertes Teilaaray eingefügt. Laufzeit O(n2 ) Mergesort Divide­and­Conquer. Jedes Array wird aufgeteilt, so lange bis es sortiert werden kann, also nur noch zwei Elemente zum Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 vergleichen. Es ist nicht in­place aber stabil Quicksort Divide­and­Conquer. Wir wählen ein Pivot­Element p und teilen in drei Teile: Alle Schlüssel kleiner als p p Alle Schlüssel größer als p Sow wird dann rekursiv Teil 1 un 3 sortiert. Die Laufzeit ist sehr gut, der worst­case jedoch nicht. Heapsort Ein heap ist ein Binärbaum, dessen Kinder größer als de Vater ist, bis auf die letzte Ebene vollständig besetzt istund höchstens eine Lücke in der letzten Ebeene hat, die ganz rechts außen liegen muss. Man kan das ganze als Array speichern: Linkes Kind von i ist 2i + 1 Rechtes Kind von i ist 2i + 2 Vater von i ist ⌊(i − 1)/2⌋ Einfügen: Schlüssel an das ganz linke Ende hängen und an die richtige Stelle aufsteigen lassen. Der kleinste Schlüssel ist in der Wurzel. extract­min:* Ersetze die Wurzel durch den letzten Knoten und lasse dann den Schlüssel in der Wurzel heruntersinken Sortieren Kontroiere einen Max­Heap(größtes oben) Entferne wiederholt das größte Elemente Speichere es an einer freiwerdenden Position Laufzeit: O(n log n) Einfügen und extract_min in O(log n). Das Verfahren ist in­place. Radixsort Straight­Radix­Sort Sortieren von rechts nach links. Radix Exchange Sortieren nach dem ersten Bit und dann unabhänig von einander mit der zweiten Stelle. Dies geschiet rekursiev. Quicksort Heapsort Mergesort Insertion­Sort Straight­Radix Radix­Exchange in­place ?? J N J N ?? stabil N N J J J nw Laufzeit(Worst­case) n^2 n log n n log n n^2 nw nw Laufzeit(Mittel) n log n n log n n log n n^2 nw nw vergleichsbasiert J J J J N N Graphenalgorithmen Ein ungerichter Graph ist ein Paar (V,E) mit V als Menge der Knoten und E die Menge der Kanten ist. Darstellung von Graphen Adjezenzmatrix O(∣V ∣2 ) Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 Adjazenzliste O(∣V ∣ + ∣E∣) In O(n^2) Schritten kann man zwischen diesen Darstellungen konvertieren Tiefensuche Bei der Tiefensuche wird ein gerichteter Tiefensuchwald berechnet, welcher bei einem ungerichteten Graphen ein Baum darstellt. Jeder Knoten bekommt eine Start und Endzeit. Es gibt Baum­, Vorwärts­, Rückwärts­ oder Querkanten. Damit kann man alle Zusammenhangskomponenten finden. Die Kanten sind dick und die Knoten Anfangs weiß. Wenn der Knoten aktiv ist wird er weiß, danach schwarz. Taxomonie von Kanten eine Baumkante ist jegliche Kante Eine Vorwärtskante geht von eine mKnoten zu einem seiner Nachbarn eine Rückwärtskante geht von einem Knoten zu einem seiner Vorfahren eine Rückwärtskante geht con einem Knoten zu einem seiner Vorfahren eine Querkante verbindet zwei unvergleichbare Knoten Zusammenhangskomponenten U und V sind zusammenhängend wenn es einen Pfad von u nach v gibt. Es gibt dann aber keine echte Obermenge davon. In einer Tiefensuche sind alle schwarzen Knoten eine Zusammenhangskomponente. Finden von Kreisen Azyklisch = kein Kreis, dies geschied, wenn es keine Rückwärtskante gibt. Starke Komponenten Der Knoten mit der Größten Finishtime ist die Quellenkomponente, zudem ist dies eine starke Komponente, in die keine Kante hineinführt. Eine Senkenkomponente ist eine Komponente in Gr, wo keine Kante herausführt. Etnfernt mein die Quellenkompennente, so bleibt er ein DFS­Wald Starke Zusammenhangskomponenten Eine Zusammenhängung die man nicht er erweitern kann. Meistens sind dies Kreise. Kosaraju Um Starkke Zusammenhangskomponenten 1. Bilde Gr, also Kanten umdrehen 2. Füre Tiefensuche auf ihn aus 3. Ordne die Knoten nach absteigender finish time 4. Führe in dieser Reihenfolge die Tiefensuche auf G aus 5. Jeder Baum spannt dann eine starke Komponennte auf Topologisches Sortieren Reflexiv­Transitive Hülle: Eine Hülle, die alle direkten und indirekten Nachbarn enthällt und jeder Knoten eine Relation zu sich selbst hat. Ordnet einen Knoten eines DAG so, dass keine Kante von einem größerem zu einem kleineren Knoten führt. Wenn wir auf einen DAG nach der finish times eines Tiefensuche umgekehrt anordnen, so ist dieser topolisch sortiert. Kürzeste Pfade s­t Connectivity Man sucht den Pfad von s nach t. Somit führt man eine Tiefensuche startend von s aus. Wenn f (t) < f (s) dann gibt es Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 einen Pfad von s nach t. Single Source Shortest Paths Wir wollen den kürzesten Pfad von s zu allen anderen Knoten finden. Wir haben die Menge F, desen Abstand uns bekannt ist. Dijkstra Wir nehmen immer den Pfad mit dem kleinsten Gewicht und gucken bei jedem Schritt global was der kleinste ist. Diese werden in der Priority Queue gespeichert. Es funktioniert nicht mit negativen Kantengewichten. Priority Queues Operationen: 1. Einfügen mit Gewicht 2. Finden und Entfernen mit minimalen Gewicht 3. Gewicht eines Elementes verringern Das ganze ist ein heap mit 0(log n) Bellman und Ford Dieser Algothmus ermöglicht das finden von kürzesten Pfaden auch mit negativen Gewichten. 1. Der Startknoten bekommt die Kosten 0, die andere n ∞. 2. Danach wird geprüft, ob die Kosten für den Anfangsknoten der Kante plus den Wert der Kante. Wenn ja aktualliesieren wir den Wert des Knotens3. Es müssen n­1 Phasen durchlaufen werden, wobei n die Anzahl Knoten ist All Pairs Shortest Paths Eingabe: gerichteter Graph mit Kiantengewichten, Ausgabe: Abstände und kürzester Weg zwischen allen Knotenpaaren Floyd Warshall Wir erstellen eine Matrix wie bei den Graphen, nur, dass wir dort das Kantengewicht eintragen. Wir versuchen nun den Pfad zu finden für die mit unedlich markierten Felder. Um z.B. das Feld a nach c zu erreichen ist das min((a,c), (a,b)+(b,c)) Breitensuche Breitensuche ist das Gegenteil von Tiefensuche. Eine Breitensuche enthällt kürzeste Pfade. Wärend bei der Breitensuche die aktiven Knoten auf eriner FIFI­Queue gespeichert werden, werden bei der Tiegensuche die aktiven Knoten auf einem Stack gespeichert. Hier gibt es nur die Discoverytime. Breitensuche dient dazu alle Abstände und kürzeste Wege von s zu berechnen. Netzwerkalgorithmen Netzwerkfluss Ein Fluss hat eine Quelle s und eine Senke t s­t­Netzwerke In So einem Netzwerk eine jede Kante eine Kapazität > 0 und eine Quelle und eine Senke Flüsse Ein Fluss ist eine Funktion die Paare von Knoten auf reele Zahlen abbildet. 1. Zulässigkeit: Der Fluss kann maximal die Kapazität c erreichen 2. Symmetrie:f(u,v) = ­f(v,u) 3. Fluerhaltung: Das was rein kommt geht wieder raus, außer bei s und t 4. |f| ist der Gesammtfluss Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 Maximalle Flüsse Wir haben ein s­t Netzwerk gegeben und wollen einen Fluss mit dem maximalen Wert erhalten. Bei mehreren s und t führt man eine SuperQuelle/Senke ein. Residualnetzwerke Das ist ein Netzwerk ­ dem Fluss. Aus 15/20 wird dann 15 zurück und 5 hin. Wird als G_f bezeichnet Augmentierende Pfade Ist ein s­t Pfad p in G_f. c_f§ heißt Restkapazität von p.Das ist die kleinste Kapazität einer Kante im Augmentierenden Pfad. Ford­Fulkerson­Methode Zur Bestimmung des maximalen Flusses. Wir wählen einen Augmentierenden Pfad. Nun wählen wir den nächsten, wobei die vollausgelasteten nur rückwärts, die unbenutzten nur vorwärts und die teilweise genutzten in beide Richtungen benutzt werden dürfen. Wir wählen hierbei immer den kürzesten weg. Diese Methode braucht O(f), mit f als Wert des maximalen Flusses. Schnitte in Netzwerken Schnitt teilt einen s­t­Netzwerk in S und T auf, wobei S und T eine Überschneidung haben. Wenn f ein Fluss in G ist, so ist f(S,T) der Fluss über (S,T), dass heißt, was von S nach T fließt. Die Kapazität ist c(S,T), dass heißt, was von S nach T fließen kann. Ein minimaler Schnitt ist ein Schnitt mit minimaler Kapazität. Der Fluss über einen Schnitt und der Wert des Flusses sind identisch. Die Kapazität des kleinsten Schnittes ist gleicher der Wert eines größten Flusses unefizient den Schnitt finden 1. maximalen Fluss berechnen 2. S besteht aus Knoten die von s aus über unkritische Kanten beuscht werden können. Kritisch = voll ausgelastet 3. T besteht aus allen anderen Kanten Bipartites Matching Wir haben einen ungerichteten Graphen gegeben, der der aus zwei Gruppen besteht. Wir wollen ein Matching(Paarung) maximaler Kardinität, also möglichst viele. Informell: Man nimmt den Knoten mit dem kleinsten Grad und sucht sich dort eine Kante. Dadurch wird bei einem Knoten der Grad auch kleiner und wir nehmen den nächsten und immer so weiter. Edmonds­Karp­Algorithmus Hierbei wird der kürzeste Pfad gewählt. Man sucht wieder einen Augmentierenden Pfad und versucht dann die Vorwärtskante zu erhöhen und die Rückwertskanten zu verrringern. Minimale Spannbäume Wir haben einen ungerichteten Graphen mit Kantengewichten und möchten einen Baum erhalten, der alle Knoten enthällt mit minimalen Kantengewicht. Prim Wir fangen mit einem Knoten an uns hängen und hängt so lange die billigste Kanten an ohne einen Kreis zu erzeugen. In die Knoten kommen die Kosten. Greedy Algorithmen Algorithmen die immer sehr geizig(greedy) sind. Matroide Heruntergeladen durch kosas ([email protected])  lOMoARcPSD|25609453 Hat eine endliche Menge und Teilmengen. Alle maximal unabhänigen Mengen eines Matroids haben die gleiche Größe. Kruskal Wir nehmen einen Graphen und wählen alle Kanten beginnent mit der kleinsten Kapazität und fügen sie unserem Baum hinzu, ohne einen Kreis zu bilden. Union­Find naiv alle an einander Hängen union by rank mit Rängen arbeiten Heruntergeladen durch kosas ([email protected])