1 Aufgabenplaner (9 Punkte)

Übungen zu Praktische Informatik 2
SS 2001
Übung 3
Name:
Tutor:
Matrikelnummer:
Punkte:
Gruppe:
Abzugeben bis:
Do, 17. 5. 2001, 12:00
1 Aufgabenplaner (9 Punkte)
Es sollen Aufgaben verwaltet werden. Eine Aufgabe (Job) ist gekennzeichnet durch einen
Namen, eine Dauer (in Stunden), einen Fertigstellungstermin (siehe Klassen Calendar,
GregorianCalendar und Date in der Java Dokumentation) und eine Priorität (niedrig,
mittel, hoch).
Die Reihenfolge der Abarbeitung (=> Ordnung) der Aufgaben soll durch den Fertigstellungstermin definiert sein. Haben zwei Aufgaben den selben Fertigstellungstermin, hat die Aufgabe
mit der höheren Priorität Vorrang. Ist auch die Priorität gleich, wird die kürzere Aufgabe zuerst gereiht.
public class Job {
// All non-public variables, methods, ... must be private
public static final int PRIO_LOW = 0, PRIO_MIDDLE = 1, PRIO_HIGH = 2;
public Job(String name, double duration,
Date deadline, int priority) { … }
// Compares two Jobs (like defined order above)
public int compareToJob(Job otherJob) { … }
public ... get{Name, Duration, Deadline, Priority}() { … }
public void printJob() { … }
}
Der Aufgabenplaner selbst soll folgende öffentliche Schnittstelle haben:
public class JobPlanner {
public JobPlanner() { … }
// Add a new job
public void addJob(Job newJob) { … }
// Next job to do
public boolean hasNextJob() { … }
public Job getNextJob() { … }
public Job removeNextJob() { … }
public Job postponeNextJob(Date newDeadline, int newPriority) { … }
// Find (reorder, remove) a job by its name
public Job findJob(String name) { … }
public Job reorderJobByName(String jobName, double newDuration,
Date newDeadline, int newPriority) { … }
public Job removeJobByName(String jobName) { … }
// Print all jobs (not ordered, as you like)
public void printAllJobs() { … }
}
Verwenden Sie als interne Datenstruktur für den Aufgabenplaner einen Heap.
Verwenden Sie das auf der Übungsseite im Internet zur Verfügung gestellte Testprogramm
(JobPlannerTest.java) für einen Ihrer abzugebenden Tests (=> Schnittstellen einhalten!). Halten Sie diese Tests für ausreichend? Wenn nein, was fehlt Ihrer Meinung nach?
Hinweis: Sie können für den Heap statt einem Array auch die Klasse java.util.Vector verwenden. Implementieren Sie den Heap aber keinesfalls als Baum (Das ist nicht Sinn der Sache)!
Hinweis: <postponeNextJob> und <reorderJobByName> erzeugen jeweils ein neues JobObjekt (dieses wird auch zurückgegeben).
2 Graphen (6 Punkte)
Gegeben seien folgende Datenstrukturen:
• Turingband als doppelt verkettete, lineare Liste (wie in Übung 1 Aufgabe 3)
• Ein Heap (wie in Übung 3 Aufgabe 1)
• Modell des Strassennetzes von Linz (Kreuzungen => Knoten, Straßen => Kanten), wie
man es (sinnvoll) für die Simulation des Straßenverkehrs benutzen könnte
• Modell des natürlichen Wasserflusses in der Donau (d.h. Donau und deren Zuflüsse).
• Modell der Gänge, Stiegen und Lifte in den Gebäuden der Linzer Uni um die Erreichbarkeit aller Räume unter verschiedenen Gesichtspunkten (z.B. Rollstuhlfahrer, ...)
ermitteln zu können.
• Modell des Straßennetzes für Überlandverbindungen in der EU (d.h. Städte und Orte
können als je ein Knoten modelliert werden).
Stellen diese Datenstrukturen (im Modell) Graphen dar? Wenn nein, warum nicht?
Wenn ja, kategorisieren Sie diese Graphen nach gerichteter/ungerichteter, gewichteter/ungewichteter, vollständiger/nicht vollständiger, zyklischer/azyklischer und zusammenhängender/unzusammenhängender Graph. Begründen Sie jeweils Ihre Entscheidungen.
Hinweis: Es ist nicht so wichtig, wie Sie die einzelnen Datenstrukturen kategorisieren (nicht
immer eindeutig, manchmal von der Sichtweise und der Detailtreue des Modells abhängig).
Viel wich tiger ist die Begründung für Ihre Kategorisierung. Ohne Begründung gibt es daher
auch keine Punkte.
3 Darstellung von Graphen (9 Punkte)
Gegeben sei ein gerichteter, ungewichteter Graph. Die Knoten seien von 0 bis n-1 durchnummeriert. Um einen solchen Graphen darstellen zu können sind (u.a.) zwei Darstellungsformen
sehr gut geeignet: Adjazenzliste (Nachteil: benötigt viel Speicher bei vielen Kanten) und Adjazenzmatrix (Nachteil: benötigt viel Speicher bei wenigen Kanten). Wegen dieser Nachteile
im Speicherbedarf ist es empfehlenswert die aktuell günstigste Darstellungsform zu nehmen.
Implementieren Sie folgenden Graphen:
public class Graph {
private static int TYPE_ADJ_LIST = 0, int TYPE_ADJ_MATRIX = 1;
private int graphType; // TYPE_ADJ_...
private int nOfNodes, nOfEdges;
... // Data structures for two different representations
public Graph(int numberOfNodes) { … }
public boolean hasEdge(int fromNode, int toNode) { … }
public void setEdge(int fromNode, int toNode) { … }
public void removeEdge(int fromNode, int toNode) { … }
public int getNumberOfEdges() { … }
public int getNumberOfNodes() { … }
// Print all edges (in a readable format) and the current graph-type
public void printAll() { … }
}
Benutzen Sie für die Darstellung der Adjazenzmatrix ein Array of java.util.BitSet.
Überlegen Sie sich eine sinnvolle Bedingung bei der die interne Darstellung des Graphen automatisch umgewandelt werden sollte (=> minimaler Speicherbedarf).
Geben Sie beim Konvertieren der Darstellungsform eine entsprechende Testausgabe aus (Bitte mit abgeben). Verwenden Sie außerdem das auf der Übungsseite im Internet zur Verfügung
gestellte Testprogramm (GraphTest.java) für einen Ihrer abzugebenden Tests (=> Schnittstellen einhalten!). Halten Sie diese Tests für ausreichend? Wenn nein, was fehlt Ihrer Meinung
nach?