Programmier-Praktikum
ACM Programming Contest (SS 2002)

Dozent	Prof. Dr. Angelika Steger
Zeit	Freitags, 12.15 - 13.45 Uhr, Terminänderung
Raum	S2229
Voraussetzungen	Grundlegende Programmierkenntnisse
Praktikumsleitung	Alexander Offtermatt-Souza und Ingo Rohloff
Anmeldung	Zentralanmeldung in der Sun-Halle
Scheinerwerb	Einzelteilnehmer: bestehen aller Aufgabenblätter Zweiergruppen: bestehen aller Aufgabenblätter und 5 frei wählbare Aufgaben
Aufgabenblätter	hier klicken
Abgabe	Final Version an acmprakt@in.tum.de
Anforderungen	korrekt, kommentiert, echt, rechtzeitig
Programmiersprachen	Unter anderem C/C++ und Java
Vorbesprechung	Freitag, 19.4.2002, 10.00 - 11.30 Uhr im S2229 mit folgenden Themen: Gruppeneinteilung Details zur Abgabeprozedur Erstes Warm Up Aufgabenblatt

Hintergrund

Die Association for Computing Machinery (ACM) ist Veranstalter des bekannten ACM Programming Contest. Dabei treten Teams aus verschiedenen Ländern gegeneinander an. Die Teams bekommen eine Menge von Programmieraufgaben gestellt, die so schnell wie möglich gelöst werden sollen. Dasjenige Team, das die meisten Aufgaben in kürzester Zeit löst gewinnt. Die Entscheidung, ob eine Aufgabe korrekt gelöst wurde wird von einem Online Judge getroffen. Der Judge testet das Programm auf gewissen Eingaben, wobei auch besonders die Randbedingungen getestet werden. Nach dem Test wird das Programm entweder akzeptiert oder abgelehnt. Mögliche Antworten des Judge sind dabei: Accepted, Presentation Error, Wrong Answer, Compile Error, Time Limit Exceeded, Memory Limit Exceeded und einige Weitere.

Inhalt und Durchführung

Aufgaben des Praktikums

Die Aufgaben stammen aus früheren ACM Programming Contests. Inhaltlich lassen sich die Aufgaben, die wir stellen werden grob in die Bereiche Geometrie, Zeichenreihen, Kombinatorik, Spiele und Puzzles, Zahlentheorie und Netzwerke einteilen.

Im Laufe des Semesters werden voraussichtlich 7 Aufgabenblätter zu bearbeiten sein, die unter http://wwwmayr.in.tum.de/lehre/2002SS/progprak/ heruntergeladen werden können bzw. bei den Besprechungsterminen verteilt werden.

Online Judge

An der Universidad de Valladolid wird ein Online Judge gehostet, mit dem die Aufgaben getestet werden können. Zur Benutzung des Online Judge beachte man das separate Merkblatt.

Scheinerwerb und Abgabe

Die Aufgaben sollen von Zweier- oder Einzelteams bearbeitet werden. Zum Testen steht der oben genannte Online Judge zur Verfügung. Wenn ein Team der Meinung ist, eine Aufgabe korrekt gelöst zu haben (z.B. wenn der Online Judge die Lösung akzeptiert), soll die Final Version des Programms per eMail an acmprakt@in.tum.de abgegeben werden.

Jede einzelne Lösung wird von der Praktikumsleitung durchgesehen und akzeptiert falls das Programm korrekt ist, ausreichend kommentiert und nicht abgeschrieben wurde.

Einzelteilnehmer bekommen einen Schein, wenn sie von jedem Aufgabenblatt die angegebene Mindestanzahl von Aufgaben korrekt und rechtzeitig gelöst haben.

Mitglieder von Zweiergruppen bekommen einen Schein, wenn sie von jedem Aufgabenblatt die angegebene Mindestanzahl von Aufgaben korrekt und rechtzeitig gelöst haben. Zusätzlich müssen noch fünf weitere Aufgaben gelöst werden, die frei wählbar sind und keinem Abgabetermin unterliegen.

Abgabetermine sind jeweils auf den Aufgabenblättern vermerkt. In begründeten Fällen kann die Abgabe maximal fünf Tage später erfolgen. Sollten bis dahin weniger als die entsprechende Mindestzahl an Aufgaben gelöst worden sein, gilt das Aufgabenblatt als nicht bestanden und der Scheinerwerb ist dann nicht mehr möglich.

Besprechungstermin und Lernziele

Jeden Freitag zwischen 10.00 und 11.30 Uhr gibt es eine (optionale) Vorbesprechung, in der die neuen Aufgaben erläutert und einige Techniken, die zur Lösung hilfreich sein könnten vorgestellt werden. Es werden aber keine Tipps, die die Aufgaben an sich betreffen verraten, sondern nur allgemeine Programmiertechniken erläutert. Mit dieser Vorgehensweise wollen wir folgende Lernziele verfolgen:

Selbstständiges Verstehen und Bearbeiten einer genau spezifizierten Aufgabe.
Entwicklung von Lösungsansätzen (d.h. in diesem Fall Lösungsalgorithmen) und deren Umsetzung in eine Programmiersprache.
Sorgfalt bei der Implementierung, da in der Praxis oft Fehler auftreten, die durch nicht abgedeckte Randbedingungen hervorgerufen werden.
Kennenlernen einiger allgemeiner Programmiertechniken (z.B. dynamisches Programmieren) und die Übertragung dieser auf ein konkretes Problem.

Schwierigkeitsgrad

Der Schwierigkeitsgrad der Aufgaben ist unterschiedlich und nimmt im Laufe des Semesters eher zu. Bei jedem Aufgabenblatt gibt es einige leichtere und einige schwerere Aufgaben, unter denen gewählt werden kann.

Programmiersprachen

Der Online Judge kann die Aufgaben in verschiedenen Sprachen bewerten; darunter auch C/C++ und Java. D.h. die Bearbeitung der Aufgaben ist an keine spezielle Programmiersprache gebunden, sondern hängt lediglich von den akzeptierten Sprachen des Judge ab.

Literatur

Cormen, Leiserson, Rivest. Introduction to Algorithms, MIT Press
Turau. Algorithmische Graphentheorie, Addison Wesley
Sedgewick. Algorithms, Addison-Wesley
The C++ Programming Language, Special Edition. von Bjarne Stroustrup, Addison Wesley
Die C ++ Programmiersprache. von Bjarne Stroustrup, Addison-Wesley
The C Programming Language. von Brian W. Kernigham, Dennis M. Ritchie, Prentice Hall
Programmieren in C. von Brian W. Kernighan, Dennis M. Ritchie
The Java Tutorial von Mary Campione, Kathy Walrath, Addison Wesley
JAVA als erste Programmiersprache. - vom Einsteiger zum Profi von Joachim Goll, Cornelia Weiß, Frank Müller, Teubner Verlag
Sun's Java Tutorial
Was Google zu Java hat.
Was Google zu C hat.

Programmier-Praktikum ACM Programming Contest (SS 2002)