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, über Zoom
  • Freitags, 11.15 Uhr - 12.45 Uhr, über Zoom

Vorlesungsaufzeichnungen werden rechtzeitig vor den Vorlesungszeiten zur Verfügung gestellt, damit sich die Teilnehmer mit den Inhalten vertraut machen können. Zu den Vorlesungszeiten selbst gibt es dann die Möglichkeit, Fragen mit dem Dozenten abzuklären und dabei auf Themen nochmal etwas detaillierter (ggf. mit Beispielen) einzugehen. Von diesen Treffen sowie von den Übungsgruppentreffen werden keine Aufnahmen gemacht. 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 12. April statt.

Zentralübung

  • Freitags, 13.00 Uhr - 13.45 Uhr, über Zoom

Die erste Zentralübung findet am Freitag, den 30. 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 16. 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. Di. 11-13 Uhr: Sven Meyer
  2. Di. 16-18 Uhr: Mohness Waizy
  3. Mi. 16-18 Uhr Henning Hillebrandt
  4. Mi. 16-18 Uhr (zusammengelegt mit Übung 3)
  5. Do. 09-11 Uhr Thorsten Götte
  6. Do. 11-13 Uhr Tim Storm
  7. Do. 11-13 Uhr (zusammengelegt mit Übung 6)
  8. Do. 14-16 Uhr Julian Werthmann
  9. Do. 16-18 Uhr Julian Werthmann
  10. Do. 16-18 Uhr (zusammengelegt mit Übung 9)
  11. Fr. 14-16 Uhr Michael Penner
  12. Fr. 14-16 Uhr Marco Wübbeke
  13. Fr. 16-18 Uhr Michael Penner
  14. Fr. 16-18 Uhr (zusammengelegt mit Übung 13)

Präsenzübungen werden über Zoom oder BBB durchgeführt werden. Links werden dazu rechtzeitig bekannt gegeben. Der Übungsbeginn ist Montag, der 19. 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.

Melden Sie sich in PAUL für die Veranstaltung an.

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 bis zu 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 im Sommersemester 2020 durch Teilnahme an den Übungen zur Klausur zugelassen wurden, können Sie sich diese Leistung in diesem Semester anrechnen lassen. Melden Sie sich dazu per Email bei Thorsten Götte.

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

Klausurtermine:

  1. Erste Klausur: 9. August 2021, 16-18 Uhr, SP1, SP2, SP2.0.201
  2. Zweite Klausur: 20. September 2021, 9-11 Uhr, Mensa Academica

Sie dürfen in der Präsenzklausur keine Hilfsmittel benutzen außer einem beidseitig handbeschriebenen DINA4 Zettel. Falls die Klausuren online stattfinden müssen, wird das eine "open book" Klausur sein, d.h. Sie können alle Materialien der Vorlesung verwenden.

Materialien:

Generell finden Sie alle Materialien im PANDA-System.