06: Algorithmen I, Vorlesung, SS 2019, 15.05.2019

Autor

Carsten Sinz, Markus Iser

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

06 |
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

Laufzeit (hh:mm:ss)

01:28:19

Serie

Algorithmen I, Vorlesung, SS 2019

Publiziert am

16.05.2019

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz