Algorithmen 2, Vorlesung, WS17/18

Algorithmen 2, Vorlesung, WS17/18

By Karlsruher Institut für Technologie (KIT)Education
Download on the App Store

Algorithmen 2, Vorlesung, WS17/18 episodes

  • 06: Algorithmen 2, Vorlesung, WS 2017/18, 07.11.2017
    06 |
    0:00:00 Starten
    0:00:32 4 Stringology (Zeichenkettenalgorithmen)
    0:04:16 Strings Sortieren
    0:15:40 Strings Sortieren - Laufzeitanalyse
    0:18:27 Naives Pattern Matching
    0:55:49 Volltextsuche von langsam bis Superschnell
    1:04:37 Suffixtabellen
    1:05:37 Etwas ""Stringology""-Notation
    1:07:03 Suffixe Sortieren
    1:14:18 Volltextsuche
    1:14:38 Suffix-Baum
    1 hr 25 min
  • 05: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 06.11.2017
    05 |
    0:00:00 Starten
    0:00:34 Turing-Reduzierbarkeit
    0:02:47 Pseudopolynomielle Laufzeit
    0:05:58 Zwei kleine Warnungen
    0:07:55 KNAPSACK Suchproblem
    0:10:22 KNAPSACK: Codierungen der Eingabe
    0:11:47 Schwere des KNAPSACK Suchproblems
    0:12:41 KNAPSACK: pseudopolynomielle Laufzeit
    0:22:08 Polynomielle Approximationsschema
    0:25:56 PTAS versus FPTAS
    0:26:34 Von pseudopolynomieller zu polynomieller Laufzeit
    0:28:12 FPTAS für KNAPSACK
    0:32:14 epsApproxKnapsack ist FPTAS
    0:32:46 epsApproxKnapsack ist FPTAS: Approximation
    0:36:12 epsApproxKnapsack ist FPTAS: Polynomialzeit
    0:37:06 Varianten von Approximation: zwei Beispiele
    0:37:56 Anfang der Übung
    0:38:33 Approximationsalgorithmen: Grundlagen
    0:40:40 Approximationsalgorithmen: Gütemaß
    0:43:43 Approximationsalgorithmen: Klassen
    0:47:55 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen
    0:49:52 2-Approximation für Jobs Scheduling
    0:51:27 4/3- Approximation für Jobs Scheduling
    0:52:00 Fall 1: kleiner Job
    0:56:49 Nur große Jobs
    1:03:52 Minimum Metric TSP
    1:13:46 Kleine Änderung in der Definition
    1:14:21 Perfekt balancierte Graphpartitionierung
    1:15:58 3-Partion
    1:17:08 Reduktion
    1 hr 21 min
  • 04: Algorithmen 2, Vorlesung, WS 2017/18, 30.10.2017
    04 |
    0:00:00 Starten
    0:01:07 Suchprobleme
    0:04:15 Approximation bei Suchprobleme
    0:07:10 Approximation bei Zählprobleme
    0:08:51 Job Scheduling: Aufgabenstellung
    0:13:14 Naheliegender Algorithmus: listScheduling
    0:20:19 Eigenschaften des Algorithmus
    0:26:55 Approxiamtionsfaktor
    0:28:43 Eigenschaften des Algorithmus (2)
    0:34:43 Erinnerung: TSP-Suchproblem
    0:37:41 TSP-alpha-Approximations-Suchproblem
    0:40:06 Erinnerung: Hamiltonkreis (Entscheidungdproblem)
    0:41:02 Schwere Approximierbarkeit des TSP
    0:42:09 Schwere Approximierbarkeit des TST: Konstruktion
    0:52:57 MetricTSP
    1 hr 8 min
  • 03: Algorithmen 2, Vorlesung, WS 2017/18, 24.10.2017
    03 |
    0:00:00 Starten
    0:00:10 Kapitel: Randomisierte Algorithmen
    0:00:45 Überblick
    0:02:44 Erdos-Renyi-Zufallsgraphen
    0:04:59 ER-Graphen: einfache Beobachtungen
    0:11:05 Manchmal interessieren sehr große n und asymptotische Eigenschaften
    0:15:21 ER-Graphen:Durschmesser <=2
    0:21:51 Zusammenhangskomponenten
    0:23:15 Erwartet konstanter Knotengrad
    0:24:21 Andere Anforderungen?
    0:24:58 Barabasi-Albert Modell
    28 min
  • 02: Algorithmen 2, Vorlesung, WS 2017/18, 23.10.2017
    02 |
    0:00:00 Starten
    0:01:08 Erinnerung an W-Theorie
    0:02:22 Randomisierter Quicksort
    0:04:34 randQS: Anzahl Vergleiche
    0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt.
    0:28:25 Chernoff-Schranken
    0:29:04 Einfache Schranken
    0:32:19 Chernoff-Schranken
    0:38:03 Chernoff-Schranken: Beweis von Teil 1
    0:44:26 Chernoff-Schranken: Verienfachungen
    0:45:47 Chernoff-Schranken: Korollare
    0:47:14 Auswertung von Und-Oder-Bäume
    0:51:13 Satz
    0:53:50 Beweis
    1:00:35 Zwischenüberlegung
    1:04:58 Algorithmus: randomisierte UOB-Auswertung
    1:07:20 Satz
    1:09:19 Beweis
    1:18:58 Satz
    1 hr 21 min
  • 01: Algorithmen 2, Vorlesung, WS 2017/18, 17.10.2017
    01 |
    0:00:00 Starten
    0:00:10 Kapitel: Randomisierte Algorithmen
    0:01:10 Überblick
    0:01:38 Sichtweisen für randomisierte Algorithmen
    0:03:33 Fundamentale Änderung
    0:04:03 Beispiel: Randomisierter Quicksort
    0:05:32 Zufallsvariablen überall
    0:05:49 Errinerung an W-Theorie
    0:09:32 Standardbeispiel: Würfeln
    0:15:26 Algorithmen mit unbekannter Laufzeit
    0:16:25 Algorithmen, die ""variierende Ausgaben"" liefern
    0:21:05 Vorteile randomisierter Algorithmen
    0:23:28 Motivation
    0:25:14 Polynome
    0:32:21 Ausblick: polynomial identity testing
    0:35:27 Randomisierter Quicksort
    0:37:27 randQS: Anzahl Vergleiche
    43 min

About Algorithmen 2, Vorlesung, WS17/18

From the publisher's feed

Algorithmen 2, Vorlesung, WS17/18

More shows like Algorithmen 2, Vorlesung, WS17/18

IEEE International Conference on Robotics and Automation, 2013 by Karlsruher Institut für Technologie (KIT)

IEEE International Conference on Robotics and Automation, 2013

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung

0 Listeners

Theoretische Grundlagen der Informatik, Vorlesung, WS18/19 by Karlsruher Institut für Technologie (KIT)

Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

0 Listeners

Digitaltechnik und Entwurfsverfahren, WS12/13, Vorlesung by Karlsruher Institut für Technologie (KIT)

Digitaltechnik und Entwurfsverfahren, WS12/13, Vorlesung

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung

0 Listeners

Softwaretechnik 1, Vorlesung, SS2018 by Karlsruher Institut für Technologie (KIT)

Softwaretechnik 1, Vorlesung, SS2018

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019

0 Listeners

Algorithmen 1, SS2019, Vorlesung by Karlsruher Institut für Technologie (KIT)

Algorithmen 1, SS2019, Vorlesung

0 Listeners

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 by Karlsruher Institut für Technologie (KIT)

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

0 Listeners