Algorithmen und Datenstrukturen
Algorithmen und Datenstrukturen in Java
Algorithmen und Datenstrukturen in Java
Kartei Details
Karten | 35 |
---|---|
Lernende | 28 |
Sprache | Deutsch |
Kategorie | Informatik |
Stufe | Universität |
Erstellt / Aktualisiert | 13.05.2013 / 27.06.2023 |
Weblink |
https://card2brain.ch/box/algorithmen_und_datenstrukturen
|
Einbinden |
<iframe src="https://card2brain.ch/box/algorithmen_und_datenstrukturen/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Lernkarteien erstellen oder kopieren
Mit einem Upgrade kannst du unlimitiert Lernkarteien erstellen oder kopieren und viele Zusatzfunktionen mehr nutzen.
Melde dich an, um alle Karten zu sehen.
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)
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
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
- 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
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()
Java Node List ADT •Exceptions? •Methoden?
Exceptions: EmptyListException ElementNotFoundException Methoden: Remove() addBefore() addAfter() In Listen: while-Schleife, in Arrays: for-each
LinkedHashSet
•Reihenfolge garantiert
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:
-
- 1 / 35
-