GAD-Zusammenfassung-SS2016 PDF

Preview

Summary

Grundlagen: Algorithmen und Datenstrukturen SS 2016 Es handelt sich hierbei nicht um eine Zusammenfassung, sondern mehr um einen der Folien. die Richtigkeit des Inhaltes wird keine Verantwortung Inhalt .....................................................................................................

Description

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

GAD-ZUSAMMENFASSUNG Es handelt sich hierbei nicht um eine Zusammenfassung, sondern mehr um einen Fließtext der Folien. Für die Richtigkeit des Inhaltes wird keine Verantwortung übernohmen.

In Inha ha halt lt Einführung ....................................................................................................................................................3 Abstrakte Datentypen und Datenstrukturen ...................................................................................3 Softwareentwicklung .............................................................................................................................3 Effizienz.....................................................................................................................................................3 Beispiele....................................................................................................................................................4 Effizienz ......................................................................................................................................................... 8 Eingabekodierung..................................................................................................................................8 Effizenzmessung.....................................................................................................................................9 Wachstumsrate/ -ordnung ..................................................................................................................9 Maschinenmodell ................................................................................................................................. 13 Laufzeitanalyse ..................................................................................................................................... 14 Durchschnittliche Laufzeit .................................................................................................................. 16 Erwartete Laufzeit ................................................................................................................................ 17 Datenstrukturen für Sequenzen .......................................................................................................... 20 Sequenzen ............................................................................................................................................ 20 Dynamische Felder ............................................................................................................................. 20 Doppelt verkettete Liste .................................................................................................................... 22 Einfach verkettete Liste ...................................................................................................................... 22 Stacks und Queues ............................................................................................................................. 22 Sortieret Sequenz................................................................................................................................ 23 Hashtabellen ......................................................................................................................................... 23 Sortieren ..................................................................................................................................................... 33 Einfache Verfahren ............................................................................................................................. 33 MergeSort ............................................................................................................................................. 35 Seite | 1

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Untere Schranke .................................................................................................................................. 37 QuickSort............................................................................................................................................... 37 Selektieren ............................................................................................................................................. 38 Schnelleres Sortieren .......................................................................................................................... 39 Priority Queues.......................................................................................................................................... 41 Allgemeines ........................................................................................................................................... 41 Heaps ..................................................................................................................................................... 42 Binomial Heap...................................................................................................................................... 44 Suchstrukturen ......................................................................................................................................... 47 Binärer Suchbaum .............................................................................................................................. 47 AVL-Bäume .......................................................................................................................................... 49 (a,b)-Baum ............................................................................................................................................ 52 Graphen ..................................................................................................................................................... 57 Netzwerk ............................................................................................................................................... 57 Graph ..................................................................................................................................................... 57 Graphentravesierung ......................................................................................................................... 60 Kürzeste Wege..................................................................................................................................... 66

Seite | 2

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Ei Ein nfü führ hr hrun un ungg Definition: Ein Algorithmus ist eine formale Handlungsvorschrift zur Lösung von Instanzen einer bestimmten Problemklasse Informelle Beispiele     

Kochrezept Schriftliches Rechnen Bauanleitung Weg aus einem Labyrinth Zeichnen eines Krieses

Formalisierung (Informatik) Eingabe -> Algorithmus -> Ausgabe

Abstrakte Datentypen und Datenstrukturen Abstrakter Datentyp legt fest, welche Operationen was tun (Semantik), aber nicht wie (konkrete Implementierung). Bsp.: PriorityQueue mit Operationen insert und deleteMin Datenstruktur ist ein formalisiertes Objekt zur Speicherung, Verwaltung von bzw. Zugriff auf Daten, die dabei geeignet angeordnet, kodiert und verknüpft werden. Bsp.: BinaryHeap als konkrete Implementierung von PriorityQueue.

Softwareentwicklung Probleme -> Modellierung -> Algorithmen und Datenstrukturen -> Implementierung   

Abstraktion vom genauen Problem (Vereinfachung) Geeignete Auswahl von Algorithmen/Datenstrukturen Grundsätzliche Probleme: Korrektheit, Komplexität, Robustheit/Sicherheit, aber vor allem Effizienz

Effizienz im Sinn von Laufzeit, Speicheraufwand, Festplattenzugriffen, Energieverbrauch. Kritische Beispiele:  

Riesige Datenmengen (Bioinformatik) Echzeitanwendungen (Spiele, Flugzeugsteuerung)

Ziele der Vorlesung: Grundstock an effizienten Algorithmen und Datenstrukturen für Standartproblemen. Seite | 3

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Beispiele Weg aus dem Labyrinth Es soll ein Algorithmus gefunden werden, mit welchem es möglich ist aus einem dunklen Labyrinth zu finden. 1. Versuch: mit einer Hand an der Wand entlang Problem: Inseln werden endlos umkreist.

2. Versuch: gerade bis zur Wand, der Wand folgen bis man wieder in dieselbe Richtung läuft, dann wieder gerade bis zur Wand usw. Problem Jetzt kann es vorkommen, dass wir im Kreis laufen.

Pledge-Algorithmus Zu Beginn sucht man sich eine Zielrichtung aus und folgt dieser so lange, bis man auf ein Hindernis stößt. Nun folgt man dieser Wand mittels der Rechte-Hand-Regel (1. Versuch) und addiert zu einer Konstante, welche zu Beginn auf 0 gesetzt, nach jedem Abbiegen nach rechts eins und subtrahiert eins, sobald man nach links abbiegt. Sobald man wieder bei 0 angekommen ist befolgt man nicht mehr die Rechte-Hand-Regel, sondern läuft so lange gerade aus, bis man auf ein Hindernis stößt usw.

Seite | 4

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Kreis zeichnen Wie kann ein Computer einen Kreis zeichnen?

Mit Winkelfuntion Naiver Ansatz: eine Runde wie mit dem Zirkel Problem: sin() und cos() sind teuer! Eingabe:

Radius R Pixelanzahl n

for i = 0; i < n; i++ do plot(R * cos(2π * i/n), R * sin(2π * i/n));

Mit Wurzelfunktion Schnellerer Ansatz: x² + y² + R² bzw. y = √(R² - x²) Problem: sqrt() ist auch noch relativ teuer! Eingabe:

Radius R

for x = -R; x ℕ

Problem:

T sehr schwer exakt zu bestimmen bzw. beschreiben

Lösung:

Gruppierung der Instanzen (meist nach Größe)

Eingabekodierung Bei Betrachtung der Länge der Eingabe: Vorsicht bei der Kodierung!

Beispiel: Primfaktorisierung Gegeben: Gesucht:

Zahl x Є ℕ

𝑒 Primfaktoren von x (Primzahlen p1, …, pk mit 𝑥 = ∏𝑘𝑖=1 𝑝𝑖 𝑖 )

Bekannt als hartes Problem (wichtig für RSA-Verschlüsselung!) Trivialer Algorithmus

Teste y = 2 bis ⌊√𝑥⌋ aller Zahlen, ob diese x teilen wenn ja, dann bestimme wiederholt das Ergebnis der Division bis die Teilung nicht mehr ohne Rest möglich ist. (Es müssen nur die Zahlen bis ⌊√𝑥⌋ getestet werden, da dadurch alle getestet wurden.)

Laufzeit ⌊√𝑥⌋ Teilbarkeitstest und höchstes log2 x Divisionen 



Unäre Kodierung von x (x Einsen als Eingabe): Laufzeit polynomiell bezüglich der Länge der Eingabe Binäre Kodierung von x (⌈𝑙𝑜𝑔2 𝑥⌉ Bits): Laufzeit exponentiell bezüglich der Länge der Eingabe

Beispiel: Sortieren Betrachtete Eingabegröße:  

Größe von Zahlen: Anzahl Bits bei binärer Kodierung Größe von Mengen/Folgen: Anzahl Elemente

Gegeben: Gesucht:

Folge von Zahlen a1, …, an Є ℕ

sortieret Folge der Zahlen

Größe der Eingabe: n Seite | 8

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Manchmal Betrachtung von mehr Parametern: 

Größe von Graphen: Anzahl Knoten und Anzahl Kanten

Effizenzmessung

Sein 𝐼𝑛 die Menge der Instanzen (korrekte Eingaben) der Größe 𝑛 eines Problems. Effizensmaße: 

Worst case:



Average case:



Best case:

𝑡(𝑛) = max{𝑇(𝑖) ∶ 𝑖 ∈ 𝐼𝑛 } 𝑡(𝑛) =

1 ∑ 𝑇(𝑖) |𝐼𝑛 | 𝑖∈𝐼𝑛

𝑡(𝑛) = min{𝑇(𝑖): 𝑖 ∈ 𝐼𝑛 }

(Wir stellen sicher, dass max und min existieren und dass 𝐼𝑛 endlich ist.)

Vor- und Nachteile der Maße 





Worst case: Liefert Garantie für die Effizienz des Algorithmus, evt. aber sehr pessimistische Abschätzung Average case: Beschreibt durchschnittliche Laufzeit, aber nicht unbedingt übereinstimmend mit dem „typischen Fall“ in der Praxis, ggf. Verallgemeinerung mit Wahrscheinlichkeitsverteilung Best case: Vergleich mit worst case liefert Aussage über die Abweichung innerhalb der Instanzen gleicher Größe, evt. sehr optimistisch

Exakte Formeln für t(n) sind meist sehr aufwendig bzw. nicht möglich! Betrachte asymptotisches Wachstum (𝑛 → ∞)

Wachstumsrate/ -ordnung

Wir sind an einer Abschätzung des Wachstums von 𝑓(𝑛) interessiert: 

Wenn 𝑓(𝑥) schneller wächst als 𝑔(𝑥), dann wird 𝑓(𝑥) immer irgendwann größer als 𝑔(𝑥) werden (für ausreichend große Werte von 𝑥).

Man betrachtet meistens nur die Wachstumsrate für genügend große n, da meistens Verfahren gesucht werden, welche auch für große n noch schnell sind. Kleine Daten brauchen meistens nicht lange und somit ist die Wachstumsrate für kleine n nicht so interessant.

Seite | 9

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Auf konstante Faktoren kann verzichtet werden, da unser Maschinenmodell nur eine Abstraktion von echten Computern ist und die reale Laufzeit sowieso nur bis auf konstante Faktoren bestimmt werden kann. Daher ist es meistens sinnvoll, Algorithmen mit gleicher Wachstumsrate erstmal als gelichwertig zu betrachten. Laufzeitangaben werden meistens nur durch einfache Funktionen angegeben. 



𝑓(𝑛) und 𝑔(𝑛) haben die gleiche Wachstumsrate, falls für große 𝑛 das Verhältnis durch Konstanten beschränkt ist: 𝑓(𝑛) ≤ 𝑑 ∃𝑐, 𝑑 ∈ ℝ+ ∃𝑛0 ∈ ℕ ∀𝑛 > 𝑛0 ∶ 𝑐 ≤ 𝑔(𝑛) 𝑓(𝑛) wächst schneller als 𝑔(𝑛), wenn es für alle positiven Konstanten 𝑐 ein 𝑛0 gibt, ab dem 𝑓(𝑛) ≥ 𝑐 ∗ 𝑔(𝑛) für 𝑛 ≥ 𝑛0 gilt, d.h., ∀𝑐 ∈ ℝ+ ∃𝑛0 ∈ ℕ ∀𝑛 ≥ 𝑛0 : 𝑓(𝑛) ≥ 𝑐 ∗ 𝑔(𝑛) Anders ausgedrückt: lim

𝑔(𝑛)

0→∞ 𝑓(𝑛)

=0

Beispiel

𝑛2 und 5𝑛2 − 7𝑛 haben gleiche Wachstumsrate, da für alle 𝑛 ≥ 2 1 ≤ Beide wachsen schneller als 𝑛 . 3 2

5𝑛2 −7𝑛 𝑛2

≤ 5 gilt.

Es soll eine Webseite entwickelt werden, die Benutzerdaten bearbeitet. Programm A benötigt 𝑓𝐴 (𝑛) = 140𝑛 + 500 Mikrosekunden, um 𝑛 Einträge zu bearbeite. Programm B benötigt 𝑓𝐵 (𝑛) = 𝑛2 + 20𝑛 + 2500 Mikrosekunden für 𝑛 Einträge. Eine kleine Berechnung zeigt:

Für 20 ≤ 𝑛 ≤ 100 ist 𝑛2 + 20𝑛 + 2500 ≤ 140𝑛 + 500

Die multiplikativen Konstanten 140, 1, 20 und die Additiven Konstanten 500, 2500 sind meistens schwer zu bestimmen (und abhängig von Einzelheiten der Implementierung. Oft ist nur bekannt:  

Programm A braucht 𝑎𝑛 + 𝑏 Mikrosekunden, Programm B braucht 𝑐𝑛 2 + 𝑑𝑛 + 𝑒 Mikrosekunden

mit nicht allzu großen Konstanten 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 .

Wichtig ist nun: Unabhängig von den Werten von 𝑎, … , 𝑒 gibt es immer eine Zahl 𝑛0 , sodass ab 𝑛0 Daten das Programm A schneller ist als B.

Wir sagen, dass 𝑓𝐴 (𝑛) langsamer als 𝑓𝐵 (𝑛) wächst, falls ab einem gewissen Punkt 𝑓𝐴 (𝑛) stets unter 𝑓𝐵 (𝑛) liegt. Wir führen die Groß-O-Notation ein, um diesen Sachverhalt zu formalisieren. Informell ist Ο(𝑓) die Menge der Funktionen, die langsamer oder so schnell wie 𝑓 wachsen. Seite | 10

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Asymptotische Notation Mengen zur Formalisierung des asymptotischen Verhaltens: Ο(𝑓(𝑛)) = {𝑔(𝑛): ∃𝑐 > 0: ∃𝑛0 > 0: ∀𝑛 ≥ 𝑛0 : 𝑔(𝑛) ≤ 𝑐 ∗ 𝑓(𝑛)}

Groß-O-Notation

„𝑔 wächst (bis auf einen Konstanten Faktor) höchstens so schnell wie 𝑓“

Groß-Omega-Notation

Ω(𝑓(𝑛)) = {𝑔(𝑛): ∃𝑐 > 0: ∃𝑛0 > 0: ∀𝑛 ≥ 𝑛0 : 𝑔(𝑛) ≥ 𝑐 ∗ 𝑓(𝑛)}

„𝑓 wächst (bis auf einen konstanten Faktor) höchstens so schnell wie 𝑔.“

𝜊(𝑓(𝑛)) = {𝑔(𝑛): ∀𝑐 > 0: ∃𝑛0 > 0: ∀𝑛 ≥ 𝑛0 : 𝑔(𝑛) ≤ 𝑐 ∗ 𝑓(𝑛)}

Klein-o-Notation

„𝑔 wächst echt langsamer als 𝑓.“

𝜔(𝑓(𝑛)) = {𝑔(𝑛): ∀𝑐 > 0: ∃𝑛0 > 0: ∀𝑛 ≥ 𝑛0 : 𝑔(𝑛) ≥ 𝑐 ∗ 𝑓(𝑛)}

Klein-Omega-Notation

„𝑔 wächst echt schneller als 𝑓.“

𝜃(𝑓(𝑛)) = Ο(𝑓(𝑛)) ∩ Ω(𝑓(𝑛))

Groß-Theta-Notation

𝑓(𝑛) ∈ 𝜃(𝑔(𝑛)) → „𝑓 wächst bis auf Konstante Faktoren genau so schnell wie 𝑔.“

Beispiele für Asymptotische Notation   

5𝑛2 − 7𝑛 ∈ 𝑂(𝑛2 ), 10 + 100𝑛 ∈ 𝑂(𝑛2 ), 4𝑛2 ∈ 𝑂(𝑛3 ) 𝑛2

5𝑛2 − 7𝑛 ∈ Ω(𝑛 2 ), 𝑛³ ∈ Ω(n2 ), 𝑛 𝑙𝑜𝑔(𝑛) ∈ Ω(𝑛) 5𝑛2 − 7𝑛 ∈ 𝜃(𝑛2 )

Seite | 11

Grundlagen: Algorithmen und Datenstrukturen

 

SS 2016

log(𝑛) ∈ 𝑜(𝑛), 𝑛3 ∈ 𝑜(2𝑛 ) 𝑛5 ∈ 𝜔(𝑛3 ), 22𝑛 ∈ 𝜔(2𝑛 )

Asymptotische Notation als Platzhalter

Statt 𝑔(𝑛) ∈ 𝑂(𝑓(𝑛)) schreibt man oft auch 𝑔(𝑛) = 𝑂(𝑓(𝑛))

Für 𝑓(𝑛) + 𝑔(𝑛) mit 𝑔(𝑛) ∈ 𝑜(ℎ(𝑛)) schreibt man auch 𝑓(𝑛) + 𝑔(𝑛) = 𝑓(𝑛) + 𝑜(ℎ(𝑛))

Statt 𝑂(𝑓(𝑛)) ⊆ 𝑂(𝑔(𝑛)) schreibt man auch 𝑂(𝑓(𝑛)) = 𝑂(𝑔(𝑛))

Beispiel

𝑛3 + 𝑛 = 𝑛 3 + 𝑜 (𝑛3 ) = (1 + 𝑜 (1))𝑛3 = 𝑂(𝑛 3 )

O-Notations“gleichungen“ sollten von links nach rechts gelesen werden!

Rechenregeln

Für Funktionen 𝑓(𝑛) (bzw. 𝑔(𝑛)) mit ∃𝑛0 ∀𝑛 ≥ 𝑛0 : 𝑓(𝑛) > 0 gilt    

𝑐 ∗ 𝑓(𝑛) ∈ 𝜃(𝑓(𝑛)) für jede Konstante 𝑐 > 0 𝑂(𝑓(𝑛)) + 𝑂(𝑔(𝑛)) = 𝑂(𝑓(𝑛) + 𝑔(𝑛)) 𝑂(𝑓(𝑛)) ∗ 𝑂(𝑔(𝑛)) = 𝑂(𝑓(𝑛) ∗ 𝑔(𝑛)) 𝑂(𝑓(𝑛) + 𝑔(𝑛)) = 𝑂(𝑓(𝑛)) falls 𝑔(𝑛) ∈ 𝑂(𝑓(𝑛))

Die Ausdrücke sind auch korrekt für Ω statt 𝑂. Vorsicht, der letzte heißt dann 

Ω(𝑓(𝑛) + 𝑔(𝑛)) = Ω(𝑓(𝑛)) falls 𝑔(𝑛) ∈ 𝑂(𝑓(𝑛))

Ableitungen und O-Notation

Seien f und g differenzierbar (lässt sich ableiten) Dann gilt:  Falls 𝑓 ′ (𝑛) ∈ 𝑂(𝑔′ (𝑛)), dann auch 𝑓(𝑛) ∈ 𝑂(𝑔(𝑛))  Falls 𝑓 ′ (𝑛) ∈ Ω(𝑔′ (𝑛)), dann auch 𝑓(𝑛) ∈ Ω(𝑔(𝑛))  Falls 𝑓 ′ (𝑛) ∈ 𝑜(𝑔′ (𝑛)), dann auch 𝑓(𝑛) ∈ 𝑜(𝑔(𝑛))  Falls 𝑓 ′ (𝑛) ∈ 𝜔(𝑔′ (𝑛)), dann auch 𝑓(𝑛) ∈ 𝜔(𝑔(𝑛)) Umgekehrt gilt das im Allgemeinen nicht.

Wachstumsrate von Polynomen

Sei 𝑝 ein Polynom der Ordnung 𝑘 bzgl. der Variable 𝑛, also 𝑘

Dann ist 𝑝(𝑛) ∈ Θ(𝑛𝑘 ).

𝑝(𝑛) = ∑ 𝑎𝑖 ∗ 𝑛 𝑖 𝑖=0

𝑚𝑖𝑡

𝑎𝑘 > 0

Seite | 12

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

Beweis

Zu zeige: 𝑝(𝑛) ∈ 𝑂(𝑛𝑘 ) und 𝑝(𝑛) ∈ Ω(𝑛𝑘 ) 𝑝(𝑛) ∈ 𝑂(𝑛𝑘 )

Für 𝑛 ≥ 1 gilt:

𝑘

𝑘

𝑖=0

𝑖=0

𝑝(𝑛) ≤ ∑|𝑎𝑖 | ∗ 𝑛 𝑖 ≤ 𝑛𝑘 ∑|𝑎𝑖 |

Also ist die Definition

𝑂(𝑓(𝑛)) = {𝑔(𝑛): ∃𝑐 > 0: ∃𝑛0 > 0: ∀𝑛 ≥ 𝑛0 : 𝑔(𝑛) ≤ 𝑐 ∗ 𝑓(𝑛)}

mit 𝑐 = ∑ 𝑘𝑖=0|𝑎𝑖 | und 𝑛0 = 1 erfüllt. 𝑝(𝑛) ∈ Ω(𝑛 𝑘 )

𝑘−1

𝐴 = ∑|𝑎𝑖 | 𝑖=0

Für positive 𝑛 gilt dann:

𝑝(𝑛) ≥ 𝑎𝑘 𝑛𝑘 − 𝐴𝑛𝑘−1 =

Also ist die Definition

𝑎𝑘 𝑘 𝑎𝑘 𝑛 + 𝑛 𝑘−1 ( 𝑛 − 𝐴) 2 2

Ω(𝑓(𝑛)) = {𝑔(𝑛): ∃𝑐 > 0: ∃𝑛𝑜 > 0: ∀𝑛 ≥ 𝑛𝑜 : 𝑔(𝑛) ≥ 𝑐 ∗ 𝑓(𝑛)}

mit 𝑐 = 𝑎𝑘 /2 und 𝑛0 > 2𝐴/𝑎 𝑘 erfüllt.

Maschinenmodell RAM: Aufbau Prozessor:  

Beschränkte Anzahl an Registern 𝑅1 , … , 𝑅𝑘 Instruktionszeiger zum nächsten Befehl

Programm: 

Nummerierte Liste von Befehlen (Adresse in Sprungbefehlen entsprechend dieser Nummerierung)

Eingabe: 

Steht in Speicherzellen 𝑆[1], … , 𝑆[𝑅1 ]

Modell/Realer Rechner  

Unendlicher/endlicher Speicher Abhängigkeit/Unabhängigkeit der Größe der Speicherzellen von der Eingabegröße Seite | 13

Grundlagen: Algorithmen und Datenstrukturen

SS 2016

RAM: Speicher   



Unbeschränkt viele Speicherzellen (words)𝑆[0], 𝑆[1], 𝑆[2], … , von denen zu jedem Zeitpunkt nur endlich viele benutzt werden Beliebig große Zellen führen zu unrealistischen Algorithmen Jede Speicherzelle darf bei Eingabelänge 𝑛 eine Zahl mit 𝑂(log 𝑛) Bits speichern. (Für konstant große Zellen würde man einen Faktor 𝑂(log 𝑛) bei der Rechenzeit erhalten.) Gespeicherte Werte stellen polynomiell in Eingabelänge 𝑛 beschränkte Zahlen dar (sinnvoll für Array-Indizes; bildet auch geschichtliche Entwicklung 4->8->16->32>84 Bits ab)

Begrenzter Parallelismus:  

Sequentielles Maschinenmodell, aber verknüpft logarithmisch viele Bits in konstanter Zeit

RAM...