Institut für Theoretische Informatik, Algorithmik II

Algorithmen II

Klausur am 25.09.2020

Die Prüfung findet am Freitag, den 25.09.2020, um 13.30 Uhr im Zelt am Forum (befindet sich zwischen dem AKK und dem Hörsaal Audimax) statt.

Die Bearbeitungszeit beträgt 120 Minuten. Es darf ein doppelseitig handbeschriebenes DIN A4 Blatt mit in die Klausur genommen werden.

Hier die An-/Abmeldedaten:

Anmeldebeginn:  10.07.2020
Anmeldeschluss: 18.09.2020
Abmeldeschluss: 24.09.2020

Diese Fristen gelten auch für Anmeldungen in Papierform, bitte schreiben Sie frühzeitig an Anja Blancani (blancaniNkn4∂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.
 

Bitte beachten Sie zur Prüfungsteilnahme unbedingt folgende Hinweise des KIT-Präsidiums (siehe auch hier, "Studium & Lehre/Prüfungen & Lehrveranstaltungen/Was ist bei der Durchführung der Klausuren im Sommersemester 2020 zu beachten? (Stand: 14.07.2020)):
 

  • Bitte lesen Sie die „Erklärung über den fehlenden Verdacht einer Infektion mit dem Coronavirus bei der Teilnahme an einer Präsenz-Prüfung des Karlsruher Instituts für Technologie (KIT) External Link“, unterschreiben diese am oder kurz vor Prüfungstermin, um Ihren aktuellen Gesundheitszustand zum Prüfungszeitraum zu bestätigen. Bringen Sie diese zur Klausur mit. Blanko-Formulare sind auch bei den Aufsichtspersonen vorrätig.
  • Die Verwendung einer Mund‐Nase‐Bedeckung (nicht‐medizinische Alltagsmaske, Halstuch o.ä.) ist für Aufsichtspersonal und Prüflinge beim Betreten und Verlassen des Prüfungsraums dringend empfohlen. Während der Abfassung der Klausur kann sie abgelegt werden.
  • Die Studierenden (Prüflinge) dürfen sich weder vor noch nach der Klausur vor dem Hörsaal oder vor dem Gebäude versammeln. Abstands- und Hygieneregeln sind im Umfeld des Prüfungsortes und am Prüfungsort selbst jederzeit einzuhalten. Sie verlassen das Gebäude nach der Prüfung einzeln und entfernen sich zügig.
  • Den Anweisungen der Aufsichtspersonen ist Folge zu leisten.
     

Erklärung über den fehlenden Verdacht einer Infektion mit dem Coronavirus bei der Teilnahme an einer Präsenz-Prüfung des Karlsruher Instituts für Technologie (KIT):

https://intranet.kit.edu/downloads/erklaerung-praesenzpruefung.pdf  External Link


Bitte achten Sie unbedingt darauf, die aktuelle Version der Erklärung mitzubringen, zur Zeit ist das die Fassung Stand 06.07.2020.

Abweichend von der Studien- und Prüfungsordnung des KIT und aufgrund der besonderen Situation im Hinblick auf das Coronavirus (SARS-CoV-2) wurde für die aktuelle Prüfungsphase die Möglichkeit eröffnet, sich von allen Erfolgskontrollen ohne Angabe von Gründen auch kurzfristig, d. h. bis unmittelbar vor einer Erfolgskontrolle, von dieser schriftlich abzumelden. Eine solche Abmeldung kann per E-Mail an den/die zuständige/n Prüfer/in erfolgen. Es ist kein ärztliches Attest erforderlich. Bitte senden Sie Ihre Prüfungsabmeldung unbedingt mit CC an blancaniWmj2∂kit edu.
 

Bitte beachten Sie dabei folgende Punkte: Sofern noch möglich, ist eine Abmeldung von der jeweiligen Erfolgskontrolle seitens der Kandidatin bzw. des Kandidaten selbstständig im Campusmanagementsystem durchzuführen – bitte sehen Sie in diesen Fällen von einer Abmeldung per E-Mail ab. Wenn Sie sich direkt per E-Mail bei Ihrem/r zuständige/n Prüfer/in abmelden, verwenden Sie für die Abmeldung Ihre KIT-E-Mail-Adresse, um eine eindeutige und sichere Zuordnung zu ermöglichen. Geben Sie Ihre Matrikelnummer sowie den Namen sowie Nummer der Erfolgskontrolle(n) an, von der bzw. denen Sie sich abmelden möchten.

 

Beachten Sie bitte auch folgendes (siehe auch hier):
 

Im Wartebereich vor Einlass in den Prüfungsraum oder während der Prüfung treten bei mir Symptome einer Covid-19-Erkrankung auf. Wie soll ich mich verhalten?

Weisen Studierende im Wartebereich vor Einlass in den Prüfungsraum oder während der Prüfung Symptome einer Covid-19-Erkrankung auf, haben die Prüferinnen bzw. Prüfer diese Personen unverzüglich von der Teilnahme an der betreffenden Prüfung auszuschließen. Der Sachverhalt ist von der Prüferin/dem Prüfer bzw. der aufsichtführenden Person zu dokumentieren und dem zuständigen Prüfungsausschuss zur Kenntnis zu geben. Den ausgeschlossenen Personen wird empfohlen, sich bei Fragen zu dem weiteren Ablauf (z.B. Wiederholung der Prüfung, Wertung der Prüfung) mit dem zuständigen Prüfungsausschuss in Verbindung zu setzen.

Der Ausschluss von der Teilnahme an der Prüfung wird nicht als unentschuldigtes Versäumnis oder als Rücktritt ohne Geltendmachung triftiger Gründe gewertet. Vielmehr gilt der Prüfungsversuch - selbst wenn er bereits begonnen haben sollte – als nicht unternommen. Betroffenen Studierenden verbleibt weiterhin die ihnen regulär vor Beginn der Prüfung zustehende Anzahl von Prüfungsversuchen.

Können betroffene Personen durch eine ärztliche Bescheinigung nachweisen, dass sie an einer chronischen Erkrankung oder Allergie leiden, die zu coronaspezifischen Symptomen führt, ist das KIT bestrebt, ihnen eine Teilnehme an der Prüfung zu gestatten, dies möglichst in einem gesonderten Raum oder unter Tragens einer Mund-Nasen-Bedeckung. Um hier die geeigneten organisatorischen Maßnahmen ergreifen zu können, werden die betroffenen Prüfungskandidatinnen und -kandidaten gebeten, sich frühzeitig mit der Prüferin bzw. dem Prüfer in Verbindung setzen.

 

Weitere Informationen finden Sie hier.

 

 

Informationen

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.

Lehrinhalt

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.

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.

Prüfung

Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung im Umfang von 120 Minuten nach § 4 Abs. 2 Nr. 1 SPO.

Klausur am 20.03.2020

Die Klausur findet nicht statt, weitere Informationen erhalten Sie hier.

Info:

Am 23.12.2019 findet KEINE Vorlesung statt.

Klausur:

Die Hauptklausur findet am 20.03.2020 um 11:00 statt. Die Bearbeitungszeit beträgt 120 Minuten.
Es darf ein doppelseitig handbeschriebenes DIN A4 Blatt mit in die Klausur genommen werden.

Skript:

Skript (Stand: 28.10.2019)

Folien:

Komplett: Folien (Stand: 03.02.2020)
Kapitel 0 (overview): Folien (Stand: 01.12.2019)
Kapitel 1 (algorithm engineering): Folien (Stand: 01.12.2019)
Kapitel 2 (advanced datastructures): Folien (Stand: 01.12.2019)
Kapitel 3 (shortest path algorithms): Folien (Stand: 01.12.2019)
Kapitel 4 (dfs): Folien (Stand: 01.12.2019)
Kapitel 5 (maximum flows and matchings): Folien (Stand: 01.12.2019)
Kapitel 6 (randomized algorithms): Folien (Stand: 01.12.2019)
Kapitel 7 (external algorithms): Folien (Stand: 01.12.2019)
Kapitel 8 (approximation algorithms): Folien (Stand: 01.12.2019)
Kapitel 9 (fixed parameter algorithms): Folien (Stand: 03.12.2019)
Kapitel 10 (parallel algorithms): Folien (Stand: 03.02.2020)
Kapitel 11 (stringology): Folien (Stand: 03.02.2020)
Kapitel 11a (cobs): Folien (Stand: 26.01.2020)
Kapitel 11b (burrows wheeler transform): Folien (Stand: 27.01.2020)
Kapitel 12 (geometric algorithms): Folien (Stand: 03.02.2020)
Kapitel 13 (online algorithms): Folien (Stand: 03.02.2020)

Übungen:

Übung 1: Folien (Stand: 21.10.2019)
Übung 2: Folien (Stand: 28.10.2019)
Übung 3: Folien (Stand: 05.11.2019)
Übung 4: Folien (Stand: 11.11.2019)
Übung 5: Folien (Stand: 18.11.2019)
Übung 6: Folien (Stand: 26.11.2019)
Übung 7: Folien (Stand: 10.12.2019)
Übung 8: Folien (Stand: 17.12.2019)
Übung 9: Folien (Stand: 14.01.2020)
Übung 10: Folien (Stand: 21.01.2020)

Übungsblätter:

Übungsblatt 1: Aufgaben (Stand: 21.10.2019) Musterlösung (Stand: 05.11.2019)
Übungsblatt 2: Aufgaben (Stand: 05.11.2019) Musterlösung (Stand: 22.11.2019)
Übungsblatt 3: Aufgaben (Stand: 22.11.2019) Musterlösung (Stand: 06.12.2019)
Übungsblatt 4: Aufgaben (Stand: 06.12.2019) Musterlösung (Stand: 04.01.2020)
Übungsblatt 5: Aufgaben (Stand: 21.01.2020) Musterlösung (Stand: 21.01.2020)
Übungsblatt 6: Aufgaben (Stand: 21.01.2020) Musterlösung (Stand: 26.02.2020)
Übungsblatt 7: Aufgaben (Stand: 26.02.2020) Musterlösung (Stand: 26.02.2020)