Compilerbaupraktikum - Aufgabenblatt 1
Generelles
Allgemeine Hinweise
Für alle Praktikumsaufgaben gilt, dass Einsendungen, die nicht in der jeweils mitgegebenen Testumgebung laufen, mit null Punkten bewertet werden! Das beinhaltet insbesondere alle Programme, die sich nicht fehlerfrei kompilieren lassen. Als Testsystem werden wir dabei star mit den dort installierten Compilern und Compilerwerkzeugen benutzen. Prüfen Sie bitte rechtzeitig vor der Abgabe, ob ihr Programm auch dort lauffähig ist. Die Aussage „aber bei mir zuhause hat es funktioniert“ führt entgegen mancher Erwartungen nicht zur Punktevergabe.
Ebenfalls mit null Punkten werden alle Abgaben bewertet, die sich nicht exakt an die vorgegebenen Formate halten. Hier sollen insbesondere falsch gepackte Archive erwähnt werden (die nicht alle nötigen/die falschen/zu viele Dateien enthalten, eine falsche Verzeichnisstruktur besitzen, …). Kleiner Tipp (der bisher jedes Jahr von mindestens fünf Studenten ignoriert wurde): Vor der Abgabe einfach mal selbst das Archiv auspacken und nachsehen was drin ist.
Bei Fragen wenden Sie sich bitte an Ihren Praktikumsbetreuer während des Praktikums.
Sollten wir beim persönlichen Beantworten von Fragen feststellen, dass unsere Aufgabenstellung nicht präzise genug war, so werden wir einen konkretisierenden Eintrag in der Newsgroup erstellen. Zur Bewertung wird die Aufgabenstellung inklusive aller von uns erstellten Nachrichten in der Newsgroup herangezogen. Schauen Sie daher bitte ab und zu ebendort nach, ob sich die Aufgabenstellung inzwischen eventuell leicht geändert hat und ob ihre bereits fertige Lösung nochmal bearbeitet werden muss.
Abgabemodus
Die Abgabe erfolgt digital über das Goya-System. Die Lösung ist in einer Datei loesung.tar.gz verpackt abzugeben. In dieser tar.gz-Datei sollen ausschließlich die Dateien priorityQueue.c und priorityQueue.h (ohne irgendwelche Unterverzeichnisse!) enthalten sein.
Aufgabe 1 (80 Punkte)
Kurzbeschreibung
Implementieren Sie eine Prioritätswarteschlange in C, die beliebig viele Elemente speichern kann. Erweitern Sie dabei ein vorgegebenes Interface, so dass Ihre Warteschlange problemlos in andere (bereits existierende) Programme eingebunden werden kann.
Aufgabenstellung
Eine Prioritätswarteschlange ist eine Datenstruktur, die darauf optimiert ist Schlüssel-Daten-Paare in der Reihenfolge abzuarbeiten, die die Ordnung der Schlüssel vorgibt. Sowohl Stack als auch Queue sind Spezialfälle dieser Struktur (mit ab- bzw. aufsteigenden Schlüsseln). Das von Ihnen zu implementierende Interface sieht wie folgt aus:
-
priorityQueue* newPriorityQueue()
liefert einen Zeiger auf eine neue Prioritätswarteschlange
-
priorityQueueEntry priorityQueueInsert(priorityQueue* queue, int key, void* data)
fügt ein neues Schlüssel-/Daten-Paar in die Queue ein und gibt einen eindeutigen Identifikator für das Tupel in der internen Struktur zurück. Der Zeiger data muss verschieben zum null-Zieger sein, da dieser als Rückgabewert der Funktion priorityQueueExtract() eine leere Prioritätswarteschlange anzeigt
-
void priorityQueueDecreaseKey(priorityQueue* queue, priorityQueueEntry* entry, int newKey)
erlaubt die nachträgliche Modifikation des Schlüssels für einen Eintrag auf einen beliebigen, niedrigeren Wert; das entspricht einer Erhöhung der Priorität des Datums
die Variable, auf die entry zeigt, darf von der Funktion modifiziert werden
-
void* priorityQueueExtract(priorityQueue* queue)
entfernt das Element mit der höchsten Priorität (= dem kleinsten Schlüssel) und gibt es zurück. Enthält die Prioritätswarteschlange keine Elemente mehr, dass wird der null-Zeiger zurück gegeben
-
void deletePriorityQueue(priorityQueue* queue)
gibt den Speicher für die Queue an das Betriebssystem zurück
Als zugrundeliegende Datenstruktur möchten wir Ihnen den binären Min-Heap empfehlen, allerdings steht es Ihnen frei eine andere Datenstruktur zu nutzen, die eine vergleichbare Effizienz erreicht. Wir bitten Sie, von der Verwendung von einfachen sortierten Arrays bzw. Listenabzusehen, insbesondere weil diese eine schlechtere Effizienz besitzen. Zur Veranschaulichung der Funktionsweise des binären Min-Heaps dient dieses Java-Applet.
Achten Sie bei Ihrer Implementation ferner darauf, illegale Benutzereingaben soweit wie möglich abzufangen und das Programm mit einer sinnvollen Fehlermeldung sauber zu beenden. Sie dürfen dafür Assertions verwenden.
Aufgabe 2 (20 Punkte)
Kurzbeschreibung
Analysieren Sie die asymptotische Laufzeit der Funktionen, die Sie implementiert haben.
Aufgabenstellung
Da Sie die Landau-Notation bereits kennengelernt haben sollten, möchten wir von Ihnen, dass Sie die Effizienz der von Ihnen entwickelten Datenstruktur einschätzen. Ihre Analyse muss für einen Informatiker nachvollziehbar richtig sein, was bedeutet, dass Sie Ihre Aussagen nicht beweisen müssen. Sie dürfen die Analyse direkt im Quellcode in Form von Kommentaren vornehmen.
Ein Beispiel:
void foo(unsigned int n)
{
/* O(1) */
float* array = malloc(n * sizeof(float));
/* O(n) */
for (unsigned int i = 0; i < n; ++i)
{
/* O(1) */
array[i] = i;
}
/* Gesamtlaufzeit: O(1) + O(n) = O(n) */
}