Datenstrukturen und Algorithmen (MuA)

Aktuell

• Die zweite Klausur wurde nun korrigiert!
  • Bewertung
  • Die aufgeführten Noten werden noch nicht ans Prüfungssekretariat übermittelt. Sollten Sie jedoch jene akzeptieren, so können Sie um eine zeitnahe Weiterleitung ans Prüfungssekretariat bitten. Schicken Sie dazu bitte eine Benachrichtigung an florida@upb.de mit allen notwendigen Daten. Eine nachträgliche Änderung der Note ist dann nicht mehr möglich!
  • Bei Problemen mit den zuständigen Prüfungssekretariaten oder eventueller Umschreibung wenden Sie sich bitte an den Dekan.
  • Die Klausureinsicht findet voraussichtlich am Montag den 16 November ab 18Uhr im Raum F2.211 statt.
  • Aufgrund von Abwesenheit werden bislang nicht eingetragene Bitten um Eintragung in Kürze bearbeitet. Sobald dies geschieht werden die jeweiligen Personen entsprechend benachrichtigt.
  • Mündliche Prüfungen können nach vorheriger Vereinbarung (ausschließlich am Freitag) stattfinden. Hierzu ist eine rechtzeitige Terminabsprache mit Prof. Elsässer und eine Anmeldung beim jeweiligen Prüfungssekretariat notwendig.

Modulinformationen

• Modul I.2.2: Datenstrukturen und Algorithmen
• V4 + Ü2 + ZÜ1 SWS (Kontaktzeit)
• 8 ECTS-Credits (Workload)

Für weiterführende Informationen siehe auch den Eintrag im Modulhandbuch.

Inhaltsangabe

Algorithmen bilden die Grundlage jeder Hardware und Software: Ein Schaltkreis setzt einen Algorithmus in Hardware um, ein Programm macht einen Algorithmus "für den Rechner verstehbar". Algorithmen spielen daher eine zentrale Rolle in der Informatik. Wesentliches Ziel des Algorithmenentwurfs ist die (Ressourcen-) Effizienz, d.h. die Entwicklung von Algorithmen, die ein gegebenes Problem möglichst schnell oder mit möglichst geringem Speicherbedarf lösen.

Untrennbar verbunden mit effizienten Algorithmen sind effiziente Datenstrukturen, also Methoden, große Datenmengen im Rechner so zu organisieren, dass Anfragen wie Suchen, Einfügen und Löschen aber auch komplexere Anfragen effizient beantwortet werden können.

Die in dieser Veranstaltung vorgestellten Entwurfs- und Analysemethoden für effiziente Algorithmen und Datenstrukturen, sowie die grundlegenden Beispiele wie Sortierverfahren, dynamische Suchstrukturen und Graphenalgorithmen gehören zu den Grundlagen für Algorithmenentwicklung und Programmierung in weiten Bereichen der Informatik.

Inhaltliche Gliederung:

1. Einführung (Rechenmodelle, Effizienzmaße, Beispiele)
2. Analysetechniken (Invarianten, Rekurrenzgleichungen)
3. Sortieralgorithmen (Insertion-Sort, Merge-Sort, Quick-Sort, Heap-Sort, Counting-Sort)
4. Datenstrukturen (Verkette Listen, Bäume, Graphen, Dynamische Suchstrukturen, Suchbäume, Balancierung von Suchbäumen, Hashing)
5. Graphenalgorithmen (Tiefen- und Breitensuche, Kürzeste Wege, Minimale Spannbäume)
6. Entwurfsparadigmen (Inkrementelle Entwicklung, Teile-und-Herrsche, Greedy Algorithmen, Dynamische Programmierung)

Kontakt

Bei Fragen und Problemen wenden Sie sich bitte an Robert Elsässer oder Adrian Ogierman.

Prüfung

Es werden im Anschluss an die Vorlesung zwei Klausurtermine angeboten.

   Klausur 1

   Klausur 2

Termine

• Vorlesung:

Tag	Zeit	Raum	Dozent
Montag	11:00-13:00	Audimax	Robert Elsässer
Freitag	11:00-13:00	G	Robert Elsässer

• Zentralübung:

Gruppe	Tag	Zeit	Raum	Tutor
Zentralübung	Do	13:00-14:00	G	Robert Elsässer

• Übungsgruppen:

Sie müssen sich über Ihren StudInfo_{flex}-Zugang zu den Übungen anmelden.

Gruppe	Tag	Zeit	Raum	Tutor
Übungsgruppe 1	Mo	07:00-09:00	E2.310	Hendrik Renken
Übungsgruppe 2	Mo	14:00-16:00	E2.316	Michael Knopf
Übungsgruppe 3	Mo	14:00-16:00	D1.312	Yuhan Yan
Übungsgruppe 4	Mo	16:00-18:00	E2.316	Michael Knopf
Übungsgruppe 5	Mo	16:00-18:00	E2.310	Fritz Blumentritt
Übungsgruppe 6	Di	09:00-11:00	D1.303	Tobias Wybranietz
Übungsgruppe 7	Di	09:00-11:00	E2.310	Adrian Ogierman
Übungsgruppe 8	Di	16:00-18:00	N3.206	Florentin Neumann
Übungsgruppe 9	Di	16:00-18:00	E2.310	Sebastian Abshoff
Übungsgruppe 10	Mi	07:00-09:00	E2.310	Thim Strothmann
Übungsgruppe 11	Mi	14:00-16:00	H3	Markus Benter
Übungsgruppe 12	Do	09:00-11:00	E2.316	Timo Klerx
Übungsgruppe 13	Do	16:00-18:00	D1.312	Ralf Dreesen
Übungsgruppe 14	Fr	14:00-16:00	E2.310	Sascha Brandt

  

Skript

Die Vorlesung orientiert sich in Notation und Aufbau an dem Grundlagenbuch "Introduction to Algorithms" von Cormen, Leiserson, Rivest und Stein (2. Auflage).

Zur Nacharbeit und Vertiefung wird die unten angegebene Literatur empfohlen.

Folien

Hier erscheint im Laufe des Semesters die Folien-Präsentation der einzelnen Vorlesungen. Bitte beachten Sie, dass diese nur zur Unterstützung der Vorlesung gedacht sind und keinen selbsterklärenden Charakter besitzen. Ein alleiniges Lernen an Hand dieser Folien kann den Besuch der Vorlesung und die Lektüre der angegebenen Literatur nicht ersetzen und wird im Allgemeinen zum Bestehen der Prüfung nicht ausreichen.

Die Literaturangaben [CLRS 2nd] beziehen sich immer auf Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 2. Auflage. Jedoch verfügen auch die anderen Grundlagenbücher i.d.R. über Abschnitte zu den behandelten Inhalten.

Vorlesung	Folien (als PDF)	Literatur
17.04.2009	Einleitung, Pseudocode, Invarianten, Laufzeitanalyse, Groß-O-Notation	[CLRS 2nd]: Seite 3-22, 41-50, 184-185
20.04.2009	Inkrementelle Algorithmen, Insertion-Sort, Divide & Conquer Algorithmen, Merge-Sort	[CLRS 2nd]: Seite 15-18, 23-25 [CLRS 2nd]: Seite 28-36
24.04.2009	Average-Case Analyse, Elementare Wahrscheinlichkeitstheorie	[CLRS 2nd]: Seite 1100-1109
27.04.2009	Quick-Sort, Master Theorem	[CLRS 2nd]: Seite 145-158, 62-74
04.05.2009	Quick-Sort, Master Theorem	[CLRS 2nd]: Seite 145-158, 62-74
08.05.2009	Heaps, Heap-Sort	[CLRS 2nd]: Seite 127-138
11.05.2009	Heaps, Heap-Sort	[CLRS 2nd]: Seite 127-138
15.05.2009	Untere Schranke für Vergleichssortierer, Counting-Sort	[CLRS 2nd]: Seite 165-170
18.05.2009	Korrektheit von Counting Sort, ADTs und Datenstrukturen	[CLRS 2nd]: Seite 165-170
22.05.2009	Stacks, Queues, Listen, Bäume, Binäre Suchbäume	[CLRS 2nd]: Seite 197-209, 214-216, 253-264
25.05.2009	AVL-Bäume	[Ottmann, Widmeyer]: Seite 260-272
29.05.2009	Hashtabellen	[CLRS 2nd]: Seite 221-232, 237-245
05.06.2009	Hashtabellen	[CLRS 2nd]: Seite 221-232, 237-245
08.06.2009	Elementare Graphalgorithmen, Breitensuche	[CLRS 2nd]: Seite 525-538
12.06.2009	Tiefensuche	[CLRS 2nd]: Seite 540-549
15.06.2009	Kürzeste Wege, Algorithmus von Dijkstra	[CLRS 2nd]: Seite 549-551, 580-583
19.06.2009	Transitive Hülle, Minimale Spannbäume	[CLRS 2nd]: Seite 632-633, 561-563
22.06.2009	Algorithmus von Prim und Kruskal, Disjunkte Vereinigungsmengen	[CLRS 2nd]: Seite 563-573, 498-503
26.06.2009	Union-Find, All Pairs Shortest Path	[CLRS 2nd]: Seite 503-504, 620-621, 629-630
29.06.2009	All Pairs Shortest Path, Divide and Conquer, Matrix Multiplikation	[CLRS 2nd]: Seite 630-632, 735
03.07.2009	Gierige Algorithmen, Schedulingprobleme	[CLRS 2nd]: Seite 735-741
06.07.2009	Gierige Algorithmen, Intevall Scheduling, Datenkompression	[CLRS 2nd]: Seite 735-741 [Kleinberg, Tardos]: Seite 115-121
13.07.2009	Gierige Algorithmen, Schedulingprobleme, Datenkompression	[Kleinberg, Tardos]: Seite 115-121
17.07.2009	Datenkompression	[CLRS 2nd]: Seite 385-391
20.07.2009	Dynamische Programmierung	[CLRS 2nd]: Seite: 323-324, 350-355 [Kleinberg, Tardos]: Seite: 266-272
24.07.2009	Zusammenfassung und Wiederholung

Aufgaben

Hier erscheinen im Laufe des Semesters die Übungen zur Vertiefung des Lehrstoffes. Im Rahmen der Zentralübung werden jede Woche die meisten Aufgaben besprochen. Die Kästen für die Abgaben befinden sich auf D3.

Übung (als PDF)	Ausgewählte Musterlösungen (als PDF)
1. Übung	Musterlösung
2. Übung	Musterlösung
3. Übung	Musterlösung
4. Übung	Musterlösung
5. Übung	Musterlösung
6. Übung (7tes Blatt)	Musterlösung
7. Übung (8tes Blatt)	Musterlösung
8. Übung (10tes Blatt)	Java-Framework | Musterlösung (Source)
9. Übung (11tes Blatt)	Musterlösung
10. Übung (13tes Blatt)	Musterlösung
Probeklausur	Musterlösung

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (2-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben. Übungszettel, bei welchen jedoch mehr als 4 Personen angegeben sind, werden mit 0 Punkten gewertet.

Wichtig: An dieser Stelle wird darauf hingewiesen, dass bei den Aufgaben, Lösungen und Korrekturen keine Garantie für Vollständigkeit oder Fehlerfreiheit übernommen wird! Wir sind jedoch bemüht den Fehlergrad in einem geringen Rahmen zu halten.

Bonuspunkte

Durch aktive Mitarbeit in den Übungen haben Sie die Möglichkeit, ihre in der abschließenden Prüfung erreichte Note wie folgt zu verbessern:

• Erreichen Sie mindestens 50% der Punkte der Übungsaufgaben, so verbessert sich die Note der Prüfung um 1/3 (ein Notenschritt).
• Erreichen Sie mindestens 75% der Punkte der Übungsaufgaben, so verbessert sich die Note der Prüfung um 2/3 (zwei Notenschritte).
• Erreichen Sie mindestens 90% der Punkte der Übungsaufgaben, so verbessert sich die Note der Prüfung um 3/3 (drei Notenschritte).
• Eine Verbesserung über die Note 1,0 (sehr gut) hinaus ist nicht möglich.
• WICHTIG: Eine Verbesserung der Prüfungsnote 5,0 (nicht bestanden) ist nicht möglich.

Literatur

• Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms",
  MIT Press / McGraw-Hill, 2nd ed., ISBN: 0-262-53196-8
• Cormen, Leiserson, Rivest: "Algorithmen - Eine Einführung",
  Oldenburg, ISBN: 3-486-27515-1
• Kleinberg, Tardos: "Algorithm Design"
  Addison-Wesley, ISBN: 0-321-29535-8
• Sedgewick: "Algorithms in Java (parts 1-4)",
  Addison-Wesley, ISBN: 0-201-36120-5
• Ottmann, Widmeyer: "Algorithmen und Datenstrukturen",
  Spektrum Akademischer Verlag, ISBN: 3-321-29535-8