Algorithmen 1, SS2018, Vorlesung

03 |

0:00:00 Start

0:00:17 Roadmap

0:01:27 Tutorien

0:04:20 Effizienz von Algorithmen

0:09:09 Generelles Beispiel

0:10:38 Eingabegröße und Laufzeit

0:12:12 Genauer: Laufzeit

0:13:48 O - Notation

0:19:59 Omega Notation

0:20:16 Asymptotische Notationen

0:21:14 Nochmal anschaulich

0:21:18 Betrachtung über Grenzwerte

0:23:57 Ein Kniffligeres Beispiel

0:26:22 Basis des Logarithmus

0:27:21 Korrektheit von Algorithmen

0:28:19 Invarianten

0:40:50 Teile und Herrsche Paradigma

0:41:42 Rekursion: Laufzeit

0:43:35 Karatsuba-Ofman Multiplikation

0:45:12 Mastertheorem

0:48:11 Abschätzung von Rekurrenzen

02 |

0:00:00 Start

0:00:18 Rückblick Vorlesung 18.04

0:01:15 RAM vs. Compiler-Zwischensprache LLVM

0:05:03 Überblick heutige Vorlesung

0:06:16 Pseudocode

0:09:01 Design by Contract

0:16:14 Schleifeninvarianten

0:18:39 Beispiel

0:25:34 Rechenbeispiel

0:34:43 Zum power Algorithmus

0:37:32 Laufzeitanalyse / Rekurrenzen

0:42:10 Eine Rekurrenz für Teile und Herrsche

0:49:45 Master Theorem (einfache Form)

0:53:52 Beweisskizze: Allgemeines

0:59:37 Beweisskizze Fall db

1:07:27 Master Theorem Beispiele

1:08:56 Graphen

1:11:45 Bäume

1:13:18 Ein erster Graphalgorithmus

1:18:28 Beispiel

1:20:51 P und NP

01 |

0:00:00 Starten

0:00:10 Ankündigung

0:01:02 Rückblick - Vorlesung 16.04.2018

0:03:37 Hintergrund rekursiver Algorithmus

0:07:28 Ein rekursiver Algorithmus

0:10:35 Analyse

0:19:54 Karatsuba-Ofman-Multiplikation [1962]

0:23:44 Karatsuba-Ofman-Algorithmus

0:26:10 Beispiel

0:26:53 Analyse

0:29:22 Geht es noch besser?

0:36:02 Algorithm Engineering - Was hat das mit der Praxis zu tun?

0:39:35 Algorithmentheorie

0:40:27 Algorithmik als Algorithm Engineering

0:41:12 Zurück zur Langzahlmultiplikation

0:46:26 Skalierung

0:47:35 Einführendes und Überblick

0:49:07 (Asymptotische) Algorithmenanalyse

0:54:09 Zweite Vereinfachung: Asymptotik

1:07:05 O-Kalkül Rechenregeln

1:12:15 Maschinenmodell RAM (Random Access Machine)

1:21:01 Register

1:21:26 Hauptspeicher

1:21:53 Speicherzugriff

1:22:19 Rechnen

1:22:42 Bedingte Sprünge

1:23:35 ""Kleine"" ganze Zahlen?

1:24:06 Algorithmenanalyse im RAM-Modell

1:25:32 Mehr Maschinenmodell