Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen in Java
Algorithmen und Datenstrukturen in Java
Fichier Détails
| Cartes-fiches | 35 |
|---|---|
| Utilisateurs | 28 |
| Langue | Deutsch |
| Catégorie | Informatique |
| Niveau | Université |
| Crée / Actualisé | 13.05.2013 / 27.06.2023 |
| Lien de web |
https://card2brain.ch/box/algorithmen_und_datenstrukturen
|
| Intégrer |
<iframe src="https://card2brain.ch/box/algorithmen_und_datenstrukturen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
- Wie stehen Kanten im Verhältnis zu einem Vertex bei Graphen?
- Wie viele Kanten kann ein Vertex maximal haben?
- Wofür ist die Adjazenz-Liste?
- Jeder Vertex hat nicht zwingend eine Kante. Jede Kante hat aber per Definition zwingend zwei Vertizes.
- n-1
- Bidirektionalität zwischen Kanten und Vertizes.
AVL Baum •Balancierter Baum •Traversierungen – Reihenfolgen?
- In-Order Traversierungen eines Binärbaumes liefern eine aufsteigend sortierte Ausgabe - Im Pseudo-Code ist die geschweifte Klammer {} ein Kommentar! •Einfügen ist gleich wie beim binären Suchbaum •Inorder-Listing beachten bei Umstrukturierung: AVL Trees S. 10 •wie merkt man, welche rotation nötig ist? •Rotation: Der Mittlere Knoten (b (zweiter Knoten bei Inorder über x,y,z)) muss zur Root werden
Double Linked List •Implementierung welcher Klasse? •Was speichern Nodes? •Start- End Nodes? •Links?
...
Eigenschaften eines Graphes?
- Anzahl Vertex, Anzahl Kanten, Zyklen
Methoden?
Methoden:
endVertices(e)
opposite(v,e)
areAdjacent(v,w)
replace(v,x) -> replace elem at vertex v with x
replace(e,x) -> replace elem at edge e with x
insertVertex(o)
insertEdge(v,w,o) -> insert an edge (v,w) storing elem o
removeVertex(e)
removeEdge(e)
incidentEdges(v) -> collection of edges incident to v
vertices()
edges()
Einfügen in eine Double Linked List?
...
Graphen:
- Zyklen finden?
Siehe Bild:
Java Node List ADT •Exceptions? •Methoden?
Exceptions: EmptyListException ElementNotFoundException Methoden: Remove() addBefore() addAfter() In Listen: while-Schleife, in Arrays: for-each
LinkedHashSet
•Reihenfolge garantiert
Postorder Traversierung?
...
Preorder Traversierung?
...
Priority Queue
Methoden?
Eigenschaften?
Ordnung?
Entries?
Methoden: Insert(k,v); Size(); isEmpty(); removeMin(); min()
Eigenschaften: ORDNUNG: Wenn 2<3 und 3<4 2<4 : transitiv Wenn 2<=x und x<=2 2=x: antisymmetrisch
Entry Klasse: Key(), Value() Comparator ADT Vergl. A – B:
Suchen in einer Skiplist?
...
Summenformel
Vollständige Induktion?
Implizit, Rekursiv, iterativ?
überleg dir wie die vollständige Induktion funktioniert
Wie sieht es mit dem Laufzeitverhalten folgender Methoden bei Graphen aus?
- incidentEdges(v)
- areAdjacent(v,w)
- insertVertex(o)
- insertEdge(v,w,o)
- removeVertex(v)
- removeEdge(e) ?
siehe Bild
Binärer Suchbaum BST Einfügeimplementation?
...
Binärer Suchbaum: Löschen?
...
Boyer- Moore vs. KMP- Algorithmus •Fehlfunktions-Tabelle •Laufzeit expected und worst case
...
Bucket Sort •Bereich? •O-Notation / Laufzeit? •Unterschied / Gleichheit mit Hashtable? •Phase 1, Phase 2? •Stabilität bei gleichen Keys?
•Bereich wird von der Applikation vorgegeben; kann grosser Speicherbereich benötigen •n + N •Ziel Index wird nicht berechnet; es wird der Key verwendet (Java.Util.hashtable mit key-chaining geschlossene Adressierung) •Stabilität garantiert, weil die Reihenfolge der Keys vorhanden bleibt
Dynamische Programmierung: Subprobleme
•Rucksack-Problem
•Längste gemeinsame Subsequenz zweier Strings •LCS-Algorithmus
Let x be “XMJYAUZ” and y be “MZJAWXU”. The longest common subsequence between x and y is “MJAU”.
Graphen:
- Pfade finden?
siehe Bild
Graphen:
- DFS (Depth-First Search -> Tiefensuche) Funktionalität?
Bild
Hashtables Lineare Sondierung? Quadratisches Hashing? Linear Probing? Sinnvolle Füllmenge?
Nach dem remove(e) muss, wenn ein Feld e als AVAILABLE markiert werden, falls andere mit e verknüpft sind. Eine Hash-Table sollte zu max 80% ausgelastet sein.
Heaps Eigenschaften? Upheap-Bubbeling / Downheap? Höhe eines Heaps? Methoden?
•Binärbaum •Heap Eigenschaft –Key(v) >= key(parent) àzuoberst ist „min“ •Vollständiger Binärbaum: –Von links nach rechts aufgefüllt •Einfügen von min: •1. Normal einfügen: zuunterst •2. Reheap: unterste wird mit oberem verglichen und das kleinste somit zum Root gebracht: „upheap bubbeling“ •removeMin(): •1. Root wird vom Untersten überschrieben (es ist im moment ein grösseres Element zuoberst als gewisse darunter) •2. Reheap: vergleiche und sortiere: „downheap bubbeling“ •Höhe eines Heaps |_ log(n) _| bei n Knoten -> floor (abrunden): 3.2 └ 3.2 ┘ = 3 -> ceiiling (aufrunden): 3.2 ┌ 3.2┐ = 4 •Methoden des Heaps minHeap() maxHeap() •Höhe des Heaps •Fall 1: alle Level voll: 2^k Knoten: anzahl Knoten k = log(n+1) -1 à log(n) •Fall 2: nicht voller Level: Höhe h ~ log(n) •H = 1 K = 2 ^ 2 - 1 = 3 •H = 2 K = 2 ^ 3 - 1 = 7 •… (wenn ganz gefüllt) : ~2h+1 •H=1 K = 2^1 = 2 •H=2 K = 2^2 = 4 •… (wenn nur links gefüllt) : ~ 2h+1 •Für alle Heaps ~ ~ h = log(n) •Anwendung des Heap ADT •HeapSort: •Gegeben: Sequence s: o-o-o-o (z.b. LinkedList) •Gesucht: sortierte Sequence s‘ è Lös: 1) s à Heap (min) 2) removeMin() à s‘ aufbauen (add)
Insertion Sort Einfügen? Sortieren? For-schleifen, etc?
...
Lexikographische Sortierung / Radix Sort •Voraussetzung?
•Muss intern ein stabiler Sortieralgorithmus haben •Dimensionen werden von hinten nach vorne sortiert
Merge Sort
•IN-Array - OUT-Array •Zwei zusammenfassen und sortieren •Stabil
Quick Sort •Laufzeitverhalten? •Ablauf?
•LAUFZEIT: Im Idealfall “Good Calls”: – 25% < Pivot < 75% è n Log(n) •Bad Calls 75%< Pivot < 25% –N^2 –!: nur expected
N(log(n))
- Nicht stabil!!
Sets •Voraussetzung, Eigenschaft? •Vereinigung zweier Sequenzen?
•Müssen sortierte Sequenzen / Mengen sein •Vergl 5 mit 6 und schreibe kleinere (5) in Zielsequenz; inkrementiere Index auf Sequenz 1 und wiederhole
Breitensuche:
Eigenschaft?
Algorithmus?
Unterschied zur Tiefensuche?
- sucht möglichst nahe Vertizies
- nicht rekursiv (iterativ)
- besucht alle Vertizes und Kanten; bildet einen aufspannenden Baum
- findet auch Komponenten desselben Graphes, die nicht direkt verbunden sind (durch Iteration durch alle Knoten)
- Kürzester Weg wird nur aufgrund der Anzahl Knoten gefunden (nicht Länge des Weges)
Skiplist Definition? Grund? O-Verhalten? Was beinhaltet das update[ ]?
Kombination Array/List/Stack (einfache Strukturen) und Bäume (schnelle Strukturen)
Splay-Baum
•Splay-Operation wird immer (auch beim Suchen) gemacht •Divide-And-Conquer: merge-sort •Stichwörter: •Selection-sort: O(n^2), langsam, in-place, für kleine Data Sets •Insertion-Sort: O(n^2), inplace, wie selection •Heap-sort: O(n log n ) : schnell, in-place, für grosse Daten-Sets (1K – 1M) •Merge-sort: O(n log n): schnell, sequentieller Datenzugriff, für riesige Data Sets (> 1M)
Subsequenzen •Reihenfolge?
Ordnung?
•Kein Substring •Reihenfolge beibehalten
- Gerichtete Graphen (Directed Graphes - Digraph)
- Strong Connectivity
- Transitiver Abschluss
- Jede Kante hat eine Richtung
- der ganze Graph muss von jedem Knoten aus erreichbar sein
- der Transitive Abschluss von G wird G* :
Jeder gerichtete Pfad wird ersetzt durch eine gerichtete Kante
Was ist ein DAG?
Directed Acyclic Graph, ein gerichteter Graph ohne Zyklen
Algorithmus: Topological Sort
->Bild
