Programmiertechnik II

Sommersemester 2012

Dr. Martin v. Löwis

Die mündlichen Prüfungen finden am 17.7., 18.7., 19.7., 26.7., 27.7., und vom 24.9.-28.9. statt.

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. 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

1. Übersicht (11.04.2012 10:54:15)
2. C (11.04.2012 10:54:38)
3. Repräsentation von Objecten (24.04.2012 14:57:58)
4. Freispeicherverwaltung (24.04.2012 14:58:46)
5. Polymorphie und spätes Binden (26.04.2012 10:49:56) (macro1.c, macro2.c, funcptr.c)
6. Automatische Speicherverwaltung (10.05.2012 11:16:54)

Praktikumsaufgaben

1. Aufgabe

Abgabetermin: 8. Mai (17:00 UTC)

Punktzahl: 20P

1. Machen Sie sich mit dem Editor /usr/bin/vim vertraut
2. Richten Sie in Ihrem Browser ein exportierbares DFN-Zertifikat ein sofern Sie nicht bereits ein solches Zertifikat installiert haben.
3. Melden Sie sich beim Abgabesystem für die Übungsaufgaben an
4. 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.
5. 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.
6. 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: 22. Mai (17:00 UTC)

Punktzahl: 20P

1. Machen Sie sich mit dem Debugger /usr/bin/gdb vertraut
2. 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. Achten Sie darauf, dass Ihre Lösung auf die gleiche Art wie das C++-Programm um neue Typen von Ausdrücken erweiterbar ist.
3. 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).
4. Senden Sie Ihre Lösung in Form eines gzip-komprimierten Tarfiles ein.
5. 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.