---
# System prepended metadata

title: 'AlgoDat: Tutorium 1'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# AlgoDat: Tutorium 1

## Aufgabe 1

#### a) **[1|2|3|4]**

InsertionSort

- Index: 1 2 3 4  
$j=2$: **[1|2|3|4]**  
$i=1:  i=1 > 0$ und $A[1]=1 < key = 2$  
*Vergleich: 1 und 2*

- Index: 1 2 3 4  
$j=3:$ **[1|2|3|4]**  
$i=2:  i=2 > 0$ und $A[2]=2 < key = 3$  
*Vergleich: 3 und 4*

- Index: 1 2 3 4  
$j=4:$ **[1|2|3|4]**  
$i=3:  i=3 > 0$ und $A[3] < key = 4$  
*Vergleich: 5 und 6*

$\Rightarrow$ Auf diesem Array werden
3 Vergleiche beim InsertionSort Algorithmus durchgeführt.

MergeSort:

Index: 1 2 3 4  
Array: **[1|2|3|4]**  
$l=1<r=4$  
$m = 2$  

| TeilArray: 1 2 |     | TeilArray: 3 4 |     |
| -------------- | --- | -------------- | --- |
| l=1<r=2        |     | l=3<r=4        |     |
| *Vergleich 1*  |     | *Vergleich 2*  |     |
| m=1            |     | m=1            |     |
|**TeilArray: 1**|**TeilArray: 2**|**TeilArray: 3**|**TeilArray: 4**|
| l=1=r        |l=2=r        |l=3=r        |l=4=r        |

| Merge(A=[1,2],l=1,m=1,r=2) | Merge(A=[3,4],l=3,m=3,r=4 |
| -------------------------- | ------------------------- |
| L[1]=1<R[1]=2              | L[1]=3<R[1]=4             |
| *Vergleich 3*              | *Vergleich 4*            |

| Merge(A=[1,2,3,4],l=1,m=2,r=4) |
| ------------------------------ |
| L[1]=1<R[1]=3                  |
| *Vergleich 5*                  |
| L[2]=2<R[1]=3                  |
| *Vergleich 6*                  |

$\Rightarrow$ Auf diesem Array werden 6 Vergleiche beim MergeSort Algorithmus durchgeführt.

#### b) *analog*

InsertionSort: 6 Vergleiche
MergeSort: 6 Vergleiche

## Aufgabe 2: Add per Schleife

Schleifeninvariante: $s=a+i-1$

#### 1.) Initialisierung

Zeige: Invariante ist beim 1.Schleifendurchlauf erfüllt.

Hier: klar, denn für $i=1$ gilt:  
$s=a+i-1=a+1-1=a$

#### 2.) Aufrechterhaltung

Zeige: Wenn die Invariante vor dem $i.$ Schleifendurchlauf erfüllt ist,
dann auch vor dem $i+1.$

Hier: Vor dem $i.$ Durchlauf gilt INV,
d.h. $s=a+i-1$.
Dann wird $s$ mit $1$ addiert $\Rightarrow s=a+i$
Dann wird $i$ um $1$ erhöht $\Rightarrow s=a+i-1 \Leftarrow$ INV

#### 3.) Terminierung

Zeige:
Zusammengenommen ergeben Invariante und verletzte   Schleifenbediengung die Korrektheit.

Hier: Verletzte Schleifenbedingung: $i>b$, also $i=b+1$.
Einsetzen von "$i=b+1$" in INV liefert $s=a+b$.

$\Rightarrow$ Der Algorithmus terminiert und liefert das korrekte Ergebnis.

###### tags: `Algorithmen und Datenstrukturen` `Uni` `Informatik`
