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]
