Dozent: Prof. Dr. Christian Scheideler

Modulinformation

• V4+ZÜ1+Ü2 SWS
• 8 ECTS

Vorlesung

• Donnerstags, 11.15 Uhr - 12.45 Uhr, Audimax
• Freitags, 11.15 Uhr - 12.45 Uhr, L2

Die erste Vorlesung findet am Donnerstag, den 15. Oktober statt.

Zentralübung

• Donnerstags, 13.00 Uhr - 13.45 Uhr, Audimax

Die erste Zentralübung findet am Donnerstag, den 29. Oktober statt.

Übungsgruppen

Die Anmeldung zu den Übungsgruppen erfolgt über PAUL. 

1. Mo. 11-13 Uhr, N 3 211
2. Mo. 11-13 Uhr, O 1 252
3. Di. 11-13 Uhr, N 3 211
4. Di. 11-13 Uhr, D 1 303
5. Di. 14-16 Uhr, O 1 252
6. Di. 16-18 Uhr, N 3 211
7. Mi. 11-13 Uhr, N 3 211
8. Mi. 14-16 Uhr, D 1 303
9. Do. 09-11 Uhr, D 1 312
10. Do. 09-11 Uhr, N 3 211
11. Fr. 09-11 Uhr, O 1 252
12. Fr. 09-11 Uhr, N 3 211

Der Übungsbeginn ist Montag, der 19. Oktober.

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 eine Studienleistung bestehen (oder bereits früher bestanden haben). Dazu müssen Sie in mindestens 75% der Heimübungszettel mindestens 20% der Punkte 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: 15.02.2027, Zeit und Raum TBA
2. Zweite Klausur: 23.03.2027, Zeit und Raum TBA

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.