ADS: Algorithmen und Datenstrukturen 1 - Teil Fragestunde · Boyer-Moore: Algorithmus f ur jedes...

transcript

ADS: Algorithmen und Datenstrukturen 1Teil Fragestunde

Peter Stadler & Christian Honer zu Siederdissen

BioinformatikInstitut fur Informatik

Universitat Leipzig

04. Februar 2020[Letzte Aktualisierung: 17/02/2020, 10:34]

1 / 28

EVALUATION

Tutorium zum Modul „ADS 1“

bei Fragen zum Projekt:

cspeicher@informatik.uni-leipzig.de (Claudia Speicher, Projektleitung)

Burokratie: Abholen der Ubungszettel

Wichtig fur alle die noch Punkte zum Bestehen benotigen!

noch nicht abgeholte Ubungszettel konnen abgeholt werden

am Freitag, 7.Februar 2020, 10:50 Uhr

in Raum SG 3-13, Seminargebaude bei Thomas Gatter

Achtung: punktlich sein!

2. Termin:

Montag, 10.Feruar 2020, 10:15 Uhr

vor Raum R-109, Hartelstrasse 16-18

Stadler, Honer zu Siederdissen (Leipzig) ADS 1, VFragestunde 04. Februar 2020 2 / 28

Quick-Sort I

[Hoare, 1962]; auch als Partition-Exchange-Sort bezeichnet

Sortieren durch Austauschen mittels Divide-and-Conquer:

Bestimmung eines Pivot-Elementes x ∈ L

Zerlegung der Liste in zwei Teillisten L1 und L2 durch Austauschen,so daß linke (rechte) Teilliste L1 (L2) nur Schlussel enthalt, die kleiner(großer oder gleich) als x sind

< −−−L1 −−− > x < −−−L2 −−− >

Rekursive Sortierung der Teillisten, bis nur noch Listen der Lange 1verbleiben

Quick-Sort II

Realisierung der Zerlegung:

Duchlauf des Listenbereiches von links uber Indexvariable i , solangebis L[i ] ≥ x vorliegt

Duchlauf des Listenbereiches von rechts uber Indexvariable j , solangebis L[j ] ≤ x vorliegt

Austausch von L[i ] und L[j ]

Fortsetzung der Durchlaufe bis i > j gilt

Quick-Sort Algorithmus

Algorithmus qsort(A,l,r) sortiert die A[l] bis A[r]:

qsort(A,l,r)

if(r<=l) return // Fertig?

i=l; j=r // Initialisieren:

piv = A[(l+r)/2] // Pivot-Element

do // Schleife

while(A[i]<piv) i++ // Links suchen

while(A[j]>piv) j-- // Rechts suchen

if(i<=j)

swap(A[i],A[j]) // Tausche

i++; j--

while (i<=j) // Schleifenende

qsort(A,l,j) // Rekursive Aufrufe

qsort(A,i,r)

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde i, 1

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde j, 8

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde j, 7

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 58, 23, 44, 91, 11, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

swap i, 1 mit j, 7, i + +, j −−

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 58, 23, 44, 91, 11, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde i, 2

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 58, 23, 44, 91, 11, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde j, 6

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

swap i, 2 mit j, 6, i + +, j −−

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde i, 3

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde i, 4

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde j, 5

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

finde j, 4

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23, 44, 91, 58, 67, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

swap i, 4 mit j, 4, i + +, j −−

Quick-Sort Beispiel

Berechne Q(A,l,r)

67, 58, 23, 44, 91, 11, 30, 54

30, 11, 23︸︷︷︸Q(A,l ,j)

, 44, 91, 58, 67, 54︸︷︷︸Q(A,i ,r)

Q(A,1,j==3) und Q(A,i==5,8)

Quick-Sort: Eigenschaften

In-situ-Verfahren

nicht stabil

Kosten am geringsten, wenn Teillisten stets gleichlang sind, d.h. wenndas Pivot-Element dem mittleren Schlusselwert (Median) entspricht

Halbierung der Teillisten bei jeder Zerlegung→ Kosten O(n log n)

Worst-Case: Liste der Lange k wird in Teillisten der Langen 1 undk − 1 zerlegt (z.B. bei bereits sortierter Eingabe und Wahl des erstenoder letzten Elementes als Pivot-Element)→ Kosten O(n2)

Quick-Sort: Eigenschaften

Wahl des Pivot-Elementes ist von entscheidender Bedeutung. SinnvolleMethoden sind:

mittleres Element

Mittlerer Wert von k Elementen (z.B. k = 3) → bei fast allenEingabefolgen konnen Kosten in der Großenordnung n log n erzieltwerden

Zahlreiche Variationen von Quick-Sort(z.B. Behandlung von Duplikaten, Umschalten auf elementaresSortierverfahren fur kleine Teillisten)

Boyer-Moore

Vergleich des Musters von rechts nach links, um bei Mismatch Mustermoglichst weit verschieben zu konnen

Nutzung von im Suchmuster vorhandenen Informationen,insbesondere vorkommenden Zeichen und Suffixen

Vorkommens-Heuristik (“bad character heuristic”)

Textposition i wird mit Muster von hinten beginnend verglichen;Mismatch an Muster-Position j fur Textsymbol cwenn c im Muster nicht vorkommt (v.a. bei kurzen Mustern sehrwahrscheinlich), kann Muster hinter c geschoben werden, also um jPositionenwenn c vorkommt, kann Muster um einen Betrag verschoben werden,der der Position des letzten Vorkommens des Symbols im SuchmusterentsprichtVerschiebeumfang kann fur jeden Buchstaben des Alphabets vorab aufMuster bestimmt und in einer Tabelle vermerkt werden

Boyer-Moore: Algorithmus

fur jedes Symbol c des Alphabets wird die Position seines letztenVorkommens im Muster gespeichert ⇒ last[c]

last[c] := 0, falls das Symbol c nicht im Muster vorkommt

fur Mismatch an Musterposition j > last[c], verschiebt sich derAnfang des Musters um j − last[c] Positionen (sonst nur um eine Pos.)

while(i+m-1<=n)

while( (j>=1)&&(q[j]==t[i+j-1]) ) j--;

if( j==0 ) return i; /* match */

else // mismatch an Musterpos. j

if (last[ t[i+j-1] ] > j) i=i+1;

else i = i + j-last[ t[i+j-1] ]; # Korrigiert!

return -1; /* mismatch */

123456

q: ABRAKA

last A B K R .... C D E ...

6 2 5 3 0 0 0

1234567890123456

t: ABRBXABBAKABRAKA

ABRAKA | | <- kein ’X’: i := i+j-last[t[i+j-1]]

| | = 1+5-last[t[1+5-1]]

| | = 1+5-last[X]=1+5-0

ABRAKA| <- B/=R: i := 6+3-last[t[6+3-1]]

| = 6+3-last[B]=6+3-2

ABRAKA <- B/=A: i := 7+6-last[t[7+6-1]]

= 7+6-last[B]=7+6-2

ABRAKA

Boyer-Moore: Komplexitat

fur große Alphabete/kleine Muster wird meist O(n/m) erreicht, d.h.zumeist ist nur jedes m-te Zeichen zu inspizieren

Worst-Case jedoch O(n ×m)

Boyer-Moore: Verbesserungen

Match-Heuristik (”good suffix heuristic”)

Suffix s des Musters stimmt mit Text uberein

Fall 1: falls s nicht noch einmal im Muster vorkommt, kann Musterum m Positionen weitergeschoben werden

Fall 2: es gibt ein weiteres Vorkommen von s im Muster: Muster kannverschoben werden, bis dieses Vorkommen auf den entsprechendenTextteil zu s ausgerichtet ist

Fall 3: Prafix des Musters stimmt mit Endteil von s uberein:Verschiebung des Musters bis ubereinstimmende Teile ubereinanderliegen

Linear Worst-Case-Komplexitat O(n + m)

Gefadelte Binarbaume II / Zeiger

Losung 2: Vermeidung von Redundanz

Eine zweite Art der Fadelung kommt ohne zusatzliche Zeiger aus underfordert daher geringeren Speicherplatzaufwand. Die Algorithmen werdenlediglich geringfugig komplexer.

Beobachtung 1: Binarbaum mit n Knoten hat n+1 freie Zeiger (null)

Beobachtung 2: fur die Zwischenordnung konnen Fadenzeiger ininneren Knoten durch Folgen von Baumzeigern ersetzt werden

Idee: Benutze freie Zeiger und Baumzeiger fur Fadelung

pro Knoten zusatzliche Variablen Lfaden, Rfaden statt Lkind, Rkind

zeigen auf linken bzw. rechten Nachbarn in Durchlaufreihenfolge.

Achtung: Normale Baumzeiger mussen von Fadelzeigernunterschieden werden.

Algorithmus fur die Inorder-Traversierung

Start bei Wurzelknoten

Schleife bis der Knoten rechts außen erreicht ist:

Solange wie moglich nach links verzweigen

Knoten ausgeben

Falls Knoten Rfaden hat:

Rfaden einen Schritt folgen

Knoten ausgeben

Sonst falls Knoten rechten Sohn hat:

einen Schritt nach rechts verzweigen

Komplexitat von Algorithmen

Komplexitat: Maß fur Kosten eines Algorithmus

Bedeutung: Komplexitat hangt nur vom Algorithmus ab; unabhangigvon ubrigen Faktoren, die Rechenzeit und Hardwarebedarf beeinflussen

Bestimmung der KomplexitatNicht: Messungen auf einer bestimmten MaschineSondern: Aufwandsbestimmungen fur idealisierten Modellrechner (Bsp.:Random-Access-Maschine oder RAM)Abstraktes Komplexitatsmaß zur asymptotischen Kostenabschatzung inAbhangigkeit von Problemgoße/Eingabegroße n

abstrakt ≡ unabhangig von konkreter Maschine (konstanter Faktor)asymptotisch ≡ muss nur fur große Probleme gelten

Best Case, Average Case, Worst Case

Komplexitat hangt ab

von Eingabegroße; z.B. Anzahl der Datensatze, uber die gesuchtwerden sollaußerdem: von weiteren Eigenschaften der Eingabe; z.B.Reihenfolge der Datensatze (unsortiert – grob vorsortiert – sortiert)

Meist Abschatzung der worst case Komplexitat, d.h. unter Annahmeder fur den Algorithmus ungunstigsten Eingabe der jeweiligen Große(z.B. bestimmte Reihenfolge)

Analyse der average case Komplexitat oft viel schwerer;best case weniger interessant.

Obere Abschatzung asymptotischer Kosten

Meist Abschatzung oberer Schranken: Groß-Oh-Notation

Beispiel: Die asymptotische Komplexitat T (n) ei-nes Algorithmus ist durch die Funktion f (n) = n2

nach oben beschrankt, wenn es Konstanten n0und c > 0 gibt, so daß fur alle Werte von n > n0gilt:

T (n) ≤ c · n2

man sagt “T (n) ist in O(n2)”, in Zeichen T (n) ∈O(n2) oder einfach T (n) = O(n2) (oder im In-formatikerslang: “der Algo hat quadratische Kom-plexitat”). n

Allgemeine Definition

Definition

Sei f : N→ R eine Funktion. Dann ist

O(f ) = g |∃c > 0, ∃n0 > 0 : ∀n ≥ n0 : g(n)≤cf (n)

die Menge der Funktionen der Großenordnung f .

... In Worten:O(f ) is die Menge der Funktionen die asymptotisch nicht schnellerwachsen als f .

Beispiele fur Groß-Oh Definition

O(f ) = g |∃c > 0, ∃n0 > 0 : ∀n ≥ n0 : g(n) ≤ cf (n)

Beispiel. T (n) = 6n4 + 3n2 − 7n + 42 log n + sin cos(2n)

Behauptung: T (n) ∈ O(n4)

Beweis: Fur n ≥ 1 gilt: n4 ≥ n3 ≥ n2 ≥ n ≥ log n undn4 ≥ 1 ≥ sin(irgendwas). Also ist(6 + 3 + 7 + 42 + 1)n4 auf jeden Fall großer als T (n).

Damit folgt die Behauptung aus ∀n ≥ 1 : T (n) < 59f (n).

Alles klar?

Dann: Warum giltg(n) ∈ O(n) ⇒ g(n) ∈ O(n log n) ⇒ g(n) ∈ O(n2)?

Untere Schranken

So wie T (n) ∈ O(f ) eine obere Schranke ausdruckt, beschreibtT (n) ∈ Ω(f ) eine untere Schranke.

g ∈ Ω(f ) bedeutet, dass g (asymptotisch und in der Großenordnung)mindestens so stark wachst wie f .

Definition

Ω(f ) = h|∃c > 0, ∃n0 > 0 : ∀n > n0 : h(n) ≥ cf (n)

Exakte Schranke (d.h., nach oben und unten)

Gilt sowohl g ∈ O(f ) als auch g ∈ Ω(f ) schreibt man g ∈ Θ(f ).

Also:g ∈ Θ(f ) bedeutet: die Funktion g verlauft fur hinreichend große n imBereich [c1f , c2f ] mit geeigneten Konstanten c1 und c2.

Definition

Θ(f ) = g |∃c1, c2 > 0, ∃n0 > 0 : ∀n ≥ n0 : c1f (n)≤g(n)≤c2f (n)

Satz: Ist T (n) ein Polynom vom Grad p, dann ist T (n) ∈ Θ(np)Wachstumsordnung = hochste Potenz

Wichtige Wachstumsfunktionen

O(1) konstante Kosten

O(log n) logarithmisches Wachstum

O(n) lineares Wachstum

O(n log n) n log n-Wachstum

O(n2) quadratisches Wachstum

O(n3) kubisches Wachstum

O(2n) exponentielles Wachstum

O(n!) Wachstum der Fakultatn! = 1 · 2 · 3 · · · · · (n − 1) · n

Vergleich der Wachstumsfunktionen

Das asymptotische Wachstumsverhalten ist unabhangig von einermultiplikativen Konstante!

Das Mastertheorem

Allgemeines Theorem zur Losung von Funktionalgleichungen(Rekursionsgleichungen) der Form

T (n) = aT(nb

)+ g(n), a ≥ 1, b > 1

Warum konnen wir i.d.R. T (1) = 1 annehmen?

Funktionalgleichung beschreibt algorithmische Strategie“Divide-and-Conquer”:

Zerlege Gesamtproblem in gleich große Teilprobleme der Große n/b.

Fur Gesamtproblem lose a solche Teilprobleme.

Fur Zerlegung und Kombination der Teillosungen entstehen jeweilsOverhead-Kosten g(n).

Das Mastertheorem — Polynomialer Overhead

Es gibt verschieden geformte Losungen je nach Verhalten von g(n).

Sei jetzt g(n) polynomial, d.h. g(n) = Θ(nk):

T (n) = aT(nb

)+ Θ(nk), a ≥ 1, b > 1

Dann unterscheide 3 Falle:

T (n) =

Θ(nk) falls a < bk

Θ(nk log n) falls a = bk

Θ(nlogb(a)) falls a > bk

Das Mastertheorem — Beispiele

Sei wieder g(n) polynomial, g(n) = Θ(nk).

Setze k = 2 und b = 3 und betrachte Beispiele fur a

a = 8 T (n) = 8T(n3

)+ Θ(n2) ⇒ T (n) = Θ(n2)

a = 9 T (n) = 9T(n3

)+ Θ(n2) ⇒ T (n) = Θ(n2 log2 n)

a = 10 T (n) = 10T(n3

)+ Θ(n2) ⇒ T (n) = Θ(nlog3 10)

Zur Erinnerung: T (n) =

Θ(nk) falls a < bk

Θ(nk log n) falls a = bk

Θ(nlogb(a)) falls a > bk

Das Mastertheorem — allgemein

Setze u := logb(a). (Idee: die Falle scheiden sich an nu)

Im Fall ohne Overhead-Kosten, d.h. g(n) = 0, gilt T (n) = Θ(nu).

Allgemeine Losung

T (n) = Θ(nu), falls g(n) = O(nu−ε) fur ein ε > 0

T (n) = Θ(nu log n), falls g(n) = Θ(nu)

T (n) = Θ(g(n)), falls g(n) = Ω(nu+ε) und ag(nb ) ≤ cg(n)fur ein ε > 0

ADS: Algorithmen und Datenstrukturen 1 - Teil Fragestunde · Boyer-Moore: Algorithmus f ur jedes...

Documents