Algorithmen und Datenstrukturen
[go to overview]Winter Term 2014 / 2015
Beschreibung
Algorithmen und Datenstrukturen ist eine Pflichtveranstaltung für die BSc-Studiengänge Informatik, CV und IM, den Studiengang BEd Informatik. Die Inhalte sind im Modulhandbuch für Algorithmen und Datenstrukturen (INJE07) beschrieben. Insgesamt wird sich die Vorlesung am folgenden Buch orientieren:
- Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen - Eine Einführung mit Java, 3. Auflage, dpunkt.verlag
Darüber hinaus ist das folgende Buch zu empfehlen:
- Th. H. Cormen, Ch. E. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Verlag
Ankündigungen
Die Prüfungsanmeldung zur Hauptklausur am 4.3 ist nun in KLIPS geöffnet
- Anmeldefrist: 20.1.-25.2.
- Abmeldefrist: spätestens 2.3.
- Klausur: 4.3. 10:00 in D.028 (Dauer: 90 Minuten)
- Für die Teilnahme an der Klausur ist eine Anmeldung in KLIPS verpflichtend!
- Klausureinsicht: 9.3. 14:00-15:00 in Raum B.016
Die Nachklausur findet am 31.3 statt
- Anmeldefrist: 05.3.-27.3.
- Abmeldefrist: spätestens 27.3.
- Klausur: 31.3. 10:00 in D.028 (Dauer: 90 Minuten)
- Für die Teilnahme an der Nachklausur ist eine Anmeldung in KLIPS verpflichtend (auch wenn zuvor die Hauptklausur nicht erfolgreich mitgeschrieben wurde)!
- Klausureinsicht: 2.4. 14:00-15:00 in Raum B.016
Vorlesungsfolien
- Organisatorische Einleitung
- 1. Einleitung
- 2. Theoretische Grundlagen
2.1. Programmierparadigmen
2.2. Laufzeitanalysen
2.3. Entwurfsmuster - 3. Suchen
3.1. Suchen in sortierten Folgen
3.2. Suchen in Texten - 4. Sortieren
4.1. Algorithmen für vergleichsbasiertes Sortieren
4.2. Weitere Sortierprobleme - 5. Dynamische Datenstrukturen
5.1. Binäre Suchbäume
5.2. AVL-Bäume
5.3. 2-3-4-Bäume und Rot-Schwarz-Bäume
5.4. Heaps
5.5. Hashtabellen - 6. Graphen
6.1. Einführung Graphen
6.2. Breitensuche
6.3. Tiefensuche
6.4. Topologisches Sortieren
6.5. Berechnung kürzester Wege
6.6. Berechnung maximaler Flüsse
6.7. Spannbäume - 7. Optimierungsprobleme
7.1. Grundlagen der Optimierung
7.2. Kombinatorische Optimierung
7.3. Lineare Optimierung
7.4. Das Simplex-Verfahren - 8. Zusammenfassung
Alle Folien als einzelnes PDF: AuD1415_komplett.pdf
Übungen
Der Übungsbetrieb beginnt am 30.10. mit einer Besprechung organisationsrelevanter Themen und notwendiger Vorkenntnisse zu Übungen und Vorlesung.
Die Ausgabe eines neuen Aufgabenblatts erfolgt immer montags um 10 Uhr. Dieses muss bis zum darauffolgenden Montag bis 10 Uhr durch Sie bearbeitet werden.
Blatt | Beschreibung | Abgabe bis |
---|---|---|
Übungsblatt 1 | Dateien | Algorithmenentwurf, Funktionale Programmierung | 3. November, 10 Uhr |
Übungsblatt 2 | Logische Programmierung, Imperative Programmierung, Iterative und Rekursive Programme | 10. November, 10 Uhr |
Übungsblatt 3 | Laufzeitanalysen, Greedy-Algorithmen | 17. November, 10 Uhr |
Übungsblatt 4 | Backtracking, Dynamische Programmierung, Suchen | 24. November, 10 Uhr |
Übungsblatt 5 | Suchen, Suchen in Texten | 1. Dezember, 10 Uhr |
Übungsblatt 6 | Sortieren | 8. Dezember, 10 Uhr |
Übungsblatt 7 | Bäume, Traversierung | 15.Dezember, 10 Uhr |
Probeklausur | Probeklausur | keine Abgabe |
Übungsblatt 8 | Bäume, Hashing, Heaps, | 19. Januar, 10 Uhr |
Übungsblatt 9 | Graphen | 26. Januar, 10 Uhr |
Übungsblatt 10 | Kürzeste Wege Algorithmen | 5. Februar, 10 Uhr |
Leistungsnachweis
Für den Leistungsnachweis (8 ECTS-Punkte) ist die Klausurzulassung und das Bestehen der Klausur erforderlich. Die Klausur ist bestanden, wenn mindestens 50% der Aufgabenpunkte erreicht wurden. Dieses Semester werden keine Teilklausuren angeboten, sondern es wird nur eine Hauptklausur und eine Nachklausur geben.
Die Klausur kann nur mitschreiben, wer sich dazu auch fristgerecht angemeldet hat. Die Modalitäten zur Klausuranmeldung werden rechzeitig bekannt gegeben. Wer am Stichtag nicht angemeldet ist, kann nicht teilnehmen. Wer am Stichtag angemeldet ist, MUSS teilnehmen. Abwesenheit bei der Klausur trotz Anmeldung gilt als Fehlversuch.
Die Zulassung zur Klausur muss durch qualifiziertes Bearbeiten der Übungsaufgaben (mind. 60% der Gesamtpunktzahl) und eine aktive Teilnahme erworben werden. Eine aktive Teilnahme wird durch regelmäßige Teilnahme und Vorrechnen von Lösungen bescheinigt.
In früheren Semestern erworbene Klausurzulassungen werden NICHT anerkannt. Ausnahme: Wer aufgrund von Fehlversuchen im WS 2013/14 verpflichtet ist, an der nächsten Klausur zu AuD teilzunehmen, braucht für die Wiederholung (das ist die Hauptklausur dieses Semesters) keine neue Zulassung.
Unabhängig davon empfehlen wir aber dringend die Teilnahme am Vorlesungs- und Übungsbetrieb.
Klausurtermine:
- Hauptklausur 04.03.2015, 10 Uhr
- Nachklausur 31.03.2015, 10 Uhr
Termine
- Übung - Übung zu Algorithmen und Datenstrukturen
Veranstaltungsnummer: 04009
-
Dozent(in) Matthias Thimm
Leon Kastler
Martin LeinbergerTermin(e) - Do 10.00-12.00
F 312, KO Gebäude F - Do 14.00-16.00
G 309, KO Gebäude G - Do 16.00-18.00
F 312, KO Gebäude F - Do 16.00-18.00
A 213, KO Gebäude A
- Do 10.00-12.00
- Vorlesung - Algorithmen und Datenstrukturen
Veranstaltungsnummer: 04009
-
Dozent(in) Matthias Thimm Termin(e) - Mi 10.00-12.00; ab 04.03.15 - 04.03.15
D 028, KO Gebäude D - Di 10.00-12.00; ab 31.03.15 - 31.03.15
D 028, KO Gebäude D - Mo 16.00-18.00
D 028, KO Gebäude D - Di 16.00-18.00
D 028, KO Gebäude D
- Mi 10.00-12.00; ab 04.03.15 - 04.03.15