Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22

Algorithmen 2, WS2016/17, Vorlesung

תוכן מסופק על ידי Karlsruher Institut für Technologie (KIT). כל תוכן הפודקאסטים כולל פרקים, גרפיקה ותיאורי פודקאסטים מועלים ומסופקים ישירות על ידי Karlsruher Institut für Technologie (KIT) או שותף פלטפורמת הפודקאסט שלהם. אם אתה מאמין שמישהו משתמש ביצירה שלך המוגנת בזכויות יוצרים ללא רשותך, אתה יכול לעקוב אחר התהליך המתואר כאן https://he.player.fm/legal.

8+ y ago 1:17:17

MP4•בית הפרקים

22 | 0:00:00 Starten 0:00:42 13 Onlinealgorithmen 0:05:35 Examples 0:08:09 Competitive analysis 0:09:19 A typical online problem: ski rental 0:11:31 Upper bound for ski rental 0:14:33 Lower bound for ski rental 0:18:07 Paging 0:20:16 Definitions 0:21:49 Paging algorithms 0:25:11 Longest Forward Distance is optimal 0:27:34 Using the claim 0:29:01 Proof the claim 0:29:44 Comparison of algorithms 0:34:33 A general lower bound 0:38:53 Resource augmentation 0:40:14 Conservative algorithms 0:43:26 Competitive ratio 0:46:50 Counting the faults of OPT 0:47:32 Conclusion 0:48:30 Competitive analysis 0:49:57 Notes 0:51:02 New results 0:54:25 Randomized algorithms 0:55:38 Three types of adversaries 1:00:46 Markig Algorithm 1:04:28 Analysis of REMARk 1:06:21 Lower bound for OPT 1:07:42 Discussion 1:08:50 Why competitive analysis? 1:16:24 Disadvantages of competetive analysis

26 פרקים

#Hochschulbildung #Bildung #Vorlesung #Informatik #Strukturen #Daten #Toolbox #Korrektheitsargumente #Effizienzanalyse #Algorithmen #Mathematik #Karlsruher Instituts Für Technologie KIT #Video #KIT