Datenstrukturen und Algorithmen Flashcards
Definition Algorithmus
Bearbeitungsvorschrift zur Lösung eines Problems
- Finitheit - mit endlichen Mitteln beschreibbar
- Determinismus - es ist immer eindeutig definiert, welche Regel als nächste anzuwenden ist
- Determiniertheit - Ausgabe ist immer eindeutig bestimmt
- Platzkomplexität im Sinne vom Speicherplatz
- Zeitkomplexität - Terminierung innerhalb eines angemessenen Zeitpunkts
Klasse von Problemen
Probleme mit praktisch umsetzbarem Algorithmus
Probleme, die möglicherweise einen umsetzbaren Algorithmus haben
Probleme ohne praktikabel umsetzbaren Algorithmus
Muster Pseudocode
Eingabe:
Ausgabe:
Problem: <beschreibung></beschreibung>
- Anweisung
- Solange first <= last
1.
Search Algorithm - Binary Search
var l = 0;
var r = a.length();
while (l <= r) {
var m = (l+r) / 2;
if (s < a[l]) {
r = m-1;
} else if (s > a[l]) {
l = m+1;
} else {
return m;
}
}
Flussdiagram Elements
Use connector for a loop
Use rectangle for an instruction
Algorithmus - ggt
1) Falls a == b, return a
2) if (a > b) then swap(a,b) goto 1)
3) if (a < b) then b := b - a; goto 1)
Definition Menge mit Prädikate
Wir bezeichnen mit einer Menge all diejenigen Objekte aus einem Untersuchungsraum, für die ein gewähltes Prädikat zutrifft.
M = { x | P(x) }
Mengen-Definitionen
- Teilmenge (subset)
- Potenzmenge - kartesisches Produkt
- Vereinigung (union)
- Durchschnitt (intersection)
Definition Relation
Sei eine Menge M gegeben. Jede Teilmenge des kartesischen Produktes M x M beschreibt eine zweistellige Relation.
Beispiel: M = {1,2,3}
< - Relation = {(1,2),(1,3),(2,3)}
<= - Relation = {(1,1),(2,2),(3,3)} und <-Relation
Eigenschaften von Relationen
- R ist reflexiv, wenn für alle x in M gilt: xRx
- R ist symmetrisch, wenn für alle x,y in M gilt: wenn xRy, dann auch yRx (Beispiel: Äquivalenz-Relation)
- R ist antisymmetrisch, wenn für alle x,y in M gilt: wenn xRy und x ungleich y, dann gilt niemals yRx
- R ist asymmetrisch, wenn für alle x,y in M gilt: wenn xRy, dann gilt niemals yRx
- R ist transitiv, wenn für alle x,y,z in M gilt: wenn xRy und yRz dann gilt auch xRz
Relationen - Ordnung und Äquivalenz
- R ist eine Halbordnung - partielle Ordnung
- reflexiv
- transitiv
- antisymmetrisch
- R ist Äquivalenzrelation - falls R
- reflexiv
- symmetrisch
- transitiv
n-stellige Operation
Seien die Mengen M1,M2,…,Mn und M gegeben. Jede Zuordnung von Werten des kartesichen Produktes M1 x M2 x … x Mn zu Werten aus M wird als n-stellige Operation bezeichnet
Operationen - Eigenschaften
Sei Op: M x M -> M
- total - falls für jede Kombination aus Eingabewerten ein Wert aus M definiert ist.
- injektiv - falls für jede Kombination aus Eingabewerten ein verschiedenen Wert in M existiert. Keine zwei unterschiedliche Kombinationen haben gleiches Ergebnis. Es muss aber nicht immer ein Mapping existieren.
- surjektiv - wenn für jeden Wert in M mindestens eine Operation/ein Mapping existiert
- bijektiv - sowohl injektiv und surjektiv - ein eins zu eins Mapping
Definition - Algebra
Die Struktur A = (M1,…,Mm,Op1,…,Opn) wird als mehrsortige Algebra bezeichnet.
- universell - wenn die Operationen nur Werte aus Mi liefern
- Beispiel (N,R,+) ist universell, weil es Werte als natürliche Zahlen und reele Zahlen liefert
Definition - Abstrakte Datentypen
Gegeben
- eine Zeichenmenge Σ
- X eine Menge von Elementar-Operanden
- Ein korrekter Term ist entweder
- eine Konstante a aus der Menge X
- eine Anwendung einer Operation f(a,b,…) mit f in Σ, wobei die Anzahl der Operanden a,b,… der Stelligkeit von f entspricht und jeder Operand ein korrekter Term ist.
- Seien eine Signatur Σ, eine Menge von Elementaroperanden X und die Menge aller korrekten Terme zu Σ und X gegeben. Dann heisst die Struktur aus (T,Σ,Q) abstrakte Algebra oder abstrakter Datentyp, wenn Q eine Menge von Axiomen darstellt.
Abstrakter Datentyp - Stack
- createStack: ø -> Stack(T)
- push: Stack(T) x T -> Stack(T)
- pop: Stack(T) -> Stack(T)
- top: Stack(T) -> T
- empty: Stack(T) -> B
Axiome:
- K1: empty(createStack) = 0
- K2: empty(push(k,t)) = 1
- K3: pop(push(k,t)) = k
Klassifizierung - Datentypen
- linear
- statisch
- Basisdatentypen (primitive datatype)
- int, double, float, boolean, string
- Aggregierte Datentypen
- array (Feld), record (Verbund)
- Basisdatentypen (primitive datatype)
- dynamisch
- Linked List
- Queue
- Stack
- statisch
- non-linear
- graph
- tree
Sort Algorithm - BubbleSort
- Idea - you start from the beginning and move the elements to the end. You repeat this for each element and reduce the number fo elements in each iteration.
Eingabe: Feld natürlicher Zahlen A
Ausgabe: Feld natürlicher Zahlen A
Problem: Sortiere A
- i := 0
- Solange i < A.length
- j := 0
- Solange < (A.length - (i+1))
- Falls A[j] < A[j+1] then Swap(j,j+1)
- j := j + 1
- i := i + 1
Sort Algorithm - SelectionSort
Idea: You iterate through the list. In each iteration you find the minimum value within the remainder of the list. You set the minimum value to that position
- i := 0;
- Solange i < A.length
- minIndex := i
- j := i + 1
- Solange j < A.length
- If A[j] < A[minIndex] then minIndex := j
- j := j + 1
- Tausche A[i] und A[minIndex]
- i := i + 1
Sort Algorithm - InsertionSort
**for** (**int** i = 1; i \< a.Length(); i++) **{**// the value I want to insert into the right position var valueToBeInserted = a[i]; // j now points to the last element in the left sorted list // hence j+1 is the element which we want to insert into the right position var j = i-1; // iterate until you find the right position to insert the value and // move all the elements to the right during this process **while**(j \>= 0 && a[j] \> key) **{** a[j+1] = a[j]; j--; **}**// j+1 is the correct position because of the condition which terminates the loop a[j] \< key a[j+1] = key; **}**Search Algorithm - Binary Search / InterpolationSearch
Idea: Given a sorted list you intersect through the whole list step by step
function int midIndex(int l, int r, int[] a) {
return (r-l) / 2;
}
function int interpolMidIndex(int l, int r, int s, int[] a) {
return l + ((s - a[l]) / (a[r] - a[l])) (r - l);
}
l := 0;
r := length(A)
while( l <= r) {
m := func(l,r,s,a);
if (s > a[m])
l := m+1
else (s < a[m])
r := m-1
else return m;
}
Datenstruktur - Baum - Definitionen
- Vertex / Node - Knoten
- Root - Wurzel
- Leaf - Blatt - die Knoten, die keinen Nachfolger haben
- Vaterknoten / Sohnknoten <=> Parent/Child node
- Depth - Tiefe/Niveau => Länge des Pfades von der Wurzel zu einem Knoten
- Height - Höhe => Länge des größtmöglichen Pfades
- Ordnung - degree => maximale Anzahl an Söhnen, die ein Vaterknoten haben kann
- Ordered Tree
- partielle Ordnung durch die Reihenfolge der Knoten im Baum. Allerdings sind die Knoten auf dem gleichen Niveau noch nicht geordnet.
- Wenn man noch eine Ordnung der Knoten auf dem gleichen Niveau definiert, dann hat man einen (streng) geordneten Baum
Datenstruktur - Graph - Definitionen
-
Ungerichteter Graph
- G ist ein paar (V,E), wobei V die Menge der Vertices des Graphen und E (Edges) die Menge der binären Relationen der Vertices definiert
-
Gerichteter Graph (digraph)
- ein Graph dessen Edges/Kanten nicht symmetrisch sein müssen
-
Zyklus (Cycle)
- Ein Weg in einem gerichteten Graph, der zum Ursprungsknoten führt, wird Zyklus bezeichnet. Ein Graph mit Zyklus wird als zyklisch bezeichnet. Ein Graph ohne Zyklus wird azyklisch bezeichnet.
- Adjazenzmatrix (adjency matrix)
MinMaxSearch2
**def** **MinMaxSearch2**(list): minIndex = **0** maxIndex = **0** i = **1****while**(i \< len(list)):**if**(list[i] \< list[minIndex]): min =**0****if** (list[i] \< list[maxIndex]): max = i i = i + **1****return** list[min], list[max]
MinMaxSearch3 - eine Runde Gewinner und Verlierer und dann normale Suche
**def** **MinMaxSearch3**(list): i = **0** w = [] l = [] **while** (i \< len(list)-**1**): **if** list[i] \> list[i+**1**]: w.append(list[i]) l.append(list[i+**1**]) **else**: w.append(list[i+**1**]) l.append(list[i]) i = i + **2**min = MinSearch2(w) max = MaxSearch2(l) **return** max, min
Wieviele Vergleiche brauche ich mit dem Turnier-Modus, um das Maximum und das zweitbeste zu finden?
(n - 1) + log n
log n gibt die Höhe des Baumes, um den zweiten zu finden
n - 1 ist die Anzahl der Vergleiche, die sich aus der Summe der Vergleiche entlang des Baumes von unten nach oben ergibt
n = sum_i^{log n} (1 / 2^i)
Was ist der Index des k-ten Elements in einer aufsteigend sortierten Liste?
len(list) - k
[1,3,8,10]
2-te Element = 4 - 2
Welche Methoden für den Umgang mit Kollisionen gibt es bei Hash-Verfahren und was machen sie?
Offene Verfahren - es wird eine verzweigte Struktur aufgebaut, die die Stellen der Kollisionen expandiert
Geschlossene Verfahren - wenn es zu einer Kollision kommt, wird der nächste freie Platz in der Hash-Liste ausgewählt
Formuliere die Ausgangsgleichung des Master-Theorems
T(n) = a T(n/b) + f(n)
T(n) = a T (n/b) + nk
Was sind die drei Lösungen des Master-Theorems?
- a < bk T(n) = O(nk)
- a = bk T(n) = O(log(n) nk)
- a > bk T(n) = O(nlogba)
Was ist die Idee hinter Insertion Sort?
Es gibt die linke Hälfte der Liste, die sortiert ist. Es gibt die rechte Hälfte der Liste, die nicht sortiert ist. Ich gehe durch jedes Element in der Liste. Schiebe alles so lange nach rechts, bis ich die Stelle gefunden habe, wo ich dieses Element einsetzen kann.
