Abitur NRW Informatik 2023 · GK · Nachtermin

Aufgabenstellung: Digitales Glücksrad

Auf einem Stadtfest will ein Büroartikelmarkt Gäste kleine Büroartikel gewinnen lassen. Der Inhaber hat dazu die Idee eines besonderen „digitalen Glücksrads“ entwickelt und den Informatik-Grundkurs des örtlichen Schulzentrums mit der Programmierung beauftragt.

Das Besondere an diesem digitalen Glücksrad ist, dass auf jedem Sektor des Glücksrads ein ganzer Stapel von Gewinnen liegt. Bleibt der Pfeil des Glücksrads auf einem Sektor stehen, auf dem ein ganzer Stapel von Gewinnen liegt, so wird der oberste Gewinn des Stapels auf den im Uhrzeigersinn nächsten Glücksradsektor verschoben, d. h. auf den Stapel des nächsten Glücksradsektors gelegt, und die Spielerin bzw. der Spieler darf erneut den Pfeil des Glücksrads drehen. Andernfalls steht der Pfeil auf einem Sektor, auf dem lediglich ein einziger Gewinn liegt. Die Spielerin bzw. der Spieler bekommt diesen Gewinn und der nun leere Glücksradsektor wird aus dem Glücksrad entfernt.

Eine Spielerin dreht den Pfeil des links in Abbildung 1 gezeigten Glücksrads zweimal im Uhrzeigersinn. Beim ersten Dreh wird der Pfeil um einen Sektor weitergedreht und bleibt auf dem Sektor mit dem Bleistift stehen, welcher deshalb einen Sektor weiter auf den Locher verschoben wird. Beim zweiten Dreh wird der Pfeil dann noch weitere fünf Sektoren weitergedreht und bleibt auf dem Radierer stehen. Dieser wird mitsamt dem ganzen Glücksradsektor entfernt und die Spielerin gewinnt den Radierer. Nach diesen beiden Drehungen sieht das aktuelle Glücksrad aus wie das in Abbildung 1 rechts dargestellte Glücksrad. Da der Sektor mit dem Radierer entfernt wurde, steht der Pfeil des Glücksrads nun auf dem im Uhrzeigersinn nächsten Sektor mit dem Klebstoff obenauf.

Ein Glücksrad kann kurz durch eine Zeichenkette dargestellt werden, wobei die Gewinnstapel jeweils von unten nach oben angegeben sind und die Glücksradsektoren jeweils durch das Trennsymbol " / " voneinander getrennt sind.

Abbildung 2 zeigt die Zeichenkette zum Glücksrad, welches nach dem zweimaligen Dreh des Pfeils resultiert (siehe rechtes Glücksrad aus Abbildung 1). Der Pfeil des Glücksrads steht dabei auf dem ersten angegebenen Glücksradsektor (hier der Sektor mit dem Gewinnstapel "Tacker, Klebstoff").

Das folgende Implementationsdiagramm liegt vor.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Gewinn

Objekte der Klasse Gewinn verwalten einen einzelnen Gewinn des Glücksrads.

Methode / Konstruktor · Beschreibung

Gewinn(String pName, double pWert) · Ein neuer Gewinn mit der Bezeichnung pName und dem Gewinnwert pWert wird erstellt.

String gibName() · Die Anfrage liefert die Bezeichnung des Gewinns.

double gibWert() · Die Anfrage liefert den Gewinnwert des Gewinns.

Die Klasse Sektor

Objekte der Klasse Sektor verwalten alle Gewinne eines einzelnen Glücksradsektors in Form eines Gewinnstapels.

Methode / Konstruktor · Beschreibung

Sektor() · Ein neuer, leerer Glücksradsektor wird erstellt.

Gewinn gibOberstenGewinn() · Die Anfrage liefert den Gewinn, der oben auf dem Gewinnstapel des Sektors liegt. Sollte der Glücksradsektor leer sein, so wird null zurückgeliefert.

void entferneOberstenGewinn() · Der Gewinn, der auf dem Gewinnstapel des Sektors obenauf liegt, wird entfernt. Sollte der Glücksradsektor leer sein, so geschieht nichts.

void legeGewinnObenauf(Gewinn pGewinn) · Das Objekt pGewinn wird auf den Gewinnstapel des Sektors gelegt. Ist der Parameter pGewinn gleich null, so geschieht nichts.

boolean istLeer() · Die Anfrage liefert den Wert true, wenn der Gewinnstapel keine Objekte enthält, sonst liefert sie den Wert false.

int ermittleAnzahlGewinne() · Die Anfrage ermittelt die Anzahl der Objekte auf dem Gewinnstapel. Der Stapel der Gewinne ist nach Ablauf der Methode unverändert. Sollte der Glücksradsektor leer sein, so wird der Wert 0 zurückgeliefert.

Die Klasse Gluecksrad

Objekte der Klasse Gluecksrad verwalten ein digitales Glücksrad. Sollte das Glücksrad mindestens einen Sektor besitzen, so gibt es immer einen aktuell ausgewählten Sektor, auf den der Pfeil des Glücksrads zeigt. Andernfalls bleibt der Pfeil des Glücksrads unverändert.

Methode / Konstruktor · Beschreibung

Gluecksrad() · Ein neues, leeres Glücksrad ohne Sektoren wird erstellt.

void fuegeSektorHinzu(Stack<Gewinn> pGewinne) · Ein neuer Glücksradsektor mit dem Gewinnstapel pGewinne wird in das Glücksrad eingefügt. Sollte der Sektor der erste eingefügte Sektor sein, so wird dieser Sektor der aktuell ausgewählte Glücksradsektor, auf den der Pfeil des Glücksrads zeigt. Andernfalls bleibt der aktuell ausgewählte Sektor unverändert und der neue Sektor wird vor dem aktuellen Sektor (also gegen den Uhrzeigersinn) eingefügt. Sollte der Stapel pGewinne leer oder der Parameter pGewinne gleich null sein, so geschieht nichts.

int gibAnzahlSektoren() · Die Anfrage ermittelt die Anzahl der Sektoren des Glücksrads. Das Glücksrad ist nach Ablauf der Methode unverändert.

int ermittleAnzahlGewinne() · Die Anfrage ermittelt die Anzahl der Gewinne auf dem gesamten Glücksrad. Das Glücksrad ist nach Ablauf der Methode unverändert.

void verschiebeGewinn() · Der Gewinn, der auf dem Gewinnstapel des aktuellen Sektors obenauf liegt, wird auf den Gewinnstapel des im Uhrzeigersinn nächsten Sektors verschoben. Der aktuell ausgewählte Glücksradsektor bleibt weiterhin ausgewählt.

Gewinn simuliereZufaelligeDrehung() · Die Methode simuliert das einmalige Drehen des Pfeils des Glücksrads um eine zufällige Anzahl Sektoren im Uhrzeigersinn inklusive der Entfernung/Verschiebung eines Gewinns und einer eventuellen Entfernung eines Glücksradsektors. Zurückgeliefert wird der so gewonnene Gewinn bzw. null, falls gemäß den Spielregeln kein Gewinn erzielt wurde.

Die generische Klasse Queue

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

Methode / Konstruktor · Beschreibung

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

boolean isEmpty() · Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

void enqueue(ContentType pContent) · Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert.

void dequeue() · Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

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

Die generische Klasse Stack

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

Methode / Konstruktor · Beschreibung

Stack() · Ein leerer Stapel wird erzeugt. Objekte, die in diesem Stapel verwaltet werden, müssen vom Typ ContentType sein.

boolean isEmpty() · Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält, sonst liefert sie den Wert false.

void push(ContentType pContent) · Das Objekt pContent wird oben auf den Stapel gelegt. Falls pContent gleich null ist, bleibt der Stapel unverändert.

void pop() · Das zuletzt eingefügte Objekt wird von dem Stapel entfernt. Falls der Stapel leer ist, bleibt er unverändert.

ContentType top() · Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.

Das folgende Implementationsdiagramm liegt vor:

b)

Beschreiben Sie, wie die Klassen Gluecksrad, Gewinn, Sektor, Queue und Stack in der in Abbildung 3 dargestellten Teilmodellierung zueinander in Beziehung stehen.

Begründen Sie bezogen auf den Sachkontext, weshalb es zweckmäßig ist, die Gewinne in einem Stapel und die Sektoren in einer Schlange zu verwalten.

Aufgabenstellung: Digitales Glücksrad

Auf einem Stadtfest will ein Büroartikelmarkt Gäste kleine Büroartikel gewinnen lassen. Der Inhaber hat dazu die Idee eines besonderen „digitalen Glücksrads“ entwickelt und den Informatik-Grundkurs des örtlichen Schulzentrums mit der Programmierung beauftragt.

Das Besondere an diesem digitalen Glücksrad ist, dass auf jedem Sektor des Glücksrads ein ganzer Stapel von Gewinnen liegt. Bleibt der Pfeil des Glücksrads auf einem Sektor stehen, auf dem ein ganzer Stapel von Gewinnen liegt, so wird der oberste Gewinn des Stapels auf den im Uhrzeigersinn nächsten Glücksradsektor verschoben, d. h. auf den Stapel des nächsten Glücksradsektors gelegt, und die Spielerin bzw. der Spieler darf erneut den Pfeil des Glücksrads drehen. Andernfalls steht der Pfeil auf einem Sektor, auf dem lediglich ein einziger Gewinn liegt. Die Spielerin bzw. der Spieler bekommt diesen Gewinn und der nun leere Glücksradsektor wird aus dem Glücksrad entfernt.

Eine Spielerin dreht den Pfeil des links in Abbildung 1 gezeigten Glücksrads zweimal im Uhrzeigersinn. Beim ersten Dreh wird der Pfeil um einen Sektor weitergedreht und bleibt auf dem Sektor mit dem Bleistift stehen, welcher deshalb einen Sektor weiter auf den Locher verschoben wird. Beim zweiten Dreh wird der Pfeil dann noch weitere fünf Sektoren weitergedreht und bleibt auf dem Radierer stehen. Dieser wird mitsamt dem ganzen Glücksradsektor entfernt und die Spielerin gewinnt den Radierer. Nach diesen beiden Drehungen sieht das aktuelle Glücksrad aus wie das in Abbildung 1 rechts dargestellte Glücksrad. Da der Sektor mit dem Radierer entfernt wurde, steht der Pfeil des Glücksrads nun auf dem im Uhrzeigersinn nächsten Sektor mit dem Klebstoff obenauf.

Ein Glücksrad kann kurz durch eine Zeichenkette dargestellt werden, wobei die Gewinnstapel jeweils von unten nach oben angegeben sind und die Glücksradsektoren jeweils durch das Trennsymbol " / " voneinander getrennt sind.

Abbildung 2 zeigt die Zeichenkette zum Glücksrad, welches nach dem zweimaligen Dreh des Pfeils resultiert (siehe rechtes Glücksrad aus Abbildung 1). Der Pfeil des Glücksrads steht dabei auf dem ersten angegebenen Glücksradsektor (hier der Sektor mit dem Gewinnstapel "Tacker, Klebstoff").

Das folgende Implementationsdiagramm liegt vor.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Gewinn

Objekte der Klasse Gewinn verwalten einen einzelnen Gewinn des Glücksrads.

Methode / Konstruktor · Beschreibung

Gewinn(String pName, double pWert) · Ein neuer Gewinn mit der Bezeichnung pName und dem Gewinnwert pWert wird erstellt.

String gibName() · Die Anfrage liefert die Bezeichnung des Gewinns.

double gibWert() · Die Anfrage liefert den Gewinnwert des Gewinns.

Die Klasse Sektor

Objekte der Klasse Sektor verwalten alle Gewinne eines einzelnen Glücksradsektors in Form eines Gewinnstapels.

Methode / Konstruktor · Beschreibung

Sektor() · Ein neuer, leerer Glücksradsektor wird erstellt.

Gewinn gibOberstenGewinn() · Die Anfrage liefert den Gewinn, der oben auf dem Gewinnstapel des Sektors liegt. Sollte der Glücksradsektor leer sein, so wird null zurückgeliefert.

void entferneOberstenGewinn() · Der Gewinn, der auf dem Gewinnstapel des Sektors obenauf liegt, wird entfernt. Sollte der Glücksradsektor leer sein, so geschieht nichts.

void legeGewinnObenauf(Gewinn pGewinn) · Das Objekt pGewinn wird auf den Gewinnstapel des Sektors gelegt. Ist der Parameter pGewinn gleich null, so geschieht nichts.

boolean istLeer() · Die Anfrage liefert den Wert true, wenn der Gewinnstapel keine Objekte enthält, sonst liefert sie den Wert false.

int ermittleAnzahlGewinne() · Die Anfrage ermittelt die Anzahl der Objekte auf dem Gewinnstapel. Der Stapel der Gewinne ist nach Ablauf der Methode unverändert. Sollte der Glücksradsektor leer sein, so wird der Wert 0 zurückgeliefert.

Die Klasse Gluecksrad

Objekte der Klasse Gluecksrad verwalten ein digitales Glücksrad. Sollte das Glücksrad mindestens einen Sektor besitzen, so gibt es immer einen aktuell ausgewählten Sektor, auf den der Pfeil des Glücksrads zeigt. Andernfalls bleibt der Pfeil des Glücksrads unverändert.

Methode / Konstruktor · Beschreibung

Gluecksrad() · Ein neues, leeres Glücksrad ohne Sektoren wird erstellt.

void fuegeSektorHinzu(Stack<Gewinn> pGewinne) · Ein neuer Glücksradsektor mit dem Gewinnstapel pGewinne wird in das Glücksrad eingefügt. Sollte der Sektor der erste eingefügte Sektor sein, so wird dieser Sektor der aktuell ausgewählte Glücksradsektor, auf den der Pfeil des Glücksrads zeigt. Andernfalls bleibt der aktuell ausgewählte Sektor unverändert und der neue Sektor wird vor dem aktuellen Sektor (also gegen den Uhrzeigersinn) eingefügt. Sollte der Stapel pGewinne leer oder der Parameter pGewinne gleich null sein, so geschieht nichts.

int gibAnzahlSektoren() · Die Anfrage ermittelt die Anzahl der Sektoren des Glücksrads. Das Glücksrad ist nach Ablauf der Methode unverändert.

int ermittleAnzahlGewinne() · Die Anfrage ermittelt die Anzahl der Gewinne auf dem gesamten Glücksrad. Das Glücksrad ist nach Ablauf der Methode unverändert.

void verschiebeGewinn() · Der Gewinn, der auf dem Gewinnstapel des aktuellen Sektors obenauf liegt, wird auf den Gewinnstapel des im Uhrzeigersinn nächsten Sektors verschoben. Der aktuell ausgewählte Glücksradsektor bleibt weiterhin ausgewählt.

Gewinn simuliereZufaelligeDrehung() · Die Methode simuliert das einmalige Drehen des Pfeils des Glücksrads um eine zufällige Anzahl Sektoren im Uhrzeigersinn inklusive der Entfernung/Verschiebung eines Gewinns und einer eventuellen Entfernung eines Glücksradsektors. Zurückgeliefert wird der so gewonnene Gewinn bzw. null, falls gemäß den Spielregeln kein Gewinn erzielt wurde.

Die generische Klasse Queue

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

Methode / Konstruktor · Beschreibung

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

boolean isEmpty() · Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte enthält, sonst liefert sie den Wert false.

void enqueue(ContentType pContent) · Das Objekt pContent wird an die Schlange angehängt. Falls pContent gleich null ist, bleibt die Schlange unverändert.

void dequeue() · Das erste Objekt wird aus der Schlange entfernt. Falls die Schlange leer ist, wird sie nicht verändert.

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

Die generische Klasse Stack

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

Methode / Konstruktor · Beschreibung

Stack() · Ein leerer Stapel wird erzeugt. Objekte, die in diesem Stapel verwaltet werden, müssen vom Typ ContentType sein.

boolean isEmpty() · Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält, sonst liefert sie den Wert false.

void push(ContentType pContent) · Das Objekt pContent wird oben auf den Stapel gelegt. Falls pContent gleich null ist, bleibt der Stapel unverändert.

void pop() · Das zuletzt eingefügte Objekt wird von dem Stapel entfernt. Falls der Stapel leer ist, bleibt er unverändert.

ContentType top() · Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.

Teilaufgabe a)

Der Pfeil des rechten Glücksrads aus Abbildung 1 wird zwei weitere Male gedreht. Die erste Drehung führt ihn um drei Sektoren weiter, sodass er auf dem Sektor mit dem Fineliner endet; bei der zweiten Drehung um vier Sektoren kommt er auf dem Sektor mit dem Filzstift zum Stehen.

Stellen Sie das Glücksrad nach jeder der beiden Drehungen in der Kurzschreibweise aus Abbildung 2 dar. [6 Punkte]

a.1)

a.2)

Teilaufgabe c)

Eine Schülerin im Informatik-Grundkurs hat die folgende private Methode wasMacheIch in der Klasse Gluecksrad programmiert:

1

private Gewinn wasMacheIch(int pAnzahlSektoren) {

2

for (int i = 0; i < pAnzahlSektoren; i++) {

3

sektoren.enqueue(sektoren.front());

4

sektoren.dequeue();

5

}

6

7

verschiebeGewinn();

8

9

Gewinn g = null;

10

Sektor aktuellerSektor = sektoren.front();

11

if (aktuellerSektor.istLeer()) {

12

sektoren.dequeue();

13

aktuellerSektor = sektoren.front();

14

g = aktuellerSektor.gibOberstenGewinn();

15

aktuellerSektor.entferneOberstenGewinn();

16

}

17

return g;

18 } Analysieren Sie die Methode wasMacheIch, indem Sie für die Aufrufe mit pAnzahlSektoren = 3 und mit pAnzahlSektoren = 2 jeweils das entstehende Glücksrad in Kurzschreibweise (vgl. Abbildung 2) ermitteln. Gehen Sie dabei in beiden Fällen vom linken Glücksrad in Abbildung 1 aus. [6 Punkte]

c.1)

c.2)

c.3)

Erläutern Sie im Sachzusammenhang, welche Funktion die Quelltextzeilen 2 bis 5 der Methode wasMacheIch haben. [3 Punkte]

c.4)

Erläutern Sie im Sachzusammenhang, welche Funktion die Quelltextzeilen 7 bis 17 der Methode wasMacheIch haben. [5 Punkte]

c.5)

Erläutern Sie, welchen Zweck die Methode wasMacheIch als Ganze erfüllt. [2 Punkte]

Teilaufgabe d)

Die Methode ermittleAnzahlGewinne der Klasse Gluecksrad bestimmt, wie viele Gewinne insgesamt auf allen Sektoren des Glücksrads gestapelt liegen. Ihr Methodenkopf lautet:

public int ermittleAnzahlGewinne() d.1)

Entwickeln und erläutern Sie ein algorithmisches Verfahren, das die Methode umsetzt. [5 Punkte]

d.2)

Implementieren Sie die Methode. [7 Punkte]

Teilaufgabe e)

Ein Schüler hat in die Klasse Gluecksrad die folgende Methode eingefügt:

1

public void simuliereGluecksrad() {

2

while (!sektoren.isEmpty()) {

3

simuliereZufaelligeDrehung();

4

}

5

} Wendet er die Methode auf das Glücksrad aus Abbildung 1 an, wundert er sich darüber, dass die Simulation in einer Endlosschleife stecken bleibt.

Eine Schülerin erklärt ihm, die Simulation gerate meistens in eine Endlosschleife, weil zusätzlich geprüft werden müsste, ob das Glücksrad nur noch aus genau einem Sektor besteht, aber insgesamt noch mehr als einen Gewinn enthält.

e.1)

Begründen Sie die Aussage der Schülerin im Sachkontext. [4 Punkte]

e.2)

Beurteilen Sie, inwiefern sich bereits zu Beginn der Simulation erkennen lässt, ob sich alle Gewinne vom Glücksrad entfernen lassen. [4 Punkte]

Aufgabenstellung: Lagerverwaltung des Onlineshops Infozon

Der Onlineshop Infozon bietet eine große Zahl von Artikeln an und ist in den vergangenen Jahren stark gewachsen. Deshalb braucht das Unternehmen eine neue Software zur Lagerverwaltung. Die IT-Abteilung hat sich aus verschiedenen Gründen dafür entschieden, die Artikel in einem binären Suchbaum abzulegen, der nach der Artikelnummer geordnet ist.

Zu jedem Artikel wird festgehalten, in welchem Regalfach sich wie viele noch verkäufliche Exemplare befinden. Jedes Regalfach darf nur Exemplare eines einzigen Artikels enthalten. Auch wenn ein Regalfach leer geworden ist, bleibt es in der Lagerverwaltung dem Artikel zugeordnet.

Der Lagerbestand enthält die folgenden Beispieldaten:

Ein Ausschnitt der Modellierung ist als Implementationsdiagramm wiedergegeben:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lagerverwaltung

Objekte der Klasse Lagerverwaltung verwalten den Bestand von Artikeln in Fächern.

Auszug aus der Dokumentation der Klasse Lagerverwaltung

Lagerverwaltung()

Ein Lagerverwaltungsobjekt wird initialisiert. Das Lager ist leer.

Artikel ermittle(int pArtikelnr)

Die Anfrage liefert für die Artikelnummer pArtikelnr das entsprechende Artikelobjekt. Falls zu pArtikelnr kein Artikelobjekt existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Artikel pArtikel)

Falls der Artikel mit der gleichen Artikelnummer im Lager noch nicht existiert, wird dieser der Lagerverwaltung hinzugefügt.

void erhoeheBestand(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert, dann wird in dem Fach mit der Fachnummer pFachnr der Bestand um pAnzahl erhöht. Falls das Fach nicht existiert, dann wird dieses mit dem Bestand pAnzahl angelegt.

void entnimm(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert und zu dem Artikel das Fach mit der Fachnummer pFachnr existiert und der Bestand in diesem Fach größer gleich pAnzahl ist, dann wird der Bestand in diesem Fach um pAnzahl verringert.

Die Klasse Artikel

Objekte der Klasse Artikel verwalten die Informationen über einen Artikel und seine Fächer mit Bestandsangaben.

Auszug aus der Dokumentation der Klasse Artikel

Artikel(int pNr, String pBezeichnung)

Ein Artikelobjekt mit der Artikelnummer pNr und der Artikelbezeichnung pBezeichnung wird initialisiert.

int gibNr()

Die Artikelnummer wird zurückgeliefert.

String gibBezeichnung()

Die Artikelbezeichnung wird zurückgeliefert.

List<Fach> gibFaecher()

Eine Liste der Fächer für diesen Artikel wird zurückgeliefert.

boolean isEqual(Artikel pArtikel)

Wenn die Artikelnummer gleich der Artikelnummer des Artikels pArtikel ist, dann wird true zurückgeliefert und sonst false.

boolean isLess(Artikel pArtikel)

Wenn die Artikelnummer kleiner ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

boolean isGreater(Artikel pArtikel)

Wenn die Artikelnummer größer ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

void fuegeHinzu(int pFachnr, int pAnzahl)

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel existiert, dann wird der Bestand um pAnzahl erhöht.

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel nicht existiert, dann wird ein neues Fach mit der Fachnummer pFachnr und dem Bestand pAnzahl angelegt.

Die Klasse Fach

Objekte der Klasse Fach verwalten die Informationen über die Fachnummer und den Bestand in diesem Fach. Die Fachnummer ist für jedes Fach eindeutig.

Auszug aus der Dokumentation der Klasse Fach

Fach(int pFachnr, int pBestand)

Ein Fachobjekt mit der Fachnummer pFachnr und dem Bestand pBestand wird initialisiert.

int gibFachnr()

Die Fachnummer wird zurückgeliefert.

int gibBestand()

Der Bestand wird zurückgeliefert.

void setzeBestand(int pBestand)

Der Bestand wird auf den Wert von pBestand gesetzt.

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 generische Klasse BinarySearchTree

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

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

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

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

Auszug aus der Dokumentation des Interfaces ComparableContent<ContentType>

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.

Teilaufgabe a)

a.1)

Geben Sie eine Reihenfolge an, in der die Artikel des in Abbildung 1 gezeigten Baums eingefügt worden sein können.

a.2)

Stellen Sie den Suchbaum dar, der sich ergibt, wenn die neuen Artikel "Tennisschläger" [Artikelnr: 5005; Fachnr: 10, Bestand: 7] und "Tennisball" [Artikelnr: 3000; Fachnr: 81, Bestand: 3, Fachnr: 82, Bestand: 10] in genau dieser Reihenfolge in den bestehenden Suchbaum eingefügt werden.

Hinweis: Nutzen Sie zur Bearbeitung die Vorlage in der Anlage oder fertigen Sie eine Skizze auf Papier an.

a.3)

Geben Sie bezogen auf den dargestellten Kontext einen wichtigen Vorteil an, den ein Suchbaum im Vergleich zu einer nach Artikelnummern sortierten Liste bietet.

Teilaufgabe c)

Der Quellcode der Klasse Lagerverwaltung enthält die folgenden Methoden, die weder dokumentiert noch kommentiert sind:

public List<Artikel> ermittleEtwas(int pMindestbestand) {

return ermittleEtwas(lager, pMindestbestand);}private List<Artikel> ermittleEtwas(

BinarySearchTree<Artikel> pBaum, int pMindestbestand) {

List<Artikel> ergebnis = new List<Artikel>();

if (!pBaum.isEmpty()) {

ergebnis = ermittleEtwas(pBaum.getLeftTree(), pMindestbestand);

Artikel aktuellerArtikel = pBaum.getContent();

List<Fach> liste = aktuellerArtikel.gibFaecher();

int gesamtbestand = 0;

liste.toFirst();

while (liste.hasAccess()) {

gesamtbestand = gesamtbestand + liste.getContent().gibBestand();

liste.next();

}

if (gesamtbestand < pMindestbestand) {

ergebnis.append(aktuellerArtikel);

}

List<Artikel> rechts = ermittleEtwas(pBaum.getRightTree(), pMindestbestand);

ergebnis.concat(rechts);

}

return ergebnis;} Die öffentliche Methode wird mit dem Parameterwert pMindestbestand = 20 aufgerufen. Dabei entspricht der Suchbaum lager dem Suchbaum aus Abbildung 1.

c.1)

Analysieren Sie die beiden Methoden, indem Sie diese auf die Beispieldaten anwenden, dabei die Rückgabe ermitteln und angeben, in welcher Reihenfolge die Artikel des Baums besucht wurden.

c.2)

Erläutern Sie im Sachzusammenhang, welche Information die öffentliche Methode liefert.

Aufgabenstellung: Lagerverwaltung des Onlineshops Infozon

Der Onlineshop Infozon bietet eine große Zahl von Artikeln an und ist in den vergangenen Jahren stark gewachsen. Deshalb braucht das Unternehmen eine neue Software zur Lagerverwaltung. Die IT-Abteilung hat sich aus verschiedenen Gründen dafür entschieden, die Artikel in einem binären Suchbaum abzulegen, der nach der Artikelnummer geordnet ist.

Zu jedem Artikel wird festgehalten, in welchem Regalfach sich wie viele noch verkäufliche Exemplare befinden. Jedes Regalfach darf nur Exemplare eines einzigen Artikels enthalten. Auch wenn ein Regalfach leer geworden ist, bleibt es in der Lagerverwaltung dem Artikel zugeordnet.

Der Lagerbestand enthält die folgenden Beispieldaten:

Ein Ausschnitt der Modellierung ist als Implementationsdiagramm wiedergegeben:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lagerverwaltung

Objekte der Klasse Lagerverwaltung verwalten den Bestand von Artikeln in Fächern.

Auszug aus der Dokumentation der Klasse Lagerverwaltung

Lagerverwaltung()

Ein Lagerverwaltungsobjekt wird initialisiert. Das Lager ist leer.

Artikel ermittle(int pArtikelnr)

Die Anfrage liefert für die Artikelnummer pArtikelnr das entsprechende Artikelobjekt. Falls zu pArtikelnr kein Artikelobjekt existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Artikel pArtikel)

Falls der Artikel mit der gleichen Artikelnummer im Lager noch nicht existiert, wird dieser der Lagerverwaltung hinzugefügt.

void erhoeheBestand(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert, dann wird in dem Fach mit der Fachnummer pFachnr der Bestand um pAnzahl erhöht. Falls das Fach nicht existiert, dann wird dieses mit dem Bestand pAnzahl angelegt.

void entnimm(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert und zu dem Artikel das Fach mit der Fachnummer pFachnr existiert und der Bestand in diesem Fach größer gleich pAnzahl ist, dann wird der Bestand in diesem Fach um pAnzahl verringert.

Die Klasse Artikel

Objekte der Klasse Artikel verwalten die Informationen über einen Artikel und seine Fächer mit Bestandsangaben.

Auszug aus der Dokumentation der Klasse Artikel

Artikel(int pNr, String pBezeichnung)

Ein Artikelobjekt mit der Artikelnummer pNr und der Artikelbezeichnung pBezeichnung wird initialisiert.

int gibNr()

Die Artikelnummer wird zurückgeliefert.

String gibBezeichnung()

Die Artikelbezeichnung wird zurückgeliefert.

List<Fach> gibFaecher()

Eine Liste der Fächer für diesen Artikel wird zurückgeliefert.

boolean isEqual(Artikel pArtikel)

Wenn die Artikelnummer gleich der Artikelnummer des Artikels pArtikel ist, dann wird true zurückgeliefert und sonst false.

boolean isLess(Artikel pArtikel)

Wenn die Artikelnummer kleiner ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

boolean isGreater(Artikel pArtikel)

Wenn die Artikelnummer größer ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

void fuegeHinzu(int pFachnr, int pAnzahl)

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel existiert, dann wird der Bestand um pAnzahl erhöht.

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel nicht existiert, dann wird ein neues Fach mit der Fachnummer pFachnr und dem Bestand pAnzahl angelegt.

Die Klasse Fach

Objekte der Klasse Fach verwalten die Informationen über die Fachnummer und den Bestand in diesem Fach. Die Fachnummer ist für jedes Fach eindeutig.

Auszug aus der Dokumentation der Klasse Fach

Fach(int pFachnr, int pBestand)

Ein Fachobjekt mit der Fachnummer pFachnr und dem Bestand pBestand wird initialisiert.

int gibFachnr()

Die Fachnummer wird zurückgeliefert.

int gibBestand()

Der Bestand wird zurückgeliefert.

void setzeBestand(int pBestand)

Der Bestand wird auf den Wert von pBestand gesetzt.

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 generische Klasse BinarySearchTree

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

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

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

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

Auszug aus der Dokumentation des Interfaces ComparableContent<ContentType>

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.

Teilaufgabe b

b1)

Beschreiben Sie, wie die Klassen Lagerverwaltung, Artikel, Fach, BinarySearchTree, List und das Interface ComparableContent miteinander in Beziehung stehen.

[5 Punkte]

b2)

Begründen Sie, warum die Klasse Artikel das Interface ComparableContent implementiert.

[3 Punkte]

Teilaufgabe e

Folgende Anforderungen sollen zusätzlich im Modell berücksichtigt werden:

Zu jeder Fachnummer soll die Lagerverwaltung das zugehörige Artikelobjekt liefern können. Dazu werden die Fächer zusätzlich in einer effizienten Datenstruktur gehalten, die einen schnellen Zugriff auf jedes Fach erlaubt. Die Zahl der Fächer bleibt in absehbarer Zeit unverändert.

Jedes Fach soll „seinen“ Artikel kennen, verwalten und auf Anfrage herausgeben können.

Die Lagerverwaltung soll ein Fach anhand seiner Fachnummer vollständig leeren können.

Hinweis: Stellen Sie ausschließlich die Abweichungen vom Modell in Abbildung 2 dar.

e1)

Modellieren Sie diese Änderungen als Implementationsdiagramm (z. B. auf Papier zeichnen und fotografieren).

[6 Punkte]

e2)

Erläutern Sie die Umsetzung der Anforderungen in Ihrem Modell.

[6 Punkte]

Aufgabenstellung: Lagerverwaltung des Onlineshops Infozon

Der Onlineshop Infozon bietet eine große Zahl von Artikeln an und ist in den vergangenen Jahren stark gewachsen. Deshalb braucht das Unternehmen eine neue Software zur Lagerverwaltung. Die IT-Abteilung hat sich aus verschiedenen Gründen dafür entschieden, die Artikel in einem binären Suchbaum abzulegen, der nach der Artikelnummer geordnet ist.

Zu jedem Artikel wird festgehalten, in welchem Regalfach sich wie viele noch verkäufliche Exemplare befinden. Jedes Regalfach darf nur Exemplare eines einzigen Artikels enthalten. Auch wenn ein Regalfach leer geworden ist, bleibt es in der Lagerverwaltung dem Artikel zugeordnet.

Der Lagerbestand enthält die folgenden Beispieldaten:

Ein Ausschnitt der Modellierung ist als Implementationsdiagramm wiedergegeben:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lagerverwaltung

Objekte der Klasse Lagerverwaltung verwalten den Bestand von Artikeln in Fächern.

Auszug aus der Dokumentation der Klasse Lagerverwaltung

Lagerverwaltung()

Ein Lagerverwaltungsobjekt wird initialisiert. Das Lager ist leer.

Artikel ermittle(int pArtikelnr)

Die Anfrage liefert für die Artikelnummer pArtikelnr das entsprechende Artikelobjekt. Falls zu pArtikelnr kein Artikelobjekt existiert, dann wird null zurückgeliefert.

void fuegeHinzu(Artikel pArtikel)

Falls der Artikel mit der gleichen Artikelnummer im Lager noch nicht existiert, wird dieser der Lagerverwaltung hinzugefügt.

void erhoeheBestand(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert, dann wird in dem Fach mit der Fachnummer pFachnr der Bestand um pAnzahl erhöht. Falls das Fach nicht existiert, dann wird dieses mit dem Bestand pAnzahl angelegt.

void entnimm(Artikel pArtikel, int pFachnr, int pAnzahl)

Falls in der Lagerverwaltung ein Artikel mit der Artikelnummer pArtikel existiert und zu dem Artikel das Fach mit der Fachnummer pFachnr existiert und der Bestand in diesem Fach größer gleich pAnzahl ist, dann wird der Bestand in diesem Fach um pAnzahl verringert.

Die Klasse Artikel

Objekte der Klasse Artikel verwalten die Informationen über einen Artikel und seine Fächer mit Bestandsangaben.

Auszug aus der Dokumentation der Klasse Artikel

Artikel(int pNr, String pBezeichnung)

Ein Artikelobjekt mit der Artikelnummer pNr und der Artikelbezeichnung pBezeichnung wird initialisiert.

int gibNr()

Die Artikelnummer wird zurückgeliefert.

String gibBezeichnung()

Die Artikelbezeichnung wird zurückgeliefert.

List<Fach> gibFaecher()

Eine Liste der Fächer für diesen Artikel wird zurückgeliefert.

boolean isEqual(Artikel pArtikel)

Wenn die Artikelnummer gleich der Artikelnummer des Artikels pArtikel ist, dann wird true zurückgeliefert und sonst false.

boolean isLess(Artikel pArtikel)

Wenn die Artikelnummer kleiner ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

boolean isGreater(Artikel pArtikel)

Wenn die Artikelnummer größer ist als die Artikelnummer des Artikels pArtikel, dann wird true zurückgeliefert und sonst false.

void fuegeHinzu(int pFachnr, int pAnzahl)

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel existiert, dann wird der Bestand um pAnzahl erhöht.

Falls das Fach mit der Fachnummer pFachnr für diesen Artikel nicht existiert, dann wird ein neues Fach mit der Fachnummer pFachnr und dem Bestand pAnzahl angelegt.

Die Klasse Fach

Objekte der Klasse Fach verwalten die Informationen über die Fachnummer und den Bestand in diesem Fach. Die Fachnummer ist für jedes Fach eindeutig.

Auszug aus der Dokumentation der Klasse Fach

Fach(int pFachnr, int pBestand)

Ein Fachobjekt mit der Fachnummer pFachnr und dem Bestand pBestand wird initialisiert.

int gibFachnr()

Die Fachnummer wird zurückgeliefert.

int gibBestand()

Der Bestand wird zurückgeliefert.

void setzeBestand(int pBestand)

Der Bestand wird auf den Wert von pBestand gesetzt.

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 generische Klasse BinarySearchTree

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

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

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

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Das Interface ComparableContent gibt folgende implizit abstrakte Methoden vor:

Auszug aus der Dokumentation des Interfaces ComparableContent<ContentType>

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.

d)

Zu der nachstehenden Methode der Klasse Artikel sind der Methodenkopf sowie eine kurze Beschreibung vorgegeben:

public void fuegeHinzu(int pFachnr, int pAnzahl)

Ist für diesen Artikel bereits ein Fach mit der Fachnummer pFachnr vorhanden, so wird dessen Bestand um pAnzahl vergrößert. Ist für diesen Artikel dagegen kein Fach mit der Fachnummer pFachnr vorhanden, so wird ein neues Fach mit der Fachnummer pFachnr und dem Bestand pAnzahl erzeugt. Es muss nicht überprüft werden, ob die hinzuzufügenden Artikel im Fach noch Platz haben.

Entwickeln Sie eine algorithmische Strategie, auf deren Grundlage diese Methode arbeiten kann.

Implementieren Sie die Methode entsprechend Ihrer Strategie.

[4 + 8 Punkte]

public void fuegeHinzu(int pFachnr, int pAnzahl) {

}

Aufgabenstellung: App zur Verwaltung von E-Auto-Ladesäulen

Fahrzeuge mit Verbrennungsmotor setzen $\text{CO}_2$ frei, das wesentlich zum Klimawandel beiträgt. Aus diesem Grund strebt Deutschland an, den Verkehr auf Fahrzeuge mit Elektroantrieb (E-Autos) umzustellen. Hierfür entstehen bundesweit an zahlreichen Standorten Ladesäulen, an denen E-Autos aufgeladen werden können.

Die Ladesäulen werden von unterschiedlichen Betreibergesellschaften betrieben. Wer unterwegs sein E-Auto laden möchte, muss sich dafür jeweils bei der Betreibergesellschaft der betreffenden Ladesäule registrieren.

Eine Firma stellt eine App bereit, mit der man E-Autos an Ladesäulen verschiedener Betreibergesellschaften laden kann. Dazu hinterlegt die Fahrerin oder der Fahrer eine Kreditkarte in der App und scannt vor dem Ladevorgang den QR-Code an der Ladesäule. Anschließend leitet die Firma die Bezahlung des Ladevorgangs an die zuständige Betreibergesellschaft weiter.

Die Daten der Firma liegen in einer relationalen Datenbank. Abbildung 1 zeigt eine Teilmodellierung.

Hinweis: Das Attribut Menge gibt die bei dem Ladevorgang übertragene Energiemenge in kWh an.

Das in Abbildung 2 angegebene Datenbankschema setzt die Teilmodellierung um und liegt den folgenden Aufgaben zugrunde. Beispieldaten zu diesem Schema finden sich im Anhang.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Kunde ID · Name · Emailadresse · Kreditkartennummer

1 · Albert Anger · a@anger.de · 1234-5678-9000-4321

2 · Birte Bolweg · b@bolweg.de · 1212-3434-5656-7878

3 · Christa Ciunta · c@ciunta.de · 1111-2222-3333-4444

Betreiber Name · Adresse · Bank · Kontonummer

E-Werke Sauerland · Industrieweg 9, 59755 Arnsberg · Voltbank · 987654321

Pottpower · Werkstraße 3, 45219 Essen · Amperekasse · 232323232

Rheinstrom · An der Fabrik 7, 40597 Düsseldorf · Wattsparkasse · 123456789

Westfalenkraft · Gewerbegasse 8, 48143 Münster · Amperekasse · 100000001

Ladesaeule ID · BetreiberName · Standort · Steckertyp · maximaleLadeleistung

1 · Rheinstrom · Sonnenhang · Typ 2 · 22

2 · Pottpower · Sonnenhang · CCS · 150

3 · Westfalenkraft · Stausee · CCS · 300

4 · Pottpower · Windwinkel · CHAdeMO · 50

5 · Rheinstrom · Windwinkel · Typ 1 · 7

6 · Pottpower · Windwinkel · CCS · 150

7 · Rheinstrom · Windwinkel · CCS · 150

8 · Westfalenkraft · Grüner Strom · Typ 2 · 11

9 · Westfalenkraft · Grüner Strom · Typ 2 · 11

hatGeladen KundeID · LadesaeuleID · Zeitstempel · Menge

1 · 3 · 2023-03-21-14-27 · 35

1 · 2 · 2023-03-28-07-02 · 21

3 · 8 · 2023-03-30-22-54 · 47

1 · 6 · 2023-04-02-18-43 · 29

3 · 1 · 2023-04-06-09-00 · 38

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse LadeApp

Ein Objekt der Klasse LadeApp stellt der Benutzerin bzw. dem Benutzer auf einem mobilen Endgerät die Funktionen des Ladesystems zur Verfügung.

LadeApp()

Ein Objekt der Klasse LadeApp wird initialisiert.

String liefereEtwas()

Diese Anfrage wird in Aufgabenteil e) analysiert.

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.

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 mithilfe der Klasse DatabaseConnector dar. Objekte dieser Klasse werden nur von der Klasse DatabaseConnector erstellt. Die Klasse verfügt über keinen öffentlichen Konstruktor.

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)

Beschreiben Sie die beiden Entitätstypen Kunde und Ladesaeule anhand des Entity-Relationship-Diagramms in Abbildung 1.

Erläutern Sie die im Entity-Relationship-Diagramm enthaltenen Beziehungstypen hatGeladen und betreibt einschließlich ihrer Kardinalitäten im Sachzusammenhang.

Erläutern Sie, auf welche Weise die Beziehungstypen hatGeladen und betreibt des Entity-Relationship-Diagramms im Datenbankschema abgebildet wurden. [3 + 4 + 4 Punkte]

a.1)

a.2)

a.3)

Teilaufgabe d)

Das Unternehmen plant, die App auszubauen. Kundinnen und Kunden sollen damit Reiserouten inklusive Ladestopps planen und sich unterwegs bei Bedarf zu einem Standort mit verfügbaren Ladesäulen leiten lassen können. Dafür soll die Datenbank um folgende Aspekte ergänzt werden:

(i) Für jede Ladesäule soll festgehalten werden können, ob sie gerade belegt ist.

(ii) Kundinnen und Kunden sollen Ladesäulen für bestimmte Zeiträume reservieren können, wozu sie einen Zeitpunkt und die vorgesehene Ladedauer angeben müssen.

Modellieren Sie das Entity-Relationship-Diagramm aus Abbildung 1 so weiter, dass der neue Datenbankentwurf beide Aspekte abdeckt.

Erläutern Sie, wie Ihr Modell die Anforderungen realisiert, und begründen Sie für gegebenenfalls nötige neue Beziehungstypen die gewählten Kardinalitäten. [4 + 5 Punkte]

Hinweis: Entitäts- und Beziehungstypen sowie Attribute ohne Bedeutung für die Erweiterung brauchen nicht gezeichnet zu werden.

d.1)

d.2)

Aufgabenstellung: App zur Verwaltung von E-Auto-Ladesäulen

Fahrzeuge mit Verbrennungsmotor setzen $\text{CO}_2$ frei, das wesentlich zum Klimawandel beiträgt. Aus diesem Grund strebt Deutschland an, den Verkehr auf Fahrzeuge mit Elektroantrieb (E-Autos) umzustellen. Hierfür entstehen bundesweit an zahlreichen Standorten Ladesäulen, an denen E-Autos aufgeladen werden können.

Die Ladesäulen werden von unterschiedlichen Betreibergesellschaften betrieben. Wer unterwegs sein E-Auto laden möchte, muss sich dafür jeweils bei der Betreibergesellschaft der betreffenden Ladesäule registrieren.

Eine Firma stellt eine App bereit, mit der man E-Autos an Ladesäulen verschiedener Betreibergesellschaften laden kann. Dazu hinterlegt die Fahrerin oder der Fahrer eine Kreditkarte in der App und scannt vor dem Ladevorgang den QR-Code an der Ladesäule. Anschließend leitet die Firma die Bezahlung des Ladevorgangs an die zuständige Betreibergesellschaft weiter.

Die Daten der Firma liegen in einer relationalen Datenbank. Abbildung 1 zeigt eine Teilmodellierung.

Hinweis: Das Attribut Menge gibt die bei dem Ladevorgang übertragene Energiemenge in kWh an.

Das in Abbildung 2 angegebene Datenbankschema setzt die Teilmodellierung um und liegt den folgenden Aufgaben zugrunde. Beispieldaten zu diesem Schema finden sich im Anhang.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Kunde ID · Name · Emailadresse · Kreditkartennummer

1 · Albert Anger · a@anger.de · 1234-5678-9000-4321

2 · Birte Bolweg · b@bolweg.de · 1212-3434-5656-7878

3 · Christa Ciunta · c@ciunta.de · 1111-2222-3333-4444

Betreiber Name · Adresse · Bank · Kontonummer

E-Werke Sauerland · Industrieweg 9, 59755 Arnsberg · Voltbank · 987654321

Pottpower · Werkstraße 3, 45219 Essen · Amperekasse · 232323232

Rheinstrom · An der Fabrik 7, 40597 Düsseldorf · Wattsparkasse · 123456789

Westfalenkraft · Gewerbegasse 8, 48143 Münster · Amperekasse · 100000001

Ladesaeule ID · BetreiberName · Standort · Steckertyp · maximaleLadeleistung

1 · Rheinstrom · Sonnenhang · Typ 2 · 22

2 · Pottpower · Sonnenhang · CCS · 150

3 · Westfalenkraft · Stausee · CCS · 300

4 · Pottpower · Windwinkel · CHAdeMO · 50

5 · Rheinstrom · Windwinkel · Typ 1 · 7

6 · Pottpower · Windwinkel · CCS · 150

7 · Rheinstrom · Windwinkel · CCS · 150

8 · Westfalenkraft · Grüner Strom · Typ 2 · 11

9 · Westfalenkraft · Grüner Strom · Typ 2 · 11

hatGeladen KundeID · LadesaeuleID · Zeitstempel · Menge

1 · 3 · 2023-03-21-14-27 · 35

1 · 2 · 2023-03-28-07-02 · 21

3 · 8 · 2023-03-30-22-54 · 47

1 · 6 · 2023-04-02-18-43 · 29

3 · 1 · 2023-04-06-09-00 · 38

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse LadeApp

Ein Objekt der Klasse LadeApp stellt der Benutzerin bzw. dem Benutzer auf einem mobilen Endgerät die Funktionen des Ladesystems zur Verfügung.

LadeApp()

Ein Objekt der Klasse LadeApp wird initialisiert.

String liefereEtwas()

Diese Anfrage wird in Aufgabenteil e) analysiert.

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.

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 mithilfe der Klasse DatabaseConnector dar. Objekte dieser Klasse werden nur von der Klasse DatabaseConnector erstellt. Die Klasse verfügt über keinen öffentlichen Konstruktor.

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)

Aus der Datenbank sollen die nachstehenden Informationen abgerufen werden:

b) (i)

Ein Kunde benötigt eine Ladesäule mit dem Steckertyp CCS. Gesucht sind sämtliche Standorte, an denen mindestens eine Ladesäule mit einem Stecker des Typs CCS verfügbar ist. [3 Punkte]

b) (ii)

Aufgrund von Bauarbeiten am Standort Sonnenhang müssen die Betreibergesellschaften der dort aufgestellten Ladesäulen benachrichtigt werden. Hierfür wird eine Liste dieser Betreibergesellschaften mit Namen und Adressen benötigt, die alphabetisch aufsteigend nach dem Namen der Betreibergesellschaft geordnet ist. [5 Punkte]

Teilaufgabe c)

Gegeben ist die folgende SQL-Anweisung:

1 SELECT Kunde.Name, Kunde.Emailadresse, tmp.Lademenge

2 FROM (

3 SELECT hatGeladen.KundeID, SUM(Menge) AS Lademenge

4 FROM hatGeladen

5 INNER JOIN Ladesaeule

6 ON hatGeladen.LadesaeuleID = Ladesaeule.ID

7 WHERE Ladesaeule.BetreiberName = 'Pottpower'

8 GROUP BY hatGeladen.KundeID

9) AS tmp

10 INNER JOIN Kunde ON tmp.KundeID = Kunde.ID

11 WHERE tmp.Lademenge > 500 c) 1

Analysieren und erläutern Sie die Unterabfrage der Zeilen 3 bis 8. [4 Punkte]

c) 2

Analysieren und erläutern Sie die vollständige SQL-Anweisung. [3 Punkte]

c) 3

Erläutern Sie im Sachzusammenhang, welche Information die vollständige SQL-Anweisung liefert. [3 Punkte]

Teilaufgabe e)

Abbildung 3 zeigt als Implementationsdiagramm einen Ausschnitt aus der Modellierung der App:

Eine neue Mitarbeiterin des Unternehmens findet eine nicht dokumentierte Methode liefereEtwas der Klasse LadeApp:

1 public String liefereEtwas() {

2 String ergebnis = "Kein Ergebnis";

3 String sql = "SELECT Standort, COUNT(*) "

4 + "FROM Ladesaeule "

5 + "GROUP BY Standort";

6

7 datenbank.executeStatement(sql);

8

9 QueryResult qr = datenbank.getCurrentQueryResult();

10 if (qr != null && qr.getRowCount() > 0) {

11 ergebnis = qr.getData()[0][0];

12 int max = Integer.parseInt(qr.getData()[0][1]);

13 for (int i = 1; i < qr.getRowCount(); i++) {

14 int akt = Integer.parseInt(qr.getData()[i][1]);

15 if (akt > max) {

16 ergebnis = qr.getData()[i][0];

17 max = akt;

18 }

19 }

20 }

21 return ergebnis;

22 } e) 1

Analysieren Sie die SQL-Anweisung der Zeilen 3 – 5 und geben Sie anhand der Beispieldaten in der Anlage deren Ergebnis an. [3 Punkte]

e) 2

Analysieren Sie die Methode liefereEtwas, erläutern Sie deren Funktionsweise und geben Sie anhand der Beispieldaten in der Anlage den Rückgabewert an. [3 Punkte]

e) 3

Beschreiben Sie im Sachzusammenhang, welchen Wert die Methode zurückliefert. [2 Punkte]

e) 4

Beurteilen Sie die Aussage der Mitarbeiterin, die Methode lasse sich auch ohne Schleife (wie in den Zeilen 13 – 19) realisieren. [4 Punkte]

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker Jahr für Jahr dieselbe Pflanzenart kultiviert, verliert der Boden fortlaufend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten beanspruchen besonders viele Nährstoffe und heißen deshalb stark zehrend.

Einer zu starken Auszehrung des Bodens beugt man vor, indem man die Abfolge der angebauten Pflanzenarten auf einem Acker klug festlegt. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden nachfolgend vier Gruppen unterschieden:

wenig zehrende Pflanzenarten (w),

mittel zehrende Pflanzenarten (m),

stark zehrende Pflanzenarten (s) und

Zwischenfrüchte (z).

Zwischenfrüchte sind Pflanzenarten, die vor allem der Erholung des Bodens dienen.

Automaten sollen überprüfen, ob eine geplante Fruchtfolge vereinfachte landwirtschaftliche Regeln einhält. Dazu werden Fruchtfolgen als Zeichenketten notiert. Die Zeichenkette smz steht zum Beispiel dafür, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Der Boden lässt sich auch durch sogenannte Mischkulturen fruchtbar halten. Hierbei wird der Acker in Reihen unterteilt, und jede Reihe erhält genau eine Pflanzenart. In benachbarten Reihen stehen Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, neben Rote Bete dagegen ungünstig. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art direkt nebeneinander liegen.

Zur Planung einer Mischkultur wird ein Programm entworfen, dem die folgende Teilmodellierung zugrunde liegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

Ein Objekt der Klasse Pflanzenart modelliert eine Pflanzenart für die Ackerplanung.

Dokumentation der Klasse Pflanzenart

Pflanzenart(String pName)

Ein Objekt der Klasse mit dem Pflanzenart-Namen pName wird initialisiert.

String gibName()

Die Methode liefert den Namen der Pflanzenart.

List<Pflanzenart> gibGutenNachbarn()

Die Methode liefert eine Kopie der Liste aller Pflanzenarten, die gut neben der eigenen Pflanzenart gepflanzt werden können.

void fuegeGutenNachbarnZu(Pflanzenart pPflanzenart)

Die Pflanzenart pPflanzenart wird an die Liste der guten Nachbarpflanzenarten angehängt. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

boolean istGuterNachbar(Pflanzenart pPflanzenart)

Die Methode liefert true, wenn eine Pflanzenart mit demselben Namen wie pPflanzenart in der Liste der guten Nachbarpflanzenarten enthalten ist, ansonsten false.

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 String

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

char charAt(int index)

Die Methode liefert das Zeichen an dem angegebenen Index index. Der Index reicht von 0 einschließlich bis zur length() - 1. Das erste Zeichen besitzt den Index 0, das nächste den Index 1 und so weiter.

int compareTo(String anotherString)

Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject)

Die Methode liefert genau dann true, wenn anObject nicht null ist und wenn das übergebene Objekt anObject vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str)

Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length()

Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix)

Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode dementsprechend ebenfalls den Wert true.

String substring(int beginIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge der Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Index endIndex - 1 der Zeichenkette. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein. Sind beide Werte der Parameter identisch, so wird die leere Zeichenkette "" zurückgegeben.

Abbildung 1 zeigt das Zustandsübergangsdiagramm eines derartigen deterministischen endlichen Automaten A. Als Eingabewort liest er eine Zeichenkette, die eine Fruchtfolge darstellt. Er akzeptiert genau diejenigen Zeichenketten, deren Fruchtfolgen den Acker so zurücklassen, dass in der nächsten Anbauperiode jede beliebige Pflanzengruppe angebaut werden kann. Übergänge, die nicht eingezeichnet sind, führen in einen Fehlerzustand.

a)

Geben Sie ein möglichst kurzes Wort an, in dem jede Pflanzengruppe vorkommt und das der Automat A akzeptiert.

Erläutern Sie im Sachzusammenhang, welche Anforderungen eine Fruchtfolge erfüllen muss, damit der Automat A die zugehörige Zeichenkette akzeptiert. [2 + 5 Punkte]

b)

Man hat festgestellt, dass ein Acker, der durch eine Zwischenfrucht vorbereitet wurde, spätere Erträge erhöht und dass wenig zehrende Pflanzen die Bodenqualität kaum mindern. Daher sollen die Regeln für Fruchtfolgen wie folgt geändert werden:

Jede Fruchtfolge muss mit einer Zwischenfrucht (z) beginnen und enden.

Nach einer Zwischenfrucht (z) darf entweder eine stark (s), eine mittel (m) oder eine wenig (w) zehrende Pflanzenart gepflanzt werden.

Zwischen zwei Zwischenfrüchten in einer Fruchtfolge dürfen gepflanzt werden: entweder einmal oder zweimal Pflanzenarten, die stark (s) oder mittel (m) zehrend sind (d. h. m, s, mm, ms, sm, oder ss),

oder beliebig häufig wenig zehrende Pflanzenarten (w).

Entwickeln Sie das Zustandsübergangsdiagramm eines deterministischen endlichen Automaten B, der exakt die Zeichenketten von Fruchtfolgen akzeptiert, die diese Regeln einhalten.

Zeigen Sie, dass Ihr Automat das Wort zsmz akzeptiert, sz dagegen nicht. [6 + 4 Punkte]

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker Jahr für Jahr dieselbe Pflanzenart kultiviert, verliert der Boden fortlaufend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten beanspruchen besonders viele Nährstoffe und heißen deshalb stark zehrend.

Einer zu starken Auszehrung des Bodens beugt man vor, indem man die Abfolge der angebauten Pflanzenarten auf einem Acker klug festlegt. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden nachfolgend vier Gruppen unterschieden:

wenig zehrende Pflanzenarten (w),

mittel zehrende Pflanzenarten (m),

stark zehrende Pflanzenarten (s) und

Zwischenfrüchte (z).

Zwischenfrüchte sind Pflanzenarten, die vor allem der Erholung des Bodens dienen.

Automaten sollen überprüfen, ob eine geplante Fruchtfolge vereinfachte landwirtschaftliche Regeln einhält. Dazu werden Fruchtfolgen als Zeichenketten notiert. Die Zeichenkette smz steht zum Beispiel dafür, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Der Boden lässt sich auch durch sogenannte Mischkulturen fruchtbar halten. Hierbei wird der Acker in Reihen unterteilt, und jede Reihe erhält genau eine Pflanzenart. In benachbarten Reihen stehen Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, neben Rote Bete dagegen ungünstig. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art direkt nebeneinander liegen.

Zur Planung einer Mischkultur wird ein Programm entworfen, dem die folgende Teilmodellierung zugrunde liegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

Ein Objekt der Klasse Pflanzenart modelliert eine Pflanzenart für die Ackerplanung.

Dokumentation der Klasse Pflanzenart

Pflanzenart(String pName)

Ein Objekt der Klasse mit dem Pflanzenart-Namen pName wird initialisiert.

String gibName()

Die Methode liefert den Namen der Pflanzenart.

List<Pflanzenart> gibGutenNachbarn()

Die Methode liefert eine Kopie der Liste aller Pflanzenarten, die gut neben der eigenen Pflanzenart gepflanzt werden können.

void fuegeGutenNachbarnZu(Pflanzenart pPflanzenart)

Die Pflanzenart pPflanzenart wird an die Liste der guten Nachbarpflanzenarten angehängt. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

boolean istGuterNachbar(Pflanzenart pPflanzenart)

Die Methode liefert true, wenn eine Pflanzenart mit demselben Namen wie pPflanzenart in der Liste der guten Nachbarpflanzenarten enthalten ist, ansonsten false.

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 String

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

char charAt(int index)

Die Methode liefert das Zeichen an dem angegebenen Index index. Der Index reicht von 0 einschließlich bis zur length() - 1. Das erste Zeichen besitzt den Index 0, das nächste den Index 1 und so weiter.

int compareTo(String anotherString)

Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject)

Die Methode liefert genau dann true, wenn anObject nicht null ist und wenn das übergebene Objekt anObject vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str)

Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length()

Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix)

Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode dementsprechend ebenfalls den Wert true.

String substring(int beginIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge der Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Index endIndex - 1 der Zeichenkette. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein. Sind beide Werte der Parameter identisch, so wird die leere Zeichenkette "" zurückgegeben.

Aufgabe 4 – Teilaufgabe c)

Der Boden lässt sich auch durch den Anbau sogenannter Mischkulturen fruchtbar halten. Hierbei wird der Acker in Reihen unterteilt, und jede Reihe erhält genau eine Pflanzenart. In Nachbarreihen setzt man Pflanzenarten, die einander fördern. So passt zum Beispiel eine Reihe Kartoffeln gut neben eine Reihe Buschbohnen, während Kartoffeln neben Rote Bete ungünstig sind. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art direkt nebeneinander angelegt werden.

Zur Planung einer Mischkultur soll ein Programm entstehen, dem die folgende Teilmodellierung zugrunde liegt:

In der Klasse Pflanzenart gibt es die Methode istGuterNachbar, deren Methodenkopf lautet:

public boolean istGuterNachbar(Pflanzenart pPflanzenart)

Die Methode istGuterNachbar liefert true, falls die Liste der guten Nachbarpflanzenarten eine Pflanzenart enthält, die denselben Namen wie pPflanzenart trägt. Andernfalls liefert die Methode false.

1.

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

2.

Implementieren Sie die zuvor beschriebene Methode istGuterNachbar. [6 Punkte]

public boolean istGuterNachbar(Pflanzenart pPflanzenart)

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker Jahr für Jahr dieselbe Pflanzenart kultiviert, verliert der Boden fortlaufend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten beanspruchen besonders viele Nährstoffe und heißen deshalb stark zehrend.

Einer zu starken Auszehrung des Bodens beugt man vor, indem man die Abfolge der angebauten Pflanzenarten auf einem Acker klug festlegt. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden nachfolgend vier Gruppen unterschieden:

wenig zehrende Pflanzenarten (w),

mittel zehrende Pflanzenarten (m),

stark zehrende Pflanzenarten (s) und

Zwischenfrüchte (z).

Zwischenfrüchte sind Pflanzenarten, die vor allem der Erholung des Bodens dienen.

Automaten sollen überprüfen, ob eine geplante Fruchtfolge vereinfachte landwirtschaftliche Regeln einhält. Dazu werden Fruchtfolgen als Zeichenketten notiert. Die Zeichenkette smz steht zum Beispiel dafür, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Der Boden lässt sich auch durch sogenannte Mischkulturen fruchtbar halten. Hierbei wird der Acker in Reihen unterteilt, und jede Reihe erhält genau eine Pflanzenart. In benachbarten Reihen stehen Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, neben Rote Bete dagegen ungünstig. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art direkt nebeneinander liegen.

Zur Planung einer Mischkultur wird ein Programm entworfen, dem die folgende Teilmodellierung zugrunde liegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

Ein Objekt der Klasse Pflanzenart modelliert eine Pflanzenart für die Ackerplanung.

Dokumentation der Klasse Pflanzenart

Pflanzenart(String pName)

Ein Objekt der Klasse mit dem Pflanzenart-Namen pName wird initialisiert.

String gibName()

Die Methode liefert den Namen der Pflanzenart.

List<Pflanzenart> gibGutenNachbarn()

Die Methode liefert eine Kopie der Liste aller Pflanzenarten, die gut neben der eigenen Pflanzenart gepflanzt werden können.

void fuegeGutenNachbarnZu(Pflanzenart pPflanzenart)

Die Pflanzenart pPflanzenart wird an die Liste der guten Nachbarpflanzenarten angehängt. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

boolean istGuterNachbar(Pflanzenart pPflanzenart)

Die Methode liefert true, wenn eine Pflanzenart mit demselben Namen wie pPflanzenart in der Liste der guten Nachbarpflanzenarten enthalten ist, ansonsten false.

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 String

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Ausschnitt aus der Dokumentation der Klasse String

char charAt(int index)

Die Methode liefert das Zeichen an dem angegebenen Index index. Der Index reicht von 0 einschließlich bis zur length() - 1. Das erste Zeichen besitzt den Index 0, das nächste den Index 1 und so weiter.

int compareTo(String anotherString)

Die Methode vergleicht zwei Zeichenketten lexikografisch. Sie liefert einen Integerwert kleiner als 0, wenn der String lexikografisch vor der übergebenen Zeichenkette anotherString anzuordnen ist. Sie liefert einen Integerwert größer als 0, wenn der String lexikografisch nach der übergebenen Zeichenkette anotherString anzuordnen ist. Sind beide Zeichenketten identisch, wird der Wert 0 zurückgegeben.

boolean equals(Object anObject)

Die Methode liefert genau dann true, wenn anObject nicht null ist und wenn das übergebene Objekt anObject vom Typ String ist und die gleiche Zeichenkette repräsentiert.

int indexOf(String str)

Die Methode liefert den Index des ersten Zeichens beim ersten Vorkommen der übergebenen Zeichenkette str. Kommt die übergebene Zeichenkette nicht vor, wird -1 zurückgegeben.

int length()

Die Methode liefert die Länge der Zeichenkette.

boolean startsWith(String prefix)

Die Methode liefert genau dann den Wert true, wenn die Zeichenkette mit dem angegebenen Präfix prefix beginnt. Andernfalls liefert sie den Wert false. Wird eine leere Zeichenkette oder die identische Zeichenkette übergeben, liefert die Methode dementsprechend ebenfalls den Wert true.

String substring(int beginIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Ende der Zeichenkette. Der Wert des Parameters beginIndex darf nicht größer als die Länge der Zeichenkette sein. Ist er gleich der Länge der Zeichenkette, so wird die leere Zeichenkette "" zurückgegeben.

String substring(int beginIndex, int endIndex)

Die Methode liefert einen Teil der Zeichenkette. Dieser Teil beginnt mit dem übergebenen Index beginIndex und reicht bis zum Index endIndex - 1 der Zeichenkette. Der Wert des Parameters endIndex darf nicht größer als die Länge des Strings sein. Der Wert des Parameters beginIndex muss größer oder gleich 0 sein und darf nicht größer als der Wert von endIndex sein. Sind beide Werte der Parameter identisch, so wird die leere Zeichenkette "" zurückgegeben.

Teilaufgabe d)

Mit der nachstehenden Grammatik $G$ lassen sich Mischkulturen aus den drei Pflanzenarten Buschbohne (b), Rote Bete (r) und Kartoffel (k) erzeugen. So steht die Zeichenkette rbkbrr für eine Mischkultur, die aus einer Reihe Rote Bete, gefolgt von einer Reihe Buschbohnen und einer Reihe Kartoffeln, dann einer vierten Reihe Buschbohnen und schließlich zwei Reihen Rote Bete besteht.

Startsymbol:

S

Terminalsymbole:

{b, r, k}

Nichtterminalsymbole:

{S, A, B}

Produktionen:

{ S → AB,

A → BbA | &epsilon;,

B → k | r | rr | &epsilon; }

d.1)

Zeigen Sie, dass rbkbrr zur Sprache $L_G$ gehört, die von $G$ erzeugt wird. [3 Punkte]

d.2)

Beschreiben Sie im Sachzusammenhang, in welcher Weise die Pflanzenreihen von Mischkulturen angeordnet sind, die durch Wörter der Sprache $L_G$ dargestellt werden. [4 Punkte]

d.3)

Begründen Sie, weshalb $G$ keine reguläre Grammatik ist. [2 Punkte]

d.4)

Entwickeln Sie eine reguläre Grammatik, die die Sprache $L_G$ erzeugt. [5 Punkte]

Teilaufgabe e)

Eine Person plant, eine neue Mischkultur mit zunächst unbekannter Reihenanzahl aus Buschbohnen (b), Roter Bete (r) und Kartoffeln (k) anzulegen.

Für die Anlage einer solchen Mischkultur werden zwei Vorschläge gemacht:

(1) Die Reihenfolge Kartoffel, Buschbohne, Rote Bete, Buschbohne wird ein- oder mehrmals hintereinander gepflanzt.

Beispiel: kbrbkbrb

(2) Zuerst stehen mindestens zwei Reihen Kartoffeln, danach eine Reihe Buschbohnen und anschließend Reihen Rote Bete, und zwar ebenso viele wie Kartoffelreihen.

Beispiel: kkkkbrrrr

Die Zeichenkette der geplanten Mischkultur dient als Eingabewort eines endlichen Automaten.

e.1)

Beurteilen Sie, ob ein endlicher Automat mit dem Eingabealphabet {k, r, b} existiert, der entscheidet, ob ein Eingabewort eine Mischkultur der Form (1) darstellt. [4 Punkte]

e.2)

Begründen Sie, dass kein endlicher Automat existiert, der entscheiden kann, ob ein Eingabewort eine Mischkultur der Form (2) darstellt. [4 Punkte]