KIT | KIT-Bibliothek | Impressum | Datenschutz

02: Algorithmen 1, Vorlesung, SS 2017, 26.04.2017, 02

Asfour, Tamim; KIT | Webcast [Hrsg.]

Abstract:
0:00:00 Starten
0:00:07 Erinnerung VL 24.04.2017
0:01:55 Karatsuba-Ofman Multiplikation
0:04:33 Skalierung
0:06:59 Blick über den Tellerrand
0:09:45 Algorithmenanalyse
0:13:07 Zweite Vereinfachung: Asymptotik
0:19:44 O-Kalkül Rechenregeln
0:23:29 Maschinenmodell: RAM
0:31:59 ""Kleine"" ganze Zahlen?
0:35:00 Algorithmenanalyse im RAM-Modell
0:38:15 Mehr Maschinenmodell
0:40:56 Pseudocode
0:41:56 Design by Contract / Schleifeninvarianten
0:56:16 Programmanalyse
1:00:30 Eine Rekurrenz für Teile und Herrsche
1:02:54 Master Theorem (Einfache Form)

Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:

- Ergebnisüberprüfung (Checkers) und Zertifizierung
- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
- Grundbegriffe des Algorithm Engineering
- Effektive Umsetzung verketteter Listen
- Unbeschränkte Arrays, Stapel, und Warteschlangen
- Hashtabellen: mit Verkettung, linear probing, universelles Hashing
- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
- Selektion: quickselect
- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
... mehr

Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 03.05.2017
Erstellungsdatum 26.04.2017
DOI 10.5445/DIVA/2017-195
Identifikator KITopen-ID: 1000114599
Lizenz KITopen-Lizenz
Serie Algorithmen I, Vorlesung, SS 2017
Folge 2
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page