Ausgewählte Probleme aus dem ACM Programming Contest
Fakultät für Informatik und Mathematik ©
Name Ausgewählte Probleme aus dem ACM Programming Contest
Verantwortlich Prof. Dr. Manfred Gruber
SWS 4
ECTS 5
Sprache(n) Deutsch
Lehrform SU mit Praktikum
Angebot nach Ankündigung
Aufwand

30 Präsenzstunden Vorlesung, 30 Präsenzstunden Praktikum, 45 Stunden Vor-/Nachbereitung des Praktikums, 45 Stunden Nachbereitung der Vorlesung und Prüfungsvorbereitung

Voraussetzungen

Softwareentwicklung I und II

Ziele
  • Kenntnis der Algorithmen, sowie praktische Erfahrung mit der Implementierung von Programmen in Java/C/C++
  • praktische Anwendung der algorithmischen/mathematischen Methoden, die ein Problem von der Analyse bis zum Programm komplett behandeln
  • Teilnahme an Programmierung Wettbewerbe
Inhalt

In Referaten stellen die Teilnehmer Problemstellungen aus dem seit 1970 alljährlich stattfindenden ACM Programming Contest vor. Es geht um Themen wie Mengen, Relationen, Algebra, Algorithmische Zahlentheorie, Codierungstheorie, Algorithmische Geometrie, Kombinatorik, Greedy, Backtracking, Dynamische Programmierung, Graphentheorie, Rekursion, Teile und Herrsche, Zeichenketten-Such-Algorithmen (String-Matching-Algorithms), Kompexitätstheorie, NP-vollständige Probleme, Datenstrukturen.

Im praktischen Teil entwerfen und implementieren die Teilnehmer Programme für ausgewählte Probleme. Die Auswahl der Referatsthemen erfolgt in einer Besprechung spätestens zwei Wochen vor dem Vortrag. Die Länge eines Vortrags ist auf maximal 30 Minuten begrenzt. Der Inhalt soll ein Problem klar und mit Hilfe einiger Beispiele erläutern und eventuell verwandte Probleme präsentieren. Kurz soll auch die Realisierung der Lösung/en in einer Programmiersprache gezeigt werden, sowie der Kern der Methode im Pseudocode/Diagramm.

Beispiele aus [2]: "Verschachtelte Schachteln" S. 25, "Die Zahl 4" S. 108, "Die Torte" S. 115, "Collatz-Funktion" S. 125, "Die Türme von Hanoi" S. 146, "Orangensport" S. 196, "Alle Wege des Springers" S. 188, "Sudoku" S. 214, "Das Haus des Nikolaus" S. 221, "Verteilung der Geschenke" S. 258, "Schotten auf dem Oktoberfest" S. 266 oder "Arbitrage" S. 305.

Medien und Methoden

Tafel, Folien oder Beamer

Literatur
  1. Doina Logofatu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0126-5, 2006. (online in Campus)
  2. Doina Logofatu, Grundlegende Algorithmen mit Java, Vieweg Verlag, ISBN 978-3-8348-0369-6, 2008. (online in Campus)
  3. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8.
  4. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. MIT Press, Boston 2001, 2002, 2003, ISBN 0-262-53196-8. (engl. Orig.-Fass.)

Webreferenzen:

  1. ACM International Collegiate Programming Contest (ICPC): http://cm2prod.baylor.edu/login.jsf
  2. ACM Programming Contest Beschreibung der Uni Ulm, Information für das Contest 2008 der Uni Ulm: http://www.informatik.uni-ulm.de/acm/
  3. Internet Problem Solving Contest: http://ipsc.ksp.sk/
  4. Valladolid Programming Contest: http://icpcres.ecs.baylor.edu/onlinejudge
Zuordnungen Curricula
SPO Fachgruppe Code ab Semester Prüfungsleistungen