Modul "Ausgewählte Probleme aus dem ACM Programming Contest"

(Selected Problems of the ACM Programming Contest)


Studiengang
Bachelor Informatik und Wirtschaftsinformatik
Modulbezeichnung
Ausgewählte Probleme aus dem ACM Programming Contest
Kürzel
IF-I-B-F41
Semester
4.,  6. oder 7. Semester
Angebot
Nach Ankündigung
Modulverantwortliche(n)

Prof. Dr. Manfred Gruber

Dozent(inn)en

Doina Logofătu

Sprache
Deutsch
Zuordnung zum Curriculum
Fachwissenschaftliches Wahlpflichfach
Lehrform/SWS
Seminaristischer Unterricht mit Praktikum, 4 SWS
Arbeitsaufwand
30 Präsenzstunden Vorlesung, 30 Präsenzstunden Praktikum, 45 Stunden Vor-/Nachbereitung des Praktikums,
45 Stunden Nachbereitung der Vorlesung und Prüfungsvorbereitung
Kreditpunkte
5 ECTS-Punkte
Voraussetzungen
Softwareentwicklung I und II
Lernziele/Kompetenzen
- Kenntnis der Algorithmen,  sowie praktische Erfahrung mit der Implementierung von Programmen in Java/C/C++
- praktische Anwendung der algortihmischen/mathematischen Methoden, die ein Problem von der Analyse bis zum Programm komplett behandeln
- Teilnahme an Programmierung Wettbewerbe
Inhalt

Es werden in der Woche 2 Stunden Vorlesung/Übung und 2 Stunden Referate, Implementierungen und Diskussionen stattfinden.
In Referaten stellen die Teilnehmer Problemstellungen aus dem seit 1970 alljährlich stattfindenden ACM Programming Contest vor. Es geht überwiegend um:

  • 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. Anschließend besprechen wir jeden Vortrag, wobei wir auch gerne Implementierungsdetails analysieren können.

Als Beispiele sehen Sie sich [2] Grundlegende Algorithmen mit Java an:
            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.

Wichtig:
Wir beginnen jetzt damit, ein Team von Studierenden auszuwählen, das unsere Hochschule im regionalen Wettbewerb des ACM ICPC vertreten wird. Die Teilnahme an diesem FWP-Fach kann als ideales Training dafür angesehen werden. Bitte lesen Sie auch die Regeln auf der Webseite des Wettbewerbs durch: http://cm2prod.baylor.edu/login.jsf.
ACM Programming Contest Call: http://w3-o.cs.hm.edu/~logofatu/AnzeigeACM/index.html

Die, die sich für einen Platz im Team bewerben wollen, schreiben bitte eine EMail an EMail.
Studien-/Prüfungsleistungen
Benotete Studienarbeit (40%) und benotete mündliche Prüfung (60%)
Medienform
Tafel, Folien oder Beamer, Labor
Literatur

1.  Doina Logofătu, Algorithmen und Problemlösungen mit C++, Vieweg Verlag, ISBN 978-3-8348-0126-5, 2006. (online in Campus)
2. 
Doina Logofătu, 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.
  - 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:

4.  ACM International Collegiate Programming Contest (ICPC)
5. 
ACM Programming Contest Beschreibung der Uni Ulm
        Information für das Contest 2008 der Uni Ulm
6.  Internet Problem Solving Contest
7.  Valladolid Programming Contest