# Algorithmen und Datenstrukturen: Blatt 7

## Aufgabe 1

### Aufgabe 1a)


### Aufgabe 1b)


## Aufgabe 2

### Aufgabe 2a)

Zu zeigen:
$|U| \geq nm\Rightarrow$ es gibt (mindestens) $n$ Schlüssel in $U$,
die alle in die gleiche Zeile t von T hashen.
Beweis per Induktion:

Induktionsanfang: $m = 1$:
Fall 1: $|U| = nm = n$:
Da T nur eine Zeile t hat, werden alle n Schlüssel in diese Zeile gehasht.
Fall 2: $|U| > nm = n$:
Dadurch, dass in Fall 1 bereits n Schlüssel in t liegen, werden die Schlüssel,
die nun zusätzlich hinzugekommen sind, mit gleicher Begründung, in t gehasht.
Damit liegen mehr als $n$,
also mindestens $n$, Schlüssel in t.

Induktionsvoraussetzung: Die Aussage gilt also für ein festes $m$.

Induktionsschluss: $k=m+1$:
Fall 1: $|U| = nk = n(m+1) = nm + n$:
Nach Induktionsvoraussetzung liegen nm Schlüssel in
einer Tabelle mit der Größe $m$ so verteilt,
dass $n$ Schlüssel in einer Zeile liegen.
T hat nun die Größe $k = m+1$.
Also bleibt noch eine Zeile übrig. In diese Zeile werden die übrigen
$(nm+n)-nm = n$ Schlüssel gehasht.
Damit liegen in dieser Zeile t $n$ Schlüssel.
Fall 2: $|U| > nk = nm + n$:
Dadurch, dass in Fall 1 bereits n Schlüssel in t liegen, werden die Schlüssel,
die nun zusätzlich hinzugekommen sind,
mit gleicher Begründung, in t gehasht. Damit liegen mehr als $n$,
also mindestens $n$, Schlüssel in t.

### Aufgabe 2b)

## Aufgabe 3

### Aufgabe 3a)


### Aufgabe 3b)

## Aufgabe 4

### Aufgabe 4a)

### Aufgabe 4b)

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