Programmiertechnik II

Sommersemester 2006

Dr. Martin v. Löwis

Die Prüfung findet in Raum A-1.2 statt.

Die Anmeldung zur Prüfung ist nicht mehr online möglich; Termine müssen mit Dr. v. Löwis oder Frau Wagner abgesprochen werden.

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 10. 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: 10. 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: 24. 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: 7. Juni (17:00 GMT)

Punktzahl: 20P

Gegeben sind zwei Programme zur Berechnung perfekter Zahlen, perfect.c und perfect.java. Bestimmen Sie die Komplexität des verwendeten Algorithmus' empirisch und theoretisch.

Zur empirischen Analyse:

Ändern Sie die Programme so, dass die Zahlen im Intervall bis 1000, 2000, 10000, 100000, 1000000, 10000000 ausgerechnet werden.
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 count_perfect_numbers.
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.Bestimmen Sie dazu die Zahl der Modulo-Operationen in Abhägigkeit von n. Vergleichen Sie die theoretischen und die experimentellen Ergebnisse.
Legen Sie Ihre Lösung in Ihrem Subversion-Repository ab, und geben Sie im Abgabgesystem den URL Ihrer Lösung ab. Verwenden Sie Text- oder PDF-Dateien für Ihre Protokolle und Analysen; geben Sie zusätzlich die geänderten Quelltextdateien ab.

4. Aufgabe

Abgabgetermin: 21. Juni (17:00 GMT)

Punktzahl: 20P

Gegeben ist die folgende Schnittstelle zur Darstellung einstelliger Prädikate:

package pt2;

public interface UnaryPredicate
  /* Return true if the predicate holds for anObject. */
  boolean holdsFor(Object anObject);

Entwickeln Sie eine Iterator-Implementierung Retain, die für einen gegebenen Iterator i und ein gegebenes UnaryPredicate-Exemplar p alle Objekte o aus i liefert, für die p gilt. Retain soll über folgenden Konstruktor verfügen:
```
public Retain(java.util.Iterator i, pt2.UnaryPredicate p);
```
Entwickeln Sie eine weitere Iterator-Implementierung LineIterator, die, der Reihe nach, alle Zeilen einer Datei liefert; die Datei ist wahlweise durch ihren Namen oder eine Reader-Referenz gegeben:
```
public LineIterator(String filename);
public LineIterator(Reader r);
```
Testen Sie Ihre Implementierungen, indem Sie einen JUnit-Testfall formulieren, der folgendes überprüft: In der Datei UnaryPredicate.java gibt es genau eine Zeile, in der runde Klammern vorkommen.
Vervollständigen Sie Ihre Testsuite derart, dass jede implementierte Methode in wenigstems einem Testfall aufgerufen wird.
Legen Sie Ihre Lösung in Ihrem Subversion-Repository ab, und tragen Sie im Abgabesystem einen Verweis auf die Lösung ein.

Hinweise:

Es steht Ihnen frei, die Iteratoren als parametrisierte Typen zu implementieren. Dokumentieren Sie die minimal erforderliche Java-Version zur Ausführung der Testfälle, sowie die minimal erforderliche JUnit-Version.
Zur zeilenweisen Verarbeitung einer Datei können Sie die Klasse BufferedReader verwenden.
Beachten Sie, dass Retain.hasNext nur true liefern darf, wenn es tatsächlich weitere Elemente gibt.
Einschränkungen an die Verwendung von Iteratormethoden müssen dokumentiert werden; bei Verletzung der Einschränkungen sollen geeignete Ausnahmen ausgelöst werden.

5. Aufgabe

Abgabgetermin: 5. 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.
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: 19. 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.