Algorithmen und Datenstrukturen - Vorlesung PDF

Algorithmen und Datenstrukturen 2Prof. Marc Fischlin, SS 2024 01...

Algorithmen und Datenstrukturen 2Prof. Marc Fischlin, SS 2024 01 Einleitung Folien beruhen auf gemeinsamer Veranstaltung mit Christian Janson aus dem SS 2020 13. Oktober 2010 | Dr.Marc Fischlin | Kryptosicherheit | 1  Algorithmen Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 2  Verortung Eingabe Computer Programm Algorithmus: höherer Abstraktionsebene als Programm Euklidischer Algorithmus Algorithmus Ausgabe (ca.300 v.Chr.) Abstraktion +Verallgemeinerung Problem/ berechne ggT von a,b Modell (Problem-) berechne ggT(21,39) =3 Instanz Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 3  Algorithmus Algorithmus: Eine aus endlich vielen Schritten bestehende, ausführbare Handlungsvorschrift Eine aus endlich zur eindeutigen vielen Schritten bestehende, ausführbare Handlungsvorschrift Umwandlung zur eindeutigen von Eingabe- Umwandlung von in Ausgabedaten. Eingabe- in Ausgabedaten nach Cormen et al., Introduction to Algorithms Namensgeber: Ibn Musa Al-Chwarismis (ca. 825): Buch: Regeln der Wiedereinsetzung und Reduktion, ins Lateinische als „Al-Chwarismis Buch“ übersetzt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 4  Allgemeine Charakteristika Algorithmen (I) keine übereinstimmende Finitheit Charakterisierung in der Literatur! berechenbar Terminierung Effektivität Allgemeinheit Determiniertheit Korrektheit Determinismus anwendbar bestimmt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 5  Allgemeine Charakteristika Algorithmen (II) Finitheit berechenbar Terminierung Effektivität Allgemeinheit Determiniertheit Finitheit: Algorithmus hat endliche Beschreibung Korrektheit Determinismus Terminierung: Algorithmus stoppt in endlicher Zeit Effektivität: Schritte sind auf Maschine ausführbar anwendbar bestimmt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 6  Allgemeine Charakteristika Algorithmen (III) Determiniertheit: Finitheit gleicher EingabeTerminierung Algorithmus liefert bei berechenbar gleiche Ausgabe Effektivität Determinismus: Allgemeinheit Algorithmus durchläuft für gleiche Eingabe Determiniertheit Korrektheit immer die gleichen Schritte/Zustände Determinismus anwendbar bestimmt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 7  Allgemeine Charakteristika Algorithmen (IV) Finitheit Allgemeinheit: berechenbar Terminierung Algorithmus für Effektivität ganze Problemklasse anwendbar Korrektheit: Allgemeinheit Determiniertheit Falls Algorithmus terminiert, ist die Korrektheit Ausgabe richtigDeterminismus anwendbar bestimmt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 8  Beispiel: Euklidischer Algorithmus (I) gcd(a,b) // a,b0 integers 1 IF b==0 THEN 2 return a 3 ELSE //a mod b Divisionsrest 4 return gcd(b,a mod b) Finitheit: Algorithmus hat endliche Beschreibung ✓ Terminierung: Algorithmus stoppt in endlicher Zeit Effektivität: Schritte sind auf Maschine ausführbar ✓ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 9  Beispiel: Euklidischer Algorithmus (II) gcd(a,b) // a,b0 integers 1 IF b==0 THEN 2 return a 3 ELSE //a mod b Divisionsrest 4 return gcd(b,a mod b) Finitheit: Algorithmus hat endliche Beschreibung Terminierung: Algorithmus stoppt in endlicher Zeit ✓ Effektivität: Schritte sind auf Maschine ausführbar Divisionsrest ist stets zwischen 0 und b−1, so dass zweites Argument in jeder Iteration um mindestens 1 kleiner wird und schließlich Basisfall b=0 erreicht wird Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 10  Beispiel: Euklidischer Algorithmus (III) gcd(a,b) // a,b0 integers 1 IF b==0 THEN 2 return a 3 ELSE //a mod b Divisionsrest 4 return gcd(b,a mod b) Determiniertheit: gleiche Eingabe, gleiche Ausgabe ✓ Determinismus: gleiche Eingabe, gleiche Schritte ✓ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 11  Beispiel: Euklidischer Algorithmus (IV) gcd(a,b) // a,b0 integers 1 IF b==0 THEN 2 return a 3 ELSE //a mod b Divisionsrest 4 return gcd(b,a mod b) Allgemeinheit: für Problemklasse anwendbar ✓ Korrektheit: falls terminiert, Ausgabe richtig ✓ Folgt aus gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 𝑚𝑜𝑑 𝑏) (ohne Beweis) sowie gcd 𝑎, 0 = 𝑎 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 12  Lernziele Algorithmen Abschnitte 6 und 7 geeignete Modellierung von Problemen erlernen Entwurfs- paradigmen Übungen kennenlernern Umsetzung in Abschnitt 7 Algorithmus Programme können (hier: Java) wichtige Algorithmen Analysetechniken erlernen wissen Abschnitt 6 Korrektheit Terminierung Aufwand Abschnitte 2 und 8 (auch 6,7) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 13  Vorlesung und Übung (I) Eingabe Computer Programm Algorithmus Ausgabe Abstraktion +Verallgemeinerung Problem/ Modell Übung Vorlesung (Problem-) +Übung Instanz Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 14  Vorlesung und Übung (II) Code generiert mittels ChatGPT auf die Frage „Wie könnte bfs in java aussehen“, 21.März 2023 … lauffähiger 1 public void bfs(int s) { 2 Eingabe visited boolean[] Java-Code = new boolean[V]; Computer 3 LinkedList queue = new LinkedList(); Programm 4 5 visited[s] = true; 6 queue.add(s); Pseudocode: … Algorithmus Ausgabe einfacher Zugang BFS(G,s) Abstraktion +Verallgemeinerung Problem/ Modell Übung 1 s.color=GRAY; … 2 newQueue(Q); Vorlesung 3 (Problem-) enqueue(Q,s); +Übung … Instanz Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 15  Wie verhalten sich Determiniertheit (gleiche Eingabe, gleiche Ausgabe) und Determinismus (gleiche Eingabe, gleiche Schritte/Zustände) zueinander? Was halten Sie von folgender Idee, die mod-Funktion (z.B. für den Euklidischen Algorithmus) umzusetzen? MOD(a,b) //a,b0 integers 1 WHILE a>=b DO 2 a=a-b 3 END WHILE 4 return a Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 16  Datenstrukturen Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 17  Datenstrukturen Datenstrukturen: Eine aus endlich vielen Schritten bestehende, ausführbare Handlungsvorschrift zur eindeutigen Eine Datenstruktur ist eine Methode, Umwandlung Daten für den von Eingabe- Zugriff in Ausgabedaten. und die Modifikation zu organisieren nach Cormen et al., Introduction to Algorithms Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 18  Beispiel: Array 0 1 2 3 4 5 6 7 8 A 12 47 17 98 72 Datenstrukturen beinhalten Daten + Strukturbestandteile z.B. A ist achter Eintrag im Speicher Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 19 Abstrakte Datentypen (ADTs) und Datenstrukturen näher an der Anwendung Beispiel: Stack mit Operationen Abstrakter Datentyp („was“) isEmpty,pop,push Übergang fließend; ADTs werden daher oft auch als Datenstruktur bezeichnet Stack-Operationen Datenstruktur („wie“) als Array oder verkettete Liste näher „an der Maschine“ Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 20  Lernziele Datenstrukturen Abschnitte 3-5 Vor- und Nachteile der verschiedenen Strukturen Einfache erkennen Datenstrukturen Übungen beherrschen Umsetzung in Abschnitt 3 Daten- Programme können strukturen (hier: Java) komplexe Datenstrukturen Analysetechniken erlernen kennenlernen Abschnitte 4 und 5 Korrektheit Terminierung Aufwand Abschnitte 3-5 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 21  Algorithmen und Datenstrukturen Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 22  Datenstrukturen in Algorithmen verwendet Daten- Problem Algorithmus struktur Dijkstra(…) gesucht: „Suche 1 … Datenstruktur, kürzesten 2 WHILE… mit der man leicht Weg“ 3 „gib mir den kleinste Einträge kleinsten Wert“ finden kann Abschnitt 6 4 … wirkt sich auf Effizienz des Algorithmus aus Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 23  Algorithmen für Datenstrukturen Daten- verwendet Daten- Problem Algorithmus struktur struktur „Konstruiere eine Datenstruktur, mit der man schnell kleinste Werte finden kann“ komplexere einfache Datenstruktur Abschnitt 4 (auch 3 und 5) Datenstruktur (z.B. Heap) (z.B. Array) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 01 Einleitung | 24  Algorithmen und Datenstrukturen 21.PMarc Fischlin, SS 2024 02 Sortieren Folien beruhen auf gemeinsamer Veranstaltung mit Christian Janson aus dem SS 2020 13. Oktober 2010 | Dr.Marc Fischlin | Kryptosicherheit | 1  Das Sortierproblem Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 2 Sortierproblem in der Praxis Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 3 Sortierproblem Gegeben: Folge von Objekten Gesucht: Sortierung der Objekte (gemäß ausgewiesenen Schlüsselwerts) Schlüssel(wert) Wert, nach dem Objekt sortiert wird „Satellitendaten“ Steuer-ID Name Objekt Adresse Bankverbindung Beispiel … Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 4 Schlüsselproblem Schlüssel(werte) müssen nicht eindeutig sein, aber müssen „sortierbar“ sein Schlüssel(wert) Wert, nach dem Objekt sortiert wird „Satellitendaten“ Annahme im Folgenden: Es gibt eine totale Ordnung Objekt ≤ auf der Menge 𝑀 aller möglichen Schlüsselwerte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 5  Exkurs Totale Ordnung Beispiel: lexikographische Ordnung auf Strings Sei 𝑀 eine nicht leere Menge und ≤ ⊆ 𝑀 × 𝑀 eine binäre Relation auf 𝑀 Die Relation ≤ auf 𝑀 ist genau dann eine totale Ordnung, wenn gilt: Reflexivität: ∀𝑥 ∈ 𝑀: 𝑥 ≤ 𝑥 Transitivität: ∀𝑥, 𝑦, 𝑧 ∈ 𝑀: 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑧 ⇒ 𝑥 ≤ 𝑧 Antisymmetrie: ∀𝑥, 𝑦 ∈ 𝑀: 𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑥 ⇒ 𝑥 = 𝑦 (ohne Totalität: Totalität: ∀𝑥, 𝑦 ∈ 𝑀: 𝑥 ≤ 𝑦 ∨ 𝑦 ≤ 𝑥 partielle Ordnung) Bemerkung: Totale Ordnung ≤ impliziert Relation > durch 𝑥 > 𝑦: ⇔ 𝑥 ≰ 𝑦 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 6 Darstellung in diesem Abschnitt Wir betrachten nur Schlüssel(werte) ohne Satellitendaten, in Beispielen meistens durch Zahlen gegeben Eingabe der Objekte bzw. Schlüsselwerte in Form eines Arrays A: 0 1 2 3 4 5 6 7 8 A 53 12 17 44 33 25 17 4 76 Lese-/Schreibzugriff per Index in konstanter Zeit: y=A weist y den Wert 17 zu A=99 überschreibt 33 mit 99 A.length beschreibt (fixe) Länge des Arrays, im Beispiel 9 A[i…j] beschreibt Teil-Array von Index i bis j, 0=key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: FOR-Schleife i=1 2 key=12 3 j=0 WHILE-Schleife j=0 A[j]=53 > key=12 7 53 12 53 12 17 87 1.Fall: 6 j=-1 5 linker Rand erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 11 Beispiel: Insertion Sort (II) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 FOR-Schleife i=1 2 key=17 3 j=1 WHILE-Schleife j=1 A[j]=53 > key=17 53 12 53 53 17 87 2.Fall: 6 j=0 5 Einfügeposition erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 12 Beispiel: Insertion Sort (III) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 FOR-Schleife i=1 2 key=17 3 j=1 j=1 WHILE-Schleife j=0 A[j]=12 < key=17 53 12 17 53 53 17 87 7 2.Fall: 6 j=0 Einfügeposition erreicht Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 13 Beispiel: Insertion Sort (IV) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Beispiel: i=2 i=1 FOR-Schleife i=3 2 key=87 3 j=2 j=1 j=2 WHILE-Schleife j=0 A[j]=53 < key=87 53 12 17 53 53 17 87 7 3.Fall: Element bleibt Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 14 Terminierung insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Jede Ausführung der WHILE-Schleife erniedrigt jkey DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Schleifeninvariante (der FOR-Schleife): Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 16 Korrektheit (II) Beweis per Induktion: Induktionsbasis i=1: Beim ersten Eintritt ist A=a und „sortiert“. Ferner gilt noch A=a,…,A[n-1]=a[n-1]. Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 17 Korrektheit (III) Beweis per Induktion: Induktionsschritt von i-1 auf i: Vor der (i-1)–ten Ausführung galt Schleifeninvariante nach Voraussetzung. Inbesondere war A,…,A[i-2] sortierte Version von a,…,a[i-2] und A[i-1]=a[i-1],…,A[n-1]=a[n-1] Durch die WHILE-Schleife wurde A[i-1]=a[i-1] nach links einsortiert und größere Elemente von A,…,A[i-2] um jeweils eine Position nach rechts verschoben. Elemente A[i],…,A[n-1] wurden nicht geändert Also gilt Invariante auch für i Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 18 Korrektheit (IV) Aus Schleifeninvariante folgt für letzte Ausführung (also quasi vor gedanklichem Eintritt der Schleife für i=n): A,…,A[n-1] ist sortierte Version von a,…,a[n-1] und somit am Ende das Array sortiert Bei jedem Eintritt für Zählerwert i (und nach letzter Ausführung) entsprechen die aktuellen Einträge in A,…,A[i-1] den sortierten ursprünglichen Eingabewerten a,…,a[i-1]. Ferner gilt A[i]=a[i],…, A[n-1]=a[n-1]. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 19  Wozu brauchen Sie (intuitiv) beim Sortieren die vier Eigenschaften einer totalen Ordnung? Überlegen Sie sich, dass Insertion Sort stabil ist, d.h. die Reihenfolge von Objekten mit gleichem Schlüssel bleibt erhalten. Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 20  Laufzeitanalysen: O-Notation Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 21 Laufzeitanalyse Wieviel Schritte macht Algorithmus in Abhängigkeit von der Eingabekomplexität? meistens: schlechtester Fall über fasst alle Eingaben alle Eingaben gleicher Komplexität ähnlicher Komplexität zusammen (Worst-Case-)Laufzeit Beispiel: 𝑛 Anzahl zu 𝑇(𝑛) = max { Anzahl Schritte für x } sortierender Zahlen Maximum über alle Eingaben (man könnte auch zusätzlich x der Komplexität 𝑛 Größe der Zahlen betrachten; wird aber meist von Anzahl dominiert) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 22  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (I) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 6 j=j-1; 6 c6 7 A[j+1]=key; 7 c7 𝑛−1 Analysiere, wie oft jede Zeile maximal ausgeführt wird Jede Zeile 𝑖 hat Aufwand 𝑐𝑖 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 23  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (II) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 Z5+𝑛 − 1 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 𝑛(𝑛 − 1)Τ2 6 j=j-1; 6 c6 𝑛(𝑛 − 1)Τ2 7 A[j+1]=key; 7 c7 𝑛−1 Zeilen 4, 5 und 6 im schlimmsten Fall bis j=-1 also jeweils i-mal. Insgesamt: Analysiere, wie oft jede Zeile 𝑛−1 maximal ausgeführt wird 𝑛(𝑛 − 1) ෍𝑖 = 2 Jede Zeile 𝑖 hat 𝑖=1 Aufwand 𝑐𝑖 (Zeile 4 jeweils einmal mehr bis Abbruch) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 24  𝑛 Anzahl zu Laufzeitanalyse Insertion Sort (III) sortierender Elemente Zeile Aufwand Anzahl insertionSort(A) 1 FOR i=1 TO A.length-1 DO 1 c1 𝑛 // insert A[i] in pre-sorted sequence A[0..i-1] 2 c2 𝑛−1 2 key=A[i]; 3 c3 𝑛−1 3 j=i-1; // search for insertion point backwards 4 c4 Z5+𝑛 − 1 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right5 c5 𝑛(𝑛 − 1)Τ2 6 j=j-1; 6 c6 𝑛(𝑛 − 1)Τ2 7 A[j+1]=key; 7 c7 𝑛−1 maximale Gesamtlaufzeit Insertion-Sort: Analysiere, wie oft jede Zeile maximal ausgeführt wird 𝑇 𝑛 = 𝑐1 ∙ 𝑛 + 𝑐2 + 𝑐3 + 𝑐4 + 𝑐7 ∙ 𝑛 − 1 +(𝑐4 + 𝑐5 + 𝑐6) ∙ 𝑛(𝑛−1) 2 Jede Zeile 𝑖 hat Aufwand 𝑐𝑖 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 25 Kosten für individuelle Schritte? Wie teuer ist z.B. Zuweisung A[j+1]=A[j] in Zeile 5, also was ist 𝑐5? Hängt stark von Berechnungsmodell ab (in dem Pseudocode-Algorithmus umgesetzt wird)… CPU Quelle: ke.tu-darmstadt.de Quelle: de.wikipedia.org/wiki/Turingmaschine Schaltkreis RAM Turingmaschine nehmen üblicherweise an, dass elementare Operationen (Zuweisung, Vergleich,…) in einem Schritt möglich → 𝒄𝟓 = 𝟏 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 26 Asymptotische Vereinfachung (I) Zeit 𝑇(𝑛) Gesamtlaufzeit Insertion-Sort (mit 𝑐𝑖 = 1): 𝐷(𝑛) 𝑇 𝑛 = 𝑛 + 4 ∙ 𝑛 − 1 + 3 ∙ 𝑛(𝑛−1)2 Zum Vergleich (nur dominanter Term) : 𝐷(𝑛) = 3 ∙ 𝑛(𝑛−1) 2 𝑛 𝑇(𝑛) 𝐷(𝑛) relativer Fehler (𝑻 𝒏 − 𝑫 𝒏 )Τ𝑻(𝒏) 100 15.346 14.850 3,2321 % 1.000 1.503.496 1.498.500 0,3323 % 10.000 150.034.996 149.985.000 0,0333 % 100.000 15.000.349.996 14.999.850.000 0,0033 % 1.000.000 150.000.034.999.996 1.499.998.500.000 0,0003 % Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 27 Asymptotische Vereinfachung (II) Weiter Vereinfachung (nur abhängiger Term) : 𝐴(𝑛) = 𝑛(𝑛−1) 2 Zum Vergleich (nur dominanter Term) : 𝐷(𝑛) = 3 ∙ 𝑛(𝑛−1) 2 Konstante ändert sich „schnell“ durch Fortschritte in Rechenleistung Konstante hängt stark vom Berechnungsmodell ab Beispiel Moore‘s Law (bis ca. 2000): Verdoppelung der Transistoren etwa alle 1,5 Jahre Quelle: de.wikipedia.org/wiki/Mooresches_Gesetz Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 28  Paul Bachmann 𝚯-Notation / Landau-Symbole Edmund Landau ca. 1900 Funktionen 𝑓, 𝑔: ℕ ⟶ ℝ>0 Eingabekomplexität Laufzeit Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐1 𝑔(𝑛) und 𝑐2 𝑔(𝑛) für hinreichend große 𝑛 eingeschlossen Funktion 𝑓 Für alle 𝑛 größer gleich 𝑛0 Schreibweise: 𝑓 ∈ Θ 𝑔 , manchmal auch 𝑓 = Θ 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 29 Veranschaulichung 𝚯-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) 𝑐2 𝑔(𝑛) ≥ 𝑓(𝑛) 𝑔(𝑛) ist eine asymptotisch scharfe Schranke von 𝑓(𝑛) Θ-Notation beschränkt eine Funktion asymptotisch von oben und unten Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 30 Beispiel: Laufzeit Insertion Sort 𝐢𝐧 𝚯-Notation (I) 𝑇 𝑛 =𝑛+4∙ 𝑛−1 +3∙𝑛 𝑛−1 2 = Θ(𝑛2 ) Für untere Schranke wähle 𝑐1 = 32 und 𝑛0 = 2: 𝑇 𝑛 ≥ 5∙ 𝑛−1 + 32 ∙ 𝑛2 − 32 ∙ 𝑛 7 ≥ 2 ∙𝑛−5 + 32 ∙ 𝑛2 3 ≥ 2 ∙ 𝑛2 für 𝑛 ≥ 2 Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 31 Beispiel: Laufzeit Insertion Sort 𝐢𝐧 𝚯-Notation (II) 𝑛 𝑛−1 für 𝑐1 = 32, 𝑇 𝑛 =𝑛+4∙ 𝑛−1 +3∙ 2 = Θ(𝑛2 ) 𝑐2 = 7, 𝑛0 = 2 Für obere Schranke wähle 𝑐2 = 7 und das bereits fixierte 𝑛0 = 2: 𝑇 𝑛 ≤𝑛+ 4∙𝑛 + 2 ∙ 𝑛(𝑛 − 1) ≤ 5∙𝑛 + 2 ∙ 𝑛2 ≤ 5 ∙ 𝑛2 + 2 ∙ 𝑛2 ≤ 7 ∙ 𝑛2 Θ 𝑔 = 𝑓 ∶ ∃ 𝑐1 , 𝑐2 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐1 𝑔(𝑛) ≤ 𝑓(𝑛) ≤ 𝑐2 𝑔(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 32 𝚶-Notation Obere asymptotische Schranke Ο 𝑔 = 𝑓 ∶ ∃ 𝑐 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐𝑔 𝑛 für hinreichend große 𝑛 Funktion 𝑓 beschränkt Für alle 𝑛 größer gleich 𝑛0 Sprechweise: 𝑓 wächst höchstens so schnell wie 𝑔 Schreibweise: 𝑓 = Ο 𝑔 oder auch 𝑓𝜖 Ο 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 33 Veranschaulichung der 𝚶-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 0 ≤ 𝑓(𝑛) ≤ 𝑐𝑔(𝑛) Beachte: Θ 𝑔(𝑛) ⊆ Ο 𝑔(𝑛) und somit 𝑓 𝑛 =Θ 𝑔 ⟹𝑓 𝑛 =Ο 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 34 𝚶-Notation: Rechenregeln Konstanten: 𝑓 𝑛 = 𝑎 mit 𝑎 ∈ ℝ>0 konstant. Dann 𝑓 𝑛 = Ο 1 Skalare Multiplikation: 𝑓 = Ο 𝑔 und 𝑎 ∈ ℝ>0. Dann 𝑎 ⋅ 𝑓 = Ο 𝑔 Addition: 𝑓1 = Ο 𝑔1 und 𝑓2 = Ο 𝑔2. Dann 𝑓1 + 𝑓2 = Ο max 𝑔1 , 𝑔2 punktweise Multiplikation: 𝑓1 = Ο 𝑔1 und 𝑓2 = Ο 𝑔2. Dann 𝑓1 ⋅ 𝑓2 = Ο 𝑔1 ⋅ 𝑔2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 35 Ω-Notation Untere asymptotische Schranke Ω 𝑔 = 𝑓 ∶ ∃ 𝑐 ∈ ℝ>0 , 𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛) Positive Konstanten 𝑓(𝑛) wird von 𝑐𝑔 𝑛 für hinreichend große 𝑛 Funktion 𝑓 unten beschränkt Für alle 𝑛 größer gleich 𝑛0 Sprechweise: 𝑓 wächst mindestens so schnell wie 𝑔 Schreibweise: 𝑓 = Ω 𝑔 oder auch 𝑓ϵ Ω 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 36 Veranschaulichung der Ω-Notation Quelle: Corman et al. Introduction to Algorithms 𝑛 ≥ 𝑛0 : 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛) Beachte: Θ 𝑔(𝑛) ⊆ Ω 𝑔(𝑛) und somit 𝑓 𝑛 =Θ 𝑔 ⟹𝑓 𝑛 =Ω 𝑔 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 37  Überlegen Sie sich die Rechenregeln für Ω analog zu denen für die 𝑂-Notation. Überlegen Sie sich, dass gilt: 𝑂 𝑛 ⊆ 𝑂 𝑛2 ⊆ 𝑂 𝑛3 ⊆ 𝑂 𝑛4 ⊆ 𝑂 𝑛5 ⊆ … und Ω 𝑛 ⊇ Ω 𝑛2 ⊇ Ω 𝑛3 ⊇ Ω 𝑛4 ⊇ Ω 𝑛5 ⊇… und dass die Inklusionen jeweils strikt sind Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 38 Zusammenhang 𝑶, Ω und 𝚯 Für beliebige 𝑓 𝑛 , 𝑔 𝑛 : ℕ ⟶ ℝ>0 gilt: 𝑓 𝑛 = Θ(𝑔 𝑛 ) genau dann, wenn 𝑓 𝑛 = Ο(𝑔 𝑛 ) und 𝑓 𝑛 = Ω(𝑔 𝑛 ) Beachte: Ω 𝑔 , 𝑂 𝑔 sind nur untere bzw. obere Schranken: Beispiel: 𝑓(𝑛) = Θ 𝑛3 , also auch: 𝑓 𝑛 = 𝑂 𝑛5 , da Θ 𝑛3 ⊆ 𝑂 𝑛3 ⊆ 𝑂 𝑛5 𝑓 𝑛 = Ω(𝑛), da Θ 𝑛3 ⊆ Ω 𝑛3 ⊆ Ω(𝑛) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 39 Anwendung O-Notation (I) 𝑓 = 𝑂(𝑔) übliche Schreibweise, sollte aber gelesen werden als 𝑓 ∈ 𝑂(𝑔) Allgemein besser immer als Mengen auffassen und von links nach rechts lesen (mit ∈, ⊆): 5 ∙ 𝑛2 + 𝑛4 = 𝑂 𝑛2 + 𝑛4 = 𝑂 𝑛4 = 𝑂(𝑛5 ) ∈ ⊆ ⊆ als Menge 𝑓 𝑛 + 𝑛4 = { 𝑓(𝑛) + 𝑛4 } nicht: 𝑶 𝒏𝟒 = 𝑶 𝒏𝟓 , und damit auch 𝑶 𝒏𝟓 = 𝑶 𝒏𝟒 wird mit Mengenschreibweise klarer: 𝐴 ⊆ 𝐵 bedeutet allgemein nicht auch 𝐵 ⊆ 𝐴 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 40 Anwendung O-Notation (II) Ungleichungen mit ≤ sollten nur mit 𝑂 verwendet werden, Ungleichungen mit ≥ sollten nur mit Ω verwendet werden. 5 ∙ 𝑛2 + 𝑛4 ≤ 6 ∙ 𝑛4 = 𝑂 𝑛4 es gibt 𝑐, 𝑛0 und Funktion 𝑓(𝑛) mit 6 ∙ 𝑛4 ≤ 𝑐 ∙ 𝑓(𝑛) obere Schranke vs. untere Schranke nicht: 𝟓 ∙ 𝒏𝟐 + 𝒏𝟒 ≤ 𝟔 ∙ 𝒏𝟒 = 𝜴 𝒏𝟒 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 41 𝑶, Ω und 𝚯 bei Insertion Sort (I) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; Algorithmus macht maximal 𝑇 𝑛 viele Schritte und 𝑇 𝑛 = Θ(𝑛2 ) Also Laufzeit Insertion Sort = Θ(𝑛2 ) ? korrekte Anwendung: Laufzeit ≤ 𝑇 𝑛 = 𝑂(𝑛2 ) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 42 𝑶, Ω und 𝚯 bei Insertion Sort (II) insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; zur Erinnerung: (Worst-Case-)Laufzeit 𝑇(𝑛) = max { Anzahl Schritte für x } Für untere Schranke muss man „nur“ eine schlechte bzw. die schlechteste Eingabe x finden Dann gilt 𝑇(𝑛) ≥ Anzahl Schritte für schlechtes x Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 43  𝑶, Ω und 𝚯 bei Insertion Sort (III) Insertion Sort hat quadratische insertionSort(A) Laufzeit Θ(𝑛2 ) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; „Schlechte“ Eingabe: A 𝑛 𝑛−1 𝑛−2 … … 2 1 Jede WHILE-Schleifenausführung für 𝑖 = 1, … , 𝑛 − 1 macht jeweils 𝑖 Iterationen Insgesamt macht Algorithmus für A also σ𝑛−1 𝑖=1 𝑖 = 𝑛(𝑛−1) 2 = Ω(𝑛2 ) Schritte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 44 „Gute“ Eingaben für Insertion Sort? insertionSort(A) 1 FOR i=1 TO A.length-1 DO // insert A[i] in pre-sorted sequence A[0..i-1] 2 key=A[i]; 3 j=i-1; // search for insertion point backwards 4 WHILE j>=0 AND A[j]>key DO 5 A[j+1]=A[j]; // move elements to right 6 j=j-1; 7 A[j+1]=key; „gute“ Eingaben bereits vorsortiert, extremes Beispiel: A 1 2 3 … … 𝑛−2 𝑛−1 WHILE-Schleife wird für dieses A nie ausgeführt Insgesamt macht Algorithmus für dieses A also Θ(𝑛) Schritte Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 45 Laufzeit Insertion Sort (I) „guter“ Fall „schlechter“ Fall (fast vorsortiertes Array) (invertiertes, vorsortiertes Array) Quelle: https://web.archive.org/web/20150302064244/http://www.sorting-algorithms.com/insertion-sort Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 46 Laufzeit Insertion Sort (II) „guter“ Fall „schlechter“ Fall (fast vorsortiertes Array) (invertiertes, vorsortiertes Array) Quelle: https://web.archive.org/web/20150302064244/http://www.sorting-algorithms.com/insertion-sort Insertion Sort hat Wort-Case-Laufzeiten: auch wenn für manche Eingaben schneller, gilt: quadratische Laufzeit Θ(𝑛2 ) Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 47 Komplexitätsklassen 𝑛 ist die Länge der Eingabe (z.B. Arraylänge, Länge des Strings) Klasse Bezeichnung Beispiel Θ(1) Konstant Einzeloperation Θ(log 𝑛) Logarithmisch Binäre Suche Θ(𝑛) Linear Sequentielle Suche Θ(𝑛 log 𝑛) Quasilinear Sortieren eines Arrays Θ(𝑛2 ) Quadratisch Matrixaddition Θ(𝑛3 ) Kubisch Matrixmultiplikation Θ(𝑛𝑘 ) Polynomiell Θ(2𝑛 ) Exponentiell Travelling-Salesperson* Θ(𝑛!) Faktoriell Permutationen *wenn der Algorithmus geschickt implementiert ist Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 48 𝝄-Notation und ω-Notation nicht asymptotisch scharfe Schranken 𝜊 𝑔 = 𝑓 ∶ ∀ 𝑐 ∈ ℝ>0 , ∃𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑓 𝑛 < 𝑐𝑔(𝑛) Gilt für alle Konstanten 𝑐 > 0, in Ο-Notation für eine Konstante 𝑐 > 0 Beispiel: 2𝑛 = 𝜊 𝑛2 und 2𝑛2 ≠ 𝜊 𝑛2 𝜔 𝑔 = 𝑓 ∶ ∀𝑐 ∈ ℝ>0 , ∃𝑛0 ∈ ℕ, ∀𝑛 ≥ 𝑛0 , 0 ≤ 𝑐𝑔 𝑛 < 𝑓(𝑛) 2 𝑛2ൗ Beispiel: 𝑛 ൗ2 = ω 𝑛 und 2 ≠ 𝜔 𝑛2 Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 49  Was macht der folgende Sortier-Algorithmus Bubble-Sort? bubbleSort(A) 1 FOR i=A.length-1 DOWNTO 0 DO 2 FOR j=0 TO i-1 DO 3 IF A[j]>A[j+1] THEN SWAP(A[j],A[j+1]); //temp=A[j+1]; A[j+1]=A[j]; A[j]=temp; Welche Laufzeit hat der Algorithmus? Wie verhält er sich im Vergleich zu Insertion Sort? Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 50  Merge Sort Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 51  Entwurfsmethoden Idee Divide & Conquer (& Combine) → Abschnitt 7 Teile Liste in Hälften, sortiere (rekursiv) Hälften, sortiere wieder zusammen (Teil-)Sortierung 53 12 17 44 können im Array A[0…3] selbst erfolgen 53 12 17 44 A[0…1], A[2…3] 53 12 17 44 A,A,A,A 12 53 17 44 A[0…1], A[2…3] linke & rechte Grenze A[0…3] 12 17 44 53 beschreiben Teilliste Algorithmen und Datenstrukturen | Marc Fischlin | SS 24 | 02 Sortieren | 52 Algorithmus: Merge Sort Wir sortieren im Array A zwischen Position left (links) und right (rechts) mergeSort(A,left,right) //initial left=0,right=A.length-1 1 IF left