Komplexitätstheorie PDF

Komplexitätstheorie 324 Algorithmische Komplexität 325 Berechenbarkeits- und Komplexitätstheorie ▪ Berechenbarkeitstheorie: ▪ Definition: Untersucht, ob es prinzipiell möglich ist, bestimmte Probleme durch Algorithmen zu lösen. ▪ Ziel: Bestimm...

Komplexitätstheorie 324 Algorithmische Komplexität 325 Berechenbarkeits- und Komplexitätstheorie ▪ Berechenbarkeitstheorie: ▪ Definition: Untersucht, ob es prinzipiell möglich ist, bestimmte Probleme durch Algorithmen zu lösen. ▪ Ziel: Bestimmen, welche Probleme lösbar sind und welche nicht. ▪ Beispiele: Entscheidungsprobleme, wie die Frage, ob eine Turing-Maschine für alle Eingaben stoppt. ▪ → Inhalt der Vorlesung Theoretische Informatik III. ▪ Komplexitätstheorie: ▪ Definition: Analysiert die Effizienz von Algorithmen hinsichtlich der benötigten Ressourcen. ▪ Kernfragen: ▪ Wie schnell ist ein Algorithmus? ▪ Wieviel Speicherplatz wird benötigt? ▪ Relevanz für die Praxis: ▪ Bestimmt, ob ein Entscheidungsverfahren in realen Anwendungen praktikabel ist. ▪ Betrachtet den Ressourcenverbrauch wie Laufzeit und Speicherplatz. 326 Ziel der Komplexitätsbetrachtungen ▪ Abstrakte Analyse: ▪ Bestimmung der Ressourcenanforderungen (Laufzeit und Speicherplatz) eines Algorithmus. ▪ Unabhängigkeit von: ▪ Programmiersprache ▪ Betriebssystem ▪ Prozessorleistung ▪ Speicherausstattung ▪ Computerarchitektur ▪ Wegen dieser Unabhängigkeit arbeitet man in der Komplexitätstheorie mit einheitenlosen Zahlen. 327 [Hoff22] Rucksackproblem ▪ Wir betrachten das Rucksackproblem: ▪ Grundproblem: ▪ Ein Dieb findet am Einbruchs-Ort verschiedene unterschiedlich große Gegenstände mit verschiedenem Wert. ▪ Aufgabe des Diebes: Seinen Beute-Rucksack so füllen, dass der erbeutete Wert maximal wird. ▪ Annahme: ▪ Unbegrenzte Anzahl an Gegenständen jedes Typs. ▪ Wert und Volumen der Gegenstände sind ganzzahlige Größen. 328 [Hoff22] Rucksackproblem Definition: Rucksackproblem ▪ Gegeben seien eine Zahl 𝑣 ∈ ℕ+ und eine Menge von Wertepaaren 2 𝑐1 , 𝑣2 , … , 𝑐𝑛 , 𝑣𝑛 ∈ ℕ+ ▪ Gesucht ist eine Folge ganzzahliger Werte 𝑎1 , … , 𝑎𝑛 ∈ ℕ+, sodass gilt: ▪ σ𝑛𝑖=1 𝑎𝑖 𝑣𝑖 ≤ 𝑣 ▪ und σ𝑛𝑖=1 𝑎𝑖 𝑐𝑖 ist maximal. 329 [Hoff22]  Rucksackproblem: Beispiel Rucksackproblem Gegenstand B Gegenstand A Wert: 5 Wert: 4 Volumen: 4 Volumen: 3 Gegenstand D Gegenstand C Rucksack-Volumen: 14 Wert: 11 Wert: 10 Volumen: 8 Volumen: 7 [Hoff22] 330  Rucksackproblem: Beispiel Beute 1 Beute 2 0xA 1xB 0xA 0xB 0xC 1xD 2xC 0xD Gesamtwert: 16 Gesamtwert: 20 Gesamtvolumen: 12 (von 14) Gesamtvolumen: 14 (von 14) 331 [Hoff22] Quiz https://partici.fi/33103264 332 Rucksackproblem: Lösungsansätze ▪ Ziel: Annäherung an die algorithmische Lösung des Rucksackproblems. ▪ Erste Schritte: ▪ Untersuchung einer vereinfachten Problemvariante. ▪ Ziel: Maximal erreichbaren Gewinn ermitteln, ohne sofort eine konkrete Auswahl der Gegenstände zu treffen. ▪ Weiterentwicklung der Algorithmen: ▪ Strategie zur Erweiterung, um aus den Ergebnissen eine Liste der zu entwendenden Gegenstände abzuleiten. ▪ Ziel: Von der Berechnung des Gewinns zur praktischen Anwendung mit vollständigen Lösungen. [Hoff22] 333  Rucksackproblem: Lösungsansätze ▪ Ziel: Annäherung an die algorithmische Lösung des Rucksackproblems. ▪ Erste Schritte: ▪ Untersuchung einer vereinfachten Problemvariante. ▪ Ziel: Maximal erreichbaren Gewinn ermitteln, ohne sofort eine konkrete Auswahl der Gegenstände zu treffen. ▪ Weiterentwicklung der Algorithmen: ▪ Strategie zur Erweiterung, um aus den Ergebnissen eine Liste der zu entwendenden Gegenstände abzuleiten. ▪ Ziel: Von der Berechnung des Gewinns zur praktischen Anwendung mit vollständigen Lösungen. 334 [Hoff22] Rucksackproblem: Rekursive Implementierung ▪ Parameter: Freies Rucksackvolumen. ▪ Ablaufprinzip: ▪ Iteration über alle 𝑚 Elemente ▪ Hypothetische Auswahl des i-ten Elements ▪ Rekursiver Aufruf zur optimalen Befüllung des verbleibenden Rucksacks ▪ Speicherung der besten Lösung in der Variablen "best" KnapsackRecursive.java 335 [Hoff22]  knapsack(14) Rucksackproblem: i tmp best 0 15+4=19 19 Rekursive 1 14+5=19 19 Implementierung: 2 10+10=20 20 Ablauf 3 8+11=19 20 knapsack(11) knapsack(10) knapsack(7) knapsack(6) i tmp best i tmp best i tmp best i tmp best 0 11+4=15 15 0 10+4=14 14 0 5+4=9 9 0 4+4=15 8 1 10+5=15 15 1 8+5=13 14 1 4+5=9 9 1 0+5=15 8 2 5+10=15 15 2 4+10=14 14 2 0+10=10 10 2 — 8 3 4+11=15 15 3 0+11=11 14 3 — 10 3 — 8 … … … … … … … … … … … … knapsack(4) knapsack(3) knapsack(0) i tmp best i tmp best i tmp best 0 0+4=4 4 0 0+4=4 4 0 — 0 1 0+5=5 5 1 — 4 1 — 0 2 — 5 2 — 4 2 — 0 3 — 5 3 — 4 3 — 0 336 [Hoff22] … … … Rucksackproblem: Rekursive Implementierung: Laufzeit ▪ Einfluss des Rekursionsbaums: ▪ Der Rekursionsbaum liefert wertvolle Informationen über die Laufzeitkomplexität des Algorithmus. ▪ Funktionsaufrufanalyse: ▪ Schleifenkörper wird 𝑚-mal durchlaufen. ▪ Jedes Mal wird ein rekursiver Aufruf ausgelöst. ▪ Der Parameter n wird bei jedem Aufruf mindestens um 1 verringert → Maximale Tiefe des Baumes ist 𝑛. ▪ Insgesamt hat der Rekursionsbaum maximal 𝑚𝑛 Knoten. ▪ Laufzeitabschätzung: ▪ Laufzeit lässt sich durch den Term 𝑚𝑛 nach oben abschätzen. ▪ In der Komplexitätstheorie schreibt man diese Beziehung als 𝑂(𝑚𝑛 ). [Hoff22] 337  Rucksackproblem: Rekursive Implementierung: Zusammenfassung Die rekursive Implementierung von knapsack(n) besitzt die folgende Komplexität: Laufzeit Speicherplatz 𝑂(𝑚𝑛 ) 𝑂(𝑛) [Hoff22] 338  Rucksackproblem: Rekursive Implementierung: Speicherplatz ▪ Rekursiver Speicherplatzbedarf: ▪ Jeder rekursive Aufruf erzeugt einen neuen Stack-Rahmen. ▪ In diesen Rahmen werden lokale Variablen zwischengespeichert. ▪ Maximale Tiefe und Rucksackspeicher: ▪ Maximale Anzahl von Stack-Rahmen entspricht der Rekursionstiefe 𝑛. ▪ Speicherbedarf steigt linear mit der Größe des Rucksacks. ▪ Parameterabhängigkeit: ▪ Die Anzahl 𝑚 der Gegenstände hat keinen Einfluss auf den Speicherplatz. ▪ Der Speicherbedarf der rekursiven Implementierung ist somit 𝑂(𝑛). [Hoff22] 339 Rucksackproblem: Dynamische Programmierung Grundprinzip der Dynamischen Programmierung ▪ Problemdekomposition: ▪ Zerlegung eines komplexen Problems in einfachere Teilprobleme. ▪ Lösung der Teilprobleme und Speicherung der Ergebnisse. ▪ Wiederverwendung ▪ Zugriff auf die zuvor gespeicherten Ergebnisse ▪ Vermeidung von redundantem Rechnen durch Abrufen gespeicherter Ergebnisse. ▪ Optimalitätsprinzip: ▪ Zusammensetzung der optimalen Lösung aus optimalen Lösungen der Teilprobleme. ▪ Effiziente Lösungssuche durch Nutzung gespeicherter Informationen. 340 340  Rucksackproblem: Dynamische Programmierung ▪ Mit dynamischer Programmierung lässt sich das Rucksackproblem viel effizienter Lösen. ▪ In unserer rekursiven Implementierung haben wir die Variable best. Diese liefert uns den Wert der bisher besten Füllung des Rucksacks mit Volumen n. ▪ Wir ersetzen best durch eine Tabelle der Länge n. In best[j] speichern wir dann den maximal zu erbeutenden Wert für einen Rucksack mit Volumen j. [Hoff22] 341 Rucksackproblem: Dynamische Programmierung: Iterative Lösung ▪ Arbeitsweise ▪ Initiale Befüllung des Arrays: Befüllung ausschließlich mit Typ-A-Gegenständen. ▪ Kontinuierliche Aktualisierung: ▪ Das Array best wird laufend in einem iterativen Prozess aktualisiert. ▪ Schritt 2 integriert Typ-B-Gegenstände, Schritt 2 berücksichtigt Typ-C-Gegenstände. ▪ Optimierungsmechanismus: ▪ Optimale Lösung für best[i]: Ermittlung aus den bereits berechneten Werten. ▪ Beispielentscheidungen: Nach der zweiten Iteration gibt best den Wert 18 an (maximal mit Typ-A/B). ▪ Entscheidungsfindung: ▪ Hinzufügen von Typ-C: Wert 10, restliches Volumen, Vergleich mit best zur optimalen Nutzung des Volumens. ▪ - Entscheidungsregel: Bei best + 10 größer als 18 lohnt sich der Typ-C-Diebstahl. ▪ Ergebnis: Maximales Ergebnis steht in best. 342 [Hoff22] Rucksackproblem: Dynamische Programmierung: Implementierung KnapsackIterative.java 343  Rucksackproblem: Dynamische Programmierung: Implementierung: Laufzeit ▪ Die Methode knapsack. enthält zwei verschachtelte Schleifen. ▪ Äußere Schleife: ▪ Iteriert über alle Gegenstände. ▪ Wird 𝑚 mal ausgeführt. ▪ Innere Schleife: ▪ Umfasst alle Rucksackvolumina von 0 bis 𝑛. ▪ Laufzeitkomplexität: ▪ Proportional zum Produkt 𝑚 · 𝑛. ▪ Beide Schleifen zusammen bestimmen die Skalierung der Laufzeit. [Hoff22] 344  Rucksackproblem: Dynamische Programmierung: Implementierung: Laufzeit ▪ Speicherplatzverbrauch: Außer Array best keine Hilfsvariablen. ▪ Array-Struktur: ▪ 𝑛 Elemente in best. ▪ Speicherplatz wächst linear mit dem Rucksackvolumen. ▪ Effiziente Nutzung: ▪ Eine besondere Eigenschaft des Rucksackproblems reduziert den Speicherbedarf. ▪ Nur Ergebnisse der letzten Iteration nötig: Alte Zwischenergebnisse werden verworfen. ▪ Dadurch Lösung des Rucksackproblems mit einem eindimensionalen Array. [Hoff22] ▪ Speicherplatz ist linear zu Anzahl der Elemente 𝑛. 345  Rucksackproblem: Rekursive Implementierung: Zusammenfassung Die iterative Implementierung von knapsack(n) besitzt die folgende Komplexität: Laufzeit Speicherplatz 𝑂(𝑚 ⋅ 𝑛) 𝑂(𝑛) [Hoff22] 346  Rucksackproblem: Vollständige Implementierung ▪ Die bisherigen Implementierungen liefern den maximalen Gewinn, aber nicht die Auswahl der Gegenstände. ▪ Zielsetzung: Zusätzlich Auswahl der Gegenstände bestimmen. ▪ Lösung: ▪ Ergänzung durch zweites Array items zur Speicherung des zuletzt hinzugefügten Gegenstandstyps. ▪ Bei jeder Aktualisierung von best[j] wird auch KnapsackIterativeComplete.java items[j] aktualisiert. [Hoff22] 347  Rucksackproblem: Vollständige Implementierung ▪ Rückverfolgung der Einträge: Der Dieb kann durch die gespeicherten Einträge die optimale Auswahl der Gegenstände identifizieren. ▪ Bestimmung des ersten Gegenstands: items = C deutet auf den ersten Typ-C-Gegenstand hin ▪ Bestimmung des zweiten Gegenstands: ▪ Volumen von C wird von 14 subtrahiert: items[14-1] = C. ▪ Ein zweiter Typ-C-Gegenstand wird gewählt. ▪ … [Hoff22] 348 Fragen? 349 O-Kalkül ▪ Wie haben die O-Notation für die Komplexität bereits verwendet. ▪ Jetzt betrachten wir diese Notation genauer: ▪ Wir definieren sie formal. ▪ Wir betrachten die Rechenregeln der O-Notation. ▪ Sinn: ▪ Nutzung des O-Kalküls als effektives Werkzeug zur Beschreibung von Wachstumsfunktionen. ▪ Einteilung von Komplexitäten in Äquivalenzklassen 350  O-Notation: Definition: O-Notation Definition Eine Funktion 𝑓: ℕ → ℝ+ hat die ▪ O veranschaulicht, dass eine Komplexitätsklasse Funktion 𝑓 höchstens genauso O 𝑔 𝑛 , schnell wächst wie eine Funktion wenn es eine Konstante 𝑐 ∈ ℝ+ und ein 𝑔. 𝑛0 ∈ ℕ gibt , sodass Das Notationszeichen O ist eines ▪ 𝑓 𝑛 ≤𝑐⋅𝑔 𝑛 von mehreren Landau-Symbolen. für alle 𝑛 ≥ 𝑛0 gilt. ▪ Diese Symbole sind benannt nach dem deutschen Mathematiker Edmund Georg Hermann Landau. [Hoff22] 351  𝑔 𝑓 O-Notation: Definition: Betrachtungen ▪ 𝑓 𝑛 ≤ 𝑐 ⋅ 𝑔(𝑛) muss erst ab einem bestimmten Wert 𝑛0 gelten. ▪ Kerngedanke: ▪ Komplexitätsanalyse konzentriert sich auf sehr große Eingaben. ▪ 𝑛 strebt gegen unendlich. 𝑔 ▪ Verhalten der Wachstumsfunktionen auf endlichen 𝑓 Anfangsstücken ist irrelevant. ▪ Wir betrachten also die sogenannte „asymptotische Komplexität“. ▪ Beispiel: 𝑓: ℕ → ℝ+, 𝑛 ↦ 2𝑛2 scheint zunächst schneller zu wachsen als 𝑔: ℕ → ℝ+, 𝑛 ↦ 𝑛3. Bei 𝑛 = 2 überholt wird 𝑓 aber von 𝑔 überholt und bleibt für alle 𝑛 > 2 kleiner. 352 O-Notation: Definition: Betrachtungen ▪ Konstante 𝑐 in der Definition ist beliebig wählbar. Dadurch ignoriert die O-Notation praktisch Konstanten. ▪ Gehört 𝑓 zu O(𝑔(𝑛)), dann gehört auch 𝑘 ⋅ 𝑓 dazu, unabhängig von 𝑘. ▪ Ziel: Abstraktion von konkreten Einheiten. Die Zunahme der Größe ist entscheidend, nicht der reale Wert. ▪ Beispiel: Die Funktionen 𝑓: ℕ → ℝ+ , 𝑛 ↦ 2 ⋅ 𝑛2 , 𝑔: ℕ → ℝ+ , 𝑛 ↦ 10 ⋅ 𝑛2 und ℎ: ℕ → ℝ+ , 𝑛 ↦ 100 ⋅ 𝑛2 sind alle O(𝑛2 ). 353 O-Notation: Schreibweise ▪ O(𝑔(𝑛)) beschreibt eine Menge von Funktionen. ▪ Somit bedeutet 𝑓 ∈ 𝑂(𝑔(𝑛)), dass die Funktion 𝑓 in die durch 𝑔 definierte Klasse fällt. ▪ In der Informatik nutzt man meist die (formal inkorrekte) Schreibweise 𝑓(𝑛) = O(𝑔(𝑛)). 354 Quiz https://partici.fi/33103264 355 Definition: Ω-, Θ-Notation Eine Funktion 𝑓: ℕ → ℝ+ hat die Ω- und Θ-Notation Komplexitätsklasse ▪ O, Ω und Θ sind die drei gängigsten Ω 𝑔 𝑛 , Landau-Symbole. wenn es eine Konstante 𝑐 ∈ ℝ+ und ein 𝑛0 ∈ ℕ gibt , sodass ▪ O-Notation: Schätzt das asymptotische 𝑓 𝑛 ≥𝑐⋅𝑔 𝑛 Wachstum von 𝑓 nach oben ab. für alle 𝑛 ≥ 𝑛0 gilt. ▪ Omega-Notation (Ω): Abschätzung des Wachstums nach unten. 𝑓 hat die Komplexitätsklasse ▪ Theta-Notation (Θ): Beschreibt eine Θ 𝑔 𝑛 , Abschätzung des Wachstums in beide wenn es sowohl in O 𝑔 𝑛 als Richtungen. auch in Ω 𝑔 𝑛 liegt. [Hoff22] 356 O, Ω- und Θ-Notation Quelle der Grafiken: [Hoff22] 357 O-Notation vs. Θ- Notation ▪ Die O-Notation ist in der Informatik praktisch der Standard. Komplexität von Algorithmen wird meist in O-Notation angegeben. ▪ Vergleich mit Θ-Notation: Die Θ-Komplexität wäre eigentlich passender, da sie Laufzeit und Speicherbedarf in beide Richtungen (obere und untere Schranken) abschätzt. ▪ Missverständnisse der O-Notation: Beispielsweise suggeriert O(2𝑛 ), dass Probleme dieser Klasse Algorithmen, erfordern deren Laufzeit oder Speicher exponentiell mit der Eingangsgröße 𝑛 wächst. Tatsächlich liegen aber auch die Algorithmen mit linearem Ressourcenverbrauch in dieser Klasse! [Hoff22] 358 Herausforderungen der Θ-Komplexität ▪ Berechnungsschwierigkeiten: ▪ Schwierige Bestimmung, da sowohl obere als auch untere Schranken nachgewiesen werden müssen. ▪ Untere Schranken: ▪ Nachweis, dass alle Algorithmen die Komplexität 𝑔(𝑛) mindestens erreichen. ▪ Praxisprobleme: ▪ Nur wenige Probleme haben formale Nachweise exakter unterer Schranken. [Hoff22] 359  Bevorzugung der O-Notation: O-Notation ist weit verbreitet, da sie einfacher zu berechnen ist. O-Notation Einschränkung: vs. Θ- Man bleibt meist bei O-Notation, obwohl Notation: die Θ-Notation genauer wäre. Fazit Komplexitätsanalyse: Die formale Berechnung der Θ- Komplexität bleibt eine Herausforderung. [Hoff22] 360 Problemkomplexität Definition: Problemkomplexität ▪ Betrachtung bisher: Sei 𝑃 ein Problem, das mit „Ja“ oder „Nein“ ▪ Beschreibung der asymptotischen beantwortet werden kann (sog. „Ja-Nein-Problem“). Komplexität einzelner Algorithmen. Sei 𝐴 die Menge aller Algorithmen, die 𝑃 entscheiden. ▪ Erweiterter Begriff: Wir sagen: ▪ Komplexität wird nicht nur auf 𝑃 = O 𝑔 𝑛 , falls für ein 𝑎 ∈ 𝐴 gilt: 𝑓𝑎 = O 𝑔 𝑛 Algorithmen, sondern auch auf 𝑃 = Ω 𝑔 𝑛 , falls für ein 𝑎 ∈ 𝐴 gilt: 𝑓𝑎 = Ω 𝑔 𝑛 Probleme angewandt. 𝑃 = Θ 𝑔 𝑛 , falls 𝑃 ∈ O 𝑔 𝑛 und 𝑃 ∈ Ω 𝑔 𝑛 ▪ Neuer Fokus: Die Funktion 𝑓𝑎 : ℕ → ℝ+ beschreibt den ▪ Analyse der Schwierigkeit von Ressourcenverbrauch von 𝑎 in Abhängigkeit von der Problemen selbst, nicht nur der Eingabelänge 𝑛. Algorithmen, die sie lösen. [Hoff22] 361 Rechenregeln im O-Kalkül: Alternative Definition der Landau-Symbole ▪ Für den algebraischen Umgang eignet sich eine andere Definition der Landau-Symbole O und Ω besser als die Satz: Grenzwertregel bisherige. ▪ Die bisherige Definition mit dem 𝑓 ≤ 𝑐 · 𝑔(𝑛) bzw. Für zwei Funktionen 𝑓, 𝑔: ℕ → ℝ+ gilt: 𝑓 ≥ 𝑐 · 𝑔(𝑛) eignet sich für die folgenden Beweise nur eingeschränkt. 𝑓(𝑛) lim𝑔(𝑛) < ∞ ⇒ 𝑓 𝑛 = O(𝑔(𝑛) 𝑛→∞ 𝑓(𝑛) ▪ Alternative Charakterisierung mit dem Quotienten 𝑔(𝑛) 𝑓(𝑛) ▪ Geht dieser für wachsendes 𝑛 gegen ∞, dann wächst 𝑓 lim > 0 ⇒ 𝑓 𝑛 = Ω(𝑔(𝑛) 𝑛→∞ 𝑔(𝑛) asymptotisch schneller als 𝑔. ▪ Geht dieser für wachsendes 𝑛 gegen 0, dann wächst 𝑓 asymptotisch langsamer als 𝑔. ▪ Konvergiert er gegen einen konstanten Wert > 0, dann haben wir gleiches asymptotisches Wachstum. [Hoff22] 362 Rechenregeln im O-Kalkül: Alternative Definition der Landau-Symbole Quelle: [Hoff22] 363  Rechenregeln im O-Kalkül: Polynome Beweis: Satz: Wachstum von Polynomen ▪ Wir betrachten das asymptotische Wachstum von Polynomen der Form: Sei 𝑝 ein Polynom vom Grad 𝑘. 𝑝 𝑛 = 𝑎𝑘 𝑛𝑘 + 𝑎𝑘−1 𝑛𝑘−1 + ⋯ + 𝑎1 𝑛 + 𝑎0. Dann gilt 𝑝 𝑛 = Θ 𝑛𝑘. ▪ Gilt 𝑎𝑘 > 0, dann ist 𝑘 der Grad des Polynoms 𝑝. ▪ Es gilt: 𝑎𝑘−1 𝑎1 𝑎0 lim 𝑝(𝑛) = lim 𝑎𝑘 + + ⋯ + 𝑘+1 + 𝑘 = 𝑎𝑘 𝑛→∞ 𝑛 𝑘 𝑛→∞ 𝑛 𝑛 𝑛 ▪ Wegen 𝑎𝑘 > 0 folgt aus der Grenzwertregel 𝑝 𝑛 = Θ 𝑛𝑘. [Hoff22] 364  Rechenregeln im O-Kalkül Satz: Summe im O-Kalkül Satz: Basen von Logarithmen im O-Kalkül Seien 𝑓, 𝑔: ℕ → ℝ+ mit 𝑓 𝑛 = O(𝑔(𝑛)), dann gilt mit 𝑓 𝑛 + 𝑔(𝑛) = O(𝑔(𝑛)) Es gilt O(log 𝑎 𝑛) = O(log 𝑏 𝑛) Satz: Multiplikation im O-Kalkül Für ein Funktion 𝑔: ℕ → ℝ+ und Konstanten 𝑘 ∈ ℝ+ gilt O(𝑘 ⋅ 𝑔(𝑛))=O(𝑔(𝑛)) [Hoff22] 365 Quiz https://partici.fi/33103264 366 Experiment 367 Sortieren: Aufgabenstellung ▪ Sortieren von Daten ist eine gängige Aufgabe. ▪ Aufgabe: ▪ Gegeben ist eine Folge von n Datensätzen. ▪ Jeder Datensatz besitzt einen Schlüssel, nach dem geordnet werden soll. ▪ Ziel ist es, die Datensätze nach dem Schlüssel zu ordnen. ▪ Aus Speicherplatzgründen sind vor allem diejenigen Sortierverfahren interessant, die direkt auf der Eingabefolge arbeiten. Diese Verfahren nennt man in-place-Verfahren. 368 Sortieren: Aufgabenstellung ▪ Im folgenden nehmen wir an, unsere Datensätze seien Zahlen. ▪ Die Zahlen wollen wir aufsteigend sortieren. 5 17 28 Eingangsdaten 15 11 1 3 20 25 6 12 8 369 Sortieren: BubbleSort Prinzip: Pseudocode: Eingabefolge wird von links nach rechts durchlaufen. Das aktuelle Element wird mit dem 1 for i = 1 to lenght(A) rechten Nachbarn verglichen. Ist das 2 for j = 1 to length(A)-1 Sortierkriterium verletzt, dann werden 3 if (A[j] > A[j+1]) die beiden Elemente getauscht. 4 tausche A[j] und A[j+1] Dies wird solange wiederholt, bis die Folge sortiert ist. 370 Sortieren Grundidee: ▪ Man betrachtet die Folge als einen Stapel Mergesort nummerierter Karten, der von einem „Meister“ sortiert werden soll. 371  Schritt 1 (Teilen): Sortieren: ▪ Falls der Stapel nur aus einer Karte besteht, gib ihn sofort zurück. Mergesort: ▪ Andernfalls: Teile den Stapel in zwei möglichst Algorithmus gleich große Teile und gib jeden Teil je einem Gehilfen mit der Bitte, ihn ebenfalls genau nach dem hier beschriebenen Verfahren zu sortieren. 372 Sortieren Schritt 2 (Mischen) ▪ Nimm die Stapel der Gehilfen und durchlaufe Mergesort: ▪ gleichzeitig beide Stapel von oben nach unten. Mische die Karten nach einer Art Algorithmus ▪ Reißverschlussverfahren zusammen. Gib den so erhaltenen Stapel an den Meister. 373 Sortieren Mergesort: Rekursion ▪ Das Prinzip Gehilfen zu beauftragen, mit einem Teil der Daten den gleichen Algorithmus auszuführen, lösen wir mit Rekursion. Die Gehilfen beauftragen Untergehilfen usw. bis nur noch aus einer Karte bestehende Stapel übrigbleiben. ▪ Beispiel: Mergesort mit 6 Karten. 374 Sortieren Wir brauchen die rekursive Funktion MergeSort() und die Mergesort: Hilfsfunktion Merge() für das Mischen. Pseudocode: Rekursion 375 Arbeitsauftrag 1: Laufzeit-Analyse von Sortier-Verfahren 1. Quellcode analysieren ▪ Öffnen Sie die Datei „SortComparison.java“ und verschaffen Sie sich einen Überblick über den bestehenden Code. ▪ Verstehen Sie die Funktionsweise der implementierten Sortierverfahren. 2. Test mit kleinen Arrays ▪ Erzeugen Sie zunächst kleinere Arrays mit verschiedenen Werten. ▪ Sortieren Sie diese Arrays mit beiden Sortierverfahren und geben Sie die sortierten Arrays zur Kontrolle auf der Konsole aus. 3. Erweiterung auf größere Arrays ▪ Entfernen Sie die Ausgabe der sortierten Arrays. ▪ Erhöhen Sie die Array-Größe schrittweise (z. B. verdoppeln, vervierfachen, verachtfachen, usw.). ▪ Messen Sie die Laufzeiten der verschiedenen Sortierverfahren und analysieren Sie, wie sich die Laufzeit verhält, wenn die Array-Größe wächst. ▪ Welche Laufzeit-Ordnungen vermuten Sie? 4. Vergleich der Verfahren für große Arrays ▪ Ermitteln Sie, welches der Sortierverfahren sich am besten für sehr große Arrays (z. B. 1 Million Elemente) eignet. 376 Arbeitsauftrag 2: Laufzeit-Analyse von Knapsack-Verfahren Zeitmessungen bei Knapsack- Implementierungen ▪ Fügen Sie in die bestehenden Knapsack- Implementierungen (Rucksackprobleme) Zeitmessungen ein. ▪ Testen Sie die Laufzeiten der Algorithmen für sehr große Rucksackvolumen (n) und vergleichen Sie deren Effizienz. 377 Fragen? 378