Datenstrukturen und Algorithmen

Dozent: Prof. Dr. Christian Scheideler

Modulinformation

  • Modul I.2.2 (MuA)
  • V4+ZÜ1+Ü2+P2 SWS
  • 9 ECTS

Vorlesung

  • Montags 11.15 Uhr - 12.45 Uhr, L1
  • Freitags, 11.15 Uhr - 12.45 Uhr, L2

Vorlesungsaufzeichnungen werden über PANDA zur Verfügung gestellt. Weiterhin gibt es in PANDA ein Forum, in dem die Teilnehmer sich zu jedem Zeitpunkt austauschen können. Die erste Vorlesung findet am Montag, den 8. April statt.

Zentralübung

  • Freitags, 13.00 Uhr - 13.45 Uhr, L2

Die erste Zentralübung findet am Freitag, den 26. April statt.

Programmierpraktikum

Das Programmierpraktikum ist nur relevant, wenn Sie in PAUL in Ihrem Modul "Data Structures and Algorithms" den Eintrag "Praktikum: Datenstrukturen und Algorithmen" sehen und das Praktikum noch nicht in früheren Semestern bestanden haben. Beachten Sie, dass das Programmierpraktikum eine eigene Prüfung in PAUL hat (= qualifizierte Teilnahme), die Sie explizit in der Prüfungsanmeldung in PAUL anmelden müssen.

Informationen zum Programmierpraktikum werden Sie in PANDA finden. Weiterhin besteht am Freitag, dem 12. April von 13:00 - 13:45 Uhr im Rahmen der Zentralübung die Möglichkeit, mit dem Leiter des Programmierpraktikums, Rainer Feldmann, zu sprechen.

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

  1. Mo. 09-11 Uhr: Dominik Fockel
  2. Mo. 09-11 Uhr: Lea Hamelmann
  3. Di. 09-11 Uhr: Adrian Kumbrink
  4. Di. 09-11 Uhr: Milo Sendzik
  5. Mi. 09-11 Uhr: Dominik Fockel
  6. Mi. 09-11 Uhr: Moritz Manegold
  7. Mi. 14-16 Uhr: Milo Sendzik
  8. Mi. 14-16 Uhr: Philipp Dresselmann
  9. Mi. 16-18 Uhr: Julian Werthmann
  10. Do. 09-11 Uhr: Marlena Müller
  11. Do. 14-16 Uhr: David Liedtke
  12. Do. 16-18 Uhr: Philipp Dresselmann
  13. Fr. 09-11 Uhr: Marcus Baurichter
  14. Fr. 14-16 Uhr: Dominik Fockel

Der Übungsbeginn ist Montag, der 15. April.

Die Veranstaltung wird über die PANDA-Plattform organisiert. Dort finden sich sämtliche Informationen und Materialien sowie alle Details zum Übungsbetrieb.

Außerdem wird es dort einen allgemeines Forum und ein Forum für jede Übungsgruppe geben.

Inhalt der Vorlesung:

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 und mit möglichst geringem Speicherplatz 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 beantworten werden können.

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

Inhaltliche Gliederung:

  1. Einführung (Rechenmodelle, Effizienzmaße, Beispiele)
  2. Analysetechniken (Invarianten, Rekurrenzgleichungen)
  3. Sortierverfahren (Insertionsort, Mergesort, Quicksort, Heapsort, Countingsort)
  4. Datenstrukturen (Verkettete Listen, Bäume, Graphen, dynamische Suchstrukturen, Hashing)
  5. Graphenalgorithmen (Tiefen- und Breitensuche, kürzeste Wege, minimale Spannbäume)
  6. Entwurfsparadigmen (inkrementelle Entwicklung, Teile-und-Herrsche, Greedy Algorithmen, dynamische Programmierung)

Folien (siehe auch PANDA):

  • Kapitel 1: Einleitung
  • Kapitel 2: Grundlagen
  • Kapitel 3: Inkrementelle Algorithmen
  • Kapitel 4: Divide & Conquer - Merge-Sort
  • Kapitel 5: Rekursionen
  • Kapitel 6: Quicksort
  • Kapitel 7: Heapsort
  • Kapitel 8: Untere Schranken für Sortieren
  • Kapitel 9: Sortieren in linearer Zeit
  • Kapitel 10: Elementare Datenstrukturen
  • Kapitel 11: Binäre Suchbäume
  • Kapitel 12: Balancierte binäre Suchbäume
  • Kapitel 13: Hashing
  • Kapitel 14: Elementare Graphalgorithmen
  • Kapitel 15: Kürzeste Wege
  • Kapitel 16: Minimale Spannbäume
  • Kapitel 17: All Pairs Shortest Path Problem
  • Kapitel 18: Divide & Conquer
  • Kapitel 19: Gierige Algorithmen
  • Kapitel 20: Dynamische Programmierung

Übungen:

Um die Inhalte der Vorlesung zu vertiefen, bieten wir Präsenzübungen und auch Heimübungen an. Heimübungen lösen Sie in Kleingruppen von 2 bis 3 Personen und geben Ihre Lösung einmal pro Woche ab. Durch diese Punkte können Sie in der Klausur einen Bonus erreichen, sofern Sie die Klausur bestehen. Sie erhalten einen Bonusnotenschritt, wenn Sie 60% der Punkte auf den Heimübungen erreicht haben.

Zusätzlich haben Sie die Möglichkeit, in den wöchentlich stattfindenden Übungsgruppen Präsenzübungen zu bearbeiten. Dabei steht Ihnen ein Tutor als Ansprechpartner zur Verfügung.

Die Übungsaufgaben werden Freitags in das PANDA-System eingestellt. Die Abgabefrist ist jeweils der übernächste Mittwoch um 23:59 Uhr (MESZ). Bei verspäteter Abgabe erfolgt keine Bewertung!

Bei weiteren Fragen wenden Sie sich an Ihren Tutor.

Klausurzulassung:

Um die Klausur erfolgreich bestehen zu können, müssen Sie folgende Prüfungen nachweisen, soweit diese in Ihrem Modul "Data Structures and Algorithms" in PAUL anmeldbar sind

  1. Sie müssen eine Studienleistung im Rahmen der Vorlesung/Übung bestehen (oder bereits früher bestanden haben).
  2. Sie müssen eine qualifizierte Teilnahme im Rahmen des Praktikums bestehen (oder bereits früher bestanden haben), falls Sie ein Praktikum absolvieren müssen.

Für 1) müssen Sie in mindestens 75% der Heimübungszettel mindestens 20% der Punkte erreichen. Für 2) müssen Sie mindestens 33% der Gesamtpunkte des Praktikums erreichen.

Falls Sie bereits in einem vorigen Semester die Studienleistung zu "Datenstrukturen und Algorithmen" erhalten haben, so gilt diese auch für dieses Semester als erfüllt. Den Bonuspunkt aus einem vorigen Semester können Sie allerdings nicht übertragen.

Die Vorlesung ist nur dann bestanden, wenn die Klausur mit mindestens 4,0 bestanden ist. 

Klausurtermine:

  1. Erste Klausur: wird noch bekannt gegeben
  2. Zweite Klausur: wird noch bekannt gegeben

Sie dürfen in der Präsenzklausur keine Hilfsmittel benutzen außer einem beidseitig handbeschriebenen DINA4 Zettel.

Literatur:

  • Thomas Ottmann und Peter Widmayer. Algorithmen und Datenstrukturen. Springer Vieweg, 6. Edition, 2017. ISBN-10: 3662556499.
  • Martin Dietzfelbinger, Kurt Mehlhorn und Peter Sanders. Algorithmen und Datenstrukturen: Die Grundwerkzeuge. Springer Vieweg. Edition 2014.
  • Thomas H. Corman, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Algorithmen - Eine Einführung. De Gruyter Oldenbourg, 4. Edition, 2013. ISBN-10: 3486748610.
  • Robert Sedgewick und Kevin Wayne. Algorithmen: Algorithmen und Datenstrukturen. Person Studium, 4. aktualisierte Edition, 2014. ISBN-10: 9783868941845.

Materialien:

Generell finden Sie alle Materialien im PANDA-System.

Further information: