Datenstrukturen und Algorithmen

Question 1

Definition Algorithmus

Answer 1

Bearbeitungsvorschrift zur Lösung eines Problems

1. Finitheit - mit endlichen Mitteln beschreibbar
2. Determinismus - es ist immer eindeutig definiert, welche Regel als nächste anzuwenden ist
3. Determiniertheit - Ausgabe ist immer eindeutig bestimmt
4. Platzkomplexität im Sinne vom Speicherplatz
5. Zeitkomplexität - Terminierung innerhalb eines angemessenen Zeitpunkts

Question 2

Klasse von Problemen

Answer 2

Probleme mit praktisch umsetzbarem Algorithmus

Probleme, die möglicherweise einen umsetzbaren Algorithmus haben

Probleme ohne praktikabel umsetzbaren Algorithmus

Question 3

Muster Pseudocode

Answer 3

Eingabe:

Ausgabe:

Problem: <beschreibung></beschreibung>

1. Anweisung
2. Solange first <= last
   1.

Question 4

Search Algorithm - Binary Search

Answer 4

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;

}

}

Question 5

Flussdiagram Elements

Answer 5

Use connector for a loop

Use rectangle for an instruction

Question 6

Algorithmus - ggt

Answer 6

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)

Question 7

Definition Menge mit Prädikate

Answer 7

Wir bezeichnen mit einer Menge all diejenigen Objekte aus einem Untersuchungsraum, für die ein gewähltes Prädikat zutrifft.

M = { x | P(x) }

Question 8

Mengen-Definitionen

Answer 8

• Teilmenge (subset)
• Potenzmenge - kartesisches Produkt
• Vereinigung (union)
• Durchschnitt (intersection)

Question 9

Definition Relation

Answer 9

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

Question 10

Eigenschaften von Relationen

Answer 10

• 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

Question 11

Relationen - Ordnung und Äquivalenz

Answer 11

• R ist eine Halbordnung - partielle Ordnung
  
  • reflexiv
  • transitiv
  • antisymmetrisch
• R ist Äquivalenzrelation - falls R
  
  • reflexiv
  • symmetrisch
  • transitiv

Question 12

n-stellige Operation

Answer 12

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

Question 13

Operationen - Eigenschaften

Answer 13

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

Question 14

Definition - Algebra

Answer 14

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

Question 15

Definition - Abstrakte Datentypen

Answer 15

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.

Question 16

Abstrakter Datentyp - Stack

Answer 16

• 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

Question 17

Klassifizierung - Datentypen

Answer 17

• linear
  
  • statisch
    
    • Basisdatentypen (primitive datatype)
      
      • int, double, float, boolean, string
    • Aggregierte Datentypen
      
      • array (Feld), record (Verbund)
  • dynamisch
    
    • Linked List
    • Queue
    • Stack
• non-linear
  
  • graph
  • tree

Question 18

Sort Algorithm - BubbleSort

Answer 18

• 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

1. i := 0
2. Solange i < A.length
   
   1. j := 0
   2. Solange < (A.length - (i+1))
      
      1. Falls A[j] < A[j+1] then Swap(j,j+1)
      2. j := j + 1
   3. i := i + 1

Question 19

Sort Algorithm - SelectionSort

Answer 19

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

1. i := 0;
2. Solange i < A.length
   
   1. minIndex := i
   2. j := i + 1
   3. Solange j < A.length
      
      1. If A[j] < A[minIndex] then minIndex := j
      2. j := j + 1
   4. Tausche A[i] und A[minIndex]
   5. i := i + 1

Question 20

Sort Algorithm - InsertionSort

Answer 20

**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; **}**

Question 21

Search Algorithm - Binary Search / InterpolationSearch

Answer 21

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;

}

Question 22

Datenstruktur - Baum - Definitionen

Answer 22

• 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

Question 23

Datenstruktur - Graph - Definitionen

Answer 23

• 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)

Question 24

MinMaxSearch2

Answer 24

**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]

Question 25

MinMaxSearch3 - eine Runde Gewinner und Verlierer und dann normale Suche

Answer 25

**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

Question 26

Wieviele Vergleiche brauche ich mit dem Turnier-Modus, um das Maximum und das zweitbeste zu finden?

Answer 26

(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)

Question 27

Was ist der Index des k-ten Elements in einer aufsteigend sortierten Liste?

Answer 27

len(list) - k

[1,3,8,10]

2-te Element = 4 - 2

Question 28

Welche Methoden für den Umgang mit Kollisionen gibt es bei Hash-Verfahren und was machen sie?

Answer 28

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

Question 29

Formuliere die Ausgangsgleichung des Master-Theorems

Answer 29

T(n) = a T(n/b) + f(n)

T(n) = a T (n/b) + n^k

Question 30

Was sind die drei Lösungen des Master-Theorems?

Answer 30

• a < b^k T(n) = O(n^k)
• a = b^k T(n) = O(log(n) n^k)
• a > b^k T(n) = O(n^log_ba)

Question 31

Was ist die Idee hinter Insertion Sort?

Answer 31

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.