---
tags: Assignments
---

# Blatt 06

|Kurs |Semester |Team |
|--- |--- |--- |
|Algorithmen und Datenstrukturen |SS 2020 |Carlo Mohl & Noah Nuebling |

---

## Aufgabe 1

### 1)
Um das Wort s in das Wort s' umzuwandeln können wir alle Buchstaben der LGTS belassen. Um nun die 'inkorrekten' Teilworte w zwischen den Elementen der LGTS in s in die entsprechenden 'korrekten' Teilworte w' von s' umzuwandeln, können wir für jedes Element aus dem korrekten w' entweder ein Element aus dem w umwandlen oder ein Element in w einfügen. Wir brauchen also höchstens |w'| Operationen um w in w' umzuwandeln.

Die Länge aller w' aufsummiert ist m - |LGTS(s,s')|.

### 2)
Gegenbeispiel: Man nehme das gleiche Wort für n und m z.B "Tee" und vergleiche die Editierdistanz zwischen "nichts tun" und "löschen aller Zeichen von s und einfügen der Zeichen von s´". Dabei kommt für "nichts tun" eine Editierdistanz von 0 heraus, bei "löschen aller Zeichen von s und einfügen der Zeichen von s´" eine Editierdistanz von 3. 3>0 -> somit Aussage falsch.

### 3)

Falsch. Gegenbeispiel:

xabcy

yabcx

### 4)

Falsch.

s = a b c d x y

s' = a y b x c d

s_4 = a b c d

-> Haben trotzdem gemeinsame Zeichen.

### 5)

Falsch. Gegenbeispiel:

ANA

## Aufgabe 2

### OST zu WEST

OST, EST, WEST

### RAST zu LOS

RAST, LAST, LAS, LOS

### ZUNGE zu MAGEN

ZUNGE, ZUNGEN, ZANGEN, ZAGEN, MAGEN

### BODEN zu SEE

BODEN ODEN, DEN, SEN, SEE

### EINS zu ZEHN

EINS, EIN, ZEIN, ZEHN

## Aufgabe 3

_Im folgenden benutzen wir "Schritt" und "Operation" mit gleicher Bedeutung. Hiermit meinen wir die Operationen die angewendet werden um Wörter in andere Wörter umzuwandeln. Also Löschen, Einfügen, und Ersetzen._

### a)

1.)

__Positive Definitheit__
Die ED(s, s') entspricht der minimalen Anzahl an Schritten um s in s' umzuwandeln. Die Anzahl der Schritte ist >= 0.
Die Anzahl der Schritte ist genau dann 0 wenn s = s'.

__Symmetrie__
Da alle Operationen reversibel sind, gilt: Für eine minimale Abfolge an Schritten f um s in s' umzuwandeln, kann die umgekehrte Abfolge an Schritte f' auf s' angewendet werden kann um s' mit einer minimalen Anzahl an Schritten in s umzuwandeln.

In sofern Löschen und Einfügen die selben Kosten haben gilt also d(a,b) = d(b,a).

__Dreiecksungleichung__
d(a,c) ist gleich der Länge der minimalen Schrittefolge um a in c umzuwandeln |f(a,c)|. d(a,b) + d(b,c) ist gleich der Summe der Längen der minimalen umwandlungs-Schrittefolgen |f(a,b)| + |f(b,c)|. Diese beiden Schrittefolgen hintereinander ausgeführt beschreiben nun auch eine Schrittefolge die a in c umwandelt f'(a,c). |f'(a,c)| muss nun aber >= |f(a,c)| sein, da f(a,c) nach Definition minimal ist.

2.)

Siehe den Text unter "Symmetrie" weiter oben.
Wenn z.B. p(Einfügen) = 1 und p(Löschen) = 2, dann gilt die Symmetrie nicht, da eine Operation und ihre Reversierungsoperations unterschiedliche Kosten haben.

### b)

Nein, die Länge des längsten gemeinsamen Teilwortes und die Länge der längsten gemeinsamen Teilsequenz sind keine Metriken, denn beide sind nicht 0 wenn a = b. (insofern |a| = |b| > 0)
Damit haben Sie nicht die Eigenschaft der positiven Definitheit.

## Aufgabe 4

### a)

__1. Aggregationsmethode__

$c(Op_i) = 1 \textbf{ für } i \neq 4^j + 1$

$c(Op_i) = 4^{j+1} + 4^{j} + 1 \textbf{ für } i = 4^j + 1$

$$
\sum_{i=1}^{n} c(Op_i) = n + \sum_{j=0}^{log_4n} 5\cdot 4^j \leq 8n
$$

__2. Bankkontomethode__

$c'_i = 8$

Bei billigen Einfügungen gilt $c_i = 1$, der Überschuss beträgt also 7.

Bei Vergrößerungsoperationen beträgt unser Guthaben mindestens

$$
\sum_{i=1}^{3 \cdot 4^{j-1}} 7 + 8 = 21 \cdot 4^{j-1} + 8 \geq 5 \cdot 4^{j} + 8
$$

Das Guthaben ist größer als die Reallokierungskosten $5 \cdot 4^j + 1$, damit haben wir also eine valide obere Schranke gefunden.

### b)

:::info
_Lieber Tutor, das folgende ist Blödsinn, und du kannst es gerne ignorieren._
:::

Anzahl Elemente in der x-ten Ebene: 2^x (Die Wurzel ist auf der 0-ten Ebene)

Worst case Laufzeit für ein Element der Ebene x:

- Wenn x = ceil(log n) - 1: ceil(log n) - 1
- Auf der letzten Ebene, kann es sein, dass es kein rechtes Kind gibt. Dann muss der Baum im worst-case bis zur Wurzel traversiert werden
- Wenn x = ceil(log n) - 2: ceil(log n) - 2
- Gleiches gilt für die zweit-letzte Ebene
- Sonst: (log n) - x
- In allen anderen Fällen muss es in einem balancierten Baum ein rechtes Kind geben. Hier wird der Baum also im worst-case bis ganz nach unten traversiert.

Es ergibt sich also die folgende Formel für die Gesamtlaufzeit:

$\sum_{x=0}^{ceil(\log n) - 3} 2^x \cdot (ceil(\log n) - x)$

$+ 2^{ceil(\log n) - 2} \cdot (ceil(\log n) - 2)$

$+ 2^{ceil(\log n) - 1} \cdot (ceil(\log n) - 1)$

Wenn diese Formel richtig ist und eine ausreichend scharfe obere Schranke darstellt, dann würde Wolfram Alpha sagen, dass sie in O(n) ist.