Abitur NRW Informatik 2021 · LK · Haupttermin

Aufgabenstellung: Wetterdatenverwaltung

Ein Projektkurs zum Thema „Klimawandel“ plant, eine Software zu entwickeln, mit der Wetterdaten verwaltet und analysiert werden können.

Als Grundlage dienen dem Kurs Daten von Wetterstationen aus ganz Deutschland, die jeweils einen eindeutigen Stationsnamen und eine Stadt besitzen. Je nach Ausstattung kann eine Wetterstation unterschiedliche Messwertarten erfassen (z. B. die Temperatur in °C oder die Windgeschwindigkeit in km/h). Zu jeder Messung werden Messwertart, Messwert und Zeitpunkt abgespeichert (vgl. Abbildung 1).

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

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Wetterdatenverwaltung

Objekte der Klasse Wetterdatenverwaltung verwalten Wetterstationen mit ihren Messungen.

Auszug aus der Dokumentation der Klasse Wetterdatenverwaltung

Wetterdatenverwaltung()

Ein Objekt der Klasse Wetterdatenverwaltung wird initialisiert.

List<Wetterstation> gibWetterstationen()

Eine Liste mit allen Wetterstationen wird zurückgeliefert.

Wetterstation gibWetterstation(String pStationsname)

Die Wetterstation mit dem Namen pStationsname wird zurückgeliefert. Wenn zu diesem Namen keine Wetterstation existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Wetterstation pWetterstation)

Die Wetterstation pWetterstation wird der Wetterdatenverwaltung hinzugefügt, wenn der Stationsname bisher noch nicht existiert. Sonst geschieht nichts.

void fuegeHinzu(Wetterstation pWetterstation, Messung pMessung)

Wenn die Wetterstation pWetterstation in der Wetterdatenverwaltung existiert, dann wird dieser Station die Messung pMessung hinzugefügt. Sonst geschieht nichts.

Double ermittleEtwas(String pMesswertart, int pJahr)

Diese Methode soll in Teilaufgabe b) analysiert werden.

Die Klasse Wetterstation

Objekte der Klasse Wetterstation verwalten ihren Stationsnamen, ihre Stadt und ihre Messungen.

Auszug aus der Dokumentation der Klasse Wetterstation

Wetterstation(String pStationsname, String pStadt)

Ein Objekt der Klasse Wetterstation wird mit dem Stationsnamen pStationsname und der Stadt pStadt initialisiert.

String gibStationsname()

Der Stationsname wird zurückgeliefert.

String gibStadt()

Die Stadt wird zurückgeliefert.

List<Messung> gibMessungen()

Eine Liste mit allen Messungen dieser Wetterstation wird zurückgeliefert.

void fuegeHinzu(Messung pMessung)

Die Messung pMessung wird hinzugefügt.

List<Messung> ermittleSortierteMessungen(String pMesswertart)

Diese Methode soll in Teilaufgabe c) hinzugefügt werden.

Die Klasse Messung

Objekte der Klasse Messung verwalten ihre Messwertart, ihren Messwert und ihren Zeitpunkt.

Auszug aus der Dokumentation der Klasse Messung

Messung(String pMesswertart, double pMesswert, int pJahr, int pMonat, int pTag, int pStunde, int pMinute)

Ein Objekt der Klasse Messung wird mit der Messwertart pMesswertart, dem Messwert pMesswert und dem Zeitpunkt der Messung initialisiert.

String gibMesswertart()

Die Messwertart wird zurückgeliefert.

double gibMesswert()

Der Messwert wird zurückgeliefert.

int gibJahr()

Das Jahr wird zurückgeliefert.

int gibMonat()

Der Monat wird zurückgeliefert.

int gibTag()

Der Tag wird zurückgeliefert.

int gibStunde()

Die Stunde wird zurückgeliefert.

int gibMinute()

Die Minute wird zurückgeliefert.

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.

a)

Beschreiben Sie, in welchen Beziehungen die Klassen der in Abbildung 2 dargestellten Teilmodellierung zueinander stehen.

Begründen Sie im Sachkontext, weshalb es zweckmäßig ist, die Sammlungen der Wetterstationen und der Messungen jeweils als lineare Liste statt als Feld (Array) umzusetzen.

[5 Punkte]

d)

Der Test des ersten Software-Prototyps zeigt, dass das Projekt ausgebaut werden muss, damit es wirklich aussagekräftige Ergebnisse liefert. Zusätzlich sollen die folgenden Anforderungen realisiert werden:

Der Zeitpunkt einer Messung soll so präzisiert werden, dass in Zukunft zusätzlich zum Jahr, zum Monat, zum Tag, zur Stunde und zur Minute auch noch die Sekunde erfasst werden soll. Der so beschriebene Zeitpunkt soll in eine eigene Klasse ausgelagert werden, welche auch jeweils die Abfrage der genannten Attribute einzeln ermöglichen soll.

Um möglichst schnell zu jeder Messung die zugehörige Wetterstation ermitteln zu können, soll eine Messung auch Kenntnis über ihre Wetterstation haben. Eine Messung soll ihre Wetterstation auch zurückliefern können.

Der Projektkurs möchte in Zukunft auch mobile Messungen durchführen können, z. B. mit Wetterballons oder Treibbojen. Eine mobile Messung soll weiterhin einer Wetterstation zugeordnet sein. Zusätzlich soll nur für jede mobile Messung ihre Position in Form von zwei Werten gespeichert werden (z. B. 51.955013, 7.611646). Beide Werte sollen auch abgerufen werden können.

Modellieren Sie die oben aufgeführten Anforderungen als Erweiterung des Implementationsdiagramms aus Abbildung 2.

Erläutern Sie, auf welche Weise Sie die zweite und die dritte Anforderung in Ihrem Implementationsdiagramm umsetzen.

[13 Punkte]

Hinweis: Klassen, Methoden und Attribute des Implementationsdiagramms aus Abbildung 2, die unverändert bleiben, brauchen nicht dargestellt oder angegeben zu werden.

e)

Ein Schüler regt an, die Klassen Wetterstation und Messung durch eine neue Klasse Wetteraufzeichnung zu ersetzen. Nachfolgend sind Beispieldaten für Wetteraufzeichnungen abgebildet:

Stationsname

Stadt

Messwertart

Messwert

Zeitpunkt

Botanischer Garten · Berlin · Temperatur · 17.0 · 2020-08-04 09:01

Botanischer Garten · Berlin · Temperatur · 18.4 · 2020-08-04 10:02

Botanischer Garten · Berlin · Temperatur · 20.6 · 2020-08-04 12:07

Leuchtturm · Kiel · Windgeschwindigkeit · 2.0 · 2019-08-03 10:02

Leuchtturm · Kiel · Windgeschwindigkeit · 20.0 · 2019-12-31 12:07

Zugspitze · Garmisch-Partenkirchen · Temperatur · -10.3 · 2019-12-31 09:01

Zugspitze · Garmisch-Partenkirchen · Windgeschwindigkeit · 20.0 · 2019-12-31 09:01

Zugspitze · Garmisch-Partenkirchen · Temperatur · 4.0 · 2020-08-04 13:01

Zugspitze · Garmisch-Partenkirchen · Windgeschwindigkeit · 32.0 · 2020-08-04 13:01

Teststation · Soest

Abbildung 3: Beispieldaten für Wetteraufzeichnungen

Die Klasse Wetterdatenverwaltung würde in diesem Fall eine Liste mit Objekten der Klasse Wetteraufzeichnung verwalten.

Der Schüler meint, dass sich aus dieser einen Liste von Wetteraufzeichnungen ohnehin alle Informationen entnehmen ließen, dass sein Vorschlag leichter zu implementieren sei und dass er darüber hinaus keine nennenswerten Nachteile habe.

Beurteilen Sie die Aussage des Schülers.

[7 Punkte]

Aufgabenstellung: Wetterdatenverwaltung

Ein Projektkurs zum Thema „Klimawandel“ plant, eine Software zu entwickeln, mit der Wetterdaten verwaltet und analysiert werden können.

Als Grundlage dienen dem Kurs Daten von Wetterstationen aus ganz Deutschland, die jeweils einen eindeutigen Stationsnamen und eine Stadt besitzen. Je nach Ausstattung kann eine Wetterstation unterschiedliche Messwertarten erfassen (z. B. die Temperatur in °C oder die Windgeschwindigkeit in km/h). Zu jeder Messung werden Messwertart, Messwert und Zeitpunkt abgespeichert (vgl. Abbildung 1).

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

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Wetterdatenverwaltung

Objekte der Klasse Wetterdatenverwaltung verwalten Wetterstationen mit ihren Messungen.

Auszug aus der Dokumentation der Klasse Wetterdatenverwaltung

Wetterdatenverwaltung()

Ein Objekt der Klasse Wetterdatenverwaltung wird initialisiert.

List<Wetterstation> gibWetterstationen()

Eine Liste mit allen Wetterstationen wird zurückgeliefert.

Wetterstation gibWetterstation(String pStationsname)

Die Wetterstation mit dem Namen pStationsname wird zurückgeliefert. Wenn zu diesem Namen keine Wetterstation existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Wetterstation pWetterstation)

Die Wetterstation pWetterstation wird der Wetterdatenverwaltung hinzugefügt, wenn der Stationsname bisher noch nicht existiert. Sonst geschieht nichts.

void fuegeHinzu(Wetterstation pWetterstation, Messung pMessung)

Wenn die Wetterstation pWetterstation in der Wetterdatenverwaltung existiert, dann wird dieser Station die Messung pMessung hinzugefügt. Sonst geschieht nichts.

Double ermittleEtwas(String pMesswertart, int pJahr)

Diese Methode soll in Teilaufgabe b) analysiert werden.

Die Klasse Wetterstation

Objekte der Klasse Wetterstation verwalten ihren Stationsnamen, ihre Stadt und ihre Messungen.

Auszug aus der Dokumentation der Klasse Wetterstation

Wetterstation(String pStationsname, String pStadt)

Ein Objekt der Klasse Wetterstation wird mit dem Stationsnamen pStationsname und der Stadt pStadt initialisiert.

String gibStationsname()

Der Stationsname wird zurückgeliefert.

String gibStadt()

Die Stadt wird zurückgeliefert.

List<Messung> gibMessungen()

Eine Liste mit allen Messungen dieser Wetterstation wird zurückgeliefert.

void fuegeHinzu(Messung pMessung)

Die Messung pMessung wird hinzugefügt.

List<Messung> ermittleSortierteMessungen(String pMesswertart)

Diese Methode soll in Teilaufgabe c) hinzugefügt werden.

Die Klasse Messung

Objekte der Klasse Messung verwalten ihre Messwertart, ihren Messwert und ihren Zeitpunkt.

Auszug aus der Dokumentation der Klasse Messung

Messung(String pMesswertart, double pMesswert, int pJahr, int pMonat, int pTag, int pStunde, int pMinute)

Ein Objekt der Klasse Messung wird mit der Messwertart pMesswertart, dem Messwert pMesswert und dem Zeitpunkt der Messung initialisiert.

String gibMesswertart()

Die Messwertart wird zurückgeliefert.

double gibMesswert()

Der Messwert wird zurückgeliefert.

int gibJahr()

Das Jahr wird zurückgeliefert.

int gibMonat()

Der Monat wird zurückgeliefert.

int gibTag()

Der Tag wird zurückgeliefert.

int gibStunde()

Die Stunde wird zurückgeliefert.

int gibMinute()

Die Minute wird zurückgeliefert.

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) [12 Punkte]

Als das Projekt bereits weit fortgeschritten ist, stößt eine Schülerin in der Klasse Wetterdatenverwaltung auf die nicht dokumentierte Methode ermittleEtwas.

1 public Wetterstation ermittleEtwas(String pMesswertart,

2 int pJahr, int pMonat, int pTag) {

3 Wetterstation gesuchteStation = null;

4 Messung tempMessung = null;

5 wetterstationen.toFirst();

6 while (wetterstationen.hasAccess()) {

7 Wetterstation station = wetterstationen.getContent();

8 List<Messung> messungen = station.gibMessungen();

9 messungen.toFirst();

10 while (messungen.hasAccess()) {

11 Messung m = messungen.getContent();

12 if (m.gibMesswertart().equals(pMesswertart)

13 && m.gibJahr() == pJahr

14 && m.gibMonat() == pMonat

15 && m.gibTag() == pTag

16 && (gesuchteStation == null

17 || m.gibMesswert() > tempMessung.gibMesswert())) {

18 gesuchteStation = station;

19 tempMessung = m;

20 }

21 messungen.next();

22 }

23 wetterstationen.next();

24 }

25 return gesuchteStation;

26 }

Hinweis: Nehmen Sie an, dass die Wetterstationen in der Reihenfolge der Beispieldaten aus Abbildung 1 vorliegen.

Analysieren Sie die Methode und geben Sie die Rückgabewerte der folgenden drei Methodenaufrufe für die Beispieldaten aus Abbildung 1 an:

Erläutern Sie, in welchen Fällen die Methode null als Ergebnis liefert.

Entscheiden Sie, ob in Zeile 16 der Bedingungsteil gesuchteStation == null durch tempMessung == null ersetzt werden dürfte, und begründen Sie Ihre Entscheidung.

Erläutern Sie, welche Aufgabe die Methode im Sachzusammenhang erfüllt.

Teilaufgabe c) [13 Punkte]

In die Klasse Wetterstation soll die Methode ermittleSortierteMessungen aufgenommen werden. Für die über pMesswertart übergebene Messwertart soll sie die Messungen der jeweiligen Wetterstation als nach Messwerten aufsteigend sortierte Liste liefern. Liegen für die Wetterstation oder die Messwertart keine Messungen vor, soll eine leere Liste das Ergebnis sein.

Der Methodenkopf lautet:

public List<Messung> ermittleSortierteMessungen(String pMesswertart)

Entwickeln und erläutern Sie ein algorithmisches Vorgehen für diese Methode.

Implementieren Sie die Methode in Java.

public List<Messung> ermittleSortierteMessungen(String pMesswertart)

Ein neu gegründetes Startup in Köln vermietet Elektro-Roller, sogenannte Scooter. Jeder Scooter besitzt einen GPS-Empfänger und sendet per Internetverbindung jede Minute seine aktuelle Position (Standort) und seinen aktuellen Batterie-Zustand (Akkuladung) an den Server des Unternehmens. Damit sich der Abstand eines Scooters zur Firmenzentrale einfacher bestimmen lässt, geben die Scooter ihre Position relativ zur Firmenzentrale (Koordinatenursprung) an. Auf dem Server wird jeweils die zuletzt gemeldete Position als Punkt in einem Koordinatensystem abgelegt. Abbildung 1 stellt die momentane Lage in der näheren Umgebung der Firmenzentrale dar.

Das Unternehmen verwaltet die Scooter in einem binären Suchbaum. Als Suchschlüssel im Baum dient die eindeutige vierstellige (Serien-)Nummer eines Scooters.

Aktuell setzt das Unternehmen die vier in Abbildung 1 gezeigten Scooter ein. Der daraus entstehende binäre Suchbaum ist in Abbildung 2 zu sehen.

Die Software des Unternehmens verwaltet außer den Scooter-Daten auch die Daten der Kundinnen und Kunden, die einen Scooter mieten wollen. Vereinfachend ist modelliert, dass jede Kundin und jeder Kunde nur durch eine eindeutige E-Mail-Adresse sowie eine Kreditkartennummer für die Abrechnung beschrieben wird.

Grundlage der Softwareentwicklung ist der in Abbildung 3 gezeigte Ausschnitt des Implementationsdiagramms.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Scooter

Objekte dieser Klasse verwalten die Daten eines Scooters.

Methode / Konstruktor · Beschreibung

Scooter(int pNummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige Nummer pNummer wird gespeichert.

boolean isEqual(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, gleich der Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, kleiner als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isGreater(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, größer als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

int gibNummer() · Die Methode liefert die eindeutige Nummer des Scooters.

int gibAkkuladung() · Die Methode liefert den Batterie-Zustand des Scooters. Der Wert entspricht der Akkuladung in Prozent, d. h., der Wert liegt im Wertebereich 0 (Akku ist leer) bis 100 (Akku ist vollständig aufgeladen).

Kunde gibAusleiher() · Die Methode liefert das Objekt der Klasse Kunde, welches den Scooter momentan ausgeliehen hat. Ist der Scooter momentan nicht verliehen, so wird null zurückgegeben.

Standort gibStandort() · Die Methode liefert ein Objekt der Klasse Standort, welches die Koordinaten relativ zur Firmenzentrale enthält. Z. B. bedeutet der Standort (-300|400), dass sich der Scooter 300 Meter in westlicher Richtung und 400 Meter in nördlicher Richtung von der Firmenzentrale befindet.

void setzeAkkuladung(int pAkkuladung) · Die Methode verändert den Wert der Akkuladung auf den Wert pAkkuladung. Ist der Wert kleiner als 0 oder größer als 100, so geschieht nichts.

void setzeAusleiher(Kunde pAusleiher) · Die Methode speichert die Daten der Person, die den Scooter momentan ausgeliehen hat. Ist der Parameter pAusleiher gleich null, so ist der Scooter wieder frei und kann von jemand anderem ausgeliehen werden.

void setzeStandort(Standort pStandort) · Die Methode setzt den Standort des Scooters auf pStandort.

Die Klasse ScooterVerwaltung

Objekte dieser Klasse verwalten Scooter sowie Kundinnen und Kunden und ermöglichen die Ausleihe von Scootern.

Methode / Konstruktor · Beschreibung

ScooterVerwaltung() · Ein Objekt der Klasse wird initialisiert. Es verwaltet noch keine Scooter und keine Daten von Kundinnen und Kunden.

Scooter gibScooter(int pScooternummer) · Liefert das Scooter-Objekt mit der (Serien-)Nummer pScooternummer. Falls es kein Scooter-Objekt mit der entsprechenden (Serien-)Nummer gibt, dann wird null zurückgeliefert.

List<Kunde> ermittleWarnliste(int pDistanz) · Die Methode liefert eine Liste aller Kundinnen und Kunden, die sich mit ihrem ausgeliehenen Scooter um mehr als pDistanz Meter Luftlinie von der Firmenzentrale entfernt haben. Die Firmenzentrale befindet sich im Standort (0|0). Gibt es keine Kundin und keinen Kunden, die bzw. der sich zu weit entfernt hat, oder ist der Parameter pDistanz < 0, so wird eine leere Liste zurückgegeben. Scooter, die momentan nicht ausgeliehen wurden, sich aber in größerer Distanz befinden, werden nicht berücksichtigt, weil es keine Person gibt, an den eine Warnmeldung verschickt werden könnte.

List<Scooter> ermittleEtwas(List<Scooter> pScooterSammlung) · Die Methode wird in Teilaufgabe c) analysiert.

Die Klasse Kunde

Objekte dieser Klasse verwalten die Daten einer Kundin bzw. eines Kunden.

Methode / Konstruktor · Beschreibung

Kunde(String pEMailAdresse, String pKreditkartennummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige E-Mail-Adresse pEMailAdresse der Kundin bzw. des Kunden und die zugehörige Kreditkartennummer pKreditkartennummer werden gespeichert.

String gibEMailAdresse() · Die eindeutige E-Mail-Adresse der Kundin bzw. des Kunden wird zurückgeliefert.

String gibKreditkartennummer() · Die Kreditkartennummer der Kundin bzw. des Kunden wird zurückgeliefert.

Die Klasse Standort

Objekte dieser Klasse verwalten die Koordinaten eines Standorts für Scooter. Die Koordinaten werden relativ zur Firmenzentrale gespeichert, welche sich im Koordinatenursprung befindet.

Methode / Konstruktor · Beschreibung

Standort(int pX, int pY) · Ein Objekt der Klasse wird initialisiert. Die Koordinaten (pX|pY) werden im Objekt gespeichert.

int liefereDistanz(Standort pOrt) · Die auf volle Meter abgerundete Distanz (Luftlinie in Metern) zwischen dem gespeicherten Ort und dem durch pOrt referenzierten Ort wird zurückgegeben. Sollte pOrt den Wert null haben, so wird der Wert 0 zurückgegeben.

int gibX() · Die x-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in westlicher (bei negativem Wert) bzw. in östlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

int gibY() · Die y-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in südlicher (bei negativem Wert) bzw. in nördlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

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 / Konstruktor · 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 der 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 der Liste 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.

Die generische Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

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.

Methode / Konstruktor · Beschreibung

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.

Methode · Beschreibung

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.

a)

Weitere Scooter des Unternehmens sollen in den bestehenden Datenbestand aufgenommen werden. Als Erstes werden die vier Scooter mit den Nummern 4999, 4400, 1000 und 8500 genau in dieser Reihenfolge in den Suchbaum aus Abbildung 2 eingefügt.

Stellen Sie den Suchbaum, der nach dem Einfügen vorliegt, grafisch dar.

Stellen Sie den Suchbaum grafisch dar, der sich aus dem Suchbaum mit den acht Suchschlüsseln ergibt, wenn der Scooter mit der Nummer 4671 gestohlen wurde und daher aus dem System entfernt werden muss.

d)

Wenn Scooter sehr weit von der Firmenzentrale entfernt sind, kann die Drohne sie abends nicht mehr gut anfliegen. Daher sollen Kundinnen und Kunden, die sich z. B. mehr als 10 000 Meter von der Firmenzentrale entfernen, per hinterlegter E-Mail-Adresse gewarnt werden.

Um die Liste aller Personen zu bestimmen, die eine solche Warnmeldung bekommen sollen, bietet die Klasse ScooterVerwaltung die Methode ermittleWarnliste an, die folgenden Methodenkopf hat:

public List<Kunde> ermittleWarnliste(int pDistanz)

Die Dokumentation der Methode befindet sich in der Anlage.

Entwickeln Sie eine Strategie für den Algorithmus dieser Methode.

Implementieren Sie die Methode gemäß der Dokumentation.

e)

Ein Praktikant bemerkt, dass die Entfernung eines Scooters zur Firmenzentrale in mehreren Zusammenhängen eine zentrale Information ist, und nennt dafür zwei Beispiele:

Bei entliehenen Scootern spielt die Entfernung etwa beim Versenden von Warnmeldungen für zu weit entfernte Scooter eine Rolle.

Bei nicht entliehenen Scootern ist sie hingegen ein wichtiges Kriterium für den Flug der Drohne, welche kontrolliert, ob vorschriftsmäßig geparkt wurde.

Deshalb regt er an, im binären Suchbaum die Entfernung zwischen Scooter und Firmenzentrale als Sortierkriterium zu nutzen.

Ein neu gegründetes Startup in Köln vermietet Elektro-Roller, sogenannte Scooter. Jeder Scooter besitzt einen GPS-Empfänger und sendet per Internetverbindung jede Minute seine aktuelle Position (Standort) und seinen aktuellen Batterie-Zustand (Akkuladung) an den Server des Unternehmens. Damit sich der Abstand eines Scooters zur Firmenzentrale einfacher bestimmen lässt, geben die Scooter ihre Position relativ zur Firmenzentrale (Koordinatenursprung) an. Auf dem Server wird jeweils die zuletzt gemeldete Position als Punkt in einem Koordinatensystem abgelegt. Abbildung 1 stellt die momentane Lage in der näheren Umgebung der Firmenzentrale dar.

Das Unternehmen verwaltet die Scooter in einem binären Suchbaum. Als Suchschlüssel im Baum dient die eindeutige vierstellige (Serien-)Nummer eines Scooters.

Aktuell setzt das Unternehmen die vier in Abbildung 1 gezeigten Scooter ein. Der daraus entstehende binäre Suchbaum ist in Abbildung 2 zu sehen.

Die Software des Unternehmens verwaltet außer den Scooter-Daten auch die Daten der Kundinnen und Kunden, die einen Scooter mieten wollen. Vereinfachend ist modelliert, dass jede Kundin und jeder Kunde nur durch eine eindeutige E-Mail-Adresse sowie eine Kreditkartennummer für die Abrechnung beschrieben wird.

Grundlage der Softwareentwicklung ist der in Abbildung 3 gezeigte Ausschnitt des Implementationsdiagramms.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Scooter

Objekte dieser Klasse verwalten die Daten eines Scooters.

Methode / Konstruktor · Beschreibung

Scooter(int pNummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige Nummer pNummer wird gespeichert.

boolean isEqual(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, gleich der Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, kleiner als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isGreater(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, größer als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

int gibNummer() · Die Methode liefert die eindeutige Nummer des Scooters.

int gibAkkuladung() · Die Methode liefert den Batterie-Zustand des Scooters. Der Wert entspricht der Akkuladung in Prozent, d. h., der Wert liegt im Wertebereich 0 (Akku ist leer) bis 100 (Akku ist vollständig aufgeladen).

Kunde gibAusleiher() · Die Methode liefert das Objekt der Klasse Kunde, welches den Scooter momentan ausgeliehen hat. Ist der Scooter momentan nicht verliehen, so wird null zurückgegeben.

Standort gibStandort() · Die Methode liefert ein Objekt der Klasse Standort, welches die Koordinaten relativ zur Firmenzentrale enthält. Z. B. bedeutet der Standort (-300|400), dass sich der Scooter 300 Meter in westlicher Richtung und 400 Meter in nördlicher Richtung von der Firmenzentrale befindet.

void setzeAkkuladung(int pAkkuladung) · Die Methode verändert den Wert der Akkuladung auf den Wert pAkkuladung. Ist der Wert kleiner als 0 oder größer als 100, so geschieht nichts.

void setzeAusleiher(Kunde pAusleiher) · Die Methode speichert die Daten der Person, die den Scooter momentan ausgeliehen hat. Ist der Parameter pAusleiher gleich null, so ist der Scooter wieder frei und kann von jemand anderem ausgeliehen werden.

void setzeStandort(Standort pStandort) · Die Methode setzt den Standort des Scooters auf pStandort.

Die Klasse ScooterVerwaltung

Objekte dieser Klasse verwalten Scooter sowie Kundinnen und Kunden und ermöglichen die Ausleihe von Scootern.

Methode / Konstruktor · Beschreibung

ScooterVerwaltung() · Ein Objekt der Klasse wird initialisiert. Es verwaltet noch keine Scooter und keine Daten von Kundinnen und Kunden.

Scooter gibScooter(int pScooternummer) · Liefert das Scooter-Objekt mit der (Serien-)Nummer pScooternummer. Falls es kein Scooter-Objekt mit der entsprechenden (Serien-)Nummer gibt, dann wird null zurückgeliefert.

List<Kunde> ermittleWarnliste(int pDistanz) · Die Methode liefert eine Liste aller Kundinnen und Kunden, die sich mit ihrem ausgeliehenen Scooter um mehr als pDistanz Meter Luftlinie von der Firmenzentrale entfernt haben. Die Firmenzentrale befindet sich im Standort (0|0). Gibt es keine Kundin und keinen Kunden, die bzw. der sich zu weit entfernt hat, oder ist der Parameter pDistanz < 0, so wird eine leere Liste zurückgegeben. Scooter, die momentan nicht ausgeliehen wurden, sich aber in größerer Distanz befinden, werden nicht berücksichtigt, weil es keine Person gibt, an den eine Warnmeldung verschickt werden könnte.

List<Scooter> ermittleEtwas(List<Scooter> pScooterSammlung) · Die Methode wird in Teilaufgabe c) analysiert.

Die Klasse Kunde

Objekte dieser Klasse verwalten die Daten einer Kundin bzw. eines Kunden.

Methode / Konstruktor · Beschreibung

Kunde(String pEMailAdresse, String pKreditkartennummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige E-Mail-Adresse pEMailAdresse der Kundin bzw. des Kunden und die zugehörige Kreditkartennummer pKreditkartennummer werden gespeichert.

String gibEMailAdresse() · Die eindeutige E-Mail-Adresse der Kundin bzw. des Kunden wird zurückgeliefert.

String gibKreditkartennummer() · Die Kreditkartennummer der Kundin bzw. des Kunden wird zurückgeliefert.

Die Klasse Standort

Objekte dieser Klasse verwalten die Koordinaten eines Standorts für Scooter. Die Koordinaten werden relativ zur Firmenzentrale gespeichert, welche sich im Koordinatenursprung befindet.

Methode / Konstruktor · Beschreibung

Standort(int pX, int pY) · Ein Objekt der Klasse wird initialisiert. Die Koordinaten (pX|pY) werden im Objekt gespeichert.

int liefereDistanz(Standort pOrt) · Die auf volle Meter abgerundete Distanz (Luftlinie in Metern) zwischen dem gespeicherten Ort und dem durch pOrt referenzierten Ort wird zurückgegeben. Sollte pOrt den Wert null haben, so wird der Wert 0 zurückgegeben.

int gibX() · Die x-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in westlicher (bei negativem Wert) bzw. in östlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

int gibY() · Die y-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in südlicher (bei negativem Wert) bzw. in nördlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

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 / Konstruktor · 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 der 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 der Liste 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.

Die generische Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

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.

Methode / Konstruktor · Beschreibung

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.

Methode · Beschreibung

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.

b)

Erläutern Sie, wie die Klassen ScooterVerwaltung, Scooter, Kunde, List und BinarySearchTree untereinander und mit dem Interface ComparableContent zusammenhängen.

Begründen Sie bezogen auf den Sachkontext, warum es effizienter ist, die Scooter in einem binären Suchbaum statt in einer linearen Liste zu verwalten, während es für die Kundinnen und Kunden vertretbar ist, eine Liste zu verwenden.

Ein neu gegründetes Startup in Köln vermietet Elektro-Roller, sogenannte Scooter. Jeder Scooter besitzt einen GPS-Empfänger und sendet per Internetverbindung jede Minute seine aktuelle Position (Standort) und seinen aktuellen Batterie-Zustand (Akkuladung) an den Server des Unternehmens. Damit sich der Abstand eines Scooters zur Firmenzentrale einfacher bestimmen lässt, geben die Scooter ihre Position relativ zur Firmenzentrale (Koordinatenursprung) an. Auf dem Server wird jeweils die zuletzt gemeldete Position als Punkt in einem Koordinatensystem abgelegt. Abbildung 1 stellt die momentane Lage in der näheren Umgebung der Firmenzentrale dar.

Das Unternehmen verwaltet die Scooter in einem binären Suchbaum. Als Suchschlüssel im Baum dient die eindeutige vierstellige (Serien-)Nummer eines Scooters.

Aktuell setzt das Unternehmen die vier in Abbildung 1 gezeigten Scooter ein. Der daraus entstehende binäre Suchbaum ist in Abbildung 2 zu sehen.

Die Software des Unternehmens verwaltet außer den Scooter-Daten auch die Daten der Kundinnen und Kunden, die einen Scooter mieten wollen. Vereinfachend ist modelliert, dass jede Kundin und jeder Kunde nur durch eine eindeutige E-Mail-Adresse sowie eine Kreditkartennummer für die Abrechnung beschrieben wird.

Grundlage der Softwareentwicklung ist der in Abbildung 3 gezeigte Ausschnitt des Implementationsdiagramms.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Scooter

Objekte dieser Klasse verwalten die Daten eines Scooters.

Methode / Konstruktor · Beschreibung

Scooter(int pNummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige Nummer pNummer wird gespeichert.

boolean isEqual(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, gleich der Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isLess(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, kleiner als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

boolean isGreater(Scooter pComparableContent) · Wenn die eindeutige Nummer des Scooter-Objekts, von dem die Methode aufgerufen wird, größer als die Nummer des Scooter-Objekts pComparableContent ist, wird true geliefert. Sonst wird false geliefert.

int gibNummer() · Die Methode liefert die eindeutige Nummer des Scooters.

int gibAkkuladung() · Die Methode liefert den Batterie-Zustand des Scooters. Der Wert entspricht der Akkuladung in Prozent, d. h., der Wert liegt im Wertebereich 0 (Akku ist leer) bis 100 (Akku ist vollständig aufgeladen).

Kunde gibAusleiher() · Die Methode liefert das Objekt der Klasse Kunde, welches den Scooter momentan ausgeliehen hat. Ist der Scooter momentan nicht verliehen, so wird null zurückgegeben.

Standort gibStandort() · Die Methode liefert ein Objekt der Klasse Standort, welches die Koordinaten relativ zur Firmenzentrale enthält. Z. B. bedeutet der Standort (-300|400), dass sich der Scooter 300 Meter in westlicher Richtung und 400 Meter in nördlicher Richtung von der Firmenzentrale befindet.

void setzeAkkuladung(int pAkkuladung) · Die Methode verändert den Wert der Akkuladung auf den Wert pAkkuladung. Ist der Wert kleiner als 0 oder größer als 100, so geschieht nichts.

void setzeAusleiher(Kunde pAusleiher) · Die Methode speichert die Daten der Person, die den Scooter momentan ausgeliehen hat. Ist der Parameter pAusleiher gleich null, so ist der Scooter wieder frei und kann von jemand anderem ausgeliehen werden.

void setzeStandort(Standort pStandort) · Die Methode setzt den Standort des Scooters auf pStandort.

Die Klasse ScooterVerwaltung

Objekte dieser Klasse verwalten Scooter sowie Kundinnen und Kunden und ermöglichen die Ausleihe von Scootern.

Methode / Konstruktor · Beschreibung

ScooterVerwaltung() · Ein Objekt der Klasse wird initialisiert. Es verwaltet noch keine Scooter und keine Daten von Kundinnen und Kunden.

Scooter gibScooter(int pScooternummer) · Liefert das Scooter-Objekt mit der (Serien-)Nummer pScooternummer. Falls es kein Scooter-Objekt mit der entsprechenden (Serien-)Nummer gibt, dann wird null zurückgeliefert.

List<Kunde> ermittleWarnliste(int pDistanz) · Die Methode liefert eine Liste aller Kundinnen und Kunden, die sich mit ihrem ausgeliehenen Scooter um mehr als pDistanz Meter Luftlinie von der Firmenzentrale entfernt haben. Die Firmenzentrale befindet sich im Standort (0|0). Gibt es keine Kundin und keinen Kunden, die bzw. der sich zu weit entfernt hat, oder ist der Parameter pDistanz < 0, so wird eine leere Liste zurückgegeben. Scooter, die momentan nicht ausgeliehen wurden, sich aber in größerer Distanz befinden, werden nicht berücksichtigt, weil es keine Person gibt, an den eine Warnmeldung verschickt werden könnte.

List<Scooter> ermittleEtwas(List<Scooter> pScooterSammlung) · Die Methode wird in Teilaufgabe c) analysiert.

Die Klasse Kunde

Objekte dieser Klasse verwalten die Daten einer Kundin bzw. eines Kunden.

Methode / Konstruktor · Beschreibung

Kunde(String pEMailAdresse, String pKreditkartennummer) · Ein Objekt der Klasse wird initialisiert. Die eindeutige E-Mail-Adresse pEMailAdresse der Kundin bzw. des Kunden und die zugehörige Kreditkartennummer pKreditkartennummer werden gespeichert.

String gibEMailAdresse() · Die eindeutige E-Mail-Adresse der Kundin bzw. des Kunden wird zurückgeliefert.

String gibKreditkartennummer() · Die Kreditkartennummer der Kundin bzw. des Kunden wird zurückgeliefert.

Die Klasse Standort

Objekte dieser Klasse verwalten die Koordinaten eines Standorts für Scooter. Die Koordinaten werden relativ zur Firmenzentrale gespeichert, welche sich im Koordinatenursprung befindet.

Methode / Konstruktor · Beschreibung

Standort(int pX, int pY) · Ein Objekt der Klasse wird initialisiert. Die Koordinaten (pX|pY) werden im Objekt gespeichert.

int liefereDistanz(Standort pOrt) · Die auf volle Meter abgerundete Distanz (Luftlinie in Metern) zwischen dem gespeicherten Ort und dem durch pOrt referenzierten Ort wird zurückgegeben. Sollte pOrt den Wert null haben, so wird der Wert 0 zurückgegeben.

int gibX() · Die x-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in westlicher (bei negativem Wert) bzw. in östlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

int gibY() · Die y-Koordinate des Standorts wird zurückgeliefert. Diese entspricht der Entfernung in südlicher (bei negativem Wert) bzw. in nördlicher (bei positivem Wert) Richtung in Metern von der Firmenzentrale.

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 / Konstruktor · 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 der 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 der Liste 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.

Die generische Klasse BinarySearchTree<ContentType extends ComparableContent<ContentType>>

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.

Methode / Konstruktor · Beschreibung

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.

Methode · Beschreibung

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.

Allabendlich soll kontrolliert werden, ob sämtliche Scooter regelkonform abgestellt sind. Dafür setzt das Unternehmen eine Drohne ein, die am Abend jeden Scooter anfliegt und von ihm ein Foto an die Firmenzentrale übermittelt.

c) Ein Praktikant hat in der Klasse ScooterVerwaltung die folgende Methode programmiert.

1 public List<Scooter> ermittleEtwas(

2 List<Scooter> pScooterSammlung) {

3 Standort ort = new Standort(0, 0);

4 List<Scooter> ergebnis = new List<Scooter>();

5 while (!pScooterSammlung.isEmpty()) {

6 pScooterSammlung.toFirst();

7 Scooter naechster = pScooterSammlung.getContent();

8 pScooterSammlung.next();

9 while (pScooterSammlung.hasAccess()) {

10 Scooter test = pScooterSammlung.getContent();

11 if (ort.liefereDistanz(test.gibStandort())

12 < ort.liefereDistanz(naechster.gibStandort())) {

13 naechster = test;

14 }

15 pScooterSammlung.next();

16 }

17 pScooterSammlung.toFirst();

18 while (pScooterSammlung.getContent() != naechster) {

19 pScooterSammlung.next();

20 }

21 pScooterSammlung.remove();

22 ergebnis.append(naechster);

23 ort = naechster.gibStandort();

24 }

25 return ergebnis;

26 }

Angenommen, ermittleEtwas wird mit dem Parameter pScooterSammlung aufgerufen, der auf eine Liste verweist, welche die in Abbildung 1 gezeigten Scooter in der Reihenfolge 4588, 4671, 1341 und 5001 enthält.

Analysieren Sie den Quelltext der Methode, indem Sie ihn auf die Beispieldaten anwenden und die dabei entstehende Rückgabe-Liste ermitteln.

Erläutern Sie, wie die Methode arbeitet.

Erläutern Sie bezogen auf den Sachkontext, welche Information die Methode zurückgibt.

[12 Punkte]

Aufgabenstellung: Einkaufslisten-App

Ein Unternehmen plant die Entwicklung einer App, mit der sich mehrere Einkaufslisten anlegen und verwalten lassen.

Zur Registrierung sind für alle Nutzerinnen und Nutzer der eigene Name, ein eindeutiger Benutzername und ein Passwort erforderlich. Mehrere Personen können außerdem gemeinsam eine Einkaufsliste verwalten.

Damit das Anlegen einer Einkaufsliste einfacher wird, sind im System bereits zahlreiche Produkte hinterlegt, die ausgewählt werden können. Selbstverständlich dürfen Nutzerinnen und Nutzer auch eigene neue Produkte ergänzen.

Das Unternehmen speichert seine Daten in einer relationalen Datenbank, die auf einem über das Internet erreichbaren Datenbank-Server liegt und mit Benutzername und Passwort zugänglich ist. Ein Teil der Modellierung dieser Datenbank wird nachfolgend gezeigt.

Das folgende Datenbankschema gibt die Modellierung der Datenbank wieder. Im Anhang stehen Beispieldatensätze zu diesem Schema.

Anlage: Beispieldaten der Datenbank

Einkaufsliste

ID · Titel

14 · Salatliste

15 · Biomarkt

16 · Hamstern

17 · Einkaufen

18 · Geburtstagsfeier

19 · Biomarkt

Kategorie

Name

Backwaren

Getränke

Hygieneartikel

Kühlprodukte

Obst/Gemüse

Süßspeisen

Tiefkühlprodukte

Produkt

Bezeichnung · Kategorie

Schafskäse · Kühlprodukte

Gouda · Kühlprodukte

Hefe · Kühlprodukte

Brot · Backwaren

Baguette · Backwaren

Paprika · Obst/Gemüse

Gurke · Obst/Gemüse

Salat · Obst/Gemüse

Salamipizza · Tiefkühlprodukte

Erbsen · Tiefkühlprodukte

Schokolade · Süßspeisen

Bonbons · Süßspeisen

Limonade · Getränke

Klopapier · Hygieneartikel

Biomango · Obst/Gemüse

Benutzer

Benutzername · Vorname · Nachname · Passwort 1

FabBen · Ben · Lovelace · ab4bd73e2123ddef3

JaStIn · Jana · Strehl · 3e2123ddef3ab4bd7

Edelweiss · Julian · Beton · ab4bd7ab4bd7eefde

Pudelski · Laura · Pudelski · bd7ab4bd7eef00e0e

Linus · Knut · Bremhorst · ef0023ddef3ab47ea

1 Die Passwörter werden nicht im Klartext, sondern verschlüsselt in der Datenbank gespeichert.

gehoertZu

EinkaufslisteID · Benutzername

14 · Linus

15 · FabBen

16 · FabBen

16 · Linus

17 · Linus

18 · FabBen

19 · JaStIn

stehtAuf

ProduktBezeichnung · EinkaufslisteID · Menge

Schafskäse · 14 · 2

Schokolade · 15 · 3

Salat · 14 · 1

Paprika · 14 · 1

Limonade · 18 · 24

Bonbons · 18 · 3

Brot · 16 · 5

Gouda · 15 · 1

Brot · 18 · 3

Gurke · 17 · 2

Paprika · 17 · 1

Baguette · 18 · 6

Salamipizza · 17 · 3

Schafskäse · 15 · 2

Schokolade · 18 · 1

Erbsen · 18 · 1

Schokolade · 17 · 2

Hefe · 17 · 1

Hefe · 16 · 12

Klopapier · 16 · 25

Anhang: Dokumentationen der Klassen

Die Klasse EinkaufslistenApp

Ein Objekt der Klasse EinkaufslistenApp verwaltet eine aus der passenden Datenbank geladene Einkaufsliste.

Ausschnitt aus der Dokumentation der Klasse EinkaufslistenApp

EinkaufslistenApp(String pBenutzername, String pPasswort)

Ein neues Objekt der Klasse wird mit den Parametern pBenutzername und pPasswort initialisiert.

int[] ladeListenIDs()

Die Methode lädt die IDs der Einkaufslisten aus der Datenbank, die der angemeldeten Person zugeordnet sind, und gibt sie zurück.

void ladeListe(int pID)

Die Methode lädt die Einträge der mit der ID identifizierten Einkaufsliste aus der Datenbank und speichert sie. Existiert die ID nicht, ist keine Benutzerin bzw. kein Benutzer angemeldet oder gehört die Einkaufsliste mit der übergebenen ID nicht zu dem Benutzernamen, so wird keine Einkaufsliste gespeichert.

int gibAktuelleID()

Die Methode liefert die ID zu der aktuell geladenen Einkaufsliste. Ist keine Einkaufsliste geladen, wird -1 zurückgegeben.

List<Eintrag> gibAktuelleEintraege()

Die Methode liefert die Einträge der aktuellen Einkaufsliste in einem Objekt der Klasse Liste<Eintrag>. Ist keine aktuelle Einkaufsliste geladen, so wird null zurückgegeben.

Dokumentation der privaten Methode pruefeBenutzerZugriff

boolean pruefeBenutzerZugriff(int pID)

Die Methode prüft anhand eines Datenbankzugriffs, ob die über den Parameter identifizierte Einkaufsliste zu dem angemeldeten Benutzer gehört. In diesem Fall liefert sie den Wert true als Rückgabe, in allen anderen Fällen liefert sie den Wert false als Rückgabe.

Die Klasse Eintrag

Ein Objekt der Klasse Eintrag verwaltet ein aus der passenden Datenbank geladenes Produkt sowie die für die zugehörige Einkaufsliste gespeicherte Menge.

Ausschnitt aus der Dokumentation der Klasse Eintrag

Eintrag(Produkt pProdukt, int pMenge)

Ein neues Objekt der Klasse wird mit den Parametern pProdukt und pMenge initialisiert.

void setzeErledigt(boolean pErledigt)

Die Methode speichert, ob der Eintrag erledigt ist.

boolean istErledigt()

Die Methode liefert, ob der Eintrag erledigt ist.

int gibMenge()

Die Methode liefert die gespeicherte Menge des Eintrags.

Produkt gibProdukt()

Die Methode liefert das Produkt zu dem Eintrag.

Die Klasse Produkt

Ein Objekt der Klasse Produkt repräsentiert ein aus der passenden Datenbank geladenes Produkt.

Ausschnitt aus der Dokumentation der Klasse Produkt

Produkt(String pBezeichnung, String pKategorie)

Ein neues Objekt der Klasse wird mit den Parametern pBezeichnung und pKategorie initialisiert.

String gibBezeichnung()

Die Methode liefert die gespeicherte Bezeichnung des Produkts.

String gibKategorie()

Die Methode liefert die Kategorie des Produkts.

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.

Die Klasse DatabaseConnector

Ein Objekt der Klasse DatabaseConnector ermöglicht die Abfrage und Manipulation einer relationalen Datenbank. Beim Erzeugen des Objekts wird eine Datenbankverbindung aufgebaut, sodass anschließend SQL-Anweisungen an diese Datenbank gerichtet werden können.

Dokumentation der Klasse DatabaseConnector

DatabaseConnector(String pIP, int pPort, String pDatabase, String pUsername, String pPassword)

Ein Objekt vom Typ DatabaseConnector wird erstellt, und eine Verbindung zur Datenbank wird aufgebaut. Mit den Parametern pIP und pPort werden die IP-Adresse und die Port-Nummer übergeben, unter denen die Datenbank mit Namen pDatabase zu erreichen ist. Mit den Parametern pUsername und pPassword werden Benutzername und Passwort für die Datenbank übergeben.

void executeStatement(String pSQLStatement)

Der Auftrag schickt den im Parameter pSQLStatement enthaltenen SQL-Befehl an die Datenbank ab. Handelt es sich bei pSQLStatement um einen SQL-Befehl, der eine Ergebnismenge liefert, so kann dieses Ergebnis anschließend mit der Methode getCurrentQueryResult abgerufen werden.

QueryResult getCurrentQueryResult()

Die Anfrage liefert das Ergebnis des letzten mit der Methode executeStatement an die Datenbank geschickten SQL-Befehls als Objekt vom Typ QueryResult zurück. Wurde bisher kein SQL-Befehl abgeschickt oder ergab der letzte Aufruf von executeStatement keine Ergebnismenge (z. B. bei einem INSERT-Befehl oder einem Syntaxfehler), so wird null geliefert.

String getErrorMessage()

Die Anfrage liefert null oder eine Fehlermeldung, die sich jeweils auf die letzte zuvor ausgeführte Datenbankoperation bezieht.

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

Ein Objekt der Klasse QueryResult stellt die Ergebnistabelle einer Datenbankanfrage mit Hilfe der Klasse DatabaseConnector dar. Objekte dieser Klasse werden nur von der Klasse DatabaseConnector erstellt. Die Klasse verfügt über keinen öffentlichen Konstruktor.

Dokumentation der Klasse QueryResult

String[][] getData()

Die Anfrage liefert die Einträge der Ergebnistabelle als zweidimensionales Feld vom Typ String. Der erste Index des Feldes stellt die Zeile und der zweite die Spalte dar (d. h. String[zeile][spalte]).

String[] getColumnNames()

Die Anfrage liefert die Bezeichner der Spalten der Ergebnistabelle als Feld vom Typ String zurück.

String[] getColumnTypes()

Die Anfrage liefert die Typenbezeichnung der Spalten der Ergebnistabelle als Feld vom Typ String zurück. Die Bezeichnungen entsprechen den Angaben in der Datenbank.

int getRowCount()

Die Anfrage liefert die Anzahl der Zeilen der Ergebnistabelle als int.

int getColumnCount()

Die Anfrage liefert die Anzahl der Spalten der Ergebnistabelle als int.

Teilaufgabe a)

a)

Erläutern Sie, welche Bedeutung der Beziehungstyp stehtAuf im gegebenen Sachzusammenhang hat.

Begründen Sie, weshalb es vorteilhafter ist, einen Entitätstyp Kategorie zu modellieren, anstatt lediglich ein Attribut mit dem Bezeichner Kategorie im Entitätstyp Produkt zu modellieren, falls Nutzerinnen und Nutzer neue Produkte anlegen können.

[8 Punkte]

Teilaufgabe d)

d)

Erläutern Sie die Assoziationen, die in Abbildung 5 zu sehen sind, im Sachkontext.

Vergleichen Sie das Implementationsdiagramm in Abbildung 5 mit dem Entity-Relationship-Diagramm in Abbildung 2 und erläutern Sie Gemeinsamkeiten sowie Unterschiede hinsichtlich der Daten, die in der App bzw. in der Datenbank modelliert werden.

Hinweis: Ziehen Sie hierfür zusätzlich die Dokumentationen im Anhang heran.

[14 Punkte]

Aufgabenstellung: Einkaufslisten-App

Ein Unternehmen plant die Entwicklung einer App, mit der sich mehrere Einkaufslisten anlegen und verwalten lassen.

Zur Registrierung sind für alle Nutzerinnen und Nutzer der eigene Name, ein eindeutiger Benutzername und ein Passwort erforderlich. Mehrere Personen können außerdem gemeinsam eine Einkaufsliste verwalten.

Damit das Anlegen einer Einkaufsliste einfacher wird, sind im System bereits zahlreiche Produkte hinterlegt, die ausgewählt werden können. Selbstverständlich dürfen Nutzerinnen und Nutzer auch eigene neue Produkte ergänzen.

Das Unternehmen speichert seine Daten in einer relationalen Datenbank, die auf einem über das Internet erreichbaren Datenbank-Server liegt und mit Benutzername und Passwort zugänglich ist. Ein Teil der Modellierung dieser Datenbank wird nachfolgend gezeigt.

Das folgende Datenbankschema gibt die Modellierung der Datenbank wieder. Im Anhang stehen Beispieldatensätze zu diesem Schema.

Anlage: Beispieldaten der Datenbank

Einkaufsliste

ID · Titel

14 · Salatliste

15 · Biomarkt

16 · Hamstern

17 · Einkaufen

18 · Geburtstagsfeier

19 · Biomarkt

Kategorie

Name

Backwaren

Getränke

Hygieneartikel

Kühlprodukte

Obst/Gemüse

Süßspeisen

Tiefkühlprodukte

Produkt

Bezeichnung · Kategorie

Schafskäse · Kühlprodukte

Gouda · Kühlprodukte

Hefe · Kühlprodukte

Brot · Backwaren

Baguette · Backwaren

Paprika · Obst/Gemüse

Gurke · Obst/Gemüse

Salat · Obst/Gemüse

Salamipizza · Tiefkühlprodukte

Erbsen · Tiefkühlprodukte

Schokolade · Süßspeisen

Bonbons · Süßspeisen

Limonade · Getränke

Klopapier · Hygieneartikel

Biomango · Obst/Gemüse

Benutzer

Benutzername · Vorname · Nachname · Passwort 1

FabBen · Ben · Lovelace · ab4bd73e2123ddef3

JaStIn · Jana · Strehl · 3e2123ddef3ab4bd7

Edelweiss · Julian · Beton · ab4bd7ab4bd7eefde

Pudelski · Laura · Pudelski · bd7ab4bd7eef00e0e

Linus · Knut · Bremhorst · ef0023ddef3ab47ea

1 Die Passwörter werden nicht im Klartext, sondern verschlüsselt in der Datenbank gespeichert.

gehoertZu

EinkaufslisteID · Benutzername

14 · Linus

15 · FabBen

16 · FabBen

16 · Linus

17 · Linus

18 · FabBen

19 · JaStIn

stehtAuf

ProduktBezeichnung · EinkaufslisteID · Menge

Schafskäse · 14 · 2

Schokolade · 15 · 3

Salat · 14 · 1

Paprika · 14 · 1

Limonade · 18 · 24

Bonbons · 18 · 3

Brot · 16 · 5

Gouda · 15 · 1

Brot · 18 · 3

Gurke · 17 · 2

Paprika · 17 · 1

Baguette · 18 · 6

Salamipizza · 17 · 3

Schafskäse · 15 · 2

Schokolade · 18 · 1

Erbsen · 18 · 1

Schokolade · 17 · 2

Hefe · 17 · 1

Hefe · 16 · 12

Klopapier · 16 · 25

Anhang: Dokumentationen der Klassen

Die Klasse EinkaufslistenApp

Ein Objekt der Klasse EinkaufslistenApp verwaltet eine aus der passenden Datenbank geladene Einkaufsliste.

Ausschnitt aus der Dokumentation der Klasse EinkaufslistenApp

EinkaufslistenApp(String pBenutzername, String pPasswort)

Ein neues Objekt der Klasse wird mit den Parametern pBenutzername und pPasswort initialisiert.

int[] ladeListenIDs()

Die Methode lädt die IDs der Einkaufslisten aus der Datenbank, die der angemeldeten Person zugeordnet sind, und gibt sie zurück.

void ladeListe(int pID)

Die Methode lädt die Einträge der mit der ID identifizierten Einkaufsliste aus der Datenbank und speichert sie. Existiert die ID nicht, ist keine Benutzerin bzw. kein Benutzer angemeldet oder gehört die Einkaufsliste mit der übergebenen ID nicht zu dem Benutzernamen, so wird keine Einkaufsliste gespeichert.

int gibAktuelleID()

Die Methode liefert die ID zu der aktuell geladenen Einkaufsliste. Ist keine Einkaufsliste geladen, wird -1 zurückgegeben.

List<Eintrag> gibAktuelleEintraege()

Die Methode liefert die Einträge der aktuellen Einkaufsliste in einem Objekt der Klasse Liste<Eintrag>. Ist keine aktuelle Einkaufsliste geladen, so wird null zurückgegeben.

Dokumentation der privaten Methode pruefeBenutzerZugriff

boolean pruefeBenutzerZugriff(int pID)

Die Methode prüft anhand eines Datenbankzugriffs, ob die über den Parameter identifizierte Einkaufsliste zu dem angemeldeten Benutzer gehört. In diesem Fall liefert sie den Wert true als Rückgabe, in allen anderen Fällen liefert sie den Wert false als Rückgabe.

Die Klasse Eintrag

Ein Objekt der Klasse Eintrag verwaltet ein aus der passenden Datenbank geladenes Produkt sowie die für die zugehörige Einkaufsliste gespeicherte Menge.

Ausschnitt aus der Dokumentation der Klasse Eintrag

Eintrag(Produkt pProdukt, int pMenge)

Ein neues Objekt der Klasse wird mit den Parametern pProdukt und pMenge initialisiert.

void setzeErledigt(boolean pErledigt)

Die Methode speichert, ob der Eintrag erledigt ist.

boolean istErledigt()

Die Methode liefert, ob der Eintrag erledigt ist.

int gibMenge()

Die Methode liefert die gespeicherte Menge des Eintrags.

Produkt gibProdukt()

Die Methode liefert das Produkt zu dem Eintrag.

Die Klasse Produkt

Ein Objekt der Klasse Produkt repräsentiert ein aus der passenden Datenbank geladenes Produkt.

Ausschnitt aus der Dokumentation der Klasse Produkt

Produkt(String pBezeichnung, String pKategorie)

Ein neues Objekt der Klasse wird mit den Parametern pBezeichnung und pKategorie initialisiert.

String gibBezeichnung()

Die Methode liefert die gespeicherte Bezeichnung des Produkts.

String gibKategorie()

Die Methode liefert die Kategorie des Produkts.

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.

Die Klasse DatabaseConnector

Ein Objekt der Klasse DatabaseConnector ermöglicht die Abfrage und Manipulation einer relationalen Datenbank. Beim Erzeugen des Objekts wird eine Datenbankverbindung aufgebaut, sodass anschließend SQL-Anweisungen an diese Datenbank gerichtet werden können.

Dokumentation der Klasse DatabaseConnector

DatabaseConnector(String pIP, int pPort, String pDatabase, String pUsername, String pPassword)

Ein Objekt vom Typ DatabaseConnector wird erstellt, und eine Verbindung zur Datenbank wird aufgebaut. Mit den Parametern pIP und pPort werden die IP-Adresse und die Port-Nummer übergeben, unter denen die Datenbank mit Namen pDatabase zu erreichen ist. Mit den Parametern pUsername und pPassword werden Benutzername und Passwort für die Datenbank übergeben.

void executeStatement(String pSQLStatement)

Der Auftrag schickt den im Parameter pSQLStatement enthaltenen SQL-Befehl an die Datenbank ab. Handelt es sich bei pSQLStatement um einen SQL-Befehl, der eine Ergebnismenge liefert, so kann dieses Ergebnis anschließend mit der Methode getCurrentQueryResult abgerufen werden.

QueryResult getCurrentQueryResult()

Die Anfrage liefert das Ergebnis des letzten mit der Methode executeStatement an die Datenbank geschickten SQL-Befehls als Objekt vom Typ QueryResult zurück. Wurde bisher kein SQL-Befehl abgeschickt oder ergab der letzte Aufruf von executeStatement keine Ergebnismenge (z. B. bei einem INSERT-Befehl oder einem Syntaxfehler), so wird null geliefert.

String getErrorMessage()

Die Anfrage liefert null oder eine Fehlermeldung, die sich jeweils auf die letzte zuvor ausgeführte Datenbankoperation bezieht.

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

Ein Objekt der Klasse QueryResult stellt die Ergebnistabelle einer Datenbankanfrage mit Hilfe der Klasse DatabaseConnector dar. Objekte dieser Klasse werden nur von der Klasse DatabaseConnector erstellt. Die Klasse verfügt über keinen öffentlichen Konstruktor.

Dokumentation der Klasse QueryResult

String[][] getData()

Die Anfrage liefert die Einträge der Ergebnistabelle als zweidimensionales Feld vom Typ String. Der erste Index des Feldes stellt die Zeile und der zweite die Spalte dar (d. h. String[zeile][spalte]).

String[] getColumnNames()

Die Anfrage liefert die Bezeichner der Spalten der Ergebnistabelle als Feld vom Typ String zurück.

String[] getColumnTypes()

Die Anfrage liefert die Typenbezeichnung der Spalten der Ergebnistabelle als Feld vom Typ String zurück. Die Bezeichnungen entsprechen den Angaben in der Datenbank.

int getRowCount()

Die Anfrage liefert die Anzahl der Zeilen der Ergebnistabelle als int.

int getColumnCount()

Die Anfrage liefert die Anzahl der Spalten der Ergebnistabelle als int.

Teilaufgabe b) [8 Punkte]

Aus der Datenbank, die nach dem Schema in Abbildung 3 aufgebaut ist, sollen die nachstehenden Informationen abgefragt werden:

i.

Gesucht sind die Bezeichnungen aller Produkte, die mit der Zeichenkette 'Bio' beginnen. Das Ergebnis soll zuerst aufsteigend nach der Kategorie und danach aufsteigend nach der Bezeichnung geordnet sein.

ii.

Damit die Datenbank klein bleibt, sollen die Produktbezeichnungen und Kategorienamen derjenigen Produkte ermittelt werden, die auf keiner Einkaufsliste stehen. Jedes Produkt darf dabei nur einmal erscheinen.

Teilaufgabe c) [13 Punkte]

Gegeben sind die folgenden SQL-Anweisungen i. und ii.:

i.

SELECT Produkt.Bezeichnung, SUM(stehtAuf.Menge) AS Menge

FROM Produkt

LEFT JOIN stehtAuf

ON Produkt.Bezeichnung = stehtAuf.ProduktBezeichnung

WHERE Produkt.KategorieName = 'Obst/Gemüse'

GROUP BY Produkt.Bezeichnung

Angewendet auf die Beispieldaten (siehe Anlage) liefert diese SQL-Anweisung folgendes Ergebnis:

Bezeichnung · Menge

Biomango · NULL

Gurke · 2

Paprika · 2

Salat · 1

Abbildung 4: Ergebnis der SQL-Anweisung i.

ii.

SELECT Produkt.Bezeichnung, SUM(stehtAuf.Menge) AS Menge

FROM Produkt

INNER JOIN stehtAuf

ON Produkt.Bezeichnung = stehtAuf.ProduktBezeichnung

WHERE Produkt.KategorieName = 'Obst/Gemüse'

GROUP BY Produkt.Bezeichnung

UNION

SELECT Produkt.Bezeichnung, 0 AS Menge

FROM Produkt

WHERE Produkt.Bezeichnung NOT IN (

SELECT stehtAuf.ProduktBezeichnung

FROM stehtAuf

)

AND Produkt.KategorieName = 'Obst/Gemüse'

Analysieren Sie die zweite SQL-Anweisung (ii), indem Sie diese auf die Beispieldaten der Anlage anwenden und das Ergebnis eintragen:

Bezeichnung · Menge

Vergleichen Sie sowohl die Ergebnisse als auch den Aufbau der beiden SQL-Anweisungen.

Hinweis: Das SQL-Konstrukt 0 AS spaltenbezeichner setzt in der Spalte spaltenbezeichner für jeden Datensatz den Wert 0.

Aufgabenstellung: Einkaufslisten-App

Ein Unternehmen plant die Entwicklung einer App, mit der sich mehrere Einkaufslisten anlegen und verwalten lassen.

Zur Registrierung sind für alle Nutzerinnen und Nutzer der eigene Name, ein eindeutiger Benutzername und ein Passwort erforderlich. Mehrere Personen können außerdem gemeinsam eine Einkaufsliste verwalten.

Damit das Anlegen einer Einkaufsliste einfacher wird, sind im System bereits zahlreiche Produkte hinterlegt, die ausgewählt werden können. Selbstverständlich dürfen Nutzerinnen und Nutzer auch eigene neue Produkte ergänzen.

Das Unternehmen speichert seine Daten in einer relationalen Datenbank, die auf einem über das Internet erreichbaren Datenbank-Server liegt und mit Benutzername und Passwort zugänglich ist. Ein Teil der Modellierung dieser Datenbank wird nachfolgend gezeigt.

Das folgende Datenbankschema gibt die Modellierung der Datenbank wieder. Im Anhang stehen Beispieldatensätze zu diesem Schema.

Anlage: Beispieldaten der Datenbank

Einkaufsliste

ID · Titel

14 · Salatliste

15 · Biomarkt

16 · Hamstern

17 · Einkaufen

18 · Geburtstagsfeier

19 · Biomarkt

Kategorie

Name

Backwaren

Getränke

Hygieneartikel

Kühlprodukte

Obst/Gemüse

Süßspeisen

Tiefkühlprodukte

Produkt

Bezeichnung · Kategorie

Schafskäse · Kühlprodukte

Gouda · Kühlprodukte

Hefe · Kühlprodukte

Brot · Backwaren

Baguette · Backwaren

Paprika · Obst/Gemüse

Gurke · Obst/Gemüse

Salat · Obst/Gemüse

Salamipizza · Tiefkühlprodukte

Erbsen · Tiefkühlprodukte

Schokolade · Süßspeisen

Bonbons · Süßspeisen

Limonade · Getränke

Klopapier · Hygieneartikel

Biomango · Obst/Gemüse

Benutzer

Benutzername · Vorname · Nachname · Passwort 1

FabBen · Ben · Lovelace · ab4bd73e2123ddef3

JaStIn · Jana · Strehl · 3e2123ddef3ab4bd7

Edelweiss · Julian · Beton · ab4bd7ab4bd7eefde

Pudelski · Laura · Pudelski · bd7ab4bd7eef00e0e

Linus · Knut · Bremhorst · ef0023ddef3ab47ea

1 Die Passwörter werden nicht im Klartext, sondern verschlüsselt in der Datenbank gespeichert.

gehoertZu

EinkaufslisteID · Benutzername

14 · Linus

15 · FabBen

16 · FabBen

16 · Linus

17 · Linus

18 · FabBen

19 · JaStIn

stehtAuf

ProduktBezeichnung · EinkaufslisteID · Menge

Schafskäse · 14 · 2

Schokolade · 15 · 3

Salat · 14 · 1

Paprika · 14 · 1

Limonade · 18 · 24

Bonbons · 18 · 3

Brot · 16 · 5

Gouda · 15 · 1

Brot · 18 · 3

Gurke · 17 · 2

Paprika · 17 · 1

Baguette · 18 · 6

Salamipizza · 17 · 3

Schafskäse · 15 · 2

Schokolade · 18 · 1

Erbsen · 18 · 1

Schokolade · 17 · 2

Hefe · 17 · 1

Hefe · 16 · 12

Klopapier · 16 · 25

Anhang: Dokumentationen der Klassen

Die Klasse EinkaufslistenApp

Ein Objekt der Klasse EinkaufslistenApp verwaltet eine aus der passenden Datenbank geladene Einkaufsliste.

Ausschnitt aus der Dokumentation der Klasse EinkaufslistenApp

EinkaufslistenApp(String pBenutzername, String pPasswort)

Ein neues Objekt der Klasse wird mit den Parametern pBenutzername und pPasswort initialisiert.

int[] ladeListenIDs()

Die Methode lädt die IDs der Einkaufslisten aus der Datenbank, die der angemeldeten Person zugeordnet sind, und gibt sie zurück.

void ladeListe(int pID)

Die Methode lädt die Einträge der mit der ID identifizierten Einkaufsliste aus der Datenbank und speichert sie. Existiert die ID nicht, ist keine Benutzerin bzw. kein Benutzer angemeldet oder gehört die Einkaufsliste mit der übergebenen ID nicht zu dem Benutzernamen, so wird keine Einkaufsliste gespeichert.

int gibAktuelleID()

Die Methode liefert die ID zu der aktuell geladenen Einkaufsliste. Ist keine Einkaufsliste geladen, wird -1 zurückgegeben.

List<Eintrag> gibAktuelleEintraege()

Die Methode liefert die Einträge der aktuellen Einkaufsliste in einem Objekt der Klasse Liste<Eintrag>. Ist keine aktuelle Einkaufsliste geladen, so wird null zurückgegeben.

Dokumentation der privaten Methode pruefeBenutzerZugriff

boolean pruefeBenutzerZugriff(int pID)

Die Methode prüft anhand eines Datenbankzugriffs, ob die über den Parameter identifizierte Einkaufsliste zu dem angemeldeten Benutzer gehört. In diesem Fall liefert sie den Wert true als Rückgabe, in allen anderen Fällen liefert sie den Wert false als Rückgabe.

Die Klasse Eintrag

Ein Objekt der Klasse Eintrag verwaltet ein aus der passenden Datenbank geladenes Produkt sowie die für die zugehörige Einkaufsliste gespeicherte Menge.

Ausschnitt aus der Dokumentation der Klasse Eintrag

Eintrag(Produkt pProdukt, int pMenge)

Ein neues Objekt der Klasse wird mit den Parametern pProdukt und pMenge initialisiert.

void setzeErledigt(boolean pErledigt)

Die Methode speichert, ob der Eintrag erledigt ist.

boolean istErledigt()

Die Methode liefert, ob der Eintrag erledigt ist.

int gibMenge()

Die Methode liefert die gespeicherte Menge des Eintrags.

Produkt gibProdukt()

Die Methode liefert das Produkt zu dem Eintrag.

Die Klasse Produkt

Ein Objekt der Klasse Produkt repräsentiert ein aus der passenden Datenbank geladenes Produkt.

Ausschnitt aus der Dokumentation der Klasse Produkt

Produkt(String pBezeichnung, String pKategorie)

Ein neues Objekt der Klasse wird mit den Parametern pBezeichnung und pKategorie initialisiert.

String gibBezeichnung()

Die Methode liefert die gespeicherte Bezeichnung des Produkts.

String gibKategorie()

Die Methode liefert die Kategorie des Produkts.

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.

Die Klasse DatabaseConnector

Ein Objekt der Klasse DatabaseConnector ermöglicht die Abfrage und Manipulation einer relationalen Datenbank. Beim Erzeugen des Objekts wird eine Datenbankverbindung aufgebaut, sodass anschließend SQL-Anweisungen an diese Datenbank gerichtet werden können.

Dokumentation der Klasse DatabaseConnector

DatabaseConnector(String pIP, int pPort, String pDatabase, String pUsername, String pPassword)

Ein Objekt vom Typ DatabaseConnector wird erstellt, und eine Verbindung zur Datenbank wird aufgebaut. Mit den Parametern pIP und pPort werden die IP-Adresse und die Port-Nummer übergeben, unter denen die Datenbank mit Namen pDatabase zu erreichen ist. Mit den Parametern pUsername und pPassword werden Benutzername und Passwort für die Datenbank übergeben.

void executeStatement(String pSQLStatement)

Der Auftrag schickt den im Parameter pSQLStatement enthaltenen SQL-Befehl an die Datenbank ab. Handelt es sich bei pSQLStatement um einen SQL-Befehl, der eine Ergebnismenge liefert, so kann dieses Ergebnis anschließend mit der Methode getCurrentQueryResult abgerufen werden.

QueryResult getCurrentQueryResult()

Die Anfrage liefert das Ergebnis des letzten mit der Methode executeStatement an die Datenbank geschickten SQL-Befehls als Objekt vom Typ QueryResult zurück. Wurde bisher kein SQL-Befehl abgeschickt oder ergab der letzte Aufruf von executeStatement keine Ergebnismenge (z. B. bei einem INSERT-Befehl oder einem Syntaxfehler), so wird null geliefert.

String getErrorMessage()

Die Anfrage liefert null oder eine Fehlermeldung, die sich jeweils auf die letzte zuvor ausgeführte Datenbankoperation bezieht.

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

Ein Objekt der Klasse QueryResult stellt die Ergebnistabelle einer Datenbankanfrage mit Hilfe der Klasse DatabaseConnector dar. Objekte dieser Klasse werden nur von der Klasse DatabaseConnector erstellt. Die Klasse verfügt über keinen öffentlichen Konstruktor.

Dokumentation der Klasse QueryResult

String[][] getData()

Die Anfrage liefert die Einträge der Ergebnistabelle als zweidimensionales Feld vom Typ String. Der erste Index des Feldes stellt die Zeile und der zweite die Spalte dar (d. h. String[zeile][spalte]).

String[] getColumnNames()

Die Anfrage liefert die Bezeichner der Spalten der Ergebnistabelle als Feld vom Typ String zurück.

String[] getColumnTypes()

Die Anfrage liefert die Typenbezeichnung der Spalten der Ergebnistabelle als Feld vom Typ String zurück. Die Bezeichnungen entsprechen den Angaben in der Datenbank.

int getRowCount()

Die Anfrage liefert die Anzahl der Zeilen der Ergebnistabelle als int.

int getColumnCount()

Die Anfrage liefert die Anzahl der Spalten der Ergebnistabelle als int.

e) Im Zuge einer Sicherheitsprüfung entdeckt das Unternehmen, dass ein Nutzer sämtliche Einkaufslisten der gesamten Datenbank abgerufen hat. Ein Praktikant erklärt dies damit, dass der Abruf einer fremden Einkaufsliste, auf die kein Zugriff bestehen dürfte, lediglich durch die App auf dem Endgerät unterbunden wird. Seiner Meinung nach wäre es besser, die Leserechte der Nutzerin bzw. des Nutzers serverseitig zu beschränken.

Beurteilen Sie, bei welchen Daten der modellierten Datenbank (siehe Abbildung 2 bzw. Abbildung 3) es sich um personenbezogene und damit schützenswerte Daten handelt.

Beurteilen Sie, ob eine Zugriffsprüfung auf dem Server zweckmäßiger ist als eine Prüfung auf dem Client.

(7 Punkte)

Aufgabenstellung:

Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, worum ihn seine Eltern gebeten haben, entdeckt er seine alte Modelleisenbahn, mit der er als Kind oft gespielt hat. Dabei fällt ihm ein, dass er früher stets eine sinnvolle Schienenanlage bauen wollte, auf der die Eisenbahn entweder im Kreis fuhr oder an Prellböcken endete. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Damit die Untersuchung überschaubar bleibt, betrachtet er zunächst nur die folgenden Bauteile.

Ein endlicher Automat soll dazu verwendet werden, zu überprüfen, ob eine Schienenanlage sinnvoll aufgebaut ist.

Hierfür reiht er die Bauteil-IDs zu Wörtern aneinander, die jeweils eine Schienenanlage repräsentieren. Eine Anlage aus zwei Prellböcken mit einer Brücke dazwischen wird zum Beispiel durch das Wort p1b2p beschrieben.

Zur Überprüfung von Schienenanlagen entwirft Leonard einen deterministischen endlichen Automaten A, dessen Zustandsübergangsdiagramm in Abbildung 2 zu sehen ist:

a)

Erläutern Sie, durch welche Eigenschaften sich die Schienenanlagen auszeichnen, die zu den vom Automaten A akzeptierten Wörtern gehören.

Ermitteln Sie sämtliche vom Automaten A akzeptierten Wörter von minimaler Länge, in denen jede Bauteil-ID mindestens einmal vorkommt.

Erläutern Sie, was der Zustand $q_1$ im Sachzusammenhang bedeutet.

b)

Das Wort pp ist Element der Sprache $L_A$ des Automaten A (vgl. Abbildung 2), die zugehörige Schienenanlage ist jedoch nicht sinnvoll.

Begründen Sie im Sachzusammenhang, weshalb die Schienenanlage, die zum Wort pp gehört, nicht sinnvoll ist.

Modifizieren Sie das Zustandsübergangsdiagramm aus Abbildung 2 derart, dass der zugehörige deterministische endliche Automat jedes Wort der Sprache $L_A$ außer dem Wort pp akzeptiert.

Aufgabenstellung:

Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, worum ihn seine Eltern gebeten haben, entdeckt er seine alte Modelleisenbahn, mit der er als Kind oft gespielt hat. Dabei fällt ihm ein, dass er früher stets eine sinnvolle Schienenanlage bauen wollte, auf der die Eisenbahn entweder im Kreis fuhr oder an Prellböcken endete. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Damit die Untersuchung überschaubar bleibt, betrachtet er zunächst nur die folgenden Bauteile.

Ein endlicher Automat soll dazu verwendet werden, zu überprüfen, ob eine Schienenanlage sinnvoll aufgebaut ist.

Hierfür reiht er die Bauteil-IDs zu Wörtern aneinander, die jeweils eine Schienenanlage repräsentieren. Eine Anlage aus zwei Prellböcken mit einer Brücke dazwischen wird zum Beispiel durch das Wort p1b2p beschrieben.

Zur Überprüfung von Schienenanlagen entwirft Leonard einen deterministischen endlichen Automaten A, dessen Zustandsübergangsdiagramm in Abbildung 2 zu sehen ist:

Ab jetzt kommen keine Brücken und Prellböcke mehr zum Einsatz; stattdessen werden für die Schienenanlagen zusätzlich 90°-Kurvenelemente genutzt. Leonard will jedoch ausschließlich Rechtskurven verwenden:

Teilaufgabe c) [16 Punkte]

Die Sprache $L_G$ wird von der nachstehenden Grammatik $G$ erzeugt:

Startsymbol:

$S$

Terminalsymbole:

$\{g,\, r\}$

Nichtterminalsymbole:

$\{S,\, A,\, B\}$

Produktionen:

$$\{\quad S \rightarrow rrA,\quad A \rightarrow gBg,\quad B \rightarrow gBg \mid rr\quad\}$$

c.1

Zeigen Sie, dass $rrggrrgg$ ein Wort ist, das sich mit der Grammatik $G$ ableiten lässt, während dies für das Wort $rrrr$ nicht gelingt.

c.2

Erläutern Sie im Sachzusammenhang, für welche Schienenanlagen die Sprache $L_G$ steht.

c.3

Begründen Sie, weshalb $G$ keine reguläre Grammatik ist.

c.4

Entwickeln Sie einen Kellerautomaten, der die Sprache $L_G$ erkennt. Erstellen Sie dazu auf Papier ein Zustandsübergangsdiagramm oder eine formale Definition und laden Sie ein Foto davon hoch:

Teilaufgabe e) [5 Punkte]

Leonard möchte mithilfe eines deterministischen endlichen Automaten prüfen, ob ein Wort zu einer Schienenanlage gehört, die ein „Quadrat“ bildet. Mit einem „Quadrat“ ist eine Schienenanlage gemeint, die aus vier Rechtskurven an den vier Ecken besteht. Zwischen den Rechtskurven sind für jede der vier Seiten gleich viele gerade Gleisstücke verbaut. Leonard möchte beliebig große „Quadrate“ zulassen.

e

Beurteilen Sie, ob ein endlicher Automat entscheiden kann, ob ein Wort eine Schienenanlage in Form eines „Quadrats“ beschreibt.

Aufgabenstellung:

Leonard besucht einen Informatikkurs und plant, nach dem Abitur Informatik zu studieren. Beim Aufräumen des Dachbodens, worum ihn seine Eltern gebeten haben, entdeckt er seine alte Modelleisenbahn, mit der er als Kind oft gespielt hat. Dabei fällt ihm ein, dass er früher stets eine sinnvolle Schienenanlage bauen wollte, auf der die Eisenbahn entweder im Kreis fuhr oder an Prellböcken endete. Mit seinem Wissen aus der theoretischen Informatik will Leonard untersuchen, ob eine Schienenanlage sinnvoll aufgebaut ist. Damit die Untersuchung überschaubar bleibt, betrachtet er zunächst nur die folgenden Bauteile.

Ein endlicher Automat soll dazu verwendet werden, zu überprüfen, ob eine Schienenanlage sinnvoll aufgebaut ist.

Hierfür reiht er die Bauteil-IDs zu Wörtern aneinander, die jeweils eine Schienenanlage repräsentieren. Eine Anlage aus zwei Prellböcken mit einer Brücke dazwischen wird zum Beispiel durch das Wort p1b2p beschrieben.

Zur Überprüfung von Schienenanlagen entwirft Leonard einen deterministischen endlichen Automaten A, dessen Zustandsübergangsdiagramm in Abbildung 2 zu sehen ist:

d) Leonard will mit einem Computerprogramm prüfen, ob die vorhandenen Bauteile genügen, um eine bestimmte Schienenanlage zu errichten. Dabei sollen in diesen Anlagen ausschließlich Prellböcke (p), Rechtskurven (r) und gerade Gleisstücke (g) vorkommen.

In der Klasse Schienenanlagentester legt er eine Methode genugBauteile an, der zwei Zeichenketten aus den Zeichen p, r und g übergeben werden.

Der Methodenkopf lautet:

public boolean genugBauteile(String pAnlage, String pBauteile) Der Parameter pAnlage enthält das Wort, das die zu errichtende Schienenanlage beschreibt.

Der Parameter pBauteile ist eine Zeichenkette, die die IDs aller verfügbaren Bauteile ohne bestimmte Ordnung direkt aneinandergereiht enthält.

Die Methode muss NICHT prüfen, ob das Wort der Schienenanlage eine sinnvolle Anlage beschreibt.

Sie liefert true, falls die vorhandenen Bauteile für die Schienenanlage genügen, andernfalls false.

1.

2.