Abitur NRW Informatik 2023 · LK · Nachtermin

Aufgabenstellung: Digitales Glücksrad

Auf einem Stadtfest will ein Büroartikelmarkt seinen Gästen anbieten, kleine Büroartikel zu gewinnen. Dafür hat der Geschäftsinhaber die Idee eines besonderen „digitalen Glücksrads“ entwickelt und den Informatik-Leistungskurs des örtlichen Schulzentrums mit der Programmierung beauftragt.

Die Besonderheit dieses digitalen Glücksrads besteht darin, dass auf jedem Sektor ein ganzer Gewinnstapel 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 in Abbildung 1 links dargestellten 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").

Gegeben ist das folgende Implementationsdiagramm:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Gewinn

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

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

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

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

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.

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

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

a)

Das rechte Glücksrad aus Abbildung 1 wird noch zwei weitere Male gedreht. Bei der ersten Drehung rückt der Pfeil um drei Sektoren weiter und zeigt danach auf den Sektor mit dem Fineliner, bei der zweiten Drehung rückt er um vier Sektoren weiter und zeigt danach auf den Sektor mit dem Filzstift.

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

[6 Punkte]

c)

Eine Schülerin aus dem Informatik-Leistungskurs hat den folgenden Quelltext für die private Methode wasMacheIch der Klasse Gluecksrad implementiert:

1 private Gewinn wasMacheIch(int pAnzahlSektoren) {

2 if (sektoren.isEmpty()) {

3 return null;

4 } else {

5 Sektor aktuell = sektoren.front();

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

7 sektoren.dequeue();

8 sektoren.enqueue(aktuell);

9 aktuell = sektoren.front();

10 }

11 Gewinn gewinn = aktuell.gibOberstenGewinn();

12 aktuell.entferneOberstenGewinn();

13 if (aktuell.istLeer()) {

14 sektoren.dequeue();

15 return gewinn;

16 } else {

17 sektoren.dequeue();

18 sektoren.enqueue(aktuell);

19 Sektor hilf = sektoren.front();

20 hilf.legeGewinnObenauf(gewinn);

21 while (sektoren.front() != aktuell) {

22 sektoren.enqueue(sektoren.front());

23 sektoren.dequeue();

24 }

25 return null;

26 }

27 }

28 }

Analysieren Sie die Methode wasMacheIch, indem Sie jeweils das Glücksrad in Kurzschreibweise (vgl. Abbildung 2) ermitteln, das nach einem Aufruf mit pAnzahlSektoren = 3 bzw. nach einem Aufruf mit pAnzahlSektoren = 2 entsteht. Gehen Sie bei beiden Aufrufen vom linken Glücksrad in Abbildung 1 aus.

[6 Punkte]

Erläutern Sie im Sachzusammenhang, welche Funktion die Quelltextzeilen 5 bis 10 der Methode wasMacheIch haben.

[3 Punkte]

Erläutern Sie im Sachzusammenhang, welche Funktion die Quelltextzeilen 11 bis 26 der Methode wasMacheIch haben.

[4 Punkte]

Erläutern Sie, welchen Gesamtzweck die Methode wasMacheIch erfüllt.

[2 Punkte]

d)

Die Methode ermittleAnzahlGewinne der Klasse Sektor bestimmt, wie viele Gewinne auf einem Sektor des Glücksrads übereinander gestapelt liegen. Sie hat diesen Methodenkopf:

public int ermittleAnzahlGewinne()

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

[5 Punkte]

Implementieren Sie diese Methode in Quelltext.

[6 Punkte]

e)

Ein Schüler hat der Klasse Gluecksrad die folgende Methode ergänzt:

1 public void simuliereGluecksrad() {

2 while (!sektoren.isEmpty()) {

3 simuliereZufaelligeDrehung();

4 }

5 }

Er wendet die Methode auf das Glücksrad aus Abbildung 1 an und stellt verwundert fest, dass die Simulation in einer Endlosschleife steckenbleibt.

Eine Schülerin erklärt ihm, die Simulation laufe meistens in eine Endlosschleife, weil zusätzlich geprüft werden müsste, ob das Glücksrad nur noch genau einen Sektor hat, auf dem insgesamt jedoch mehr als ein Gewinn liegt.

Begründen Sie im Sachkontext die Aussage der Schülerin.

[4 Punkte]

Geben Sie bezogen auf die Modellierung in Abbildung 3 eine Schleifenbedingung an, die die von der Schülerin genannte Bedingung überprüft.

[3 Punkte]

Beurteilen Sie, inwiefern sich bereits zu Beginn der Simulation erkennen lässt, ob sich sämtliche Gewinne vom Glücksrad entfernen lassen.

[3 Punkte]

Aufgabenstellung: Digitales Glücksrad

Auf einem Stadtfest will ein Büroartikelmarkt seinen Gästen anbieten, kleine Büroartikel zu gewinnen. Dafür hat der Geschäftsinhaber die Idee eines besonderen „digitalen Glücksrads“ entwickelt und den Informatik-Leistungskurs des örtlichen Schulzentrums mit der Programmierung beauftragt.

Die Besonderheit dieses digitalen Glücksrads besteht darin, dass auf jedem Sektor ein ganzer Gewinnstapel 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 in Abbildung 1 links dargestellten 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").

Gegeben ist das folgende Implementationsdiagramm:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Gewinn

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

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

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

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

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.

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

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

b) Beschreiben Sie, in welchen Beziehungen die Klassen Gluecksrad, Gewinn, Sektor, Queue und Stack in der Teilmodellierung aus Abbildung 3 zueinander stehen.

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

[4 + 4 Punkte]

1.

2.

Ihre Antworten wurden abgegeben. Vergleichen Sie Ihre Ausführungen mit den Musterkriterien.

Aufgabenstellung

Ein Informatikkurs hat selbst eine Methode zur Verschlüsselung von Nachrichten entworfen: Jeder Buchstabe des Alphabets wird durch eine Folge aus Nullen und Einsen ersetzt (nachfolgend „Chiffre“ genannt). Die Länge dieser Chiffre kann variieren. Der Einfachheit halber werden in der Aufgabe nur die sieben Buchstaben A, E, H, L, O, T und W betrachtet.

Um ein fehlerfreies Ver- und Entschlüsseln zu gewährleisten, bilden sie die Chiffren der Buchstaben nach diesem Prinzip:

Genau ein Buchstabe gehört zu jedem Blatt eines Binärbaums. Von der Wurzel aus wird untersucht, ob der Weg zum gesuchten Buchstaben in den linken oder in den rechten Teilbaum führt. Der Weg in den linken Teilbaum wird mit 0, der in den rechten Teilbaum mit 1 codiert. Die Nullen und Einsen werden vereinfachend als Zeichenketten abgelegt.

Ein solcher Baum legt eindeutig fest, welche Chiffre zu welchem Buchstaben gehört. Da das Verfahren den Baum nicht vorgibt, ergeben verschiedene Bäume verschiedene Chiffren. Der Baum stellt somit den Schlüssel dar.

Jedem Buchstaben ist eine eigene Chiffre zugeordnet. Man kann alle Chiffren in einer Tabelle sammeln. Zum Schlüssel-Beispiel aus Abbildung 1 erhält man die folgende unvollständige Chiffrier-Tabelle:

Buchstabe · A · O · T · E · W · L · H

Chiffre · · · · · · 1101

Abbildung 2: unvollständige Chiffrier-Tabelle zum Beispiel aus Abbildung 1

Zur Nutzung dieses Verschlüsselungssystems wurde ein Softwaremodell entwickelt, das ausschnittsweise so dargestellt ist:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Chiffrierer

Ein Objekt der Klasse Chiffrierer verwaltet die Entschlüsselung und Verschlüsselung von Zeichenketten mittels eines Binärbaums und einer Tabelle.

Ausschnitt aus der Dokumentation der Klasse Chiffrierer

Chiffrierer()

Ein Objekt der Klasse existiert, es ist nicht initialisiert. Eine Chiffrier-Tabelle und ein Chiffrier-Baum existieren nicht, das Entschlüsseln und das Verschlüsseln sind noch nicht möglich.

void initialisiere(Schluessel pSchluessel, String pPasswort)

Wenn das übergebene Passwort zum übergebenen Schlüssel passt, werden mit diesen Parametern der Chiffrier-Baum und die Chiffrier-Tabelle initialisiert. Das Entschlüsseln und das Verschlüsseln sind dann möglich.

String verschluessele(String pKlartext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Verschlüsselung gelingt, wird der übergebene Klartext verschlüsselt und der entsprechende Geheimtext zurückgegeben.

String entschluessele(String pGeheimtext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Entschlüsselung gelingt, wird der übergebene Geheimtext entschlüsselt und der entsprechende Klartext zurückgegeben.

Dokumentation privater Methoden der Klasse Chiffrierer

void erstelleChiffrierTabelle()

Diese Methode soll in Teilaufgabe c) analysiert werden.

void ermittleChiffrierTabelle(BinaryTree<String> pBaum, String pChiffre)

Diese Methode soll in Teilaufgabe c) analysiert werden.

String entschluesseleBuchstaben(String pChiffre)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, wird der Klarbuchstabe zu der übergebenen Chiffre zurückgegeben. Andernfalls wird null zurückgegeben. Die Chiffre wird nicht auf Korrektheit geprüft.

Die Klasse Schluessel

Ein Objekt der Klasse verwaltet einen Chiffrier-Baum sowie den Zugriff auf den Chiffrier-Baum über ein Passwort.

Ausschnitt aus der Dokumentation der Klasse Schluessel

Schluessel(String pPasswort, BinaryTree<String> pChiffrierBaum)

Ein neues Objekt der Klasse wird mit den übergebenen Parametern initialisiert. Das Passwort wird nicht im Klartext gespeichert sondern ein Prüfwert.

BinaryTree<String> gibChiffrierBaum(String pPasswort)

Sofern das Passwort korrekt ist, wird eine Referenz auf den gespeicherten Chiffrier-Baum zurückgegeben. Andernfalls wird null zurückgegeben.

Dokumentation privater Methoden der Klasse Schluessel

boolean pruefePasswort(String pPasswort)

Die Methode liefert true, wenn die Zeichenkette pPasswort dem beim Erzeugen des Objekts übergebenen Passwort entspricht. Andernfalls liefert sie false.

Die Klasse ChiffrierTabelle

Ein Objekt der Klasse verwaltet die Chiffren zu den Buchstaben analog zum Chiffrier-Baum.

Ausschnitt aus der Dokumentation der Klasse ChiffrierTabelle

ChiffrierTabelle()

Ein neues Objekt der Klasse wird initialisiert. Es ist keine Kombination aus Buchstabe und Chiffre gespeichert.

void fuegeHinzu(String pBuchstabe, String pChiffre)

Die Kombination aus dem Klartext-Buchstaben und der Chiffre für diesen Buchstaben wird gespeichert. Ist für den Buchstaben bereits eine Chiffre vorhanden, wird die vorhandene gelöscht und die zuletzt übergebene gespeichert.

String gibChiffre(String pBuchstabe)

Sofern für den übergebenen Buchstaben eine Chiffre existiert, wird diese zurückgegeben. Andernfalls wird null zurückgegeben.

Die generische Klasse BinaryTree<ContentType>

Mithilfe der generischen Klasse BinaryTree können beliebig viele Objekte vom Typ ContentType in einem Binärbaum verwaltet werden. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der generischen Klasse BinaryTree sind.

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree<ContentType>()

Nach dem Aufruf des Konstruktors existiert ein leerer Binärbaum.

BinaryTree<ContentType>(ContentType pContent)

Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binärbaum und hat pContent als Inhaltsobjekt und zwei leere Teilbäume. Falls der Parameter null ist, wird ein leerer Binärbaum erzeugt.

BinaryTree<ContentType>(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree)

Wenn der Parameter pContent ungleich null ist, wird ein Binärbaum mit pContent als Inhaltsobjekt und den beiden Teilbäume pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum als leerer Binärbaum eingefügt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binärbaum erzeugt.

boolean isEmpty()

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

void setContent(ContentType pContent)

Wenn der Binärbaum leer ist, wird der Parameter pContent als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefügt. Ist der Binärbaum nicht leer, wird das Inhaltsobjekt durch pContent ersetzt. Die Teilbäume werden nicht geändert. Wenn pContent null ist, bleibt der Binärbaum unverändert.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Binärbaumes. Wenn der Binärbaum leer ist, wird null zurückgegeben.

void setLeftTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als linken Teilbaum. Falls der Parameter null ist, ändert sich nichts.

void setRightTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, ändert sich nichts.

BinaryTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

BinaryTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

Die Klasse String

Ein Objekt der Klasse String kann eine Zeichenkette, die eine URL repräsentieren soll, auf Korrektheit geprüft werden.

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 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 der Parameter 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 ein Zeichen vor endIndex. 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.

a)

Der in Abbildung 1 als Chiffrier-Baum abgebildete Schlüssel dient dazu, Klartexte zu verschlüsseln und Geheimtexte wieder zu entschlüsseln.

Vervollständigen Sie die in Abbildung 2 gegebene Chiffrier-Tabelle.

Buchstabe · A · O · T · E · W · L · H

Chiffre · · · · · · 1101

Ermitteln Sie sowohl den Geheimtext für den Klartext $k_1 = \text{"WELT"}$ als auch den Klartext für den Geheimtext $g_2 = \text{"11100011011101001"}$.

Erläutern Sie allgemein, wie ein einzelner Buchstabe verschlüsselt und eine einzelne Chiffre entschlüsselt wird, und zwar jeweils mithilfe eines Chiffrier-Baums und mithilfe einer Chiffrier-Tabelle.

b)

Erläutern Sie mithilfe von Abbildung 3 und der Dokumentationen im Anhang, auf welche grundlegende Weise der direkte Zugriff auf den Chiffrier-Baum in der Klasse Schluessel geschützt wird.

e)

Passwortgeschützte Informationen lassen sich mit modernen Informatiksystemen angreifen, etwa indem automatisiert sehr viele mögliche Passwörter systematisch durchprobiert werden.

Die Klasse Schluessel soll so erweitert werden, dass ein derartiger Angriff durch Ausprobieren des Passworts auf den geschützten Chiffrier-Baum praktisch nicht mehr durchführbar ist. Bei bereits vorhandenen Schlüsseln soll dafür keine Passwortänderung erforderlich sein.

Entwickeln Sie eine Strategie, mit der der Chiffrier-Baum gegen einen solchen Angriff geschützt wird.

Modellieren Sie Ihre Strategie als Erweiterung der Klasse Schluessel (vgl. Abbildung 3) und stellen Sie die erweiterte Klasse in Form eines Implementationsdiagramms dar.

Erläutern Sie, auf welche Weise Ihre Modellierung die Strategie umsetzt.

Aufgabenstellung

Ein Informatikkurs hat selbst eine Methode zur Verschlüsselung von Nachrichten entworfen: Jeder Buchstabe des Alphabets wird durch eine Folge aus Nullen und Einsen ersetzt (nachfolgend „Chiffre“ genannt). Die Länge dieser Chiffre kann variieren. Der Einfachheit halber werden in der Aufgabe nur die sieben Buchstaben A, E, H, L, O, T und W betrachtet.

Um ein fehlerfreies Ver- und Entschlüsseln zu gewährleisten, bilden sie die Chiffren der Buchstaben nach diesem Prinzip:

Genau ein Buchstabe gehört zu jedem Blatt eines Binärbaums. Von der Wurzel aus wird untersucht, ob der Weg zum gesuchten Buchstaben in den linken oder in den rechten Teilbaum führt. Der Weg in den linken Teilbaum wird mit 0, der in den rechten Teilbaum mit 1 codiert. Die Nullen und Einsen werden vereinfachend als Zeichenketten abgelegt.

Ein solcher Baum legt eindeutig fest, welche Chiffre zu welchem Buchstaben gehört. Da das Verfahren den Baum nicht vorgibt, ergeben verschiedene Bäume verschiedene Chiffren. Der Baum stellt somit den Schlüssel dar.

Jedem Buchstaben ist eine eigene Chiffre zugeordnet. Man kann alle Chiffren in einer Tabelle sammeln. Zum Schlüssel-Beispiel aus Abbildung 1 erhält man die folgende unvollständige Chiffrier-Tabelle:

Buchstabe · A · O · T · E · W · L · H

Chiffre · · · · · · 1101

Abbildung 2: unvollständige Chiffrier-Tabelle zum Beispiel aus Abbildung 1

Zur Nutzung dieses Verschlüsselungssystems wurde ein Softwaremodell entwickelt, das ausschnittsweise so dargestellt ist:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Chiffrierer

Ein Objekt der Klasse Chiffrierer verwaltet die Entschlüsselung und Verschlüsselung von Zeichenketten mittels eines Binärbaums und einer Tabelle.

Ausschnitt aus der Dokumentation der Klasse Chiffrierer

Chiffrierer()

Ein Objekt der Klasse existiert, es ist nicht initialisiert. Eine Chiffrier-Tabelle und ein Chiffrier-Baum existieren nicht, das Entschlüsseln und das Verschlüsseln sind noch nicht möglich.

void initialisiere(Schluessel pSchluessel, String pPasswort)

Wenn das übergebene Passwort zum übergebenen Schlüssel passt, werden mit diesen Parametern der Chiffrier-Baum und die Chiffrier-Tabelle initialisiert. Das Entschlüsseln und das Verschlüsseln sind dann möglich.

String verschluessele(String pKlartext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Verschlüsselung gelingt, wird der übergebene Klartext verschlüsselt und der entsprechende Geheimtext zurückgegeben.

String entschluessele(String pGeheimtext)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, nicht null übergeben wird und die Entschlüsselung gelingt, wird der übergebene Geheimtext entschlüsselt und der entsprechende Klartext zurückgegeben.

Dokumentation privater Methoden der Klasse Chiffrierer

void erstelleChiffrierTabelle()

Diese Methode soll in Teilaufgabe c) analysiert werden.

void ermittleChiffrierTabelle(BinaryTree<String> pBaum, String pChiffre)

Diese Methode soll in Teilaufgabe c) analysiert werden.

String entschluesseleBuchstaben(String pChiffre)

Sofern das Chiffrierer-Objekt korrekt initialisiert ist, wird der Klarbuchstabe zu der übergebenen Chiffre zurückgegeben. Andernfalls wird null zurückgegeben. Die Chiffre wird nicht auf Korrektheit geprüft.

Die Klasse Schluessel

Ein Objekt der Klasse verwaltet einen Chiffrier-Baum sowie den Zugriff auf den Chiffrier-Baum über ein Passwort.

Ausschnitt aus der Dokumentation der Klasse Schluessel

Schluessel(String pPasswort, BinaryTree<String> pChiffrierBaum)

Ein neues Objekt der Klasse wird mit den übergebenen Parametern initialisiert. Das Passwort wird nicht im Klartext gespeichert sondern ein Prüfwert.

BinaryTree<String> gibChiffrierBaum(String pPasswort)

Sofern das Passwort korrekt ist, wird eine Referenz auf den gespeicherten Chiffrier-Baum zurückgegeben. Andernfalls wird null zurückgegeben.

Dokumentation privater Methoden der Klasse Schluessel

boolean pruefePasswort(String pPasswort)

Die Methode liefert true, wenn die Zeichenkette pPasswort dem beim Erzeugen des Objekts übergebenen Passwort entspricht. Andernfalls liefert sie false.

Die Klasse ChiffrierTabelle

Ein Objekt der Klasse verwaltet die Chiffren zu den Buchstaben analog zum Chiffrier-Baum.

Ausschnitt aus der Dokumentation der Klasse ChiffrierTabelle

ChiffrierTabelle()

Ein neues Objekt der Klasse wird initialisiert. Es ist keine Kombination aus Buchstabe und Chiffre gespeichert.

void fuegeHinzu(String pBuchstabe, String pChiffre)

Die Kombination aus dem Klartext-Buchstaben und der Chiffre für diesen Buchstaben wird gespeichert. Ist für den Buchstaben bereits eine Chiffre vorhanden, wird die vorhandene gelöscht und die zuletzt übergebene gespeichert.

String gibChiffre(String pBuchstabe)

Sofern für den übergebenen Buchstaben eine Chiffre existiert, wird diese zurückgegeben. Andernfalls wird null zurückgegeben.

Die generische Klasse BinaryTree<ContentType>

Mithilfe der generischen Klasse BinaryTree können beliebig viele Objekte vom Typ ContentType in einem Binärbaum verwaltet werden. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der generischen Klasse BinaryTree sind.

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree<ContentType>()

Nach dem Aufruf des Konstruktors existiert ein leerer Binärbaum.

BinaryTree<ContentType>(ContentType pContent)

Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binärbaum und hat pContent als Inhaltsobjekt und zwei leere Teilbäume. Falls der Parameter null ist, wird ein leerer Binärbaum erzeugt.

BinaryTree<ContentType>(ContentType pContent, BinaryTree<ContentType> pLeftTree, BinaryTree<ContentType> pRightTree)

Wenn der Parameter pContent ungleich null ist, wird ein Binärbaum mit pContent als Inhaltsobjekt und den beiden Teilbäume pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum als leerer Binärbaum eingefügt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binärbaum erzeugt.

boolean isEmpty()

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

void setContent(ContentType pContent)

Wenn der Binärbaum leer ist, wird der Parameter pContent als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefügt. Ist der Binärbaum nicht leer, wird das Inhaltsobjekt durch pContent ersetzt. Die Teilbäume werden nicht geändert. Wenn pContent null ist, bleibt der Binärbaum unverändert.

ContentType getContent()

Diese Anfrage liefert das Inhaltsobjekt des Binärbaumes. Wenn der Binärbaum leer ist, wird null zurückgegeben.

void setLeftTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als linken Teilbaum. Falls der Parameter null ist, ändert sich nichts.

void setRightTree(BinaryTree<ContentType> pTree)

Wenn der Binärbaum leer ist, wird pTree nicht angehängt. Andernfalls erhält der Binärbaum den übergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, ändert sich nichts.

BinaryTree<ContentType> getLeftTree()

Diese Anfrage liefert den linken Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

BinaryTree<ContentType> getRightTree()

Diese Anfrage liefert den rechten Teilbaum des Binärbaumes. Der Binärbaum ändert sich nicht. Wenn der Binärbaum leer ist, wird null zurückgegeben.

Die Klasse String

Ein Objekt der Klasse String kann eine Zeichenkette, die eine URL repräsentieren soll, auf Korrektheit geprüft werden.

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 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 der Parameter 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 ein Zeichen vor endIndex. 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.

c)

Die privaten Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle der Klasse Chiffrierer stellen eine zentrale interne Funktionalität der Klasse zur Verfügung.

1 private void erstelleChiffrierTabelle() {

2 chiffrierTabelle = new ChiffrierTabelle();

3 ermittleChiffrierTabelle(chiffrierBaum, "");

4 }

5

6 private void ermittleChiffrierTabelle(

7 BinaryTree<String> pBaum, String pChiffre) {

8 if (pBaum.getLeftTree().isEmpty()

9 && pBaum.getRightTree().isEmpty()) {

10 chiffrierTabelle.fuegeHinzu(pBaum.getContent(), pChiffre);

11 } else {

12 ermittleChiffrierTabelle(pBaum.getLeftTree(),

13 pChiffre + "0");

14 ermittleChiffrierTabelle(pBaum.getRightTree(),

15 pChiffre + "1");

16 }

17 }

Anhand der Beispieldaten aus Abbildung 1 sollen die Methoden untersucht werden. Hierfür wird die parameterlose Methode erstelleChiffrierTabelle (Zeilen 1 bis 4) aufgerufen. Das Objekt der Klasse Chiffrierer hält unter dem Bezeichner chiffrierBaum den in Abbildung 1 dargestellten Chiffrier-Baum.

Analysieren Sie die Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle und erläutern Sie, wie sie funktionieren.

Wenden Sie die Methoden erstelleChiffrierTabelle und ermittleChiffrierTabelle auf die Beispieldaten aus Abbildung 1 an und dokumentieren Sie, in welcher Reihenfolge die Methode ermittleChiffrierTabelle aufgerufen wird, indem Sie jeweils den übergebenen Parameter pChiffre angeben.

d)

Die private Methode entschluesseleBuchstaben der Klasse Chiffrierer entschlüsselt mithilfe des verwalteten Chiffrier-Baums einen übergebenen Geheimtext und liefert den zugehörigen Buchstaben als Zeichenkette, falls ein gültiger Schlüssel gesetzt ist. Andernfalls ist der Rückgabewert null. Die private Methode wird von der öffentlichen Methode entschluessele benutzt. Ihr Methodenkopf lautet:

private String entschluesseleBuchstaben(String pChiffre)

Implementieren Sie die Methode entschluesseleBuchstaben.

Ergänzen Sie Ihren Quellcode um Kommentare.

Hinweis: Nehmen Sie an, dass pChiffre eine zum gespeicherten Chiffrier-Baum passende gültige Chiffre ist, falls dieser vorhanden ist.

Sachkontext: E-Auto-Ladesäulen-App

Fahrzeuge mit Verbrennungsmotor setzen $\text{CO}_2$ frei, das erheblich zum Klimawandel beiträgt. Daher strebt Deutschland an, den Straßenverkehr auf Elektrofahrzeuge (E-Autos) zu verlagern. Zu diesem Zweck entstehen bundesweit an zahlreichen Standorten Ladesäulen für E-Autos.

Die Ladesäulen werden von unterschiedlichen Betreibergesellschaften betrieben. Wer sein E-Auto unterwegs 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 in der App eine Kreditkarte und scannt vor dem Ladevorgang den QR-Code der Ladesäule. Anschließend leitet die Firma die Zahlung für den Ladevorgang an die Betreibergesellschaft der Ladesäule weiter.

Die Daten der Firma liegen in einer relationalen Datenbank. Abbildung 1 zeigt einen Teil der Modellierung.

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

Datenbankschema

Das in Abbildung 2 gezeigte Datenbankschema setzt die Teilmodellierung um und wird im Weiteren zugrunde gelegt. Beispieldaten zu diesem Schema finden sich im Anhang.

Implementationsdiagramm der App

Die App soll die Standorte aller Ladesäulen eines bestimmten Steckertyps innerhalb eines vorgegebenen Umkreises um die aktuelle Position der Benutzerin bzw. des Benutzers anzeigen. Abbildung 3 enthält als Implementationsdiagramm einen Ausschnitt der App-Modellierung.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema

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. Hier sind nur die für die Bearbeitung des Aufgabenteils e) relevanten Methoden dokumentiert.

Dokumentation der Klasse LadeApp

LadeApp()

Ein Objekt der Klasse LadeApp wird initialisiert.

List<String> gibStandorteImUmkreis(double pEntfernung, String pSteckertyp)

Die Anfrage gibt eine Liste mit den Namen von allen passenden Standorten von Ladesäulen zurück. Dabei gilt:

Die Liste enthält alle Standorte aus der Datenbank, an denen mindestens eine Ladesäule mit dem im Parameter pSteckertyp übergebenen Steckertyp zur Verfügung steht und

bei denen die Entfernung von der aktuellen Position der Benutzerin bzw. des Benutzers maximal den in dem Parameter pEntfernung in km übergebenen Wert hat.

Wenn ein Fehler in der Datenbankverbindung auftritt, wird eine leere Liste zurückgegeben.

double gibEntfernungZurAktuellenPosition(String pStandort)

Es wird die Distanz in km zwischen der aktuellen Position der Benutzerin bzw. des Benutzers und dem im Parameter pStandort übergebenen Standort ermittelt.

Die generische Klasse List

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

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

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

Die Klasse DatabaseConnector

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

Dokumentation der Klasse DatabaseConnector

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

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

void executeStatement(String pSQLStatement)

Der Auftrag schickt den im Parameter pSQLStatement enthaltenen SQL-Befehl an die Datenbank ab.

Handelt es sich bei pSQLStatement um einen SQL-Befehl, der eine Ergebnismenge liefert, so kann dieses Ergebnis anschließend mit der Methode getCurrentQueryResult abgerufen werden.

QueryResult getCurrentQueryResult()

Die Anfrage liefert das Ergebnis des letzten mit der Methode executeStatement an die Datenbank geschickten SQL-Befehls als Objekt vom Typ QueryResult zurück.

Wurde bisher kein SQL-Befehl abgeschickt oder ergab der letzte Aufruf von executeStatement keine Ergebnismenge (z. B. bei einem INSERT-Befehl oder einem Syntaxfehler), so wird null geliefert.

String getErrorMessage()

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

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

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

Dokumentation der Klasse QueryResult

String[][] getData()

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

String[] getColumnNames()

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

String[] getColumnTypes()

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

int getRowCount()

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

int getColumnCount()

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

Teilaufgabe a)

a.1

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

[3 Punkte]

a.2

Erläutern Sie im Sachzusammenhang die Beziehungstypen hatGeladen und betreibt des Entity-Relationship-Diagramms unter Einbeziehung der Kardinalitäten.

[4 Punkte]

a.3

Erläutern Sie, auf welche Weise die Beziehungstypen hatGeladen und betreibt des Entity-Relationship-Diagramms im Datenbankschema realisiert wurden.

[4 Punkte]

Teilaufgabe d)

Die Datenbank der App soll so ergänzt werden, dass Nutzerinnen und Nutzer zusätzlich Angaben zu ihrem E-Auto speichern können. E-Autos desselben Modells besitzen stets den gleichen Anschlusstyp und laden ausschließlich an Ladesäulen mit passendem Steckertyp.

Ein Praktikant schlägt hierfür eine Erweiterung der Relation Kunde vor und nennt zur Verdeutlichung neben dem Relationenschema auch Beispieldaten:

Kunde( ID, Name, Emailadresse, Kreditkartennummer, Modell, Anschlusstyp)

Kunde

ID

Name

Emailadresse

Kreditkartennummer

Modell

Anschlusstyp

1

Albert Anger

a@anger.de

1234-5678-9000-4321

Buzzcar

CCS

2

Birte Bolweg

b@bolweg.de

1212-3434-5656-7878

Nicola

Typ 2

3

Christa Ciunta

c@ciunta.de

1111-2222-3333-4444

Buzzcar

CCS

d.1

Beurteilen Sie das Relationenschema der Relation Kunde, das der Praktikant vorschlägt, bezüglich der ersten drei Normalformen.

[4 Punkte]

d.2

Überführen Sie das Relationenschema der Relation Kunde, das der Praktikant vorschlägt, in die dritte Normalform.

[5 Punkte]

Sachkontext: E-Auto-Ladesäulen-App

Fahrzeuge mit Verbrennungsmotor setzen $\text{CO}_2$ frei, das erheblich zum Klimawandel beiträgt. Daher strebt Deutschland an, den Straßenverkehr auf Elektrofahrzeuge (E-Autos) zu verlagern. Zu diesem Zweck entstehen bundesweit an zahlreichen Standorten Ladesäulen für E-Autos.

Die Ladesäulen werden von unterschiedlichen Betreibergesellschaften betrieben. Wer sein E-Auto unterwegs 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 in der App eine Kreditkarte und scannt vor dem Ladevorgang den QR-Code der Ladesäule. Anschließend leitet die Firma die Zahlung für den Ladevorgang an die Betreibergesellschaft der Ladesäule weiter.

Die Daten der Firma liegen in einer relationalen Datenbank. Abbildung 1 zeigt einen Teil der Modellierung.

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

Datenbankschema

Das in Abbildung 2 gezeigte Datenbankschema setzt die Teilmodellierung um und wird im Weiteren zugrunde gelegt. Beispieldaten zu diesem Schema finden sich im Anhang.

Implementationsdiagramm der App

Die App soll die Standorte aller Ladesäulen eines bestimmten Steckertyps innerhalb eines vorgegebenen Umkreises um die aktuelle Position der Benutzerin bzw. des Benutzers anzeigen. Abbildung 3 enthält als Implementationsdiagramm einen Ausschnitt der App-Modellierung.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema

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. Hier sind nur die für die Bearbeitung des Aufgabenteils e) relevanten Methoden dokumentiert.

Dokumentation der Klasse LadeApp

LadeApp()

Ein Objekt der Klasse LadeApp wird initialisiert.

List<String> gibStandorteImUmkreis(double pEntfernung, String pSteckertyp)

Die Anfrage gibt eine Liste mit den Namen von allen passenden Standorten von Ladesäulen zurück. Dabei gilt:

Die Liste enthält alle Standorte aus der Datenbank, an denen mindestens eine Ladesäule mit dem im Parameter pSteckertyp übergebenen Steckertyp zur Verfügung steht und

bei denen die Entfernung von der aktuellen Position der Benutzerin bzw. des Benutzers maximal den in dem Parameter pEntfernung in km übergebenen Wert hat.

Wenn ein Fehler in der Datenbankverbindung auftritt, wird eine leere Liste zurückgegeben.

double gibEntfernungZurAktuellenPosition(String pStandort)

Es wird die Distanz in km zwischen der aktuellen Position der Benutzerin bzw. des Benutzers und dem im Parameter pStandort übergebenen Standort ermittelt.

Die generische Klasse List

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

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

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

Die Klasse DatabaseConnector

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

Dokumentation der Klasse DatabaseConnector

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

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

void executeStatement(String pSQLStatement)

Der Auftrag schickt den im Parameter pSQLStatement enthaltenen SQL-Befehl an die Datenbank ab.

Handelt es sich bei pSQLStatement um einen SQL-Befehl, der eine Ergebnismenge liefert, so kann dieses Ergebnis anschließend mit der Methode getCurrentQueryResult abgerufen werden.

QueryResult getCurrentQueryResult()

Die Anfrage liefert das Ergebnis des letzten mit der Methode executeStatement an die Datenbank geschickten SQL-Befehls als Objekt vom Typ QueryResult zurück.

Wurde bisher kein SQL-Befehl abgeschickt oder ergab der letzte Aufruf von executeStatement keine Ergebnismenge (z. B. bei einem INSERT-Befehl oder einem Syntaxfehler), so wird null geliefert.

String getErrorMessage()

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

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

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

Dokumentation der Klasse QueryResult

String[][] getData()

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

String[] getColumnNames()

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

String[] getColumnTypes()

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

int getRowCount()

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

int getColumnCount()

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

Teilaufgabe b)

Es sollen die folgenden Informationen aus der Datenbank abgefragt werden:

(i)

Für den Standort Sonnenhang soll eine Liste ausgegeben werden, die alle auftretenden Kombinationen aus Steckertyp und maximaler Ladeleistung enthält, wobei keine Kombination mehrfach erscheinen darf. Die Sortierung erfolgt zuerst absteigend nach der maximalen Ladeleistung, anschließend aufsteigend nach der Bezeichnung des Steckertyps. [4 Punkte]

(ii)

Gesucht ist eine Liste aller Kundinnen und Kunden, die an Ladesäulen des Betreibers Pottpower Strom geladen haben. Zu jeder Person sollen der Name, die E-Mail-Adresse und die gesamte geladene Energiemenge angezeigt werden. Die Sortierung soll absteigend nach der Gesamtlademenge erfolgen. [5 Punkte]

Teilaufgabe c)

Gegeben ist die folgende SQL-Anweisung:

1 SELECT Ladesaeule.Standort, COUNT(*) AS Anzahl

2 FROM Ladesaeule

3 WHERE Ladesaeule.ID NOT IN (

4 SELECT hatGeladen.LadesaeuleID

5 FROM hatGeladen

6 WHERE Zeitstempel BETWEEN '2023-03-01-00-00'

7 AND '2023-03-31-23-59'

8)

9 GROUP BY Ladesaeule.Standort

10 ORDER BY Anzahl DESC

c.1)

Analysieren und erläutern Sie zuerst die Unterabfrage, die sich in den Zeilen 4 bis 7 befindet. [4 Punkte]

c.2)

Analysieren und erläutern Sie die SQL-Anweisung als Ganzes. [4 Punkte]

c.3)

Erläutern Sie im Sachzusammenhang, welche Information mit der gesamten SQL-Anweisung bestimmt wird. [2 Punkte]

Teilaufgabe e)

Die App soll die Standorte aller Ladesäulen anzeigen können, die einen bestimmten Steckertyp haben und innerhalb eines festgelegten Umkreises um die aktuelle Position der Nutzerin bzw. des Nutzers liegen. Abbildung 3 zeigt als Implementationsdiagramm einen Ausschnitt der Modellierung der App.

Ein Softwareentwickler hat die Methode gibStandorteImUmkreis bereits teilweise bearbeitet:

1 public List<String> gibStandorteImUmkreis(double pEntfernung,

2 String pSteckertyp) {

3 String sql = "SELECT DISTINCT Standort "

4 + "FROM Ladesaeule "

5 + "WHERE Ladesaeule.Steckertyp = "

6 + "'" + pSteckertyp + "';";

7

8 datenbank.executeStatement(sql);

9

10 QueryResult qr = datenbank.getCurrentQueryResult();

11 List<String> ergebnis = new List<String>();

12 if (qr != null) {

13 // TODO: Hier weiterarbeiten!!!

14 }

15 return ergebnis;

16 }

e.1)

Analysieren Sie den unvollständigen Programmtext der Methode gibStandorteImUmkreis und beurteilen Sie bezüglich aller drei Punkte der Methodendokumentation, ob der Entwickler diese schon umgesetzt hat. [4 Punkte]

e.2)

Entwickeln und beschreiben Sie ein algorithmisches Verfahren, mit dem der vorliegende Programmtext so erweitert wird, dass alle Punkte der Methodendokumentation erfüllt sind. [3 Punkte]

e.3)

Vervollständigen Sie den Programmtext der Methode gibStandorteImUmkreis so, dass alle Punkte der Methodendokumentation umgesetzt werden (Ersatz für Zeile 13). [4 Punkte]

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker jedes Jahr dieselbe Pflanzenart kultiviert, entzieht sie dem Boden fortwährend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten benötigen besonders viele Nährstoffe aus dem Boden und gelten deshalb als stark zehrend.

Ein zu starkes Auszehren des Bodens kann verhindert werden, indem die zeitliche Abfolge der auf einem Acker angebauten Pflanzenarten klug festgelegt wird. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden hier 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 vereinfachten landwirtschaftlichen Regeln genügt. Fruchtfolgen werden hierfür als Zeichenketten notiert. So bedeutet die Zeichenkette smz, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Abbildung 1 zeigt das Zustandsübergangsdiagramm eines solchen deterministischen endlichen Automaten A. Als Eingabewort erhält er eine Zeichenkette, die eine Fruchtfolge darstellt. Er akzeptiert genau die Zeichenketten der Fruchtfolgen, nach denen der Acker in der nächsten Anbauperiode für jede beliebige Pflanzengruppe bereit ist. Übergänge, die nicht eingezeichnet sind, führen in einen Fehlerzustand.

Der Boden kann auch durch sogenannte Mischkulturen fruchtbar gehalten werden. Hierbei wird der Acker in Reihen aufgeteilt, wobei jede Reihe nur mit einer Pflanzenart bestellt wird. Nebeneinanderliegende Reihen erhalten Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, dagegen schlecht neben Rote Bete. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art aneinandergrenzen.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

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

Signatur / Konstruktor / Methode · Beschreibung

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> gibGuteNachbarn() · 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.

Die Klasse Ackerplanung

Ein Objekt der Klasse Ackerplanung verwaltet Pflanzenarten für die Ackerplanung.

Signatur / Konstruktor / Methode · Beschreibung

Ackerplanung() · Ein neues Objekt wird initialisiert. Es werden zu Beginn noch keine Pflanzenarten verwaltet.

List<Pflanzenart> gibAllePflanzenarten() · Die Methode liefert eine Liste mit allen verwalteten Pflanzenarten.

void fuegePflanzenartZu(Pflanzenart pPflanzenart) · Die Methode hängt das Objekt pPflanzenart an die Liste der verwalteten Pflanzenarten allePflanzenarten an. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

List<Pflanzenart> passtZwischen(Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) · Die Methode liefert eine Liste mit Pflanzenarten, die aufgrund von landwirtschaftlichen Kriterien zwischen die beiden Pflanzenarten pPflanzenart1 und pPflanzenart2 gepflanzt werden können.

Die generische Klasse List<ContentType>

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

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

Signatur · Beschreibung

List() · Eine leere Liste wird erzeugt.

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

boolean hasAccess() · Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

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

void toFirst() · Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast() · Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

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

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

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

void insert(ContentType pContent) · Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls 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 (Ausschnitt)

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Signatur · Beschreibung

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 der 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.

a)

Geben Sie ein Wort von möglichst geringer Länge an, in dem alle Pflanzengruppen vorkommen und das der Automat A akzeptiert.

Erläutern Sie im Sachzusammenhang, welchen Bedingungen Fruchtfolgen genügen müssen, damit die zugehörigen Zeichenketten vom Automaten A akzeptiert werden.

b)

Weil Zwischenfrüchte die Erträge der folgenden Pflanzen erhöhen, sollen die Regeln für Fruchtfolgen angepasst werden. Das Zustandsübergangsdiagramm des Automaten A soll so erweitert werden, dass

unmittelbar vor jeder stark zehrenden Pflanzenart (s) eine Zwischenfrucht (z) in der Fruchtfolge steht.

Außerdem soll die Fruchtfolge mit einer Zwischenfrucht (z) enden.

Abgesehen von diesen Einschränkungen soll der neue Automat genau die Wörter akzeptieren, die auch der Automat A akzeptiert (vgl. Abbildung 1).

Modifizieren Sie das Zustandsübergangsdiagramm des Automaten A gemäß der beschriebenen Erweiterung.

Zeigen Sie, dass Ihr Automat zswz akzeptiert, sz hingegen nicht.

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker jedes Jahr dieselbe Pflanzenart kultiviert, entzieht sie dem Boden fortwährend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten benötigen besonders viele Nährstoffe aus dem Boden und gelten deshalb als stark zehrend.

Ein zu starkes Auszehren des Bodens kann verhindert werden, indem die zeitliche Abfolge der auf einem Acker angebauten Pflanzenarten klug festgelegt wird. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden hier 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 vereinfachten landwirtschaftlichen Regeln genügt. Fruchtfolgen werden hierfür als Zeichenketten notiert. So bedeutet die Zeichenkette smz, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Abbildung 1 zeigt das Zustandsübergangsdiagramm eines solchen deterministischen endlichen Automaten A. Als Eingabewort erhält er eine Zeichenkette, die eine Fruchtfolge darstellt. Er akzeptiert genau die Zeichenketten der Fruchtfolgen, nach denen der Acker in der nächsten Anbauperiode für jede beliebige Pflanzengruppe bereit ist. Übergänge, die nicht eingezeichnet sind, führen in einen Fehlerzustand.

Der Boden kann auch durch sogenannte Mischkulturen fruchtbar gehalten werden. Hierbei wird der Acker in Reihen aufgeteilt, wobei jede Reihe nur mit einer Pflanzenart bestellt wird. Nebeneinanderliegende Reihen erhalten Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, dagegen schlecht neben Rote Bete. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art aneinandergrenzen.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

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

Signatur / Konstruktor / Methode · Beschreibung

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> gibGuteNachbarn() · 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.

Die Klasse Ackerplanung

Ein Objekt der Klasse Ackerplanung verwaltet Pflanzenarten für die Ackerplanung.

Signatur / Konstruktor / Methode · Beschreibung

Ackerplanung() · Ein neues Objekt wird initialisiert. Es werden zu Beginn noch keine Pflanzenarten verwaltet.

List<Pflanzenart> gibAllePflanzenarten() · Die Methode liefert eine Liste mit allen verwalteten Pflanzenarten.

void fuegePflanzenartZu(Pflanzenart pPflanzenart) · Die Methode hängt das Objekt pPflanzenart an die Liste der verwalteten Pflanzenarten allePflanzenarten an. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

List<Pflanzenart> passtZwischen(Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) · Die Methode liefert eine Liste mit Pflanzenarten, die aufgrund von landwirtschaftlichen Kriterien zwischen die beiden Pflanzenarten pPflanzenart1 und pPflanzenart2 gepflanzt werden können.

Die generische Klasse List<ContentType>

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

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

Signatur · Beschreibung

List() · Eine leere Liste wird erzeugt.

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

boolean hasAccess() · Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

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

void toFirst() · Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast() · Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

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

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

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

void insert(ContentType pContent) · Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls 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 (Ausschnitt)

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Signatur · Beschreibung

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 der 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.

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

Die Klasse Ackerplanung enthält die Methode passtZwischen mit dem folgenden Methodenkopf:

public List<Pflanzenart> passtZwischen(

Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) Die Methode passtZwischen liefert als Ergebnis eine Liste aller Pflanzenarten, die sowohl für pPflanzenart1 als auch für pPflanzenart2 gute Nachbarpflanzenarten darstellen.

1.

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

2.

Implementieren Sie die beschriebene Methode passtZwischen.

public List<Pflanzenart> passtZwischen(Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) { }

Sachkontext: Fruchtfolgen und Mischkulturen

Wird auf einem Acker jedes Jahr dieselbe Pflanzenart kultiviert, entzieht sie dem Boden fortwährend dieselben Nährstoffe, bis sie nicht mehr in ausreichender Menge vorliegen. Man spricht dann davon, dass der Boden „ausgezehrt“ ist. Manche Pflanzenarten benötigen besonders viele Nährstoffe aus dem Boden und gelten deshalb als stark zehrend.

Ein zu starkes Auszehren des Bodens kann verhindert werden, indem die zeitliche Abfolge der auf einem Acker angebauten Pflanzenarten klug festgelegt wird. Diese Abfolge heißt „Fruchtfolge“. Vereinfachend werden hier 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 vereinfachten landwirtschaftlichen Regeln genügt. Fruchtfolgen werden hierfür als Zeichenketten notiert. So bedeutet die Zeichenkette smz, dass auf einem Acker erst eine stark zehrende, dann eine mittel zehrende Pflanzenart und zuletzt eine Zwischenfrucht angebaut wird.

Abbildung 1 zeigt das Zustandsübergangsdiagramm eines solchen deterministischen endlichen Automaten A. Als Eingabewort erhält er eine Zeichenkette, die eine Fruchtfolge darstellt. Er akzeptiert genau die Zeichenketten der Fruchtfolgen, nach denen der Acker in der nächsten Anbauperiode für jede beliebige Pflanzengruppe bereit ist. Übergänge, die nicht eingezeichnet sind, führen in einen Fehlerzustand.

Der Boden kann auch durch sogenannte Mischkulturen fruchtbar gehalten werden. Hierbei wird der Acker in Reihen aufgeteilt, wobei jede Reihe nur mit einer Pflanzenart bestellt wird. Nebeneinanderliegende Reihen erhalten Pflanzenarten, die sich gegenseitig fördern. So passen Kartoffeln gut neben Buschbohnen, dagegen schlecht neben Rote Bete. Bei einigen Pflanzenarten können auch mehrere Reihen derselben Art aneinandergrenzen.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Pflanzenart

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

Signatur / Konstruktor / Methode · Beschreibung

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> gibGuteNachbarn() · 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.

Die Klasse Ackerplanung

Ein Objekt der Klasse Ackerplanung verwaltet Pflanzenarten für die Ackerplanung.

Signatur / Konstruktor / Methode · Beschreibung

Ackerplanung() · Ein neues Objekt wird initialisiert. Es werden zu Beginn noch keine Pflanzenarten verwaltet.

List<Pflanzenart> gibAllePflanzenarten() · Die Methode liefert eine Liste mit allen verwalteten Pflanzenarten.

void fuegePflanzenartZu(Pflanzenart pPflanzenart) · Die Methode hängt das Objekt pPflanzenart an die Liste der verwalteten Pflanzenarten allePflanzenarten an. Ist bereits ein Objekt mit dem Namen von pPflanzenart in der Liste enthalten, so passiert nichts.

List<Pflanzenart> passtZwischen(Pflanzenart pPflanzenart1, Pflanzenart pPflanzenart2) · Die Methode liefert eine Liste mit Pflanzenarten, die aufgrund von landwirtschaftlichen Kriterien zwischen die beiden Pflanzenarten pPflanzenart1 und pPflanzenart2 gepflanzt werden können.

Die generische Klasse List<ContentType>

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

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

Signatur · Beschreibung

List() · Eine leere Liste wird erzeugt.

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

boolean hasAccess() · Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst liefert sie den Wert false.

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

void toFirst() · Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

void toLast() · Falls die Liste nicht leer ist, wird das letzte Objekt der Liste aktuelles Objekt. Ist die Liste leer, geschieht nichts.

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

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

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

void insert(ContentType pContent) · Falls es ein aktuelles Objekt gibt ( hasAccess() == true), wird ein neues Objekt pContent vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt gibt ( hasAccess() == false), wird pContent in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt. Falls 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 (Ausschnitt)

Ein Objekt der Klasse String repräsentiert eine Zeichenkette.

Signatur · Beschreibung

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 der 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) (3 + 4 + 2 + 5 Punkte)

Mit der unten angegebenen 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, in der zuerst eine Reihe Rote Bete, anschließend eine Reihe Buschbohnen, dann eine Reihe Kartoffeln, als vierte Reihe wieder Buschbohnen und zum Schluss zwei Reihen Rote Bete angebaut werden.

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 zu der Sprache $L_G$ gehört, die von $G$ erzeugt wird.

d.2)

Beschreiben Sie im Sachzusammenhang, in welcher Weise die Pflanzenreihen jener Mischkulturen aufeinanderfolgen, deren Wörter in der Sprache $L_G$ liegen.

d.3)

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

d.4)

Entwickeln Sie eine reguläre Grammatik, die die Sprache $L_G$ erzeugt.

Teilaufgabe e) (4 + 4 Punkte)

Eine neue Mischkultur mit zunächst unbekannter Reihenanzahl soll aus Buschbohnen (b), Rote Bete (r) und Kartoffeln (k) angelegt werden. Dafür existieren zwei Vorschläge zur Anordnung:

(1) Es wird einmal oder mehrmals die folgende Folge von vier Reihen nebeneinander gepflanzt: Kartoffel, Buschbohne, Rote Bete, Buschbohne.

Beispiel: kbrbkbrb

(2) Es kommen zunächst mindestens zwei Reihen Kartoffeln, dann eine Reihe Buschbohnen und dann die entsprechende Anzahl an Rote-Bete-Reihen. Insgesamt sind es genauso viele Reihen Kartoffeln wie Rote Bete.

Beispiel: kkkkbrrrr

Die Zeichenkette der geplanten Mischkultur dient als Eingabewort für einen endlichen Automaten.

e.1)

Beurteilen Sie, ob ein endlicher Automat mit dem Eingabealphabet {k, r, b} existiert, der feststellen kann, ob ein Eingabewort einer Mischkultur der Form (1) entspricht.

e.2)

Erläutern Sie, wie ein Kellerautomat mit dem Eingabealphabet {k, r, b} arbeitet, der ein Eingabewort genau dann akzeptiert, wenn es einer Mischkultur der Form (2) entspricht.