Grundlagen der Informatik II (Sommersemester 2009)

To english version

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.

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:

Informationen

TUCaN-Link 20-00-0005-iv
CP (SWS) 8 (4+4)
Sprache Deutsch
Prüfung schriftlich

Organizers

Prof. Alejandro Buchmann Dr. Ilia Petrov Wesley Terpstra Pablo Guerrero
A A A | Print | Contact | Legal note | Search