30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019

An episode of the Algorithmen 2, Vorlesung, WS18/19 podcast, hosted by M.Sc. Demian Hespe, titled "30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019" was published on February 7, 2019 and runs 86 minutes.

February 7, 2019 ·86m · Algorithmen 2, Vorlesung, WS18/19

0:00 / 0:00

Summary

30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle Algorithmen 0:12:26 Fully Polynomial Time Approximation Scheme 0:13:31 Fixed Parameter Algorithmen 0:14:49 VERTEX Cover 0:15:05 Fixed parameter tractable 0:16:32 Naive tiefenbeschränkte Suche 0:19:19 Kernbildung für Vertex Cover 0:21:45 Warum Parallelverarbeitung 0:22:58 Modell Nachrichtengekoppelte Parallelrechner 0:23:30 Kostenmodell für Nachrichtenaustausch 0:24:56 Warum kein Multicore-Modell? 0:26:18 Analyse paralleler Algorithmen 0:26:49 Pseudocode 0:27:41 Weniger ist mehr 0:28:10 Hyperwürfel 0:28:56 Hyperwürfelaulgorithmus 0:31:31 Paralleles Quicksort 0:32:00 Theoretiker-Parallelisierung 0:34:01 Onlinealgorithmen 0:34:29 Competitive analysis 0:35:19 A typical online problem: Ski rental 0:36:32 Paging 0:37:48 Comparison of algorithms 0:39:57 Discussion 0:42:00 Stringology 0:43:29 Strings Sortieren 0:47:55 Naives Pattern Matching 0:48:29 Knuth-Morris-Pratt 0:50:27 Volltextsuche von Langsam bis Superschnell 0:51:18 Invertierter Index 0:52:13 Etwas ""Stringology""-Notation 0:53:14 Suffixe Sortieren 0:53:56 Volltextsuche 0:54:45 Suffix-Baum 0:56:22 SA mit Präfix Verdopplung 0:58:05 Ein erster Teile-und-Herrsche-Ansatz 0:58:52 SA berechnen 1:00:42 Rekursion 1:03:52 LCP-Array 1:07:13 Datenkompression 1:08:51 Wörterbasierte Textkompression 1:09:59 Lempel-Ziv Kompression 1:11:29 Burrows Wheeler Transformation 1:14:47 Geometrische Algorithmen 1:15:37 Plane-Sweep-Algorithmen 1:18:08 Verallgemeinerung 1:21:33 Mehr Linienschnitt 1:22:51 Kleine einschließende Kugel

Episode Description

30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle Algorithmen 0:12:26 Fully Polynomial Time Approximation Scheme 0:13:31 Fixed Parameter Algorithmen 0:14:49 VERTEX Cover 0:15:05 Fixed parameter tractable 0:16:32 Naive tiefenbeschränkte Suche 0:19:19 Kernbildung für Vertex Cover 0:21:45 Warum Parallelverarbeitung 0:22:58 Modell Nachrichtengekoppelte Parallelrechner 0:23:30 Kostenmodell für Nachrichtenaustausch 0:24:56 Warum kein Multicore-Modell? 0:26:18 Analyse paralleler Algorithmen 0:26:49 Pseudocode 0:27:41 Weniger ist mehr 0:28:10 Hyperwürfel 0:28:56 Hyperwürfelaulgorithmus 0:31:31 Paralleles Quicksort 0:32:00 Theoretiker-Parallelisierung 0:34:01 Onlinealgorithmen 0:34:29 Competitive analysis 0:35:19 A typical online problem: Ski rental 0:36:32 Paging 0:37:48 Comparison of algorithms 0:39:57 Discussion 0:42:00 Stringology 0:43:29 Strings Sortieren 0:47:55 Naives Pattern Matching 0:48:29 Knuth-Morris-Pratt 0:50:27 Volltextsuche von Langsam bis Superschnell 0:51:18 Invertierter Index 0:52:13 Etwas ""Stringology""-Notation 0:53:14 Suffixe Sortieren 0:53:56 Volltextsuche 0:54:45 Suffix-Baum 0:56:22 SA mit Präfix Verdopplung 0:58:05 Ein erster Teile-und-Herrsche-Ansatz 0:58:52 SA berechnen 1:00:42 Rekursion 1:03:52 LCP-Array 1:07:13 Datenkompression 1:08:51 Wörterbasierte Textkompression 1:09:59 Lempel-Ziv Kompression 1:11:29 Burrows Wheeler Transformation 1:14:47 Geometrische Algorithmen 1:15:37 Plane-Sweep-Algorithmen 1:18:08 Verallgemeinerung 1:21:33 Mehr Linienschnitt 1:22:51 Kleine einschließende Kugel

Share this episode

Similar Episodes

28: Algorithmen II, Vorlesung, WS 2019/20, 04.02.2020

Feb 5, 2020 ·80m

27: Algorithmen II, Vorlesung, WS 2019/20, 03.02.2020

Feb 3, 2020 ·67m

26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.2020

Feb 3, 2020 ·83m

25: Algorithmen II, Vorlesung, WS 2019/20, 27.01.2020

Jan 27, 2020 ·72m

24: Algorithmen II, Vorlesung, WS 2019/20, 21.01.2020

Jan 23, 2020 ·74m

23: Algorithmen II, Vorlesung, WS 2019/20, 20.01.2020

Jan 21, 2020 ·80m

Similar Podcasts

Programmieren, WS18/19, Vorlesung Karlsruher Institut für Technologie (KIT) – Objekte und Klassen – Typen, Werte und Variablen – Methoden – Kontrollstrukturen – Rekursion – Referenzen, Listen – Vererbung – Ein/-Ausgabe – Exceptions – Programmiermethodik – Implementierung elementarer Algorithmen (z.B. Sortierverfahren) in Java Literaturhinweise: P. Pepper, Programmieren Lernen, Springer, 3. Auflage 2007 Weiterführende Literatur B. Eckels: Thinking in Java. Prentice Hall 2006 J. Bloch: Effective Java, Addison-Wesley 2008Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu Grundbegriffe der Informatik, Vorlesung, WS18/19 Karlsruher Institut für Technologie (KIT) Inhalt der Vorlesung:- Algorithmen informell, Grundlagen des Nachweises ihrer Korrektheit, Berechnungskomplexität, 'schwere' Probleme, O-Notation, Mastertheorem- Alphabete, Wörter, formale Sprachen, endliche Akzeptoren, kontextfreie Grammatiken- induktive/rekursive Definitionen, vollständige und strukturelle Induktion, Hüllenbildung- Relationen und Funktionen- Graphen- Syntax und Semantik für AussagenlogikWeiterführende Literatur- Goos: Vorlesungen über Informatik, Band 1, Springer, 2005- Abeck: Kursbuch Informatik I, Universitätsverlag Karlsruhe, 2005Ziel:Der/die Studierende soll- grundlegende Definitionsmethoden erlernen und in die Lage versetzt werden, entsprechende Definitionen zu lesen und zu verstehen.- den Unterschied zwischen Syntax und Semantik kennen.- die grundlegenden Begriffe aus diskreter Mathematik und Informatik kennen und die Fähigkeit haben, sie im Zusammenhang mit der Beschreibung von Problemen und Beweisen anzuwenden. Vorlesungsaufzeichnung: http://w Endnu en jul med Poul Nesgaard Sidste år skete der det, der bare ikke måtte ske. Poul Nesgaard havde brugt hele december på at lave ét godt juleprogram, der skulle sendes juleaftensdag. Men udsendelsen blev sat for sent på, og alt gik i vasken på grund af en intern fejl. Derfor har DR givet Poul Nesgaard lov til at fortsætte udviklingen for åben mikrofon frem mod juleaften. Poul stoler ikke længere på DR's algoritmer og sætter i stedet i år sin lid til sine to medværter og en ny, intelligent superpult, der måske kan redde julen. NFT Podcast: Ars Cryptotica (Art For Anarchists) John Ikeda-Williams Art For Anarchists, together with producer, John Ikeda-Williams regularly discuss, define and explain art from a historical perspective, art in general, social justice issues & social change, NFT art, NFT platforms. They also interview artists, creators, and other influential people in the industry. “Ars Cryptotica” basically means “I am of the crypto revolution!”Tags include: #nfts #nft #digitalart #art #cryptoart #l #algo #algorithm #cryptopunk #AI #uptickproject #uptick #rarible #artforanarchists #podcast #crypto #blockchain #digitalartist #nonfungibletoken

URL copied to clipboard!