Universität Paderborn - Home Universität Paderborn
Die Universität der Informationsgesellschaft

Datenstrukturen und Algorithmen (MuA)




Aktuell



Modulinformationen

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)


Prüfung

Es werden im Anschluss an die Vorlesung zwei Klausurtermine angeboten.



Termine



Newsgroup

Die Informatik-Rechnerbetreuung (IRB) hat zu der Vorlesung eine Newsgroup für die Studierenden zur Diskussion zur Verfügung gestellt. Die Organisatoren der Veranstaltung haben keinen Einfluss auf Inhalt und Gestaltung dieser Newsgroup. Bei technischen Problemen können wir Ihnen nicht helfen, wenden sie sich bitte an postmaster@upb.de.

Wichtig: Von unserer Seite aus werden niemals offizielle Ankündigungen in dieser Newsgroup veröffentlicht. Alle offiziellen Informationen befinden sich auf dieser Webseite.



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.




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.



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.



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:



Literatur



- Robert Elsässer