Abitur NRW Informatik 2021 · GK · Nachtermin

Aufgabenstellung: Das Spiel Brainbreaker

Im Spiel Brainbreaker gilt es, einen verborgenen Code aus vier Stellen herauszufinden. Jede Stelle enthält dabei eine Ziffer zwischen 0 und 5. Der Spieler gibt Tipps ab, die ebenfalls aus vier Ziffern von 0 bis 5 bestehen und vom System bewertet werden. Anhand dieser Bewertung lässt sich erkennen, wie dicht ein Tipp am gesuchten Code liegt.

Die Bewertung erfolgt nach diesen Regeln (siehe Beispiel in Abbildung 1):

Haben Tipp und geheimer Code an derselben Stelle dieselbe Ziffer, so wird dies als so genannter Volltreffer (V) mit 10 Punkten bewertet.

Haben Tipp und geheimer Code an unterschiedlichen Stellen dieselbe Ziffer, so wird dies als so genannter Teiltreffer (T) mit einem Punkt bewertet.

Jede Stelle des geheimen Codes darf höchstens einmal bei der Bewertung berücksichtigt werden.

Volltreffer werden nicht zusätzlich als Teiltreffer gewertet.

Die Gesamtbewertung eines Tipps ist die Summe der Punkte aller seiner Stellen; nur sie wird dem Spieler als Rückmeldung genannt. Man möchte den geheimen Code mit möglichst wenigen Tipps finden.

Für die Umsetzung des Spiels Brainbreaker hat Jana ein Implementationsdiagramm erstellt, von dem Abbildung 2 einen Ausschnitt darstellt. Die Dokumentation der relevanten Methoden steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Ziffernfolge

Objekte der Klasse Ziffernfolge dienen zur Verwaltung von vierstelligen Ziffernfolgen für das Spiel Brainbreaker. Die Ziffern einer Ziffernfolge sind ganze Zahlen. Die einzelnen Ziffern können gesetzt und abgefragt werden.

Ausschnitt aus der Dokumentation der Klasse Ziffernfolge

Ziffernfolge(String pCodierung)

Ein neues Objekt zum Verwalten einer Ziffernfolge wird erzeugt. Die Zeichen der übergebenen Zeichenkette müssen Ziffern sein. Die Werte der Ziffernfolge werden diesen Ziffern gemäß initialisiert. Ist pCodierung == null, so werden die vier Ziffern mit dem Wert -1 initialisiert.

int gibWert(int pIndex)

Die Belegung der Ziffernfolge an der Stelle pIndex wird zurückgeliefert. Die erste Stelle hat den Index 0.

void setzeWert(int pIndex, int pWert)

Die Belegung der Ziffernfolge an der Stelle pIndex wird auf pWert gesetzt.

int ermittleBewertung(Ziffernfolge pAndereFolge)

Es wird ermittelt, welche Punktezahl die übergebene Ziffernfolge pAndereFolge erreichen würde, wenn das Instanzobjekt dem geheimen Code entsprechen würde.

Die Klasse Spiel

Objekte der Klasse Spiel verwalten die Ziffernfolgen für eine Partie des Spiels Brainbreaker.

Ausschnitt aus der Dokumentation der Klasse Spiel

Spiel()

Ein neues Objekt zum Verwalten der Ziffernfolgen einer Partie Brainbreaker wird erzeugt. Es wird gemäß den Spielregeln eine zufällige Ziffernfolge als geheimer Code generiert.

Ziffernfolge gibTipp(int pIndex)

Es wird der pIndex-te abgegebene Tipp des Spielers zurückgeliefert. Ist pIndex größer als die Anzahl der Tipps oder ist pIndex < 1, so wird null zurückgeliefert.

int gibAnzahlTipps()

Es wird die Anzahl bisher abgegebener Tipps zurückgeliefert.

void fuegeTippHinzu(Ziffernfolge pTipp)

Ein neuer Tipp wird hinzugefügt, die Anzahl der abgegebenen Tipps um eins erhöht.

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.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

Teilaufgabe a)

a.1)

Ermitteln Sie, welche Bewertung der Tipp 5555 erhält, wenn der geheime Code 2553 lautet, und begründen Sie diese Bewertung.

a.2)

Ermitteln Sie einen Tipp, der für den geheimen Code 2553 mit 22 bewertet wird.

a.3)

Erläutern Sie, aus welchem Grund es keinen Tipp geben kann, der mit 31 bewertet wird.

Teilaufgabe c)

Janas Freund Ben hat für die Klasse Ziffernfolge die folgende Methode ermittleVolltreffer geschrieben:

1 private int ermittleVolltreffer (Ziffernfolge pAndereFolge) {

2 int z = 0;

3 for (int i = 0; i < 4; i++) {

4 for (int j = 0; j < 4; j++) {

5 if (i == j && gibWert(i) == pAndereFolge.gibWert(j)) {

6 z = z + 10;

7 }

8 }

9 }

10 return z;

11 }

Analysieren Sie die Methode ermittleVolltreffer, indem Sie für die folgenden übergebenen Ziffernfolgen jeweils ermitteln, welchen Wert die Methode zurückgibt, wobei der geheime Code 0554 ist:

Übergebene Ziffernfolge

Geheimer Code

Rückgabewert

3250

0554

4545

0554

5555

0554

Teilaufgabe d)

Jana will die Klasse Spiel um die Methode erstelleGefilterteListe ergänzen. Aus einer übergebenen Liste von Ziffernfolgen soll sie diejenigen auswählen, die mit pLetzteBewertung bewertet würden, falls pLetzterTipp der zuletzt abgegebene Tipp ist, und die damit als geheimer Code möglich sind. Der Methodenkopf lautet:

public List<Ziffernfolge> erstelleGefilterteListe(

List<Ziffernfolge> pZiffernfolgen,

Ziffernfolge pLetzterTipp,

int pLetzteBewertung)

d.1)

Entwickeln Sie eine algorithmische Strategie, mit der die Methode erstelleGefilterteListe implementiert werden kann.

d.2)

Implementieren Sie die Methode erstelleGefilterteListe.

Aufgabenstellung: Das Spiel Brainbreaker

Im Spiel Brainbreaker gilt es, einen verborgenen Code aus vier Stellen herauszufinden. Jede Stelle enthält dabei eine Ziffer zwischen 0 und 5. Der Spieler gibt Tipps ab, die ebenfalls aus vier Ziffern von 0 bis 5 bestehen und vom System bewertet werden. Anhand dieser Bewertung lässt sich erkennen, wie dicht ein Tipp am gesuchten Code liegt.

Die Bewertung erfolgt nach diesen Regeln (siehe Beispiel in Abbildung 1):

Haben Tipp und geheimer Code an derselben Stelle dieselbe Ziffer, so wird dies als so genannter Volltreffer (V) mit 10 Punkten bewertet.

Haben Tipp und geheimer Code an unterschiedlichen Stellen dieselbe Ziffer, so wird dies als so genannter Teiltreffer (T) mit einem Punkt bewertet.

Jede Stelle des geheimen Codes darf höchstens einmal bei der Bewertung berücksichtigt werden.

Volltreffer werden nicht zusätzlich als Teiltreffer gewertet.

Die Gesamtbewertung eines Tipps ist die Summe der Punkte aller seiner Stellen; nur sie wird dem Spieler als Rückmeldung genannt. Man möchte den geheimen Code mit möglichst wenigen Tipps finden.

Für die Umsetzung des Spiels Brainbreaker hat Jana ein Implementationsdiagramm erstellt, von dem Abbildung 2 einen Ausschnitt darstellt. Die Dokumentation der relevanten Methoden steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Ziffernfolge

Objekte der Klasse Ziffernfolge dienen zur Verwaltung von vierstelligen Ziffernfolgen für das Spiel Brainbreaker. Die Ziffern einer Ziffernfolge sind ganze Zahlen. Die einzelnen Ziffern können gesetzt und abgefragt werden.

Ausschnitt aus der Dokumentation der Klasse Ziffernfolge

Ziffernfolge(String pCodierung)

Ein neues Objekt zum Verwalten einer Ziffernfolge wird erzeugt. Die Zeichen der übergebenen Zeichenkette müssen Ziffern sein. Die Werte der Ziffernfolge werden diesen Ziffern gemäß initialisiert. Ist pCodierung == null, so werden die vier Ziffern mit dem Wert -1 initialisiert.

int gibWert(int pIndex)

Die Belegung der Ziffernfolge an der Stelle pIndex wird zurückgeliefert. Die erste Stelle hat den Index 0.

void setzeWert(int pIndex, int pWert)

Die Belegung der Ziffernfolge an der Stelle pIndex wird auf pWert gesetzt.

int ermittleBewertung(Ziffernfolge pAndereFolge)

Es wird ermittelt, welche Punktezahl die übergebene Ziffernfolge pAndereFolge erreichen würde, wenn das Instanzobjekt dem geheimen Code entsprechen würde.

Die Klasse Spiel

Objekte der Klasse Spiel verwalten die Ziffernfolgen für eine Partie des Spiels Brainbreaker.

Ausschnitt aus der Dokumentation der Klasse Spiel

Spiel()

Ein neues Objekt zum Verwalten der Ziffernfolgen einer Partie Brainbreaker wird erzeugt. Es wird gemäß den Spielregeln eine zufällige Ziffernfolge als geheimer Code generiert.

Ziffernfolge gibTipp(int pIndex)

Es wird der pIndex-te abgegebene Tipp des Spielers zurückgeliefert. Ist pIndex größer als die Anzahl der Tipps oder ist pIndex < 1, so wird null zurückgeliefert.

int gibAnzahlTipps()

Es wird die Anzahl bisher abgegebener Tipps zurückgeliefert.

void fuegeTippHinzu(Ziffernfolge pTipp)

Ein neuer Tipp wird hinzugefügt, die Anzahl der abgegebenen Tipps um eins erhöht.

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.

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

Teilaufgabe b)

Für die Programmierung des Spiels Brainbreaker hat Jana ein Implementationsdiagramm erstellt. In Abbildung 2 ist ein Teil dieses Diagramms dargestellt. Im Anhang befindet sich eine Dokumentation der wichtigen Methoden.

b)

Erläutern Sie die in Abbildung 2 dargestellte Teilmodellierung bezogen auf den Sachzusammenhang. [9 Punkte]

Teilaufgabe e)

In der nächsten Version soll sich der Schwierigkeitsgrad des Spiels einstellen lassen, sodass es noch reizvoller wird. Dafür sind zusätzlich diese Anforderungen umzusetzen:

Für jedes Spiel soll sich die Länge des Geheimcodes festlegen lassen.

Spielende sollen Hinweise nacheinander einzeln anfordern können. Jeder Hinweis nennt die Ziffer des Geheimcodes an einer zufällig gewählten Stelle. Zudem soll festgehalten werden, wie viele Hinweise ein Spielender schon genutzt hat, und diese Anzahl soll abrufbar sein.

e.1

Modellieren Sie die oben beschriebenen Anforderungen als Erweiterung des Implementationsdiagramms in Abbildung 2. [8 Punkte]

Hinweis: Methoden und Attribute aus Abbildung 2, die unverändert bleiben, müssen nicht angegeben bzw. dargestellt werden. Sie können ein Foto Ihres erweiterten Klassendiagramms hochladen oder die Änderungen (neue bzw. angepasste Attribute und Methoden) beschreiben.

e.2

Erläutern Sie, auf welche Weise Ihr Implementationsdiagramm die Anforderungen umsetzt. [3 Punkte]

Sachkontext: Automatisierte Verkehrszählung

Damit sich das Verkehrsaufkommen auf Fernstraßen besser beurteilen lässt, finden regelmäßig Verkehrszählungen statt. Im Zuge der Digitalisierung soll dieser Vorgang nun automatisch ablaufen. Eine Kamera und eine passende Bilderkennungssoftware sollen dazu die Ortskürzel (auch Ortskennzeichen genannt) der vorbeifahrenden Kraftfahrzeuge (Kfz) selbstständig identifizieren und zählen. Die Daten werden in einem binären Suchbaum gespeichert, dessen Ordnung sich aus der alphabetischen Reihenfolge der Ortskürzel ergibt.

Die Zählsoftware soll um weitere Merkmale erweitert werden: Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Bei der Fahrzeugklasse soll unterschieden werden zwischen dem typischen Personenverkehr in PKW einerseits und allen sonstigen, insbesondere größeren Kraftfahrzeugen andererseits (z. B. Bussen, Traktoren und Lastkraftwagen).

Grundlage der Software ist das Implementationsdiagramm, von dem Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der benutzten Klassen steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Zaehlung

Ein Objekt dieser Klasse führt die Verkehrszählung automatisiert durch, d. h., es dient zur Erfassung, Verwaltung und Auswertung aller Zählungsdaten.

Zaehlung()

Ein Objekt der Klasse wird initialisiert. Alle notwendigen Rahmenbedingungen zur Durchführung der Zählung sind nach Ausführung des Konstruktors erledigt (z. B. Initialisierung der Datenstrukturen).

void erfasseKfz(String pOrtsKuerzel, char pKfzKlasse)

Wenn ein vorbeifahrendes Kraftfahrzeug erkannt wurde, wird diese Methode aufgerufen. Ihr wird das Ortskürzel des Kraftfahrzeugs als Parameter pOrtsKuerzel übergeben. Der Parameter pKfzKlasse beinhaltet ein Kürzel für die Fahrzeugklasse (vorgesehen sind P für PKW oder S für sonstige Kraftfahrzeuge).

Ist zum übergebenen Ortskürzel bereits ein Knoten im binären Suchbaum verkehrszaehlung enthalten, wird er ermittelt, andernfalls wird ein neuer Knoten mit einem neuen Inhaltsobjekt aus der Klasse OrtsDaten erzeugt und dem Baum hinzugefügt. Der Liste aus Messungen, die durch das Inhaltsobjekt des Knotens verwaltet werden, wird ein neues Objekt der Klasse Messung hinzugefügt, das den aktuellen Zeitstempel und die übergebene Kfz-Klasse enthält.

List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Die Anfrage liefert eine Liste aus Objekten der Klasse OrtsDaten zurück, deren Ortskürzel aus der durch pRegion näher bestimmten Region stammen. Jedes Element des Felds (Arrays) gibt ein anderes Ortskürzel der Region an.

int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2)

Diese Methode analysiert die Zählungsdaten innerhalb des angegebenen Zeitraums.

Die Klasse OrtsDaten

Ein Objekt dieser Klasse verwaltet alle Messdaten zu einem bestimmten Ortskürzel.

OrtsDaten(String pOrtsKuerzel)

Ein Objekt der Klasse wird initialisiert. Dabei wird das Ortskürzel durch den Parameter pOrtsKuerzel im Klartext übergeben. Die durch dieses Objekt verwaltete Liste der Messungen ist nachher leer.

String gibOrtsKuerzel()

Das Ortskürzel wird zurückgegeben.

int gibAnzahlMessungen()

Die Anzahl der bisher aufgezeichneten Messungen wird zurückgegeben.

List<Messung> gibMessungen()

Die Liste aller Messungen, die zum zugehörigen Ortskürzel gespeichert sind, wird zurückgegeben. Liegen keine Messungen vor, wird eine leere Liste zurückgegeben.

void erfasseMessung(Messung pMessung)

Das als pMessung übergebene Objekt wird an die Liste der Messungen, die durch dieses Objekt verwaltet werden, angehängt.

boolean isLess(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch vor demjenigen des Objekts pOrt liegt, sonst false.

boolean isEqual(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das Ortskürzel des Objekts pOrt demjenigen Ortskürzel gleich ist, das durch dieses Objekt verwaltet wird, sonst false.

boolean isGreater(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch hinter demjenigen des Objekts pOrt liegt, sonst false.

Die Klasse Messung

Ein Objekt dieser Klasse verwaltet die individuellen Messdaten einer bestimmten Messung zu einem bestimmten Ortskennzeichen.

Messung(char pKfzKlasse)

Ein Objekt dieser Klasse wird erzeugt, das als Kfz-Klasse den durch pKfzKlasse übergebenen Wert und einen Zeitstempel mit dem aktuellen Zeitpunkt enthält. Für pKfzKlasse sind die Werte P für PKW und S für sonstige Kraftfahrzeuge erlaubt.

Zeitstempel gibZeitstempel()

Der Zeitstempel dieser Messung wird zurückgegeben.

char gibKfzKlasse()

Das Kürzel der Kraftfahrzeugklasse zu dieser Messung wird zurückgegeben.

Die Klasse Zeitstempel

Ein Objekt dieser Klasse verwaltet einen sekundengenauen Zeitpunkt.

Zeitstempel()

Ein Zeitstempel mit aktuellem Datum und sekundengenauer Uhrzeit wird erzeugt.

Zeitstempel(int pJahr, int pMonat, int pTag, int pStunde, int pMinute, int pSekunde)

Ein Zeitstempel mit dem durch die Parameter bestimmten Datum und sekundengenauer Uhrzeit wird erzeugt.

boolean liegtInnerhalb(Zeitstempel pVon, Zeitstempel pBis)

Wenn dieser Zeitstempel innerhalb des durch die beiden Zeitstempel pVon und pBis angegebenen Zeitraums liegt, wird true zurückgegeben, sonst false.

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.

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

Teilaufgabe a) [8 Punkte]

An einer Zählstelle haben bislang Kraftfahrzeuge mit den Ortskürzeln AC, MS, MS und PB die Messstelle passiert. Der folgende binäre Suchbaum stellt diese Messungen dar:

a.1)

a.2)

Erweitern Sie den binären Suchbaum aus Abbildung 1, wobei die Kamera nun nacheinander die Ortskürzel ST, MS, BI, RS, SO, MS, OB, HSK, PB, DO erfasst.

Zeichnen Sie jeweils den entstehenden Suchbaum nach dem Einfügen der dritten zusätzlichen Messung (nach BI) sowie nach dem Einfügen der letzten zusätzlichen Messung (nach DO).

Teilaufgabe c) [12 Punkte]

Um die Zählungsergebnisse auszuwerten, sollen die erfassten Daten nach verschiedenen Kriterien gefiltert werden. Zunächst sollen die Ortsdaten gesammelt werden, deren Ortskürzel zu einer bestimmten Region gehören. Dafür ist die Methode ermittleRegionDaten zu implementieren. Ihr wird ein Feld (Array) von String-Objekten mit den Ortskürzeln der gewünschten Region übergeben, und sie gibt eine Liste von Objekten der Klasse OrtsDaten zurück.

c.1)

c.2)

public List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Teilaufgabe d) [12 Punkte]

Die Implementation der Klasse Zaehlung enthält die undokumentierte Methode ermittleEtwas:

1 public int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2) {

2 return ermittleEtwas(verkehrszaehlung, pZ1, pZ2);

3 }

4

5 private int ermittleEtwas(BinarySearchTree<OrtsDaten> pBaum,

6 Zeitstempel pZ1, Zeitstempel pZ2) {

7 int ret = 0;

8 if (!pBaum.isEmpty()) {

9 OrtsDaten aktuell = pBaum.getContent();

10 List<Messung> lmAktuell = aktuell.gibMessungen();

11 lmAktuell.toFirst();

12 while (lmAktuell.hasAccess()) {

13 Zeitstempel zs =

14 lmAktuell.getContent().gibZeitstempel();

15 if (zs.liegtInnerhalb(pZ1, pZ2)) {

16 ret = ret + 1;

17 }

18 lmAktuell.next();

19 }

20 ret = ret + ermittleEtwas(pBaum.getLeftTree(),

21 pZ1, pZ2);

22 ret = ret + ermittleEtwas(pBaum.getRightTree(),

23 pZ1, pZ2);

24 }

25 return ret;

26 }

d)

Sachkontext: Automatisierte Verkehrszählung

Damit sich das Verkehrsaufkommen auf Fernstraßen besser beurteilen lässt, finden regelmäßig Verkehrszählungen statt. Im Zuge der Digitalisierung soll dieser Vorgang nun automatisch ablaufen. Eine Kamera und eine passende Bilderkennungssoftware sollen dazu die Ortskürzel (auch Ortskennzeichen genannt) der vorbeifahrenden Kraftfahrzeuge (Kfz) selbstständig identifizieren und zählen. Die Daten werden in einem binären Suchbaum gespeichert, dessen Ordnung sich aus der alphabetischen Reihenfolge der Ortskürzel ergibt.

Die Zählsoftware soll um weitere Merkmale erweitert werden: Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Bei der Fahrzeugklasse soll unterschieden werden zwischen dem typischen Personenverkehr in PKW einerseits und allen sonstigen, insbesondere größeren Kraftfahrzeugen andererseits (z. B. Bussen, Traktoren und Lastkraftwagen).

Grundlage der Software ist das Implementationsdiagramm, von dem Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der benutzten Klassen steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Zaehlung

Ein Objekt dieser Klasse führt die Verkehrszählung automatisiert durch, d. h., es dient zur Erfassung, Verwaltung und Auswertung aller Zählungsdaten.

Zaehlung()

Ein Objekt der Klasse wird initialisiert. Alle notwendigen Rahmenbedingungen zur Durchführung der Zählung sind nach Ausführung des Konstruktors erledigt (z. B. Initialisierung der Datenstrukturen).

void erfasseKfz(String pOrtsKuerzel, char pKfzKlasse)

Wenn ein vorbeifahrendes Kraftfahrzeug erkannt wurde, wird diese Methode aufgerufen. Ihr wird das Ortskürzel des Kraftfahrzeugs als Parameter pOrtsKuerzel übergeben. Der Parameter pKfzKlasse beinhaltet ein Kürzel für die Fahrzeugklasse (vorgesehen sind P für PKW oder S für sonstige Kraftfahrzeuge).

Ist zum übergebenen Ortskürzel bereits ein Knoten im binären Suchbaum verkehrszaehlung enthalten, wird er ermittelt, andernfalls wird ein neuer Knoten mit einem neuen Inhaltsobjekt aus der Klasse OrtsDaten erzeugt und dem Baum hinzugefügt. Der Liste aus Messungen, die durch das Inhaltsobjekt des Knotens verwaltet werden, wird ein neues Objekt der Klasse Messung hinzugefügt, das den aktuellen Zeitstempel und die übergebene Kfz-Klasse enthält.

List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Die Anfrage liefert eine Liste aus Objekten der Klasse OrtsDaten zurück, deren Ortskürzel aus der durch pRegion näher bestimmten Region stammen. Jedes Element des Felds (Arrays) gibt ein anderes Ortskürzel der Region an.

int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2)

Diese Methode analysiert die Zählungsdaten innerhalb des angegebenen Zeitraums.

Die Klasse OrtsDaten

Ein Objekt dieser Klasse verwaltet alle Messdaten zu einem bestimmten Ortskürzel.

OrtsDaten(String pOrtsKuerzel)

Ein Objekt der Klasse wird initialisiert. Dabei wird das Ortskürzel durch den Parameter pOrtsKuerzel im Klartext übergeben. Die durch dieses Objekt verwaltete Liste der Messungen ist nachher leer.

String gibOrtsKuerzel()

Das Ortskürzel wird zurückgegeben.

int gibAnzahlMessungen()

Die Anzahl der bisher aufgezeichneten Messungen wird zurückgegeben.

List<Messung> gibMessungen()

Die Liste aller Messungen, die zum zugehörigen Ortskürzel gespeichert sind, wird zurückgegeben. Liegen keine Messungen vor, wird eine leere Liste zurückgegeben.

void erfasseMessung(Messung pMessung)

Das als pMessung übergebene Objekt wird an die Liste der Messungen, die durch dieses Objekt verwaltet werden, angehängt.

boolean isLess(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch vor demjenigen des Objekts pOrt liegt, sonst false.

boolean isEqual(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das Ortskürzel des Objekts pOrt demjenigen Ortskürzel gleich ist, das durch dieses Objekt verwaltet wird, sonst false.

boolean isGreater(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch hinter demjenigen des Objekts pOrt liegt, sonst false.

Die Klasse Messung

Ein Objekt dieser Klasse verwaltet die individuellen Messdaten einer bestimmten Messung zu einem bestimmten Ortskennzeichen.

Messung(char pKfzKlasse)

Ein Objekt dieser Klasse wird erzeugt, das als Kfz-Klasse den durch pKfzKlasse übergebenen Wert und einen Zeitstempel mit dem aktuellen Zeitpunkt enthält. Für pKfzKlasse sind die Werte P für PKW und S für sonstige Kraftfahrzeuge erlaubt.

Zeitstempel gibZeitstempel()

Der Zeitstempel dieser Messung wird zurückgegeben.

char gibKfzKlasse()

Das Kürzel der Kraftfahrzeugklasse zu dieser Messung wird zurückgegeben.

Die Klasse Zeitstempel

Ein Objekt dieser Klasse verwaltet einen sekundengenauen Zeitpunkt.

Zeitstempel()

Ein Zeitstempel mit aktuellem Datum und sekundengenauer Uhrzeit wird erzeugt.

Zeitstempel(int pJahr, int pMonat, int pTag, int pStunde, int pMinute, int pSekunde)

Ein Zeitstempel mit dem durch die Parameter bestimmten Datum und sekundengenauer Uhrzeit wird erzeugt.

boolean liegtInnerhalb(Zeitstempel pVon, Zeitstempel pBis)

Wenn dieser Zeitstempel innerhalb des durch die beiden Zeitstempel pVon und pBis angegebenen Zeitraums liegt, wird true zurückgegeben, sonst false.

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.

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

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

Erläutern Sie, weshalb für die Verwaltung der Ortsdaten ein binärer Suchbaum gegenüber einer linearen Liste besonders geeignet ist.

Erläutern Sie, weshalb es sinnvoll ist, die Daten im Suchbaum nach Ortskürzeln statt nach Zeitstempeln zu ordnen.

Sachkontext: Automatisierte Verkehrszählung

Damit sich das Verkehrsaufkommen auf Fernstraßen besser beurteilen lässt, finden regelmäßig Verkehrszählungen statt. Im Zuge der Digitalisierung soll dieser Vorgang nun automatisch ablaufen. Eine Kamera und eine passende Bilderkennungssoftware sollen dazu die Ortskürzel (auch Ortskennzeichen genannt) der vorbeifahrenden Kraftfahrzeuge (Kfz) selbstständig identifizieren und zählen. Die Daten werden in einem binären Suchbaum gespeichert, dessen Ordnung sich aus der alphabetischen Reihenfolge der Ortskürzel ergibt.

Die Zählsoftware soll um weitere Merkmale erweitert werden: Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Bei der Fahrzeugklasse soll unterschieden werden zwischen dem typischen Personenverkehr in PKW einerseits und allen sonstigen, insbesondere größeren Kraftfahrzeugen andererseits (z. B. Bussen, Traktoren und Lastkraftwagen).

Grundlage der Software ist das Implementationsdiagramm, von dem Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der benutzten Klassen steht im Anhang.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Zaehlung

Ein Objekt dieser Klasse führt die Verkehrszählung automatisiert durch, d. h., es dient zur Erfassung, Verwaltung und Auswertung aller Zählungsdaten.

Zaehlung()

Ein Objekt der Klasse wird initialisiert. Alle notwendigen Rahmenbedingungen zur Durchführung der Zählung sind nach Ausführung des Konstruktors erledigt (z. B. Initialisierung der Datenstrukturen).

void erfasseKfz(String pOrtsKuerzel, char pKfzKlasse)

Wenn ein vorbeifahrendes Kraftfahrzeug erkannt wurde, wird diese Methode aufgerufen. Ihr wird das Ortskürzel des Kraftfahrzeugs als Parameter pOrtsKuerzel übergeben. Der Parameter pKfzKlasse beinhaltet ein Kürzel für die Fahrzeugklasse (vorgesehen sind P für PKW oder S für sonstige Kraftfahrzeuge).

Ist zum übergebenen Ortskürzel bereits ein Knoten im binären Suchbaum verkehrszaehlung enthalten, wird er ermittelt, andernfalls wird ein neuer Knoten mit einem neuen Inhaltsobjekt aus der Klasse OrtsDaten erzeugt und dem Baum hinzugefügt. Der Liste aus Messungen, die durch das Inhaltsobjekt des Knotens verwaltet werden, wird ein neues Objekt der Klasse Messung hinzugefügt, das den aktuellen Zeitstempel und die übergebene Kfz-Klasse enthält.

List<OrtsDaten> ermittleRegionDaten(String[] pRegion)

Die Anfrage liefert eine Liste aus Objekten der Klasse OrtsDaten zurück, deren Ortskürzel aus der durch pRegion näher bestimmten Region stammen. Jedes Element des Felds (Arrays) gibt ein anderes Ortskürzel der Region an.

int ermittleEtwas(Zeitstempel pZ1, Zeitstempel pZ2)

Diese Methode analysiert die Zählungsdaten innerhalb des angegebenen Zeitraums.

Die Klasse OrtsDaten

Ein Objekt dieser Klasse verwaltet alle Messdaten zu einem bestimmten Ortskürzel.

OrtsDaten(String pOrtsKuerzel)

Ein Objekt der Klasse wird initialisiert. Dabei wird das Ortskürzel durch den Parameter pOrtsKuerzel im Klartext übergeben. Die durch dieses Objekt verwaltete Liste der Messungen ist nachher leer.

String gibOrtsKuerzel()

Das Ortskürzel wird zurückgegeben.

int gibAnzahlMessungen()

Die Anzahl der bisher aufgezeichneten Messungen wird zurückgegeben.

List<Messung> gibMessungen()

Die Liste aller Messungen, die zum zugehörigen Ortskürzel gespeichert sind, wird zurückgegeben. Liegen keine Messungen vor, wird eine leere Liste zurückgegeben.

void erfasseMessung(Messung pMessung)

Das als pMessung übergebene Objekt wird an die Liste der Messungen, die durch dieses Objekt verwaltet werden, angehängt.

boolean isLess(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch vor demjenigen des Objekts pOrt liegt, sonst false.

boolean isEqual(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das Ortskürzel des Objekts pOrt demjenigen Ortskürzel gleich ist, das durch dieses Objekt verwaltet wird, sonst false.

boolean isGreater(OrtsDaten pOrt)

Die Anfrage liefert true zurück, wenn das von diesem Objekt verwaltete Ortskürzel alphabetisch hinter demjenigen des Objekts pOrt liegt, sonst false.

Die Klasse Messung

Ein Objekt dieser Klasse verwaltet die individuellen Messdaten einer bestimmten Messung zu einem bestimmten Ortskennzeichen.

Messung(char pKfzKlasse)

Ein Objekt dieser Klasse wird erzeugt, das als Kfz-Klasse den durch pKfzKlasse übergebenen Wert und einen Zeitstempel mit dem aktuellen Zeitpunkt enthält. Für pKfzKlasse sind die Werte P für PKW und S für sonstige Kraftfahrzeuge erlaubt.

Zeitstempel gibZeitstempel()

Der Zeitstempel dieser Messung wird zurückgegeben.

char gibKfzKlasse()

Das Kürzel der Kraftfahrzeugklasse zu dieser Messung wird zurückgegeben.

Die Klasse Zeitstempel

Ein Objekt dieser Klasse verwaltet einen sekundengenauen Zeitpunkt.

Zeitstempel()

Ein Zeitstempel mit aktuellem Datum und sekundengenauer Uhrzeit wird erzeugt.

Zeitstempel(int pJahr, int pMonat, int pTag, int pStunde, int pMinute, int pSekunde)

Ein Zeitstempel mit dem durch die Parameter bestimmten Datum und sekundengenauer Uhrzeit wird erzeugt.

boolean liegtInnerhalb(Zeitstempel pVon, Zeitstempel pBis)

Wenn dieser Zeitstempel innerhalb des durch die beiden Zeitstempel pVon und pBis angegebenen Zeitraums liegt, wird true zurückgegeben, sonst false.

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.

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

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

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

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

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

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

e)

Eine Stadt will ermitteln, welche Fahrzeuge von Berufspendlern genutzt werden. Die Softwarefirma empfiehlt, bei jeder Zählung neben Ortskürzeln, Kfz-Klassen und Zeitpunkten zusätzlich die vollständigen Kfz-Kennzeichen abzuspeichern. Weil angenommen wird, dass alle Pendler mit dem PKW anreisen, sollen die Daten nach der Erfassung über das Attribut kfzKlasse der Klasse Messung gefiltert werden. Anschließend sollen anhand der Kennzeichen jene Fahrzeuge bestimmt werden, die regelmäßig zu ähnlichen Tageszeiten an derselben Zählstelle vorbeifahren.

Beurteilen Sie den Vorschlag im Hinblick auf die erforderlichen Anpassungen der Datenstrukturen sowie im Sachkontext im Hinblick auf die Grundprinzipien des Datenschutzes. (6 Punkte)

Das Unternehmen GoBigOrGoHome24 will die Gesundheit seiner Beschäftigten fördern, indem es sie zur regelmäßigen Teilnahme an Sportangeboten motiviert.

Die Beschäftigten sollen sich aus einer breiten Auswahl an Angeboten zu unterschiedlichen Sportarten Angebote aussuchen und dafür anmelden. Ein Angebot umfasst eine zuvor festgelegte Zahl an Einheiten, die zu besuchen sind. Das Unternehmen trägt die Kosten eines Angebots komplett, sofern die Person an sämtlichen Sporteinheiten teilnimmt. Fehlt sie unentschuldigt, verringert sich der Zuschuss der Firma. Die Länge einer Sporteinheit wird in Minuten angegeben.

Um die Daten zu verwalten, plant die Firma den Aufbau einer relationalen Datenbank, der die folgende Teilmodellierung zugrunde liegt:

Die weiteren Aufgaben beziehen sich auf das Datenbankschema in Abbildung 2, das nur einen Teil der Gesamtdatenbank abbildet. Im Anhang finden sich Beispieldaten dazu.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Teilnehmer ID · Vorname · Nachname

1 · Ada · Lovelace

2 · John · von Neumann

3 · Alan · Turing

4 · Konrad · Zuse

5 · Tim · Berners-Lee

Sportangebot ID · Sportart · Trainername

42 · Zumba · Joseph Weizenbaum

101 · Fitness · Gottfried Wilhelm Leibniz

2020 · Fitness · Gottfried Wilhelm Leibniz

2021 · Yoga · Joseph Weizenbaum

Sporteinheit ID · Datum · Thema · Dauer · SportangebotID

1 · 2020-08-13 · Ausdauer Laufband · 90 · 101

2 · 2020-08-13 · Grundschritte · 45 · 42

3 · 2020-08-14 · Tanzausdauer · 45 · 42

4 · 2020-08-17 · Zirkeltraining · 90 · 101

5 · 2020-08-20 · Ausdauer Fahrrad · 90 · 101

6 · 2020-08-20 · Spezialschritte · 45 · 42

7 · 2020-08-21 · Intervalltanzen · 45 · 42

8 · 2020-08-24 · Kräftigung des Rumpfes · 90 · 101

9 · 2020-08-27 · Eigene Tanzchoreographie · 45 · 42

angemeldet TeilnehmerID · SportangebotID

1 · 42

1 · 101

1 · 2020

2 · 42

3 · 42

3 · 101

4 · 101

5 · 101

fehlt TeilnehmerID · SporteinheitID · istEntschuldigt

1 · 1 · ja

1 · 2 · ja

3 · 9 · ja

4 · 8 · nein

5 · 4 · ja

5 · 5 · nein

a)

Erläutern Sie die Beziehungstypen des Entity-Relationship-Diagramms in Abbildung 1 bezogen auf den vorliegenden Sachkontext.

Begründen Sie, weshalb im Entity-Relationship-Modell in Abbildung 1 die jeweiligen Kardinalitäten gewählt wurden.

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

[10 Punkte]

d)

Begründen Sie anhand von zwei Argumenten, weshalb das Datenbankschema in Abbildung 2 die dritte Normalform nicht erfüllt.

Wandeln Sie das Datenbankschema aus Abbildung 2 in ein neues Schema um, das die dritte Normalform erfüllt.

Hinweis: Alle Sporteinheiten eines Sportangebots haben dieselbe Dauer.

[9 Punkte]

e)

Nach der Evaluation des Gesundheitsförderungsprogramms der Firma sind folgende Änderungen nötig:

Teilnehmende müssen für jedes Angebot einen festgelegten Eigenanteil selbst zahlen. Gespeichert werden soll die Höhe dieses Eigenanteils sowie, ob und wann er bezahlt wurde.

Weil Mitarbeitende häufig nachfragen, wo ihr gebuchtes Angebot stattfindet, sollen auch die Sporträume erfasst werden. Es soll festgehalten werden, welches Sportangebot in welchem Raum stattfindet; ein Sportangebot findet stets im gleichen Raum statt. Zu jedem Raum sollen die eindeutige Raumbezeichnung und die Raumgröße gespeichert werden.

Modellieren Sie eine Erweiterung des Entity-Relationship-Diagramms aus Abbildung 1, sodass der neue Datenbankentwurf die beschriebenen Aspekte zusätzlich abbildet.

Hinweis: Für die Erweiterung unwichtige Entitäts- und Beziehungstypen brauchen nicht dargestellt zu werden.

Erläutern Sie, auf welche Weise Ihr entwickeltes Modell die Anforderungen realisiert, und begründen Sie die von Ihnen gewählten Kardinalitäten.

[12 Punkte]

Das Unternehmen GoBigOrGoHome24 will die Gesundheit seiner Beschäftigten fördern, indem es sie zur regelmäßigen Teilnahme an Sportangeboten motiviert.

Die Beschäftigten sollen sich aus einer breiten Auswahl an Angeboten zu unterschiedlichen Sportarten Angebote aussuchen und dafür anmelden. Ein Angebot umfasst eine zuvor festgelegte Zahl an Einheiten, die zu besuchen sind. Das Unternehmen trägt die Kosten eines Angebots komplett, sofern die Person an sämtlichen Sporteinheiten teilnimmt. Fehlt sie unentschuldigt, verringert sich der Zuschuss der Firma. Die Länge einer Sporteinheit wird in Minuten angegeben.

Um die Daten zu verwalten, plant die Firma den Aufbau einer relationalen Datenbank, der die folgende Teilmodellierung zugrunde liegt:

Die weiteren Aufgaben beziehen sich auf das Datenbankschema in Abbildung 2, das nur einen Teil der Gesamtdatenbank abbildet. Im Anhang finden sich Beispieldaten dazu.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Teilnehmer ID · Vorname · Nachname

1 · Ada · Lovelace

2 · John · von Neumann

3 · Alan · Turing

4 · Konrad · Zuse

5 · Tim · Berners-Lee

Sportangebot ID · Sportart · Trainername

42 · Zumba · Joseph Weizenbaum

101 · Fitness · Gottfried Wilhelm Leibniz

2020 · Fitness · Gottfried Wilhelm Leibniz

2021 · Yoga · Joseph Weizenbaum

Sporteinheit ID · Datum · Thema · Dauer · SportangebotID

1 · 2020-08-13 · Ausdauer Laufband · 90 · 101

2 · 2020-08-13 · Grundschritte · 45 · 42

3 · 2020-08-14 · Tanzausdauer · 45 · 42

4 · 2020-08-17 · Zirkeltraining · 90 · 101

5 · 2020-08-20 · Ausdauer Fahrrad · 90 · 101

6 · 2020-08-20 · Spezialschritte · 45 · 42

7 · 2020-08-21 · Intervalltanzen · 45 · 42

8 · 2020-08-24 · Kräftigung des Rumpfes · 90 · 101

9 · 2020-08-27 · Eigene Tanzchoreographie · 45 · 42

angemeldet TeilnehmerID · SportangebotID

1 · 42

1 · 101

1 · 2020

2 · 42

3 · 42

3 · 101

4 · 101

5 · 101

fehlt TeilnehmerID · SporteinheitID · istEntschuldigt

1 · 1 · ja

1 · 2 · ja

3 · 9 · ja

4 · 8 · nein

5 · 4 · ja

5 · 5 · nein

b)

Aus der Datenbank sollen die nachstehenden Informationen abgerufen werden: Entwerfen Sie zu jeder der folgenden Anfragen eine passende SQL-Anweisung. [11 Punkte]

c)

Gegeben ist die folgende SQL-Anweisung:

1 SELECT Sportart, Trainername

2 FROM Sportangebot

3 WHERE Sportangebot.ID NOT IN (

4 SELECT Sportangebot.ID

5 FROM Teilnehmer

6 INNER JOIN angemeldet

7 ON Teilnehmer.ID = angemeldet.TeilnehmerID

8 INNER JOIN Sportangebot

9 ON angemeldet.SportangebotID = Sportangebot.ID

10 WHERE Teilnehmer.ID = 2

11)

12 ORDER BY Sportangebot.Sportart ASC

Aufgabenstellung

Die Künstlerin Mosa Iks strebt Ruhm mit Kunstwerken an, die sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammensetzen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b in der gleichen Abfolge stehen wie die zugehörigen Farbsteine in der Zeile. Bereits besonders erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

Anhang

Dokumentation ausgewählter Methoden der Klasse String

char charAt(int index) Die Anfrage gibt das Zeichen am angegebenen Index zurück. Der Index hat einen Wertebereich von 0 bis length() - 1. Das erste Zeichen dieser Zeichenkette ist an Index 0, das nächste an Index 1 und so weiter, wie bei Array-Indizes.

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 das übergebene Objekt anObject nicht null ist und wenn es 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 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 des 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 Zeichen an Position endIndex - 1. 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)

Kennzeichnend für das Werk „GESTERN“ ist, dass in jeder Zeile eines Mosaiks ausschließlich rote und gelbe Steine liegen, blaue dagegen nicht. Jede Zeile umfasst mindestens zwei Steine; dabei hat der letzte Stein (der ganz rechts liegende) eine Farbe, die weiter links in derselben Zeile schon mindestens einmal vorkommt. Im Folgenden wird jede Zeile für sich betrachtet.

Entscheiden Sie, ob es sich bei den Wörtern grg, gbggg und rrg um Wörter handelt, die zulässige Zeilen des Werkes „GESTERN“ darstellen.

Entwickeln Sie das Zustandsübergangsdiagramm eines deterministischen endlichen Automaten, der genau diejenigen Wörter akzeptiert, die zulässige Mosaiksteinzeilen im Werk „GESTERN“ darstellen.

[9 Punkte]

b)

Mosa arbeitet gerade am Mosaik „HEUTE“. Die Wortdarstellungen der Steinzeilen dieses Mosaiks erkennt der folgende deterministische endliche Automat A:

Geben Sie für den Automaten A die Zustandsmenge, die Menge der Endzustände sowie den Startzustand an.

Ermitteln Sie zum Zustandsübergangsdiagramm aus Abbildung 2 ein Wort der Länge 8, das der Automat A akzeptiert, und ein Wort der Länge 8, das der Automat A nicht akzeptiert.

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

[8 Punkte]

Aufgabenstellung

Die Künstlerin Mosa Iks strebt Ruhm mit Kunstwerken an, die sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammensetzen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b in der gleichen Abfolge stehen wie die zugehörigen Farbsteine in der Zeile. Bereits besonders erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

Anhang

Dokumentation ausgewählter Methoden der Klasse String

char charAt(int index) Die Anfrage gibt das Zeichen am angegebenen Index zurück. Der Index hat einen Wertebereich von 0 bis length() - 1. Das erste Zeichen dieser Zeichenkette ist an Index 0, das nächste an Index 1 und so weiter, wie bei Array-Indizes.

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 das übergebene Objekt anObject nicht null ist und wenn es 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 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 des 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 Zeichen an Position endIndex - 1. 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.

Die Künstlerin plant, Abwandlungen des Kunstwerks „HEUTE“ zu schaffen. Mit einer regulären Grammatik will sie dazu beliebige Wörter der Sprache generieren, die jeweils Zeilen des Kunstwerks „HEUTE“ darstellen. Der zugehörige deterministische endliche Automat $A$ ist in Abbildung 2 angegeben:

c)

Entwerfen Sie eine reguläre Grammatik, die genau die vom Automaten $A$ akzeptierten Wörter erzeugt.

Vor einiger Zeit hat die Künstlerin ein Mosaik gestaltet, dessen Zeilen aus genau 4 oder 5 Steinen bestehen. Deshalb nannte sie es „VIERFÜNF“.

Die Wörter, welche diese Zeilen darstellen, entsprechen genau den Wörtern, die die folgende Grammatik $G_{45}$ erzeugt:

Startsymbol: S

Nichtterminale: N = {S, A, B}

Terminale: T = {r, g, b}

Produktionen: P = {

S -> rAr | gAg | bAb,

A -> rBr | gBg | bBb,

B -> r | g | b | ε

}

d) 1.

Erläutern Sie, aus welchem Grund jedes Wort, das die Grammatik $G_{45}$ erzeugt, genau 4 oder 5 Zeichen lang ist.

d) 2.

Ermitteln Sie für die folgenden Wörter jeweils die Ableitung und entscheiden Sie anhand dieser, ob die Wörter von der Grammatik $G_{45}$ erzeugt werden können: ggggg, rrbb.

d) 3.

Erläutern Sie, nach welchen allgemeinen Regeln die Zeilen der Mosaike aufgebaut sind, deren Wörter sich mit der Grammatik $G_{45}$ erzeugen lassen.

d) 4.

Begründen Sie, aus welchem Grund die Grammatik $G_{45}$ keine reguläre Grammatik darstellt.

d) 5.

Beurteilen Sie, ob eine reguläre Grammatik existiert, die genau die Wörter erzeugt, welche auch die Grammatik $G_{45}$ erzeugt.

Aufgabenstellung

Die Künstlerin Mosa Iks strebt Ruhm mit Kunstwerken an, die sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammensetzen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b in der gleichen Abfolge stehen wie die zugehörigen Farbsteine in der Zeile. Bereits besonders erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

Anhang

Dokumentation ausgewählter Methoden der Klasse String

char charAt(int index) Die Anfrage gibt das Zeichen am angegebenen Index zurück. Der Index hat einen Wertebereich von 0 bis length() - 1. Das erste Zeichen dieser Zeichenkette ist an Index 0, das nächste an Index 1 und so weiter, wie bei Array-Indizes.

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 das übergebene Objekt anObject nicht null ist und wenn es 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 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 des 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 Zeichen an Position endIndex - 1. 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.

Teilaufgabe e)

Die Künstlerin möchte automatisiert prüfen, ob eine Zeichenkette ein Wort ist, das einer Zeile ihres Werks „SPIEGEL“ entspricht. Jede Zeile dieses Kunstwerks zeichnet sich dadurch aus, dass die Farbfolge von links nach rechts und von rechts nach links gelesen gleich ist. Zudem sind wiederum ausschließlich die Farben rot (r), gelb (g) und blau (b) erlaubt.

Sie bittet einen befreundeten Informatiker, eine Methode zu schreiben, die für eine als Parameter übergebene Zeichenkette genau dann true liefert, wenn diese eine Zeile des Werks „SPIEGEL“ repräsentiert.

Die Methode istSpiegelwort in der Klasse Mosaik besitzt diesen Methodenkopf:

public boolean istSpiegelwort(String pWort)

1.

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

2.

Implementieren Sie die Methode istSpiegelwort.

Hinweis: Ein Auszug aus der Dokumentation der Klasse String steht im Anhang (bzw. Kontext) zur Verfügung.