KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithmen I, SS 2015, gehalten am 27.04.2015, Vorlesung 05

Hofheinz. Dennis

  • 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
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 01.12.2015
Erstellungsdatum 27.04.2015
DOI 10.5445/DIVA/2015-894
Identifikator KITopen-ID: 1000113534
Serie Algorithmen 1, Vorlesung und Übung, SS 2015
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page