Sommersemester 2009
PD Dr. Michael Brinkmeier

[Mitteilungen] [Inhalte] [Termine] [Prüfung] [Literatur] [Materialien]

Mitteilungen

• Die Mitschriften der Mittwoch 11:00 Uhr Übung werden in Zukunft online gestellt.
  Für den Zugriff benötigt man einen Nutzernamen und ein Passwort.
  Hinweise für beide finden sie weiter unten (oder sie können sie in den Übungen und Vorlesungen erfahren).
  
  
• Die Ergebnisse der beiden Bonusklausuren können der untenstehenden Tabelle entnommen werden. Die Tabelle ist auch als PDF erhältlich.
  
  

  Matrikel	Bonus 1	Bonus 2	Summe		Matrikel	Bonus 1	Bonus 2	Summe
  29277	8	11	19		42437	3		3
  31148	5		5		42461	3		3
  32638		5	5		42464		7	7
  34729	3		3		42672	3		3
  34851	5		5		43143	2		2
  34891	9	5	14		43293	3	10	13
  36558	6	9	15		43330	6	14	20
  38244	8	9	17		43343	4	6	10
  39211	7	4	11		43344	11	14	25
  39278	2	5	7		43350		4	4
  39468		1	1		43351	11	8	19
  39555	6		6		43358	14	12	26
  39797	1		1		43374	12	10	22
  40787	4	6	10		43395	5	5	10
  40895	7	13	20		43516	5	1	6
  41021	6		6		43549	9		9
  41022	6		6		43552	6	10	16
  41927	4	7	11		43586	5		5
  41953	3	2	5		43603	10	7	17
  41959	10	8	18		43617	6	12	18
  41981		9	9		43631	1	11	12
  41982	4		4		43647	10	8	18
  41991	8	4	12		43649	8	11	19
  42030	2	5	7		43650	9	7	16
  42103	5		5		43815	9		9
  42137	5	7	12		43952	10	6	16
  42171		9	9		43957	3	3	6
  42214	5	6	11		43974	12	14	26
  42221					44002	5	5	10
  42236	5	12	17		44009	10	14	24
  42244	5	3	8		44012	5	8	13
  42262	3	9	12		44039	4	3	7
  42267	7	11	18		44086	6	15	21
  42276	10	11	21		44130	6	9	15
  42312	8	9	17		44306	7	13	20
  42336	7	7	14		44307	10	12	22
  42415	5		5		44329	5	9	14
  42434	5		5		44519	2	1	3

  
  

Inhalte

In der Vorlesung werden grundlegende Prinzipien für den Entwurf und die Analyse von Algorithmen und Datenstrukturen besprochen. Dazu gehören insbesondere die Analyse der Laufzeit und der Korrektheit des Ergebnisses. Die vorgestellten Techniken werden an konkreten Algorithmen aus verschiedenen Bereichen erläutert.

Übersicht über die geplanten Themen

• Grundlegende Techniken (z.B. Iteration und Rekursion)
• Analyse von Algorithmen (z.B. Korrektheit, Laufzeitverhalten sowie asymptotische Notationen)
  
• Grundlegende Datentypen und Datenstrukturen (Stacks, Queues, Listen, Binärbäume,...), einschließlich Implementierung und Analyse
• Balancierte Suchbäume und einfache Hashverfahren
• Sortierverfahren (Insertion-Sort, Mergesort, Heapsort, Bubblesort, Quicksort, Bucketsort, Radixsort)
• Grundbegriffe der Graphentheorie sowie grundlegende Algorithmen für Graphen:
• Breiten- und Tiefensuche
• Zusammenhangskomponenten
• Minimale Spannbäume
• Detektion von Kreisen
• Algorithmenparadigmen:
• Greedy
• Divide-and-Conquer
• Dynamische Programmierung
• Backtracking
• Branch-and-Bound
• Priority Queues (Vorrangswarteschlangen)

Termine

Prüfung

Am Ende des Semesters muß eine 90 minütige Prüfungsklausur bestanden werden.

 Zusätzlich finden im Laufe des Semesters zwei 15 minütige Kurzklausuren statt. Die erste in der Vorlesung am 12. Mai und die zweite am 23. Juni. Die in diesen Klausuren gesammelten Punkte werden zu einem Bonus für die abschließende Prüfungsklausur verrechnet. Die Gesamtpunktzahl P für die Prüfung ergibt sich nach folgender Formel:

P = n + 0,1 N (n1+n2)/(N1+N2)

n: In der Prüfungsklausur erreichte Punktzahl
N: Maximaplunktzahl der Prüfungsklausr
n1,n2: In der ersten/zweiten Kurzklausur erreichte Punkte
N1,N2: Maximalpunktzahl in der ersten/zweiten Kurzklausur

D.h. der Bonus kann im Maximum 10% der in der Prüfungsklausur erreichbaren Punkte sein.

Das Übungsprogramm ist obligatorisch. Es wird jede Woche Übungszettel geben, die in den Übungen besprochen werden.

Literatur und Links

Begleitend zur Vorlesung empfehlen wir die folgenden Bücher und Skripte:

• Dietzfelbinger, Algorithmen und Datenstrukturen, Skript, TU Ilmenau, 2005
  
  
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2nd Edition; MIT Press, 2001
• Ottmann und Widmayer, Algorithmen und Datenstrukturen; Spektrum Akad. Verlag, 1998
• Robert Sedgewick, Algorithmen; Addison-Wesley, 2002
• Uwe Schöning, Algorithmik; Spektrum Akad. Verlag, 2001
• Kurt Mehlhorn, Datenstrukturen und effiziente Algorithmen, Band 1 Sortieren und Suchen; EATCS Monographs on Theor. Comp. Sci., 1984 (englische Version)
• Jon Kleinberg, Eva Tardos, Algorithm Design; Addison Wesley, 2005
• Volker Heun, Grundlegende Algorithmen; Vieweg, 2003

Die Bücher befinden sich teilweise in größerer Zahl in der Bibliothek und können dort entliehen werden.

Links

• Die Homepage der Vorlesung im Sommersemester 2008
  
  
• Das Wörterbuch der Algorithmen und Datenstrukturen des NIST (National Institute of standards and Technology

Materialien und Übungsblätter