Abitur NRW Informatik 2023 GK · Haupttermin mit Lösungen

Aufgabenstellung: Sportturniere

Bei Sportturnieren sollen möglichst Teams mit ungefähr gleicher Spielstärke aufeinandertreffen, damit die Leistungsunterschiede berücksichtigt werden. Deshalb werden die Teams nach jeder Runde gemäß ihrem bisherigen Erfolg im Turnier in eine Reihenfolge gebracht. Auf Grundlage dieser Reihenfolgen werden die Paarungen nach diesem Prinzip bestimmt:

Bei Beginn des Turniers werden alle Teams in zufälliger Reihenfolge angeordnet.

Nach jeder Partie wird die Reihenfolge der Teams anhand ihrer Punktzahlen angepasst: Die Reihenfolge der Teams ist absteigend nach deren Punktzahl geordnet. Für einen Sieg erhält ein Team 1 Punkt, für eine Niederlage -1 Punkt. Bei einem Unentschieden erhalten beide Teams 0 Punkte.

Um für ein Team A einen Gegner zu bestimmen, wird das Team B als Gegner ausgewählt, das in der Reihenfolge möglichst nah beim Team A ist.

Um zu vermeiden, dass immer wieder die gleichen Teams gegeneinander spielen, wird eine Maximalzahl gleicher Begegnungen festgelegt: Zwei Teams sollen höchstens so häufig wie in dieser Zahl festgelegt gegeneinander spielen.

Das folgende Softwaremodell stellt einen ersten Entwurf zur Verwaltung eines solchen Turniers dar:

Anlage: Beispieldaten

Teams (in dieser Reihenfolge im Feld teams):

SF Forst

SG Heide

TV Feld

SSV Bergen

TuS Wiese

SV Wald Spiele:

Runde 1:

SF Forst – SG Heide: Sieger ist SF Forst

TV Feld – SSV Bergen: Sieger ist TV Feld

TuS Wiese – SV Wald: Unentschieden

Runde 2:

SF Forst – TV Feld: Unentschieden

TuS Wiese – SG Heide: Sieger ist TuS Wiese

SV Wald – SSV Bergen: Unentschieden

Runde 3:

SF Forst – TuS Wiese: noch nicht beendet

TV Feld – SV Wald: noch nicht beendet

SSV Bergen – SG Heide: noch nicht beendet

Aktueller Punktestand:

Platzierung · Team · Punkte

1. · SF Forst · 1

2. · TV Feld · 1

3. · TuS Wiese · 1

4. · SV Wald · 0

5. · SSV Bergen · -1

6. · SG Heide · -2

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Team

Objekte der Klasse Team repräsentieren die zu einem Team vorhandenen Daten. Zu jedem Team in einem Turnier soll immer nur genau ein Objekt existieren. Ein Objekt der Klasse verwaltet Referenzen auf die Spiel-Objekte, an denen das Team beteiligt ist.

Dokumentation der Klasse Team

Team(String pName)

Ein Objekt der Klasse wird initialisiert. Die übergebene Zeichenkette wird gespeichert. Das Team hat keine eigenen Spiele gespeichert.

String gibName()

Die Methode liefert den Namen des Teams zurück.

int berechnePunkte()

Die Methode liefert die Punkte des Teams auf Basis der eigenen Spiele, die bereits beendet sind. Die Rückgabe entspricht der Summe der Einzelbewertungen jedes beendeten Spiels für das Team. Wurde noch kein eigenes Spiel beendet, wird 0 zurückgegeben.

void fuegeHinzu(Spiel pSpiel)

Das durch den Parameter referenzierte Objekt der Klasse Spiel wird zu den eigenen Spielen hinzugefügt.

int zaehleSpieleGegen(Team pGegner)

Die Methode liefert die Anzahl der gespielten Spiele, die das als Parameter übergebene Team gegen dieses Team gespielt hat. Wird null für den Parameter übergeben, so wird -1 zurückgegeben.

Die Klasse Turnierverwaltung

Objekte der Klasse Turnierverwaltung verwaltet alle Teams und alle Spiele eines Turniers. Die Teams werden in der Reihenfolge verwaltet, in der sie sich für das Turnier angemeldet haben.

Dokumentation der Klasse Turnierverwaltung

Turnierverwaltung(Team[] pTeams)

Ein Objekt der Klasse wird initialisiert. Die im Feld übergebenen Teams werden in einer zufälligen Reihenfolge angeordnet. Es existieren keine Spiele.

Team[] berechnePlatzierungen()

Die Methode liefert alle im Turnier vorhanden Teams in einem Feld. Das Feld ist absteigend nach der Punktzahl der Teams sortiert. Sind zwei Teams punktgleich, ist die Reihenfolge zufällig.

void fuegeHinzu(Spiel pSpiel)

Das übergebene Spiel wird der Liste aller Spiele hinzugefügt. Außerdem wird beiden Teams das übergebene Spiel hinzugefügt. Dabei wird davon ausgegangen, dass die beiden im Spiel referenzierten Objekte der Klasse Team nicht identisch sind und von dem Objekt der Klasse Turnierverwaltung referenziert werden.

Team[] gibTeams()

Die Methode liefert die Teams in der Reihenfolge, in der sie sich zum Turnier angemeldet haben.

Dokumentation dieser privaten Methode der Klasse:

List<Team> filtereTeams(Team pTeam, int pGleicheBegegnungen)

Es wird eine Liste zurückgegeben, die alle Teams enthält, die bisher in dem Turnier höchstens den als Wert von pGleicheBegegnungen mal gegen das übergebene Team gespielt haben. Die übergebenen Parameter werden nicht geprüft, es wird davon ausgegangen, dass sinnvolle Werte übergeben werden.

Die Klasse Spiel

Ein Objekt der Klasse Spiel verwaltet die beteiligten Teams, ob das Spiel bereits beendet wurde und das siegende Team des Spiels, sofern es eins gibt.

Dokumentation der Klasse Spiel

Spiel(Team pTeamA, Team pTeamB)

Ein Objekt der Klasse wird initialisiert. Die beiden übergebenen Teams werden in dem Spiel gespeichert. Das Spiel gilt als nicht beendet. Es ist kein Sieger eingetragen.

Team gibTeamA()

Die Methode liefert das Team A des Spiels.

Team gibTeamB()

Die Methode liefert das Team B des Spiels.

boolean istBeendet()

Ist das Spiel beendet, wird true zurückgegeben, andernfalls wird false zurückgegeben.

int berechnePunkte(Team pTeam)

Ist das Spiel nicht beendet oder ist kein Sieger gespeichert (das Spiel also als unentschieden gewertet), so wird der Wert 0 zurückgegeben. Ist das im Parameter referenzierte Team nicht an dem Spiel beteiligt, wird der Wert -1 zurückgegeben.

void setzeSieger(Team pSieger)

Das Spiel wird als beendet gewertet. Das übergebene Team wird als Sieger gesetzt. Wird null übergeben, gilt das Spiel als unentschieden. Es wird davon ausgegangen, dass entweder null oder ein an dem Spiel beteiligtes Team übergeben wird.

Team gibSieger()

Die Methode liefert den Sieger des Spiels. Gibt es keinen Sieger, weil das Spiel unentschieden oder noch nicht beendet ist, wird null geliefert.

Die generische Klasse List

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

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

a)

Analysieren Sie das Implementationsdiagramm und erläutern Sie, was die abgebildeten Assoziationen im Sachkontext bedeuten.

Erläutern Sie unter Verwendung des Implementationsdiagramms und der Dokumentation im Anhang, auf welche Weise das Modell das Hinzufügen eines Spiels und das Eintragen des Siegers vorsieht. (4 + 4 Punkte)

d)

Um die Software etwas flexibler zu gestalten, soll das Modell um folgende Punkte verändert werden:

1. Es soll für jedes Spiel das Datum und die Uhrzeit festgehalten werden, wann das Spiel beginnt.

2. Für jedes Team soll jeweils angefragt werden können, gegen welche Teams es bereits gespielt hat.

Erweitern Sie das Modell aus Abbildung 1 entsprechend den genannten Änderungswünschen.

Erläutern Sie, auf welche Weise Ihr Modell die Anforderungen erfüllt.

Hinweis: Stellen Sie lediglich die Abweichungen des Modells gegenüber Abbildung 1 dar. (7 + 5 Punkte)

Aufgabenstellung: Sportturniere

Bei Sportturnieren sollen möglichst Teams mit ungefähr gleicher Spielstärke aufeinandertreffen, damit die Leistungsunterschiede berücksichtigt werden. Deshalb werden die Teams nach jeder Runde gemäß ihrem bisherigen Erfolg im Turnier in eine Reihenfolge gebracht. Auf Grundlage dieser Reihenfolgen werden die Paarungen nach diesem Prinzip bestimmt:

Bei Beginn des Turniers werden alle Teams in zufälliger Reihenfolge angeordnet.

Nach jeder Partie wird die Reihenfolge der Teams anhand ihrer Punktzahlen angepasst: Die Reihenfolge der Teams ist absteigend nach deren Punktzahl geordnet. Für einen Sieg erhält ein Team 1 Punkt, für eine Niederlage -1 Punkt. Bei einem Unentschieden erhalten beide Teams 0 Punkte.

Um für ein Team A einen Gegner zu bestimmen, wird das Team B als Gegner ausgewählt, das in der Reihenfolge möglichst nah beim Team A ist.

Um zu vermeiden, dass immer wieder die gleichen Teams gegeneinander spielen, wird eine Maximalzahl gleicher Begegnungen festgelegt: Zwei Teams sollen höchstens so häufig wie in dieser Zahl festgelegt gegeneinander spielen.

Das folgende Softwaremodell stellt einen ersten Entwurf zur Verwaltung eines solchen Turniers dar:

Anlage: Beispieldaten

Teams (in dieser Reihenfolge im Feld teams):

SF Forst

SG Heide

TV Feld

SSV Bergen

TuS Wiese

SV Wald Spiele:

Runde 1:

SF Forst – SG Heide: Sieger ist SF Forst

TV Feld – SSV Bergen: Sieger ist TV Feld

TuS Wiese – SV Wald: Unentschieden

Runde 2:

SF Forst – TV Feld: Unentschieden

TuS Wiese – SG Heide: Sieger ist TuS Wiese

SV Wald – SSV Bergen: Unentschieden

Runde 3:

SF Forst – TuS Wiese: noch nicht beendet

TV Feld – SV Wald: noch nicht beendet

SSV Bergen – SG Heide: noch nicht beendet

Aktueller Punktestand:

Platzierung · Team · Punkte

1. · SF Forst · 1

2. · TV Feld · 1

3. · TuS Wiese · 1

4. · SV Wald · 0

5. · SSV Bergen · -1

6. · SG Heide · -2

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Team

Objekte der Klasse Team repräsentieren die zu einem Team vorhandenen Daten. Zu jedem Team in einem Turnier soll immer nur genau ein Objekt existieren. Ein Objekt der Klasse verwaltet Referenzen auf die Spiel-Objekte, an denen das Team beteiligt ist.

Dokumentation der Klasse Team

Team(String pName)

Ein Objekt der Klasse wird initialisiert. Die übergebene Zeichenkette wird gespeichert. Das Team hat keine eigenen Spiele gespeichert.

String gibName()

Die Methode liefert den Namen des Teams zurück.

int berechnePunkte()

Die Methode liefert die Punkte des Teams auf Basis der eigenen Spiele, die bereits beendet sind. Die Rückgabe entspricht der Summe der Einzelbewertungen jedes beendeten Spiels für das Team. Wurde noch kein eigenes Spiel beendet, wird 0 zurückgegeben.

void fuegeHinzu(Spiel pSpiel)

Das durch den Parameter referenzierte Objekt der Klasse Spiel wird zu den eigenen Spielen hinzugefügt.

int zaehleSpieleGegen(Team pGegner)

Die Methode liefert die Anzahl der gespielten Spiele, die das als Parameter übergebene Team gegen dieses Team gespielt hat. Wird null für den Parameter übergeben, so wird -1 zurückgegeben.

Die Klasse Turnierverwaltung

Objekte der Klasse Turnierverwaltung verwaltet alle Teams und alle Spiele eines Turniers. Die Teams werden in der Reihenfolge verwaltet, in der sie sich für das Turnier angemeldet haben.

Dokumentation der Klasse Turnierverwaltung

Turnierverwaltung(Team[] pTeams)

Ein Objekt der Klasse wird initialisiert. Die im Feld übergebenen Teams werden in einer zufälligen Reihenfolge angeordnet. Es existieren keine Spiele.

Team[] berechnePlatzierungen()

Die Methode liefert alle im Turnier vorhanden Teams in einem Feld. Das Feld ist absteigend nach der Punktzahl der Teams sortiert. Sind zwei Teams punktgleich, ist die Reihenfolge zufällig.

void fuegeHinzu(Spiel pSpiel)

Das übergebene Spiel wird der Liste aller Spiele hinzugefügt. Außerdem wird beiden Teams das übergebene Spiel hinzugefügt. Dabei wird davon ausgegangen, dass die beiden im Spiel referenzierten Objekte der Klasse Team nicht identisch sind und von dem Objekt der Klasse Turnierverwaltung referenziert werden.

Team[] gibTeams()

Die Methode liefert die Teams in der Reihenfolge, in der sie sich zum Turnier angemeldet haben.

Dokumentation dieser privaten Methode der Klasse:

List<Team> filtereTeams(Team pTeam, int pGleicheBegegnungen)

Es wird eine Liste zurückgegeben, die alle Teams enthält, die bisher in dem Turnier höchstens den als Wert von pGleicheBegegnungen mal gegen das übergebene Team gespielt haben. Die übergebenen Parameter werden nicht geprüft, es wird davon ausgegangen, dass sinnvolle Werte übergeben werden.

Die Klasse Spiel

Ein Objekt der Klasse Spiel verwaltet die beteiligten Teams, ob das Spiel bereits beendet wurde und das siegende Team des Spiels, sofern es eins gibt.

Dokumentation der Klasse Spiel

Spiel(Team pTeamA, Team pTeamB)

Ein Objekt der Klasse wird initialisiert. Die beiden übergebenen Teams werden in dem Spiel gespeichert. Das Spiel gilt als nicht beendet. Es ist kein Sieger eingetragen.

Team gibTeamA()

Die Methode liefert das Team A des Spiels.

Team gibTeamB()

Die Methode liefert das Team B des Spiels.

boolean istBeendet()

Ist das Spiel beendet, wird true zurückgegeben, andernfalls wird false zurückgegeben.

int berechnePunkte(Team pTeam)

Ist das Spiel nicht beendet oder ist kein Sieger gespeichert (das Spiel also als unentschieden gewertet), so wird der Wert 0 zurückgegeben. Ist das im Parameter referenzierte Team nicht an dem Spiel beteiligt, wird der Wert -1 zurückgegeben.

void setzeSieger(Team pSieger)

Das Spiel wird als beendet gewertet. Das übergebene Team wird als Sieger gesetzt. Wird null übergeben, gilt das Spiel als unentschieden. Es wird davon ausgegangen, dass entweder null oder ein an dem Spiel beteiligtes Team übergeben wird.

Team gibSieger()

Die Methode liefert den Sieger des Spiels. Gibt es keinen Sieger, weil das Spiel unentschieden oder noch nicht beendet ist, wird null geliefert.

Die generische Klasse List

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

Dokumentation der Klasse List<ContentType>

List()

Eine leere Liste wird erzeugt.

boolean isEmpty()

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

boolean hasAccess()

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

void next()

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

void toFirst()

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

void toLast()

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

ContentType getContent()

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

void setContent(ContentType pContent)

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

void append(ContentType pContent)

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

void insert(ContentType pContent)

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

void concat(List<ContentType> pList)

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

void remove()

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

b)

Die private Methode filtereTeams der Klasse Turnierverwaltung filtert die Teams heraus, die höchstens eine bestimmte Anzahl ( pGleicheBegegnungen) von Spielen gegen das übergebene Team gespielt haben. Das als Parameter übergebene Team ist nicht im Ergebnis der Methode enthalten. Die übergebenen Parameter sollen nicht geprüft werden, es wird davon ausgegangen, dass sinnvolle Werte übergeben werden. Die Methode hat den folgenden Methodenkopf:

private List<Team> filtereTeams(Team pTeam, int pGleicheBegegnungen)

Entwickeln Sie einen Algorithmus, der das Filtern gemäß der obigen Beschreibung umsetzt.

Implementieren Sie die Methode.

[10 Punkte]

c)

Im Quellcode des Projekts findet sich in der Klasse Team die folgende Methode ohne Dokumentation:

1 public int[] wasErmittleIch() {

2 int[] result = new int[3];

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

4 result[i] = 0;

5 }

6 eigeneSpiele.toFirst();

7 while (eigeneSpiele.hasAccess()) {

8 Spiel spiel = eigeneSpiele.getContent();

9 if (spiel.istBeendet()) {

10 if (spiel.gibSieger() == null) {

11 result[1] = result[1] + 1;

12 } else {

13 if (spiel.gibSieger().gibName().equals(name)) {

14 result[0] = result[0] + 1;

15 } else {

16 result[2] = result[2] + 1;

17 }

18 }

19 }

20 eigeneSpiele.next();

21 }

22 return result;

23 }

Analysieren Sie die Methode für das Team SF Forst anhand der Beispieldaten in der Anlage.

result[0] (Siege):

result[1] (Unentschieden):

result[2] (Niederlagen):

e)

Bei der Umsetzung der Software ist zu klären, wie die Partien der nächsten Runde bestimmt werden. Vereinfachend bleibt unberücksichtigt, wie oft zwei Mannschaften bereits gegeneinander gespielt haben. Zudem wird eine gerade Teamanzahl angenommen.

Jede Partie soll voraussichtlich möglichst ausgeglichen verlaufen. Dafür sollen Teams mit ähnlichem Erfolg im Turnier aufeinandertreffen: Die Punktdifferenz zweier Gegner soll möglichst klein sein.

Hierzu liegen zwei Vorschläge vor:

(i) Beginne in der Mitte der Rangfolge:

Wähle das erste der beiden mittleren Teams.

Dieses Team ist in der Reihenfolge von zwei Teams umgeben: Wähle von den beiden Teams das als Gegner aus, zu dem die Punktdifferenz geringer ist.

Ist die Punktdifferenz gleich, wähle das untere Team als Gegner.

Entferne die beiden gewählten Teams aus der Rangfolge.

Wiederhole diesen Prozess, bis nur noch zwei Teams ungeplant sind.

Sind nur noch zwei Teams ungeplant, lasse diese beiden gegeneinander spielen.

(ii) Beginne bei der aktuellen Rangfolge beim ersten Team:

Wähle das erste Team gegen das zweite Team als Spiel.

Entferne beide Teams aus der Rangfolge.

Wiederhole diesen Prozess, bis die Rangfolge leer ist.

Aufgabenstellung: Sachkontext Wohnungsankauf der Firma Besserwohnen

Die Firma Besserwohnen handelt in einer ländlichen Region mit Wohnungen und vermietet sie auch. Sie möchte ausschließlich Wohnungen erwerben, bei denen ein Wertzuwachs zu erwarten ist.

Als Entscheidungshilfe für die Beschäftigten beim Ankauf neuer Wohnungen hat eine Expertengruppe der Firma, gestützt auf Erfahrungen aus früheren Käufen, ein Einschätzungsverfahren auf Basis eines Binärbaums entwickelt. Es liefert anhand der folgenden drei nummerierten Kriterien für eine neue Wohnung entweder eine Kaufempfehlung oder keine.

Zimmeranzahl (Kriteriumnummer 0)

Quadratmeterpreis: Preis für je einen Quadratmeter in Euro (Kriteriumnummer 1)

Größe: Wohnungsgröße in Quadratmetern 1 (Kriteriumnummer 2)

1 Die Einheit „Quadratmeter“ wird in dieser Klausur mit qm abgekürzt.

Abbildung 1 stellt den Binärbaum dar, den die Firma Besserwohnen derzeit verwendet. Solch ein Baum heißt im Folgenden Einschätzungsbaum.

Man startet an der Wurzel und beantwortet für eine neue Wohnung die dort enthaltenen Fragen. Schon in jedem Knoten liegt eine Einschätzung vor, ob der Kauf empfohlen wird oder nicht (AKTUELLE KAUFEMPFEHLUNG). Enthält ein Knoten eine weitere Frage, ist die Einschätzung vermutlich besser, wenn man auch diese für die betrachtete Wohnung beantwortet und bei Ja in den linken, bei Nein in den rechten Teilbaum wechselt.

Die Einschätzung einer neuen Wohnung mithilfe des Baums endet erst, wenn ein Blatt erreicht ist oder der in einem Knoten zu vergleichende Kriterienwert wegen unvollständiger Angaben zur Wohnung fehlt.

Abbildung 2: Die Daten zu zwei Wohnungen · Wohnung 1 · Wohnung 2

Zimmeranzahl · 3 · 5

Quadratmeterpreis · 25 € · 30 €

Größe · 70 qm · unbekannt

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Einschaetzungsprogramm

Objekte der Klasse Einschaetzungsprogramm dienen der Einschätzung von neuen Wohnungen hinsichtlich der Frage, ob sie zur weiteren Vermarktung angekauft werden sollten.

Auszug aus der Dokumentation der Klasse Einschaetzungsprogramm

Einschaetzungsprogramm()

Ein Objekt der Klasse Einschaetzungsprogramm wird initialisiert.

boolean ermittleKaufempfehlung(Wohnung pWohnung)

Die Anfrage liefert true, falls eine Kaufempfehlung für die übergebene Wohnung pWohnung gegeben wird. Sonst liefert sie false.

public void macheEtwas(List<Boolean> pPfad, Frage pFrage, boolean pKaufempfehlungBeiJa)

Die Methode wird in Aufgabenteil d) untersucht.

Die Klasse Wohnung

Ein Objekt der Klasse Wohnung repräsentiert eine Wohnung und verwaltet ihre Eigenschaften.

Auszug aus der Dokumentation der Klasse Wohnung

Wohnung(Integer pZimmeranzahl, Integer pQuadratmeterpreis, Integer pGroesse)

Ein Objekt der Klasse Wohnung wird initialisiert. Die als Parameter übergebenen Werte werden übernommen. Für Werte, die für die zugehörige Wohnung nicht vorliegen, soll dabei null übergeben werden.

Integer gibWert(int pKriteriumnummer)

Die Anfrage liefert den eingetragenen Wert des Kriteriums mit der als Parameter übergebenen Nummer pKriteriumnummer. Hierbei steht die Nummer 0 für die Zimmeranzahl, die Nummer 1 für den Quadratmeterpreis und die Nummer 2 für die Größe. Bei allen anderen Werten von pKriteriumnummer wird null zurückgeliefert. Wurde bei Erstellung des Wohnung-Objekts für ein Kriterium der Wert null übergeben, so wird entsprechend null als Wert von diesem Kriterium zurückgegeben.

Die Klasse Inhalt

Ein Objekt der Klasse Inhalt repräsentiert den einem Knoten eines Einschätzungsbaums zugewiesenen Inhalt. Mit einem Objekt der Klasse Inhalt kann daher sowohl die Einschätzung bzgl. einer Kaufempfehlung gemäß der Position im Baum gespeichert werden als auch eine präzisierende Frage in Form eines Objekts der Klasse Frage verwaltet werden.

Auszug aus der Dokumentation der Klasse Inhalt

Inhalt(boolean pKaufempfehlung)

Ein Objekt der Klasse Inhalt wird initialisiert und speichert den als Parameter übergebenen Wert pKaufempfehlung. Es wird zu Beginn kein Objekt der Klasse Frage verwaltet.

boolean gibKaufempfehlung()

Die Anfrage liefert den gespeicherten Wert für eine Kaufempfehlung.

Frage gibFrage()

Falls ein Objekt der Klasse Frage von diesem Inhalt-Objekt verwaltet wird, so wird es zurückgegeben. Sonst wird null zurückgegeben.

void setzeFrage(Frage pFrage)

Das als Parameter übergebene Objekt wird gespeichert. Wird null übergeben, so verwaltet dieses Inhaltsobjekt nach Ausführung kein Objekt der Klasse Frage.

Die Klasse Frage

Ein Objekt der Klasse Frage repräsentiert eine Frage, bei der der Wert eines Kriteriums einer Wohnung mit einem Schwellenwert verglichen wird. Hierfür verwaltet ein Objekt der Klasse Frage die Nummer eines Kriteriums und den Schwellenwert.

Auszug aus der Dokumentation der Klasse Frage

Frage(int pKriteriumnummer, int pSchwellenwert)

Ein Objekt der Klasse Frage wird mit den als Parameter übergebenen Werten initialisiert.

String gibAntwort(Wohnung pWohnung)

Wenn bei der übergebenen Wohnung pWohnung kein Wert für das Kriterium mit der von der Frage verwalteten Kriteriumnummer eingetragen ist, sondern dort null eingetragen ist, dann ist kein Vergleich mit dem Schwellenwert möglich und die Methode liefert den Wert null. Sonst vergleicht die Methode den betreffenden Kriterienwert der Wohnung mit dem von der Frage verwalteten Schwellenwert und gibt die Zeichenkette (den String) "Ja" zurück, falls der betreffende Kriterienwert der Wohnung kleiner gleich dem Schwellenwert ist, und gibt andernfalls die Zeichenkette (den String) "Nein" zurück.

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.

Die generische Klasse BinaryTree<ContentType>

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

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree()

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

BinaryTree(ContentType pContent)

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

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

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

boolean isEmpty()

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

void setContent(ContentType pContent)

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

ContentType getContent()

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

void setLeftTree(BinaryTree<ContentType> pTree)

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

void setRightTree(BinaryTree<ContentType> pTree)

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

BinaryTree<ContentType> getLeftTree()

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

BinaryTree<ContentType> getRightTree()

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

Das Ermitteln von Einschätzungen soll mit einem Programm automatisiert werden. Abbildung 3 zeigt einen Ausschnitt aus dem Implementationsdiagramm des Einschätzungsprogramms der Firma Besserwohnen.

b)

Aufgabenstellung: Sachkontext Wohnungsankauf der Firma Besserwohnen

Die Firma Besserwohnen handelt in einer ländlichen Region mit Wohnungen und vermietet sie auch. Sie möchte ausschließlich Wohnungen erwerben, bei denen ein Wertzuwachs zu erwarten ist.

Als Entscheidungshilfe für die Beschäftigten beim Ankauf neuer Wohnungen hat eine Expertengruppe der Firma, gestützt auf Erfahrungen aus früheren Käufen, ein Einschätzungsverfahren auf Basis eines Binärbaums entwickelt. Es liefert anhand der folgenden drei nummerierten Kriterien für eine neue Wohnung entweder eine Kaufempfehlung oder keine.

Zimmeranzahl (Kriteriumnummer 0)

Quadratmeterpreis: Preis für je einen Quadratmeter in Euro (Kriteriumnummer 1)

Größe: Wohnungsgröße in Quadratmetern 1 (Kriteriumnummer 2)

1 Die Einheit „Quadratmeter“ wird in dieser Klausur mit qm abgekürzt.

Abbildung 1 stellt den Binärbaum dar, den die Firma Besserwohnen derzeit verwendet. Solch ein Baum heißt im Folgenden Einschätzungsbaum.

Man startet an der Wurzel und beantwortet für eine neue Wohnung die dort enthaltenen Fragen. Schon in jedem Knoten liegt eine Einschätzung vor, ob der Kauf empfohlen wird oder nicht (AKTUELLE KAUFEMPFEHLUNG). Enthält ein Knoten eine weitere Frage, ist die Einschätzung vermutlich besser, wenn man auch diese für die betrachtete Wohnung beantwortet und bei Ja in den linken, bei Nein in den rechten Teilbaum wechselt.

Die Einschätzung einer neuen Wohnung mithilfe des Baums endet erst, wenn ein Blatt erreicht ist oder der in einem Knoten zu vergleichende Kriterienwert wegen unvollständiger Angaben zur Wohnung fehlt.

Abbildung 2: Die Daten zu zwei Wohnungen · Wohnung 1 · Wohnung 2

Zimmeranzahl · 3 · 5

Quadratmeterpreis · 25 € · 30 €

Größe · 70 qm · unbekannt

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Einschaetzungsprogramm

Objekte der Klasse Einschaetzungsprogramm dienen der Einschätzung von neuen Wohnungen hinsichtlich der Frage, ob sie zur weiteren Vermarktung angekauft werden sollten.

Auszug aus der Dokumentation der Klasse Einschaetzungsprogramm

Einschaetzungsprogramm()

Ein Objekt der Klasse Einschaetzungsprogramm wird initialisiert.

boolean ermittleKaufempfehlung(Wohnung pWohnung)

Die Anfrage liefert true, falls eine Kaufempfehlung für die übergebene Wohnung pWohnung gegeben wird. Sonst liefert sie false.

public void macheEtwas(List<Boolean> pPfad, Frage pFrage, boolean pKaufempfehlungBeiJa)

Die Methode wird in Aufgabenteil d) untersucht.

Die Klasse Wohnung

Ein Objekt der Klasse Wohnung repräsentiert eine Wohnung und verwaltet ihre Eigenschaften.

Auszug aus der Dokumentation der Klasse Wohnung

Wohnung(Integer pZimmeranzahl, Integer pQuadratmeterpreis, Integer pGroesse)

Ein Objekt der Klasse Wohnung wird initialisiert. Die als Parameter übergebenen Werte werden übernommen. Für Werte, die für die zugehörige Wohnung nicht vorliegen, soll dabei null übergeben werden.

Integer gibWert(int pKriteriumnummer)

Die Anfrage liefert den eingetragenen Wert des Kriteriums mit der als Parameter übergebenen Nummer pKriteriumnummer. Hierbei steht die Nummer 0 für die Zimmeranzahl, die Nummer 1 für den Quadratmeterpreis und die Nummer 2 für die Größe. Bei allen anderen Werten von pKriteriumnummer wird null zurückgeliefert. Wurde bei Erstellung des Wohnung-Objekts für ein Kriterium der Wert null übergeben, so wird entsprechend null als Wert von diesem Kriterium zurückgegeben.

Die Klasse Inhalt

Ein Objekt der Klasse Inhalt repräsentiert den einem Knoten eines Einschätzungsbaums zugewiesenen Inhalt. Mit einem Objekt der Klasse Inhalt kann daher sowohl die Einschätzung bzgl. einer Kaufempfehlung gemäß der Position im Baum gespeichert werden als auch eine präzisierende Frage in Form eines Objekts der Klasse Frage verwaltet werden.

Auszug aus der Dokumentation der Klasse Inhalt

Inhalt(boolean pKaufempfehlung)

Ein Objekt der Klasse Inhalt wird initialisiert und speichert den als Parameter übergebenen Wert pKaufempfehlung. Es wird zu Beginn kein Objekt der Klasse Frage verwaltet.

boolean gibKaufempfehlung()

Die Anfrage liefert den gespeicherten Wert für eine Kaufempfehlung.

Frage gibFrage()

Falls ein Objekt der Klasse Frage von diesem Inhalt-Objekt verwaltet wird, so wird es zurückgegeben. Sonst wird null zurückgegeben.

void setzeFrage(Frage pFrage)

Das als Parameter übergebene Objekt wird gespeichert. Wird null übergeben, so verwaltet dieses Inhaltsobjekt nach Ausführung kein Objekt der Klasse Frage.

Die Klasse Frage

Ein Objekt der Klasse Frage repräsentiert eine Frage, bei der der Wert eines Kriteriums einer Wohnung mit einem Schwellenwert verglichen wird. Hierfür verwaltet ein Objekt der Klasse Frage die Nummer eines Kriteriums und den Schwellenwert.

Auszug aus der Dokumentation der Klasse Frage

Frage(int pKriteriumnummer, int pSchwellenwert)

Ein Objekt der Klasse Frage wird mit den als Parameter übergebenen Werten initialisiert.

String gibAntwort(Wohnung pWohnung)

Wenn bei der übergebenen Wohnung pWohnung kein Wert für das Kriterium mit der von der Frage verwalteten Kriteriumnummer eingetragen ist, sondern dort null eingetragen ist, dann ist kein Vergleich mit dem Schwellenwert möglich und die Methode liefert den Wert null. Sonst vergleicht die Methode den betreffenden Kriterienwert der Wohnung mit dem von der Frage verwalteten Schwellenwert und gibt die Zeichenkette (den String) "Ja" zurück, falls der betreffende Kriterienwert der Wohnung kleiner gleich dem Schwellenwert ist, und gibt andernfalls die Zeichenkette (den String) "Nein" zurück.

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.

Die generische Klasse BinaryTree<ContentType>

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

Dokumentation der Klasse BinaryTree<ContentType>

BinaryTree()

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

BinaryTree(ContentType pContent)

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

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

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

boolean isEmpty()

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

void setContent(ContentType pContent)

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

ContentType getContent()

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

void setLeftTree(BinaryTree<ContentType> pTree)

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

void setRightTree(BinaryTree<ContentType> pTree)

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

BinaryTree<ContentType> getLeftTree()

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

BinaryTree<ContentType> getRightTree()

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

a) Zunächst soll der Einschätzungsbaum aus Abbildung 1 verwendet werden. In Abbildung 2 sind die Werte von zwei Wohnungen angegeben.

· Wohnung 1 · Wohnung 2

Zimmeranzahl · 3 · 5

Quadratmeterpreis · 25 € · 30 €

Größe · 70 qm · unbekannt

Ermitteln Sie für jede der beiden Wohnungen aus Abbildung 2, ob eine Kaufempfehlung ausgesprochen würde.

Geben Sie für eine Wohnung ein Beispiel mit Zimmeranzahl, Quadratmeterpreis und Größe an, bei dem zur Einschätzung vier Fragen beantwortet werden und keine Kaufempfehlung erfolgt.

Ermitteln Sie, in welchem Bereich die Größe einer Wohnung mit vier Zimmern und einem Quadratmeterpreis von 40 € liegen muss, um eine Kaufempfehlung zu erhalten.

c) Die Klasse Einschaetzungsprogramm besitzt eine Methode ermittleKaufempfehlung mit dem folgenden Methodenkopf:

public boolean ermittleKaufempfehlung(Wohnung pWohnung) Mithilfe des verwalteten Einschätzungsbaums bestimmt diese Methode für das übergebene Objekt der Klasse Wohnung, ob eine Kaufempfehlung gegeben wird oder nicht.

Entwickeln und erläutern Sie ein algorithmisches Verfahren, das mit dem verwalteten Einschätzungsbaum die Kaufempfehlung für eine Wohnung bestimmt.

Implementieren Sie gemäß Ihrem Verfahren die Methode ermittleKaufempfehlung sowie bei Bedarf zusätzliche Hilfsmethoden.

d) In der Klasse Einschaetzungsprogramm wurde folgende Methode macheEtwas implementiert, die weder dokumentiert noch kommentiert wurde:

1 public void macheEtwas(List<Boolean> pPfad, Frage pFrage,

2

boolean pKaufempfehlungBeiJa) {

3

BinaryTree<Inhalt> bt = einschaetzungsbaum;

4

pPfad.toFirst();

5

while (pPfad.hasAccess() && !bt.isEmpty()) {

6

if (pPfad.getContent() == true) {

7

bt = bt.getLeftTree();

8

} else {

9

bt = bt.getRightTree();

10

}

11

pPfad.next();

12

}

13

14

if (!bt.isEmpty() && bt.getLeftTree().isEmpty()

15

&& bt.getRightTree().isEmpty()) {

16

bt.getContent().setzeFrage(pFrage);

17

bt.getLeftTree().setContent(

18

new Inhalt(pKaufempfehlungBeiJa));

19

bt.getRightTree().setContent(

20

new Inhalt(!pKaufempfehlungBeiJa));

21

}

22 } Analysieren Sie den Quelltext und erläutern Sie, wie die Methode macheEtwas funktioniert.

Erläutern Sie, welche Wirkung die Methode macheEtwas im Sachkontext hat.

e) Jeder Knoten im Einschätzungsbaum (vgl. Abbildung 1) repräsentiert eine Menge von Wohnungen, die über gleiche Eigenschaften hinsichtlich der drei Kriterien Zimmeranzahl, Quadratmeterpreis und Größe verfügen.

Das zweite Blatt von links im Einschätzungsbaum in Abbildung 1 repräsentiert z. B. alle Wohnungen, die eine Zimmeranzahl von höchstens 2 haben und deren Größe größer als 15 qm ist. Der Quadratmeterpreis darf beliebig sein.

Ein Softwareentwickler macht daher den folgenden Vorschlag:

Zu jedem Knoten im Einschätzungsbaum, der eine positive Kaufempfehlung enthält, soll ein Objekt einer neuen Klasse Profil erzeugt werden. In diesem Objekt wird für jedes Kriterium gespeichert, in welchem Intervall (vom zu überschreitenden Minimalwert bis zum zulässigen Maximalwert) der Wert des entsprechenden Kriteriums liegen muss, damit man im Baum an die Stelle des entsprechenden Knotens gekommen wäre.

Das Profil zum oben angesprochenen zweiten Blatt von links im Baum aus Abbildung 1 speichert dann folgende Intervalle (untere Grenze jeweils ausgeschlossen, obere jeweils eingeschlossen):

· zu überschreitender Minimalwert · zulässiger Maximalwert

Zimmeranzahl · – · 2

Quadratmeterpreis · – · –

Größe · 15 · –

Statt des Baums in Abbildung 1 kann nun eine Liste der Objekte vom Typ Profil gespeichert werden. Hierbei müssen nur Profile mit Kaufempfehlung gespeichert werden. Die Einschätzung einer Wohnung wird wie folgt ermittelt: Wenn in der Liste ein Profil-Objekt gefunden werden kann, zu dem die Wohnung passt, so wird eine Kaufempfehlung gegeben, andernfalls nicht.

Beurteilen Sie den obigen Vorschlag daraufhin, ob er zu denselben Einschätzungen führt wie der Einschätzungsbaum.

Aufgabenstellung: Sachkontext Bahnlinien-Datenbank

Ein Informatikprojektkurs plant, einige Bahnlinien in einer Datenbank zu modellieren. In einer ersten Version sollen unter anderem die Bahnhöfe und die Streckenabschnitte erfasst werden.

Ein Streckenabschnitt ist eine direkte Verbindung von dem einen Bahnhof zu dem anderen Bahnhof ohne Zwischenhalt. Aus Sicherheitsgründen kann ein Streckenabschnitt nur in einer Richtung und somit nicht für die Gegenrichtung genutzt werden.

Eine Bahnlinie besteht aus Streckenabschnitten, die die Folge der Bahnhöfe auf dieser Bahnlinie beschreiben. Dabei wird für jeden zugehörigen Streckenabschnitt die Fahrzeit in Minuten angegeben.

Um die Daten zu verwalten, will der Projektkurs eine relationale Datenbank einrichten, die auf der folgenden Teilmodellierung beruht:

Die folgenden Aufgaben beziehen sich auf das in Abbildung 3 dargestellte Datenbankschema, das nur einen Teil der Gesamtdatenbank abbildet. Im Anhang stehen Beispieldaten zu diesem Schema zur Verfügung.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema

Bahnhof

Name

barrierefrei

Glücksdorf · 1

Oberdorf · 0

Medeburg · 1

Zweierwalde · 1

Hintertupfingen · 1

Bahnlinie

ID

Name

L1 · Bergexpress

L2 · Burglinie

L3 · Hintertupfingenlinie

L4 · Glücksdorfexpress

Streckenabschnitt

ID

vonBahnhofName

zuBahnhofname

1 · Glücksdorf · Oberdorf

2 · Oberdorf · Medeburg

3 · Medeburg · Hintertupfingen

4 · Medeburg · Zweierwalde

5 · Zweierwalde · Hintertupfingen

6 · Hintertupfingen · Glücksdorf

gehoertZu

StreckenabschnittID

BahnlinieID

Abschnittsnummer

Fahrzeit

1 · L1 · 1 · 30

2 · L1 · 2 · 20

3 · L1 · 3 · 90

1 · L2 · 1 · 40

2 · L2 · 2 · 50

4 · L2 · 3 · 30

5 · L3 · 1 · 50

6 · L4 · 1 · 90

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Bahnlinientest

Ein Objekt der Klasse wird genutzt, um die Datenbankverbindung und die Datenbankabfragen zu testen.

Bahnlinientest()

Ein Objekt vom Typ DatabaseConnector wird initialisiert und stellt die Datenbankverbindung her.

int ermittleEtwas(String pID)

Diese Methode ist Bestandteil der Teilaufgabe d.

Die Klasse DatabaseConnector

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

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

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

void executeStatement(String pSQLStatement)

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

QueryResult getCurrentQueryResult()

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

String getErrorMessage()

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

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

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

String[][] getData()

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

String[] getColumnNames()

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

String[] getColumnTypes()

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

int getRowCount()

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

int getColumnCount()

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

a)

Erläutern Sie, auf welche Weise die Bahnlinie L1 samt ihren Streckenabschnitten in der Datenbank abgelegt ist (vgl. Beispieldaten).

Beschreiben Sie den in Abbildung 2 dargestellten Ausschnitt des Entity-Relationship-Modells.

Erläutern Sie für jeden im Entity-Relationship-Modell enthaltenen Beziehungstyp unter Beachtung der Kardinalitäten, wie er im Datenbankschema realisiert wurde.

e)

Ein Schüler meint, man könne den Entitätstyp Bahnhof ohne nennenswerte Nachteile entfernen. Die Bahnhofsnamen stehen ohnehin im Entitätstyp Streckenabschnitt als vonBahnhofName und zuBahnhofName angegeben. Die Barrierefreiheit der Bahnhöfe lasse sich zudem in den Entitätstyp Streckenabschnitt übernehmen und dort als Attribute barrierefreiVonBahnhof und barrierefreiZuBahnhof ergänzen.

Begründen Sie, weshalb man diesen Vorschlag zurückweisen sollte.

Aufgabenstellung: Sachkontext Bahnlinien-Datenbank

Ein Informatikprojektkurs plant, einige Bahnlinien in einer Datenbank zu modellieren. In einer ersten Version sollen unter anderem die Bahnhöfe und die Streckenabschnitte erfasst werden.

Ein Streckenabschnitt ist eine direkte Verbindung von dem einen Bahnhof zu dem anderen Bahnhof ohne Zwischenhalt. Aus Sicherheitsgründen kann ein Streckenabschnitt nur in einer Richtung und somit nicht für die Gegenrichtung genutzt werden.

Eine Bahnlinie besteht aus Streckenabschnitten, die die Folge der Bahnhöfe auf dieser Bahnlinie beschreiben. Dabei wird für jeden zugehörigen Streckenabschnitt die Fahrzeit in Minuten angegeben.

Um die Daten zu verwalten, will der Projektkurs eine relationale Datenbank einrichten, die auf der folgenden Teilmodellierung beruht:

Die folgenden Aufgaben beziehen sich auf das in Abbildung 3 dargestellte Datenbankschema, das nur einen Teil der Gesamtdatenbank abbildet. Im Anhang stehen Beispieldaten zu diesem Schema zur Verfügung.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema

Bahnhof

Name

barrierefrei

Glücksdorf · 1

Oberdorf · 0

Medeburg · 1

Zweierwalde · 1

Hintertupfingen · 1

Bahnlinie

ID

Name

L1 · Bergexpress

L2 · Burglinie

L3 · Hintertupfingenlinie

L4 · Glücksdorfexpress

Streckenabschnitt

ID

vonBahnhofName

zuBahnhofname

1 · Glücksdorf · Oberdorf

2 · Oberdorf · Medeburg

3 · Medeburg · Hintertupfingen

4 · Medeburg · Zweierwalde

5 · Zweierwalde · Hintertupfingen

6 · Hintertupfingen · Glücksdorf

gehoertZu

StreckenabschnittID

BahnlinieID

Abschnittsnummer

Fahrzeit

1 · L1 · 1 · 30

2 · L1 · 2 · 20

3 · L1 · 3 · 90

1 · L2 · 1 · 40

2 · L2 · 2 · 50

4 · L2 · 3 · 30

5 · L3 · 1 · 50

6 · L4 · 1 · 90

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Bahnlinientest

Ein Objekt der Klasse wird genutzt, um die Datenbankverbindung und die Datenbankabfragen zu testen.

Bahnlinientest()

Ein Objekt vom Typ DatabaseConnector wird initialisiert und stellt die Datenbankverbindung her.

int ermittleEtwas(String pID)

Diese Methode ist Bestandteil der Teilaufgabe d.

Die Klasse DatabaseConnector

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

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

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

void executeStatement(String pSQLStatement)

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

QueryResult getCurrentQueryResult()

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

String getErrorMessage()

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

void close()

Die Datenbankverbindung wird geschlossen.

Die Klasse QueryResult

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

String[][] getData()

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

String[] getColumnNames()

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

String[] getColumnTypes()

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

int getRowCount()

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

int getColumnCount()

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

Teilaufgabe b)

Aus der Datenbank sollen die folgenden Angaben ermittelt werden:

i.

Ermittelt werden sollen die Namen der Bahnhöfe, die von Medeburg aus über einen einzelnen Streckenabschnitt unmittelbar erreicht werden können. Die Ausgabe soll aufsteigend nach Bahnhofsnamen geordnet sein. [3 Punkte]

ii.

Ermittelt werden sollen zu jeder Bahnlinie ihr Name und ihre gesamte Fahrzeit. [5 Punkte]

Teilaufgabe c)

Gegeben ist die nachstehende SQL-Anweisung:

1 SELECT gehoertZu.BahnlinieID, vonBahnhofName,

2 zuBahnhofname, Fahrzeit

3 FROM Streckenabschnitt

4 INNER JOIN gehoertZu

5 ON gehoertZu.StreckenabschnittID = Streckenabschnitt.ID

6 WHERE Fahrzeit = (

7 SELECT MAX(Fahrzeit)

8 FROM gehoertZu

9)

Analysieren und erläutern Sie die Unterabfrage in den Zeilen 7 – 8. [3 Punkte]

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

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

Teilaufgabe d)

Eine Schülerin des Projektkurses hat zusätzlich eine Erweiterung programmiert. Abbildung 4 stellt einen Ausschnitt des Implementationsdiagramms dar.

Die nachstehende Methode der Klasse Bahnlinientest besitzt keine Dokumentation.

1 public int ermittleEtwas(String pID) {

2 boolean gefunden = false;

3 int anzahl = 1;

4 db.executeStatement("SELECT * FROM gehoertZu ");

5 if (db.getErrorMessage() == null) {

6 QueryResult qr = db.getCurrentQueryResult();

7 if (qr.getRowCount() > 0) {

8 for (int i = 0; i < qr.getRowCount(); i++) {

9 String bahnlinieID = qr.getData()[i][1];

10 if (pID.equals(bahnlinieID)) {

11 anzahl = anzahl + 1;

12 gefunden = true;

13 }

14 }

15 }

16 }

17 if (!gefunden) {

18 anzahl = -1;

19 }

20 return anzahl;

21 }

Analysieren Sie die Methode und erläutern Sie, wie sie arbeitet, wobei Sie die SQL-Anweisung in Zeile 4 einbeziehen. [4 Punkte]

Geben Sie jeweils den Rückgabewert der Methode an, wenn diese mit den Beispieldaten im Anhang aufgerufen wird: [4 Punkte]

:

Erläutern Sie bezogen auf den Sachkontext, welche Information die Methode bestimmt. [3 Punkte]

Entscheiden Sie, ob sich die von der Methode gelieferte Information auch mit einer SQL-Anweisung bestimmen lässt, sodass keine Schleife nötig ist. Begründen Sie kurz bzw. geben Sie die Idee oder die Anweisung an. [3 Punkte]

Aufgabenstellung:

Beim Snooker, einer Variante des Billards, liegen zu Beginn 15 rote Kugeln auf dem Tisch, die als Rote (r) bezeichnet werden, sowie 6 Kugeln in anderen Farben, die unter dem Begriff Farbige (f) zusammengefasst werden. Zusätzlich befindet sich eine weiße Kugel, die Weiße (w), auf dem Tisch (vgl. Abbildung 1).

Bei einem Spielzug (auch „Stoß“ genannt) soll man mit dem Billardstock die Weiße so anstoßen, dass sie eine andere Kugel trifft und diese eingelocht wird, d. h. in eines der Löcher am Tischrand (die sogenannten „Taschen“) fällt.

Der Snookerschüler Jonte und sein Trainer Max spielen eine Trainingsvariante, in der jede eingelochte Kugel unmittelbar wieder auf den Tisch gelegt wird.

Der Spieler am Zug muss mit dem ersten Stoß genau eine Rote einlochen. Hat er damit Erfolg, bleibt er am Zug und muss mit dem nächsten Stoß genau eine Farbige einlochen. Gelingt auch das, setzt er das abwechselnde Einlochen von Roten und Farbigen fort, bis ihm ein Fehler unterläuft.

Ein Fehler liegt vor, wenn die falsche Kugelsorte angespielt und eingelocht wird, die Weiße eingelocht wird oder bei einem Stoß gar keine Kugel eingelocht wird. Auch bei einem Fehler werden eingelochte Kugeln auf ihre Anfangsposition zurückgelegt. Nach einem Fehler wechselt der Spieler.

Zur Vereinfachung nehmen wir an, dass im Training ausschließlich die folgenden Ereignisse auftreten:

Stoß (s) – Ein neuer Stoß beginnt durch das Anstoßen der Weißen mit dem Billardstock.

Nach dem Anstoßen der Weißen tritt genau eines der folgenden vier Ereignisse ein:

Eine rote Kugel wird angespielt und eingelocht (r).

Eine farbige Kugel wird angespielt und eingelocht (f).

Die weiße Kugel wird eingelocht (w).

Keine Kugel wird eingelocht (k).

Außerdem wird angenommen, dass pro Stoß höchstens eine Kugel eingelocht wird.

Jonte eröffnet jedes Trainingsspiel. Beide trainieren, bis sie aufhören möchten, wobei der letzte Stoß stets noch zum Spiel zählt.

Jonte und Max halten ihre Spiele in Protokollen fest, um sie später für das weitere Training auszuwerten. Dazu schreiben sie die Buchstaben der eingetretenen Ereignisse in zeitlicher Reihenfolge auf.

Beispiel für ein sehr kurzes Trainingsspiel: Jonte locht eine Rote und eine Farbige ein, bei seinem dritten Stoß fällt keine Kugel in eine Tasche. Anschließend locht Max mit seinem ersten Stoß eine Rote ein. Das zugehörige Protokoll lautet: srsfsksr

Zur Auswertung vieler Protokolle wurde ein deterministischer endlicher Automat A entworfen, der Spielprotokolle untersucht. Sein Zustandsübergangsdiagramm zeigt Abbildung 2.

a)

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

[4 Punkte] Ermitteln Sie ein vom Automaten $A$ akzeptiertes Wort, bei dessen Verarbeitung sämtliche Zustände durchlaufen werden, und erläutern Sie, wie das Trainingsspiel verläuft, das mit diesem Wort protokolliert wurde.

[6 Punkte] Erläutern Sie im Sachzusammenhang, was die Zustände $q_0$ , $q_2$ und $q_6$ bedeuten und wofür die von ihnen ausgehenden Übergänge stehen.

b)

Ein deterministischer endlicher Automat $B$ mit dem Eingabealphabet $\{f, k, r, s, w\}$ soll konstruiert werden. Als Eingabe erhält er garantiert nur gültige Spielprotokolle. Er soll von diesen genau jene akzeptieren, bei denen im zugehörigen Trainingsspiel sowohl Jonte als auch Max mindestens einmal gestoßen haben.

[2 Punkte] Geben Sie das kürzestmögliche Wort eines Spielprotokolls an, in dem Jonte und Max beide mindestens einmal gestoßen haben.

[2 Punkte] Geben Sie ein Wort der Länge 6 für ein Spielprotokoll an, in dem lediglich einer der beiden gestoßen hat.

[7 Punkte] Entwerfen Sie das Zustandsübergangsdiagramm des Automaten $B$ .