Abitur NRW Informatik 2021 · LK · Nachtermin

Aufgabenstellung:

Im Spiel Brainbreaker gilt es, einen verborgenen vierstelligen Code herauszufinden. Jede Stelle enthält dabei eine Ziffer zwischen 0 und 5. Man darf Tipps abgeben, die ebenfalls vierstellig sind und nur Ziffern von 0 bis 5 enthalten. Das System bewertet jeden Tipp. Anhand dieser Bewertung lässt sich erkennen, wie dicht der Tipp am gesuchten geheimen Code liegt.

Die Bewertung läuft folgendermaßen ab (siehe Beispiel in Abbildung 1):

Stimmen Tipp und geheimer Code an derselben Stelle in der Ziffer überein, zählt das als Volltreffer (V) und erhält 10 Punkte.

Kommt eine Ziffer in Tipp und geheimem Code vor, jedoch an verschiedenen Stellen, zählt das als Teiltreffer (T) und erhält einen Punkt.

Bei der Bewertung darf jede Stelle des geheimen Codes maximal einmal einbezogen werden.

Ein Volltreffer zählt nicht zugleich als Teiltreffer.

Die Gesamtbewertung eines Tipps ist die Summe der Punkte seiner einzelnen Stellen und bildet die einzige Rückmeldung zum abgegebenen Tipp. Das Spielziel besteht darin, den geheimen Code mit möglichst wenigen Tipps zu finden.

Für die Programmierung des Spiels Brainbreaker hat Jana ein Implementationsdiagramm erstellt. Abbildung 2 stellt einen Teil dieses Diagramms dar. Die Dokumentation der wichtigen Methoden befindet sich im Anhang.

Teilaufgabe a)

a.1)

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

a.2)

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

a.3)

Erläutern Sie, warum es keinen Tipp mit einer Bewertung von 31 geben kann.

Teilaufgabe c)

Janas Freund Ben hat begonnen, die Klasse Ziffernfolge zu implementieren. Für die Ermittlung der Punktzahl eines Tipps hat er die folgende Methode entwickelt:

public int ermittleBewertung(Ziffernfolge pTipp) {

Ziffernfolge tippKopie = pTipp.bildeKopie();

Ziffernfolge kopie = bildeKopie();

int punkte = 0;

for (int i = 0; i < tippKopie.gibLaenge(); i++) {

if (tippKopie.gibWert(i) == kopie.gibWert(i)) {

tippKopie.setzewert(i, -1);

kopie.setzewert(i, -2);

punkte = punkte + 10;

}

}

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

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

if (tippKopie.gibWert(i) == kopie.gibWert(j)) {

punkte = punkte + 1;

tippKopie.setzewert(i, -1);

kopie.setzewert(j, -2);

}

}

}

return punkte;

}

Analysieren Sie die Methode ermittleBewertung, indem Sie jeweils den Rückgabewert dieser Methode für die Parameterwerte ermitteln, wenn der geheime Code 5414 lautet:

pAndereFolge

geheimer Code

Rückgabewert

3250

5414

4514

5414

1212

5414

c.2)

Erläutern Sie die Funktionsweise der Methode im Sachzusammenhang und begründen Sie, warum es im Zusammenhang mit dieser Funktionsweise wichtig ist, die Setze-Methoden in den Zeilen 7 und 8 sowie 16 und 17 mit zwei unterschiedlichen Werten im zweiten Parameter aufzurufen, die keine zulässigen Ziffern eines Codes sind.

c.3)

Begründen Sie anhand der Beispieldaten, weshalb Volltreffer vor Teiltreffern bewertet werden müssen.

Teilaufgabe d)

Entwickeln Sie für die Methode erzeugeAlleZiffernfolgen eine algorithmische Strategie.

Implementieren Sie die Methode erzeugeAlleZiffernfolgen in Java:

public List<Ziffernfolge> erzeugeAlleZiffernfolgen()

Teilaufgabe e)

Jana hat Ben erzählt, dass sie plant, das Spiel auch so zu implementieren, dass der Computer in der Rolle des Ratenden ist. Ben schlägt Jana für den Computer die Strategie gemäß folgendem Struktogramm vor:

Ben behauptet, mit seiner Strategie sei der geheime Code spätestens nach 10 Tipps gefunden (ein Tipp entspricht dabei der Bewertung einer Ziffernfolge).

e.1)

Analysieren Sie den im Struktogramm dargestellten Algorithmus und erläutern Sie, wie er im Sachzusammenhang funktioniert.

e.2)

Beurteilen Sie die Behauptung von Ben.

Aufgabenstellung:

Im Spiel Brainbreaker gilt es, einen verborgenen vierstelligen Code herauszufinden. Jede Stelle enthält dabei eine Ziffer zwischen 0 und 5. Man darf Tipps abgeben, die ebenfalls vierstellig sind und nur Ziffern von 0 bis 5 enthalten. Das System bewertet jeden Tipp. Anhand dieser Bewertung lässt sich erkennen, wie dicht der Tipp am gesuchten geheimen Code liegt.

Die Bewertung läuft folgendermaßen ab (siehe Beispiel in Abbildung 1):

Stimmen Tipp und geheimer Code an derselben Stelle in der Ziffer überein, zählt das als Volltreffer (V) und erhält 10 Punkte.

Kommt eine Ziffer in Tipp und geheimem Code vor, jedoch an verschiedenen Stellen, zählt das als Teiltreffer (T) und erhält einen Punkt.

Bei der Bewertung darf jede Stelle des geheimen Codes maximal einmal einbezogen werden.

Ein Volltreffer zählt nicht zugleich als Teiltreffer.

Die Gesamtbewertung eines Tipps ist die Summe der Punkte seiner einzelnen Stellen und bildet die einzige Rückmeldung zum abgegebenen Tipp. Das Spielziel besteht darin, den geheimen Code mit möglichst wenigen Tipps zu finden.

Für die Programmierung des Spiels Brainbreaker hat Jana ein Implementationsdiagramm erstellt. Abbildung 2 stellt einen Teil dieses Diagramms dar. Die Dokumentation der wichtigen Methoden befindet sich im Anhang.

b)

Erläutern Sie die Teilmodellierung, die in Abbildung 2 dargestellt ist, bezogen auf den Sachzusammenhang. (9 Punkte)

Aufgabenstellung:

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

Die Zählsoftware soll um weitere Merkmale ergänzt werden. Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Dabei wird bei der Fahrzeugklasse zwischen dem üblichen Personenverkehr mit Pkw auf der einen Seite und allen übrigen, vor allem größeren Kraftfahrzeugen auf der anderen Seite (z. B. Bussen, Traktoren und Lastkraftwagen) unterschieden.

Grundlage der Software ist das Implementationsdiagramm, von dem die folgende Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der verwendeten Klassen befindet sich im Anhang.

Teilaufgabe a) [8 Punkte]

Bisher haben Kraftfahrzeuge mit den Ortskürzeln AC, MS, MS und PB eine Zählstelle passiert. Der folgende binäre Suchbaum stellt diese Messungen dar:

a.1

a.2

Erweitern Sie den binären Suchbaum aus Abbildung 1 um weitere Messungen: Die Kamera erfasst nun nacheinander die Ortskürzel ST, MS, BI, RS, SO, MS, OB, HSK, PB, DO (stellen Sie den dabei jeweils entstehenden Suchbaum nach dem Einfügen der dritten und der letzten dieser Messungen dar).

Teilaufgabe c) [14 Punkte]

Für die Statistik sollen die erfassten Daten nach bestimmten Kriterien ausgewertet werden. Zunächst soll bestimmt werden, wie viele Kraftfahrzeuge die Zählstelle innerhalb eines gegebenen Zeitraums passiert haben. Dafür erhält eine noch zu implementierende Methode ermittleAnzahl zwei Objekte der Klasse Zeitstempel, die Beginn und Ende des Zeitraums festlegen. Ihr Methodenkopf lautet:

public int ermittleAnzahl(Zeitstempel pVon, Zeitstempel pBis) c.1

c.2

Aufgabenstellung:

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

Die Zählsoftware soll um weitere Merkmale ergänzt werden. Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Dabei wird bei der Fahrzeugklasse zwischen dem üblichen Personenverkehr mit Pkw auf der einen Seite und allen übrigen, vor allem größeren Kraftfahrzeugen auf der anderen Seite (z. B. Bussen, Traktoren und Lastkraftwagen) unterschieden.

Grundlage der Software ist das Implementationsdiagramm, von dem die folgende Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der verwendeten Klassen befindet sich im Anhang.

b)

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

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

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

[12 Punkte]

d)

Weil täglich mehrere Verkehrszählungen an verschiedenen Standorten und in verschiedenen Zeiträumen stattfinden, soll die Software beliebig viele Zählungen getrennt voneinander verwalten können. Zu jeder Zählung sollen ihr Standort (genaue Adresse mit Straße, Hausnummer, Postleitzahl und Ort) sowie ihr Beginn und ihr Ende gespeichert werden.

Entwerfen Sie ausgehend von der Modellierung in Abbildung 2 eine erweiterte Modellierung in Form eines Implementationsdiagramms, die den oben genannten Anforderungen genügt.

Hinweis: Stellen Sie in Ihrer Lösung nur diejenigen Teile dar, die eine Veränderung zu Abbildung 2 darstellen. Geben Sie in den relevanten Klassen lediglich die Konstruktoren an; weitere Methoden müssen nicht dargestellt werden.

Erläutern Sie die von Ihnen erweiterte Modellierung.

[10 Punkte]

Aufgabenstellung:

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

Die Zählsoftware soll um weitere Merkmale ergänzt werden. Für jede Messung sollen der exakte Zeitpunkt sowie die Fahrzeugklasse des Fahrzeugs, das die Zählstelle durchfuhr, festgehalten werden. Dabei wird bei der Fahrzeugklasse zwischen dem üblichen Personenverkehr mit Pkw auf der einen Seite und allen übrigen, vor allem größeren Kraftfahrzeugen auf der anderen Seite (z. B. Bussen, Traktoren und Lastkraftwagen) unterschieden.

Grundlage der Software ist das Implementationsdiagramm, von dem die folgende Abbildung 2 einen Ausschnitt zeigt. Die Dokumentation der verwendeten Klassen befindet sich im Anhang.

Eine Stadt will ermitteln, welche Fahrzeuge von Berufspendlern genutzt werden. Die Softwarefirma empfiehlt, bei sämtlichen Zählungen neben Ortskürzeln, Kfz-Klassen und Zeitpunkten zusätzlich die kompletten Kfz-Kennzeichen abzulegen. Weil man annimmt, dass alle Pendler mit dem Pkw anreisen, sollen die erfassten Daten anschließend über das Attribut kfzKlasse der Klasse Messung gefiltert werden. Anhand der Kennzeichen sollen dann die Fahrzeuge bestimmt werden, die regelmäßig zu ähnlichen Tageszeiten an derselben Zählstelle vorbeikommen. Die Softwarefirma hebt hervor, der Datenschutz sei sichergestellt, weil alle Daten verschlüsselt und sicher gespeichert würden.

e)

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

Aufgabenstellung:

Das Unternehmen GoBigOrGoHome24 will die Gesundheit seiner Belegschaft fördern, indem es zur regelmäßigen Teilnahme an Sportangeboten anregt. Die Beschäftigten wählen aus einem breiten Angebot verschiedener Sportarten und melden sich an. Ein Sportangebot umfasst eine zuvor festgelegte Zahl an Einheiten, die zu absolvieren sind. Nimmt eine Mitarbeiterin oder ein Mitarbeiter an allen Einheiten teil, übernimmt die Firma die Kosten des Angebots in voller Höhe. Fehlt jemand unentschuldigt, verringert sich der Zuschuss der Firma. Die Länge einer Sporteinheit wird in Minuten angegeben.

Um die Daten zu verwalten, plant die Firma den Aufbau einer relationalen Datenbank, die auf der folgenden Teilmodellierung beruht:

Die folgenden Aufgaben beziehen sich auf das Datenbankschema aus Abbildung 2, das nur einen Teil der gesamten Datenbank abbildet. Beispieldaten dazu finden sich im Anhang.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Teilnehmer

ID · Vorname · Nachname

1 · Ada · Lovelace

2 · John · von Neumann

3 · Alan · Turing

4 · Konrad · Zuse

5 · Tim · Berners-Lee

Sportangebot

ID · Sportart · Trainername

42 · Zumba · Joseph Weizenbaum

101 · Fitness · Gottfried Wilhelm Leibniz

2020 · Fitness · Gottfried Wilhelm Leibniz

2021 · Yoga · Joseph Weizenbaum

Sporteinheit

ID · Datum · Thema · Dauer · SportangebotID

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

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

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

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

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

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

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

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

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

angemeldet

TeilnehmerID · SportangebotID

1 · 42

1 · 101

1 · 2020

2 · 42

3 · 42

3 · 101

4 · 101

5 · 101

fehlt

TeilnehmerID · SporteinheitID · istEntschuldigt

1 · 1 · ja

1 · 2 · ja

3 · 9 · ja

4 · 8 · nein

5 · 4 · ja

5 · 5 · nein

a)

Erläutern Sie die im Entity-Relationship-Diagramm in Abbildung 1 dargestellten Beziehungstypen bezogen auf den Sachkontext.

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

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

d)

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

Überführen Sie das Datenbankschema aus Abbildung 2 in ein neues Schema, das die dritte Normalform erfüllt.

Hinweis: Alle Sporteinheiten eines Sportangebots haben die gleiche Dauer. [9 Punkte]

e)

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

i. Die Teilnehmerinnen und Teilnehmer müssen nun einen bestimmten Beitrag als Eigenanteil für jedes Angebot selbst bezahlen. Es soll gespeichert werden, wie hoch dieser Eigenanteil ist und ob bzw. wann sie dieser bezahlt wurde.

ii. Für eine Trainerin bzw. einen Trainer soll eine E-Mail-Adresse verwaltet werden. Außerdem sollen auch mehrere Trainerinnen und Trainer ein Sportangebot gemeinsam anbieten können.

Modellieren Sie eine Erweiterung des Datenbankschemas aus Abbildung 2, sodass der neue Entwurf die beschriebenen Aspekte zusätzlich abdeckt.

Erläutern Sie, auf welche Weise Ihr Modell die Anforderungen erfüllt, und begründen Sie die gewählten Kardinalitäten.

Hinweis: Unveränderte Relationsschemata brauchen nicht aufgeführt zu werden. [12 Punkte]

Aufgabenstellung:

Das Unternehmen GoBigOrGoHome24 will die Gesundheit seiner Belegschaft fördern, indem es zur regelmäßigen Teilnahme an Sportangeboten anregt. Die Beschäftigten wählen aus einem breiten Angebot verschiedener Sportarten und melden sich an. Ein Sportangebot umfasst eine zuvor festgelegte Zahl an Einheiten, die zu absolvieren sind. Nimmt eine Mitarbeiterin oder ein Mitarbeiter an allen Einheiten teil, übernimmt die Firma die Kosten des Angebots in voller Höhe. Fehlt jemand unentschuldigt, verringert sich der Zuschuss der Firma. Die Länge einer Sporteinheit wird in Minuten angegeben.

Um die Daten zu verwalten, plant die Firma den Aufbau einer relationalen Datenbank, die auf der folgenden Teilmodellierung beruht:

Die folgenden Aufgaben beziehen sich auf das Datenbankschema aus Abbildung 2, das nur einen Teil der gesamten Datenbank abbildet. Beispieldaten dazu finden sich im Anhang.

Anlage: Ausschnitt aus den Beispieldaten zum Datenbankschema aus Abbildung 2

Teilnehmer

ID · Vorname · Nachname

1 · Ada · Lovelace

2 · John · von Neumann

3 · Alan · Turing

4 · Konrad · Zuse

5 · Tim · Berners-Lee

Sportangebot

ID · Sportart · Trainername

42 · Zumba · Joseph Weizenbaum

101 · Fitness · Gottfried Wilhelm Leibniz

2020 · Fitness · Gottfried Wilhelm Leibniz

2021 · Yoga · Joseph Weizenbaum

Sporteinheit

ID · Datum · Thema · Dauer · SportangebotID

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

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

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

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

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

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

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

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

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

angemeldet

TeilnehmerID · SportangebotID

1 · 42

1 · 101

1 · 2020

2 · 42

3 · 42

3 · 101

4 · 101

5 · 101

fehlt

TeilnehmerID · SporteinheitID · istEntschuldigt

1 · 1 · ja

1 · 2 · ja

3 · 9 · ja

4 · 8 · nein

5 · 4 · ja

5 · 5 · nein

Teilaufgabe b) [11 Punkte]

Es sollen die folgenden Informationen aus der Datenbank abgerufen werden:

Entwerfen Sie zu jeder der oben genannten Anfragen eine passende SQL-Anweisung.

i.

Ermittelt werden sollen die Namen sämtlicher Trainerinnen und Trainer zusammen mit der Zahl der Sportangebote, die sie jeweils durchführen. Die Ausgabe soll aufsteigend nach dem Namen der Trainerinnen und Trainer geordnet sein. [3 Punkte]

ii.

Gesucht wird eine Übersicht über die Teilnehmerinnen und Teilnehmer, die Sporteinheiten versäumt haben. Für jede Person sollen Vorname, Nachname und die Anzahl ihrer versäumten Sporteinheiten ausgegeben werden. [4 Punkte]

iii.

Ermitteln sollen Sie Vor- und Nachname aller Personen, die zu mindestens einem Sportangebot angemeldet sind und bisher nie gefehlt haben. [4 Punkte]

Teilaufgabe c) [8 Punkte]

Gegeben ist die folgende SQL-Anweisung:

1 SELECT *

2 FROM (

3 SELECT Sportangebot.Sportart, Sportangebot.Trainername,

4 COUNT(angemeldet.SportangebotID) as X

5 FROM Sportangebot

6 LEFT JOIN angemeldet

7 ON Sportangebot.ID = angemeldet.SportangebotID

8 GROUP BY Sportangebot.ID

9) AS A

10 WHERE A.X >= 2

11 ORDER BY A.X DESC

1.

Analysieren und erläutern Sie erst die Unterabfrage (Zeilen 3 bis 9) und danach die vollständige SQL-Anweisung. [6 Punkte]

2.

Erläutern Sie, welche Information die gesamte SQL-Anweisung im Sachzusammenhang liefert. [2 Punkte]

Aufgabenstellung

Die Künstlerin Mosa Iks strebt mit ihren Werken nach Ruhm. Diese setzen sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b genauso aufeinanderfolgen wie die zugehörigen Farbsteine in der Zeile des Kunstwerks. Bereits sehr erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

a)

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

Entscheiden Sie für die Wörter grg, gbggg und rrg jeweils, ob sie eine zulässige Zeile des Werkes „GESTERN“ darstellen.

Entwickeln Sie für einen deterministischen endlichen Automaten das Zustandsübergangsdiagramm, sodass er exakt diejenigen Wörter akzeptiert, die im Werk „GESTERN“ zulässige Zeilen aus Mosaiksteinen darstellen.

b)

Das Mosaik „HEUTE“, das Mosa gerade anfertigt, setzt sich aus Zeilen von Mosaiksteinen zusammen, deren Wortdarstellungen vom folgenden deterministischen endlichen Automaten A erkannt werden:

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

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

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

Aufgabenstellung

Die Künstlerin Mosa Iks strebt mit ihren Werken nach Ruhm. Diese setzen sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b genauso aufeinanderfolgen wie die zugehörigen Farbsteine in der Zeile des Kunstwerks. Bereits sehr erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

c)

Die Künstlerin entwickelt ständig neue Einfälle. Zurzeit begeistern sie Mosaike, deren Zeilen durch Wörter beschrieben werden, die nach der folgenden Grammatik $G$ gebildet sind:

Startsymbol: $S$

Nichtterminale: $N = \{S, A, B, C, D\}$

Terminale: $T = \{r, g, b\}$

Produktionen: $P = \{$

$S \rightarrow rrA$,

$A \rightarrow bB \mid bD \mid gC \mid gD$,

$B \rightarrow bB \mid bD$,

$C \rightarrow gC \mid gD$,

$D \rightarrow rr \mid rrA$

$\}$

Ermitteln Sie für die folgenden Wörter die Ableitungen und entscheiden Sie anhand dieser, ob die Wörter in der Sprache der Grammatik $G$ liegen: $rrbrr$, $rrggr$, $rrggrrbrr$.

d)

Mosa plant schon ihr nächstes Werk mit dem Titel „MORGEN“. Jede Zeile soll links mit einem oder mehreren roten Steinen beginnen, danach mindestens einen blauen Stein aufweisen und am Ende nur noch gelbe Steine enthalten. Dabei soll es doppelt so viele gelbe Steine geben wie rote Steine am Zeilenanfang.

Begründen Sie, weshalb sich kein endlicher Automat konstruieren lässt, der feststellen kann, ob ein Wort eine Zeile des Werks „MORGEN“ beschreibt.

Entwerfen Sie einen nichtdeterministischen Kellerautomaten, der genau diejenigen Wörter akzeptiert, die eine Steinzeile des Werks „MORGEN“ darstellen.

Aufgabenstellung

Die Künstlerin Mosa Iks strebt mit ihren Werken nach Ruhm. Diese setzen sich aus beliebig vielen Zeilen mit beliebig vielen Mosaiksteinen in den Farben rot (r), gelb (g) und blau (b) zusammen. Jede Zeile eines Werks beschreibt sie als Wort, in dem die Buchstaben r, g und b genauso aufeinanderfolgen wie die zugehörigen Farbsteine in der Zeile des Kunstwerks. Bereits sehr erfolgreich war sie mit Bildern, deren Mosaiksteine nach bestimmten Regeln angeordnet sind.

e) Die Künstlerin möchte automatisiert prüfen, ob Zeichenketten Wörter sind, die Zeilen des Werks „MORGEN“ darstellen. Vorab wird bereits sichergestellt, dass die zu prüfenden Zeichenketten ausschließlich die Zeichen r, g und b enthalten.

Sie bittet einen befreundeten Informatiker, eine Methode zu schreiben, die zu einer als Parameter übergebenen linearen Liste aus Zeichenketten true zurückgibt, wenn alle Listenelemente Wörter sind, die Zeilen des Werks „MORGEN“ darstellen. Falls mindestens eines der Listenelemente keine Zeile des Werks darstellt, so gibt sie false zurück.

Der Methodenkopf der Methode sindWoerterVonMorgen in der Klasse Mosaik lautet:

public boolean sindWoerterVonMorgen(List<String> pListe)

1.

Entwickeln Sie für die Methode sindWoerterVonMorgen ein algorithmisches Verfahren. [4 Punkte]

2.

Implementieren Sie die Methode sindWoerterVonMorgen. [6 Punkte]

Hinweis: Dem Anhang der Abiturprüfung können Sie Auszüge aus der Dokumentation der Klassen String und List<ContentType> entnehmen.