Programmiertechnik II
Sommersemester 2009
Dr. Martin v. Löwis
Die Prüfungen finden am 27.7. und 28.7. in C-1.7 statt und an allen anderen Tagen in A-1.2. Falls Sie Ihren Prüfungstermin absagen oder ändern müssen, wenden Sie sich an Frau Wagner.
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 8. 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
- Übersicht (22.04.2009 15:36:01)
- C (22.04.2009 15:36:29)
- Repräsentation von Objecten (07.05.2009 14:46:22)
- Freispeicherverwaltung (07.05.2009 14:46:51)
- Polymorphie und spätes Binden (25.05.2009 11:32:55)
- Automatische Speicherverwaltung (29.05.2009 08:55:57)
- Weitere Konzepte (29.05.2009 08:58:10)
- Analyse von Algorithmen (29.05.2009 19:54:21)
- Datentypen in Java (05.06.2009 11:27:09)
- Modultests (05.06.2009 10:59:33)
- Sortieren: Einfache Algorithmen (12.06.2009 11:40:22)
- Sortieren: Quicksort und Mergesort (24.07.2009 16:36:37)
- Sortieren: Priority Queues and Heapsort (15.06.2009 14:19:38)
- Sortieren: Radixsort (19.06.2009 11:52:27)
- Bäume (19.06.2009 11:51:37)
- Hash-Tabellen (19.06.2009 11:49:47)
- Code-Durchsicht (26.06.2009 08:53:38)
- Prolog (02.07.2009 19:18:09)
- Graph-Algorithmen (17.07.2009 12:34:21)
- Zufallszahlen (17.07.2009 10:35:25)
Praktikumsaufgaben
1. Aufgabe
Abgabetermin: 15. Mai (17:00 UTC)
Punktzahl: 20P
- Machen Sie sich mit dem Editor /usr/bin/vim vertraut
- Richten Sie in Ihrem Browser ein exportierbares DFN-Zertifikat ein. Die HPI-CA hat für diese Veranstaltung zu folgenden Zeiten geöffnet:
- Fr 24.4. 12:30-13:30
- Mo 27.4. 12:30-13:00
- Di 28.4. 12:30-13:30
- Di 28.4. 17:00-18:30
- Mi 29.4. 12:30-13:30
- Do 30.4. 12:30-13:30
- Melden Sie sich beim Abgabesystem 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.
- Zusatzaufgabe:Erweitern Sie Ihre Speicherverwaltung auf
mehrere Arena-Blöcke; verwenden Sie dazu sbrk(2) (wahlweise
mmap(2)), um vom Betriebssystem weiteren Speicher anzufordern. Zur Verwaltung
der verschiedenen Arenas wird eine einfach-verkettete Liste empfohlen.
2. Aufgabe
Abgabetermin: 2. Juni (17:00 UTC)
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).
- Senden Sie Ihre Lösung in Form eines gzip-komprimierten Tarfiles ein.
- Zusatzaufgabe:Erweitern Sie Ihre Lösung um ein Konstrukt instanceof(e, T), welches für
einen Ausdruck e überprüft, ob er ein Exemplar des Typs T oder eines Subtyps von T ist. Beispielsweise
sollten in main() instanceof(p, Binary) und instanceof(p, Plus) gelten, instanceof(p, Number) aber
nicht. Hinweis: Zur Berücksichtigung der Vererbung eignen sich virtuelle Funktionen.
3. Aufgabe
Abgabgetermin: 12. Juni (17:00 UTC)
Punktzahl: 20P
Gegeben sind zwei Programme zur Primzahlensuche,
prime.c (auf Basis von GMP)
und prime.java.
Bestimmen Sie die Komplexität des Primzahltests empirisch und theoretisch.
Zur empirischen Analyse:
- Ändern Sie die Programme so, dass Primzahlen ab 10**N, mit N = 12, 13, 14 usw. gesucht
werden. Brechen Sie ab, wenn die Laufzeit mehrere Minuten beträgt.
- 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.
- 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.
Bestimmen Sie außerdem, ob die folgenden Aussagen wahr sind.
Beweisen Sie die wahren Aussagen.
- O(100*N2) ⊂ O(N3)
- 10*N+20 ∈ O(N)
- N3/2 ∈ O(N log N)
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.
Zusatzaufgabe: Messen Sie für das C-Programm auch die
Zahl der Takte, die zur Berechnung benötigt werden, mithilfe
der x86-Anweisung rdtsc.
4. Aufgabe
Abgabgetermin: 26. Juni (17:00 UTC)
Punktzahl: 20P
Implementieren Sie die folgende Schnittstelle, die den
abstrakte Deque (Doule-Ended QUEue) repräsentiert, zwei Mal:
package de.uni_potsdam.hpi;
public interface Deque{
int capacity();
int size();
void clear();
void addFirst(Object e) throws DequeFull;
void addLast(Object e) throws DequeFull;
Object removeFirst() throws DequeEmpty;
Object removeLast() throws DequeEmpty;
}
Eine Klasse, die die Schnittstelle Deque implementiert, soll dabei
folgende Eigenschaften besitzen:
- Der Konstruktor der Klasse erwartet die maximale Kapazität des
Deque-Exemplars. Die Methode
capacity()
gibt diese Größe
zurück.
- Mit der Methode
addLast(Object)
wird ein Element in die
Warteschlange am Ende eingefügt. Falls die Kapazität bereits erreicht
ist, löst .addLast die Ausnahme de.uni_potsdam.hpi.DequeFull
aus. Gleichermaßen fügt addFirst am Anfang ein.
- Die Methode
removeFirst()
liefert das erste Elemente der
Warteschlange und entfernt es aus dieser. Sollte die Warteschlange
leer sein, so löst .removeFirst die Ausnahme
de.uni_potsdam.hpi.DequeEmpty
aus. Gleichermaßen
löscht removeLast ein Element am Ende.
- 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 Deque zum einen als doppelt 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. Alternativ ist es auch erlaubt,
erstes und letztes Element der List miteinander zu verbinden, ggf.
unter Einsatz eines Wächterelements.
- Implementieren Sie Deque 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 Deque q gilt nach q.addLast(o): o == q.removeFirst()
- Fügt man in eine Deque mit 7 Elementen eines mit addLast ein,
erhält man es mit removeLast sofort zurück
- Fügt man in eine Deque mit 7 Elementen eines mit addFirst ein,
erhält man es mit removeFirst sofort zurück
- Fügt man in eine Deque 6 mal den Wert null ein und danach
ein von null verschiedenes Objekt o, und führt danach wiederholt
removeFirst aus, so erhält man 6 mal den Wert null, und danach o.
- Nach Aufruf von .clear() liefert .size() den Wert 0.
- .removeLast liefert für eine leere Deque eine Ausnahme.
- .addFirst liefert für eine volle Deque eine Ausnahme.
Geben Sie im Abgabesystem ein Tarfile ab, welches sämtliche Klassen
im Quelltext sowie ein Ant-File enthält.
Das Ant-File soll Ihre Klassen übersetzen und die Testsuite ausführen.
Sie können für das ant-File davon ausgehen, dass sowohl
junit.jar als auch ant-junit.jar im Klassenpfad aufgeführt sind.
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.
Zusatzaufgabe: Ermitteln Sie mithilfe eines Analysewerkzeugs
(wie
Covertura,
Clover,
Quilt oder
NoUnit), wie vollständig
Ihre Testsuite ist, und vervollständigen Sie sie zu 100% Code-Abdeckung
(bezüglich des von Ihrem Werkzeug realisierten Messverfahrens).
5. Aufgabe
Abgabgetermin: 10. Juli (17:00 UTC)
Punktzahl: 20P
- Implementieren Sie eine Klasse für Priority-Queues auf Basis von
Heaps, die die Schnittstelle java.util.Queue derart implementiert, dass
bei .remove() immer das kleinste Objekt (bezüglich java.lang.Comparable)
zurückgegeben wird.
- Testen Sie Ihre Klasse, indem Sie in einem
Simulationsprogramm die Klasse PriorityQueue durch Ihre eigene Klasse
austauschen.
- Testen Sie Ihre Klasse weiterhin dadurch, dass Sie eine zufällige
Zahl von Zufallszahlen in die Queue einfügen und wieder aus der Queue
auslesen.
- Führen Sie eine Code-Durchsicht der Ihnen zugeteilten Teillösung von Aufgabe 4 durch.
- Zusatzaufgabe: Stellen Sie auch eine Implementierung von Heapsort auf
Basis Ihrer Heap-Implementierung bereit, bei der sowohl für die
Priority-Queue und den Sortieralgorithmus im Hintergrund der gleiche Code
zum Einsatz kommt.
6. Aufgabe
Abgabgetermin: 24. Juli (17:00 UTC)
Punktzahl: 20P
Über 4 Jungen im Alter von 11 bis 14 Jahren, die alle ein verschiedenes
Alter, verschiedene Wohnorte haben und unterschiedliche Hobbies haben, ist folgendes
bekannt:
- David wohnt in Berlin.
- Der Schachspieler ist jünger als der Mainzer.
- Alexander wohnt in Leipzig.
- Florian, der Klavier spielt, ist älter als David.
- Der Handballspieler ist ein Jahr älter als der Leipziger.
- Der Fussballspieler ist 11 Jahre alt.
- Lukas wohnt in Hamburg.
- Alexander ist 12.
- Lukas ist 13.
Formulieren Sie ein Prolog-Programm, welches aus diesen Aussagen für
jeden der Jungen ermittelt, in welcher Stadt er lebt, wie alt er ist und welches
Hobby er hat.
Hinweis: Jede Eigenschaft (Name, Alter, Wohnort, Hobby) kommt in der Lösung nur einmal vor.