Programmiertechnik II

Sommersemester 2007

Dr. Martin v. Löwis

Die Prüfungen finden in den Wochen vom 30.7.-3.8. (Raum A-1.2) und vom 24.9.-28.9. (Raum A-E.7) statt.

Am 16.7. bietet Paul Bouche um 17:00 einen zusätzlichen Konsultationstermin zu den Übungen im Hörsaal 3 an.

Die Lehrveranstaltung vermittelt Theorie und Praxis der Programmierung von Software am Beispiel der Sprachen C, Java und Prolog.

Diskutiert werden Algorithmen und Datenstrukturen zum Sortieren und Suchen, Graphenalgorithmen, Algorithmen und Datenstrukturen zur Implementierung objekt-orientierter Sprachen sowie die deklarative Programmierung. Diese Inhalte werden im allgemeineren Kontext der Softwareproduktion eingebettet.

Die Leistungserfassung besteht aus einer mündlichen Prüfung und der semesterbegleitenden Bearbeitung der Übungsaufgaben; Abgabetermin für die erste Serie von Übungsaufgaben ist der 7. Mai. Zur Zulassung zur mündlichen Prüfung muss die Hälfte der Punkte aus den Übungsaufgaben erreicht werden; die Note wird in der mündlichen Prüfung festgelegt.

Vorlesungen

Praktikumsaufgaben

1. Aufgabe

Abgabetermin: 7. Mai (17:00 GMT)

Punktzahl: 20P

Machen Sie sich mit dem Editor /usr/bin/vim vertraut
Richten Sie in Ihrem Browser ein exportierbares Zertifikat ein
Melden Sie sich beim Abgabesystem (Dienst mittlerweile außer Betrieb) für die Übungsaufgaben an
Implementieren Sie eine Freispeicherverwaltung mit der Schnittstelle
```
/* allocate.h */
void* allocate();
void deallocate(void *data);
```
die den Speicher aus einem festen Speicherblock entsprechend der Deklarationen
```
#define BLOCKSIZE 40
#define NUM_BLOCKS 1024
extern unsigned char arena[BLOCKSIZE*NUM_BLOCKS];
extern unsigned short allocated_map[NUM_BLOCKS/16];
```
erhält; verwenden Sie zu Ihrer Lösung die Bibliothek libarena. Die Funktion allocate() alloziert Blöcke fester Größe (BLOCKSIZE); die Funktion deallocate() gibt diese Blöcke wieder frei. Falls alle Blöcke alloziert sind, gibt allocate() als Ergebnis 0. Das Feld allocated_map speichert mit einem Bit pro Block, welche Blöcke alloziert sind.
Senden Sie Ihre Lösung in Form eines einzelen gzip-komprimierten Tarfiles ein. Dieses sollte im Wurzelverzeichnis ein Makefile haben, mit zwei Zielen "liballocate.a" und "testapp" (basierend auf testapp.c). Gehen Sie in Ihrer Lösung davon aus, dass die Makefile-Variable LIBARENA das Verzeichnis angibt, in dem sich libarena.a und arena.h befinden.

2. Aufgabe

Abgabetermin: 23. Mai (17:00 GMT)

Punktzahl: 20P

Machen Sie sich mit dem Debugger /usr/bin/gdb vertraut
Gegeben sei ein C++-Programm zur Manipulation, Darstellung und Berechnung von Ausdrücken. Übertragen Sie dieses Programm in ein struktur-ähnliches C-Programm; gehen Sie dazu von beiliegendem Gerüst aus.
Generieren Sie mittels /usr/bin/script eine Abschrift einer Debugger-Sitzung, aus der Ausschnitte aus dem Ablauf Ihres Programms ersichtlich werden (wie etwa die Berechnung des Ausdrucks).
Legen Sie die Quelldateien Ihrer Lösung in Ihrem Subversion-Repository ab und reichen Sie im Abgabesystem den URL zu Ihrer Lösung ein.

3. Aufgabe

Abgabgetermin: 6. Juni (17:00 GMT)

Punktzahl: 20P

Gegeben sind zwei Programme zur Matrizenmultiplikation, multiply.c und multiply.java. Bestimmen Sie die Komplexität der Multiplikation empirisch und theoretisch.

Zur empirischen Analyse:

Ändern Sie die Programme so, dass Matrizen der Größen 10, 20, 30, 40, 50, 100, 500, 1000 Eingabe sind.
Verwenden Sie einerseits das Programm /usr/bin/time zur Ermittlung der Gesamtlaufzeit, und andererseits die C-Funktion clock(3) und die Java-Methode java.lang.System.currentTimeMillis() zur Ermittlung der Laufzeit von mult.
Protokollieren Sie Ihre Experimente; geben Sie im Protokoll alle für die Messung relevanten Einflussparameter an.
Stellen Sie die Gesamtergebnisse tabellarisch oder graphisch dar.

Zur theoretischen Analyse bestimmen Sie die Komplexitätsklasse der verwendeten Algorithmen, und erläutern Sie Ihre Analyse. Vergleichen Sie die theoretischen und die experimentellen Ergebnisse.

Geben Sie Ihre Lösung in Form eines Tarfiles ab, das einerseits Ihre Protokolle und Analysen als Text- oder PDF-Datei enthält und andererseits Anhänge zu den Protokollen, wie etwa modifizierten Quelltextdateien.

4. Aufgabe

Abgabgetermin: 20. Juni (17:00 GMT)

Punktzahl: 20P

Implementieren Sie die folgende Schnittstelle, die eine abstrakte Warteschlange repräsentiert, zwei Mal:

package de.uni_potsdam.hpi;
public interface Queue
  int capacity();
  int size();
  void clear();
  Object get() throws QueueEmpty;
  void put(Object o) throws QueueFull;

Eine Klasse, die die Schnittstelle Queue implementiert, soll dabei folgende Eigenschaften besitzen:

Der Konstruktor der Klasse erwartet die maximale Kapazität des Queue-Exemplars. Die Methode capacity() gibt diese Größe zurück.
Mit der Methode put(Object) wird ein Element in die Warteschlange am Ende eingefügt. Falls die Kapazität bereits erreicht ist, löst .put die Ausnahme de.uni_potsdam.hpi.QueueFull aus.
Die Methode get() liefert das erste Elemente der Warteschlange und entfernt es aus dieser. Sollte die Warteschlange leer sein, so löst .get die Ausnahme de.uni_potsdam.hpi.QueueEmpty aus.
Die Methode size() liefert die aktuelle Zahl von Elementen in der Warteschlange.
Die Methode clear() löscht alle Elemente aus der Warteschlange.

Achten Sie bei Ihrer Implementierung darauf, dass alle Methoden die Komplexität O(1) besitzen (vorausgesetzt, dass alle Elementaroperationen, einschließlich der Speicherallozierung, in konstanter Zeit erfolgen).

Implementieren Sie Queue zum einen als einfach verkettete Liste. Zur Erreichung konstanter Zeit für alle Operationen empfiehlt es sich, eine Referenz nicht nur auf den Anfang der Liste, sondern auch auf das Ende der Liste zu führen.
Implementieren Sie Queue zum anderen als Ringpuffer auf Basis eines Arrays. Für einen solchen Ringpuffer sind neben dem Array selbst zwei Integer-Variablen (etwa first und last) erforderlich, die den ersten und den letzten belegten Index anzeigen.
Vergleichen Sie die Laufzeit beider Implementierungen für folgendes Anwendungsszenario: In eine Warteschlange der Kapazität 1000 werden 500 Elemente eingefügt, danach wird oft abwechselnd ein Element entfernt und der Leerstring ("") eingefügt; vergleichen Sie insbesondere die Zeit für dieses Einfügen und Entfernen.
Schreiben Sie auf Basis von JUnit eine Sammlung von Testfällen für Ihre Klassen, die wenigstens die folgenden Eigenschaften testet:
- Für eine leere Queue q gilt nach q.put(o): o == q.get()
- Fügt man in eine Queue 6 mal den Wert null ein und danach ein von null verschiedenes Objekt o, und führt danach wiederholt get aus, so erhält man 6 mal den Wert null, und danach o.
- Nach Aufruf von .clear() liefert .size() den Wert 0.
- .get liefert für eine leere Queue eine Ausnahme.
- .put liefert für eine volle Queue eine Ausnahme.

Legen Sie in Ihrem Subversion-Repository sämtliche Klassen im Quelltext sowie ein Ant-File ab, welches Ihre Klassen übersetzt und die Testsuite ausführt. Sie können für das ant-File davon ausgehen, dass sowohl junit.jar als auch ant-junit.jar im Klassenpfad aufgeführt sind.

Reichen Sie im Abgabesystem den URL zu Ihrer Lösung ein. Ihre Lösung wird in einer Folgeaufgabe zur Code-Durchsicht einigen Kommilitonen zur Verfügung gestellt. Achten Sie darauf, dass aus Ihrem Code Ihre Autorenschaft möglichst nicht hervorgeht.

5. Aufgabe

Abgabgetermin: 4. Juli (17:00 GMT)

Punktzahl: 20P

Implementieren Sie eine stabile Version von Quicksort für verkettete Listen. Verwenden Sie zum Vergleichen die Annahme, dass die Elemente in der Liste java.lang.Comparable konsistent implementieren. Verzichten Sie dabei auf indexbasierte Zugriffe.
Testen Sie Ihren Algorithmus, in dem Sie eine zufällige Zahl von Zufallsexemplaren des Typs java.lang.Integer generieren und diese sortieren.
Entwickeln Sie eine Anwendung Ihres Sortierverfahrens, die die Standardeingabe zeilenweise sortiert und ausgibt.
Führen Sie eine Code-Durchsicht der Ihnen in unserem Online-Werkzeug (Dienst mittlerweile außer Betrieb) zugeteilten Teillösung zugeteilten Teillösung von Aufgabe 4 durch. Sollten bei dieser Zuteilung Probleme aufgetreten sein, wenden Sie sich bitte an Dr. v. Löwis.
Legen Sie Ihre Lösung in Ihrem Subversion-Repository ab, und tragen Sie im Abgabesystem einen Verweis auf die Lösung ein.

6. Aufgabe

Abgabgetermin: 17. Juli (17:00 GMT)

Punktzahl: 20P

Formulieren Sie ein Prolog-Programm, welches ein gegebenes Puzzle löst, und geben Sie Ihre Lösung im Abgabesystem ab.
Hinweis: Eine Lösung kann in Prolog beispielsweise als Liste von Nummern der Puzzlekarten und deren Orientierung dargestellt werden.