Category:Videos: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(b-tree aktualisiert)
No edit summary
 
(26 intermediate revisions by the same user not shown)
Line 10: Line 10:
! Release
! Release
|-
|-
| Algorithmus von Kruskal
| [[Algorithmus von Kruskal]]
| https://youtu.be/Pz6x3BB86YA
| https://youtu.be/Pz6x3BB86YA
| Pz6x3BB86YA
| Pz6x3BB86YA
Line 27: Line 27:
| SoSe 2013
| SoSe 2013
|-
|-
| Algorithmus von Prim
| [[Algorithmus von Prim]]
| https://youtu.be/tGsKpnBBM2U
| https://youtu.be/tGsKpnBBM2U
| tGsKpnBBM2U
| tGsKpnBBM2U
Line 36: Line 36:
#[https://youtu.be/tGsKpnBBM2U?t=11m14s Das sieht doch aus wie der Algorithmus von Dijkstra?]
#[https://youtu.be/tGsKpnBBM2U?t=11m14s Das sieht doch aus wie der Algorithmus von Dijkstra?]
#[https://youtu.be/tGsKpnBBM2U?t=12m07s Wie lautet die Invariante?]
#[https://youtu.be/tGsKpnBBM2U?t=12m07s Wie lautet die Invariante?]
#[https://youtu.be/tGsKpnBBM2U?t=12m40s Warum ist der Algorithmus korrekt ?]
#[https://youtu.be/tGsKpnBBM2U?t=12m40s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/tGsKpnBBM2U?t=13m00s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/tGsKpnBBM2U?t=13m00s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/tGsKpnBBM2U?t=13m47s Was ist die asymptotische Komplexität des Algorithhmus?]
#[https://youtu.be/tGsKpnBBM2U?t=13m47s Was ist die asymptotische Komplexität des Algorithhmus?]
Line 44: Line 44:
| SoSe 2013
| SoSe 2013
|-
|-
| Union Find
| [[Union Find]]
| https://youtu.be/wE8Y8TU-iUI
| https://youtu.be/wE8Y8TU-iUI
| wE8Y8TU-iUI
| wE8Y8TU-iUI
Line 56: Line 56:
| SoSe 2013
| SoSe 2013
|-
|-
| Algorithmus von Dijkstra
| [[Algorithmus von Dijkstra]]
| https://youtu.be/6nSc8ojXZ1A
| https://youtu.be/6nSc8ojXZ1A
| 6nSc8ojXZ1A
| 6nSc8ojXZ1A
Line 77: Line 77:
| SoSe 2013
| SoSe 2013
|-
|-
| All Pairs Shortest Paths
| [[All Pairs Shortest Paths]]
| https://youtu.be/3_zqU5GWo4w
| https://youtu.be/3_zqU5GWo4w
| 3_zqU5GWo4w
| 3_zqU5GWo4w
Line 101: Line 101:
| SoSe 2013
| SoSe 2013
|-
|-
| String matching based on finite automaton
| [[String matching based on finite automaton]]
| https://youtu.be/fu5ovC9R8r0
| https://youtu.be/fu5ovC9R8r0
| fu5ovC9R8r0
| fu5ovC9R8r0
|  
| TODO
| Sascha Weiß
| Sascha Weiß
| Rolf Egert
| Rolf Egert
Line 110: Line 110:
| SoSe 2013
| SoSe 2013
|-
|-
| B-Trees
| [[B-Trees]]
| https://youtu.be/vbRZ8h6ROYc
| https://youtu.be/vbRZ8h6ROYc
| vbRZ8h6ROYc
| vbRZ8h6ROYc
Line 137: Line 137:
| SoSe 2013
| SoSe 2013
|-
|-
| HashTable
| [[HashTable]]
| https://youtu.be/AzrnDztV63U
| https://youtu.be/AzrnDztV63U
| AzrnDztV63U
| AzrnDztV63U
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/AzrnDztV63U?t=00m00s Einführung]
#[https://youtu.be/AzrnDztV63U?t=00m04s Beispiel]
#[https://youtu.be/AzrnDztV63U?t=05m12s Welche abstrakte Datenstruktur wird implementiert?]
#[https://youtu.be/AzrnDztV63U?t=07m31s Wie kann man sie in Java implementieren?]
#[https://youtu.be/AzrnDztV63U?t=10m26s Wie sehen denn diese ominösen Hashfunktionen aus?]
#[https://youtu.be/AzrnDztV63U?t=11m52s Wie kommt man von einem Index zum nächsten?]
#[https://youtu.be/AzrnDztV63U?t=14m11s Was lässt sich über die asymptotische Komplexität aussagen?]
#[https://youtu.be/AzrnDztV63U?t=19m01s Was ist eine Bounded Map?]
#[https://youtu.be/AzrnDztV63U?t=19m21s Und was ist eine Hashtabelle?]
#[https://youtu.be/AzrnDztV63U?t=19m50s Was gibt es über Hashfunktionen zu sagen?]
#[https://youtu.be/AzrnDztV63U?t=20m25s Wie ist das mit dem Probing?]
#[https://youtu.be/AzrnDztV63U?t=21m17s Schließlich die asymptotische Komplexität?]
| Sascha Weiß
| Sebastian Bechtel
| 21:47
| 21:47
| SoSe 2013
| SoSe 2013
|-
|-
| Sortierproblem
| [[Sortierproblem]]
| https://youtu.be/so2Kqzq9tvc
| https://youtu.be/so2Kqzq9tvc
| so2Kqzq9tvc
| so2Kqzq9tvc
| row 1, cell 3
| TODO
| row 1, cell 3
| N/A
| Rolf Egert
| 2:23
| 2:23
| SoSe 2013
| SoSe 2012
|-
|-
| Simple String Matching
| [[Simple String Matching]]
| https://youtu.be/5p4fZGRaYuo
| https://youtu.be/5p4fZGRaYuo
| 5p4fZGRaYuo
| 5p4fZGRaYuo
| row 1, cell 3
| TODO
| row 1, cell 3
| Sascha Weiß
| Rolf Egert
| 4:38
| 4:38
| SoSe 2013
| SoSe 2013
|-
|-
| Merge Sort
| [[Merge Sort]]
| https://youtu.be/7kdQwh-WvhA
| https://youtu.be/7kdQwh-WvhA
| 7kdQwh-WvhA
| 7kdQwh-WvhA
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/7kdQwh-WvhA?t=00m00s Mergesort]
#[https://youtu.be/7kdQwh-WvhA?t=02m36s Fragen]
#[https://youtu.be/7kdQwh-WvhA?t=02m44s Wie funktioniert der Algorithmus?]
#[https://youtu.be/7kdQwh-WvhA?t=03m04s Was ist die asymptotische Komplexität des Algorithmus?]
#[https://youtu.be/7kdQwh-WvhA?t=03m23s Was macht Merge?]
#[https://youtu.be/7kdQwh-WvhA?t=03m34s Wie lautet die Invariante?]
#[https://youtu.be/7kdQwh-WvhA?t=03m58s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/7kdQwh-WvhA?t=04m10s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/7kdQwh-WvhA?t=04m31s Was ist die asymptotische Komplexität des Algorithmus?]
| Sascha Weiß
| Rolf Egert
| 4:44
| 4:44
| SoSe 2013
| SoSe 2013
|-
|-
| Selection Sort
| [[Selection Sort]]
| https://youtu.be/SyDboKHspv0
| https://youtu.be/SyDboKHspv0
| SyDboKHspv0
| SyDboKHspv0
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/SyDboKHspv0?t=00m00s Selection Sort]
#[https://youtu.be/SyDboKHspv0?t=02m55s Fragen]
#[https://youtu.be/SyDboKHspv0?t=02m57s Wie lautet die Invariante?]
#[https://youtu.be/SyDboKHspv0?t=03m12s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/SyDboKHspv0?t=03m23s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/SyDboKHspv0?t=03m40s Was ist die asymptotische Komplexität des Algorithmus?]
| Sascha Weiß
| Rolf Egert
| 4:19
| 4:19
| SoSe 2013
| SoSe 2013
|-
|-
| Quick Sort
| [[Quick Sort]]
| https://youtu.be/It9ccZB9BqM
| https://youtu.be/It9ccZB9BqM
| It9ccZB9BqM
| It9ccZB9BqM
| row 1, cell 3
|
| row 1, cell 3
#[https://youtu.be/It9ccZB9BqM?t=00m00s Quicksort]
#[https://youtu.be/It9ccZB9BqM?t=02m54s Fragen]
#[https://youtu.be/It9ccZB9BqM?t=02m55s Wie funktioniert der Algorithmus?]
#[https://youtu.be/It9ccZB9BqM?t=03m21s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/It9ccZB9BqM?t=03m43s Was ist die asymptotische Komplexität des Algorithmus?]
| Sascha Weiß
| Rolf Egert
| 4:19
| 4:19
| SoSe 2013
| SoSe 2013
|-
|-
| Quick Sort in place
| [[Quick Sort in-place]]
| https://youtu.be/9b_B17MXRG0
| https://youtu.be/9b_B17MXRG0
| 9b_B17MXRG0
| 9b_B17MXRG0
| row 1, cell 3
| TODO
| row 1, cell 3
| Sascha Weiß
| Rolf Egert
| 7:23
| 7:23
| SoSe 2013
| SoSe 2013
|-
|-
| Algorithmische Problemstellungen und Algorithmen ganz allgemein
| [[Algorithmische Problemstellungen und Algorithmen ganz allgemein]]
| https://youtu.be/NwWZmsCV5Ec
| https://youtu.be/NwWZmsCV5Ec
| NwWZmsCV5Ec
| NwWZmsCV5Ec
| row 1, cell 3
| TODO
| row 1, cell 3
| Sascha Weiß
|
| 6:04
| 6:04
| SoSe 2013
| SoSe 2013
|-
|-
| Asymptotische Komplexität
| [[Asymptotische Komplexität]]
| https://youtu.be/dpgkYeSXSPI
| https://youtu.be/dpgkYeSXSPI
| dpgkYeSXSPI
| dpgkYeSXSPI
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/dpgkYeSXSPI?t=00m00s Einführung]
#[https://youtu.be/dpgkYeSXSPI?t=00m01s Worum geht es überhaupt bei der asymptotischen Komplexität?]
#[https://youtu.be/dpgkYeSXSPI?t=00m40s Was heißt dabei mathematische Abstraktion?]
#[https://youtu.be/dpgkYeSXSPI?t=02m07s Jetzt aber ein Beispiel]
#[https://youtu.be/dpgkYeSXSPI?t=06m12s Ein Beispiel aus der Vorlesung]
#[https://youtu.be/dpgkYeSXSPI?t=07m21s Vielleicht noch ein weiteres Beispiel aus der Vorlesung?]
#[https://youtu.be/dpgkYeSXSPI?t=09m07s Der andere String Matching Algorithmus?]
#[https://youtu.be/dpgkYeSXSPI?t=09m55s Was wissen wir nach den Beispielen?]
#[https://youtu.be/dpgkYeSXSPI?t=11m41s Da gibt es aber noch das Laufzeitsystem?]
#[https://youtu.be/dpgkYeSXSPI?t=12m41s Vorab eine eigene Speicherverwaltung selbst einrichten?]
#[https://youtu.be/dpgkYeSXSPI?t=14m42s Asymptotischer Vergleich mathematischer Funktionen]
#[https://youtu.be/dpgkYeSXSPI?t=19m04s Mathematische Regeln und die wichtigsten Funktionen]
#[https://youtu.be/dpgkYeSXSPI?t=22m50s Die O-Notation]
#[https://youtu.be/dpgkYeSXSPI?t=24m51s Warum betrachten wir eigentlich Funktionen mit reellen Argumenten und Werten, wenn die Parameter zur Beschreibung der Datenmenge und die resultierende Anzahl Taktzyklen doch ganzzahlig sind?]
#[https://youtu.be/dpgkYeSXSPI?t=25m20s Zusammenfassung spezielle Funktionen]
| Sascha Weiß
|
| 26:11
| 26:11
| SoSe 2013
| SoSe 2013
|-
|-
| Doubly Linked List
| [[Doubly Linked List]]
| https://youtu.be/6Fm2zJBXc0A
| https://youtu.be/6Fm2zJBXc0A
| 6Fm2zJBXc0A
| 6Fm2zJBXc0A
| row 1, cell 3
| TODO
| row 1, cell 3
| Sascha Weiß
|
| 1:29
| 1:29
| SoSe 2013
| SoSe 2013
|-
|-
| ArrayList
| [[ArrayList]]
| https://youtu.be/uYTck0kDvl4
| https://youtu.be/uYTck0kDvl4
| uYTck0kDvl4
| uYTck0kDvl4
| TODO
| TODO
| row 1, cell 3
| Sascha Weiß
|
| 2:13
| 2:13
| SoSe 2013
| SoSe 2013
|-
|-
| Bubble Sort
| [[Bubble Sort]]
| https://youtu.be/gTCYd7rmbIc
| https://youtu.be/gTCYd7rmbIc
| gTCYd7rmbIc
| gTCYd7rmbIc
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/gTCYd7rmbIc?t=00m00s Bubblesort]
#[https://youtu.be/gTCYd7rmbIc?t=02m17s Fragen]
#[https://youtu.be/gTCYd7rmbIc?t=02m18s Wie lautet die Invariante?]
#[https://youtu.be/gTCYd7rmbIc?t=02m33s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/gTCYd7rmbIc?t=02m46s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/gTCYd7rmbIc?t=03m03s Was ist die asymptotische Komplexität des Algorithmus?]
#[https://youtu.be/gTCYd7rmbIc?t=03m23s Wie funktioniert dieses Bubbling?]
| Sascha Weiß
| Rolf Egert
| 3:48
| 3:48
| SoSe 2013
| SoSe 2013
|-
|-
| Referenzsemantik
| [[Referenzsemantik]]
| https://youtu.be/nhaj-OYlfjo
| https://youtu.be/nhaj-OYlfjo
| nhaj-OYlfjo
| nhaj-OYlfjo
| row 1, cell 3
| TODO
| row 1, cell 3
| Sascha Weiß
|
| 2:37
| 2:37
| SoSe 2013
| SoSe 2013
|-
|-
| Heaps
| [[Heaps]]
| https://youtu.be/j-r4YOPFp7E
| https://youtu.be/j-r4YOPFp7E
| j-r4YOPFp7E
| j-r4YOPFp7E
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/j-r4YOPFp7E?t=00m00s Einführung]
#[https://youtu.be/j-r4YOPFp7E?t=00m06s Bounded Priority Queue]
#[https://youtu.be/j-r4YOPFp7E?t=01m54s Wie sehen Heaps nun aus?]
#[https://youtu.be/j-r4YOPFp7E?t=06m01s Wie fügt man einen neuen Key mit Methode insert in einen Heap ein?]
#[https://youtu.be/j-r4YOPFp7E?t=07m44s Das hört doch nicht immer erst an der Wurzel auf, oder?]
#[https://youtu.be/j-r4YOPFp7E?t=08m33s Wie löscht man den kleinsten Key mit Methode extract min?]
#[https://youtu.be/j-r4YOPFp7E?t=10m15s Das hört doch nicht immer erst an einem Blatt auf, oder?]
#[https://youtu.be/j-r4YOPFp7E?t=11m08s Und wie reduziert man nun einen Key mit Methode decrease key?]
#[https://youtu.be/j-r4YOPFp7E?t=12m45s Das hört doch nicht immer an der Wurzel auf, oder?]
#[https://youtu.be/j-r4YOPFp7E?t=13m34s Was ist noch einmal ein Heap abstrakt gesehen?]
#[https://youtu.be/j-r4YOPFp7E?t=13m54s Wie wird eine Bounded Priority Queue als Heap implementiert?]
#[https://youtu.be/j-r4YOPFp7E?t=14m53s Wie war das noch mit dem Array Positions?]
#[https://youtu.be/j-r4YOPFp7E?t=15m40s Wie war das noch mit den IDs?]
#[https://youtu.be/j-r4YOPFp7E?t=16m39s Und wie war das zu guter Letzt mit der Verwaltung freier IDs?]
#[https://youtu.be/j-r4YOPFp7E?t=17m23s Wie fügt man einen neuen Key mit Methode insert in einen Heap ein?]
#[https://youtu.be/j-r4YOPFp7E?t=18m34s Wie löscht man den kleinesn key mit Methode extract min?]
#[https://youtu.be/j-r4YOPFp7E?t=19m42s Und wie reduziert man nun einen Key mit Methode decrease key?]
| Sascha Weiß
| Rolf Egert
| 12:26
| 12:26
| SoSe 2013
| SoSe 2013
|-
|-
| Linked List
| [[Linked List]]
| https://youtu.be/O9PquupPZCs
| https://youtu.be/O9PquupPZCs
| O9PquupPZCs
| O9PquupPZCs
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/O9PquupPZCs?t=00m00s Linked List]
#[https://youtu.be/O9PquupPZCs?t=07m56s Fragen]
#[https://youtu.be/O9PquupPZCs?t=07m58s Was ist allgemein eine Linked List?]
#[https://youtu.be/O9PquupPZCs?t=08m24s Wie war das noch mit der Suche?]
#[https://youtu.be/O9PquupPZCs?t=09m05s Wie war das mit dem Einfügen?]
#[https://youtu.be/O9PquupPZCs?t=09m55s Wie war das mit dem Löschen?]
#[https://youtu.be/O9PquupPZCs?t=11m06s Was sind verzeigerte Strukturen?]
#[https://youtu.be/O9PquupPZCs?t=11m37s Was ist der Sinn von verzeigerten Strukturen?]
| Sascha Weiß
|
| 7:20
| 7:20
| SoSe 2013
| SoSe 2013
|-
|-
| Binary Search Tree
| [[Binary Search Tree]]
| https://youtu.be/AdhRIRgVZVw
| https://youtu.be/AdhRIRgVZVw
| AdhRIRgVZVw
| AdhRIRgVZVw
| row 1, cell 3
|
| row 1, cell 3
#[https://youtu.be/AdhRIRgVZVw?t=00m00s Binärer Suchbaum]
#[https://youtu.be/AdhRIRgVZVw?t=00m02s Erfolgreiche Suche]
#[https://youtu.be/AdhRIRgVZVw?t=01m20s Nicht-Erfolgreiche Suche]
#[https://youtu.be/AdhRIRgVZVw?t=02m20s Einfügen]
#[https://youtu.be/AdhRIRgVZVw?t=03m17s Löschen]
| Sascha Weiß
| Rolf Egert
| 6:22
| 6:22
| SoSe 2013
| SoSe 2013
|-
|-
| Binary Search Tree Travesieren
| [[Binary Search Tree Travesieren]]
| https://youtu.be/PXqM9q57BMk
| https://youtu.be/PXqM9q57BMk
| PXqM9q57BMk
| PXqM9q57BMk
| row 1, cell 3
|  
| row 1, cell 3
#[https://youtu.be/PXqM9q57BMk?t=00m00s Binärer Suchbaum Travesieren]
#[https://youtu.be/PXqM9q57BMk?t=05m04s Fragen]
#[https://youtu.be/PXqM9q57BMk?t=05m06s Wie lautet die Invariante?]
#[https://youtu.be/PXqM9q57BMk?t=05m40s Warum ist der Algorithmus korrekt?]
#[https://youtu.be/PXqM9q57BMk?t=05m53s Wie wird die Invariante sichergestellt?]
#[https://youtu.be/PXqM9q57BMk?t=06m37s Wie lautet die Variante?]
#[https://youtu.be/PXqM9q57BMk?t=06m51s Was ist die asymptotische Komplexität des Algorithmus?]
| Sascha Weiß
| Rolf Egert
| 7:20
| 7:20
| SoSe 2013
| SoSe 2013
|-
|-
| Generics und Collections
| [[Generics und Collections]]
| https://youtu.be/ZCREPAE-DVw
| https://youtu.be/ZCREPAE-DVw
| ZCREPAE-DVw
| ZCREPAE-DVw
|  
| #
| Thomas Lüdecke
| [[Thomas Lüdecke]]
| 37:54
| 37:54
| WiSe 2014/2015
| WiSe 2014/2015
|-
|-
| Bucket Sort
| [[Bucket Sort]]
| https://youtu.be/-POIDU_ew98
| https://youtu.be/-POIDU_ew98
| -POIDU_ew98
| -POIDU_ew98
| row 1, cell 3
| #
| row 1, cell 3
| #
| 7:36
| 7:36
| SoSe 2013
| SoSe 2013
|-
|-
| Decision Tree
| [[Decision Tree]]
| https://youtu.be/b9HTcSf7JbQ
| https://youtu.be/b9HTcSf7JbQ
| b9HTcSf7JbQ
| b9HTcSf7JbQ
| row 1, cell 3
| #
| row 1, cell 3
| #
| 9:07
| 9:07
| SoSe 2013
| SoSe 2013
|-
|-
| Komplexität algorithmischer Probleme
| [[Komplexität algorithmischer Probleme]]
|  
| https://youtu.be/fvtGtFALvcs
|  
| fvtGtFALvcs
|
| Thomas Lüdecke
|  
|  
#[https://youtu.be/fvtGtFALvcs?t=00m08s Asymptotische Komplexität ...]
#[https://youtu.be/fvtGtFALvcs?t=00m36s Untere Schranken Sortieren ...]
#[https://youtu.be/fvtGtFALvcs?t=01m44s Für untere Schranken reicht, ...]
#[https://youtu.be/fvtGtFALvcs?t=03m26s Entscheidungsbaum Mergesort n größer 4]
#[https://youtu.be/fvtGtFALvcs?t=05m07s Permutation identifizieren]
#[https://youtu.be/fvtGtFALvcs?t=06m33s Mathematische Analyse]
#[https://youtu.be/fvtGtFALvcs?t=08m01s Wirklich schwere Probleme]
#[https://youtu.be/fvtGtFALvcs?t=08m20s Handlungsreisendenproblem (TSP)]
#[https://youtu.be/fvtGtFALvcs?t=08m39s Rucksackproblem]
#[https://youtu.be/fvtGtFALvcs?t=09m45s Steinerbaumproblem]
#[https://youtu.be/fvtGtFALvcs?t=10m35s Mengenpackung/-überdeckung]
#[https://youtu.be/fvtGtFALvcs?t=11m36s Clique / Unabhängige Menge]
#[https://youtu.be/fvtGtFALvcs?t=12m06s Maximale Clique]
#[https://youtu.be/fvtGtFALvcs?t=12m31s Was heißt schwer?]
#[https://youtu.be/fvtGtFALvcs?t=13m20s Ansatz der Theorie]
#[https://youtu.be/fvtGtFALvcs?t=14m15s Was ist polynomielle Laufzeit?]
#[https://youtu.be/fvtGtFALvcs?t=15m40s Arten von Problemen]
#[https://youtu.be/fvtGtFALvcs?t=17m39s Entscheidungsproblem abgeleitet]
#[https://youtu.be/fvtGtFALvcs?t=19m39s Zertifikate]
#[https://youtu.be/fvtGtFALvcs?t=22m40s Zertifikate beim TSP]
#[https://youtu.be/fvtGtFALvcs?t=24m07s Problemklassen P und NP]
#[https://youtu.be/fvtGtFALvcs?t=25m41s Reduktion von Problemen]
#[https://youtu.be/fvtGtFALvcs?t=26m57s Reduktion auf kürzestes Pfade]
#[https://youtu.be/fvtGtFALvcs?t=28m5s Reduktion von Problemen Fazit]
#[https://youtu.be/fvtGtFALvcs?t=29m53s Polynomielle Reduktion]
#[https://youtu.be/fvtGtFALvcs?t=30m30s Die Klasse NPC]
#[https://youtu.be/fvtGtFALvcs?t=31m50s Circuit-SAT ist in NPC]
#[https://youtu.be/fvtGtFALvcs?t=33m14s Beweisskizze Circuit-SAT ist in NPC]
#[https://youtu.be/fvtGtFALvcs?t=38m17s Auch SAT ist in NPC]
#[https://youtu.be/fvtGtFALvcs?t=39m13s Beweisskizze SAT in NPC]
#[https://youtu.be/fvtGtFALvcs?t=39m56s Auch 3-CNF ist in NPC]
#[https://youtu.be/fvtGtFALvcs?t=40m42s Beweis 3-CNF in NPC]
#[https://youtu.be/fvtGtFALvcs?t=42m26s Auch CLIQUE ist in NPC]
#[https://youtu.be/fvtGtFALvcs?t=43m32s Beweisskizze MAX-CLIQUE in NPC]
#[https://youtu.be/fvtGtFALvcs?t=46m30s Grundprinzip der Argumentation]
| [[Thomas Lüdecke]]
|  
|  
| 48:07
| SoSe 2015
| SoSe 2015
|-
|-
| Algorithmische Konzepte
| [[Algorithmische Konzepte]]
|  
| https://youtu.be/4vvHneNV2VQ
|  
| 4vvHneNV2VQ
|
| Thomas Lüdecke
|  
|  
#[https://youtu.be/4vvHneNV2VQ?t=00m08s Schwere algorithmische Probleme]
#[https://youtu.be/4vvHneNV2VQ?t=02m30s Vorab Datenmenge reduzieren]
#[https://youtu.be/4vvHneNV2VQ?t=05m45s Kritische Punkte vorab]
#[https://youtu.be/4vvHneNV2VQ?t=08m56s Lösung zuerst grob bestimmen]
#[https://youtu.be/4vvHneNV2VQ?t=10m58s Divide and Conquer]
#[https://youtu.be/4vvHneNV2VQ?t=13m10s Dynamische Programmierung]
#[https://youtu.be/4vvHneNV2VQ?t=14m31s Fibonacci-Zahlen]
#[https://youtu.be/4vvHneNV2VQ?t=14m45s Binomialkoeffizienten]
#[https://youtu.be/4vvHneNV2VQ?t=16m36s Greedy-Ansatz]
#[https://youtu.be/4vvHneNV2VQ?t=25m38s Greedy verallgemeinert]
#[https://youtu.be/4vvHneNV2VQ?t=26m26s Backtracking]
#[https://youtu.be/4vvHneNV2VQ?t=28m28s Lokale Suche: Beispiel TSP]
#[https://youtu.be/4vvHneNV2VQ?t=31m00s Lokale Suche: Beispiel Rucksackproblem]
#[https://youtu.be/4vvHneNV2VQ?t=32m34s Generische lokale Suche]
#[https://youtu.be/4vvHneNV2VQ?t=34m02s Wiederholte lokale Suche]
#[https://youtu.be/4vvHneNV2VQ?t=36m03s Spezielles Datenprofil ausnutzen]
#[https://youtu.be/4vvHneNV2VQ?t=36m31s Granularität: Rucksackproblem]
#[https://youtu.be/4vvHneNV2VQ?t=37m34s Beispiel Rucksackproblem]
#[https://youtu.be/4vvHneNV2VQ?t=41m11s Spezielle Strukturen]
#[https://youtu.be/4vvHneNV2VQ?t=44m26s Zusätzliche Informationen]
| [[Thomas Lüdecke]]
|  
|  
| 47:53
| SoSe 2015
| SoSe 2015
|}
|-}

Latest revision as of 13:06, 28 July 2015

Title URL ID Chapters Cut Colaborators Duration Release
Algorithmus von Kruskal https://youtu.be/Pz6x3BB86YA Pz6x3BB86YA
  1. Einführung
  2. Der Algorithmus von Kruskal anhand eines Beispiels
  3. Und wie ist das bei mehreren Zusammenhangskomponenten?
  4. Welches Problem löst der Algorithmus von Kruskal genau?
  5. Wie lautet die Invariante?
  6. Warum ist der Algorithmus korrekt?
  7. Wie wird die Invariante sichergestellt?
  8. Was ist die asymptotische Komplexität des Algorithmus?
 Sascha Weiß Rolf Egert 11:00 SoSe 2013
Algorithmus von Prim https://youtu.be/tGsKpnBBM2U tGsKpnBBM2U
  1. Einführung
  2. Der Algorithmus von Prim anhand eines Beispiels
  3. Korrektheitsbeweis für den Algorithmus von Prim
  4. Das sieht doch aus wie der Algorithmus von Dijkstra?
  5. Wie lautet die Invariante?
  6. Warum ist der Algorithmus korrekt?
  7. Wie wird die Invariante sichergestellt?
  8. Was ist die asymptotische Komplexität des Algorithhmus?
 Sascha Weiß Rolf Egert 14:32 SoSe 2013
Union Find https://youtu.be/wE8Y8TU-iUI wE8Y8TU-iUI
  1. Einführung
  2. Wie funktioniert Union-Find nochmal?
  3. Und wie war das noch mit der asymptotischen Komplexität?
 Sascha Weiß Rolf Egert 7:49 SoSe 2013
Algorithmus von Dijkstra https://youtu.be/6nSc8ojXZ1A 6nSc8ojXZ1A
  1. Einführung
  2. Ändern sich die Pfade stark in jeder Iteration?
  3. Auf was für Strukturen arbeiten wir eigentlich?
  4. Distanzen und kürzeste Pfade
  5. Varianten des Kürzeste-Pfade-Problems
  6. Dijkstra implementiert
  7. Wieso funktioniert dieser Algorithmus, warum ist er korrekt?
  8. Was gibt es zum Preprocessing bzw. Induktionsanfang zu sagen?
  9. Was ist in der Queue?
  10. Was wissen wir über die erledigten Knoten?
  11. Und was wissen wir über die unerledigten Knoten?
  12. Und was ist mit der asymptotischen Komplexität?
 Sascha Weiß Stephan Wahl 24:36 SoSe 2013
All Pairs Shortest Paths https://youtu.be/3_zqU5GWo4w 3_zqU5GWo4w
  1. Einführung
  2. Einführendes Beispiel
  3. Wie sieht das für ein einzelnes Knotenpaar aus?
  4. Können wir noch ein Knotenpaar sehen?
  5. Was ist mit negativen Zyklen?
  6. Beschleunigung: Repeated Squaring
  7. Floyd-Warshal
  8. Wie lautet die Invariante? (Bellman-Ford)
  9. Warum ist der Algorithmus korrekt? (Bellman-Ford)
  10. Wie wird die Invariante sichergestellt? (Bellman-Ford)
  11. Was ist die asymptotische Komplexität des Algorithmus? (Bellman-Ford)
  12. Was war das noch? (Repeated Squaring)
  13. Wie lautet die Invariante? (Floyd-Warshal)
  14. Wie wird die Invariante sichergestellt? (Floyd-Warshal)
  15. Was ist die asymptotische Komplexität des Algorithmus? (Floyd-Warshal)
 Sascha Weiß Rolf Egert 21:35 SoSe 2013
String matching based on finite automaton https://youtu.be/fu5ovC9R8r0 fu5ovC9R8r0 TODO Sascha Weiß Rolf Egert 5:59 SoSe 2013
B-Trees https://youtu.be/vbRZ8h6ROYc vbRZ8h6ROYc
  1. Einführung
  2. Vielwegbäume und Vielwegsuchbäume
  3. B-Bäume
  4. Finden eines Schlüsselwertes
  5. Einfügen eines neuen Schlüsselwertes
  6. Einfügen mit Split-Operation
  7. Einfügen mit Split-Operation an der Wurzel
  8. Nochmal das Gleiche mit mehr Knoten im Baum
  9. Löschen aus einem B-Baum
  10. Löschen aus einem inneren Knoten
  11. Löschen mit Merge-Operation
  12. Löschen mit Rotate-Operation
  13. Beispiel mit einer Rotate- und einer Merge-Operation
  14. Merge-Operation an der Wurzel
  15. Was sind Vielwegbäume und Vielwegsuchbäume?
  16. Was sind B-Bäume?
  17. Was ist die Invariante beim Einfügen?
  18. Und was ist die Invariante beim Löschen?
 Sascha Weiß Rolf Egert 20:02 SoSe 2013
HashTable https://youtu.be/AzrnDztV63U AzrnDztV63U
  1. Einführung
  2. Beispiel
  3. Welche abstrakte Datenstruktur wird implementiert?
  4. Wie kann man sie in Java implementieren?
  5. Wie sehen denn diese ominösen Hashfunktionen aus?
  6. Wie kommt man von einem Index zum nächsten?
  7. Was lässt sich über die asymptotische Komplexität aussagen?
  8. Was ist eine Bounded Map?
  9. Und was ist eine Hashtabelle?
  10. Was gibt es über Hashfunktionen zu sagen?
  11. Wie ist das mit dem Probing?
  12. Schließlich die asymptotische Komplexität?
 Sascha Weiß Sebastian Bechtel 21:47 SoSe 2013
Sortierproblem https://youtu.be/so2Kqzq9tvc so2Kqzq9tvc TODO N/A Rolf Egert 2:23 SoSe 2012
Simple String Matching https://youtu.be/5p4fZGRaYuo 5p4fZGRaYuo TODO Sascha Weiß Rolf Egert 4:38 SoSe 2013
Merge Sort https://youtu.be/7kdQwh-WvhA 7kdQwh-WvhA
  1. Mergesort
  2. Fragen
  3. Wie funktioniert der Algorithmus?
  4. Was ist die asymptotische Komplexität des Algorithmus?
  5. Was macht Merge?
  6. Wie lautet die Invariante?
  7. Warum ist der Algorithmus korrekt?
  8. Wie wird die Invariante sichergestellt?
  9. Was ist die asymptotische Komplexität des Algorithmus?
 Sascha Weiß Rolf Egert 4:44 SoSe 2013
Selection Sort https://youtu.be/SyDboKHspv0 SyDboKHspv0
  1. Selection Sort
  2. Fragen
  3. Wie lautet die Invariante?
  4. Warum ist der Algorithmus korrekt?
  5. Wie wird die Invariante sichergestellt?
  6. Was ist die asymptotische Komplexität des Algorithmus?
 Sascha Weiß Rolf Egert 4:19 SoSe 2013
Quick Sort https://youtu.be/It9ccZB9BqM It9ccZB9BqM
  1. Quicksort
  2. Fragen
  3. Wie funktioniert der Algorithmus?
  4. Warum ist der Algorithmus korrekt?
  5. Was ist die asymptotische Komplexität des Algorithmus?
 Sascha Weiß Rolf Egert 4:19 SoSe 2013
Quick Sort in-place https://youtu.be/9b_B17MXRG0 9b_B17MXRG0 TODO Sascha Weiß Rolf Egert 7:23 SoSe 2013
Algorithmische Problemstellungen und Algorithmen ganz allgemein https://youtu.be/NwWZmsCV5Ec NwWZmsCV5Ec TODO Sascha Weiß 6:04 SoSe 2013
Asymptotische Komplexität https://youtu.be/dpgkYeSXSPI dpgkYeSXSPI
  1. Einführung
  2. Worum geht es überhaupt bei der asymptotischen Komplexität?
  3. Was heißt dabei mathematische Abstraktion?
  4. Jetzt aber ein Beispiel
  5. Ein Beispiel aus der Vorlesung
  6. Vielleicht noch ein weiteres Beispiel aus der Vorlesung?
  7. Der andere String Matching Algorithmus?
  8. Was wissen wir nach den Beispielen?
  9. Da gibt es aber noch das Laufzeitsystem?
  10. Vorab eine eigene Speicherverwaltung selbst einrichten?
  11. Asymptotischer Vergleich mathematischer Funktionen
  12. Mathematische Regeln und die wichtigsten Funktionen
  13. Die O-Notation
  14. Warum betrachten wir eigentlich Funktionen mit reellen Argumenten und Werten, wenn die Parameter zur Beschreibung der Datenmenge und die resultierende Anzahl Taktzyklen doch ganzzahlig sind?
  15. Zusammenfassung spezielle Funktionen
 Sascha Weiß 26:11 SoSe 2013
Doubly Linked List https://youtu.be/6Fm2zJBXc0A 6Fm2zJBXc0A TODO Sascha Weiß 1:29 SoSe 2013
ArrayList https://youtu.be/uYTck0kDvl4 uYTck0kDvl4 TODO Sascha Weiß 2:13 SoSe 2013
Bubble Sort https://youtu.be/gTCYd7rmbIc gTCYd7rmbIc
  1. Bubblesort
  2. Fragen
  3. Wie lautet die Invariante?
  4. Warum ist der Algorithmus korrekt?
  5. Wie wird die Invariante sichergestellt?
  6. Was ist die asymptotische Komplexität des Algorithmus?
  7. Wie funktioniert dieses Bubbling?
 Sascha Weiß Rolf Egert 3:48 SoSe 2013
Referenzsemantik https://youtu.be/nhaj-OYlfjo nhaj-OYlfjo TODO Sascha Weiß 2:37 SoSe 2013
Heaps https://youtu.be/j-r4YOPFp7E j-r4YOPFp7E
  1. Einführung
  2. Bounded Priority Queue
  3. Wie sehen Heaps nun aus?
  4. Wie fügt man einen neuen Key mit Methode insert in einen Heap ein?
  5. Das hört doch nicht immer erst an der Wurzel auf, oder?
  6. Wie löscht man den kleinsten Key mit Methode extract min?
  7. Das hört doch nicht immer erst an einem Blatt auf, oder?
  8. Und wie reduziert man nun einen Key mit Methode decrease key?
  9. Das hört doch nicht immer an der Wurzel auf, oder?
  10. Was ist noch einmal ein Heap abstrakt gesehen?
  11. Wie wird eine Bounded Priority Queue als Heap implementiert?
  12. Wie war das noch mit dem Array Positions?
  13. Wie war das noch mit den IDs?
  14. Und wie war das zu guter Letzt mit der Verwaltung freier IDs?
  15. Wie fügt man einen neuen Key mit Methode insert in einen Heap ein?
  16. Wie löscht man den kleinesn key mit Methode extract min?
  17. Und wie reduziert man nun einen Key mit Methode decrease key?
 Sascha Weiß Rolf Egert 12:26 SoSe 2013
Linked List https://youtu.be/O9PquupPZCs O9PquupPZCs
  1. Linked List
  2. Fragen
  3. Was ist allgemein eine Linked List?
  4. Wie war das noch mit der Suche?
  5. Wie war das mit dem Einfügen?
  6. Wie war das mit dem Löschen?
  7. Was sind verzeigerte Strukturen?
  8. Was ist der Sinn von verzeigerten Strukturen?
 Sascha Weiß 7:20 SoSe 2013
Binary Search Tree https://youtu.be/AdhRIRgVZVw AdhRIRgVZVw
  1. Binärer Suchbaum
  2. Erfolgreiche Suche
  3. Nicht-Erfolgreiche Suche
  4. Einfügen
  5. Löschen
 Sascha Weiß Rolf Egert 6:22 SoSe 2013
Binary Search Tree Travesieren https://youtu.be/PXqM9q57BMk PXqM9q57BMk
  1. Binärer Suchbaum Travesieren
  2. Fragen
  3. Wie lautet die Invariante?
  4. Warum ist der Algorithmus korrekt?
  5. Wie wird die Invariante sichergestellt?
  6. Wie lautet die Variante?
  7. Was ist die asymptotische Komplexität des Algorithmus?
 Sascha Weiß Rolf Egert 7:20 SoSe 2013
Generics und Collections https://youtu.be/ZCREPAE-DVw ZCREPAE-DVw # Thomas Lüdecke 37:54 WiSe 2014/2015
Bucket Sort https://youtu.be/-POIDU_ew98 -POIDU_ew98 # # 7:36 SoSe 2013
Decision Tree https://youtu.be/b9HTcSf7JbQ b9HTcSf7JbQ # # 9:07 SoSe 2013
Komplexität algorithmischer Probleme https://youtu.be/fvtGtFALvcs fvtGtFALvcs
  1. Asymptotische Komplexität ...
  2. Untere Schranken Sortieren ...
  3. Für untere Schranken reicht, ...
  4. Entscheidungsbaum Mergesort n größer 4
  5. Permutation identifizieren
  6. Mathematische Analyse
  7. Wirklich schwere Probleme
  8. Handlungsreisendenproblem (TSP)
  9. Rucksackproblem
  10. Steinerbaumproblem
  11. Mengenpackung/-überdeckung
  12. Clique / Unabhängige Menge
  13. Maximale Clique
  14. Was heißt schwer?
  15. Ansatz der Theorie
  16. Was ist polynomielle Laufzeit?
  17. Arten von Problemen
  18. Entscheidungsproblem abgeleitet
  19. Zertifikate
  20. Zertifikate beim TSP
  21. Problemklassen P und NP
  22. Reduktion von Problemen
  23. Reduktion auf kürzestes Pfade
  24. Reduktion von Problemen Fazit
  25. Polynomielle Reduktion
  26. Die Klasse NPC
  27. Circuit-SAT ist in NPC
  28. Beweisskizze Circuit-SAT ist in NPC
  29. Auch SAT ist in NPC
  30. Beweisskizze SAT in NPC
  31. Auch 3-CNF ist in NPC
  32. Beweis 3-CNF in NPC
  33. Auch CLIQUE ist in NPC
  34. Beweisskizze MAX-CLIQUE in NPC
  35. Grundprinzip der Argumentation
 Thomas Lüdecke 48:07 SoSe 2015
Algorithmische Konzepte https://youtu.be/4vvHneNV2VQ 4vvHneNV2VQ
  1. Schwere algorithmische Probleme
  2. Vorab Datenmenge reduzieren
  3. Kritische Punkte vorab
  4. Lösung zuerst grob bestimmen
  5. Divide and Conquer
  6. Dynamische Programmierung
  7. Fibonacci-Zahlen
  8. Binomialkoeffizienten
  9. Greedy-Ansatz
  10. Greedy verallgemeinert
  11. Backtracking
  12. Lokale Suche: Beispiel TSP
  13. Lokale Suche: Beispiel Rucksackproblem
  14. Generische lokale Suche
  15. Wiederholte lokale Suche
  16. Spezielles Datenprofil ausnutzen
  17. Granularität: Rucksackproblem
  18. Beispiel Rucksackproblem
  19. Spezielle Strukturen
  20. Zusätzliche Informationen
 Thomas Lüdecke 47:53 SoSe 2015
Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Category:Videos&oldid=3496"