Ziel dieser Veranstaltung ist der Erwerb von grundlegenden Kompetenzen im algorithmischen Denken, insbesondere bezüglich Korrektheit und Laufzeitbetrachtung. Die Teilnehmer lernen wichtige Datenstrukturen und Algorithmen kennen und lernen Laufzeitverhalten und Speicherplatzanforderungen der Algorithmen bestimmen zu können. Es wird außerdem ein Grundstein für die Basisalgorithm von Datenbanken gelegt (z.B. Indexstrukturen).
Stoffplan: Komplexität von Algorithmen, Sortierverfahren, Graphenalgorithmen, Allgemeine Bäume und Binärbäume, Binäre Suchbäume, Mehrwegbäume, B-Baum u. Varianten, Digitale Suchbäume, Hashverfahren (intern, extern, erweiterbar), Graphische Datenstrukturen, Spezielle Themen (Bitmap Index, Indexstrukturen für "broadcast data", etc.).
Hinweis
Diese Grundlagenvorlesung wird von wechselnden Lehrstühlen angeboten. Den aktuellen Veranstalter finden Sie im TUCaN. Diese Seite enthält die Materialien der letzten Veranstaltung von Prof. Buchmann.
Table of Contents
Folien
| Thema | Folien | |
|---|---|---|
| 1 | Einführung/Administrativa | Folien (PDF, 408 KB) |
| 2 | Übersicht: Problemlösen | Folien (PDF, 536 KB) |
| 3 | Analyse | Folien (PDF, 860 KB) |
| 4 | Graphen Definitionen | Folien (PDF, 892 KB) |
| 5 | Graphen Algorithmen | Folien (PDF, 2 MB) |
| 6 | Graphendarstellung | Folien (PDF, 420 KB) |
| 7 | Bäume – Einführung | Folien (PDF, 544 KB) |
| 8 | Binärbäume | Folien (PDF, 704 KB) |
| 9 | Binärsuchbäume | Folien (PDF, 994 KB) |
| 10 | Mehrwegbäume | Folien (PDF, 2 MB) |
| 11 | Sortieren | Folien (PDF, 828 KB) |
| 12 | Hashing | Folien (PDF, 848 KB) |
| 13 | Geometrische Datenstrukturen | Folien (PDF, 1,6 MB) |
Übungsblätter
| Name | Übung | Lösungen Gruppenaufgaben | Lösungen Hausaufgaben | |
|---|---|---|---|---|
| 1 | Giggle | (PDF, 88 KB) | (PDF, 132 KB) | (PDF, 164 KB) |
| 2 | Simiantec | (PDF, 148 KB) | (PDF, 196 KB) | (PDF, 196 KB) |
| 3 | Färbung | (PDF, 460 KB) | (PDF, 520 KB) | (PDF, 1.4 MB) |
| 4 | mq306 | (PDF, 136 KB) | (PDF, 384 KB) | (PDF, 408 KB) |
| 5 | Feldfrau | (PDF, 336 KB) | (PDF, 596 KB) | (PDF, 772 KB) |
| 6 | e-minus | (PDF, 424 KB) | (PDF, 1.5 MB) | (PDF, 1.7 MB) |
| 7 | Bäume | (PDF, 464 KB) | (PDF, 2.7 MB) | (PDF, 2.7 MB) |
| 8 | Mehrwegbäume | (PDF, 128 KB) | (PDF, 156 KB) | (PDF, 188 KB) |
| 9 | Deutsche Tekeloom | (PDF, 128 KB) | (PDF, 676 KB) | (PDF, 788 KB) |
| 10 | Stooges | (PDF, 124 KB) | (PDF, 436 KB) | (PDF, 552 KB) |
| 11 | Heaps / Hash | (PDF, 196 KB) | (PDF, 296 KB) | (PDF, 358 KB) |
| 12 | Hashing | (PDF, 140 KB) | (PDF, 172 KB) | (PDF, 204 KB) |
| 13 | Geometrisches | (PDF, 288 KB) | (PDF, 740 KB) | (PDF, 740 KB) |
Literatur
Wir werden hauptsächlich das Buch "Introduction to Algorithms", 2nd Edition, von Thomas Cormen et al, ISBN 0-262-03293-7 verwenden.
Die wichtigen, relevanten Kapitel sind: 1-4, 6, 7, 10-13, 16.3, 18,
22-26 und Appendix A und B.
Bitte beachten Sie, dass wir diese Liste in der Zukunft anpassen werden.
Zusätzliche Papiere
Die Vorlesung verweist wahlweise auf zusätzliche Papiere:
- Jagan Sankaranarayanam, Hanan Samet. Distance Oracles for Spatial Networks. ICDE 2009, Shanghai, April 2009
- Hanan Samet, Jagan Sankaranarayanan, Houman Alborzi. Scalable Network Distance Browsing in Spatial Databases. SIGMOD 2008, Vancouver June 2008
- Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi. Tree Indexing on Flash Disks. ICDE 2009, March 29 - April 2, 2009, Shanghai, China
- Devesh Agrawal, Deepak Ganesan, Ramesh Sitaraman, Yanlei Diao, and Shashi Singh Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices. VLDB 09, August 24-28, 2009, Lyon, France
Print
Contact
Legal note
Search