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

Vorlesungsaufzeichnungen werden jeweils vor den Vorlesungszeiten oben in PANDA gestellt. Es wird keine live Vorlesungen geben, aber es besteht während der Vorlesungszeiten die Gelegenheit, in PANDA über die Inhalte der Vorlesung mit dem Dozenten zu chatten. 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 20. April statt.

Zentralübung

  • Montags, 13.00 Uhr - 13.45 Uhr

Voraussichtlich werden wir lediglich die Musterlösungen vor der Zentralübung in PANDA online stellen. Es wird keine live Zentralübung geben, aber es besteht während der Zentralübungszeiten die Gelegenheit, in PANDA über die Lösungen mit dem Leiter der Zentralübung zu chatten. Die erste Zentralübung findet am Montag, den 27. 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 Montag, dem 27. April von 1300 - 13.45 Uhr die Möglichkeit, mit dem Leiter des Programmierpraktikums, Rainer Feldmann, zu chatten.

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

  1. Mo. 14-16 Uhr Sven Meyer
  2. Mo. 14-16 Uhr Christopher Haensch
  3.  Mo. 16-18 Uhr Lukas Fehring
  4. Di. 14-16 Uhr Christopher Haensch
  5. Mi. 16-18 Uhr Philipp Manegold
  6. Do. 11-13 Uhr Fabian Rensing
  7. Do. 11-13 Uhr Thorsten Götte
  8. Do. 11-13 Uhr Kristian Hinnenthal
  9. Do. 14-16 Uhr Paul Kramer
  10. Do. 16-18 Uhr Lukas Wirth
  11. Fr. 9-11 Uhr Melina Kleber
  12. Fr. 14-16 Uhr Lukas Wirth
  13. Fr. 16-18 Uhr Lars Luchterhandt
  14. Fr. 16-18 Uhr Thilo Berger

Präsenzübungen werden über Webex durchgeführt werden. Links werden dazu rechtzeitig bekannt gegeben. Der Übungsbeginn ist Montag, der 27. April.

Die Veranstaltung wird über die PANDA-Plattform organisiert. Dort finden sich sämtliche Informationen und Materialien sowie alle Details zum Übungsbetrieb. 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: (zuletzt aktualisiert am 13.04.)

  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 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 Montag vor der Vorlesung in PANDA. 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 2019 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 Kristian Hinnenthal und Thorsten Götte.

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

Klausurtermine:

  1. Erste Klausur: 3. August 2020, 16-18 Uhr, SP1 + SP 2
  2. Zweite Klausur: 21. September 2020, 9-11 Uhr, SP2

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

Materialien:

Generell finden Sie alle Materialien im PANDA-System.