Algorithmen und Datenstrukturen Kapitel 1 0.2cm ......Boxen f ur besonders Wichtiges / f ur Interessierte Das Buch zur Vorlesung: Cormen et al. ’Introduction to Algorithms’, McGraw-Hill

EinfuhrungAlgorithmenanalyse

Algorithmen und DatenstrukturenKapitel 1

Algorithmen & Algorithmenanalyse

Frank [email protected]

14. Oktober 2015

Frank Heitmann [email protected] 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


Definition


Bemerkung




Motivation


Definition


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












Motivation












Motivation












Motivation












Motivation












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










Motivation










Motivation










Motivation










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

Aber:

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 (√

n)

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 (√

n)

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

Satz

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

Satz

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→∞

1

2− 3

n=

1

2

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→∞

1

2− 3

n=

1

2







Satz / Definition

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

Beispiel


limn→∞

1/2n2 − 3n

n2= lim

n→∞

1

2− 3

n=

1

2






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

Satz

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





Satz


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







Satz


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







Satz


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







Satz


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







Satz


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







Satz


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







Satz


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







Satz


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






Weitere wichtige Eigenschaften

Satz

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.





Satz

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








Satz

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








Satz

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








Satz

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








Satz

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

Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)

Sei f ∈ O(h1) und g ∈ O(h2), dann gibt es c , n0, so dass f (n) ≤ c ·h1(n) ∀n ≥ n0 und ebenso c ′, n′0, so dass g(n′) ≤ c ′·h2(n′) ∀n′ ≥ n′0.Daraus folgt f (n′′)·g(n′′) ≤ c ·c ′ ·h1(n′′)·h2(n′′) ∀n′′ ≥ max(n0, n′0),also f · g ∈ O(h1 · h2).





Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)






Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)






Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)






Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)






Satz

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

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

3 f ∈ O(h1), g ∈ O(h2)⇒ f · g ∈ O(h1 · h2)

Beweis (fur 3.)





Zur Ubung

Zur Ubung

Formaler Nachweis der obigen Eigenschaften (ubt dasFormale).

Sei g eine unserer ’ublichen Funktionen’. Man uberlege sichfur jedes X ∈ O,Ω,Θ, o, ω ein f mit f ∈ X (g) (bautIntuition auf).




Algorithmus 1: Lineare Suche

Algorithmus 9 Algorithmus 1


Analyse

Laufzeit ist linear in der Lange n des Arrays, d.h. in O(n) odergenauer sogar in Θ(n). (Korrektheit ist noch zu zeigen. Dazuspater mehr...)




Algorithmus 1: Lineare Suche

Algorithmus 10 Algorithmus 1


Analyse

Laufzeit ist linear in der Lange n des Arrays, d.h. in O(n) odergenauer sogar in Θ(n). (Korrektheit ist noch zu zeigen. Dazuspater mehr...)




Algorithmus 2: Fakultat

Algorithmus 11 fac(n)

1: res = 12: for i = 1 to n do3: res = res · i4: end for5: return res

Analyse

Die Laufzeit ist in O(n). Aber Achtung!

Dies ist exponentiell inder Große der Eingabe! Diese ist namlich nur in O(log n).







Analyse

Die Laufzeit ist in O(n). Aber Achtung!

Dies ist exponentiell inder Große der Eingabe! Diese ist namlich nur in O(log n).







Analyse

Die Laufzeit ist in O(n). Aber Achtung! Dies ist exponentiell inder Große der Eingabe! Diese ist namlich nur in O(log n).




Vorgehen

Vorgehen, wenn wir einen Algorithmus analysieren:

1 Uberlegen bzgl. welcher Kenngroße der Eingabe wir messenwollen. Diese kann sich von der Große der Eingabeunterscheiden! (Beispiel: Anzahl Knoten eines Graphen).

2 Laufzeit/Speicherbedarf bzgl. dieser Kenngroße ausdrucken.

3 Nochmal uberlegen, ob dies die Aussage des Ergebnissesverfalscht (so wie bei der Fakultatsberechnung eben).

⇒ I.A. sollte sich die eigentliche Eingabegroße leicht durch dieKenngroße ausdrucken lassen und der Unterschied sollte nichtzu groß sein.

+ Beim Graphen mit n Knoten ist die Adjazenmatrix in O(n2).− Ist eine Zahl n die Eingabe, so ist die Eingabegroße in O(log n).

Eine Laufzeit von O(n) ware also exponentiell in der Eingabe!




Algorithmus 3: Bestimmung des Maximums


Analyse

Laufzeit ist linear in der Lange n des Arrays, d.h. in O(n) odergenauer sogar in Θ(n).




Algorithmus 3: Bestimmung des Maximums


Analyse

Laufzeit ist linear in der Lange n des Arrays, d.h. in O(n) odergenauer sogar in Θ(n).




Algorithmus 4: MaxSort



Laufzeit ist in O(n2).




Algorithmus 4: MaxSort



Laufzeit ist in O(n2).




Algorithmus 5: InsertionSort



Laufzeit ist ebenfalls in O(n2).




Algorithmus 5: InsertionSort



Laufzeit ist ebenfalls in O(n2).




Algorithmus 6: Binare Suche




Laufzeit ist in O(log n).




Algorithmus 6: Binare Suche




Laufzeit ist in O(log n).




Algorithmus 7: Brute-Force-Algorithmen

Das Mengenpartitionsproblem

Gegeben sei eine Menge S ⊆ N. Gesucht ist eine Menge A ⊆ S , sodass

∑x∈A x =

∑x∈A x gilt.

Algorithmus 22 Suchraum durchsuchen

1: for all A ⊆ S do2: if

∑x∈A x =

∑x∈A x then

3: return true4: end if5: end for6: return false

Laufzeit ist in O(2|S |).




Algorithmus 7: Brute-Force-Algorithmen

Das Mengenpartitionsproblem

Gegeben sei eine Menge S ⊆ N. Gesucht ist eine Menge A ⊆ S , sodass

∑x∈A x =

∑x∈A x gilt.

Algorithmus 23 Suchraum durchsuchen

1: for all A ⊆ S do2: if

∑x∈A x =

∑x∈A x then

3: return true4: end if5: end for6: return false

Laufzeit ist in O(2|S |).




Eine kleine Warnung zum Schluss

Wichtige Anmerkung

Die O-Notation ’verschluckt’ Konstanten. Wenn die zu gross/kleinsind, dann kann dies das Ergebnis verfalschen! In dem Fall ist danneine genauere Analyse (ohne O-Notation) notig. I.A. hat sich dieO-Notation aber bewahrt, weil Extreme wie 106 · n und 10−10 · 2nin der Praxis kaum vorkommen.Kurz: O(2n) ist nicht zwingend immer schlimmer als O(n) aber auflange Sicht (d.h. bei wachsenden Eingabelangen) auf jeden Fallund im Allgemeinen (und bei allem, was einem so i.A. in der Praxisbegegnet) ist O(2n) eben doch schlimmer als O(n).




Sequentielle Algorithmen - Zusammenfassung

Ein paar Merkregeln fur die bisherigen Laufzeiten:

Konstant - Selten. Es wird nicht mal die ganze Eingabebetrachtet! - Aber Grundoperationen kosten nur konstant viel!

Logarithmisch - Bei wiederholten Halbierungen oder wennman mit der Hohe eines Baumes arbeitet.

Lineare Laufzeiten, wenn man sich jedes Element der Eingabeeinmal (oder: eine konstante Anzahl von Malen) ansieht.

Quadratisch - jedes Element mit jedem anderen vergleichen.

Hohere Polynome - ?

Exponentiell - wenn man jede Moglichkeit durchprobiert.










Hohere Polynome - ?











Hohere Polynome - ?











Hohere Polynome - ?











Hohere Polynome - ?











Hohere Polynome - ?





Zusammenfassung

Begriffe: Datentyp, Datenstruktur, Algorithmus

Zeit- und Platzkomplexitat (’gute’ Algorithmen), wobei wirdas uniforme Kostenmaß nutzen (jeder (elementare) Schritteine Zeiteinheit, jede (elementare) Variable eine Platzeinheit)

Zwei Definitionen fur die O-Notation (und Verwandte)

Wichtige Eigenschaften der O-Notation

Wichtige Funktionen und ihre Klassifizierung bzgl. derO-Notation

Lineares Suchen und Binares Suchen

MaxSort und InsertionSort




Themen der Vorlesung

Thema 2

Wir untersuchen den Zeit- und Platzbedarf von Algorithmen, wobeiwir das uniforme Kostenmaß nutzen (jeder (elementare) Schritt eineZeiteinheit, jede (elementare) Variable eine Platzeinheit). Zeit- undPlatzbedarf wird abhangig von der Lange n der Eingabe gezahlt.Hierzu nutzen wir Funktionen f : N→ N, bzw. f : N→ R.

Thema 1 & 3

Weitere (Ober-)Themen der Vorlesung sind bekannte Algorithmenfur Probleme lesen, verstehen und anwenden zu konnen, sowie neueAlgorithmen entwerfen, deren Korrektheit beweisen und ihre Laufzeitanalysieren zu konnen.




Themen der Vorlesung

Thema 2

Wir untersuchen den Zeit- und Platzbedarf von Algorithmen, wobeiwir das uniforme Kostenmaß nutzen (jeder (elementare) Schritt eineZeiteinheit, jede (elementare) Variable eine Platzeinheit). Zeit- undPlatzbedarf wird abhangig von der Lange n der Eingabe gezahlt.Hierzu nutzen wir Funktionen f : N→ N, bzw. f : N→ R.

Thema 1 & 3

Weitere (Ober-)Themen der Vorlesung sind bekannte Algorithmenfur Probleme lesen, verstehen und anwenden zu konnen, sowie neueAlgorithmen entwerfen, deren Korrektheit beweisen und ihre Laufzeitanalysieren zu konnen.




Ausblick: Eine andere Art von Algorithmen


1: if n == 0 then2: return 13: else4: return n · fac(n − 1)5: end if

Dies ist ein rekursiver Algorithmus... unsere bisherigen Technikensind hier bei der Analyse wenig hilfreich.




Ausblick: Eine andere Art von Algorithmen


1: if n == 0 then2: return 13: else4: return n · fac(n − 1)5: end if

Dies ist ein rekursiver Algorithmus... unsere bisherigen Technikensind hier bei der Analyse wenig hilfreich.




Ausblick

Nachstes Mal:

Rekurrenzgleichungen

Korrektheit von Algorithmen

Dabei: Weiteres zu Suchen und Sortieren

Datenstrukturen


Documents

Algorithmen und Datenstrukturen Kapitel 1 0.2cm ......Boxen f ur besonders Wichtiges / f ur Interessierte Das Buch zur Vorlesung: Cormen et al. ’Introduction to Algorithms’, McGraw-Hill