Abitur NRW Informatik 2022 · GK · Nachtermin

Aufgabenstellung: Verpackungsstation

Auf einem Biobauernhof werden die geernteten Kartoffeln in einer hofeigenen Verpackungsstation abgepackt. Ein Förderband transportiert die Kartoffeln zu einer Sortieranlage, die jede Kartoffel danach über eine Rutsche zu einer passenden Packung leitet. Sobald eine Packung gefüllt ist, wird sie verladen und durch eine neue, leere Packung ersetzt. Abbildung 1 stellt die Verpackungsstation schematisch dar.

Die zentrale Schwierigkeit liegt darin, für jede als Nächstes auf dem Förderband ankommende Kartoffel eine passende Packung auszuwählen. Kartoffeln sind Naturprodukte und unterscheiden sich stark in ihrer Größe, sodass die Packungen nicht immer exakt gleich schwer sind.

Einerseits muss eine Packung ein festgelegtes Minimalgewicht erreichen, um als voll zu gelten. Andererseits soll dieses Minimalgewicht möglichst knapp überschritten werden, weil dem Bauernhof sonst unnötige Verluste entstehen.

Nachfolgend wird ein Programm betrachtet, das diese Verpackungsstation simuliert. Es setzt die in Abbildung 2 angegebene Teilmodellierung um.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Verpackungsstation

Ein Objekt dieser Klasse simuliert die Verpackung von Kartoffeln eines Biobauernhofes in einzelne Packungen sowie die Verladung dieser Packungen.

Konstruktor / Methode

Beschreibung

Verpackungsstation(int pAnzahlPackungen)

Ein Objekt der Klasse Verpackungsstation wird initialisiert. In dem vom Objekt verwalteten Versandlager sind keine fertig befüllten Packungen enthalten. Auf dem vom Objekt verwalteten Förderband sind keine Kartoffeln. Der Parameter pAnzahlPackungen gibt an, wie viele Packungen die Station gleichzeitig befüllen wird.

void ergaenzeKartoffeln(List<Kartoffel> pKartoffeln)

Das vom Objekt verwaltete Förderband wird mit den Kartoffel-Objekten der Liste pKartoffeln in beliebiger Reihenfolge gefüllt.

Packung verpackeKartoffel()

Die Methode wird in Aufgabenteil b) analysiert.

List<Packung> gibVersandlager()

Die Methode liefert die Liste der bereits gefüllten Packungen des Versandlagers zurück.

Die Klasse Kartoffel

Ein Objekt dieser Klasse repräsentiert eine einzelne Kartoffel in der Simulation der Verpackungsstation.

Konstruktor / Methode

Beschreibung

Kartoffel(int pGewicht)

Eine neue Kartoffel wird mit dem Gewicht pGewicht initialisiert.

int gibGewicht()

Das Gewicht der Kartoffel wird zurückgegeben.

Die Klasse Packung

Ein Objekt dieser Klasse repräsentiert eine einzelne Kartoffelpackung des Biobauernhofes, welche mit Kartoffeln befüllt werden kann.

Konstruktor / Methode

Beschreibung

Packung()

Eine leere Kartoffelpackung wird erzeugt, d. h., die von dem Objekt verwaltete Datensammlung der Kartoffel-Objekte ist leer.

void verpacke(Kartoffel pKartoffel)

Die Kartoffel pKartoffel wird in die Packung eingefüllt/verpackt, d. h., das Objekt pKartoffel wird der Datensammlung der Kartoffel-Objekte hinzugefügt.

List<Kartoffel> gibKartoffeln()

Die Methode liefert die Liste aller bereits verpackten Kartoffeln dieser Packung.

int ermittleGewicht()

Die Methode ermittelt das Gesamtgewicht der bereits verpackten Kartoffeln dieser Packung.

int gibMinimalgewicht()

Die Methode liefert das Minimalgewicht dieser Packung. Dieses legt fest, ab welchem Minimalgewicht diese Packung für den Versand vorbereitet werden kann.

Die generische Klasse Queue<ContentType>

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

Konstruktor / Methode

Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

Erläutern Sie, in welchen Beziehungen die Klassen der Modellierung in Abbildung 2 zueinander stehen.

[4 Punkte]

a.2)

Begründen Sie, weshalb es zweckmäßig ist, dass Objekte vom Typ Packung die Objekte vom Typ Kartoffel in einer Liste verwalten.

[3 Punkte]

Teilaufgabe d)

Weil sich die Verpackungsstation bewährt hat, sollen die Algorithmen verbessert und zusätzlich neue Funktionen ergänzt werden. Hierfür ist die Modellierung in Abbildung 2 anzupassen.

Diese Anforderungen kommen hinzu:

i. Für jede Packung soll der Zeitpunkt gespeichert werden, wann sie fertig gepackt wurde. Dieser Zeitpunkt soll natürlich auch abrufbar sein.

ii. Neben normalen Packungen soll es nun auch noch sogenannte Premiumpackungen geben. Neben den normalen Funktionalitäten soll bei Premiumpackungen das Minimalgewicht individuell gesetzt werden können. Darüber hinaus soll das Durchschnittsgewicht der Kartoffeln abgefragt werden können.

d.1)

Modellieren Sie die oben genannten Anforderungen als Erweiterung der Modellierung aus Abbildung 2. Stellen Sie dabei ausschließlich die Änderungen und Ergänzungen als Implementationsdiagramm dar.

[6 Punkte]

d.2)

Erläutern Sie, auf welche Weise Ihr Implementationsdiagramm jede der genannten Anforderungen umsetzt.

[6 Punkte]

Teilaufgabe e)

e)

Bei der Erweiterung des Programms hat ein Programmierer einen Einfall. Die Anzahl der Kartoffeln auf dem Förderband ist zwar nicht konstant, aber auf Grund der Größe des realen Förderbandes zumindest nach oben begrenzt. Es gibt also eine maximale Anzahl an Kartoffeln, die auf dem Förderband liegen können. In so einem Fall, so meint er sich zu erinnern, wählt man eigentlich eine statische Datenstruktur, z. B. ein Feld (Array).

Begründen Sie, weshalb das Förderband trotz des Einwands des Programmierers besser mit einer Schlange als mit einem Feld (Array) umgesetzt werden sollte.

[6 Punkte]

Aufgabenstellung: Verpackungsstation

Auf einem Biobauernhof werden die geernteten Kartoffeln in einer hofeigenen Verpackungsstation abgepackt. Ein Förderband transportiert die Kartoffeln zu einer Sortieranlage, die jede Kartoffel danach über eine Rutsche zu einer passenden Packung leitet. Sobald eine Packung gefüllt ist, wird sie verladen und durch eine neue, leere Packung ersetzt. Abbildung 1 stellt die Verpackungsstation schematisch dar.

Die zentrale Schwierigkeit liegt darin, für jede als Nächstes auf dem Förderband ankommende Kartoffel eine passende Packung auszuwählen. Kartoffeln sind Naturprodukte und unterscheiden sich stark in ihrer Größe, sodass die Packungen nicht immer exakt gleich schwer sind.

Einerseits muss eine Packung ein festgelegtes Minimalgewicht erreichen, um als voll zu gelten. Andererseits soll dieses Minimalgewicht möglichst knapp überschritten werden, weil dem Bauernhof sonst unnötige Verluste entstehen.

Nachfolgend wird ein Programm betrachtet, das diese Verpackungsstation simuliert. Es setzt die in Abbildung 2 angegebene Teilmodellierung um.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Verpackungsstation

Ein Objekt dieser Klasse simuliert die Verpackung von Kartoffeln eines Biobauernhofes in einzelne Packungen sowie die Verladung dieser Packungen.

Konstruktor / Methode

Beschreibung

Verpackungsstation(int pAnzahlPackungen)

Ein Objekt der Klasse Verpackungsstation wird initialisiert. In dem vom Objekt verwalteten Versandlager sind keine fertig befüllten Packungen enthalten. Auf dem vom Objekt verwalteten Förderband sind keine Kartoffeln. Der Parameter pAnzahlPackungen gibt an, wie viele Packungen die Station gleichzeitig befüllen wird.

void ergaenzeKartoffeln(List<Kartoffel> pKartoffeln)

Das vom Objekt verwaltete Förderband wird mit den Kartoffel-Objekten der Liste pKartoffeln in beliebiger Reihenfolge gefüllt.

Packung verpackeKartoffel()

Die Methode wird in Aufgabenteil b) analysiert.

List<Packung> gibVersandlager()

Die Methode liefert die Liste der bereits gefüllten Packungen des Versandlagers zurück.

Die Klasse Kartoffel

Ein Objekt dieser Klasse repräsentiert eine einzelne Kartoffel in der Simulation der Verpackungsstation.

Konstruktor / Methode

Beschreibung

Kartoffel(int pGewicht)

Eine neue Kartoffel wird mit dem Gewicht pGewicht initialisiert.

int gibGewicht()

Das Gewicht der Kartoffel wird zurückgegeben.

Die Klasse Packung

Ein Objekt dieser Klasse repräsentiert eine einzelne Kartoffelpackung des Biobauernhofes, welche mit Kartoffeln befüllt werden kann.

Konstruktor / Methode

Beschreibung

Packung()

Eine leere Kartoffelpackung wird erzeugt, d. h., die von dem Objekt verwaltete Datensammlung der Kartoffel-Objekte ist leer.

void verpacke(Kartoffel pKartoffel)

Die Kartoffel pKartoffel wird in die Packung eingefüllt/verpackt, d. h., das Objekt pKartoffel wird der Datensammlung der Kartoffel-Objekte hinzugefügt.

List<Kartoffel> gibKartoffeln()

Die Methode liefert die Liste aller bereits verpackten Kartoffeln dieser Packung.

int ermittleGewicht()

Die Methode ermittelt das Gesamtgewicht der bereits verpackten Kartoffeln dieser Packung.

int gibMinimalgewicht()

Die Methode liefert das Minimalgewicht dieser Packung. Dieses legt fest, ab welchem Minimalgewicht diese Packung für den Versand vorbereitet werden kann.

Die generische Klasse Queue<ContentType>

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

Konstruktor / Methode

Beschreibung

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

b)

Die Klasse Verpackungsstation bietet die Methode verpackeKartoffel an. Nachfolgend ist eine erste Fassung des Quellcodes abgebildet.

1 public void verpackeKartoffel() {

2 Kartoffel neu = foerderband.front();

3 foerderband.dequeue();

4

5 int m = 0;

6 for (int i = 0; i < packungen.length; i++) {

7 if (packungen[i].ermittleGewicht()

8 < packungen[m].ermittleGewicht()) {

9 m = i;

10 }

11 }

12

13 packungen[m].verpacke(neu);

14

15 if (packungen[m].ermittleGewicht()

16 >= packungen[m].gibMinimalgewicht()) {

17 versandlager.append(packungen[m]);

18 packungen[m] = new Packung();

19 }

20 }

Analysieren Sie den Quelltext der Methode und erläutern Sie, wie sie arbeitet.

Erläutern Sie bezogen auf den Sachkontext, welche Strategie die Methode beim Verpacken einer Kartoffel verfolgt.

Beurteilen Sie, ob diese erste Fassung der Methode die Kartoffeln im Sinne der Anforderungen des Bauernhofes optimal verpackt.

[6 + 3 + 4 Punkte]

c)

Vor der Auslieferung an den Großhändler soll festgestellt werden, wie viele Kartoffeln schon fertig verpackt sind.

Künftig soll dies die Methode ermittleKartoffelanzahl der Klasse Verpackungsstation leisten. Sie bestimmt die Anzahl der Kartoffeln in sämtlichen Packungen der Liste versandlager. Ihr Methodenkopf lautet:

public int ermittleKartoffelanzahl()

Entwerfen Sie eine algorithmische Strategie für die Methode ermittleKartoffelanzahl.

[6 Punkte]

Implementieren Sie die Methode ermittleKartoffelanzahl gemäß Ihrer Strategie.

[6 Punkte]

public int ermittleKartoffelanzahl()

Aufgabenstellung

Im Nationalpark Wildlife teilen sich mehrere Tierarten ein weitläufiges Freigelände. Die Parkleitung will untersuchen, wie die Tiere miteinander in Kontakt treten. Hierfür tragen die Tiere Halsbänder, die Begegnungen mit anderen Tieren technisch erfassen und verwalten können.

Jedes Halsband sendet in regelmäßigen Zeitabständen ein Signal mit einem eindeutigen individuellen Schlüssel aus fünf Zeichen. Empfängt ein Halsband das Signal eines anderen Halsbands, kommt eine sogenannte Begegnung zustande. Bei dieser werden der mit dem Signal übertragene Schlüssel, die Stärke des Signals (z. B. zur Ermittlung des Abstands der beiden Tiere) und der Zeitpunkt der Begegnung lokal auf dem empfangenden Halsband gespeichert.

Empfängt ein Halsband einen bestimmten Schlüssel zum ersten Mal, wird für diesen zusätzlich ein sogenannter Kontakt angelegt. Dieser verwaltet alle Begegnungen mit dem gleichen Schlüssel. Existiert ein Kontakt zu einem bestimmten Schlüssel, so gibt es bereits mindestens eine Begegnung mit dem Halsband, das diesen Schlüssel versendet.

Die Begegnungen eines Kontakts werden aufsteigend nach ihrem Zeitpunkt sortiert. Die Kontakte werden nach dem Schlüssel alphabetisch sortiert in einem Suchbaum verwaltet.

Zur Überprüfung der Funktionsfähigkeit werden die Halsbänder zunächst einen Tag lang in einem kleineren Gehege an einigen Erdmännchen des Parks getestet. Zum Zeitpunkt der Aktivierung sind auf den Halsbändern zunächst weder Kontakte noch Begegnungen gespeichert. Das Halsband eines Erdmännchens erfasst während des Tests Begegnungen in der in Abbildung 1 angegebenen Reihenfolge. Abbildung 2 zeigt den Suchbaum mit allen Kontakten (dargestellt über ihren Schlüssel und die Anzahl der zugehörigen Begegnungen), der sich bei der Verarbeitung der Begegnungen aus Abbildung 1 ergibt.

Nr.

Schlüssel

Signalstärke

Zeitpunkt

1 · ncgde · 132 · 2022-03-19 15:54

2 · grsmt · 154 · 2022-03-19 16:21

3 · grsmt · 46 · 2022-03-19 16:23

4 · bdsuw · 113 · 2022-03-19 16:27

5 · pwagb · 21 · 2022-03-19 16:33

6 · mkwda · 78 · 2022-03-19 16:34

7 · ncgde · 103 · 2022-03-19 16:35

8 · mkwda · 142 · 2022-03-19 16:39

9 · wrlyr · 69 · 2022-03-19 17:02

Abbildung 1: Begegnungen des Halsbands eines Erdmännchens

Abbildung 4 zeigt einen Ausschnitt aus dem Implementationsdiagramm des Softwaresystems der Halsbänder.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Halsband

Objekte der Klasse Halsband verwalten alle Begegnungen mit anderen Halsbändern in den hierzu angelegten Kontakten. Jedes Objekt dieser Klasse bzw. jedes Halsband entspricht jeweils genau einem Tier.

Ausschnitt aus der Dokumentation der Klasse Halsband

Halsband(String pSchluessel)

Ein Objekt der Klasse wird initialisiert. Zunächst sind weder Kontakte noch Begegnungen gespeichert, der Suchbaum ist leer. Das Halsband versendet in regelmäßigen Zeitabständen Signale mit dem individuellen Schlüssel pSchluessel.

void verarbeiteNeueBegegnung(Begegnung pBegegnung)

Die Methode fügt die Begegnung pBegegnung dem zugehörigen Kontakt hinzu. Falls kein entsprechender Kontakt existiert, wird dieser zunächst erstellt und dem Suchbaum hinzugefügt. Falls pBegegnung == null ist, geschieht nichts.

private List<Begegnung> liefereEtwas(BinarySearchTree<Kontakt> pBaum, int pZahl)

Diese Methode soll in Aufgabenteil c) analysiert werden.

Die Klasse Kontakt

Objekte der Klasse Kontakt verwalten alle Begegnungen, die mit dem gleichen Schlüssel gekennzeichnet sind. Die Begegnungen liegen nach dem Zeitpunkt aufsteigend sortiert vor, zu dem die zugehörigen Signale empfangen wurden. Die Klasse implementiert das Interface ComparableContent.

Ausschnitt aus der Dokumentation der Klasse Kontakt

Kontakt(String pSchluessel)

Ein neuer Kontakt zum erstmalig empfangenen Schlüssel pSchluessel wird initialisiert. Die Liste der Begegnungen ist anfangs leer.

String gibSchluessel()

Die Anfrage liefert den Schlüssel des Kontakts.

List<Begegnung> gibBegegnungen()

Die Anfrage liefert eine neue Liste aller Begegnungsobjekte des Kontakts. Diese sind aufsteigend nach dem Zeitpunkt, zu dem die zugehörigen Signale empfangen wurden, sortiert.

void fuegeBegegnungHinzu(Begegnung pBegegnung)

Die Begegnung pBegegnung wird der Liste der verwalteten Begegnungen unter Beachtung des Sortierkriteriums hinzugefügt.

boolean isGreater(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch größer als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

boolean isEqual(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel und der Schlüssel des Kontakts pKontakt lexikographisch gleich sind, sonst liefert sie den Wert false.

boolean isLess(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch kleiner als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

Die Klasse Begegnung

Objekte der Klasse Begegnung verwalten den von einem empfangenen Signal übertragenen Schlüssel, die Stärke des Signals und den Zeitpunkt des Empfangs. Der Zeitpunkt, zu dem das Signal empfangen wird, liegt als Zeichenkette in der Form JJJJ-MM-TT HH:MM vor (z. B. 2022-03-19 15:54).

Ausschnitt aus der Dokumentation der Klasse Begegnung

Begegnung(String pSchluessel, int pSignalstaerke, String pZeitpunkt)

Eine neue Begegnung mit dem Halsband, das den Schlüssel pSchluessel versendet, wird initialisiert. Das zugehörige Signal wird zum Zeitpunkt pZeitpunkt mit der Signalstärke pSignalstaerke empfangen.

String gibSchluessel()

Die Anfrage liefert den Schlüssel der Begegnung.

int gibSignalstaerke()

Die Anfrage liefert die Signalstärke der Begegnung.

String gibZeitpunkt()

Die Anfrage liefert den Zeitpunkt der Begegnung.

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 (hasAccess() == false). 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.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Dokumentation des Interfaces ComparableContent<ContentType>

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

Teilaufgabe a)

In Abbildung 3 sind die Begegnungen dargestellt, die das Halsband eines weiteren Erdmännchens am Testtag aufgezeichnet hat.

a.1)

Geben Sie an, welche Kontakte beim Verarbeiten der Begegnungen aus Abbildung 3 neu angelegt werden und in welcher Reihenfolge sie in den Suchbaum eingefügt werden.

a.2)

Stellen Sie den Suchbaum, der sich nach der Verarbeitung sämtlicher Begegnungen aus Abbildung 3 ergibt, samt aller darin enthaltenen Kontakte dar (mit Schlüssel und Anzahl der jeweils zugehörigen Begegnungen).

a.3)

Beschreiben Sie in allgemeiner Form, wie sich ein Element in einen Suchbaum einfügen lässt.

Teilaufgabe b)

Die Methode verarbeiteNeueBegegnung der Klasse Halsband ordnet eine neue Begegnung entsprechend der Dokumentation im Anhang einem schon vorhandenen oder neu anzulegenden Kontakt zu. Ihr Methodenkopf lautet:

public void verarbeiteNeueBegegnung(Begegnung pBegegnung) b.1)

Entwickeln und erläutern Sie eine algorithmische Vorgehensweise für die Methode verarbeiteNeueBegegnung.

b.2)

Implementieren Sie die Methode verarbeiteNeueBegegnung entsprechend Ihrer Strategie und der Dokumentation im Anhang.

Teilaufgabe c)

Die private Methode liefereEtwas der Klasse Halsband ist undokumentiert und entstand in einer frühen Entwicklungsphase der Halsbänder. Im Hinblick auf das nächste Update will der Park prüfen, ob die Methode sinnvoll zu neuen Funktionen beitragen kann oder endgültig gelöscht werden sollte.

1 private List<Begegnung> liefereEtwas(

2 BinarySearchTree<Kontakt> pBaum, int pZahl) {

3 List<Begegnung> ergebnis = new List<Begegnung>();

4 if (!pBaum.isEmpty()) {

5 ergebnis.concat(liefereEtwas(pBaum.getLeftTree(),

6 pZahl));

7

8 List<Begegnung> begegnungen

9 = pBaum.getContent().gibBegegnungen();

10 begegnungen.toFirst();

11 while (begegnungen.hasAccess()) {

12 Begegnung aktuell = begegnungen.getContent();

13 if (aktuell.gibSignalstaerke() > pZahl) {

14 ergebnis.append(aktuell);

15 }

16 begegnungen.next();

17 }

18

19 ergebnis.concat(liefereEtwas(pBaum.getRightTree(),

20 pZahl));

21 }

22 return ergebnis;

23 } Die Methode wird auf die Beispieldaten des Testtages aus den Abbildungen 1 und 2 angewendet. Als Argument für den Parameter pBaum wird der Suchbaum aus Abbildung 2 übergeben, für den Parameter pZahl der Wert 100.

c.1)

Analysieren Sie, wie die Methode liefereEtwas arbeitet, und stellen Sie den Inhalt der Liste dar, die bei Anwendung mit den oben genannten Parameterwerten zurückgegeben wird.

Tragen Sie die Begegnungen in der Reihenfolge ein, in der sie in der zurückgegebenen Liste stehen:

Schlüssel · Signalstärke · Zeitpunkt

c.2)

Erläutern Sie, wie die Methode liefereEtwas funktioniert.

c.3)

Erläutern Sie im Sachzusammenhang, welches Ergebnis die Methode liefereEtwas liefert.

Aufgabenstellung

Im Nationalpark Wildlife teilen sich mehrere Tierarten ein weitläufiges Freigelände. Die Parkleitung will untersuchen, wie die Tiere miteinander in Kontakt treten. Hierfür tragen die Tiere Halsbänder, die Begegnungen mit anderen Tieren technisch erfassen und verwalten können.

Jedes Halsband sendet in regelmäßigen Zeitabständen ein Signal mit einem eindeutigen individuellen Schlüssel aus fünf Zeichen. Empfängt ein Halsband das Signal eines anderen Halsbands, kommt eine sogenannte Begegnung zustande. Bei dieser werden der mit dem Signal übertragene Schlüssel, die Stärke des Signals (z. B. zur Ermittlung des Abstands der beiden Tiere) und der Zeitpunkt der Begegnung lokal auf dem empfangenden Halsband gespeichert.

Empfängt ein Halsband einen bestimmten Schlüssel zum ersten Mal, wird für diesen zusätzlich ein sogenannter Kontakt angelegt. Dieser verwaltet alle Begegnungen mit dem gleichen Schlüssel. Existiert ein Kontakt zu einem bestimmten Schlüssel, so gibt es bereits mindestens eine Begegnung mit dem Halsband, das diesen Schlüssel versendet.

Die Begegnungen eines Kontakts werden aufsteigend nach ihrem Zeitpunkt sortiert. Die Kontakte werden nach dem Schlüssel alphabetisch sortiert in einem Suchbaum verwaltet.

Zur Überprüfung der Funktionsfähigkeit werden die Halsbänder zunächst einen Tag lang in einem kleineren Gehege an einigen Erdmännchen des Parks getestet. Zum Zeitpunkt der Aktivierung sind auf den Halsbändern zunächst weder Kontakte noch Begegnungen gespeichert. Das Halsband eines Erdmännchens erfasst während des Tests Begegnungen in der in Abbildung 1 angegebenen Reihenfolge. Abbildung 2 zeigt den Suchbaum mit allen Kontakten (dargestellt über ihren Schlüssel und die Anzahl der zugehörigen Begegnungen), der sich bei der Verarbeitung der Begegnungen aus Abbildung 1 ergibt.

Nr.

Schlüssel

Signalstärke

Zeitpunkt

1 · ncgde · 132 · 2022-03-19 15:54

2 · grsmt · 154 · 2022-03-19 16:21

3 · grsmt · 46 · 2022-03-19 16:23

4 · bdsuw · 113 · 2022-03-19 16:27

5 · pwagb · 21 · 2022-03-19 16:33

6 · mkwda · 78 · 2022-03-19 16:34

7 · ncgde · 103 · 2022-03-19 16:35

8 · mkwda · 142 · 2022-03-19 16:39

9 · wrlyr · 69 · 2022-03-19 17:02

Abbildung 1: Begegnungen des Halsbands eines Erdmännchens

Abbildung 4 zeigt einen Ausschnitt aus dem Implementationsdiagramm des Softwaresystems der Halsbänder.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Halsband

Objekte der Klasse Halsband verwalten alle Begegnungen mit anderen Halsbändern in den hierzu angelegten Kontakten. Jedes Objekt dieser Klasse bzw. jedes Halsband entspricht jeweils genau einem Tier.

Ausschnitt aus der Dokumentation der Klasse Halsband

Halsband(String pSchluessel)

Ein Objekt der Klasse wird initialisiert. Zunächst sind weder Kontakte noch Begegnungen gespeichert, der Suchbaum ist leer. Das Halsband versendet in regelmäßigen Zeitabständen Signale mit dem individuellen Schlüssel pSchluessel.

void verarbeiteNeueBegegnung(Begegnung pBegegnung)

Die Methode fügt die Begegnung pBegegnung dem zugehörigen Kontakt hinzu. Falls kein entsprechender Kontakt existiert, wird dieser zunächst erstellt und dem Suchbaum hinzugefügt. Falls pBegegnung == null ist, geschieht nichts.

private List<Begegnung> liefereEtwas(BinarySearchTree<Kontakt> pBaum, int pZahl)

Diese Methode soll in Aufgabenteil c) analysiert werden.

Die Klasse Kontakt

Objekte der Klasse Kontakt verwalten alle Begegnungen, die mit dem gleichen Schlüssel gekennzeichnet sind. Die Begegnungen liegen nach dem Zeitpunkt aufsteigend sortiert vor, zu dem die zugehörigen Signale empfangen wurden. Die Klasse implementiert das Interface ComparableContent.

Ausschnitt aus der Dokumentation der Klasse Kontakt

Kontakt(String pSchluessel)

Ein neuer Kontakt zum erstmalig empfangenen Schlüssel pSchluessel wird initialisiert. Die Liste der Begegnungen ist anfangs leer.

String gibSchluessel()

Die Anfrage liefert den Schlüssel des Kontakts.

List<Begegnung> gibBegegnungen()

Die Anfrage liefert eine neue Liste aller Begegnungsobjekte des Kontakts. Diese sind aufsteigend nach dem Zeitpunkt, zu dem die zugehörigen Signale empfangen wurden, sortiert.

void fuegeBegegnungHinzu(Begegnung pBegegnung)

Die Begegnung pBegegnung wird der Liste der verwalteten Begegnungen unter Beachtung des Sortierkriteriums hinzugefügt.

boolean isGreater(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch größer als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

boolean isEqual(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel und der Schlüssel des Kontakts pKontakt lexikographisch gleich sind, sonst liefert sie den Wert false.

boolean isLess(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch kleiner als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

Die Klasse Begegnung

Objekte der Klasse Begegnung verwalten den von einem empfangenen Signal übertragenen Schlüssel, die Stärke des Signals und den Zeitpunkt des Empfangs. Der Zeitpunkt, zu dem das Signal empfangen wird, liegt als Zeichenkette in der Form JJJJ-MM-TT HH:MM vor (z. B. 2022-03-19 15:54).

Ausschnitt aus der Dokumentation der Klasse Begegnung

Begegnung(String pSchluessel, int pSignalstaerke, String pZeitpunkt)

Eine neue Begegnung mit dem Halsband, das den Schlüssel pSchluessel versendet, wird initialisiert. Das zugehörige Signal wird zum Zeitpunkt pZeitpunkt mit der Signalstärke pSignalstaerke empfangen.

String gibSchluessel()

Die Anfrage liefert den Schlüssel der Begegnung.

int gibSignalstaerke()

Die Anfrage liefert die Signalstärke der Begegnung.

String gibZeitpunkt()

Die Anfrage liefert den Zeitpunkt der Begegnung.

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 (hasAccess() == false). 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.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Dokumentation des Interfaces ComparableContent<ContentType>

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

Die Halsbänder, die im Park verwendet werden, besitzen außerdem eine GPS-Einheit, mit der sie jederzeit ihren genauen Standort ermitteln. Die momentane Position wird durch zwei Koordinaten angegeben. So liegt der Parkeingang etwa bei den Koordinaten 52.7478 und 9.6156.

Das Forschungsteam des Parks möchte das Verhalten der Tiere genauer untersuchen und für einzelne Tiere detaillierte Bewegungsprofile erstellen. Hierfür soll die vorhandene Software um die folgenden Punkte ergänzt werden:

1. Manche Tierarten, etwa Elefanten, bilden regelmäßig kleinere Herden, deren Zusammensetzung wechselt. Ob ein Tier zu einer Herde gehört, erkennt man unter anderem daran, dass es mit bestimmten Kontakten jeweils mindestens eine bestimmte Zahl an Begegnungen hat.

Deshalb soll ein Kontakt die Anzahl seiner Begegnungen selbst speichern und auf Nachfrage ausgeben können.

2. Ein Halsband ermittelt in festen Zeitabständen seinen Standort. Die GPS-Einheit liefert die aktuelle Position, die gemeinsam mit dem jeweiligen Zeitpunkt gespeichert wird. Jede Angabe zur Position sowie der Zeitpunkt eines Standorts sollen einzeln abrufbar sein.

Außerdem soll ein Halsband beliebig viele Standorte verwalten können.

3. Es soll möglich sein, alle Standorte auszugeben, die zwischen zwei vorgegebenen Zeitpunkten aufgezeichnet wurden.

d)

Modellieren Sie die oben genannten Anforderungen als Erweiterung der Modellierung aus Abbildung 4 und stellen Sie dabei nur die Veränderungen und Erweiterungen in Form eines Implementationsdiagramms dar. [6 Punkte]

Aufgabenstellung

Im Nationalpark Wildlife teilen sich mehrere Tierarten ein weitläufiges Freigelände. Die Parkleitung will untersuchen, wie die Tiere miteinander in Kontakt treten. Hierfür tragen die Tiere Halsbänder, die Begegnungen mit anderen Tieren technisch erfassen und verwalten können.

Jedes Halsband sendet in regelmäßigen Zeitabständen ein Signal mit einem eindeutigen individuellen Schlüssel aus fünf Zeichen. Empfängt ein Halsband das Signal eines anderen Halsbands, kommt eine sogenannte Begegnung zustande. Bei dieser werden der mit dem Signal übertragene Schlüssel, die Stärke des Signals (z. B. zur Ermittlung des Abstands der beiden Tiere) und der Zeitpunkt der Begegnung lokal auf dem empfangenden Halsband gespeichert.

Empfängt ein Halsband einen bestimmten Schlüssel zum ersten Mal, wird für diesen zusätzlich ein sogenannter Kontakt angelegt. Dieser verwaltet alle Begegnungen mit dem gleichen Schlüssel. Existiert ein Kontakt zu einem bestimmten Schlüssel, so gibt es bereits mindestens eine Begegnung mit dem Halsband, das diesen Schlüssel versendet.

Die Begegnungen eines Kontakts werden aufsteigend nach ihrem Zeitpunkt sortiert. Die Kontakte werden nach dem Schlüssel alphabetisch sortiert in einem Suchbaum verwaltet.

Zur Überprüfung der Funktionsfähigkeit werden die Halsbänder zunächst einen Tag lang in einem kleineren Gehege an einigen Erdmännchen des Parks getestet. Zum Zeitpunkt der Aktivierung sind auf den Halsbändern zunächst weder Kontakte noch Begegnungen gespeichert. Das Halsband eines Erdmännchens erfasst während des Tests Begegnungen in der in Abbildung 1 angegebenen Reihenfolge. Abbildung 2 zeigt den Suchbaum mit allen Kontakten (dargestellt über ihren Schlüssel und die Anzahl der zugehörigen Begegnungen), der sich bei der Verarbeitung der Begegnungen aus Abbildung 1 ergibt.

Nr.

Schlüssel

Signalstärke

Zeitpunkt

1 · ncgde · 132 · 2022-03-19 15:54

2 · grsmt · 154 · 2022-03-19 16:21

3 · grsmt · 46 · 2022-03-19 16:23

4 · bdsuw · 113 · 2022-03-19 16:27

5 · pwagb · 21 · 2022-03-19 16:33

6 · mkwda · 78 · 2022-03-19 16:34

7 · ncgde · 103 · 2022-03-19 16:35

8 · mkwda · 142 · 2022-03-19 16:39

9 · wrlyr · 69 · 2022-03-19 17:02

Abbildung 1: Begegnungen des Halsbands eines Erdmännchens

Abbildung 4 zeigt einen Ausschnitt aus dem Implementationsdiagramm des Softwaresystems der Halsbänder.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Halsband

Objekte der Klasse Halsband verwalten alle Begegnungen mit anderen Halsbändern in den hierzu angelegten Kontakten. Jedes Objekt dieser Klasse bzw. jedes Halsband entspricht jeweils genau einem Tier.

Ausschnitt aus der Dokumentation der Klasse Halsband

Halsband(String pSchluessel)

Ein Objekt der Klasse wird initialisiert. Zunächst sind weder Kontakte noch Begegnungen gespeichert, der Suchbaum ist leer. Das Halsband versendet in regelmäßigen Zeitabständen Signale mit dem individuellen Schlüssel pSchluessel.

void verarbeiteNeueBegegnung(Begegnung pBegegnung)

Die Methode fügt die Begegnung pBegegnung dem zugehörigen Kontakt hinzu. Falls kein entsprechender Kontakt existiert, wird dieser zunächst erstellt und dem Suchbaum hinzugefügt. Falls pBegegnung == null ist, geschieht nichts.

private List<Begegnung> liefereEtwas(BinarySearchTree<Kontakt> pBaum, int pZahl)

Diese Methode soll in Aufgabenteil c) analysiert werden.

Die Klasse Kontakt

Objekte der Klasse Kontakt verwalten alle Begegnungen, die mit dem gleichen Schlüssel gekennzeichnet sind. Die Begegnungen liegen nach dem Zeitpunkt aufsteigend sortiert vor, zu dem die zugehörigen Signale empfangen wurden. Die Klasse implementiert das Interface ComparableContent.

Ausschnitt aus der Dokumentation der Klasse Kontakt

Kontakt(String pSchluessel)

Ein neuer Kontakt zum erstmalig empfangenen Schlüssel pSchluessel wird initialisiert. Die Liste der Begegnungen ist anfangs leer.

String gibSchluessel()

Die Anfrage liefert den Schlüssel des Kontakts.

List<Begegnung> gibBegegnungen()

Die Anfrage liefert eine neue Liste aller Begegnungsobjekte des Kontakts. Diese sind aufsteigend nach dem Zeitpunkt, zu dem die zugehörigen Signale empfangen wurden, sortiert.

void fuegeBegegnungHinzu(Begegnung pBegegnung)

Die Begegnung pBegegnung wird der Liste der verwalteten Begegnungen unter Beachtung des Sortierkriteriums hinzugefügt.

boolean isGreater(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch größer als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

boolean isEqual(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel und der Schlüssel des Kontakts pKontakt lexikographisch gleich sind, sonst liefert sie den Wert false.

boolean isLess(Kontakt pKontakt)

Die Anfrage liefert den Wert true, wenn der eigene Schlüssel lexikographisch kleiner als der Schlüssel des Kontakts pKontakt ist, sonst liefert sie den Wert false.

Die Klasse Begegnung

Objekte der Klasse Begegnung verwalten den von einem empfangenen Signal übertragenen Schlüssel, die Stärke des Signals und den Zeitpunkt des Empfangs. Der Zeitpunkt, zu dem das Signal empfangen wird, liegt als Zeichenkette in der Form JJJJ-MM-TT HH:MM vor (z. B. 2022-03-19 15:54).

Ausschnitt aus der Dokumentation der Klasse Begegnung

Begegnung(String pSchluessel, int pSignalstaerke, String pZeitpunkt)

Eine neue Begegnung mit dem Halsband, das den Schlüssel pSchluessel versendet, wird initialisiert. Das zugehörige Signal wird zum Zeitpunkt pZeitpunkt mit der Signalstärke pSignalstaerke empfangen.

String gibSchluessel()

Die Anfrage liefert den Schlüssel der Begegnung.

int gibSignalstaerke()

Die Anfrage liefert die Signalstärke der Begegnung.

String gibZeitpunkt()

Die Anfrage liefert den Zeitpunkt der Begegnung.

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 (hasAccess() == false). 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.

Die Objekte der Klasse ContentType sind damit vollständig geordnet. Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binärbaumes. Alle Objekte im rechten Teilbaum sind größer als das Inhaltsobjekt des Binärbaumes. Diese Bedingung gilt auch in beiden Teilbäumen.

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

BinarySearchTree()

Der Konstruktor erzeugt einen leeren Suchbaum.

boolean isEmpty()

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

void insert(ContentType pContent)

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

ContentType search(ContentType pContent)

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

void remove(ContentType pContent)

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

ContentType getContent()

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

BinarySearchTree<ContentType> getLeftTree()

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

BinarySearchTree<ContentType> getRightTree()

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

Das generische Interface ComparableContent<ContentType>

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

Dokumentation des Interfaces ComparableContent<ContentType>

boolean isGreater(ContentType pComparableContent)

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

boolean isEqual(ContentType pComparableContent)

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

boolean isLess(ContentType pComparableContent)

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

e)

Jede Mitarbeiterin und jeder Mitarbeiter des Parks hat ein Diensthandy, das von der Parkleitung zentral betreut und mit Updates versehen wird. So sind sie bei der Arbeit auf dem großen Gelände stets erreichbar und können bei Bedarf Unterstützung rufen. Außerdem benachrichtigt die Parkleitung das Personal über das Smartphone, wenn es in Rufbereitschaft kurzfristig von zu Hause aus einspringen muss (z. B. wegen unerwarteter Krankmeldungen einzelner Kolleginnen oder Kollegen).

Zur Verbesserung der Sicherheit des Personals spielt die Parkleitung mit einem Update automatisch eine neue App auf die Smartphones auf. Sie bietet dieselben Funktionen wie die im Park verwendeten Halsbänder, einschließlich der drei oben genannten Erweiterungen. Die Parkleitung weiß dabei, welcher Schlüssel welcher Mitarbeiterin bzw. welchem Mitarbeiter zugeordnet ist.

Die App wird beim Hochfahren des Smartphones automatisch gestartet und läuft ständig im Hintergrund. Außerdem werden sämtliche erfassten Daten jeden Tag abgerufen und auf den zentralen Server des Parks übertragen.

Begründen Sie unter Heranziehung eines Grundprinzips des Datenschutzes, weshalb das Vorgehen der Parkleitung bedenklich ist.

[6 Punkte]

Aufgabenstellung: Datenbank der Schach-Liga

Die Schach-AG einer Schule plant, gemeinsam mit den Schach-AGs weiterer Schulen eine Schach-Liga zu gründen, in der dauerhaft Wettkämpfe stattfinden. Dabei treten die Schulen wiederholt in einzelnen Partien oder auch in ganzen Turnieren gegeneinander an. Die Schülerinnen und Schüler eines Informatikkurses sollen hierfür eine Datenbank entwickeln, die die folgenden Daten verwalten soll:

Für die teilnehmenden Schulen sollen der Name, eine eindeutige Nummer (die sogenannte Schulnummer) und die Adresse verwaltet werden. Damit die Lehrenden der verschiedenen Schulen untereinander Kontakt aufnehmen können, sollen außerdem folgende Daten von der Lehrerin oder dem Lehrer der Schach-AG gespeichert werden: der Name, das Geburtsdatum, die Telefonnummer und die E-Mail-Adresse.

Von den Spielerinnen und Spielern werden der Name und die zugehörige Schule verwaltet. Um feststellen zu können, welche Spielerinnen und Spieler im gleichen Jahr geboren sind, wird außerdem das Geburtsdatum gespeichert. Dadurch können die Spielerinnen und Spieler in Altersgruppen eingeteilt werden.

Bei einer Partie spielen zwei Spielerinnen bzw. Spieler gegeneinander. Beide können aus der gleichen Schule oder von verschiedenen Schulen stammen. Dabei werden der Zeitpunkt des Beginns der Partie und das Ergebnis gespeichert. Außerdem wird gespeichert, wer die Farbe Weiß und wer die Farbe Schwarz hat.

Der Informatikkurs hat für die Datenbank einen Entwurf erstellt, der aus dem folgenden Entity-Relationship-Diagramm besteht:

Aus dem Entity-Relationship-Diagramm entstand das folgende Datenbankschema (siehe Abbildung 2):

Für das Ergebnis einer Partie gilt folgende Speicherung: Bei einem Sieg von Weiß steht der Wert 1, bei einem Sieg von Schwarz der Wert -1. Endet die Partie unentschieden (ein sogenanntes Patt), wird der Wert 0 abgelegt.

Anlage: Beispieldaten der Datenbank

Tabelle: Lehrer

EMailAdresse · Name · Geburtsdatum · Telefonnummer

allen@info.nrw · Frances E. Allen · 1971-08-04 · 0123-4567

blanch@info.nrw · Gertrude Blanch · 1972-02-02 · 01233-5678

lovelace@info.nrw · Ada Lovelace · 1973-12-10 · 01232-68104

chen@info.nrw · Peter Chen · 1977-01-03 · 01131-5316161

bayer@info.nrw · Rudolf Bayer · 1977-03-03 · 01121-6695314

dahl@info.nrw · Ole-Johann Dahl · 1977-10-12 · 01911-718212

Tabelle: Schule

Schulnummer · Name · Adresse · LehrerEMailAdresse

123 · Gamma-Gesamtschule · Baumallee 13, 10007 Krähwinkel · bayer@info.nrw

170 · Huffman-Hauptschule · Holzweg 5, 10006 Jammertal · blanch@info.nrw

552 · Gödel-Gymnasium · An de Dyk 13, 1005 Nergenshuizen · dahl@info.nrw

662 · Knuth-Kolleg · Hintergasse 3, 10001 Vordertupfingen · chen@info.nrw

732 · Shannon-Schule · Heimweg 3, 10004 Posemuckel · allen@info.nrw

840 · Knuth-Kolleg · Vorderer Weg 1, 10000 Hintertupfingen · lovelace@info.nrw

Tabelle: Spieler

ID · Name · Geburtsdatum · gehoertZu

1 · Armin Gips · 2010-03-14 · 123

2 · Lee Coeur · 2011-02-26 · 123

3 · Heinz Ellmann · 2009-08-05 · 552

4 · Karl Ender · 2006-06-30 · 840

5 · Kai Mauer · 2008-05-23 · 732

6 · Klaus Uhr · 2011-04-27 · 840

7 · Nico Laus · 2009-12-15 · 123

8 · Lisa Bonn · 2009-11-13 · 662

9 · Johannes Brodt · 2007-02-01 · 170

Tabelle: Partie

Startzeitpunkt · spieltWeissID · spieltSchwarzID · Ergebnis

2022-04-07 12:00 · 1 · 2 · -1

2022-04-07 12:45 · 2 · 1 · -1

2022-04-07 13:30 · 1 · 2 · -1

2022-04-07 12:00 · 3 · 5 · 0

2022-04-08 08:10 · 3 · 7 · 1

2022-04-26 09:55 · 7 · 3 · 1

2022-04-27 11:40 · 9 · 6 · 1

2022-04-28 13:50 · 7 · 6 · -1

2022-04-29 08:10 · 3 · 2 · 1

Hinweis: Ist das Ergebnis 1, so hat Weiß gewonnen. Ist das Ergebnis -1, so hat Schwarz gewonnen. Ist das Ergebnis 0, so gab es ein Patt (ein Unentschieden).

Teilaufgabe a)

a.1

Beschreiben Sie den in Abbildung 1 gezeigten Ausschnitt der Datenbankmodellierung und erläutern Sie, auf welche Weise das entwickelte Entity-Relationship-Diagramm die geschilderten Anforderungen abbildet. [10 Punkte]

a.2

Ermitteln Sie, welche anderen Attribute sich aus den vorhandenen als Primärschlüssel für die Entitätstypen Spieler, Schule und Lehrer eignen würden. [2 Punkte]

Teilaufgabe d)

Die Datenbank soll zusätzlich zu den bisherigen Partien auch Turniere samt ihrer Partien abbilden.

An einem Turnier nehmen mehrere Schulen teil, von denen eine Schule als Sieger des Turniers ermittelt wird. Ein Turnier findet an einem bestimmten Termin statt und hat einen Namen.

Für einen Termin stellen die Schulen jeweils mehrere Spielerinnen und Spieler.

Eine Partie ist entweder Teil eines Turniers oder gehört zu keinem Turnier. Für Turnierpartien gelten die gleichen Anforderungen wie im bisherigen Modell. Vereinfachend dürfen weiterhin Spielerinnen und Spieler derselben Schule gegeneinander antreten.

d.1

Modellieren Sie eine Erweiterung des Entity-Relationship-Diagramms aus Abbildung 1, sodass der neue Entwurf auch die beschriebenen Gesichtspunkte abdeckt. [5 Punkte]

d.2

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

Aufgabenstellung: Datenbank der Schach-Liga

Die Schach-AG einer Schule plant, gemeinsam mit den Schach-AGs weiterer Schulen eine Schach-Liga zu gründen, in der dauerhaft Wettkämpfe stattfinden. Dabei treten die Schulen wiederholt in einzelnen Partien oder auch in ganzen Turnieren gegeneinander an. Die Schülerinnen und Schüler eines Informatikkurses sollen hierfür eine Datenbank entwickeln, die die folgenden Daten verwalten soll:

Für die teilnehmenden Schulen sollen der Name, eine eindeutige Nummer (die sogenannte Schulnummer) und die Adresse verwaltet werden. Damit die Lehrenden der verschiedenen Schulen untereinander Kontakt aufnehmen können, sollen außerdem folgende Daten von der Lehrerin oder dem Lehrer der Schach-AG gespeichert werden: der Name, das Geburtsdatum, die Telefonnummer und die E-Mail-Adresse.

Von den Spielerinnen und Spielern werden der Name und die zugehörige Schule verwaltet. Um feststellen zu können, welche Spielerinnen und Spieler im gleichen Jahr geboren sind, wird außerdem das Geburtsdatum gespeichert. Dadurch können die Spielerinnen und Spieler in Altersgruppen eingeteilt werden.

Bei einer Partie spielen zwei Spielerinnen bzw. Spieler gegeneinander. Beide können aus der gleichen Schule oder von verschiedenen Schulen stammen. Dabei werden der Zeitpunkt des Beginns der Partie und das Ergebnis gespeichert. Außerdem wird gespeichert, wer die Farbe Weiß und wer die Farbe Schwarz hat.

Der Informatikkurs hat für die Datenbank einen Entwurf erstellt, der aus dem folgenden Entity-Relationship-Diagramm besteht:

Aus dem Entity-Relationship-Diagramm entstand das folgende Datenbankschema (siehe Abbildung 2):

Für das Ergebnis einer Partie gilt folgende Speicherung: Bei einem Sieg von Weiß steht der Wert 1, bei einem Sieg von Schwarz der Wert -1. Endet die Partie unentschieden (ein sogenanntes Patt), wird der Wert 0 abgelegt.

Anlage: Beispieldaten der Datenbank

Tabelle: Lehrer

EMailAdresse · Name · Geburtsdatum · Telefonnummer

allen@info.nrw · Frances E. Allen · 1971-08-04 · 0123-4567

blanch@info.nrw · Gertrude Blanch · 1972-02-02 · 01233-5678

lovelace@info.nrw · Ada Lovelace · 1973-12-10 · 01232-68104

chen@info.nrw · Peter Chen · 1977-01-03 · 01131-5316161

bayer@info.nrw · Rudolf Bayer · 1977-03-03 · 01121-6695314

dahl@info.nrw · Ole-Johann Dahl · 1977-10-12 · 01911-718212

Tabelle: Schule

Schulnummer · Name · Adresse · LehrerEMailAdresse

123 · Gamma-Gesamtschule · Baumallee 13, 10007 Krähwinkel · bayer@info.nrw

170 · Huffman-Hauptschule · Holzweg 5, 10006 Jammertal · blanch@info.nrw

552 · Gödel-Gymnasium · An de Dyk 13, 1005 Nergenshuizen · dahl@info.nrw

662 · Knuth-Kolleg · Hintergasse 3, 10001 Vordertupfingen · chen@info.nrw

732 · Shannon-Schule · Heimweg 3, 10004 Posemuckel · allen@info.nrw

840 · Knuth-Kolleg · Vorderer Weg 1, 10000 Hintertupfingen · lovelace@info.nrw

Tabelle: Spieler

ID · Name · Geburtsdatum · gehoertZu

1 · Armin Gips · 2010-03-14 · 123

2 · Lee Coeur · 2011-02-26 · 123

3 · Heinz Ellmann · 2009-08-05 · 552

4 · Karl Ender · 2006-06-30 · 840

5 · Kai Mauer · 2008-05-23 · 732

6 · Klaus Uhr · 2011-04-27 · 840

7 · Nico Laus · 2009-12-15 · 123

8 · Lisa Bonn · 2009-11-13 · 662

9 · Johannes Brodt · 2007-02-01 · 170

Tabelle: Partie

Startzeitpunkt · spieltWeissID · spieltSchwarzID · Ergebnis

2022-04-07 12:00 · 1 · 2 · -1

2022-04-07 12:45 · 2 · 1 · -1

2022-04-07 13:30 · 1 · 2 · -1

2022-04-07 12:00 · 3 · 5 · 0

2022-04-08 08:10 · 3 · 7 · 1

2022-04-26 09:55 · 7 · 3 · 1

2022-04-27 11:40 · 9 · 6 · 1

2022-04-28 13:50 · 7 · 6 · -1

2022-04-29 08:10 · 3 · 2 · 1

Hinweis: Ist das Ergebnis 1, so hat Weiß gewonnen. Ist das Ergebnis -1, so hat Schwarz gewonnen. Ist das Ergebnis 0, so gab es ein Patt (ein Unentschieden).

Teilaufgabe b)

Aus der Datenbank sollen die folgenden Informationen abgefragt werden:

i.

Ermittelt werden sollen die Namen sämtlicher Spielerinnen und Spieler mit Geburtsjahr 2008 oder 2009.

ii.

Gesucht werden alle Partien, die Weiß verloren hat. Zu jeder dieser Partien sollen der Startzeitpunkt, der Name der Person, die Weiß spielt, sowie der Name von deren Schule ausgegeben werden.

iii.

Ausgegeben werden sollen die Schulnummer und der Name jeder Schule zusammen mit der Anzahl der Spielerinnen und Spieler, die für die jeweilige Schule antreten. Die Ausgabe soll nach dieser Anzahl absteigend geordnet sein.

Teilaufgabe c)

Gesucht sind alle Spielerinnen und Spieler, die bisher noch keine Partie gespielt haben. Zusätzlich sollen zu jeder Person ihre Schule sowie deren Kontaktdaten bestimmt werden. Dafür wird folgende Anfrage an das Datenbanksystem gerichtet:

1 SELECT Spieler.Name, Schule.Name

2 FROM Spieler

3 INNER JOIN Schule

4 ON Spieler.Schulnummer = Schule.Schulnummer

5 WHERE Spieler.ID NOT IN (

6 SELECT Partie.spieltWeissID

7 FROM Partie

8)

9 ORDER BY Schule.Name ASC

c.1

Analysieren Sie die Anfrage, indem Sie sie auf die Beispieldaten in der Anlage anwenden, das Resultat darstellen und die Anfrage erläutern.

c.2

Begründen Sie, warum die SQL-Anweisung die Vorgaben nicht erfüllt.

c.3

Erläutern Sie, auf welche Weise sich die Anfrage ergänzen lässt, damit sie die gewünschte Information liefert.

Aufgabenstellung: Datenbank der Schach-Liga

Die Schach-AG einer Schule plant, gemeinsam mit den Schach-AGs weiterer Schulen eine Schach-Liga zu gründen, in der dauerhaft Wettkämpfe stattfinden. Dabei treten die Schulen wiederholt in einzelnen Partien oder auch in ganzen Turnieren gegeneinander an. Die Schülerinnen und Schüler eines Informatikkurses sollen hierfür eine Datenbank entwickeln, die die folgenden Daten verwalten soll:

Für die teilnehmenden Schulen sollen der Name, eine eindeutige Nummer (die sogenannte Schulnummer) und die Adresse verwaltet werden. Damit die Lehrenden der verschiedenen Schulen untereinander Kontakt aufnehmen können, sollen außerdem folgende Daten von der Lehrerin oder dem Lehrer der Schach-AG gespeichert werden: der Name, das Geburtsdatum, die Telefonnummer und die E-Mail-Adresse.

Von den Spielerinnen und Spielern werden der Name und die zugehörige Schule verwaltet. Um feststellen zu können, welche Spielerinnen und Spieler im gleichen Jahr geboren sind, wird außerdem das Geburtsdatum gespeichert. Dadurch können die Spielerinnen und Spieler in Altersgruppen eingeteilt werden.

Bei einer Partie spielen zwei Spielerinnen bzw. Spieler gegeneinander. Beide können aus der gleichen Schule oder von verschiedenen Schulen stammen. Dabei werden der Zeitpunkt des Beginns der Partie und das Ergebnis gespeichert. Außerdem wird gespeichert, wer die Farbe Weiß und wer die Farbe Schwarz hat.

Der Informatikkurs hat für die Datenbank einen Entwurf erstellt, der aus dem folgenden Entity-Relationship-Diagramm besteht:

Aus dem Entity-Relationship-Diagramm entstand das folgende Datenbankschema (siehe Abbildung 2):

Für das Ergebnis einer Partie gilt folgende Speicherung: Bei einem Sieg von Weiß steht der Wert 1, bei einem Sieg von Schwarz der Wert -1. Endet die Partie unentschieden (ein sogenanntes Patt), wird der Wert 0 abgelegt.

Anlage: Beispieldaten der Datenbank

Tabelle: Lehrer

EMailAdresse · Name · Geburtsdatum · Telefonnummer

allen@info.nrw · Frances E. Allen · 1971-08-04 · 0123-4567

blanch@info.nrw · Gertrude Blanch · 1972-02-02 · 01233-5678

lovelace@info.nrw · Ada Lovelace · 1973-12-10 · 01232-68104

chen@info.nrw · Peter Chen · 1977-01-03 · 01131-5316161

bayer@info.nrw · Rudolf Bayer · 1977-03-03 · 01121-6695314

dahl@info.nrw · Ole-Johann Dahl · 1977-10-12 · 01911-718212

Tabelle: Schule

Schulnummer · Name · Adresse · LehrerEMailAdresse

123 · Gamma-Gesamtschule · Baumallee 13, 10007 Krähwinkel · bayer@info.nrw

170 · Huffman-Hauptschule · Holzweg 5, 10006 Jammertal · blanch@info.nrw

552 · Gödel-Gymnasium · An de Dyk 13, 1005 Nergenshuizen · dahl@info.nrw

662 · Knuth-Kolleg · Hintergasse 3, 10001 Vordertupfingen · chen@info.nrw

732 · Shannon-Schule · Heimweg 3, 10004 Posemuckel · allen@info.nrw

840 · Knuth-Kolleg · Vorderer Weg 1, 10000 Hintertupfingen · lovelace@info.nrw

Tabelle: Spieler

ID · Name · Geburtsdatum · gehoertZu

1 · Armin Gips · 2010-03-14 · 123

2 · Lee Coeur · 2011-02-26 · 123

3 · Heinz Ellmann · 2009-08-05 · 552

4 · Karl Ender · 2006-06-30 · 840

5 · Kai Mauer · 2008-05-23 · 732

6 · Klaus Uhr · 2011-04-27 · 840

7 · Nico Laus · 2009-12-15 · 123

8 · Lisa Bonn · 2009-11-13 · 662

9 · Johannes Brodt · 2007-02-01 · 170

Tabelle: Partie

Startzeitpunkt · spieltWeissID · spieltSchwarzID · Ergebnis

2022-04-07 12:00 · 1 · 2 · -1

2022-04-07 12:45 · 2 · 1 · -1

2022-04-07 13:30 · 1 · 2 · -1

2022-04-07 12:00 · 3 · 5 · 0

2022-04-08 08:10 · 3 · 7 · 1

2022-04-26 09:55 · 7 · 3 · 1

2022-04-27 11:40 · 9 · 6 · 1

2022-04-28 13:50 · 7 · 6 · -1

2022-04-29 08:10 · 3 · 2 · 1

Hinweis: Ist das Ergebnis 1, so hat Weiß gewonnen. Ist das Ergebnis -1, so hat Schwarz gewonnen. Ist das Ergebnis 0, so gab es ein Patt (ein Unentschieden).

Teilaufgabe e)

e.1

Entscheiden Sie, bei welchen Daten des gegebenen Datenbank-Modells (siehe Abbildungen 1 und 2) es sich um personenbezogene Daten handelt. [3 Punkte]

e.2

Beurteilen Sie unter Berücksichtigung des Datenschutzes, inwieweit die in der Datenbank abgelegten Daten erforderlich sind. [3 Punkte]

Aufgabenstellung: Erstlesewörter und Lesetexte

In der Grundschule lernen Kinder zu Beginn nur einfache Wörter („Erstlesewörter“) zu lesen. Ein Wort gilt als einfach, wenn seine Aussprache weitgehend der Schreibweise entspricht und es zudem nur aus wenigen Silben besteht. In der deutschen Sprachwissenschaft gibt es Regeln zum Aufbau einer Silbe; für diese Klausur werden sie folgendermaßen vereinfacht:

Eine Silbe enthält als Silbenkern einen Vokal (a, e, i, o oder u) oder eine Vokalkombination aus zwei Vokalen.

Vor und nach dem Silbenkern kann ein Konsonant oder können mehrere Konsonanten stehen. Mit Konsonanten sind in dieser Aufgabe alle Buchstaben des Alphabets außer den Vokalen gemeint, nämlich die folgenden:

b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z

Abbildung 1: Regeln für den Aufbau einer Silbe

Der Einfachheit halber sind alle Wörter ausschließlich in Kleinbuchstaben notiert.

Wie schwer ein Text zu lesen ist, hängt neben der Silbenanzahl auch von der Buchstabenanzahl je Wort ab: Das Wort „Schifffahrt“ mit 11 Buchstaben ist schwerer zu lesen als das Wort „Nase“ mit 4 Buchstaben.

Lesetexte sollen mithilfe einer Software untersucht werden, die feststellt, ob deren Wörter für Erstleserinnen und Erstleser geeignet sind. Die Software entfernt vor der Prüfung zunächst alle Satzzeichen.

Dabei wird folgende Modellierung zugrunde gelegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lesetext

Objekte der Klasse Lesetext modellieren Lesetexte, die auf ihre Eignung als Erstlesetext untersucht werden können.

Auszug aus der Dokumentation der Klasse Lesetext

Lesetext(List<Wort> pWoerter) · Ein Objekt wird mit den Wörtern der Liste pWoerter initialisiert.

boolean istGeeignet() · Die Anfrage liefert den Wert true, wenn das Objekt als Erstlesetext geeignet ist, sonst liefert sie den Wert false.

List<Wort> gibWoerter() · Die Anfrage liefert die Liste aller Objekte der Klasse Wort, die zusammen den Lesetext bilden.

Die Klasse Wort

Objekte der Klasse Wort modellieren Wörter, die auf ihre Eignung zur Verwendung in Erstlesetexten untersucht werden können.

Auszug aus der Dokumentation der Klasse Wort

Wort(List<String> pSilben) · Ein Objekt mit den Silben der Liste pSilben wird initialisiert.

int gibAnzahlSilben() · Die Anfrage liefert die Anzahl der Silben, aus denen das Wort besteht.

String gibZeichenkette() · Die Anfrage liefert die zum Wort gehörige Zeichenkette.

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.

a)

Ausgewählte Wörter für Leseanfänger werden von der folgenden regulären Grammatik $G_1 = (N_1, T_1, S_0, P_1)$ erzeugt.

Nichtterminale: $N_1 = \{S_0, L, M, N, S, T, W\}$

Terminale: $T_1 = \{a, e, l, m, n, o, s, t, u, w\}$

Startsymbol: $S_0$

Produktionen: $P_1 = \{ S_0 \to mM \mid tT \mid wW,$

$L \to l,$

$M \to aL \mid aN \mid uS,$

$N \to n,$

$S \to s,$

$T \to aL \mid oN \mid uN,$

$W \to aL \mid aS \mid eN$ }

Ermitteln Sie drei Wörter, die sich mit der Grammatik $G_1$ ableiten lassen.

= 3, incorrect: isAnswered && validWordsCount < 3 }"

autocomplete="off" autocapitalize="off" spellcheck="false" />

Bestimmen Sie zwei Eigenschaften, die beschreiben, wie die Wörter aufgebaut sind, und die für sämtliche mit der Grammatik $G_1$ ableitbaren Wörter gelten.

Entwerfen Sie die reguläre Grammatik $G_2$, die $G_1$ so erweitert, dass außerdem die Wörter weg und tag erzeugt werden.

e)

Der Praktikant vermutet, dass sich die Frage, ob ein Wort höchstens fünf Zeichen lang ist, nicht nur durch ein Programm, sondern auch durch einen endlichen Automaten beantworten lässt.

Begründen Sie, dass ein endlicher Automat existiert, der feststellt, ob ein Eingabewort höchstens fünf Zeichen enthält.

Aufgabenstellung: Erstlesewörter und Lesetexte

In der Grundschule lernen Kinder zu Beginn nur einfache Wörter („Erstlesewörter“) zu lesen. Ein Wort gilt als einfach, wenn seine Aussprache weitgehend der Schreibweise entspricht und es zudem nur aus wenigen Silben besteht. In der deutschen Sprachwissenschaft gibt es Regeln zum Aufbau einer Silbe; für diese Klausur werden sie folgendermaßen vereinfacht:

Eine Silbe enthält als Silbenkern einen Vokal (a, e, i, o oder u) oder eine Vokalkombination aus zwei Vokalen.

Vor und nach dem Silbenkern kann ein Konsonant oder können mehrere Konsonanten stehen. Mit Konsonanten sind in dieser Aufgabe alle Buchstaben des Alphabets außer den Vokalen gemeint, nämlich die folgenden:

b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z

Abbildung 1: Regeln für den Aufbau einer Silbe

Der Einfachheit halber sind alle Wörter ausschließlich in Kleinbuchstaben notiert.

Wie schwer ein Text zu lesen ist, hängt neben der Silbenanzahl auch von der Buchstabenanzahl je Wort ab: Das Wort „Schifffahrt“ mit 11 Buchstaben ist schwerer zu lesen als das Wort „Nase“ mit 4 Buchstaben.

Lesetexte sollen mithilfe einer Software untersucht werden, die feststellt, ob deren Wörter für Erstleserinnen und Erstleser geeignet sind. Die Software entfernt vor der Prüfung zunächst alle Satzzeichen.

Dabei wird folgende Modellierung zugrunde gelegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lesetext

Objekte der Klasse Lesetext modellieren Lesetexte, die auf ihre Eignung als Erstlesetext untersucht werden können.

Auszug aus der Dokumentation der Klasse Lesetext

Lesetext(List<Wort> pWoerter) · Ein Objekt wird mit den Wörtern der Liste pWoerter initialisiert.

boolean istGeeignet() · Die Anfrage liefert den Wert true, wenn das Objekt als Erstlesetext geeignet ist, sonst liefert sie den Wert false.

List<Wort> gibWoerter() · Die Anfrage liefert die Liste aller Objekte der Klasse Wort, die zusammen den Lesetext bilden.

Die Klasse Wort

Objekte der Klasse Wort modellieren Wörter, die auf ihre Eignung zur Verwendung in Erstlesetexten untersucht werden können.

Auszug aus der Dokumentation der Klasse Wort

Wort(List<String> pSilben) · Ein Objekt mit den Silben der Liste pSilben wird initialisiert.

int gibAnzahlSilben() · Die Anfrage liefert die Anzahl der Silben, aus denen das Wort besteht.

String gibZeichenkette() · Die Anfrage liefert die zum Wort gehörige Zeichenkette.

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.

Viele Silben in deutschen Texten haben nur einen Vokal. Es gibt aber auch Silben mit mehr als einem Vokal, weil es einige typische Vokalkombinationen gibt, wie z. B. ie im Wort viel oder au im Wort Maus.

Der in Abbildung 2 abgebildete Übergangsgraph des endlichen Automaten A über dem Eingabealphabet aller Vokale erkennt die am meisten verwendeten Vokale und Vokalkombinationen in Silben deutscher Wörter.

Teilaufgabe b)

b.1)

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

b.2)

Erläutern Sie, was der Zustand $q_2$ des Automaten A im Sachzusammenhang bedeutet.

b.3)

Erläutern Sie mithilfe des Übergangsgraphen in Abbildung 2, weshalb es sich beim Automaten A nicht um einen deterministischen endlichen Automaten (DEA) handelt.

b.4)

Entwickeln Sie den Übergangsgraphen eines deterministischen endlichen Automaten, dessen akzeptierte Sprache mit der des Automaten A übereinstimmt.

Teilaufgabe c)

Der Automat A soll so verändert werden, dass der veränderte Automat weitere besonders geeignete Erstlesewörter erkennt. Dabei handelt es sich um zweisilbige Wörter der deutschen Sprache wie leiter, tiger oder fangen, für die Folgendes gilt:

1. Die erste Silbe beginnt mit einem Konsonanten, dann folgt ein Vokal bzw. eine Vokalkombination, und danach kann noch maximal ein Konsonant folgen.

2. Die zweite Silbe beginnt mit einem Konsonanten, dann folgt ein Vokal (keine Vokalkombination) und dann ein weiterer Konsonant.

Abbildung 3: Bedingungen für geeignete zweisilbige Erstlesewörter

Da unterschiedliche Konsonanten für die Beurteilung dieses Kriteriums keine Rolle spielen, werden alle Konsonanten der zu untersuchenden Wörter vor der Beurteilung durch den Automaten durch das Zeichen # ersetzt.

Beispiel: tiger wird zu #i#e#

c.1)

Modifizieren und erweitern Sie den Übergangsgraphen des Automaten A derart, dass der neue endliche Automat genau diejenigen vereinfachten Zeichenketten deutscher zweisilbiger Wörter akzeptiert, welche die Bedingungen aus Abbildung 3 erfüllen.

c.2)

Erläutern Sie, auf welche Weise Ihr endlicher Automat die Bedingungen umsetzt.

Aufgabenstellung: Erstlesewörter und Lesetexte

In der Grundschule lernen Kinder zu Beginn nur einfache Wörter („Erstlesewörter“) zu lesen. Ein Wort gilt als einfach, wenn seine Aussprache weitgehend der Schreibweise entspricht und es zudem nur aus wenigen Silben besteht. In der deutschen Sprachwissenschaft gibt es Regeln zum Aufbau einer Silbe; für diese Klausur werden sie folgendermaßen vereinfacht:

Eine Silbe enthält als Silbenkern einen Vokal (a, e, i, o oder u) oder eine Vokalkombination aus zwei Vokalen.

Vor und nach dem Silbenkern kann ein Konsonant oder können mehrere Konsonanten stehen. Mit Konsonanten sind in dieser Aufgabe alle Buchstaben des Alphabets außer den Vokalen gemeint, nämlich die folgenden:

b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z

Abbildung 1: Regeln für den Aufbau einer Silbe

Der Einfachheit halber sind alle Wörter ausschließlich in Kleinbuchstaben notiert.

Wie schwer ein Text zu lesen ist, hängt neben der Silbenanzahl auch von der Buchstabenanzahl je Wort ab: Das Wort „Schifffahrt“ mit 11 Buchstaben ist schwerer zu lesen als das Wort „Nase“ mit 4 Buchstaben.

Lesetexte sollen mithilfe einer Software untersucht werden, die feststellt, ob deren Wörter für Erstleserinnen und Erstleser geeignet sind. Die Software entfernt vor der Prüfung zunächst alle Satzzeichen.

Dabei wird folgende Modellierung zugrunde gelegt:

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Lesetext

Objekte der Klasse Lesetext modellieren Lesetexte, die auf ihre Eignung als Erstlesetext untersucht werden können.

Auszug aus der Dokumentation der Klasse Lesetext

Lesetext(List<Wort> pWoerter) · Ein Objekt wird mit den Wörtern der Liste pWoerter initialisiert.

boolean istGeeignet() · Die Anfrage liefert den Wert true, wenn das Objekt als Erstlesetext geeignet ist, sonst liefert sie den Wert false.

List<Wort> gibWoerter() · Die Anfrage liefert die Liste aller Objekte der Klasse Wort, die zusammen den Lesetext bilden.

Die Klasse Wort

Objekte der Klasse Wort modellieren Wörter, die auf ihre Eignung zur Verwendung in Erstlesetexten untersucht werden können.

Auszug aus der Dokumentation der Klasse Wort

Wort(List<String> pSilben) · Ein Objekt mit den Silben der Liste pSilben wird initialisiert.

int gibAnzahlSilben() · Die Anfrage liefert die Anzahl der Silben, aus denen das Wort besteht.

String gibZeichenkette() · Die Anfrage liefert die zum Wort gehörige Zeichenkette.

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

Vereinfachend wird ein Text als für Leseanfängerinnen und Leseanfänger geeignet betrachtet, wenn jedes seiner Wörter höchstens zwei Silben und höchstens fünf Zeichen umfasst.

Für die Klasse Lesetext ist eine Methode zu entwickeln, die feststellt, ob der betrachtete Lesetext sich als Erstlesetext eignet. Sie liefert true, wenn jedes Wort des Textes höchstens fünf Zeichen und höchstens zwei Silben besitzt, andernfalls liefert sie false.

Der Methodenkopf lautet:

public boolean istGeeignet() 1.

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

2.

Implementieren Sie die Methode istGeeignet gemäß Ihrem Verfahren. [6 Punkte]

public boolean istGeeignet() { }