Abitur NRW Informatik 2022 · GK · Haupttermin

Aufgabenstellung: Buchungssystem für Schulveranstaltungen

An der Turing-Schule finden regelmäßig verschiedene Schulveranstaltungen statt (z. B. Schulmusical, Schultheater). Früher entstanden vor dem Einlass zu einer Veranstaltung zum Teil lange Warteschlangen.

Damit alle Beteiligten besser planen können, sollen Sitzplätze für eine Veranstaltung künftig vorab reservierbar sein. Deshalb wollen die Schülerinnen und Schüler des Informatikprojektkurses ein Buchungssystem für diese Veranstaltungen entwickeln.

Die Aula wird bewährterweise für jede Veranstaltung eigens bestuhlt. Die Stühle stehen dabei stets in Sitzplatzreihen, und innerhalb einer Veranstaltung hat jede Sitzplatzreihe dieselbe Anzahl an Stühlen.

Eine Person darf für eine Veranstaltung mehrere Sitzplätze reservieren. Ist eine Veranstaltung ausgebucht, kann sich die Person auf die Warteliste eintragen lassen, bei mehreren Platzwünschen auch mehrmals. Zu jeder Person wird die Telefonnummer gespeichert, allerdings nur, damit sie bei Absagen von Veranstaltungen schnell erreichbar ist.

Das folgende Implementationsdiagramm zeigt einen ersten Modellierungsentwurf zur Verwaltung der Veranstaltungen. Die Klassendokumentationen stehen im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Veranstaltungsverwaltung

Objekte der Klasse Veranstaltungsverwaltung verwalten Veranstaltungen.

Auszug aus der Dokumentation der Klasse Veranstaltungsverwaltung

Veranstaltungsverwaltung()

Ein Objekt der Klasse Veranstaltungsverwaltung wird initialisiert.

List<Veranstaltung> gibVeranstaltungen()

Eine Liste mit allen Veranstaltungen wird zurückgeliefert. Wenn keine Veranstaltung verwaltet wird, dann wird eine leere Liste zurückgegeben.

void fuegeHinzu(Veranstaltung pVeranstaltung)

Die im Parameter übergebene Veranstaltung wird hinzugefügt.

void reserviere(Veranstaltung pVeranstaltung, int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung pVeranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls für die entsprechende Veranstaltung an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert, pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

void schreibeAufWarteliste(Veranstaltung pVeranstaltung, Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung pVeranstaltung angehängt. Falls pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

Veranstaltung ermittleVeranstaltung(String pTermin, String pVeranstaltungsname)

Für den im Parameter übergebenen Termin und Veranstaltungsnamen wird das entsprechende Veranstaltungsobjekt zurückgeliefert. Falls es zu dem Termin keine Veranstaltung mit dem Namen gibt, wird null zurückgeliefert.

List<Veranstaltung> ermittleVeranstaltungen(int pMinFreiePlaetze)

Die Methode liefert eine Liste mit den Veranstaltungen zurück, bei denen mindestens so viele Plätze frei sind, wie es durch den im Parameter übergebenen Wert pMinFreiePlaetze vorgegeben wird. Wenn es keine Veranstaltung mit der Mindestzahl an freien Plätzen gibt, dann wird eine leere Liste zurückgegeben.

Die Klasse Veranstaltung

Objekte der Klasse Veranstaltung verwalten Termine, Veranstaltungsnamen und die Sitzplätze mit den entsprechenden Reservierungen der Personen.

Auszug aus der Dokumentation der Klasse Veranstaltung

Veranstaltung(String pTermin, String pVeranstaltungsname, int pAnzahlReihen, int pAnzahlPlaetzeProReihe)

Ein Objekt der Klasse Veranstaltung wird initialisiert mit dem Termin, dem Veranstaltungsnamen, der Anzahl der Sitzplatzreihen und der Anzahl der Plätze pro Reihe.

String gibTermin()

Der Termin der Veranstaltung wird zurückgeliefert.

String gibVeranstaltungsname()

Der Veranstaltungsname der Veranstaltung wird zurückgeliefert.

int gibAnzahlFreiePlaetze()

Die Anzahl der noch freien Plätze der Veranstaltung wird zurückgeliefert.

Person gibReservierung(int pReihe, int pSitz)

Das Personenobjekt mit einer Reservierung für den Platz (pReihe, pSitz) wird zurückgeliefert. Falls der Platz nicht reserviert ist, wird null zurückgeliefert.

void reserviere(int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert oder pPerson null ist, dann geschieht nichts.

void loescheReservierung(int pReihe, int pSitz)

Für die Veranstaltung wird die Reservierung für den Platz (pReihe, pSitz) gelöscht. Falls der Platz nicht existiert, dann geschieht nichts.

void schreibeAufWarteliste(Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung angehängt. Falls pPerson null ist, dann geschieht nichts.

void macheEtwas(Person pPerson)

Diese Methode ist Bestandteil der Teilaufgabe b).

Die Klasse Person

Objekte der Klasse Person verwalten einen Namen und eine Telefonnummer einer Person.

Auszug aus der Dokumentation der Klasse Person

Person(String pName, String pTelefonnummer)

Ein Objekt der Klasse Person wird initialisiert mit dem Namen und der Telefonnummer.

String gibName()

Der Name der Person wird zurückgeliefert.

String gibTelefonnummer()

Die Telefonnummer der Person wird zurückgeliefert.

boolean istGleich(Person pPerson)

Wenn das Personenobjekt inhaltlich mit dem im Parameter übergebenen Personenobjekt pPerson gleich ist, dann wird true zurückgeliefert und sonst false. Für die Inhaltsgleichheit müssen die jeweiligen Namen und Telefonnummern übereinstimmen.

Die generische Klasse Queue

Objekte der generischen Klasse Queue (Warteschlange) verwalten beliebige Objekte vom Typ ContentType nach dem First-In-First-Out-Prinzip, d. h., das zuerst abgelegte Objekt wird als erstes wieder entnommen. Alle Methoden haben eine konstante Laufzeit, unabhängig von der Anzahl der verwalteten Objekte.

Dokumentation der Klasse Queue<ContentType>

Queue()

Eine leere Schlange wird erzeugt. Objekte, die in dieser Schlange verwaltet werden, müssen vom Typ ContentType sein.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

void enqueue(ContentType pContent)

Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert.

void dequeue()

Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

ContentType front()

Die Anfrage liefert das erste Objekt der Schlange. Die Schlange bleibt unverändert. Falls die Schlange leer ist, wird null zurückgegeben.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe a)

a.1

Beschreiben Sie, wie die Klassen der in Abbildung 2 dargestellten Teilmodellierung miteinander in Beziehung stehen.

a.2

Begründen Sie anhand des Sachkontexts, weshalb die Datensammlungen der Warteliste sinnvollerweise als Schlange (Queue) umgesetzt werden.

a.3

Begründen Sie anhand des Sachkontexts, weshalb es sinnvoll ist, die Sitzplätze samt den zugehörigen Reservierungen der Personen als zweidimensionales Feld (Array) statt als dynamische Datenstruktur umzusetzen.

Teilaufgabe d)

Nach Absprache mit der Schulleitung wollen die Schülerinnen und Schüler ihr Projekt ausbauen. Zusätzlich sollen die folgenden Anforderungen erfüllt werden:

Zu jeder Veranstaltung soll eine E-Mail-Adresse für eventuelle Rückfragen hinterlegt sein. Diese Angabe soll ebenfalls abrufbar sein.

Künftig soll die Schule für jede Veranstaltung einen einheitlichen Eintrittspreis je Sitzplatz verlangen können. Dieser Preis soll hinterlegt werden. Sowohl der Eintrittspreis als auch die Summe der Eintrittsgelder, berechnet aus den Reservierungen, sollen ebenfalls abrufbar sein.

Zu jeder Person sollen die von ihr gebuchten Veranstaltungen hinterlegt sein. Diese Angabe soll ebenfalls abrufbar sein.

d.1

Modellieren Sie die zuvor genannten Anforderungen als Erweiterung des Implementationsdiagramms aus Abbildung 2.

Hinweis: Klassen, Klassenbeziehungen, Methoden und Attribute des Implementationsdiagramms aus Abbildung 2, die unverändert bleiben, brauchen nicht erneut aufgeführt zu werden. Zeichnen Sie Ihre Erweiterung des Modells und laden Sie ein Foto davon hoch.

d.2

Erläutern Sie, auf welche Weise Ihr Implementationsdiagramm die zweite und die dritte Anforderung umsetzt.

Aufgabenstellung: Buchungssystem für Schulveranstaltungen

An der Turing-Schule finden regelmäßig verschiedene Schulveranstaltungen statt (z. B. Schulmusical, Schultheater). Früher entstanden vor dem Einlass zu einer Veranstaltung zum Teil lange Warteschlangen.

Damit alle Beteiligten besser planen können, sollen Sitzplätze für eine Veranstaltung künftig vorab reservierbar sein. Deshalb wollen die Schülerinnen und Schüler des Informatikprojektkurses ein Buchungssystem für diese Veranstaltungen entwickeln.

Die Aula wird bewährterweise für jede Veranstaltung eigens bestuhlt. Die Stühle stehen dabei stets in Sitzplatzreihen, und innerhalb einer Veranstaltung hat jede Sitzplatzreihe dieselbe Anzahl an Stühlen.

Eine Person darf für eine Veranstaltung mehrere Sitzplätze reservieren. Ist eine Veranstaltung ausgebucht, kann sich die Person auf die Warteliste eintragen lassen, bei mehreren Platzwünschen auch mehrmals. Zu jeder Person wird die Telefonnummer gespeichert, allerdings nur, damit sie bei Absagen von Veranstaltungen schnell erreichbar ist.

Das folgende Implementationsdiagramm zeigt einen ersten Modellierungsentwurf zur Verwaltung der Veranstaltungen. Die Klassendokumentationen stehen im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Veranstaltungsverwaltung

Objekte der Klasse Veranstaltungsverwaltung verwalten Veranstaltungen.

Auszug aus der Dokumentation der Klasse Veranstaltungsverwaltung

Veranstaltungsverwaltung()

Ein Objekt der Klasse Veranstaltungsverwaltung wird initialisiert.

List<Veranstaltung> gibVeranstaltungen()

Eine Liste mit allen Veranstaltungen wird zurückgeliefert. Wenn keine Veranstaltung verwaltet wird, dann wird eine leere Liste zurückgegeben.

void fuegeHinzu(Veranstaltung pVeranstaltung)

Die im Parameter übergebene Veranstaltung wird hinzugefügt.

void reserviere(Veranstaltung pVeranstaltung, int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung pVeranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls für die entsprechende Veranstaltung an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert, pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

void schreibeAufWarteliste(Veranstaltung pVeranstaltung, Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung pVeranstaltung angehängt. Falls pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

Veranstaltung ermittleVeranstaltung(String pTermin, String pVeranstaltungsname)

Für den im Parameter übergebenen Termin und Veranstaltungsnamen wird das entsprechende Veranstaltungsobjekt zurückgeliefert. Falls es zu dem Termin keine Veranstaltung mit dem Namen gibt, wird null zurückgeliefert.

List<Veranstaltung> ermittleVeranstaltungen(int pMinFreiePlaetze)

Die Methode liefert eine Liste mit den Veranstaltungen zurück, bei denen mindestens so viele Plätze frei sind, wie es durch den im Parameter übergebenen Wert pMinFreiePlaetze vorgegeben wird. Wenn es keine Veranstaltung mit der Mindestzahl an freien Plätzen gibt, dann wird eine leere Liste zurückgegeben.

Die Klasse Veranstaltung

Objekte der Klasse Veranstaltung verwalten Termine, Veranstaltungsnamen und die Sitzplätze mit den entsprechenden Reservierungen der Personen.

Auszug aus der Dokumentation der Klasse Veranstaltung

Veranstaltung(String pTermin, String pVeranstaltungsname, int pAnzahlReihen, int pAnzahlPlaetzeProReihe)

Ein Objekt der Klasse Veranstaltung wird initialisiert mit dem Termin, dem Veranstaltungsnamen, der Anzahl der Sitzplatzreihen und der Anzahl der Plätze pro Reihe.

String gibTermin()

Der Termin der Veranstaltung wird zurückgeliefert.

String gibVeranstaltungsname()

Der Veranstaltungsname der Veranstaltung wird zurückgeliefert.

int gibAnzahlFreiePlaetze()

Die Anzahl der noch freien Plätze der Veranstaltung wird zurückgeliefert.

Person gibReservierung(int pReihe, int pSitz)

Das Personenobjekt mit einer Reservierung für den Platz (pReihe, pSitz) wird zurückgeliefert. Falls der Platz nicht reserviert ist, wird null zurückgeliefert.

void reserviere(int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert oder pPerson null ist, dann geschieht nichts.

void loescheReservierung(int pReihe, int pSitz)

Für die Veranstaltung wird die Reservierung für den Platz (pReihe, pSitz) gelöscht. Falls der Platz nicht existiert, dann geschieht nichts.

void schreibeAufWarteliste(Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung angehängt. Falls pPerson null ist, dann geschieht nichts.

void macheEtwas(Person pPerson)

Diese Methode ist Bestandteil der Teilaufgabe b).

Die Klasse Person

Objekte der Klasse Person verwalten einen Namen und eine Telefonnummer einer Person.

Auszug aus der Dokumentation der Klasse Person

Person(String pName, String pTelefonnummer)

Ein Objekt der Klasse Person wird initialisiert mit dem Namen und der Telefonnummer.

String gibName()

Der Name der Person wird zurückgeliefert.

String gibTelefonnummer()

Die Telefonnummer der Person wird zurückgeliefert.

boolean istGleich(Person pPerson)

Wenn das Personenobjekt inhaltlich mit dem im Parameter übergebenen Personenobjekt pPerson gleich ist, dann wird true zurückgeliefert und sonst false. Für die Inhaltsgleichheit müssen die jeweiligen Namen und Telefonnummern übereinstimmen.

Die generische Klasse Queue

Objekte der generischen Klasse Queue (Warteschlange) verwalten beliebige Objekte vom Typ ContentType nach dem First-In-First-Out-Prinzip, d. h., das zuerst abgelegte Objekt wird als erstes wieder entnommen. Alle Methoden haben eine konstante Laufzeit, unabhängig von der Anzahl der verwalteten Objekte.

Dokumentation der Klasse Queue<ContentType>

Queue()

Eine leere Schlange wird erzeugt. Objekte, die in dieser Schlange verwaltet werden, müssen vom Typ ContentType sein.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

void enqueue(ContentType pContent)

Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert.

void dequeue()

Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

ContentType front()

Die Anfrage liefert das erste Objekt der Schlange. Die Schlange bleibt unverändert. Falls die Schlange leer ist, wird null zurückgegeben.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe b)

In der Klasse Veranstaltung findet eine Schülerin die nicht dokumentierte Methode macheEtwas:

1 public void macheEtwas(Person pPerson) {

2 for (int r = 0; r < sitzplaetze.length; r++) {

3 for (int s = 0; s < sitzplaetze[r].length; s++) {

4 if (pPerson.istGleich(gibReservierung(r, s))) {

5 loescheReservierung(r, s);

6 Person neu = warteliste.front();

7 if (neu != null) {

8 reserviere(r, s, neu);

9 }

10 warteliste.dequeue();

11 }

12 }

13 }

14 }

Nehmen Sie an, die Methode macheEtwas wird für die in Abbildung 1 gezeigte Veranstaltung aufgerufen. Als Parameter pPerson dient dabei ein Personenobjekt mit dem Namen "Ada Lovelace" und der Telefonnummer "0231 191613".

Das Objekt warteliste sei folgendermaßen belegt:

b.1)

Analysieren Sie die Methode anhand dieser Belegungen und der Beispieldaten aus Abbildung 1 und erläutern Sie, wie die Methode funktioniert und wie sich dabei die Sitzplatzbelegung und die Warteliste verändern. [6 Punkte]

b.2)

Erläutern Sie, welchen Zweck die Methode im Sachzusammenhang erfüllt. [3 Punkte]

b.3)

Beurteilen Sie, ob sich die Zeilen 6 – 9 durch die folgende Zeile ersetzen ließen: [4 Punkte]

reserviere(r, s, warteliste.front());

Teilaufgabe c)

In die Klasse Veranstaltungsverwaltung soll eine Methode mit folgendem Methodenkopf aufgenommen werden:

public List<Veranstaltung> ermittleVeranstaltungen(int pMinFreiePlaetze)

Die Methode gibt eine Liste aller Veranstaltungen zurück, die mindestens so viele freie Plätze haben, wie der Parameter pMinFreiePlaetze verlangt. Erfüllt keine Veranstaltung diese Mindestzahl an Restplätzen, wird eine leere Liste zurückgegeben.

c.1)

Entwickeln und erläutern Sie für die Methode ermittleVeranstaltungen ein algorithmisches Verfahren. [5 Punkte]

c.2)

Implementieren Sie die Methode ermittleVeranstaltungen. [7 Punkte]

Aufgabenstellung: Buchungssystem für Schulveranstaltungen

An der Turing-Schule finden regelmäßig verschiedene Schulveranstaltungen statt (z. B. Schulmusical, Schultheater). Früher entstanden vor dem Einlass zu einer Veranstaltung zum Teil lange Warteschlangen.

Damit alle Beteiligten besser planen können, sollen Sitzplätze für eine Veranstaltung künftig vorab reservierbar sein. Deshalb wollen die Schülerinnen und Schüler des Informatikprojektkurses ein Buchungssystem für diese Veranstaltungen entwickeln.

Die Aula wird bewährterweise für jede Veranstaltung eigens bestuhlt. Die Stühle stehen dabei stets in Sitzplatzreihen, und innerhalb einer Veranstaltung hat jede Sitzplatzreihe dieselbe Anzahl an Stühlen.

Eine Person darf für eine Veranstaltung mehrere Sitzplätze reservieren. Ist eine Veranstaltung ausgebucht, kann sich die Person auf die Warteliste eintragen lassen, bei mehreren Platzwünschen auch mehrmals. Zu jeder Person wird die Telefonnummer gespeichert, allerdings nur, damit sie bei Absagen von Veranstaltungen schnell erreichbar ist.

Das folgende Implementationsdiagramm zeigt einen ersten Modellierungsentwurf zur Verwaltung der Veranstaltungen. Die Klassendokumentationen stehen im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Veranstaltungsverwaltung

Objekte der Klasse Veranstaltungsverwaltung verwalten Veranstaltungen.

Auszug aus der Dokumentation der Klasse Veranstaltungsverwaltung

Veranstaltungsverwaltung()

Ein Objekt der Klasse Veranstaltungsverwaltung wird initialisiert.

List<Veranstaltung> gibVeranstaltungen()

Eine Liste mit allen Veranstaltungen wird zurückgeliefert. Wenn keine Veranstaltung verwaltet wird, dann wird eine leere Liste zurückgegeben.

void fuegeHinzu(Veranstaltung pVeranstaltung)

Die im Parameter übergebene Veranstaltung wird hinzugefügt.

void reserviere(Veranstaltung pVeranstaltung, int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung pVeranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls für die entsprechende Veranstaltung an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert, pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

void schreibeAufWarteliste(Veranstaltung pVeranstaltung, Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung pVeranstaltung angehängt. Falls pVeranstaltung null ist oder pPerson null ist, dann geschieht nichts.

Veranstaltung ermittleVeranstaltung(String pTermin, String pVeranstaltungsname)

Für den im Parameter übergebenen Termin und Veranstaltungsnamen wird das entsprechende Veranstaltungsobjekt zurückgeliefert. Falls es zu dem Termin keine Veranstaltung mit dem Namen gibt, wird null zurückgeliefert.

List<Veranstaltung> ermittleVeranstaltungen(int pMinFreiePlaetze)

Die Methode liefert eine Liste mit den Veranstaltungen zurück, bei denen mindestens so viele Plätze frei sind, wie es durch den im Parameter übergebenen Wert pMinFreiePlaetze vorgegeben wird. Wenn es keine Veranstaltung mit der Mindestzahl an freien Plätzen gibt, dann wird eine leere Liste zurückgegeben.

Die Klasse Veranstaltung

Objekte der Klasse Veranstaltung verwalten Termine, Veranstaltungsnamen und die Sitzplätze mit den entsprechenden Reservierungen der Personen.

Auszug aus der Dokumentation der Klasse Veranstaltung

Veranstaltung(String pTermin, String pVeranstaltungsname, int pAnzahlReihen, int pAnzahlPlaetzeProReihe)

Ein Objekt der Klasse Veranstaltung wird initialisiert mit dem Termin, dem Veranstaltungsnamen, der Anzahl der Sitzplatzreihen und der Anzahl der Plätze pro Reihe.

String gibTermin()

Der Termin der Veranstaltung wird zurückgeliefert.

String gibVeranstaltungsname()

Der Veranstaltungsname der Veranstaltung wird zurückgeliefert.

int gibAnzahlFreiePlaetze()

Die Anzahl der noch freien Plätze der Veranstaltung wird zurückgeliefert.

Person gibReservierung(int pReihe, int pSitz)

Das Personenobjekt mit einer Reservierung für den Platz (pReihe, pSitz) wird zurückgeliefert. Falls der Platz nicht reserviert ist, wird null zurückgeliefert.

void reserviere(int pReihe, int pSitz, Person pPerson)

Für die Veranstaltung wird für den Platz (pReihe, pSitz) für die Person eine Reservierung vorgenommen. Falls an dem Platz bereits eine Reservierung vorliegt, dann wird diese überschrieben. Falls der Platz nicht existiert oder pPerson null ist, dann geschieht nichts.

void loescheReservierung(int pReihe, int pSitz)

Für die Veranstaltung wird die Reservierung für den Platz (pReihe, pSitz) gelöscht. Falls der Platz nicht existiert, dann geschieht nichts.

void schreibeAufWarteliste(Person pPerson)

Das Personenobjekt pPerson wird an die Warteliste für die Veranstaltung angehängt. Falls pPerson null ist, dann geschieht nichts.

void macheEtwas(Person pPerson)

Diese Methode ist Bestandteil der Teilaufgabe b).

Die Klasse Person

Objekte der Klasse Person verwalten einen Namen und eine Telefonnummer einer Person.

Auszug aus der Dokumentation der Klasse Person

Person(String pName, String pTelefonnummer)

Ein Objekt der Klasse Person wird initialisiert mit dem Namen und der Telefonnummer.

String gibName()

Der Name der Person wird zurückgeliefert.

String gibTelefonnummer()

Die Telefonnummer der Person wird zurückgeliefert.

boolean istGleich(Person pPerson)

Wenn das Personenobjekt inhaltlich mit dem im Parameter übergebenen Personenobjekt pPerson gleich ist, dann wird true zurückgeliefert und sonst false. Für die Inhaltsgleichheit müssen die jeweiligen Namen und Telefonnummern übereinstimmen.

Die generische Klasse Queue

Objekte der generischen Klasse Queue (Warteschlange) verwalten beliebige Objekte vom Typ ContentType nach dem First-In-First-Out-Prinzip, d. h., das zuerst abgelegte Objekt wird als erstes wieder entnommen. Alle Methoden haben eine konstante Laufzeit, unabhängig von der Anzahl der verwalteten Objekte.

Dokumentation der Klasse Queue<ContentType>

Queue()

Eine leere Schlange wird erzeugt. Objekte, die in dieser Schlange verwaltet werden, müssen vom Typ ContentType sein.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

void enqueue(ContentType pContent)

Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert.

void dequeue()

Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

ContentType front()

Die Anfrage liefert das erste Objekt der Schlange. Die Schlange bleibt unverändert. Falls die Schlange leer ist, wird null zurückgegeben.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls (hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt (hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt (hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt (hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false), bleibt die Liste unverändert.

e)

Wenn Veranstaltungen kurzfristig abgesagt wurden, ließen sich nicht immer alle Personen rechtzeitig per Telefon erreichen. Deshalb soll ausschließlich zur schnellen Erreichbarkeit bei Absagen von Veranstaltungen zusätzlich verpflichtend die E-Mail-Adresse jeder Person gespeichert werden.

Zudem reicht der Schulleiter bei der Projektgruppe eine E-Mail zur Überprüfung ein. Diese E-Mail enthält nur Hinweise auf künftige Schulveranstaltungen. Der Schulleiter begründet sein Anliegen damit, künftig jeden Monat eine solche E-Mail als Service an alle im Buchungssystem erfassten Personen zu schicken, weil diese sich ohnehin für die Schulveranstaltungen interessierten.

Begründen Sie unter Einbeziehung eines von Ihnen gewählten Grundprinzips des Datenschutzes, weshalb der Vorschlag des Schulleiters nicht umgesetzt werden sollte. (5 Punkte)

Sachkontext: Musikverwaltung mit Hashtags für DJ P.J.

Peter Johann tritt als beliebter Discjockey („DJ P.J.“) auf. Zu seinem Erfolg trägt bei, dass er die Stücke für seine Auftritte weniger nach Titel oder Interpret auswählt, sondern vor allem nach deren Beschreibungen und Merkmalen. Dazu nutzt er eine von ihm selbst entwickelte Software, die alle Musikstücke über sogenannte Hashtags verwaltet. Ein Hashtag ist ein Schlagwort, das ein Musikstück genauer charakterisiert. Jedem Musikstück ist mindestens ein Hashtag zugewiesen. Ein Hashtag beginnt stets mit genau einem Doppelkreuz (#), darauf folgt das beschreibende Schlagwort, das ausschließlich Buchstaben und Ziffern enthalten darf. Gültige Hashtags sind zum Beispiel #Rock, #Blues, #HipHop, #Uptempo140 oder #ChaChaCha, nicht aber #Rock#*Pop!.

Die Hashtags werden in einem binären Suchbaum verwaltet.

Peter hat den Entwurf seiner Software in Abbildung 1 festgehalten und dabei berücksichtigt, dass zu einem Hashtag mehrere Musikstücke gehören können.

Anlage: Beispieldaten

Der Suchbaum bibliothek der Klasse Musikverwaltung habe folgenden Inhalt:

Unter den im Suchbaum verwalteten Hashtags seien folgende Musikstücke (hier nur durch ihren eindeutigen Titel angegeben) verzeichnet:

Hashtag · Titel der Musikstücke

#Discofox · • Jodelecho

• Party geht immer

• Tausend Tage Party

• Tausendmal ganz egal

#Mallorca · • Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Oktoberfest · • Almdudl

• Alphornblasn

• Jodelecho

#Party · • Almdudl

• Alphornblasn

• Party geht immer

• Tausend Tage Party

#Schlager · • Tausendmal tanzen

• Party geht immer

• Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Tausend · • Tausendmal tanzen

• Tausend Tage Party

• Tausendmal ganz egal

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Musikverwaltung

Objekte dieser Klasse verwalten alle Musikstücke und Hashtags einer Musikbibliothek. Ein und dasselbe Musikstück, repräsentiert durch genau ein Objekt der Klasse Musikstueck, kann mehreren Hashtags gleichzeitig zugeordnet sein.

Ausschnitt aus der Dokumentation der Klasse Musikverwaltung

Musikverwaltung()

Eine Musikverwaltung mit einer leeren Bibliothek wird initialisiert.

void fuegeStueckHinzu(Musikstueck pMusikstueck, Hashtag pHashtag)

Der Bibliothek wird das Stück pMusikstueck unter dem Hashtag pHashtag hinzugefügt. Ist das (identische) Objekt bereits in der zugehörigen Musikstück-Liste enthalten, geschieht nichts.

List<Hashtag> liefereHashtags(String pSubstring)

Die Methode liefert eine Liste aller Hashtag-Objekte zurück, deren Zeichenkette den String pSubstring enthält.

List<Musikstueck> liefereEtwas(List<Hashtag> pHashtags)

Diese Methode wird im Rahmen von Aufgabenteil c) analysiert.

Die Klasse Hashtag

Objekte dieser Klasse verwalten die Zeichenkette des Hashtags und alle Musikstücke, die diesem Hashtag zugeordnet sind.

Ausschnitt aus der Dokumentation der Klasse Hashtag

Hashtag(String pZeichenkette)

Ein neues Hashtag-Objekt für das übergebene Hashtag pZeichenkette wird initialisiert. Die Liste der verwalteten Musikstücke ist zu Beginn leer.

String gibZeichenkette()

Die Zeichenkette des Hashtags, das durch dieses Objekt repräsentiert wird, wird als String zurückgegeben.

List<Musikstueck> gibStuecke()

Eine Liste aller Musikstücke, die diesem Hashtag zugeordnet sind, wird zurückgegeben.

void fuegeStueckHinzu(Musikstueck pMusikstueck)

Das übergebene Stück pMusikstueck wird in die Liste der diesem Hashtag-Objekt zugeordneten Stücke aufgenommen. Die Liste ist nachher alphabetisch aufsteigend sortiert. Sollte pMusikstueck schon in der Liste vorhanden sein, geschieht nichts.

boolean isEqual(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, gleich der Zeichenkette des Hashtag-Objekts pAnderer ist, wird true geliefert, sonst false.

boolean isLess(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend vor der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

boolean isGreater(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend hinter der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

Die Klasse Musikstueck

Objekte dieser Klasse modellieren ein Musikstück, bestehend aus Titel und Dauer.

Dokumentation der Klasse Musikstueck

Musikstueck(String pTitel, int pDauer)

Ein neues Musikstueck-Objekt wird initialisiert. Dem Objekt wird der übergebene Titel pTitel und die Dauer pDauer in Sekunden zugeordnet.

String gibTitel()

Der Titel des Musikstücks wird zurückgegeben.

int gibDauer()

Die Dauer des Musikstücks in Sekunden wird zurückgegeben.

Die Klasse String

Objekte dieser Klasse verwalten eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

String(String pString)

Ein neues String-Objekt wird initialisiert. Dem Objekt ist nachher eine Kopie der durch pString übergebenen Zeichenkette zugeordnet.

int indexOf(String pStr)

Gibt den Index des ersten Vorkommens der angegebenen Teilzeichenkette pStr innerhalb der durch dieses Objekt verwalteten Zeichenkette zurück. Kommt pStr nicht darin vor, wird -1 zurückgegeben.

Die generische Klasse BinarySearchTree

Mithilfe der generischen Klasse BinarySearchTree können beliebig viele Objekte des Typs ContentType in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungsrelation verwaltet werden.

Ein Objekt der Klasse BinarySearchTree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ ContentType sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind.

Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface ComparableContent implementieren. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater (siehe Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen:

c1.isLess(c2) (Sprechweise: c1 ist kleiner als c2)

c1.isEqual(c2) (Sprechweise: c1 ist gleichgroß wie c2)

c1.isGreater(c2) (Sprechweise: c1 ist größer als c2)

Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

Dokumentation der generischen Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.

void insert(ContentType pContent)

Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie pContent, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts.

ContentType search(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben.

void remove(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist, ändert sich nichts.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

Das generische Interface ComparableContent<ContentType>

Das generische Interface ComparableContent muss von Klassen implementiert werden, deren Objekte in einen Suchbaum ( BinarySearchTree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, isEqual und isLess festgelegt.

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

boolean isGreater(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isEqual(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe a)

Die folgenden Hashtags werden nacheinander in der genannten Reihenfolge in einen anfangs leeren binären Suchbaum eingetragen:

1. #LoungeJazz 2. #Eminem 3. #Metal 4. #House

5. #Queen 6. #Dancefloor 7. #Dubstep 8. #PJSpezial

a.1)

Geben Sie den binären Suchbaum an, der nach diesen Einfügevorgängen vorliegt. [4 Punkte]

a.2)

Erläutern Sie am Beispiel des zusätzlich einzufügenden Hashtags #Heavy, wie ein Element in den binären Suchbaum eingefügt wird. [3 Punkte]

a.3)

Stellen Sie einen Binärbaum dar, der sich ergibt, wenn zuerst der Hashtag #Heavy eingefügt und danach der Hashtag #Eminem gelöscht wird. [3 Punkte]

Teilaufgabe d)

Es soll eine Methode entstehen, die eine Liste aller Hashtag-Objekte zurückgibt, in deren Hashtag-Zeichenkette die übergebene Buchstabenfolge vorkommt. Die öffentliche Methode erhält diesen Methodenkopf:

public List<Hashtag> liefereHashtags(String pSubstring) d.1)

Entwickeln Sie einen algorithmischen Ansatz, mit dem die Methode ihre Aufgabe erfüllt. [5 Punkte]

d.2)

Implementieren Sie die Methode liefereHashtags sowie gegebenenfalls benötigte Hilfsmethoden. [8 Punkte]

Hinweis: Im Anhang finden Sie einen Auszug aus der Dokumentation der Klasse String.

Sachkontext: Musikverwaltung mit Hashtags für DJ P.J.

Peter Johann tritt als beliebter Discjockey („DJ P.J.“) auf. Zu seinem Erfolg trägt bei, dass er die Stücke für seine Auftritte weniger nach Titel oder Interpret auswählt, sondern vor allem nach deren Beschreibungen und Merkmalen. Dazu nutzt er eine von ihm selbst entwickelte Software, die alle Musikstücke über sogenannte Hashtags verwaltet. Ein Hashtag ist ein Schlagwort, das ein Musikstück genauer charakterisiert. Jedem Musikstück ist mindestens ein Hashtag zugewiesen. Ein Hashtag beginnt stets mit genau einem Doppelkreuz (#), darauf folgt das beschreibende Schlagwort, das ausschließlich Buchstaben und Ziffern enthalten darf. Gültige Hashtags sind zum Beispiel #Rock, #Blues, #HipHop, #Uptempo140 oder #ChaChaCha, nicht aber #Rock#*Pop!.

Die Hashtags werden in einem binären Suchbaum verwaltet.

Peter hat den Entwurf seiner Software in Abbildung 1 festgehalten und dabei berücksichtigt, dass zu einem Hashtag mehrere Musikstücke gehören können.

Anlage: Beispieldaten

Der Suchbaum bibliothek der Klasse Musikverwaltung habe folgenden Inhalt:

Unter den im Suchbaum verwalteten Hashtags seien folgende Musikstücke (hier nur durch ihren eindeutigen Titel angegeben) verzeichnet:

Hashtag · Titel der Musikstücke

#Discofox · • Jodelecho

• Party geht immer

• Tausend Tage Party

• Tausendmal ganz egal

#Mallorca · • Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Oktoberfest · • Almdudl

• Alphornblasn

• Jodelecho

#Party · • Almdudl

• Alphornblasn

• Party geht immer

• Tausend Tage Party

#Schlager · • Tausendmal tanzen

• Party geht immer

• Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Tausend · • Tausendmal tanzen

• Tausend Tage Party

• Tausendmal ganz egal

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Musikverwaltung

Objekte dieser Klasse verwalten alle Musikstücke und Hashtags einer Musikbibliothek. Ein und dasselbe Musikstück, repräsentiert durch genau ein Objekt der Klasse Musikstueck, kann mehreren Hashtags gleichzeitig zugeordnet sein.

Ausschnitt aus der Dokumentation der Klasse Musikverwaltung

Musikverwaltung()

Eine Musikverwaltung mit einer leeren Bibliothek wird initialisiert.

void fuegeStueckHinzu(Musikstueck pMusikstueck, Hashtag pHashtag)

Der Bibliothek wird das Stück pMusikstueck unter dem Hashtag pHashtag hinzugefügt. Ist das (identische) Objekt bereits in der zugehörigen Musikstück-Liste enthalten, geschieht nichts.

List<Hashtag> liefereHashtags(String pSubstring)

Die Methode liefert eine Liste aller Hashtag-Objekte zurück, deren Zeichenkette den String pSubstring enthält.

List<Musikstueck> liefereEtwas(List<Hashtag> pHashtags)

Diese Methode wird im Rahmen von Aufgabenteil c) analysiert.

Die Klasse Hashtag

Objekte dieser Klasse verwalten die Zeichenkette des Hashtags und alle Musikstücke, die diesem Hashtag zugeordnet sind.

Ausschnitt aus der Dokumentation der Klasse Hashtag

Hashtag(String pZeichenkette)

Ein neues Hashtag-Objekt für das übergebene Hashtag pZeichenkette wird initialisiert. Die Liste der verwalteten Musikstücke ist zu Beginn leer.

String gibZeichenkette()

Die Zeichenkette des Hashtags, das durch dieses Objekt repräsentiert wird, wird als String zurückgegeben.

List<Musikstueck> gibStuecke()

Eine Liste aller Musikstücke, die diesem Hashtag zugeordnet sind, wird zurückgegeben.

void fuegeStueckHinzu(Musikstueck pMusikstueck)

Das übergebene Stück pMusikstueck wird in die Liste der diesem Hashtag-Objekt zugeordneten Stücke aufgenommen. Die Liste ist nachher alphabetisch aufsteigend sortiert. Sollte pMusikstueck schon in der Liste vorhanden sein, geschieht nichts.

boolean isEqual(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, gleich der Zeichenkette des Hashtag-Objekts pAnderer ist, wird true geliefert, sonst false.

boolean isLess(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend vor der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

boolean isGreater(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend hinter der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

Die Klasse Musikstueck

Objekte dieser Klasse modellieren ein Musikstück, bestehend aus Titel und Dauer.

Dokumentation der Klasse Musikstueck

Musikstueck(String pTitel, int pDauer)

Ein neues Musikstueck-Objekt wird initialisiert. Dem Objekt wird der übergebene Titel pTitel und die Dauer pDauer in Sekunden zugeordnet.

String gibTitel()

Der Titel des Musikstücks wird zurückgegeben.

int gibDauer()

Die Dauer des Musikstücks in Sekunden wird zurückgegeben.

Die Klasse String

Objekte dieser Klasse verwalten eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

String(String pString)

Ein neues String-Objekt wird initialisiert. Dem Objekt ist nachher eine Kopie der durch pString übergebenen Zeichenkette zugeordnet.

int indexOf(String pStr)

Gibt den Index des ersten Vorkommens der angegebenen Teilzeichenkette pStr innerhalb der durch dieses Objekt verwalteten Zeichenkette zurück. Kommt pStr nicht darin vor, wird -1 zurückgegeben.

Die generische Klasse BinarySearchTree

Mithilfe der generischen Klasse BinarySearchTree können beliebig viele Objekte des Typs ContentType in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungsrelation verwaltet werden.

Ein Objekt der Klasse BinarySearchTree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ ContentType sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind.

Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface ComparableContent implementieren. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater (siehe Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen:

c1.isLess(c2) (Sprechweise: c1 ist kleiner als c2)

c1.isEqual(c2) (Sprechweise: c1 ist gleichgroß wie c2)

c1.isGreater(c2) (Sprechweise: c1 ist größer als c2)

Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

Dokumentation der generischen Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.

void insert(ContentType pContent)

Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie pContent, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts.

ContentType search(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben.

void remove(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist, ändert sich nichts.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

Das generische Interface ComparableContent<ContentType>

Das generische Interface ComparableContent muss von Klassen implementiert werden, deren Objekte in einen Suchbaum ( BinarySearchTree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, isEqual und isLess festgelegt.

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

boolean isGreater(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isEqual(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

b)

Analysieren Sie die Modellierung, die im Implementationsdiagramm in Abbildung 1 dargestellt ist, und erläutern Sie, welche Bedeutung die Klassen, das Interface und die Beziehungen zwischen ihnen haben.

Erläutern Sie, aus welchem Grund es zweckmäßig ist, die Daten im Suchbaum nach Hashtags statt nach den Titeln der Musikstücke zu ordnen.

[7 + 4 Punkte]

e)

Peter will sein Programm erweitern, sodass sich für jedes Musikstück abfragen lässt, wie häufig es bereits abgespielt wurde. Dazu sieht er vor, die Klasse Musikstueck entsprechend Abbildung 2 zu ergänzen:

Peters Freundin Heidi Hecker hat dagegen einen anderen Einfall. Sie empfiehlt, die bisherige Modellierung beizubehalten. Die Anzahl der Wiedergaben würde sie einfach als Hashtag auffassen und jedes Musikstück dem dazu passenden Hashtag zuordnen. Wurde ein Stück zum Beispiel fünfmal gespielt, wird es im Baum unter dem Hashtag #5 eingeordnet (das dafür gegebenenfalls erst angelegt wird). Nach Heidis Argumentation erspart man sich so die aufwendige Modellerweiterung, und die vorhandenen Methoden der Klasse Musikverwaltung lassen sich zusätzlich zu den „normalen“ Hashtags auch dazu verwenden, besonders erfolgreiche Stücke zu finden.

Beurteilen Sie die Vorschläge, die Peter und Heidi machen.

[6 Punkte]

Sachkontext: Musikverwaltung mit Hashtags für DJ P.J.

Peter Johann tritt als beliebter Discjockey („DJ P.J.“) auf. Zu seinem Erfolg trägt bei, dass er die Stücke für seine Auftritte weniger nach Titel oder Interpret auswählt, sondern vor allem nach deren Beschreibungen und Merkmalen. Dazu nutzt er eine von ihm selbst entwickelte Software, die alle Musikstücke über sogenannte Hashtags verwaltet. Ein Hashtag ist ein Schlagwort, das ein Musikstück genauer charakterisiert. Jedem Musikstück ist mindestens ein Hashtag zugewiesen. Ein Hashtag beginnt stets mit genau einem Doppelkreuz (#), darauf folgt das beschreibende Schlagwort, das ausschließlich Buchstaben und Ziffern enthalten darf. Gültige Hashtags sind zum Beispiel #Rock, #Blues, #HipHop, #Uptempo140 oder #ChaChaCha, nicht aber #Rock#*Pop!.

Die Hashtags werden in einem binären Suchbaum verwaltet.

Peter hat den Entwurf seiner Software in Abbildung 1 festgehalten und dabei berücksichtigt, dass zu einem Hashtag mehrere Musikstücke gehören können.

Anlage: Beispieldaten

Der Suchbaum bibliothek der Klasse Musikverwaltung habe folgenden Inhalt:

Unter den im Suchbaum verwalteten Hashtags seien folgende Musikstücke (hier nur durch ihren eindeutigen Titel angegeben) verzeichnet:

Hashtag · Titel der Musikstücke

#Discofox · • Jodelecho

• Party geht immer

• Tausend Tage Party

• Tausendmal ganz egal

#Mallorca · • Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Oktoberfest · • Almdudl

• Alphornblasn

• Jodelecho

#Party · • Almdudl

• Alphornblasn

• Party geht immer

• Tausend Tage Party

#Schlager · • Tausendmal tanzen

• Party geht immer

• Tanzen im Sand

• Tausend Tage Party

• Tausendmal ganz egal

#Tausend · • Tausendmal tanzen

• Tausend Tage Party

• Tausendmal ganz egal

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Musikverwaltung

Objekte dieser Klasse verwalten alle Musikstücke und Hashtags einer Musikbibliothek. Ein und dasselbe Musikstück, repräsentiert durch genau ein Objekt der Klasse Musikstueck, kann mehreren Hashtags gleichzeitig zugeordnet sein.

Ausschnitt aus der Dokumentation der Klasse Musikverwaltung

Musikverwaltung()

Eine Musikverwaltung mit einer leeren Bibliothek wird initialisiert.

void fuegeStueckHinzu(Musikstueck pMusikstueck, Hashtag pHashtag)

Der Bibliothek wird das Stück pMusikstueck unter dem Hashtag pHashtag hinzugefügt. Ist das (identische) Objekt bereits in der zugehörigen Musikstück-Liste enthalten, geschieht nichts.

List<Hashtag> liefereHashtags(String pSubstring)

Die Methode liefert eine Liste aller Hashtag-Objekte zurück, deren Zeichenkette den String pSubstring enthält.

List<Musikstueck> liefereEtwas(List<Hashtag> pHashtags)

Diese Methode wird im Rahmen von Aufgabenteil c) analysiert.

Die Klasse Hashtag

Objekte dieser Klasse verwalten die Zeichenkette des Hashtags und alle Musikstücke, die diesem Hashtag zugeordnet sind.

Ausschnitt aus der Dokumentation der Klasse Hashtag

Hashtag(String pZeichenkette)

Ein neues Hashtag-Objekt für das übergebene Hashtag pZeichenkette wird initialisiert. Die Liste der verwalteten Musikstücke ist zu Beginn leer.

String gibZeichenkette()

Die Zeichenkette des Hashtags, das durch dieses Objekt repräsentiert wird, wird als String zurückgegeben.

List<Musikstueck> gibStuecke()

Eine Liste aller Musikstücke, die diesem Hashtag zugeordnet sind, wird zurückgegeben.

void fuegeStueckHinzu(Musikstueck pMusikstueck)

Das übergebene Stück pMusikstueck wird in die Liste der diesem Hashtag-Objekt zugeordneten Stücke aufgenommen. Die Liste ist nachher alphabetisch aufsteigend sortiert. Sollte pMusikstueck schon in der Liste vorhanden sein, geschieht nichts.

boolean isEqual(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, gleich der Zeichenkette des Hashtag-Objekts pAnderer ist, wird true geliefert, sonst false.

boolean isLess(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend vor der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

boolean isGreater(Hashtag pAnderer)

Wenn die Zeichenkette des Hashtag-Objekts, von dem die Methode aufgerufen wird, alphabetisch aufsteigend hinter der Zeichenkette des Hashtag-Objekts pAnderer liegt, wird true geliefert, sonst false.

Die Klasse Musikstueck

Objekte dieser Klasse modellieren ein Musikstück, bestehend aus Titel und Dauer.

Dokumentation der Klasse Musikstueck

Musikstueck(String pTitel, int pDauer)

Ein neues Musikstueck-Objekt wird initialisiert. Dem Objekt wird der übergebene Titel pTitel und die Dauer pDauer in Sekunden zugeordnet.

String gibTitel()

Der Titel des Musikstücks wird zurückgegeben.

int gibDauer()

Die Dauer des Musikstücks in Sekunden wird zurückgegeben.

Die Klasse String

Objekte dieser Klasse verwalten eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

String(String pString)

Ein neues String-Objekt wird initialisiert. Dem Objekt ist nachher eine Kopie der durch pString übergebenen Zeichenkette zugeordnet.

int indexOf(String pStr)

Gibt den Index des ersten Vorkommens der angegebenen Teilzeichenkette pStr innerhalb der durch dieses Objekt verwalteten Zeichenkette zurück. Kommt pStr nicht darin vor, wird -1 zurückgegeben.

Die generische Klasse BinarySearchTree

Mithilfe der generischen Klasse BinarySearchTree können beliebig viele Objekte des Typs ContentType in einem Binärbaum (binärer Suchbaum) entsprechend einer Ordnungsrelation verwaltet werden.

Ein Objekt der Klasse BinarySearchTree stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt vom Typ ContentType sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind.

Die Klasse der Objekte, die in dem Suchbaum verwaltet werden sollen, muss das generische Interface ComparableContent implementieren. Dabei muss durch Überschreiben der drei Vergleichsmethoden isLess, isEqual, isGreater (siehe Dokumentation des Interfaces) eine eindeutige Ordnungsrelation festgelegt sein.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Für je zwei Objekte c1 und c2 vom Typ ContentType gilt also insbesondere genau eine der drei Aussagen:

c1.isLess(c2) (Sprechweise: c1 ist kleiner als c2)

c1.isEqual(c2) (Sprechweise: c1 ist gleichgroß wie c2)

c1.isGreater(c2) (Sprechweise: c1 ist größer als c2)

Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

Dokumentation der generischen Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.

void insert(ContentType pContent)

Falls bereits ein Objekt in dem Suchbaum vorhanden ist, das gleichgroß ist wie pContent, passiert nichts. Andernfalls wird das Objekt pContent entsprechend der Ordnungsrelation in den Baum eingeordnet. Falls der Parameter null ist, ändert sich nichts.

ContentType search(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, liefert die Anfrage dieses, ansonsten wird null zurückgegeben. Falls der Parameter null ist, wird null zurückgegeben.

void remove(ContentType pContent)

Falls ein Objekt im binären Suchbaum enthalten ist, das gleichgroß ist wie pContent, wird dieses entfernt. Falls der Parameter null ist, ändert sich nichts.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des binären Suchbaumes. Der binäre Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

BinarySearchTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Suchbaumes. Der Suchbaum ändert sich nicht. Wenn er leer ist, wird null zurückgegeben.

Das generische Interface ComparableContent<ContentType>

Das generische Interface ComparableContent muss von Klassen implementiert werden, deren Objekte in einen Suchbaum ( BinarySearchTree) eingefügt werden sollen. Die Ordnungsrelation wird in diesen Klassen durch Überschreiben der drei implizit abstrakten Methoden isGreater, isEqual und isLess festgelegt.

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

boolean isGreater(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation größer als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isEqual(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation gleich dem Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(ContentType pComparableContent)

Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gewünschten Ordnungsrelation kleiner als das Objekt pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

Die generische Klasse List

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

c) In Peters Quelltext der Klasse Musikverwaltung findet sich folgende undokumentierte Methode:

1 public List<Musikstueck> liefereEtwas(

2 List<Hashtag> pHashtags) {

3 List<Musikstueck> ret = new List<Musikstueck>();

4 pHashtags.toFirst();

5 while (pHashtags.hasAccess()) {

6 Hashtag eintrag =

7 bibliothek.search(pHashtags.getContent());

8 if (eintrag != null) {

9 List<Musikstueck> liste = eintrag.gibStuecke();

10 liste.toFirst();

11 while (liste.hasAccess()) {

12 Musikstueck aktStueck = liste.getContent();

13 ret.append(aktStueck);

14 liste.next();

15 }

16 }

17 pHashtags.next();

18 }

19 return ret;

20 }

Die Anlage enthält Beispieldaten zu einem aktuellen Zustand des Binärbaums bibliothek der Klasse Musikverwaltung und zu den darin verwalteten Musikstücken. Davon ausgehend wird der Methode liefereEtwas nun eine Liste übergeben, in der die Hashtags #Mallorca und #Party enthalten sind.

c.1)

Analysieren Sie die Methode liefereEtwas anhand der Beispieldaten und der übergebenen Liste, indem Sie ihre Rückgabe ermitteln, und erläutern Sie, wie die Methode arbeitet. [4 Punkte]

c.2)

Erläutern Sie, welchen Zweck die Methode im Sachzusammenhang erfüllt. [2 Punkte]

c.3)

Erläutern Sie, wie oft ein Musikstück in der Ergebnisliste auftreten kann, je nachdem, welche Eingabeliste übergeben wird. [4 Punkte]

Aufgabenstellung:

Weil Gäste Restaurants meist subjektiv beurteilen, plant der Projektkurs „Gastro-Informatik“ ein Bewertungssystem, in dem eine fachkundige Gutachterin bzw. ein fachkundiger Gutachter die Qualität von Speisen und Service sowie den Hygienezustand auf einer Skala von 0 bis 10 einstuft; 10 ist dabei die beste Note.

Die dabei entstehenden Daten sollen in einer relationalen Datenbank verwaltet werden, die auf der folgenden Teilmodellierung beruht:

Das Datenbankschema in Abbildung 2 überführt die Teilmodellierung aus Abbildung 1 in eine relationale Datenbank und wird im Weiteren genauer untersucht. Die Anlage enthält Beispieldaten zu diesem Schema.

Anlage:

Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

a)

Beschreiben Sie die Teilmodellierung, die Abbildung 1 in Form eines Entity-Relationship-Diagramms zeigt.

Erläutern Sie die Beziehungstypen des Entity-Relationship-Diagramms in Abbildung 1 einschließlich ihrer Kardinalitäten bezogen auf den Sachkontext.

Erläutern Sie, auf welche Weise der 1:n-Beziehungstyp befindetSichIn sowie der n:m-Beziehungstyp bewertet des Entity-Relationship-Modells aus Abbildung 1 im Datenbankschema in Abbildung 2 realisiert wurden.

(3 + 4 + 4 Punkte)

d)

Die praktische Erprobung des Restaurantbewertungssystems hat ergeben, dass die folgenden Punkte angepasst werden müssen:

i. Zu jedem Restaurant soll eine Telefonnummer für Reservierungen und Rückfragen gespeichert werden.

ii. Gutachterinnen und Gutachter sollen dasselbe Restaurant nach Tagen oder Wochen noch einmal bewerten dürfen. Hierfür soll bei jeder Bewertung das Datum festgehalten werden.

iii. Gutachterinnen und Gutachter dürfen Wünsche zu ihrem Einsatzort angeben. Deshalb sollen pro Person mehrere bevorzugte Einsatzorte abgelegt werden können.

Modellieren Sie eine Erweiterung des Entity-Relationship-Diagramms aus Abbildung 1, sodass der neue Datenbankentwurf auch die geschilderten Aspekte abdeckt.

Erläutern Sie, auf welche Weise Ihr entwickeltes Modell die Anforderungen erfüllt, und begründen Sie für gegebenenfalls nötige neue Beziehungstypen die gewählten Kardinalitäten.

Hinweis: Entitäts- und Beziehungstypen sowie Attribute, die für die Erweiterung keine Rolle spielen, brauchen nicht eingezeichnet zu werden.

(7 + 6 Punkte)

e)

Ein Praktikant empfiehlt, anstelle des Datenbankschemas aus Abbildung 2 seinen Entwurf aus Abbildung 3 zu verwenden.

Seiner Überzeugung nach lasse sich damit Speicherplatz sparen und die Übersichtlichkeit verbessern, denn es seien deutlich weniger Attribute zu verwalten, da zusätzliche Fremdschlüssel wegfielen. Außerdem sei das Schema in Abbildung 3 leichter lesbar und habe gegenüber dem Schema in Abbildung 2 keine nennenswerten Nachteile.

Begründen Sie unter Bezug auf die genannten Argumente und unter Einbeziehung der Normalformen, weshalb der Vorschlag des Praktikanten abzulehnen ist.

(6 Punkte)

Aufgabenstellung:

Weil Gäste Restaurants meist subjektiv beurteilen, plant der Projektkurs „Gastro-Informatik“ ein Bewertungssystem, in dem eine fachkundige Gutachterin bzw. ein fachkundiger Gutachter die Qualität von Speisen und Service sowie den Hygienezustand auf einer Skala von 0 bis 10 einstuft; 10 ist dabei die beste Note.

Die dabei entstehenden Daten sollen in einer relationalen Datenbank verwaltet werden, die auf der folgenden Teilmodellierung beruht:

Das Datenbankschema in Abbildung 2 überführt die Teilmodellierung aus Abbildung 1 in eine relationale Datenbank und wird im Weiteren genauer untersucht. Die Anlage enthält Beispieldaten zu diesem Schema.

Anlage:

Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Teilaufgabe b)

Mithilfe der im Anhang abgebildeten Datenbank sollen die folgenden Abfragen formuliert werden:

i.

Ermittelt werden sollen die Namen sämtlicher Restaurants in Dortmund. Die Ausgabe soll absteigend nach dem Restaurantnamen geordnet sein.

ii.

Ermittelt werden sollen Vor- und Nachname derjenigen Gutachterinnen und Gutachter, die bereits ein Restaurant namens „Meisterpizza“ bewertet haben.

iii.

Ermittelt werden sollen die Restaurants, für die bisher keine Bewertung vorliegt. Auszugeben sind dabei Restaurantname, PLZ und Ortsname.

Teilaufgabe c)

Gegeben ist die folgende SQL-Anweisung:

1 SELECT Temp.Nachname, Temp.Vorname

2 FROM (

3 SELECT Gutachter.Nachname, Gutachter.Vorname,

4 COUNT(bewertet.RestaurantID) AS a

5 FROM Gutachter

6 INNER JOIN bewertet

7 ON Gutachter.ID = bewertet.GutachterID

8 GROUP BY bewertet.GutachterID

9) AS Temp

10 WHERE Temp.a > 1

c.1

Analysieren und erläutern Sie zuerst die Unterabfrage (Zeilen 3 bis 8), danach die gesamte SQL-Anweisung:

c.2

Erläutern Sie bezogen auf den Sachkontext, welche Information die gesamte SQL-Anweisung liefert:

Sachkontext: Signalprotokolle für das SETI-Projekt

In der modernen Astronomie spielen Radioteleskope eine zentrale Rolle. Über große Antennen erfassen sie Signale im Frequenzbereich von 0.01 GHz bis 100.00 GHz und stellen die Daten vielen Forschungsprojekten zur Verfügung. Zu diesen gehört das SETI-Projekt (Search for Extraterrestrial Intelligence), das der Frage nachgeht, ob einige der empfangenen Radiosignale von außerirdischen Zivilisationen stammen könnten, die Kontakt aufnehmen wollen.

Ein einfaches Protokoll der Signalfrequenzen kann etwa so aussehen:

43.22;0.10;3.21;1.53;14.22

Jede Sekunde wird dem Protokoll, durch ein Semikolon getrennt, ein neuer Eintrag für das stärkste Signal hinzugefügt. Bei einem empfangenen Signal wird dessen Frequenz mit zwei Nachkommastellen eingetragen. Wurde kein Signal empfangen, wird 0.00 eingetragen. Prinzipiell kann ein Signalprotokoll beliebig lang werden.

Das Wasserloch

Im SETI-Projekt achtet man in den Signalprotokollen vor allem auf Frequenzen von 1.42 GHz bis 1.66 GHz (jeweils einschließlich), das sogenannte Wasserloch. Hier gibt es besonders wenige natürliche Störsignale, weshalb man annimmt, dass eine außerirdische Zivilisation diesen Bereich für eine Kontaktaufnahme wählen würde.

Erweitertes Signalprotokoll

Auch wenn das Wasserloch nur wenige natürliche Störquellen aufweist, treten dort wiederholt künstliche Störsignale auf, die von technischen Geräten (z. B. Mikrowellenöfen) in der Nähe des Radioteleskops erzeugt werden. Verglichen mit Signalen aus weiter Ferne sind sie meist sehr energiereich und lassen sich daher häufig an ihrer Signalstärke erkennen.

Deshalb entscheidet man sich im SETI-Projekt, künftig ein erweitertes Signalprotokoll zu verwenden, das zusätzlich zur Frequenz die Signalstärke festhält. Ein erweitertes Signalprotokoll kann zum Beispiel so aussehen:

(43.22:b);(0.10:a);(3.21:d);(0.01:a);(1.53:b);(14.22:f)

Nach jeder Frequenz folgt nun, durch einen Doppelpunkt getrennt, die Signalstärke mit den Stufen

a, b, c, d, e, f

Dabei steht a für ein sehr schwaches und f für ein sehr starkes Signal. Zudem wird jeder derart erweiterte Eintrag von Klammern umschlossen.

Anhang: Dokumentation der Klassen

Die Klasse Protokollpruefer

Ein Objekt der Klasse Protokollpruefer wird verwendet, um erweiterte Signalprotokolle auf eventuelle Kontaktversuche von außerirdischen Zivilisationen zu überprüfen.

Methode · Beschreibung

Protokollpruefer()

Das Objekt der Klasse Protokollpruefer wird initialisiert.

boolean enthaeltSchwachesSignal(List<Signal> pProtokoll)

Die Methode liefert den Wert true, wenn das übergebene erweiterte Signalprotokoll pProtokoll mindestens einen Eintrag enthält, der die Signalstärke a oder b hat. Ansonsten liefert die Methode den Wert false.

Die Klasse Signal

Ein Objekt der Klasse Signal speichert einen einzelnen Signaleintrag bestehend aus einer Signalfrequenz und einer Signalstärke.

Methode · Beschreibung

Signal(double pFrequenz, char pStaerke)

Das Objekt der Klasse Signal wird mit pFrequenz als Signalfrequenz und pStaerke als Signalstärke initialisiert.

double gibFrequenz()

Die Methode liefert die Signalfrequenz des Eintrags.

char gibStaerke()

Die Methode liefert die Signalstärke des Eintrags.

Die generische Klasse List<ContentType>

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Methode · Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe a)

Werden Signalprotokolle übertragen, treten oft Fehler auf, welche die spätere Auswertung erschweren. Deshalb prüft man die Protokolle auf ihre Korrektheit. Dazu dient der Automat $A_1$, dessen Zustandsübergangsdiagramm in Abbildung 1 dargestellt ist. Diese Prüfung leistet er jedoch nur zum Teil.

Geben Sie für den Automaten $A_1$ den Startzustand, die Endzustände, das Eingabealphabet und die Zustandsmenge an.

Analysieren Sie den Automaten $A_1$ und erläutern Sie, welchen Aufbau eine Eingabezeichenfolge haben muss, damit sie als fehlerfrei akzeptiert wird.

Ermitteln Sie eine Zeichenfolge, die der Automat $A_1$ akzeptiert, obwohl sie kein korrektes Signalprotokoll ist.

Teilaufgabe b)

Im SETI-Projekt werden Signalprotokolle vor allem auf Frequenzen von $1.42\text{ GHz}$ bis $1.66\text{ GHz}$ (jeweils einschließlich) untersucht, das sogenannte Wasserloch. Dort gibt es besonders wenige störende natürliche Signale; deshalb nimmt man an, dass eine außerirdische Zivilisation diesen Bereich für die Kontaktaufnahme verwenden würde.

Ein Mitarbeiter hat die Idee, auch für die inhaltliche Auswertung einen Automaten zur Hilfe zu nehmen. Der nichtdeterministische endliche Automat $A_2$ soll von allen einfachen Signalprotokollen diejenigen akzeptieren, in denen mindestens ein Signal im Wasserloch-Frequenzbereich enthalten ist. Die formale Korrektheit des Protokolls kann vorausgesetzt werden, so dass sie vom Automaten $A_2$ nicht überprüft werden muss.

Entwerfen Sie den nichtdeterministischen endlichen Automaten $A_2$ gemäß den oben genannten Anforderungen.

Begründen Sie, warum Ihr Automat $A_2$ ein nichtdeterministischer endlicher Automat (NEA) ist.

Zeigen Sie, dass das Signalprotokoll 9.01;1.52;0.00 von Ihrem Automaten $A_2$ akzeptiert wird.

Sachkontext: Signalprotokolle für das SETI-Projekt

In der modernen Astronomie spielen Radioteleskope eine zentrale Rolle. Über große Antennen erfassen sie Signale im Frequenzbereich von 0.01 GHz bis 100.00 GHz und stellen die Daten vielen Forschungsprojekten zur Verfügung. Zu diesen gehört das SETI-Projekt (Search for Extraterrestrial Intelligence), das der Frage nachgeht, ob einige der empfangenen Radiosignale von außerirdischen Zivilisationen stammen könnten, die Kontakt aufnehmen wollen.

Ein einfaches Protokoll der Signalfrequenzen kann etwa so aussehen:

43.22;0.10;3.21;1.53;14.22

Jede Sekunde wird dem Protokoll, durch ein Semikolon getrennt, ein neuer Eintrag für das stärkste Signal hinzugefügt. Bei einem empfangenen Signal wird dessen Frequenz mit zwei Nachkommastellen eingetragen. Wurde kein Signal empfangen, wird 0.00 eingetragen. Prinzipiell kann ein Signalprotokoll beliebig lang werden.

Das Wasserloch

Im SETI-Projekt achtet man in den Signalprotokollen vor allem auf Frequenzen von 1.42 GHz bis 1.66 GHz (jeweils einschließlich), das sogenannte Wasserloch. Hier gibt es besonders wenige natürliche Störsignale, weshalb man annimmt, dass eine außerirdische Zivilisation diesen Bereich für eine Kontaktaufnahme wählen würde.

Erweitertes Signalprotokoll

Auch wenn das Wasserloch nur wenige natürliche Störquellen aufweist, treten dort wiederholt künstliche Störsignale auf, die von technischen Geräten (z. B. Mikrowellenöfen) in der Nähe des Radioteleskops erzeugt werden. Verglichen mit Signalen aus weiter Ferne sind sie meist sehr energiereich und lassen sich daher häufig an ihrer Signalstärke erkennen.

Deshalb entscheidet man sich im SETI-Projekt, künftig ein erweitertes Signalprotokoll zu verwenden, das zusätzlich zur Frequenz die Signalstärke festhält. Ein erweitertes Signalprotokoll kann zum Beispiel so aussehen:

(43.22:b);(0.10:a);(3.21:d);(0.01:a);(1.53:b);(14.22:f)

Nach jeder Frequenz folgt nun, durch einen Doppelpunkt getrennt, die Signalstärke mit den Stufen

a, b, c, d, e, f

Dabei steht a für ein sehr schwaches und f für ein sehr starkes Signal. Zudem wird jeder derart erweiterte Eintrag von Klammern umschlossen.

Anhang: Dokumentation der Klassen

Die Klasse Protokollpruefer

Ein Objekt der Klasse Protokollpruefer wird verwendet, um erweiterte Signalprotokolle auf eventuelle Kontaktversuche von außerirdischen Zivilisationen zu überprüfen.

Methode · Beschreibung

Protokollpruefer()

Das Objekt der Klasse Protokollpruefer wird initialisiert.

boolean enthaeltSchwachesSignal(List<Signal> pProtokoll)

Die Methode liefert den Wert true, wenn das übergebene erweiterte Signalprotokoll pProtokoll mindestens einen Eintrag enthält, der die Signalstärke a oder b hat. Ansonsten liefert die Methode den Wert false.

Die Klasse Signal

Ein Objekt der Klasse Signal speichert einen einzelnen Signaleintrag bestehend aus einer Signalfrequenz und einer Signalstärke.

Methode · Beschreibung

Signal(double pFrequenz, char pStaerke)

Das Objekt der Klasse Signal wird mit pFrequenz als Signalfrequenz und pStaerke als Signalstärke initialisiert.

double gibFrequenz()

Die Methode liefert die Signalfrequenz des Eintrags.

char gibStaerke()

Die Methode liefert die Signalstärke des Eintrags.

Die generische Klasse List<ContentType>

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Methode · Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Teilaufgabe c)

Die Sprache der erweiterten Signalprotokolle wird durch die nachstehende Grammatik $G_1$ erzeugt.

Startsymbol: S

Terminalsymbole: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f, (,),.,:,;}

Nichtterminalsymbole: {S, F, I, N, Z}

Produktionen:

{ S → (F:I) | S;S,

F → ZN.NN,

I → a | b | c | d | e | f,

N → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,

Z → &epsilon; | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 }

c1)

Zeigen Sie, dass das erweiterte Signalprotokoll (1.63:c) in der Sprache der Grammatik $G_1$ enthalten ist. Geben Sie dazu die einzelnen Ableitungsschritte an.

c2)

Erläutern Sie, welche Teile eines Signalprotokolls sich jeweils aus den einzelnen Nichtterminalen der Grammatik $G_1$ ableiten lassen.

c3)

Begründen Sie, warum die Grammatik $G_1$ keine reguläre Grammatik ist.

Teilaufgabe e)

Es zeigt sich bald, dass die Signalstärke Störsignale nicht verlässlich erkennen lässt. Deshalb will das SETI-Projekt künftig anders vorgehen:

Ein Teleskop (z. B. in Europa) und ein Teleskop in Nordafrika zeichnen genau denselben Zeitraum auf. Um zu überprüfen, ob beide Protokolle an derselben Stelle identische Einträge enthalten, hängt man sie, getrennt durch ein Ausrufezeichen (!), aneinander. Die dadurch entstehende Zeichenkette dient als Eingabe für den Automaten.

e)

Beurteilen Sie, ob sich ein endlicher Automat dafür eignet, die oben beschriebene Prüfung anhand der kombinierten Zeichenkette vorzunehmen.

Sachkontext: Signalprotokolle für das SETI-Projekt

In der modernen Astronomie spielen Radioteleskope eine zentrale Rolle. Über große Antennen erfassen sie Signale im Frequenzbereich von 0.01 GHz bis 100.00 GHz und stellen die Daten vielen Forschungsprojekten zur Verfügung. Zu diesen gehört das SETI-Projekt (Search for Extraterrestrial Intelligence), das der Frage nachgeht, ob einige der empfangenen Radiosignale von außerirdischen Zivilisationen stammen könnten, die Kontakt aufnehmen wollen.

Ein einfaches Protokoll der Signalfrequenzen kann etwa so aussehen:

43.22;0.10;3.21;1.53;14.22

Jede Sekunde wird dem Protokoll, durch ein Semikolon getrennt, ein neuer Eintrag für das stärkste Signal hinzugefügt. Bei einem empfangenen Signal wird dessen Frequenz mit zwei Nachkommastellen eingetragen. Wurde kein Signal empfangen, wird 0.00 eingetragen. Prinzipiell kann ein Signalprotokoll beliebig lang werden.

Das Wasserloch

Im SETI-Projekt achtet man in den Signalprotokollen vor allem auf Frequenzen von 1.42 GHz bis 1.66 GHz (jeweils einschließlich), das sogenannte Wasserloch. Hier gibt es besonders wenige natürliche Störsignale, weshalb man annimmt, dass eine außerirdische Zivilisation diesen Bereich für eine Kontaktaufnahme wählen würde.

Erweitertes Signalprotokoll

Auch wenn das Wasserloch nur wenige natürliche Störquellen aufweist, treten dort wiederholt künstliche Störsignale auf, die von technischen Geräten (z. B. Mikrowellenöfen) in der Nähe des Radioteleskops erzeugt werden. Verglichen mit Signalen aus weiter Ferne sind sie meist sehr energiereich und lassen sich daher häufig an ihrer Signalstärke erkennen.

Deshalb entscheidet man sich im SETI-Projekt, künftig ein erweitertes Signalprotokoll zu verwenden, das zusätzlich zur Frequenz die Signalstärke festhält. Ein erweitertes Signalprotokoll kann zum Beispiel so aussehen:

(43.22:b);(0.10:a);(3.21:d);(0.01:a);(1.53:b);(14.22:f)

Nach jeder Frequenz folgt nun, durch einen Doppelpunkt getrennt, die Signalstärke mit den Stufen

a, b, c, d, e, f

Dabei steht a für ein sehr schwaches und f für ein sehr starkes Signal. Zudem wird jeder derart erweiterte Eintrag von Klammern umschlossen.

Anhang: Dokumentation der Klassen

Die Klasse Protokollpruefer

Ein Objekt der Klasse Protokollpruefer wird verwendet, um erweiterte Signalprotokolle auf eventuelle Kontaktversuche von außerirdischen Zivilisationen zu überprüfen.

Methode · Beschreibung

Protokollpruefer()

Das Objekt der Klasse Protokollpruefer wird initialisiert.

boolean enthaeltSchwachesSignal(List<Signal> pProtokoll)

Die Methode liefert den Wert true, wenn das übergebene erweiterte Signalprotokoll pProtokoll mindestens einen Eintrag enthält, der die Signalstärke a oder b hat. Ansonsten liefert die Methode den Wert false.

Die Klasse Signal

Ein Objekt der Klasse Signal speichert einen einzelnen Signaleintrag bestehend aus einer Signalfrequenz und einer Signalstärke.

Methode · Beschreibung

Signal(double pFrequenz, char pStaerke)

Das Objekt der Klasse Signal wird mit pFrequenz als Signalfrequenz und pStaerke als Signalstärke initialisiert.

double gibFrequenz()

Die Methode liefert die Signalfrequenz des Eintrags.

char gibStaerke()

Die Methode liefert die Signalstärke des Eintrags.

Die generische Klasse List<ContentType>

Objekte der generischen Klasse List verwalten beliebig viele, linear angeordnete Objekte vom Typ ContentType. Auf höchstens ein Listenobjekt, aktuelles Objekt genannt, kann jeweils zugegriffen werden. Wenn eine Liste leer ist, vollständig durchlaufen wurde oder das aktuelle Objekt am Ende der Liste gelöscht wurde, gibt es kein aktuelles Objekt. Das erste oder das letzte Objekt einer Liste kann durch einen Auftrag zum aktuellen Objekt gemacht werden. Außerdem kann das dem aktuellen Objekt folgende Listenobjekt zum neuen aktuellen Objekt werden.

Das aktuelle Objekt kann gelesen, verändert oder gelöscht werden. Außerdem kann vor dem aktuellen Objekt ein Listenobjekt eingefügt werden.

Methode · Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält, sonst liefert sie den Wert false.

boolean hasAccess()

Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

void next()

Falls die Liste nicht leer ist, es ein aktuelles Objekt gibt und dieses nicht das letzte Objekt der Liste ist, wird das dem aktuellen Objekt in der Liste folgende Objekt zum aktuellen Objekt, andernfalls gibt es nach Ausführung des Auftrags kein aktuelles Objekt, d. h., hasAccess() liefert den Wert false.

void toFirst()

Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast()

Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

ContentType getContent()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt zurückgegeben. Andernfalls ( hasAccess() == false) gibt die Anfrage den Wert null zurück.

void setContent(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true) und pContent ungleich null ist, wird das aktuelle Objekt durch pContent ersetzt. Sonst bleibt die Liste unverändert.

void append(ContentType pContent)

Ein neues Objekt pContent wird am Ende der Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt ( hasAccess() == false). Falls pContent gleich null ist, bleibt die Liste unverändert.

void insert(ContentType pContent)

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt ( hasAccess() == false) und die Liste nicht leer ist oder pContent == null ist, bleibt die Liste unverändert.

void concat(List<ContentType> pList)

Die Liste pList wird an die Liste angehängt. Anschließend wird pList eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls es sich bei der Liste und pList um dasselbe Objekt handelt, pList == null oder eine leere Liste ist, bleibt die Liste unverändert.

void remove()

Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird das aktuelle Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht, gibt es kein aktuelles Objekt mehr ( hasAccess() == false). Wenn die Liste leer ist oder es kein aktuelles Objekt gibt ( hasAccess() == false), bleibt die Liste unverändert.

Um ein erweitertes Signalprotokoll später auswerten zu können, ist die Java-Methode enthaeltSchwachesSignal in der Klasse Protokollpruefer zu implementieren.

Der Methodenkopf der Methode lautet:

public boolean enthaeltSchwachesSignal(List<Signal> pProtokoll)

Signale mit zu hoher Signalstärke kommen als Kontaktversuch nicht infrage. Die Methode soll daher prüfen, ob im übergebenen Protokoll wenigstens ein schwaches Signal der Stärke a oder b vorhanden ist. Die Frequenz eines Signals soll in dieser Methode noch nicht überprüft werden.

1.

Entwickeln Sie ein algorithmisches Verfahren für die Methode enthaeltSchwachesSignal.

[4 Punkte]

2.

Implementieren Sie die Methode enthaeltSchwachesSignal gemäß Ihrem entwickelten Verfahren.

[5 Punkte]

public boolean enthaeltSchwachesSignal(List<Signal> pProtokoll) {

}