Algorithmen und Datenstrukturen Kapitel 1 0.2cm ......Boxen f ur besonders Wichtiges / f ur...

EinfuhrungAlgorithmenanalyse

Algorithmen und DatenstrukturenKapitel 1

Algorithmen & Algorithmenanalyse

Frank Heitmannheitmann@informatik.uni-hamburg.de

14. Oktober 2015

Frank Heitmann heitmann@informatik.uni-hamburg.de 1/48

Der Sprung ins Wasser...

Worum geht es bei

Algorithmen und Datenstrukturen

Und warum brauch ich das?!

Was nutzt das?

Spaß!

Grob abschatzen, ob etwas uberhaupt moglich ist.

Grob abschatzen, wie teuer etwas wird/werden kann.

Losungsvorschlage und deren Kosten verstehen.

Losungen selbst erarbeiten konnen!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Was nutzt das?

Spaß!

Abstrahieren!

Organisatorisches 1

Zur Vorlesung:

Immer Mittwochs in Horsaal A Chemie

0915 - 1045 Vorlesung mit Lecture2Go-Aufzeichnung1045 - 1100 Pause1100 - 1145 Wiederholung, Ubung, Vertiefung, ...

Boxen fur besonders Wichtiges / fur Interessierte

Das Buch zur Vorlesung:

Cormen et al. ’Introduction to Algorithms’, McGraw-Hill.

Oder jedes andere Algorithmen-Buch (+Folien)

Organisatorisches 2

Zu den Ubungsgruppen und Ubungszetteln:

Beginn diesen Mittwoch. Einige Besonderheiten:

Gruppe 01 und 04 am ZBH in Raum 16Gruppe 03 startet erst um 1240 Uhr (bis 1410)Gruppe 04 startet um 1400 Uhr (bis 1530)

Neuen Aufgabenzettel alle zwei Wochen i.A. Mo-Mi

Bearbeiten in 2er- oder 3er-Gruppen.

Abgabe ca. zwei Wochen spater am Montag bis 16 Uhr in dieAbgabebox im 1. Stock von Haus C (vor C-201).

Besprechung in den Ubungen in der Woche.

Alle Gruppenmitglieder mussen den eigenen Losungsvorschlagprasentieren konnen.

50% der Punkte aller Zettel sind notig.

Motivation

Los ...

Motivation

Begriff: Datentyp & Datenstruktur

Definition

Ein Datentyp ist eine Menge von Werten (z.B. N) undOperationen darauf (z.B. +).

Definition

Bei einer Datenstruktur sind die Daten zusatzlich in bestimmterWeise angeordnet und in bestimmter Weise wird Zugriff undVerwaltung ermoglicht. (Beispiele: Array, Liste, Stack, Graph)

Bemerkung

Abstrakte Definition/Beschreibung/Darstellung erfolgt mittels Ab-strakter Datentypen/Datenstrukturen (ADT). Dabei ist die Signaturdie algebraische Spezifikation des Datentyps. Die Algebra wird alsDatentyp zur Signatur bezeichnet.

Motivation

Definition

Bemerkung

Motivation

Definition

Bemerkung

Motivation

Ein Problem...

Folgendes Problem: Gegeben sei eine (lange) Liste mit Namen. Wirwollen herausfinden ob Max Mustermann auf der Liste steht.

Wie machen wir das?

Wie machen wir das algorithmisch?

Und was ist noch mal ein Algorithmus?

Motivation

Ein Problem...

Wie machen wir das?

Motivation

Ein Problem...

Wie machen wir das?

Motivation

Ein Problem...

Wie machen wir das?

Motivation

Begriff: Algorithmus

Definition

Ein Algorithmus ist ein endlich und prasize beschriebenesVerfahren, das Eingabewerte in Ausgabewerte umwandelt. Es ist(i.A.) deterministisch und der Ausgang ist determiniert. Dieeinzelnen Schritte sind zudem elementar/atomar und effektivausfuhrbar. Meist wird noch die Termination sowie die Korrektheitdes Verfahrens verlangt (beides muss bewiesen werden!). I.A. sollein Algorithmus ein Problem losen. Eine Instanz ist dabei einemogliche Eingabe (bspw. zwei Zahlen, die addiert werden sollen).

Bemerkung

Wir benutzen nachfolgend ubliche Pseudocode-Bausteine und Kon-ventionen. (for, while, Zuweisung, if-then, case, ...)

Motivation

Begriff: Algorithmus

Definition

Ein Algorithmus ist ein endlich und prasize beschriebenesVerfahren, das Eingabewerte in Ausgabewerte umwandelt. Es ist(i.A.) deterministisch und der Ausgang ist determiniert. Dieeinzelnen Schritte sind zudem elementar/atomar und effektivausfuhrbar. Meist wird noch die Termination sowie die Korrektheitdes Verfahrens verlangt (beides muss bewiesen werden!). I.A. sollein Algorithmus ein Problem losen. Eine Instanz ist dabei einemogliche Eingabe (bspw. zwei Zahlen, die addiert werden sollen).

Bemerkung

Wir benutzen nachfolgend ubliche Pseudocode-Bausteine und Kon-ventionen. (for, while, Zuweisung, if-then, case, ...)

Motivation

... eine Losung

Algorithmus 1 Lineare Suche

1: for i = 0 to n do2: if a[i ] == max mustermann then3: return true4: end if5: end for6: return false

Ist diese Losung gut?

Geht das besser?

Motivation

... eine Losung

Ist diese Losung gut?

Geht das besser?

Motivation

und eine andere Losung

Algorithmus 3 Binare Suche

1: while first ≤ last ∧ idx < 0 do2: m = first + ((last − first)/2)3: if a[m] < p then4: first = m + 15: else if a[m] > p then6: last = m − 17: else8: idx = m9: end if

10: end while11: return idx

Ist das besser?Welche Voraussetzungen haben wir hier?

Motivation

und eine andere Losung

Ist das besser?Welche Voraussetzungen haben wir hier?

Motivation

Sortieren

Definition (Das Sortierproblem)

Eingabe: Eine Sequenz < a1, a2, . . . , an > von n Zahlen.Gesucht: Eine Permutation < a′1, a′2, . . . , a′n > der Eingabesequenzmit a′1 ≤ a′2 ≤ . . . ≤ a′n.

Anmerkung

Ob die Reihenfolge zweier Elemente ai , aj (i < j) mit ai = ajbeibehalten werden soll oder nicht, ist nicht gesagt. Bleibt sieerhalten, d.h. ist a′p = ai , a′q = aj und p < q, so nennt man dasVerfahren stabil.Ferner heißt ein Sortierverfahren in-place (oder in situ), wenn derzusatzlich benotigte Speicherbedarf unabhangig von der gegebenenSequenz ist.

Motivation

Sortieren

Definition (Das Sortierproblem)

Eingabe: Eine Sequenz < a1, a2, . . . , an > von n Zahlen.Gesucht: Eine Permutation < a′1, a′2, . . . , a′n > der Eingabesequenzmit a′1 ≤ a′2 ≤ . . . ≤ a′n.

Anmerkung

Ob die Reihenfolge zweier Elemente ai , aj (i < j) mit ai = ajbeibehalten werden soll oder nicht, ist nicht gesagt. Bleibt sieerhalten, d.h. ist a′p = ai , a′q = aj und p < q, so nennt man dasVerfahren stabil.Ferner heißt ein Sortierverfahren in-place (oder in situ), wenn derzusatzlich benotigte Speicherbedarf unabhangig von der gegebenenSequenz ist.

Motivation

Bedeutung des Sortierens

Daten zu Sortieren ist ein fundamentales Problem:

Manchmal ist Sortieren das Wesen der Anwendung

Sortieren als Vorstufe (z.B. fur das Suchen)

Sortieren als Unterroutine (z.B. Painter’s Algorithm)

Viele verschiedene (Algorithmen-)Techniken

Beweisbarkeit einer nichttrivialen unteren Schranke

Sortiert wird standig:

Musikliste nach Kunstlern oder TitelnAnkommende Pakete uber die Datenleitung...

Motivation

Pause to Ponder...

Wem fallt ein Brute-Force-Algorithmus zum Sortieren ein?

Motivation

Sortieren mit Maximumbestimmung (MaxSort)

Algorithmus 5 Sortieren mit Max

1: for i = n downto 1 do2: idx = max(A)3: B[i ] = A[idx ]4: A[idx ] = 05: end for6: return B

Motivation

Bestimmung des Maximums

Algorithmus 6 Find Maximum1: max = 12: for i = 2 to n do3: if a[i ] > a[max ] then4: max = i5: end if6: end for7: return max ;

Motivation

InsertionSort: Die Idee

Beim Sortieren durch Einfugen (InsertionSort) wird ahnlich wiebeim Spielkarten sortieren vorgegangen:

Starte mit der leeren linken Hand

Nimm ein Karte und fuge sie an der richtigen Position in derlinken Hand ein. Dazu

Vergleiche diese neue Karte von rechts nach links mit denKarten, die schon auf der linken Hand sind.Sobald eine kleinere Karte erreicht wird, fuge ein.

⇒ Zu jedem Zeitpunkt sind die Karten auf der linken Handsortiert.

⇒ Die Karten auf der linken Hand sind jeweils die oberstenKarten des Haufens.

Motivation

InsertionSort: Der Algorithmus

Algorithmus 7 InsertionSort(A[1 . . . n])

1: for j = 2 to n do2: key = A[j ]3: i = j − 14: while i > 0 und A[i ] > key do5: A[i + 1] = A[i ]6: i = i − 17: end while8: A[i + 1] = key9: end for

Motivation

Zusammenfassung / Diskussion

Wir kennen jetzt

Lineares Suchen und binares Suchen

MaxSort und InsertionSort

Ist ein Verfahren besser als ein anderes?

Was messen wir?

Motivation

Algorithmenanalyse

Wir behandeln nachfolgend Zeit- und Platzkomplexitat. Eine(elementare) Anweisung zahlt dabei als eine Zeiteinheit. Einebenutzte (elemantare) Variable als eine Platzeinheit.

Zeit- und Platzbedarf wird abhangig von der Lange n der Eingabegezahlt. Wir arbeiten hierfur mit Funktionen f : N→ Nbzw. f : N→ R.

EinfuhrungO-Notation

Algorithmenanalyse...

Wir behandeln nachfolgend Zeit- und Platzkomplexitat (imuniformen Maß). Eine (elementare) Anweisung zahlt dabei als eineZeiteinheit. Eine benutzte (elemantare) Variable als einePlatzeinheit.

Zeit- und Platzbedarf wird abhangig von der Lange n der Eingabegezahlt. Wir arbeiten hierfur mit Funktionen f : N→ R.

O-Notation - Motivation

Wir werden nachfolgend konstante Faktoren ignorieren. Diese’verschwinden’ in der O-Notation (auch Landau-Notation).

⇒ Konzentration auf das wesentliche.

⇒ Abstrahiert von verschiedenen Rechnerarchitekturen.

⇒ Guter Vergleich von Algorithmen moglich (praxisbewahrt).

⇒ Ferner werden wir ’anfangliche Schwankungen’ ignorierenkonnen.

ABER: 5 · n und 5000 · n wird als ’im Prinzip’ gleichangesehen werden!

O-Notation - Motivation

Wir werden nachfolgend konstante Faktoren ignorieren. Diese’verschwinden’ in der O-Notation (auch Landau-Notation).

⇒ Konzentration auf das wesentliche.

⇒ Abstrahiert von verschiedenen Rechnerarchitekturen.

⇒ Guter Vergleich von Algorithmen moglich (praxisbewahrt).

⇒ Ferner werden wir ’anfangliche Schwankungen’ ignorierenkonnen.

ABER: 5 · n und 5000 · n wird als ’im Prinzip’ gleichangesehen werden!

Beware ...

Anmerkung

Der Sinn der O-Notation zur Analyse der Laufzeit und desSpeicherbedarfs von Algorithmen wird spater klarer. Gleich folgenerstmal Definitionen und Beispiele dazu, bevor die Anwendung aufAlgorithmen folgt.

O-Notation - Definition

Definition (O-Notation (und Verwandte))

O(g(n)) = f | ∃c ∈ R+∃n0 ∈ N ∀n ≥ n0 : |f (n)| ≤ c · |g(n)|Ω(g(n)) = f | ∃c ∈ R+∃n0 ∈ N ∀n ≥ n0 : |f (n)| ≥ c · |g(n)|o(g(n)) = f | ∀c ∈ R+∃n0 ∈ N ∀n ≥ n0 : |f (n)| ≤ c · |g(n)|ω(g(n)) = f | ∀c ∈ R+∃n0 ∈ N ∀n ≥ n0 : |f (n)| ≥ c · |g(n)|Θ(g(n)) = f | ∃c1, c2 ∈ R+∃n0 ∈ N ∀n ≥ n0 : c1 · |g(n)| ≤|f (n)| ≤ c2 · |g(n)|

Bemerkung

f ist dabei stets eine Funktion von N nach R, also f : N → R.(Daher uberall die Betragsstriche!) In der Literatur gibt es hierVarianten. Bei der tatsachlichen Algorithmenanalyse machen dieseaber kaum einen Unterschied.

Wichtige Funktionen

Bemerkung

Wichtige Funktionen in der Algorithmik/Algorithmenanalyse:

Konstante Funktionen

Logarithmen (log, ln)

Wurzelfunktionen (√

Polynome (beachte:√

n = n1/2)

Exponentialfunktionen (2n)

... Kombinationen davon

In welchem Zusammenhang stehen diese bzgl. der O-Notation?(⇒ Hausaufgabe!)

Wichtige Funktionen

Bemerkung

Wichtige Funktionen in der Algorithmik/Algorithmenanalyse:

Konstante Funktionen

Logarithmen (log, ln)

Wurzelfunktionen (√

Polynome (beachte:√

n = n1/2)

Exponentialfunktionen (2n)

... Kombinationen davon

In welchem Zusammenhang stehen diese bzgl. der O-Notation?(⇒ Hausaufgabe!)

Zum Logarithmus

Bemerkung

Mit log werden wir stets eine Variante des Logarithmus zur Basis 2meinen, namlich:

log(n) :=

1 , falls n ≤ 1

blog2(n)c+ 1 , sonst.

Damit ist log(n) die Lange der Binardarstellung einer naturlichenZahl n. (Die Anzahl von Speicherstellen/Schritten ist stets einenaturliche Zahl!) Andere Logarithmen werden nur selten benotigtund sind bis auf einen konstanten Faktor ohnehin gleich. DieRechengesetze wie z.B. log(x · y) = log(x) + log(y) undlog(x r ) = r · log(x) sind oft hilfreich.

O-Notation - Beispiele I

Definition (Θ - Wiederholung)

Θ(g(n)) = f | ∃c1, c2 ∈ R+∃n0 ∈ N ∀n ≥ n0 : c1 · g(n) ≤ f (n) ≤c2 · g(n)

Beispiel

Wir wollen 12n2 − 3n ∈ Θ(n2) zeigen. Wir suchen also Konstanten

c1, c2, n0, so dass

c1n2 ≤ 1

2n2 − 3n ≤ c2n2

fur alle n ≥ n0 erfullt ist. Teilen durch n2 fuhrt zu

c1 ≤1

2− 3

n≤ c2

. Dies kann man z.B. mit c1 = 28 , c2 = 1, n0 = 24 erfullen.

Beispiel

c1, c2, n0, so dass

c1n2 ≤ 1

2n2 − 3n ≤ c2n2

c1 ≤1

2− 3

n≤ c2

Beispiel

c1, c2, n0, so dass

c1n2 ≤ 1

2n2 − 3n ≤ c2n2

c1 ≤1

2− 3

n≤ c2

Beispiel

c1, c2, n0, so dass

c1n2 ≤ 1

2n2 − 3n ≤ c2n2

c1 ≤1

2− 3

n≤ c2

O-Notation - Variante

1 f (n) ∈ O(g(n))⇔ limn→∞f (n)g(n) <∞

2 f (n) ∈ o(g(n))⇔ limn→∞f (n)g(n) = 0

3 f (n) ∈ Ω(g(n))⇔ limn→∞f (n)g(n) > 0

4 f (n) ∈ ω(g(n))⇔ limn→∞f (n)g(n) =∞

Bemerkung

Mit obigen Aquivalenzen und mit Kenntnissen der Limesbildung sindeinige der unten folgenden Satze schnell zu zeigen (und evtl. schnel-ler als mit der obigen, ursprunglichen Definition).

O-Notation - Variante

1 f (n) ∈ O(g(n))⇔ limn→∞f (n)g(n) <∞

2 f (n) ∈ o(g(n))⇔ limn→∞f (n)g(n) = 0

3 f (n) ∈ Ω(g(n))⇔ limn→∞f (n)g(n) > 0

4 f (n) ∈ ω(g(n))⇔ limn→∞f (n)g(n) =∞

Bemerkung

Mit obigen Aquivalenzen und mit Kenntnissen der Limesbildung sindeinige der unten folgenden Satze schnell zu zeigen (und evtl. schnel-ler als mit der obigen, ursprunglichen Definition).

O-Notation - Beispiele II

Satz / Definition

f (n) ∈ O(g(n))⇔ limn→∞f (n)g(n) <∞

Beispiel

Wir wollen 12n2 − 3n ∈ O(n2) zeigen.

limn→∞

1/2n2 − 3n

n2= lim

n→∞

2− 3

Ahnlich zeigt man 12n2 − 3n ∈ Ω(n2) woraus das gleiche Ergebnis

wie oben folgt, wie wir gleich sehen werden.

Satz / Definition

f (n) ∈ O(g(n))⇔ limn→∞f (n)g(n) <∞

Beispiel

limn→∞

1/2n2 − 3n

n2= lim

n→∞

2− 3

Satz / Definition

f (n) ∈ O(g(n))⇔ limn→∞f (n)g(n) <∞

Beispiel

limn→∞

1/2n2 − 3n

n2= lim

n→∞

2− 3

Merkhilfe

Bemerkung

Eine kleine Merkhilfe (nicht mehr!)

f ∈ O(g) ≈ f ≤ g

f ∈ Ω(g) ≈ f ≥ g

f ∈ Θ(g) ≈ f = g

f ∈ o(g) ≈ f < g

f ∈ ω(g) ≈ f > g

Wir sagen, dass f asymptotisch kleiner gleich, großer gleich, gleich,kleiner bzw. großer ist als g , wenn f ∈ O(g), f ∈ Ω(g), f ∈Θ(g), f ∈ o(g) bzw. f ∈ ω(g) gilt.

Wichtige Eigenschaften

1 f ∈ X (g) und g ∈ X (h) impliziert f ∈ X (h)(X ∈ O,Ω,Θ, o, ω)

2 f ∈ X (f ) (X ∈ O,Ω,Θ)3 f ∈ Θ(g)⇔ g ∈ Θ(f )

Beweis (fur 1. und X = O)

Sei f ∈ O(g) und g ∈ O(h), dann gibt es c , n0, so dass f (n) ≤c · g(n) ∀n ≥ n0 und ebenso c ′, n′0, so dass g(n′) ≤ c ′ · h(n′)∀n′ ≥ n′0. Sei nun n′′0 = max(n0, n′0). Dann gelten ∀n′′ ≥ n′′0 beideUngleichungen und fur diese n′′ gilt dann f (n′′) ≤ c · g(n) ≤ c · c ′ ·h(n′′) also f (n′′) ≤ c · c ′ · h(n′′) und da c · c ′ eine Konstante ist,folgt f ∈ O(h).

2 f ∈ X (f ) (X ∈ O,Ω,Θ)3 f ∈ Θ(g)⇔ g ∈ Θ(f )

Weitere wichtige Eigenschaften

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

Sei g ∈ o(f ), dann gilt limn→∞f (n)g(n) = 0. Um g ∈ O(f ) zu zeigen,

muss limn→∞f (n)g(n) = c fur eine Konstante c gezeigt werden. Mit

c = 0 folgt dies sofort.

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

1 g ∈ O(f )⇔ f ∈ Ω(g)

2 g ∈ o(f )⇔ f ∈ ω(g)

3 g ∈ Θ(f )⇔ g ∈ O(f ) ∩ Ω(f )

4 o(f ) ⊆ O(f )

5 ω(f ) ⊆ Ω(f )

6 ω(f ) ∩ o(f ) =?

7 Ω(f ) ∩ O(f ) =?

Beweis (fur 4.)

Noch mehr wichtige Eigenschaften

1 f , g ∈ O(h)⇒ f + g ∈ O(h)

2 f ∈ O(g), c ∈ R+ ⇒ c · f ∈ O(g)