Modulcode:	infAlgMetP-01a
Englische Bezeichnung:	Algorithmic Methods in Practice
Modulverantwortliche(r):	Dr.-Ing. Sandro Esquivel
Turnus:	unregelmäßig (SS20 SS21 SS23 SS24 SS25)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	BSc-Inf-WP (BSc Inf (21)) WI (BSc Inf (15)) MSc-Inf-WP (MSc Inf (21)) 2F-MEd-Inf-WP (MEd-Hdl Inf (21)) 2F-MA-Inf-WP (2F-MA Inf (21)) MSc-WInf-WP-Inf (MSc WInf (21)) WI (MSc Inf (15)) WI (MSc WInf (15))
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ADS

Kurzfassung:

Von der Existenz algorithmischer Methoden zu wissen ist eine Sache - ihre Anwendbarkeit in konkreten Problemstellungen zu erkennen und sie zu implementieren eine andere. In diesem Kurs wollen wir uns genau diesem Aspekt widmen. Anhand von Problemen aus Programmierwettbewerben vertiefen wir bereits aus ADS bekannte Methoden und lernen weitere kennen und implementieren. Der Kurs kann als praktische Vertiefung und Fortführung einiger Inhalte aus ADS verstanden werden und bereitet auf weitere algorithmisch orientierte Kurse vor.

Der Kurs richtet sich dabei in erster Linie an Bachelorstudierende, kann aber auch als Wahlpflichtmodul im Masterstudium belegt werden.

Lernziele:

Die Studierenden vertiefen bekannte und erlernen neue algorithmische Methoden und deren Anwendbarkeit in praktischen Problemen. Besonderen Wert legen wir auf das Erkennen der geeigneten algorithmischen Methode zur Lösung einer praktischen Problemstellung und die effiziente Implementierung der Lösung.

Lehrinhalte:

In der Vorlesung vertiefen wir aus ADS bereits bekannte algorithmische Methoden und lernen zusätzliche Methoden kennen. Es werden die folgenden Themenbereiche behandelt:

• Praktische Implementierung von Algorithmen und Datenstrukturen
• Algorithmische Ansätze:
  
  • Exhaustive Search und Backtracking
  • Divide and Conquer
  • Greedy-Algorithmen
  • Dynamische Programmierung
• Algorithmisch behandelbare Probleme, z. B.:
  
  • Kombinatorische Probleme
  • Graphenprobleme
  • Suchprobleme
  • Geometrische Probleme
  • Zahlentheoretische Probleme
  • Stringverarbeitung
• Algorithmen auf Graphen, z. B.:
  
  • DFS und BFS
  • Zusammenhangskomponenten
  • Topologische Sortierung
  • Spannbäume
  • Kürzeste Pfade
  • Flussnetzwerke
• Theoretische Grundlagen, u. a. zu Kombinatorik, Graphentheorie und Geometrie

Die Inhalte werden, zusätzlich zur Behandlung in der Vorlesung, anhand praktischer (Programmier-) Übungen vertieft.

Weitere Voraussetzungen:

• Inf-ADS: Algorithmen und Datenstrukturen
• Vorkenntnisse in einer geeigneten Programmiersprache (C/C++, Java, Python)

Prüfungsleistung:

Die Zulassung zur Prüfung ist abhängig vom Lösen von Aufgabenserien in Kleingruppen. Dazu muss im Laufe des Semesters eine bestimmte Anzahl von Aufgaben erfolgreich gelöst werden. Zusätzlich muss im Rahmen der Übungen pro Kleingruppe mindestens eine Lösung zu einer Aufgabe vorgestellt werden.

Die Prüfungsleistung besteht in der theoretischen und praktischen Lösung einer Programmieraufgabe sowie der Erläuterung der Lösung und weiterer Vorlesungsinhalte.

Durch die freiwillige Teilnahme am German Collegiate Programming Contest (GCPC) während des Semesters können Bonuspunkte für das Erreichen der Klausurzulassung erworben werden.

Lehr- und Lernmethoden:

In der Vorlesung werden an Beamer und Tafel algorithmische Methoden besprochen und anhand konkreter Probleme erläutert. Die Präsenzvorlesungen werden durch Videos zum Selbststudium ergänzt.

In den Übungen werden gemeinsam Fragen zu Vorlesungsinhalten und Lösungen zu den Hausaufgaben besprochen und in Kleingruppen an den aktuellen Aufgaben gearbeitet. Lösungen werden dabei auch durch die Teilnehmenden im Stil eines kurzen Seminarvortrags präsentiert.

In den Hausaufgaben werden die Methoden angewandt im Rahmen typischer Aufgaben aus Programmierwettbewerben. Einige Aufgaben geben die algorithmische Methode vor, während andere darauf ausgelegt sind, selbst eine geeignete Lösungsmethode aus der Aufgabenstellung abzuleiten.

Zur Bearbeitung der Programmieraufgaben wird erwartet, dass die Studierenden eigene Rechner mitbringen. Es sollte mindestens ein Rechner pro Kleingruppe vorhanden sein.

Verwendbarkeit:

Die im Rahmen dieses Kurses vertieften Programmier- und Problemlösefähigkeiten sind u. a. für weiterführende algorithmisch orientierte Kurse mit Programmieranteilen, aber auch für Job Assessments nützlich.

Literatur:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms (3rd Edition). The MIT Press, 2009. ISBN 978-0-262-03384-8
• Steven S. Skiena, Miguel A. Revilla: Programming Challenges - The Programming Contest Training Manual Springer-Verlag, 2003. ISBN 0-387-00163-8
• Steven Halim, Felix Halim: Competitive Programming 3 - The New Lower Bound of Programming Contests. Lulu, 2013. Band 1 ist frei verfügbar unter: https://cpbook.net
• Antti Laaksonen: Competitive Programmer's Handbook. Creative Commons BY-NC-SA, 03.07.2018. Frei verfügbar unter: https://cses.fi/book

Verweise:

Kommentar: