Algorithmen II
- Typ: Vorlesung (V)
- Semester: WS 21/22
-
Ort:
Geb. 30.46, Chemie Neuer Hörsaal
-
Zeit:
Montag 10.00 - 11.30 Uhr
Dienstag 16.00 - 17.30 Uhr -
Dozent:
Prof. Dr. Peter Sanders
Daniel Seemaier
Hans-Peter Lehmann - SWS: 4
- LVNr.: 24079
Klausur 23.09.2022
Die Ergebnisse sind online.
Die Einsicht findet am Mittwoch, den 09.11.2022, von 11:30 Uhr bis 12:30 Uhr in Raum 236 (Informatik-Gebäude, 50.34) statt. Bringen Sie bitte Ihren Studierendenausweis mit.
Klausur 15.03.2022
Die Ergebnisse sind online.
Die Einsicht findet am Mittwoch, den 15.06.22 von 11:30 Uhr bis 13:00 Uhr in Raum 236 (Informatik-Gebäude, 50.34) statt. Bringen Sie bitte Ihren Studierendenausweis mit.
Vorlesung
Die Vorlesung findet in Präsenz statt. Dabei besteht 2G-Pflicht und für alle ZuhörerInnen Maskenpflicht. Die Aufzeichnungen vom letzten Jahr sind auf YouTube verfügbar. Weitere Informationen werden im Corona-FAQ des KIT veröffentlicht oder vom Präsidium per Mail verschickt. Achtung: Wer ohne 2G-Nachweis an einer Lehrveranstaltung teilnimmt, begeht eine Ordnungswidrigkeit, die vom KIT zur Anzeige gebracht werden kann. Die Erfassung der Kontaktdaten erfolgt über das KIT-eigene KONKIT-System.
Aktuelles
- 26.01.2021: Am nächsten Dienstag, also 01.02.22, werden wir 90 Minuten Übung machen. Wir werden gemeinsam eine Altklausur durchrechnen.
- 06.12.2021: Die KONKIT-Boxen können jetzt 2G. Fall der 2G-Status auf der KIT-Karte gespeichert ist, reicht es also, die KIT-Karte an die Box zu halten. Falls er nicht darauf gespeichert ist, brauchen wir weiterhin den QR-Code.
- 27.11.2021: Die KONKIT-Boxen können aktuell noch nicht zur 2G Kontrolle genutzt werden. Das heißt, wir werden die QR-Codes aller Teilnehmenden scannen
und zusätzlich ein amtliches Ausweisdokumentkontrollieren müssen. Zusätzlich zur 2G-Kontrolle wird für die Kontaktverfolgung auch noch KONKIT-System benutzt. Das heißt, Sie müssen zur Vorlesung folgende 3 Dinge mitbringen:- KIT-Karte
Amtliches Ausweisdokument(mittlerweile gab es vom KIT die Info, dass wir das nicht müssen)- 2G-Nachweis (Achtung: ab 01.12. gilt nur noch der QR-Code, nicht mehr der Impfpass)
- 26.11.2021: Die Vorlesung wird bis auf Weiteres in Präsenz weitergehen. Bitte achten Sie darauf, einen 2G Nachweis mitzubringen. Kommen Sie bitte nicht zu spät zur Vorlesung. Außerdem würden wir Sie bitten, nicht vor unserer Ankunft (ca 15 Minuten vor Beginn) in den Hörsaal zu gehen, damit wir an der Tür
mit den KONKIT-Boxen(siehe Update vom 27.11.21) kontrollieren können anstatt lange durch die Reihen zu laufen und die QR-Codes zu scannen. - 12.11.2021: Momentane Planung für die nächsten Termine (Änderungen vorbehalten)
- 15.11.21: Vorlesung Prof. Peter Sanders, Thema: Kürzeste Wege
- 16.11.21: Vorlesung Dr. Florian Kurpicz, Thema: Stringology (3/3)
- 27.10.2021: Momentane Planung für die nächsten Termine (Änderungen vorbehalten)
- 01.11.21: Feiertag, keine Vorlesung
- 02.11.21: Vorlesung Dr. Florian Kurpicz, Thema: Stringology (1/3)
- 08.11.21: Doppel-Übung, Thema: Heaps und Stringology
- 09.11.21: Vorlesung Dr. Florian Kurpicz, Thema: Stringology (2/3)
Skript
Skript (Stand: 22.09.2021)
Folien
Kapitel 1 (algorithm engineering): Folien (Stand: 27.10.2021)
Kapitel 2 (advanced datastructures): Folien (Stand: 27.10.2021)
Kapitel 3 (shortest path algorithms): Folien (Stand: 27.10.2021)
Kapitel 4 (dfs): Folien (Stand: 27.10.2021)
Kapitel 5 (maximum flows and matchings): Folien (Stand: 27.10.2021)
Kapitel 6 (randomized algorithms): Folien (Stand: 26.11.2021)
Kapitel 7 (external algorithms): Folien (Stand: 26.11.2021)
Kapitel 8 (approximation algorithms): Folien (Stand: 26.11.2021)
Kapitel 9 (fixed parameter algorithms): Folien (Stand: 26.11.2021)
Kapitel 10 (parallel algorithms): Folien (Stand: 29.11.2021)
Kapitel 11a (stringology): Folien (Stand: 17.11.2021) Handout (Stand: 17.11.2021)
Kapitel 11b (stringology): Folien (Stand: 17.11.2021) Handout (Stand: 17.11.2021)
Kapitel 11c (stringology): Folien (Stand: 17.11.2021) Handout (Stand: 17.11.2021)
Kapitel 12 (geometric algorithms): Folien (Stand: 01.08.2022)
Kapitel 13 (online algorithms): Folien (Stand: 26.11.2021)
Übungen
Übung 2: Folien (Stand: 07.11.2021) Handout (Stand: 15.12.2021)
Übung 3: Folien (Stand: 07.11.2021) Handout (Stand: 15.12.2021)
Übung 4: Folien (Stand: 23.11.2021) Handout (Stand: 15.12.2021)
Übung 5: Folien (Stand: 07.12.2021) Handout (Stand: 15.12.2021)
Übung 6: Folien (Stand: 07.01.2022) Handout (Stand: 07.01.2022)
Übung 7: Folien (Stand: 21.12.2021) Handout (Stand: 21.12.2021)
Übung 8: Folien (Stand: 11.01.2022) Handout (Stand: 11.01.2022)
Übung 9: Folien (Stand: 18.01.2022) Handout (Stand: 18.01.2022)
Übung 10: Folien (Stand: 02.02.2022) Handout (Stand: 02.02.2022)
Übung 11: Folien (Stand: 01.02.2022) Handout (Stand: 01.02.2022)
Übungsblätter
Übungsblatt 2: Aufgaben (Stand: 08.11.2021) Musterlösung (Stand: 22.11.2021)
Übungsblatt 3: Aufgaben (Stand: 22.11.2021) Musterlösung (Stand: 01.03.2022)
Übungsblatt 4: Aufgaben (Stand: 06.12.2021) Musterlösung (Stand: 14.01.2022)
Übungsblatt 5: Aufgaben (Stand: 20.12.2021) Musterlösung (Stand: 10.01.2022)
Übungsblatt 6: Aufgaben (Stand: 10.01.2022) Musterlösung (Stand: 31.01.2022)
Übungsblatt 7: Aufgaben (Stand: 24.01.2022) Musterlösung (Stand: 07.02.2022)
Übungsblatt 8: Aufgaben (Stand: 07.02.2022) Musterlösung (Stand: 21.02.2022)
Beschreibung
| Inhalt |
Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt. Der/die Studierende besitzt einen vertieften Einblick in die theoretischen und praktischen Aspekte der Algorithmik und kann algorithmische Probleme in verschiedenen Anwendungsgebieten identifizieren und formal formulieren. Außerdem kennt er/sie weiterführende Algorithmen und Datenstrukturen aus den Bereichen Graphenalgorithmen, Algorithmische Geometrie, String-Matching, Algebraische Algorithmen, Kombinatorische Optimierung und Algorithmen für externen Speicher. Er/Sie kann unbekannte Algorithmen eigenständig verstehen, sie den genannten Gebieten zuordnen, sie anwenden, ihre Laufzeit bestimmen, sie beurteilen sowie geeignete Algorithmen für gegebene Anwendungen auswählen. Darüber hinaus ist der/die Studierende in der Lage, bestehende Algorithmen auf verwandte Problemstellungen zu übertragen. Neben Algorithmen für konkrete Problemstellungen kennt der/die Studierende fortgeschrittene Techniken des algorithmischen Entwurfs. Dies umfasst parametrisierte Algorithmen, approximierende Algorithmen, Online-Algorithmen, randomisierte Algorithmen, parallele Algorithmen, lineare Programmierung, sowie Techniken des Algorithm Engenieering. Für gegebene Algorithmen kann der/die Studierende eingesetzte Techniken identifizieren und damit diese Algorithmen besser verstehen. Darüber hinaus kann er/sie für eine gegebene Problemstellung geeignete Techniken auswählen und sie nutzen, um eigene Algorithmen zu entwerfen. |
| Vortragssprache | Deutsch |
| Literaturhinweise |
K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox |
| Organisatorisches |
Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung im Umfang von 120 Minuten nach § 4 Abs. 2 Nr. 1 SPO. Arbeitsaufwand Vorlesung mit 3 SWS + 1 SWS Übung. 6 LP entspricht ca. 180 Stunden ca. 45 Std. Vorlesungsbesuch, ca. 15 Std. Übungsbesuch, ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter ca. 30 Std. Prüfungsvorbereitung Voraussetzungen Siehe Modubeschreibung. |