KIT | KIT-Bibliothek | Impressum | Datenschutz

06: Algorithmen I, Vorlesung, SS 2019, 15.05.2019

Sinz, Carsten; Iser, Markus

  • 0:00:00 Start
  • 0:00:09 Rückblick Vorlesung 13.05
  • 0:02:26 Folgen als Felder und Listen
  • 0:05:06 Folgen
  • 0:05:09 Ausblick: Komplexität typischer Operationen
  • 0:05:39 Verkettete Listen
  • 0:05:54 Listenglieder (Items)
  • 0:09:22 Trick: Dummy Header
  • 0:10:49 Die Listenklasse
  • 0:16:07 Splice-Operation
  • 0:24:24 Splice: Beispiel
  • 0:25:31 Weitere Operationen: Einfach mit splice
  • 0:27:52 Doch nicht so einfach? Speicherverwaltung!
  • 0:31:14 Items löschen
  • 0:32:49 Elemente einfügen
  • 0:35:47 Ganze Listen manipulieren
  • 0:39:54 Suchen
  • 0:40:33 Ganze Listen manipulieren
  • 0:42:55 Suchen
  • 0:47:19 Funktionalität vs. Effizienz
  • 0:51:24 Einfach verkettete Listen
  • 0:52:44 Einfach verkettete Listen: Invariante?
  • 0:53:59 Einfach verkettete Listen: splice
  • 0:56:55 Einfach verkettete Listen: pushBack
  • 0:59:23 Listen: Zusammenfassung
  • 1:01:50 Felder (Arrays)
  • 1:04:33 Unbeschränkte Felder
  • 1:08:02 Unbeschränkte Felder: Grundidee
  • 1:11:33 Unbeschränkte Felder mit teilweise ungenutztem Speicher
  • 1:15:42 Unbeschränkte Felder: Vergrößern
  • 1:20:08 Unbeschränkte Felder: Verkleinern
  • 1:20:59 Amortisierte Komplexität für unbeschränkte Felder
  • 1:23:40 Beweis: Account-Methode (Konto-Methode)
  • 1:27:57 Amortisierte Analyse: verallgemeinert
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 16.05.2019
Erstellungsdatum 15.05.2019
Sprache Deutsch
DOI 10.5445/DIVA/2019-370
Identifikator KITopen-ID: 1000116548
Lizenz KITopen-Lizenz
Serie Algorithmen I, Vorlesung, SS 2019
Folge 6
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page