---
# System prepended metadata

title: 'Algorithmen und Datenstrukturen: Blatt 7'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# Algorithmen und Datenstrukturen: Blatt 7

## Aufgabe 1

### Aufgabe 1a)

![1a](https://i.imgur.com/FwIHeMx.jpg)

### Aufgabe 1b)

![1b](https://i.imgur.com/eEGhJIC.jpg)

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

![3a](https://i.imgur.com/JbxLXgX.jpg)

### Aufgabe 3b)

## Aufgabe 4

### Aufgabe 4a)

### Aufgabe 4b)

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

