Algorithmen und Datenstrukturen

Grundstudium
SS 2009
Vorlesung: Di, 14-16, Do, 12-14, Prof. Martin Hofmann
Übung: Di, 10-12, 12-14, Fr 10-12, 12-14, 14-16, 16-18, Andreas Abel, Roland Axelsson und Team
Schein: ja
SWS: 3 Vorlesung + 2 Übung
Klausur: 18.7.2009, 13-15, A140, A240, B201, M218 Hauptgebäude

Aktuelles

Termin zur Einsichtnahme in die Klausurkorrektur: Fr. 30.10., 16:00 - 17:00 Uhr in D11 (Oettingenstr., heisst mittlerweile E U 111)
Die Ergebnisse der Nachholklausur stehen zum herunterladen bereit.
Folien zur Vorlesung:
- Kapitel 1 (1-42), letzte Aktualisierung (28.04. 11:33)
- Kapitel 2 (43-87), letzte Aktualisierung (30.04. 15:24)
- Kapitel 3 (88-142), letzte Aktualisierung (13.07. 13:50. Fehler in Punkt 2 auf F105 verbessert.)
- Handgeschriebene Folien zu den Operationen auf RS-Baeumen. (sind in folienK3.pdf bereits als 117a und 120a und eingefuegt.), letzte Aktualisierung (18.05. 14:16)
- Kapitel 4 (143-200), letzte Aktualisierung (07.07. 14:17, Find(a) durch Find(l) ersetzt auf F187, Parameter bei Finde-Damen eingefuegt, F187)
- Kapitel 5 (201-274), letzte Aktualisierung (14.07. 10:02)
Animationen von Algorithmen aus dem WWW

Organisatorisches

Die Vorlesung findet an den folgenden 21 Terminen statt: 21.04., 23.04., 28.04., 30.04., 05.05., 12.05., 14.05., 19.05, 26.05., 28.05., 04.06., 09.06., 16.06., 23.06., 25.06., 30.06., 02.07., 07.07., 09.07., 14.07., 16.07.

	Tag	Zeit	Ort	Beginn	Dozent
Vorlesung	Di	14.15 - 15.45	B 138 (Theresienstr. 39)	21.04.09	Martin Hofmann
	Do	12.15 - 13.45	B 138 (Theresienstr. 39)	23.04.09	Martin Hofmann
Übung	Di	10.15 - 11.45	B 046 (Theresienstr. 39)	28.04.09	Paola Maneggia
	Di	12.15 - 13.45	B 039 (Theresienstr. 39)	28.04.09	Thomas Manhardt
	Fr	10.15 - 11.45	B 039 (Theresienstr. 39)	24.04.09	Andreas Abel/ Roland Axelsson
	Fr	12.15 - 13.45	B 039 (Theresienstr. 39)	24.04.09	Julien Oster
	Fr	14.15 - 15.45	B 039 (Theresienstr. 39)	24.04.09	Bastian Gebhardt
	Fr	16.15 - 17.45	B 039 (Theresienstr. 39)	24.04.09	Sarah Breining
Klausur	18.07.	13.00 - 15.00	A140, A240, B201, M218 (Hauptgebäude)
Nachholklausur	08.10.	11.00 - 13.00	B101, B201, M218 (Hauptgebäude)

Für	Studierende der Informatik im Grundstudium
Vorkenntnisse	Grundkenntnisse in Informatik
Schein	gilt für Diplomvorprüfung im Haupt- oder Nebenfach Informatik und für den Bachelorstudiengang
Scheinerwerb	Weiteres wird noch bekanntgegeben.

Nachholklausur

Die Modulprüfung findet in Form einer ersten Semestralklausur am Ende der Vorlesungszeit (am 18.07.2009) Semesters sowie einer Nachklausur am Ende des Semesters (am 08.10.2009) statt.

Prüfungsstoff

Alles, was in der Vorlesung und in den Übungen behandelt wurde, ist prüfungsrelevant. Das schließt Flüsse in Netzwerken mit ein.

Ablauf

Datum:

Donnerstag, 8. Oktober 2009

Einlass:

10:40 Uhr bis 11:00 Uhr s.t., danach wird niemand mehr in die Prüfungsräume eingelassen.

Prüfungszeit:

11:00 Uhr s.t. bis 13:30 Uhr.

Gebäude:

Hauptgebäude, Geschwister-Scholl-Platz 1, U-Bahn U3/U6 Haltestelle "Universität".

Raum:

Verteilung über die Räume nach Anfangsbuchstaben des Familiennamens, wie er bei der Anmeldung angegeben ist:

A - L	Hörsaal B 201 (2.OG)
M - Z	Hörsaal B 101 (1.OG)

Hinweis:

Listen mit den Hörsaalnummern hängen ab ca. 10:30 Uhr vor den Prüfungsräumen aus. Falls Sie das Gebäude nicht gut kennen, ist es ratsam, einige Tage vorher die genaue Lage Ihres Prüfungsraums zu erkunden. Wenn Sie erst unmittelbar vor der Klausur nach dem Raum suchen, ist die Gefahr groß, dass Sie sich verspäten und nicht mehr mitschreiben können.

Erforderliche Unterlagen

gültiger Immatrikulationsnachweis für dieses Semester
gültiger Personalausweis oder Pass mit Lichtbild
Schreibzeug

Eigenes Papier ist nicht erforderlich und darf für die Prüfung nicht benutzt werden.

Die Klausur findet ohne Hilfsmittel statt. Insbesondere sind keine schriftlichen Unterlagen, keine Taschenrechner oder andere Rechner, keine Mobiltelefone oder andere Kommunikationsmittel erlaubt.

Wenn Sie am Tag der Klausur nicht auf Ihr Handy verzichten können, deponieren Sie es für die Dauer der Prüfung in einem der Schließfächer im Durchgang neben Hörsaal A 140 (1.OG) oder im Durchgang neben Hörsaal A 240 (2.OG). Für diese Schließfächer wird eine 2-Euro-Münze als Pfand benötigt. Auch Taschen lassen Sie besser im Schließfach, aber bitte nicht die Ausweise.

Inhalt

Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das Lehrbuch von Cormen et al. an, das in mehreren Präsenzexemplaren in der Bibliothek vorhanden ist.

Gliederung

Einführung
- Sortieren durch Einfügen
- Sortieren durch Mischen
- O-Notation
- Lösen asymptotischer Rekurrenzen
Sortier- und Suchverfahren
- HeapSort
- QuickSort
- Sortieren in Linearzeit
- Selektion
Datenstrukturen
- Hashtabellen
- Binäre Suchbäume
- Disjunkte Mengen
Entwurfsprinzipien
- Dynamische Programmierung
- Greedy Algorithmen
- Amortisierungs-Analyse
Graphalgorithmen
- Minimale Spannbäume
- Kürzeste Wege
- Flüsse in Netzwerken

Literatur

siehe bitte hier

Andreas Abel

Last modified: Tue Aug 4 15:25:10 CEST 2009