Algorithmen und Datenstrukturen - 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