Algorithmik (Vorlesung 1) - Maximilian Krieg

In der ersten Vorlesung von Algorithmik haben wir die Ziele der Vorlesung besprochen und Grundbegriffe anhand von einfachen Algorithmen diskutiert.

Anfang	algo_teil01_1 – Seite 1
Ende	algo_teil01_2 – Seite 18

Allgemeines

Begrifflichkeiten

Wert einer Teilzahlenfolge: \(w(a, i, k)=\sum_{j=i}^{k}a[j]\)
i = Kleinster Index
k = Höchster Index
n = Länge der Zahlenfolge
Es gilt, dass die Werte von i und k nicht größer als n sein können
Der Wert i darf nicht größer sein als k
1 ≤ i ≤ k ≤ n
T(n) ist die Anzahl der Additionen und Vergleiche

Beispielhafte Anwendung\( \ a = 3, -5, 7, 2, -1 \ w(a,1,3) = +3-5+7 = 5 \ w(a,2,4) = -5+7+2 = 4 \ \)

Analyse von Algorithmen

Zielstellung

Einen effizienten Algorithmus zur Bestimmung der größten Teilfolge einer n-elementigen Folge bestimmen

Algorithmus 1

Vereinfachte Berechnung/Darstellung über eine Tabelle

w(a, i, k)	k = 1	k = 2	k = 3	k = 4	k = 5
i = 1	3	-2	5	7	6
i = 2	–	-5	2	4	3
i = 3	–		7	9	8
i = 4	–	–	–	2	1
i = 5	–	–	–	–	-1

Welche Operationen werden angewandt?

Additionsoperation +
Vergleichsoperation =

Wie oft muss addiert werden?

Es gibt 10 Additionsoperation (vgl. Tabelle)
Hierbei wird ausgenutzt, dass man die vorherigen Summen weiterverwenden kann: \(w(a,i,k+1) = w(a,i,k) + a[k+1]\)

w(a, i, k)	k = 1	k = 2	k = 3	k = 4	k = 5
i = 1	0	1	1	1	1
i = 2	–	0	1	1	1
i = 3	–		0	1	1
i = 4	–	–	–	0	1
i = 5	–	–	–	–	0

Wie oft muss verglichen werden?

Für jede erzeugte Folge (15 Stk.) muss einmal verglichen werden, außer für die Erste
Daher ergibt sich: 15 – 1 = 14 Vergleichsoperation

Wie sieht ein Algorithmus zur allgemeinen Bestimmung der Additionen aus?

Erste Überlegung: \(A(n) = (n-1)+(n-2)+…+1 = \sum_{n-1}^{i=1}i=\frac{n*(n-1)}{2}\)

Wie kann dies grafisch hergeleitet werden?

Es gibt n-1 Zeilen und n Spalten
Aber nur die Hälfte davon hat Additionen (grüner Bereich)
Daraus ergibt sich \( \frac{n*(n-1)}{2} \)

Wie sieht die Überlegung zu Vergleichsoperationen aus?

Für jede Zelle muss verglichen werden, außer beim ersten Mal
Daraus ergibt sich: \(V(n) = n+(n-1)+(n-2)+…-1=\sum_{n}^{i=1}\frac{n*(n+1)}{2}-1 \)

Wie viele Operationen werden nun benötigt?

\(T(n)=A(n)+V(n) = n^2 -1\)
Ohne den Trick würde die Summe aller Operationen circa n³betragen

Algorithmus 2

Wie viele Operationen werden nun benötigt?

Das maximale Element ist in der linken Teilsumme: \(z_1 = w_{max}(a,1,m)\)
Das maximale Element ist in der rechten Teilsumme: \(z_2 = w_{max}(a,m+1,n)\)
Das maximale Element beginnt in der linken Teilsumme und endet in der Rechten: \(z_{3} = z_{3}‘ + z_{3}“\)
\(z = max(z1, z_2, z_3)\)

Was sind \( z_{3}’\) und \( z_{3}“\)?

\( z_{3}’\) entspricht \(w_{rechts}(a,1,m)\) mit einem fixem Wert für m
\( z_{3}“\) entspricht \(w_{links}(a,m+1,n)\) mit einem fixem Wert für m+1
\(w_{max}(a,1,m)\) ist ungleich \(w_{rechts}(a,1,m)\)

Ein Beispiel für \( z_{3}’\): n = 8

\( z_{3}^{‚} = w_{rechts}(a,1,4) = max(w(a,1,4), w(a,2,4), w(a,3,4), w(a,4,4))\)

Wie viele Additionen benötigt man für wrechts(a,1,m)?

Es werden n-1 Additionen benötigt
\(w_{rechts}(a,1,4)\) benötigt somit 3 Additionen

Wie viele Operationen werden insgesamt benötigt?

Anzahl der Operationen am Beispiel: n=2³

Algorithmus 3

Einleitung zu Sweep-Line bzw. Scan-Line

Beispiel zu Sweep-Line: a = 3, 2, -1, 5, -3

Wie viele Operationen werden benötigt?

Beurteilung der Laufzeit von Algorithmen

Einleitung

Die vorherigen Algorithmen hatten eine von der Eingabe unabhängige Laufzeit
Etabliert ist, dass man den Vergleich am worst case durchführt
Eine Bestimmung vom average case ist nicht immer möglich
Der average case orientiert sich an einem gleichverteilten Erwartungswert von \( \frac{1}{\text{Eingaben } E_n} \)

Beispiel: Kosten für eine Sortierfunktion

Beispiel: Erzeugung von Binärzahlen

Es kommen 1, 2, n oder n + 1 Bitänderungen vor
Der worst case entspricht: n + 1

\( \ 000 \rightarrow 001 \text{ (1 Bit = n – 2 Bit)} \ 001 \rightarrow 010 \text{ (2 Bit = n – 1 Bit)} \ 010 \rightarrow 011 \text{ (1 Bit = n – 2 Bit)} \ 011 \rightarrow 100 \text{ (3 Bit = n Bit)} \ 100 \rightarrow 101 \text{ (1 Bit = n – 2 Bit)} \ 101 \rightarrow 110 \text{ (2 Bit = n – 1 Bit)} \ 110 \rightarrow 111 \text{ (1 Bit = n – 2 Bit)} \ 111 \rightarrow 1000 \text{ (4 Bit = n + 1 Bit)}\)

Wie oft tritt dies bei einer Binärzahl der Länge n auf?

1 Bit: 2^n-1 (‚0‘ hinten)
2 Bit: 2^n-2 (’01‘ hinten)
n Bit: 2⁰ = 1
n+1 Bit: 2⁰ (Alles ‚1‘) = 1

Beispiel: Schranken für n⁵