05: Effiziente Datenstrukturen: Arrays, unbeschränkte Felder & Hashing erklärt 📊

00:00:07 Felder (Arrays) 00:00:51 Unbeschränkte Felder – Anwendungen 00:01:01 Unbeschränkte Felder – Grundidee 00:01:36 Unbeschränkte Felder mit teilweise ungenutztem Speicher 00:02:34 Kürzen 00:03:22 Amortisierte Komplexität unbeschr. Felder 00:04:52 Beweis: Konto-Methode (oder Versicherung) 00:08:57 Amortisierte Analyse – allgemeiner 00:13:47 Amortisierte Analyse – Diskussion 00:17:39 Stapel und Schlangen 00:21:18 Stapel – Implementierungsvarianten 00:25:35 Stapel – Anwendungen 00:27:25 Warteschlangen / First-In-First-Out / FIFO 00:28:39 Stapel – Implementierungsvarianten 00:38:38 Warteschlangen – Anwendungen 00:40:17 Deque – Double-Ended Queues 00:40:53 Stapel und Schlangen 00:41:57 Deque – Anwendungen 00:43:34 Vergleich: Listen – Felder 00:47:19 Ausblick: Weitere Repräsentationen von Folgen 00:48:17 Hashing (Streuspeicherung) 00:49:50 Hashtabellen 00:52:57 Exkurs: Konventionen für Elemente 00:53:55 Hashing: Anwendungen 00:59:27 Überblick 00:59:27 Erste Ideen zu Implementierungen 01:01:19 Ein (über)optimistischer Ansatz 01:04:55 Kollisionen 01:07:17 Kollisionsauflösung 01:08:08 Hashing mit verketteten Listen 01:10:40 Beispiel 01:13:33 Analyse Jun.-Prof. Dennis Hofheinz, Christoph Striecks | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | https://crypto.iti.kit.edu/index.php?id=algo-sose15 Vorlesungsaufzeichnung: KIT | WEBCAST http://webcast.kit.edu