Klausur am 15.03.2021

Hörsaaleinteilung

A bis Kra: Geb. 01.13, Alter Speisesaal Mensa
Kre bis Ve: Geb. 01.13, Neuer Speisesaal Mensa
Vo bis Wil: Informatik-Hauptgebäude 50.34, Hörsaal -101
Wim bis Z: Informatik-Hauptgebäude 50.34, Hörsaal -102

Wir gehen im Moment davon aus, dass die Klausur als Präsenzveranstaltung unter strengen Hygieneauflagen stattfindet. Insbesondere muss die ganze Zeit ein medizinischer Mund-Nasen-Schutz (nur OP-Masken oder FFP2) getragen werden, siehe auch die Corona-Verordnung Studienbetrieb (§4).

Bitte beachten Sie die Hinweise des KIT-Präsidiums unter "Studium & Lehre/Prüfungen & Lehrveranstaltungen/Was ist bei der Durchführung der Klausuren im Wintersemester 2020/21 zu beachten?" und lesen Sie dieses Merkblatt. Bitte nehmen Sie auch dieses Merkblatt zum Zutritts- und Teilnahmeverbot zur Kenntnis.

Wir weisen darauf hin, dass Sie sich problemlos bis einschließlich 14.03.2021 für die jetzige Klausur abmelden und an der nächsten Klausur im Sommersemester (vermutlich September) teilnehmen können. Es besteht eine gewisse Hoffnung, dass dann weniger strenge Regeln gelten.

Studierende, die aus medizinischen Gründen von der Mund-Nasen-Bedeckungs-Tragepflicht befreit sind oder eine Behinderung oder chronische Erkrankung haben (siehe o.g. Merkblatt, Seite 2), senden bitte spätestens bis 04.03.2021 eine E-Mail an blancaniGxb7∂kit edu.

Die Prüfung findet am Montag, den 15.03.2021, um 16 Uhr statt. Die Bearbeitungszeit beträgt 120 Minuten. Es darf ein doppelseitig handbeschriebenes DIN A4 Blatt mit in die Klausur genommen werden.

Für die Klausur am 15.03.2021 können Sie sich ab 12.01.2021 bis 05.03.2021 am Studierendenportal anmelden, eine Abmeldung ist bis einschließlich 14.03.2021 möglich. Diese Fristen gelten auch für Anmeldungen in Papierform, bitte schreiben Sie frühzeitig an Anja Blancani (blancaniIzb5∂kit edu), falls Sie eine Prüfungszulassung abgeben müssen.

Melden Sie sich bitte unbedingt zur Prüfung an. Liegt keine Anmeldung vor, verursacht das zusätzlichen Aufwand und kostet Zeit.

Die Hörsaaleinteilung veröffentlichen wir rechtzeitig.

Informationen zur Vorlesung

Die Vorlesung Algorithmen II findet im Wintersemester 2020/2021 online statt. Dazu werden die Vorlesungen vor-aufgezeichnet auf YouTube zur Verfügung gestellt. Die Vorlesungstermine werden für eine Videokonferenz über Zoom genutzt: jeweils Montags findet eine Fragestunde mit Prof. Sanders statt und Dienstags die Übung (ab 10.11.2020).

Die Vortragssprache der Vorlesung ist in diesem Jahr Englisch. Deutsche Folien und eine deutsche Aufzeichnung aus vorherigen Jahren stehen aber weiterhin zur Verfügung. Der Übungsbetrieb und die Klausur werden auf Deutsch stattfinden.

Das Passwort für das Zoom Meeting wird über Ilias bekannt gegeben.

NEU: die Zoom Meetings am Montag, den 21.12.2020 und Dienstag, den 22.12.200 finden nicht statt.

Skript

Skript (Stand: 21.10.2020)

Folien

Änderungen zum Vorjahr:

Kapitel 11 (stringology): Larsson-Sadakane Algorithmus durch Manber-Myers Algorithmus ersetzt
Kapitel 11a (COBS) und Kapitel 11b (Burrows Wheeler Transform) fallen dieses Jahr weg

Kapitel 0 (overview): Folien (Stand: 08.11.2020)
Kapitel 1 (algorithm engineering): Folien (Stand: 02.11.2020)
Kapitel 2 (advanced datastructures): Folien (Stand: 03.11.2020)
Kapitel 3 (shortest path algorithms): Folien (Stand: 01.12.2020)
Kapitel 4 (dfs): Folien (Stand: 02.11.2020)
Kapitel 5 (maximum flows and matchings): Folien (Stand: 01.12.2020)
Kapitel 6 (randomized algorithms): Folien (Stand: 01.12.2020)
Kapitel 7 (external algorithms): Folien (Stand: 01.12.2020)
Kapitel 8 (approximation algorithms): Folien (Stand: 07.12.2020)
Kapitel 9 (fixed parameter algorithms): Folien (Stand: 12.02.2021)
Kapitel 10 (parallel algorithms): Folien (Stand: 08.03.2021)
Kapitel 11 (stringology): Folien (Stand: 12.02.2021)
Kapitel 12 (geometric algorithms): Folien (Stand: 12.02.2021)
Kapitel 13 (online algorithms): Folien (Stand: 12.02.2021)

Übungen

Übung 1: Folien (Stand: 10.11.2020)
Übung 2: Folien (Stand: 17.11.2020)
Übung 3: Folien (Stand: 24.11.2020)
Übung 4: Folien (Stand: 01.12.2020)
Übung 5: Folien (Stand: 08.12.2020)
Übung 6: Folien (Stand: 15.12.2020)
Übung 7: Folien (Stand: 12.01.2021)
Übung 8: Folien (Stand: 21.01.2021)
Übung 9: Folien (Stand: 26.01.2021)
Übung 10: Folien (Stand: 02.02.2021)
Übung 11: Folien (Stand: 09.02.2021)
Übung 12: Folien (Stand: 16.02.2021)

Übungsblätter

Übungsblatt 1: Aufgaben (Stand: 09.11.2020) Musterlösung (Stand: 23.11.2020)
Übungsblatt 2: Aufgaben (Stand: 23.11.2020) Musterlösung (Stand: 18.12.2020)
Übungsblatt 3: Aufgaben (Stand: 18.12.2020) Musterlösung (Stand: 21.12.2020)
Übungsblatt 4: Aufgaben (Stand: 21.12.2020) Musterlösung (Stand: 18.01.2021)
Übungsblatt 5: Aufgaben (Stand: 18.01.2021) Musterlösung (Stand: 25.01.2021)
Übungsblatt 6: Aufgaben (Stand: 18.01.2021) Musterlösung (Stand: 02.02.2021)
Übungsblatt 7: Aufgaben (Stand: 12.02.2021) Musterlösung (Stand: 15.02.2021)

Beschreibung

Bemerkungen	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/Englisch
Voraussetzungen	Siehe Modubeschreibung.
Literaturhinweise	K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox Mehlhorn, Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie Ahuja, Magnanti, Orlin: Network Flows de Berg, Cheong, van Kreveld, Overmars: Computational Geometry: Algorithms and Applications Gonzalo Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
Arbeitsbelastung	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
Ziel	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.