Algorithmen und Datenstrukturen 1 Sommersemester 2024 PDF

Algorithmen und Datenstrukturen 1 Sommersemester 2024 Herzlich willkommen! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 1 / 88 Wer ist wer? Wir: Professur für Algorithm Engineering Ulrich Meyer (Vorlesungen) R 304 – RMS 11–15, [email protected]...

Algorithmen und Datenstrukturen 1 Sommersemester 2024 Herzlich willkommen! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 1 / 88 Wer ist wer? Wir: Professur für Algorithm Engineering Ulrich Meyer (Vorlesungen) R 304 – RMS 11–15, [email protected] Alex Schickedanz, Daniel Allendorf (Übungskoordination) R312, R311 – RMS 11–15, [email protected] Amelia Linek, Anastasia Navodkina, Arne Gideon, Arne Riester, Boris Senatov, Elias Meinecke, Gerome Stiller, Hoai Vy Nguyen, Jannis Achtnich, Joshua Kannenberg, Lukas Geis, Paul Dallwig, Sebastian Beckmann, Viktor Rieß, Zeno Weil (Tutoren) ae.cs.uni-frankfurt.de/algo124 → Teaching → SoSe 2024 → Algorithmen und Datenstrukturen 1 Wer sind Sie? Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 2 / 88 Wer sind Sie? Halten Sie für Umfragen ein Browserfenster mit folgender URL offen: https://aeffm.de/vote Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 3 / 88  Wer sind Sie? (1) aeffm.de/vote Ich studiere: (A) Informatik Bachelor (B) Bioinformatik (C) Wirtschaftsinformatik (D) Informatik als Nebenfach (E) Informatik Lehramt (F) Sonstiges Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 4 / 88  Wer sind Sie? (2) aeffm.de/vote Ich studiere Informatik Bachelor im (i) i-ten Fachsemester A= b 1, B = b 2,... Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 5 / 88  Wer sind Sie? (3) aeffm.de/vote Ich besuche diese Vorlesung (ALGO-1 bzw. Datenstrukturen) zum (i) i-ten Mal A= b 1, B = b 2,... Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 6 / 88  Worum geht’s? Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 7 / 88 Abstrakte Datentypen und Datenstrukturen Ein abstrakter Datentyp ist eine Sammlung von Operationen auf einer Menge von Objekten. Eine Datenstruktur ist eine Implementation eines abstrakten Datentyps Ein Beispiel für häufig auftretende Operationen: Das Einfügen und Entfernen von Schlüsseln nach ihrem Alter. Wenn der jüngste Schlüssel zu entfernen ist: Wähle die Datenstruktur „Stack“. Wenn der älteste Schlüssel zu entfernen ist: Wähle die Datenstruktur „Schlange“ (engl. „Queue“). Wenn Schlüssel Prioritäten besitzen und der Schlüssel mit höchster Priorität zu entfernen ist: Wähle die Datenstruktur Heap. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 8 / 88 Worum geht’s? Gegeben sei ein abstrakter Datentyp. Entwerfe eine möglichst effiziente Datenstruktur. Welche abstrakten Datentypen? ▶ Stack: Einfügen und Entfernen des jüngsten Schlüssels. ▶ Warteschlange: Einfügen und Entfernen des ältesten Schlüssels. ▶ Prioritätswarteschlange: Einfügen und Entfernen des wichtigsten Schlüssels. ▶ Wörterbuch: Einfügen, Entfernen (eines beliebigen Schlüssels) und Suche. Was heißt Effizienz? ▶ Minimiere die Laufzeit und den Speicherplatzverbrauch der einzelnen Operationen. ▶ Wie skalieren die Ressourcen mit wachsender Eingabelänge? → Asymptotische Analyse von Laufzeit und Speicherplatzverbrauch Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 9 / 88 Worum geht’s? Wie können wir effiziente Algorithmen entwerfen? Wie können wir dabei effiziente Datenstrukturen geschickt einsetzen? Algorithmen? Algorithmen für Graphen: Berechne... alle Zusammenhangskomponenten eines Graphen einen minimalen Spannbaum eines Graphen einen kürzesten Weg von Knoten u nach Knoten v Generelle Entwurfsmethoden für Algorithmen: Greedy (z.B. zur Ablaufplanung) Divide & Conquer (z.B. zum Sortieren) Dynamische Programmierung (z.B. für Paarweises Alignment) Effizienz? → Asymptotische Analyse von Laufzeit und Speicherplatzverbrauch Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 10 / 88 Worauf wird aufgebaut? (1) Diskrete Modellierung (bzw. Vorkurs): ▶ Vollständige Induktion und allgemeine Beweismethoden. ▶ Siehe hierzu auch die Seite des Vorkurs Informatik mit Folien zu Beweistechniken, Induktion und Rekursion und Asymptotik und Laufzeitanalyse. (2) Grundlagen der Programmierung 1: ▶ Kenntnis der elementaren Datenstrukturen (3) Lineare Algebra und Analysis: - Logarithmen, - Grenzwerte und - asymptotische Notation. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 11 / 88 Literatur (1/2) - Skripte und Folien zur Vorlesung finden Sie auf der Webseite der Veranstaltung. - T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Introduction to Algorithms”, 2002. - M. T. Goodrich, R. Tamassia, D. M. Mount, “Data Structures and Algorithms in C++”, 2003. - M. Dietzfelbinger, K. Mehlhorn, P. Sanders, “Algorithmen und Datenstrukturen, die Grundwerkzeuge”, 2014. - R. Sedgewick, “Algorithmen in C++”, 2002. - J. Kleinberg, E. Tardos, “Algorithm Design”, 2013. - Für mathematische Grundlagen: ▶ N. Schweikardt, Diskrete Modellierung, eine Einführung in grundlegende Begriffe und Methoden der Theoretischen Informatik, 2013. (Kapitel 2,5) ▶ D. Grieser, Mathematisches Problemlösen und Beweisen, eine Entdeckungsreise in die Mathematik, Springer Vieweg 2012. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 12 / 88 Literatur (2/2) Sämtliche Textbücher befinden sich auch in der Bibliothek im Semesterapparat von “Algorithmen und Datenstrukturen 1”. Die Bibliothek befindet sich im 1. Stock in der Robert-Mayer Strasse 11-15. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 13 / 88  Organisatorisches Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 14 / 88 Übungsbetrieb Alle Details auf der Webseite! Anmeldung zu Übungen im AUGE-System bis Donnerstag, 18.04. Übungsblätter erscheinen i.d.R. jeden Montag auf der Webseite. Lösungen (als eine PDF-Datei) sind nach einwöchiger Bearbeitungszeit online über das SAP-System abzugeben. Nach Anmeldung für die Übungen über AUGE bekommen Sie per Email ihren individuellen Abgabelink für das SAP-System. Dieser Link ist das ganze Semester lang für Sie gültig. Übungsgruppen treffen sich ab nächste Woche Donnerstag, 25.04. Heute Ausgabe 0. Übungsblatt (ohne Abgabe), Besprechung ab 25.04. Ausgabe 1. Übungsblatt: Montag, 22.04. (Abgabe bis 29.04. 23:55, Besprechung ab 02.05.) Übungsaufgaben sollten mit Anderen besprochen werden, aber Lösungen müssen eigenständig aufgeschrieben werden! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 15 / 88 Klausur Hauptklausur: Montag, 29. Juli 2024, vsl. ab 9:00 Uhr. Zweitklausur: Mittwoch, 25. September 2024, vsl. ab 9:00 Uhr. Die in den Übungen erreichten Punkte werden mit einem Maximalgewicht von 10% zu den Klausurpunkten hinzugezählt: Werden in der Klausur x% und in den Übungen y % erzielt, dann ist z = x + (y /10) die Gesamtpunktzahl (y /10 kaufmännisch gerundet). Die Veranstaltung ist bestanden, wenn die Klausur bestanden ist (i.d.R. wenn x ≥ 50). Wenn die Klausur bestanden ist, hängt die Note von der Gesamtpunktzahl z ab. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 16 / 88 Übungsblätter-Stats (1) Bonus vs. Klausur ALGO1, ALGO2, DS, GL1, MOD (WS18 - WS23) 100 90 80 70 % Klausurpunkte 60 50 40 30 20 10 0 0 10 20 30 40 50 60 70 80 90 100 % Übungspunkte Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 17 / 88 Übungsblätter-Stats (2) Bonus vs. Klausur ALGO1, ALGO2, DS, GL1, MOD (WS18 - WS23) 400 > 50% Übungspunkte 320 # Studenten 240 160 80 0 1 2 3 4 5 2,400 ≤ 50% Übungspunkte 2,000 # Studenten 1,600 1,200 800 400 0 1 2 3 4 5 Note Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 18 / 88 Übungsblätter-Stats (3) Bonus vs. Klausur ALGO1 (SS20 - SS22) 90 > 50% Übungspunkte # Studenten 60 30 0 1 2 3 4 5 450 ≤ 50% Übungspunkte 375 # Studenten 300 225 150 75 0 1 2 3 4 5 Note Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 19 / 88 Übungsblätter-Stats (4) Bonus vs. Klausur MOD (WS19 - WS23) 200 > 50% Übungspunkte 160 # Studenten 120 80 40 0 1 2 3 4 5 1,000 ≤ 50% Übungspunkte 800 # Studenten 600 400 200 0 1 2 3 4 5 Note Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 20 / 88 Bevor es losgeht... Vor- und Nachbereitung der Vorlesungen Unbedingt am Übungsbetrieb teilnehmen und Aufgaben bearbeiten! Von den Teilnehmern, die 50% der Übungspunkte erreichen, bestehen nahezu 100% auch die Klausur! Teamarbeit vs. Einzelkämpfer Studieren lernen – der richtige Umgang mit den Freiheiten Sprechstunde vereinbaren per Email. Helfen Sie uns durch ihre Fragen, Kommentare und Antworten! Die Veranstaltung kann nur durch Interaktion interessant werden. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 21 / 88  Mathematische Grundlagen Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 22 / 88 Vollständige Induktion Ziel: Zeige die Aussage A(n) für alle natürlichen Zahlen n ≥ n0. Die Methode der vollständigen Induktion 1. Zeige im I NDUKTIONSANFANG die Aussage A(n0 ) und 2. im I NDUKTIONSSCHRITT die Implikation (A(n0 ) ∧ A(n0 + 1) ∧ · · · ∧ A(n)) ⇒ A(n + 1) für jede Zahl n mit n ≥ n0. A(n0 ) ∧ A(n0 + 1) ∧ · · · ∧ A(n) heißt Induktionsannahme. Häufig nimmt man „nur“ die Aussage A(n) in der Induktionsannahme an. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 23 / 88  Wiederholung? (1) demogr. aeffm.de/vote Mathematische Grundlagen: n X Gesucht ist eine kurze Formel für i i=1 n(n−1) (1) 2 n(n+1) (2) 2 n2 −1 (3) 2 (4) Hab ich mal irgendwann gelernt... (5) Zahlen als Buchstaben!?!? n(n+1) Auflösung: (2) 2 (wie beweist man das?) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 24 / 88 Die Summe der ersten n Zahlen n X n · (n + 1) i = 1 + 2 +... + n =. 2 i=1 Vollständige Induktion nach n: P1 1·(1+1) Induktionsanfang für n = 1: i=1 i = 1 und 2 = 1. ✓ Induktionsschritt von n auf n + 1: Wir nehmen an, dass ni=1 i = n·(n+1) P ▶ 2 gilt. Pn+1 Pn n·(n+1) n·(n+1)+2·(n+1) (n+2)·(n+1) ▶ i=1 i = i=1 i + (n + 1) = 2 + (n + 1) = 2 = 2 = (n+1)·(n+2) 2 und das war zu zeigen. ✓ Ein direkter Beweis: ▶ Betrachte ein Gitter mit n Zeilen und n Spalten: n2 Gitterpunkte. ▶ Wir müssen die Gitterpunkte unterhalb der Hauptdiagonale und auf der Hauptdiagonale zählen. ▶ Die Hauptdiagonale besitzt n Gitterpunkte und unterhalb der Hauptdiagonale befindet sich die Hälfte der verbleibenden n2 − n 2 Gitterpunkte. Also folgt ni=1 i = n + n 2−n = n·(n+1) P 2. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 25 / 88  Wiederholung? (2) demogr. aeffm.de/vote Mathematische Grundlagen: n X Gesucht ist eine kurze Formel für ai mit a ̸= 1. i=0 (1) 2 · an an+2 −1 (2) n an+1 −1 (3) a−1 a·n·(n−1) (4) 2 (5) Keine Ahnung... an+1 −1 Auflösung: (3) a−1 (wie beweist man das?) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 26 / 88 Die geometrische Reihe n X an+1 − 1 ai = falls a ̸= 1. a−1 i=0 Vollständige Induktion nach n: a0+1 −1 P0 Induktionsanfang für n = 0: i=0 ai = 1 und a−1 = 1. ✓ Induktionsschritt von n auf n + 1: n+1 Wir können annehmen, dass ni=0 ai = a a−1−1 gilt. Dann ist P ▶ n+1 n+1 n+2 −an+1 an+2 −1 Pn+1 i Pn ▶ i=0 a = i i=0 a + a n+1 = a a−1−1 + an+1 = a −1+a a−1 = a−1 und das war zu zeigen. ✓ Ein direkter Beweis: Pn Pn Pn (a − 1) · i=0 ai = a · i=0 ai − i=0 ai Pn+1 i Pn i n+1 = i=1 a − i=0 a = a − a0 = an+1 − 1 und das war zu zeigen. ✓ Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 27 / 88 Binomialkoeffizienten   ( n·(n−1)···(n−k +1) n! n 1·2···k = k !·(n−k )! falls 1 ≤ k ≤ n − 1, = k 1 falls k = 0 oder k = n. Sei S eine Menge von n Elementen. Dann hat S genau kn Teilmengen
der Größe k. Pn Binomischer Lehrsatz: Es gilt (a + b)n = k =0 kn ak bn−k. Also ist
n   X n = 2n : eine n-elementige Menge hat 2n Teilmengen. i i=0 Sei Perm(S) die Menge aller Permutationen von S. Dann ist |Perm(S)| = n! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 28 / 88 k -elementige Teilmengen der Menge {1,... , n} Wieviele k -elementige Teilmengen von {1,... , n} gibt es? Wir führen eine Induktion nach n. Induktionsanfang für n = 1: 1 1

▶ 0 = 1 = 1. ▶ Es gibt genau eine Teilmenge von {1} mit keinem Element sowie genau eine Teilmenge mit einem Element. n
Induktionsschritt: Wir wissen, dass {1,... , n} genau k Teilmengen mit genau k Elementen hat. ▶ Wieviele k -elementige Teilmengen von {1,... , n, n + 1} besitzen das Element n + 1 nicht? Nach Induktionsannahme genau kn Teilmengen.
▶ Wieviele k -elementige Teilmengen von {1,... , n, n + 1} besitzen das Element n + 1? n
Nach Induktionsannahme genau k −1 Teilmengen. Es ist k + k −1 = k !(n−k )! + (k −1)!(n−(k −1))! = n!(kk −1)!(n−(k n n n! n! −1))!+n!k !(n−k )!

▶ !(k −1)!(n−k )!(n−(k −1))! = n!(n−(k −1))+n!k n!(n+1) (n+1)! n+1
k !(n−(k −1))! = k !(n+1−k )! = k !(n+1−k )! = k und das war zu zeigen. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 29 / 88  Binärsuche Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 30 / 88 Binärsuche Ein Array A = (A,... , A[n]) von n Zahlen und eine Zahl x ist gegeben: Wir möchten wissen, ob und wenn ja wo die Zahl x in A vorkommt. Wenn A nicht sortiert ist, dann wird die lineare Suche bis zu n Zellen des Arrays inspizieren. Wenn das Array aber aufsteigend sortiert ist, dann können wir Binärsuche anwenden. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 31 / 88 Binärsuche: Ein Programm void Binärsuche( int unten, int oben){ if (oben < unten) std::cout « x « “ wurde nicht gefunden.“« std::endl; int mitte = (unten+oben)/2; if (A[mitte] == x) std::cout « x « “ wurde in Position “ « mitte « “ gefunden.“ « std::endl; else { if (x < A[mitte]) Binärsuche(unten, mitte-1); else Binärsuche(mitte+1,oben);}} Wir sagen, dass Zelle A[mitte] im ersten Aufruf inspiziert wird. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 32 / 88 Binärsuche: Korrektheit Wir zeigen durch vollständige Induktion nach d = oben − unten + 1, dass der Aufruf Binärsuche(unten,oben) das korrekte Ergebnis liefert. Induktionsanfang für d = 0: Es ist d = oben − unten + 1 = 0 ⇒ oben < unten. Binärsuche(unten, oben) bricht ab mit der Antwort „x wurde nicht gefunden“. ✓ Induktionsschritt d → d + 1: Es ist oben − unten + 1 = d + 1. ▶ Wenn A[mitte] = x, dann wird mit Erfolgsmeldung abgebrochen. ✓ ▶ Ansonsten, wenn x < A[mitte], sucht Binärsuche richtigerweise in der linken Hälfte und sonst in der rechten Hälfte. ▶ Die rekursive Suche in der linken bzw. rechten Hälfte verläuft aber nach Induktionsannahme korrekt. ✓ Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 33 / 88  Wiederholung? (3) demogr. aeffm.de/vote Wie groß ist die maximale Anzahl inspizierter Zellen in der Binärsuche in einem Array mit n = 2k − 1 Zellen? (1) n (2) n·k √ (3) ⌈ k⌉ (4) k (5) Nur Kleingeister suchen, das Genie beherrscht das Chaos! Auflösung: (4) k (wie beweist man das?) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 34 / 88 Binärsuche: Die Laufzeit Wie groß ist T (n) := maximale Anzahl inspizierter Zellen für ein Array mit n Zellen, für n = 2k − 1? Hier ist eine rekursive Definition von T (n): - Rekursionsanfang: T (0) := 0. - Rekursionsschritt: T (n) := T ( n−1 2 ) + 1. n−1 2k −2 1. Wir haben n = 2k − 1 gefordert. Beachte: 2 = 2 = 2k −1 − 1. 2. Wir zeigen T (2k − 1) = k mit vollständiger Induktion nach k. Induktionsanfang: T (20 − 1) = T (0) = 0. ✓ Induktionsannahme Induktionsschritt: T (2k +1 − 1) = T (2k − 1) + 1 = k + 1. ✓ Binärsuche muss höchstens k Zahlen inspizieren gegenüber 2k − 1 Zahlen für die lineare Suche: Lineare Suche ist exponentiell langsamer als Binärsuche. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 35 / 88  Unser Freund, der Logarithmus Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 36 / 88 Rechnen mit Logarithmen Seien a > 1 und x > 0 reelle Zahlen. loga (x) ist der Logarithmus von x zur Basis a und stimmt mit z genau dann überein, wenn az = x. (a) aloga (x) = x. (b) loga (x · y ) = loga x + loga y. (c) loga (x y ) = y · loga (x). (d) loga x = (loga b) · (logb x). Wir „übersetzen“ von Basis a in Basis b. Was ist 4log2 n ? log2 n = (log2 4) · (log4 n) mit (d). 4log2 n = 4(log2 4)·(log4 n) = (4log4 n )log2 4 = n2 mit (a). Was ist bloga x ? loga x = (loga b) · (logb x) mit (d). bloga x = b(loga b)·(logb x) = (blogb x )loga b = x loga b mit (a). Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 37 / 88  Laufzeitmessung Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 38 / 88 Eingabelänge Wie gut skaliert ein Programm, d.h. wie stark nimmt die Laufzeit zu, wenn die Eingabelänge vergrößert wird? Was ist denn überhaupt die Länge einer Eingabe? → Definiere Eingabelänge abhängig von der Problemstellung. Zum Beispiel: (a) Wenn ein Array mit n „Schlüsseln“ zu sortieren ist, dann ist die Anzahl n der Schlüssel ein vernünftiges Maß für die Eingabelänge. (b) Wenn ein algorithmisches Problem für einen Graphen mit Knotenmenge V und Kantenmenge E zu lösen ist, dann ist die Summe |V | + |E| der Knoten- und Kantenzahl sinnvoll. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 39 / 88 Die worst-case Laufzeit Sei P ein Programm. Für jede Eingabelänge n setze ZeitP (n) = größte Laufzeit von P auf einer Eingabe der Länge n. Wenn also die Funktion Länge : Menge aller möglichen Eingaben → N einer Eingabe x die Eingabelänge „Länge(x)“ zuweist, dann ist ZeitP (n) = max Anzahl der Schritte von Programm P für Eingabe x Eingabe x Länge(x)=n die „worst-case Laufzeit“ von P für Eingaben der Länge n. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 40 / 88 Laufzeitmessung Für welchen Rechner sollen wir die Laufzeit berechnen? Analysiere die Laufzeit auf einem abstrakten Rechner: ▶ Der Speicher besteht aus Registern, die eine ganze Zahl speichern können. ▶ Eine CPU führt einfache boolesche und arithmetische Operationen aus. ▶ Daten werden zwischen CPU und Speicher durch (indirekte) Lade- und Speicherbefehle ausgetauscht. Damit ist die Laufzeitberechnung für jeden modernen sequentiellen Rechner gültig, aber wir erhalten für einen speziellen Rechner nur eine bis auf einen konstanten Faktor exakte Schätzung. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 41 / 88 Laufzeitmessung für welche Programmiersprache und welchen Compiler? Wir „sollten“ mit einer Assemblersprache arbeiten: Wir sind vom Compiler unabhängig und die Anzahl der Anweisungen ist relativ klein. Aber die Programmierung ist viel zu umständlich und wir wählen deshalb C++ bzw. Pseudocode. Die Anzahl ausgeführter C++ Befehle ist nur eine Schätzung der tatsächlichen Anzahl ausgeführter Assembler Anweisungen. Unsere Schätzung ist auch hier nur bis auf einen konstanten Faktor exakt. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 42 / 88 Pseudocode 1 Was ist ein Algorithmus? Eine präzise definierte Rechenvorschrift, formuliert in „Pseudocode“. 2 Und was ist Pseudocode? Eine Mischung von Umgangssprache, Programmiersprache und ma- thematischer Notation. Typischerweise ist Pseudocode kompakter, aber gleichzeitig auch leichter zu verstehen als entsprechender Code einer Programmiersprache. Pseudocode folgt keinen klaren Regeln, aber natürlich muss eine nachfolgende Implementierung trivial sein! Beispiele und Aufgaben zu Pseudocode auf der Vorlesungshomepage! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 43 / 88 Laufzeit: Skalierung bei wachsender Eingabelänge Wie skaliert die Laufzeit eines Algorithmus oder einer Datenstruktur wenn die Eingabelänge wächst? Eine exakte Laufzeitbestimmung für alle Eingaben ist oft schwierig. Wir betrachten die worst-case Laufzeit in Abhängigkeit von der Eingabelänge. ▶ Unsere Laufzeitbestimmung ist letztlich nur eine, bis auf einen konstanten Faktor exakte Schätzung. ▶ Wir interessieren uns vor allen Dingen für die Laufzeit „großer“ Eingaben und „unterschlagen“ konstante Faktoren. Wir erhalten eine von der jeweiligen Rechnerumgebung unabhängige Laufzeitanalyse, die das Wachstumsverhalten der tatsächlichen Laufzeit verlässlich voraussagt. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 44 / 88 Ein Beispiel: Das Teilfolgenproblem Die Eingabe besteht aus n ganzen Zahlen a1 ,... , an. Definiere f (i, j) = ai + ai+1 + · · · + aj für 1 ≤ i ≤ j ≤ n. Das Ziel ist die Berechnung von max{f (i, j)|1 ≤ i ≤ j ≤ n}, also die maximale Teilfolgensumme. Anwendungbeispiel für Aktien: Berechne den größten Gewinn für ein Zeitintervall. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 45 / 88 Algorithmen für das Teilfolgenproblem Wir betrachten nur Algorithmen A, die ausschließlich Additionen und/oder Vergleichsoperationen auf den Daten ausführen. AdditionenA (n) = maxa1 ,...an ∈Z { Anzahl Additionen von A für Eingabe (a1 ,... , an )} VergleicheA (n) = maxa1 ,...,an ∈Z { Anzahl Vergleiche von A für Eingabe (a1 ,... , an )}. ZeitA (n) = AdditionenA (n) + VergleicheA (n) ist die worst-case Rechenzeit von Algorithmus A. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 46 / 88 Das Teilfolgenproblem: Algorithmus A1 Max = −∞; for (i=1 ; i 1 und b > 1 gilt loga n = Θ(logb n). Warum? Es gilt loga (n) = (loga (b)) · logb (n). Also folgt loga n lim = lim loga (b). n→∞ logb n n→∞ Aber a, b > 1 und deshalb 0 < loga (b) < ∞. Die Behauptung loga n = Θ(logb n) folgt. loga (n) und der Logarithmus log2 (n) zur Basis 2 haben dasselbe Wachstum: Ab jetzt arbeiten wir nur mit log2 (n). Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 55 / 88 Rechnen mit Grenzwerten f , g : N → R≥0 seien Funktionen. Die Operation ◦ bezeichne eine der Operationen +, − oder ∗. Dann gilt lim (f (n) ◦ g(n)) = lim f (n) ◦ lim g(n), n→∞ n→∞ n→∞ falls die beiden Grenzwerte auf der rechten Seite existieren und endlich sind. Und f (n) lim f (n) lim = n→∞ , n→∞ g(n) lim g(n) n→∞ gilt, falls die beiden Grenzwerte auf der rechten Seite existieren, endlich sind und limn→∞ g(n) ̸= 0 gilt. n3 +n·(n+1)/2 n3 n·(n+1)/2 lim n3 = lim 3 + lim n3 = 1. n→∞ n→∞ n n→∞ n·(n+1) n·(n+1) Also ist n3 + 2 = Θ(n3 ) und n3 + 2 ist kubisch. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 56 / 88 Die Regel von de l’Hospital Es gilt f (n) f ′ (n) lim = lim ′ , n→∞ g(n) n→∞ g (n) falls der letzte Grenzwert existiert und falls lim f (n) = lim g(n) ∈ {0, ∞}. n→∞ n→∞ ln′ (n) 1/n lim ln(n) = lim n = ∞ und lim ′ = lim = 0. n→∞ n→∞ n→∞ n n→∞ 1 ln(n) lim n = 0 und damit loga (n) = o(n) für jedes a > 1. n→∞ Der Logarithmus wächst langsamer als jede noch so kleine Potenz nb (für 0 < b): Siehe Tafel. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 57 / 88 Unbeschränkt wachsende Funktionen Die Funktionen f : N → R und g : R → R seien gegeben. (a) f sei monoton wachsend. Dann gibt es eine Konstante K ∈ N mit f (n) ≤ K oder aber limn→∞ f (n) = ∞ gilt. Insbesondere ist f = O(1) oder 1 = o(f). (b) Für jedes a > 1 ist 1 = o(loga (n)). (c) Wenn limn→∞ f (n) = limn→∞ g(n) = ∞, dann gilt limn→∞ g(f (n)) = ∞. (d) Wenn g = o(n) und 1 = o(f ), dann ist g(f (n)) lim = 0, n→∞ f (n) also ist g(f (n)) = o(f (n)). Wenn g „sublinear“ ist und f unbeschränkt wächst, dann nimmt das Wachstum von g ◦ f ab. Anwendungen: (Siehe Tafel.) 1 = o(log2 log2 (n)). log2 log2 (n) = o(log2 (n)). (k +1) (k +1) (k ) 1 = o(log2 (n)) und log2 (n) = o(log2 (n)) für jede natürliche Zahl k. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 58 / 88 Das Integralkriterium Die Funktion f : R → R sei gegeben. (a) Wenn f monoton wachsend ist, dann gilt Z n n X Z n+1 f (x)dx ≤ f (i) ≤ f (x)dx. 0 i=1 1 (b) Wenn f monoton fallend ist, dann gilt Z n+1 Xn Z n f (x)dx ≤ f (i) ≤ f (x)dx. 1 i=1 0 Zwei wichtige Konsequenzen: n X 1 = Θ(ln(n)). i i=1 n X i k = Θ(nk +1 ), falls k ≥ 0. i=1 Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 59 / 88 Eine Wachstums-Hierarchie f1 (n) = 1, dann ist f1 = o(log2 log2 n), haben wir schon eingesehen. log2 log2 n = o(log2 n), haben wir schon eingesehen. log2 n = Θ(loga n) für jedes a > 1, haben wir schon eingesehen. log2 n = o(nb ) für jedes b > 0, haben wir schon eingesehen. b n = o(n) und n = o(n · loga n) für jedes b mit 0 < b < 1 und jedes a > 1, nb 1 n 1 limn→∞ n = limn→∞ n1−b = 0 und limn→∞ n·loga n = limn→∞ loga n = 0. n · loga n = o(nk ) für jede reelle Zahl k > 1 und jedes a > 1. nk = o(an ) für jedes a > 1, nk nk = ak ·loga n und limn→∞ an = limn→∞ ak ·loga n−n = 0. und an = o(n!) für jedes a > 1. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 60 / 88  Asymptotische Notation (1) d aeffm.de/vote Seien f (n) = n1.1 / log n, g(n) = n log3 n, h(n) = 2log2 n. Ordne die Funktionen nach asympt. Wachstum. (1) f , g, h (2) f , h, g (3) g, f , h (4) g, h, f (5) h, f , g (6) h, g, f Auflösung: (6) h, g, f Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 61 / 88  Asymptotische Notation (2) mc aeffm.de/vote Sei f : N>0 → N>0. Was gilt dann? (1) f (n) + 10 = O(f (n)) (2) f (n + 10) = O(f (n)) Auflösung: (1) f (n) + 10 = O(f (n)). Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 62 / 88  Asymptotische Notation (3) mc aeffm.de/vote √ Es seien f (n) = 0.3 · n − log n und g(n) = 10 · n0.2. Was gilt dann? (1) f (n) = O(g(n)) (2) f (n) = o(g(n)) (3) f (n) = Ω(g(n)) (4) f (n) = ω(g(n)) (5) f (n) = Θ(g(n)) Auflösung: (3) & (4) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 63 / 88  Asymptotische Notation (4) mc aeffm.de/vote Pn Es seien f (n) = n log n + 4 · n2 und g(n) = i=n/2 i. Was gilt dann? (1) f (n) = O(g(n)) (2) f (n) = o(g(n)) (3) f (n) = Ω(g(n)) (4) f (n) = ω(g(n)) (5) f (n) = Θ(g(n)) Auflösung: (1) & (3) & (5) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 64 / 88  Asymptotische Notation (5) mc aeffm.de/vote qP n Es seien f (n) = | sin n| + | cos n| und g(n) = i=1 1/i. Was gilt dann? (1) f (n) = O(g(n)) (2) f (n) = o(g(n)) (3) f (n) = Ω(g(n)) (4) f (n) = ω(g(n)) (5) f (n) = Θ(g(n)) Auflösung: (1) & (2) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 65 / 88  Algorithmenentwurf, Laufzeitmessung, und asymptotische Analyse. Wie passt das alles zusammen? Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 66 / 88 Zurück zum Teilfolgenproblem: Algorithmus A2 Max = −∞; for (i=1 ; i 0 gelte. Der Baum der Rekursionsgleichung: 1. Wir sagen, dass die Wurzel root die Eingabelänge n hat. ▶ Wenn n = 1, dann markiere root mit c und root wird zu einem Blatt. ▶ Wenn n > 1, dann markiere root mit t(n). root erhält a Kinder mit Eingabelänge n/b. 2. Sei v ein Knoten des Baums mit Eingabelänge m. ▶ Wenn m = 1, dann markiere v mit c und v wird zu einem Blatt. ▶ Wenn m > 1, dann markiere v mit t(m) und v erhält a Kinder mit Eingabelänge m/b. T (n) stimmt überein mit der Summe aller Knotenmarkierungen. (kann man mit vollständiger Induktion zeigen). Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 73 / 88 Expansion und Vermutung Die Rekursionsgleichung n T (1) = c, T (n) = a · T + t(n) b ist zu lösen. n sei eine Potenz der Zahl b > 1 und a ≥ 1, c > 0 gelte. Wir expandieren die Rekursionsgleichung und erhalten n T (n) = a · T + t(n) b  n  n  = a a·T + t + t(n) b2 b n n = a2 · T +a·t + t(n) b2 b n n n = a3 · T + a 2 · t + a · t + t(n) = · · · b3 b2 b n  n  n ? = ak · T k + ak −1 · t k −1 + ··· + a · t + t(n). b b b ? Man kann die Vermutung = mit vollständiger Induktion beweisen. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 74 / 88 Eliminierung rekursiver Terme Setze k = logb n. Dann ist bk = n und T ( bnk ) = T (1) = c. n  n  n k −1 T (n) = ak · T + a · t + · · · + a · t + t(n) bk bk −1 b k −1 X n = alogb n · T (1) + aj · t bj j=0 logb n−1 n logb n−1 n X X = alogb n · c + aj · t = nlogb a · c + aj · t. bj bj j=0 j=0 Eine Beobachtung: Wenn t(n) ≤ d · nlogb (a)−ε für Konstanten ε > 0 und d > 0, dann dominiert der erste Summand nlogb a · c. Warum? Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 75 / 88 Das Mastertheorem: Formulierung Die Rekursion n T(1) = c, T(n) = a · T + t(n) b sei zu lösen. n ist eine Potenz der Zahl b > 1 und a ≥ 1, c > 0 gelte. (a) Wenn t(n) = O n(logb a)−ε für eine Konstante ε > 0,
dann ist T (n) = Θ(nlogb a ). Die Blätter im Rekursionsbaum dominieren. (b) Wenn t(n) = Θ(nlogb a ), dann ist T (n) = Θ(nlogb a · logb n). Gleichgewicht zwischen den Schichten im Rekursionsbaum. n (c) Wenn t(n) = Ω n(logb a)+ε für eine Konstante ε > 0 und a · t

b ≤ αt(n) für eine Konstante α < 1, dann T (n) = Θ(t(n)). Die Wurzel im Rekursionsbaum dominiert. Siehe Beweis des Mastertheorems im Skript. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 76 / 88 Die Laufzeit von Algorithmus A3 Wir hatten die Rekursionsgleichungen n ZeitA3 (1) = 1, ZeitA3 (n) = 2 · ZeitA3 + 2n − 1 2 erhalten. Um das Mastertheorem anzuwenden, müssen wir c = 1, a = 2, b = 2 und t(n) = 2n − 1 setzen. In welchem Fall befinden wir uns? ▶ Es ist logb a = log2 2 = 1 und t(n) = Θ(nlogb a ). ▶ Fall (b) ist anzuwenden und liefert ZeitA3 (n) = Θ(n log2 n). Algorithmus A3 ist schneller als Algorithmus A2 , denn ZeitA3 (n) n log2 n log2 n lim = lim = lim = 0. n→∞ ZeitA2 (n) n→∞ n2 n→∞ n Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 77 / 88  Und jetzt alle... d aeffm.de/vote Die Rekursion T (1) = c, T (n) = a · T bn + t(n) sei zu lösen. n ist eine Potenz
der Zahl b > 1 und a ≥ 1, c > 0 gelte. (a) Wenn t(n) = O n(logb a)−ε für eine Konstante ε > 0,
dann ist T (n) = Θ(nlogb a ). (b) Wenn t(n) = Θ(nlogb a ), dann ist T (n) = Θ(nlogb a · logb n). (logb a)+ε
(c) Wenn t(n) = Ω n für eine Konstante ε > 0 und n
a · t b ≤ α · t(n) für eine Konstante α < 1, dann T (n) = Θ(t(n)). Lösung für T (1) = Θ(1), T (n) = 4 · T (n/2) + Θ(n)? (1) T (n) = Θ(n2 · log4 n) √ (2) T (n) = Θ(n2 ) (3) T (n) = Θ(n · log n) (4) T (n) = Θ(n · log2 n) (5) T (n) = Θ(n4 ) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 78 / 88 Was kann das Mastertheorem nicht? Um das Mastertheorem anzuwenden, muss stets dieselbe Anzahl a von Teilproblemen mit n derselben Eingabelänge b rekursiv aufgerufen werden: b darf sich während der Rekursion nicht ändern. Das Mastertheorem ist nicht auf die Rekursion T (1) = 1, T (n) = T (n − 1) + n anwendbar, weil b sich ändert. Gleiches gilt für die Rekursion T (1) = 1, T (n) = 2 · T (n − 1) + 1, die die Anzahl der Ringbewegungen in den Türmen von Hanoi zählt. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 79 / 88 Das Teilfolgenproblem: Algorithmus A4 Maxk = max{f (i, j)|1 ≤ i ≤ j ≤ k } ist der Wert einer optimalen Teilfolge für die ersten k Folgenelemente. Wie lässt sich Maxk +1 effizient berechnen? Setze Max∗k = max{f (i, k )|1 ≤ i ≤ k }. Dann ist Maxk +1 = max{Maxk , Max∗k +1 }. Warum? ▶ Fall 1: Eine optimale Teilfolge enthält das Folgenelement ak +1 nicht. Dann ist Maxk +1 = Maxk. ▶ Fall 2: Eine optimale Teilfolge enthält das Folgenelement ak +1. Dann ist Maxk +1 = Max∗k +1. Max∗k +1 = max{Max∗k + ak +1 , ak +1 }. Warum? ▶ Fall 1: Eine optimale, mit dem k + 1sten Folgenelement endende Folge enthält nicht nur ak +1. Dann ist Max∗k +1 = Max∗k + ak +1. ▶ Fall 2: Sonst ist Max∗k +1 = ak +1. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 80 / 88 Algorithmus A4 (1) Max1 = Max∗1 = a1. (2) Für k = 1,... , n − 1 setze Max∗k +1 = max{Max∗k + ak +1 , ak +1 } und Maxk +1 = max{Maxk , Max∗k +1 }. (3) Maxn wird ausgegeben. Pro Schleifendurchlauf: zwei Vergleiche und eine Addition. Also insgesamt 2(n − 1) Vergleiche und n − 1 Additionen. ZeitA4 (n) = 3(n − 1) und A4 hat lineare Laufzeit, da ZeitA4 = Θ(n). n A4 ist schneller als A3 , denn lim = 0. n→∞ n log2 n Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 81 / 88  Wachstumsverhalten in der Laufzeitanalyse: Zähle Anweisungen, die die Laufzeit dominieren Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 82 / 88 Analyse von C++ Programmen Zähle ausgeführte elementare Anweisungen wie etwa Zuweisungen und Auswahl-Anweisungen (if-else und switch). ▶ Weder iterative Anweisungen (for, while und do-while) noch Sprunganwei- sungen (break, continue, goto und return) oder Funktionsaufrufe sind zu zählen. Ist der so ermittelte Aufwand denn nicht zu klein? ▶ Zähle mindestens eine ausgeführte elementare Anweisung in jedem Schleifendurchlauf oder Funktionsaufruf. ▶ Für vernünftige Programme wird die asymptotische Laufzeit korrekt ermittelt. In den meisten Fällen sind wir an der worst-case Laufzeit interessiert: ▶ Bestimme für jede Eingabelänge n die maximale Laufzeit für eine Eingabe der Länge n. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 83 / 88 Zuweisungen, Auswahl-Anweisungen und Schleifen Eine Zuweisung zu einer „einfachen“ Variablen ist einfach zu zählen, eine Zuweisung zu einer Array-Variablen ist mit der Länge des Arrays zu gewichten. Die Auswertung der Bedingung in einer Auswahl-Anweisungen ist nicht notwendigerweise zu zählen. ▶ Aber die Laufzeit hängt jetzt vom Wert der Bedingung ab! ▶ Häufig genügt die Bestimmung des Gesamtaufwands für den längsten der alternativen Anweisungsblöcke. Der Aufwand kann in jedem Durchlauf einer Schleife variieren! ▶ Häufig genügt die Bestimmung der maximalen Anzahl ausführbarer Anwei- sungen innerhalb einer Schleife sowie die Anzahl der Schleifendurchläufe. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 84 / 88 Beispiel: For-Schleifen Die Matrizenmultiplikation A · B = C: for (i=0; i < n; i++) for (j=0; j < n; j++) {C[i][j] = 0; for (k=0; k < n ; k++) C[i][j] += A[i][k] * B[k][j]; } Zähle die Anzahl der Zuweisungen. Analysiere die geschachtelten for-Schleifen durch geschachtelte Summen: X n−1 n−1 X n−1 X n−1 X X n−1 Laufzeit = (1 + 1) = (1 + n) = n2 · (1 + n). i=0 j=0 k =0 i=0 j=0 Das Programm besitzt kubische Laufzeit. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 85 / 88 Beispiel: While-Schleifen (1/2) while (n >= 1) {n = n/2; Maximal c Anweisungen, die n nicht verändern } T (n) bezeichne die Laufzeit der while-Schleife für Parameter n. Wir erhalten die Rekursionsgleichung: T (1) ≤ 1 + c, und T (n) ≤ T (n/2) + 1 + c. Wende das Mastertheorem an: ▶ a = 1, b = 2 und t(n) ≤ 1 + c. ▶ Es ist t(n) = Θ(1) = Θ(nlogb a ). ▶ Fall 2 ist anzuwenden und T (n) = Θ(log2 n) folgt. Die Laufzeit ist logarithmisch. Warum? ▶ Höchstens 1 + c Anweisungen pro Schleifendurchlauf. ▶ Und wieviele Iterationen? Na klar, 1 + ⌊log2 n⌋ viele. Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 86 / 88  While-Schleifen d aeffm.de/vote while (n >= 12) √ { n = n; Maximal c Anweisungen, die n nicht verändern } Wie hoch ist die Laufzeit? √ (1) Θ( n log n) √ (2) Θ( n) (3) Θ(log n) p (4) Θ( log(n)) (5) Θ(log(log(n)) Auflösung: (5) Θ(log(log(n)) Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 87 / 88 Beispiel: While-Schleifen (2/2) while (n > 1) n = ( n & 1 ) ? 3*n + 1 : n/2; Was „tut“ diese while Schleife? ▶ Wenn n ungerade ist, dann ersetze n durch 3 · n + 1. ▶ Wenn n gerade ist, dann ersetze n durch n2. Was ist die asymptotische Laufzeit in Abhängigkeit von der „Eingabelänge“ n? ▶ Es ist bis heute nicht bekannt, ob die Schleife für jede Eingabe terminiert! ▶ Die Laufzeit ist deshalb erst recht nicht bekannt. Die Analyse der Laufzeit kann äußerst schwierig sein! Ulrich Meyer ALGO1 – Grundlagen 30. April 2024 88 / 88