⬑ Liste aller flipped lectures.  —  Algorithmen und Datenstrukturen

Lektion 3: Analyse von Algorithmen

In dieser Lektion behandeln wir die Grundlagen für den Vergleich von verschiedenen Algorithmen.

Lernziele

  • (einfache) Algorithmen mathematisch analysieren und vergleichen können
  • wissenschaftliche Laufzeitexperimente durchführen können
  • Bedeutung, Nutzen und Beschränkungen von asymptotischen Aussagen (~, O, Θ, Ω) kennen

Fragensammlung für die Q&A Session

Tragt hier Fragen ein, die während der Vorbereitung aufkamen, und die ihr gerne klären möchtet. Bewertet außerdem die existierenden Fragen.

Hausordnung
  • Es ist explizit erlaubt/erwünscht, auch die Fragen unter den Videos hierher zu kopieren, die ihr in der Q&A Session besprechen wollt.
  • Auch wenn ihr gerade keine eigene Frage stellen möchtet, sind die Fragen der anderen oft hilfreiche Denkanstöße auch für euch. Deshalb, und um Fragen für die Q&A Sessions zu priorisieren, könnt ihr Fragen bewerten.
    Tragt dazu bei einer Frage entweder ein (zusätzliches) »+« ein, wenn ihr diese Frage interessant findet, oder ein (zusätzliches) »-«, wenn ihr sie nicht hilfreich findet (z.B. weil die Antwort direkt im Video gegeben wird). Listet zur besseren Übersicht zuerst alle »+«, dann alle »-«, jeweils in 5er Gruppen.
  • Bevor ihr eine neue Frage eintragt, schaut ob eine existierende Frage eurer sehr nahe kommt; wenn ja, schreibt eure Frage als alternative Formulierung zu dieser Frage dazu.
  • Wenn ihr der Meinung seid, ihr könnt eine Frage in wenigen Worten beantworten, so ergänzt eure Antwort unterhalb der Frage. Auch diese Antworten könnt ihr bewerten, wenn ihr sie hilfreich findet, oder Erwiderungen ergänzen, wenn ihr sie für falsch haltet.
  • Seid konstruktiv.

Material

Die Videos entstammen dem Coursera MOOC Algorithms Part I von Robert Sedgewick und Kevin Wayne.

1 – Analysis of Algorithms Introduction

Einführung und Motivation für die Analyse von Algorithmen

Aufgaben zur Vorbereitung:

  1. Welches sind die verschiedenen vorgestellten Charaktere und ihre Perspektive auf Algorithmen?
  2. Was sind laut Sedgewick Gründe dafür, Algorithmen zu analysieren? (Bring deine Liste mit zur Vorlesung!)
  3. Was ist die scientific method? Erkläre die fünf Schritte an einem Beispiel deiner Wahl aus der (Natur-)Wissenschaft!

2 – Observations

Experimente mit Algorithmen

Aufgaben zur Vorbereitung:

  1. Was ist das 3-SUM Problem? Was ist die Eingabe, was die Ausgabe?
  2. Wie misst Sedgewick die Laufzeit von Algorithmen in Java?
  3. Wie ermittelt man graphisch (manuell) den Exponenten eines power law?
  4. Wie kommt man zur doubling hypothesis? Wie könnte ein (wissenschaftliches) Experiment zur Überprüfung einer doubling hypothesis aussehen?

3 – Mathematical Models

Abstraktion von Laufzeit zu einem mathematischen Modell

Aufgaben zur Vorbereitung:

  1. Wie setzt sich die idealisierte Laufzeit eines Programms laut Donald Knuth zusammen?
  2. Welche beiden Vereinfachungen nimmt Sedgewick vor, um die Analyse von realistischen Programmen möglich zu machen?
  3. Was ist die idealisierte Laufzeit von 3-SUM laut der vereinfachten Analyse? Was ist das verwendete mathematische Modell (was wird gezählt)?

Achtung: Die Laufzeit für subtring hat sich in Java 7 geändert; die Angabe im Video stimmt somit nicht mehr ...

4 – Order of Growth Classifications

Konzept der asymptotischen Komplexität, binäre Suche

Aufgaben zur Vorbereitung:

  1. Was ist asymptotische Komplexität (order of growth)?
  2. Welche »Übersetzungsregeln« von Code zu Laufzeitkomplexiät listet Sedgewick?
  3. Was ist binäre Suche (binary search)? Was sind Eingabe, Ausgabe und Vorbedingungen?
  4. Beschreibe intuitiv, warum binäre Suche logarithmische Komplexität hat.
  5. Was sind die Schritte, die Sedgewick verwendet, um binary search mathematisch zu analysieren? Welches Kostenmodell wird verwendet (was wird gezählt)?
  6. Wie kann man 3-SUM unter Verwendung von binary search effizienter lösen?

5 – Theory of Algorithms

best case, worst case, average case; untere Schranken und optimale Algorithmen

Aufgaben zur Vorbereitung:

  1. Was versteht man unter best/worst/average-case analysis?
  2. Was ist (in der theoretischen Algorithmik) ein optimaler Algorithmus? Seid präzise!
  3. Ist ein theoretisch optimaler Algorithmus (in der Praxis) der beste? Sammle Gründe für deine Antwort!
  4. Was ist die Bedeutung von Big-Oh, Big-Omega und Big-Theta laut diesem Video?
  5. Worin besteht (laut Sedgewick) das Problem in Big-Oh Aussagen über Laufzeiten?

6 – Memory

Grundlagen zum Speicherbedarf von Programmen

Aufgaben zur Vorbereitung:

  1. In welchen Einheiten wird Speicherplatz gemessen?
  2. Welchen Speicherbedarf in Java haben int, long, double? Wie viel Speicher benötigt eine Objektreferenz? Wie viel ein Objekt?
  3. Was ist garbage collection?