Abitur Hessen Informatik 2022 · GK

Ausleihsystem StadtRad

Eine Großstadt hat ein Ausleihsystem namens StadtRad für Fahrräder eingeführt. Nach dem Motto „Aufsteigen und losfahren“ soll für die Bürgerinnen und Bürger an zahlreichen Leihstationen im gesamten Stadtgebiet die Möglichkeit bestehen, ein Rad auszuleihen und dieses wieder an derselben oder einer anderen Station zurückzugeben. Jede Station verfügt dabei über Stellplätze, an denen die Räder angeschlossen werden. Die Anzahl der Stellplätze ist an jeder Station gleich.

Zur Verwaltung des StadtRad-Ausleihsystems

erhalten die Stationen eine eindeutige Stationsnummer,

muss jeder Kunde im System registriert sein; er ist dann über seine Kundennummer zu identifizieren,

verfügt jedes Rad über eine eindeutige Radnummer, die bei der Ausleihe beim Kunden eingetragen wird. Ist ein Rad gerade nicht verliehen, ist die Radnummer beim Stellplatz eingetragen, an dem das Rad angeschlossen ist.

Den Kunden wird eine App zur Verfügung gestellt, mit der sie sich im System registrieren, die Verfügbarkeit von Rädern an einer Station überprüfen sowie deren Ausleihe und Rückgabe durchführen können.

Material 1

GUI der StadtRad-App

Material 2

Klassendiagramm der Klasse Station

Material 3

Methode zurückgeben(...) der Klasse Verwaltung

01 public boolean zurückgeben(int KundenNr, int StationsNr) {

02 Kunde einKunde = gibKunde(KundenNr);

03 Station eineStation = gibStation(StationsNr);

04 if (einKunde != null && eineStation != null) {

05 int RadNr = einKunde.getAusgeliehenesRad();

06 if (eineStation.abstellen(RadNr) == true) {

07 einKunde.setAusgeliehenesRad(0);

08 einKunde.setEndzeit();

09 einKunde.berechneGebühren();

10 return true;

11 }

12 }

13 return false;

14 }

Material 4

Methoden suche(...) und suche2(...)

01 public int suche(String Nachname, String Vorname) {

02 return suche2(0, AnzahlKunden - 1, Nachname, Vorname);

03 }

04

05 private int suche2(int a, int b, String Nachname, String Vorname) {

06 if (b < a)

07 return 0;

08 int m = (a + b) / 2;

09 if (Kunden[m].getNachname().equals(Nachname) &&

10 Kunden[m].getVorname().equals(Vorname))

11 return Kunden[m].getKundenNr();

12 if (Kunden[m].getNachname().compareTo(Nachname) > 0 ||

13 Kunden[m].getNachname().equals(Nachname) &&

14 Kunden[m].getVorname().compareTo(Vorname) > 0)

15 return suche2(a, m - 1, Nachname, Vorname);

16 else

17 return suche2(m + 1, b, Nachname, Vorname);

18 }

Aufgaben 1 und 2

1

Benennen Sie alle Komponenten der GUI in Material 1 und beschreiben Sie, welchem Zweck diese Komponenten jeweils dienen.

[4 BE]

2.1

Modellieren Sie das StadtRad-Ausleihsystem als UML-Klassendiagramm mit den Klassen Verwaltung, Station, Kunde und Rad unter Berücksichtigung folgender Aktionen, wobei nur für die Klasse Verwaltung eine detaillierte Modellierung mit Attributen und Methoden gefordert ist:

Registrieren eines neuen Kunden mit Nachname und Vorname

Ausleihen eines Rades an einer Station durch einen Kunden: Falls kein Rad mehr verfügbar ist, liefert die Methode den Wert 0, ansonsten wird die Radnummer zurückgegeben.

Rückgabe eines Rades an einer Station durch einen Kunden: Falls alle Stellplätze an der Station belegt sind, die Rückgabe also nicht möglich ist, wird false zurückgegeben.

[9 BE]

2.2

Beschreiben Sie Ihre Modellierung und gehen Sie dabei auch auf die Klassenbeziehungen ein.

[7 BE]

Ausleihsystem StadtRad

Eine Großstadt hat ein Ausleihsystem namens StadtRad für Fahrräder eingeführt. Nach dem Motto „Aufsteigen und losfahren“ soll für die Bürgerinnen und Bürger an zahlreichen Leihstationen im gesamten Stadtgebiet die Möglichkeit bestehen, ein Rad auszuleihen und dieses wieder an derselben oder einer anderen Station zurückzugeben. Jede Station verfügt dabei über Stellplätze, an denen die Räder angeschlossen werden. Die Anzahl der Stellplätze ist an jeder Station gleich.

Zur Verwaltung des StadtRad-Ausleihsystems

erhalten die Stationen eine eindeutige Stationsnummer,

muss jeder Kunde im System registriert sein; er ist dann über seine Kundennummer zu identifizieren,

verfügt jedes Rad über eine eindeutige Radnummer, die bei der Ausleihe beim Kunden eingetragen wird. Ist ein Rad gerade nicht verliehen, ist die Radnummer beim Stellplatz eingetragen, an dem das Rad angeschlossen ist.

Den Kunden wird eine App zur Verfügung gestellt, mit der sie sich im System registrieren, die Verfügbarkeit von Rädern an einer Station überprüfen sowie deren Ausleihe und Rückgabe durchführen können.

Material 1

GUI der StadtRad-App

Material 2

Klassendiagramm der Klasse Station

Material 3

Methode zurückgeben(...) der Klasse Verwaltung

01 public boolean zurückgeben(int KundenNr, int StationsNr) {

02 Kunde einKunde = gibKunde(KundenNr);

03 Station eineStation = gibStation(StationsNr);

04 if (einKunde != null && eineStation != null) {

05 int RadNr = einKunde.getAusgeliehenesRad();

06 if (eineStation.abstellen(RadNr) == true) {

07 einKunde.setAusgeliehenesRad(0);

08 einKunde.setEndzeit();

09 einKunde.berechneGebühren();

10 return true;

11 }

12 }

13 return false;

14 }

Material 4

Methoden suche(...) und suche2(...)

01 public int suche(String Nachname, String Vorname) {

02 return suche2(0, AnzahlKunden - 1, Nachname, Vorname);

03 }

04

05 private int suche2(int a, int b, String Nachname, String Vorname) {

06 if (b < a)

07 return 0;

08 int m = (a + b) / 2;

09 if (Kunden[m].getNachname().equals(Nachname) &&

10 Kunden[m].getVorname().equals(Vorname))

11 return Kunden[m].getKundenNr();

12 if (Kunden[m].getNachname().compareTo(Nachname) > 0 ||

13 Kunden[m].getNachname().equals(Nachname) &&

14 Kunden[m].getVorname().compareTo(Vorname) > 0)

15 return suche2(a, m - 1, Nachname, Vorname);

16 else

17 return suche2(m + 1, b, Nachname, Vorname);

18 }

3.1

Beschreiben Sie das UML-Diagramm der Klasse Station in Material 2.

[5 BE]

Ausleihsystem StadtRad

Eine Großstadt hat ein Ausleihsystem namens StadtRad für Fahrräder eingeführt. Nach dem Motto „Aufsteigen und losfahren“ soll für die Bürgerinnen und Bürger an zahlreichen Leihstationen im gesamten Stadtgebiet die Möglichkeit bestehen, ein Rad auszuleihen und dieses wieder an derselben oder einer anderen Station zurückzugeben. Jede Station verfügt dabei über Stellplätze, an denen die Räder angeschlossen werden. Die Anzahl der Stellplätze ist an jeder Station gleich.

Zur Verwaltung des StadtRad-Ausleihsystems

erhalten die Stationen eine eindeutige Stationsnummer,

muss jeder Kunde im System registriert sein; er ist dann über seine Kundennummer zu identifizieren,

verfügt jedes Rad über eine eindeutige Radnummer, die bei der Ausleihe beim Kunden eingetragen wird. Ist ein Rad gerade nicht verliehen, ist die Radnummer beim Stellplatz eingetragen, an dem das Rad angeschlossen ist.

Den Kunden wird eine App zur Verfügung gestellt, mit der sie sich im System registrieren, die Verfügbarkeit von Rädern an einer Station überprüfen sowie deren Ausleihe und Rückgabe durchführen können.

Material 1

GUI der StadtRad-App

Material 2

Klassendiagramm der Klasse Station

Material 3

Methode zurückgeben(...) der Klasse Verwaltung

01 public boolean zurückgeben(int KundenNr, int StationsNr) {

02 Kunde einKunde = gibKunde(KundenNr);

03 Station eineStation = gibStation(StationsNr);

04 if (einKunde != null && eineStation != null) {

05 int RadNr = einKunde.getAusgeliehenesRad();

06 if (eineStation.abstellen(RadNr) == true) {

07 einKunde.setAusgeliehenesRad(0);

08 einKunde.setEndzeit();

09 einKunde.berechneGebühren();

10 return true;

11 }

12 }

13 return false;

14 }

Material 4

Methoden suche(...) und suche2(...)

01 public int suche(String Nachname, String Vorname) {

02 return suche2(0, AnzahlKunden - 1, Nachname, Vorname);

03 }

04

05 private int suche2(int a, int b, String Nachname, String Vorname) {

06 if (b < a)

07 return 0;

08 int m = (a + b) / 2;

09 if (Kunden[m].getNachname().equals(Nachname) &&

10 Kunden[m].getVorname().equals(Vorname))

11 return Kunden[m].getKundenNr();

12 if (Kunden[m].getNachname().compareTo(Nachname) > 0 ||

13 Kunden[m].getNachname().equals(Nachname) &&

14 Kunden[m].getVorname().compareTo(Vorname) > 0)

15 return suche2(a, m - 1, Nachname, Vorname);

16 else

17 return suche2(m + 1, b, Nachname, Vorname);

18 }

3.2

Implementieren Sie den Konstruktor der Klasse Station. Er soll unter anderem alle Stellplätze mit 0 initialisieren. (4 BE)

public Station(int StationsNr) {

}

3.3

Analysieren Sie die Methode zurückgeben(...) der Klasse Verwaltung in Material 3. Dabei ordnet die Methode abstellen(...) einem Stellplatz einer Station ein Rad zu, falls dort noch ein Stellplatz frei ist. (7 BE)

3.4

Implementieren Sie die Methode abstellen(...) der Klasse Station, die folgende Aufgaben erledigen soll:

Es wird überprüft, ob sich an der Station noch ein freier Stellplatz zum Abstellen befindet.

Wird ein freier Stellplatz ermittelt, wird bei diesem die Radnummer eingetragen und der Wert true zurückgegeben.

Ansonsten wird der Wert false zurückgegeben.

[7 BE]

public boolean abstellen(int RadNr) {

}

Ausleihsystem StadtRad

Eine Großstadt hat ein Ausleihsystem namens StadtRad für Fahrräder eingeführt. Nach dem Motto „Aufsteigen und losfahren“ soll für die Bürgerinnen und Bürger an zahlreichen Leihstationen im gesamten Stadtgebiet die Möglichkeit bestehen, ein Rad auszuleihen und dieses wieder an derselben oder einer anderen Station zurückzugeben. Jede Station verfügt dabei über Stellplätze, an denen die Räder angeschlossen werden. Die Anzahl der Stellplätze ist an jeder Station gleich.

Zur Verwaltung des StadtRad-Ausleihsystems

erhalten die Stationen eine eindeutige Stationsnummer,

muss jeder Kunde im System registriert sein; er ist dann über seine Kundennummer zu identifizieren,

verfügt jedes Rad über eine eindeutige Radnummer, die bei der Ausleihe beim Kunden eingetragen wird. Ist ein Rad gerade nicht verliehen, ist die Radnummer beim Stellplatz eingetragen, an dem das Rad angeschlossen ist.

Den Kunden wird eine App zur Verfügung gestellt, mit der sie sich im System registrieren, die Verfügbarkeit von Rädern an einer Station überprüfen sowie deren Ausleihe und Rückgabe durchführen können.

Material 1

GUI der StadtRad-App

Material 2

Klassendiagramm der Klasse Station

Material 3

Methode zurückgeben(...) der Klasse Verwaltung

01 public boolean zurückgeben(int KundenNr, int StationsNr) {

02 Kunde einKunde = gibKunde(KundenNr);

03 Station eineStation = gibStation(StationsNr);

04 if (einKunde != null && eineStation != null) {

05 int RadNr = einKunde.getAusgeliehenesRad();

06 if (eineStation.abstellen(RadNr) == true) {

07 einKunde.setAusgeliehenesRad(0);

08 einKunde.setEndzeit();

09 einKunde.berechneGebühren();

10 return true;

11 }

12 }

13 return false;

14 }

Material 4

Methoden suche(...) und suche2(...)

01 public int suche(String Nachname, String Vorname) {

02 return suche2(0, AnzahlKunden - 1, Nachname, Vorname);

03 }

04

05 private int suche2(int a, int b, String Nachname, String Vorname) {

06 if (b < a)

07 return 0;

08 int m = (a + b) / 2;

09 if (Kunden[m].getNachname().equals(Nachname) &&

10 Kunden[m].getVorname().equals(Vorname))

11 return Kunden[m].getKundenNr();

12 if (Kunden[m].getNachname().compareTo(Nachname) > 0 ||

13 Kunden[m].getNachname().equals(Nachname) &&

14 Kunden[m].getVorname().compareTo(Vorname) > 0)

15 return suche2(a, m - 1, Nachname, Vorname);

16 else

17 return suche2(m + 1, b, Nachname, Vorname);

18 }

4

Für die Kundenbetreuung sollen die Kunden nach den Nachnamen sortiert werden. Bei gleichem Nachnamen soll als zusätzliches Sortierkriterium der Vorname hinzugenommen werden. Implementieren Sie einen Sortieralgorithmus für die im Feld Kunden der Klasse Verwaltung gespeicherten Kunden.

Programmierhinweis

public int compareTo(String anotherString)

String1.compareTo(String2) vergleicht String1 mit String2. Das Ergebnis ist kleiner als 0, falls String1 lexikographisch vor String2 kommt, und größer als 0, falls String1 lexikographisch nach String2 kommt. Falls die beiden Strings gleich sind, ist das Ergebnis 0.

5

Analysieren Sie die in Material 4 dargestellten Methoden zum Suchen.

Videoportal

Eine Internet-Plattform für Umweltaktivitäten möchte ihr Online-Angebot um ein Video-Portal ergänzen. Alle Nutzer sollen die Möglichkeit erhalten, eigene Videoclips hochzuladen. Dafür soll ein Datenbankserver mit einem relationalen Datenbanksystem zum Einsatz kommen.

Alle Nutzer sollen sich über ein eindeutiges Pseudonym mit einem Passwort anmelden, um Zugriff auf die Inhalte des Portals zu erhalten. Darüber hinaus werden auch eine E-Mail-Adresse und das Geburtsdatum des Nutzers verlangt. Möchte der Nutzer Videoclips hochladen, muss er zunächst mindestens einen Videokanal mit einer eindeutigen Bezeichnung erstellen. Videoclips sind immer einem Videokanal zugeordnet. Zum Videokanal werden das Erstelldatum gespeichert und eine Kanalinfo, damit die anderen Nutzer sich darüber informieren können, zu welchem thematischen Schwerpunkt Videoclips in diesem Kanal zu finden sind. Die Nutzer können die Videokanäle abonnieren, um beim Einloggen über das neueste Upload-Material auf dem Laufenden gehalten zu werden.

Die Videokanäle enthalten dann thematisch zugeordnete Videoclips, von denen eine eindeutige ID, der Titel, die Laufzeit und das Uploaddatum gespeichert werden. Videoclips können von allen Nutzern mit einem bis fünf Sternen bewertet werden.

Um die Suche nach passenden Inhalten zu optimieren, können gesuchte Videoclips über eine Schlagwortsuche eingegrenzt werden. Dabei kann jeder Videoclip über mehrere Schlagworte gefunden werden. In Material 1 ist das unvollständige Diagramm zum Video-Portal dargestellt.

Material 1

Unvollständiges ER-Diagramm zum Videoportal

Material 2

Die Tabelle Kanal-Nutzer

Bezeichnung · Kanalinfo · Erstelldatum · Pseudonym · Passwort · EMail · Geburtsdatum

Antarktis · Leben in der Antarktis · 2017-07-01 · Robert · 54321 · ro@gmail.com · 1976-02-03

Klimawandel · Übers Klima · 2012-04-06 · Annalena · 12345 · al@gmx.de · 1989-09-02

Regenwald · Lateinamerikas Regenwälder · 2018-09-25 · Udo · 56789 · udo@gmx.com · 1999-08-23

Weltmeere · Verschmutzung der Meere · 2015-01-29 · Gretchen2001 · 23456 · gr2001@gmail.de · 2001-04-05

Luftverschmutzung · Neueste Daten · 2014-03-23 · Robert · 54321 · ro@gmail.com · 1976-02-03

Aufgaben

1.1

Erläutern Sie die angegebenen Kardinalitäten und Optionalitäten des Beziehungstyps markiert_mit (Material 1).

[2 BE]

1.2

Modellieren Sie für das Video-Portal entsprechend den Vorgaben eine Datenbank als Erweiterung des ER-Diagramms in Material 1 unter Angabe der Kardinalitäten und Optionalitäten.

[5 BE]

1.3

Erläutern Sie den Unterschied zwischen den Begriffen „Entität“ und „Entitätstyp“ im Kontext Nutzer.

[3 BE]

2

In Material 2 befindet sich ein anderer Ansatz der Datenbank in Form der Tabelle Kanal-Nutzer. Modellieren Sie das ER-Diagramm, von dem die Überführungsregeln zur gegebenen Relation führen.

[3 BE]

3.1

Überführen Sie Ihr ER-Diagramm aus Aufgabe 1.2 in ein optimiertes Relationenmodell und kennzeichnen Sie darin die Primär- und Fremdschlüssel.

[3 BE]

3.2

Erklären Sie die Funktion von Primär- und Fremdschlüsseln in einer Relation.

[2 BE]

Videoportal

Eine Internet-Plattform für Umweltaktivitäten möchte ihr Online-Angebot um ein Video-Portal ergänzen. Alle Nutzer sollen die Möglichkeit erhalten, eigene Videoclips hochzuladen. Dafür soll ein Datenbankserver mit einem relationalen Datenbanksystem zum Einsatz kommen.

Alle Nutzer sollen sich über ein eindeutiges Pseudonym mit einem Passwort anmelden, um Zugriff auf die Inhalte des Portals zu erhalten. Darüber hinaus werden auch eine E-Mail-Adresse und das Geburtsdatum des Nutzers verlangt. Möchte der Nutzer Videoclips hochladen, muss er zunächst mindestens einen Videokanal mit einer eindeutigen Bezeichnung erstellen. Videoclips sind immer einem Videokanal zugeordnet. Zum Videokanal werden das Erstelldatum gespeichert und eine Kanalinfo, damit die anderen Nutzer sich darüber informieren können, zu welchem thematischen Schwerpunkt Videoclips in diesem Kanal zu finden sind. Die Nutzer können die Videokanäle abonnieren, um beim Einloggen über das neueste Upload-Material auf dem Laufenden gehalten zu werden.

Die Videokanäle enthalten dann thematisch zugeordnete Videoclips, von denen eine eindeutige ID, der Titel, die Laufzeit und das Uploaddatum gespeichert werden. Videoclips können von allen Nutzern mit einem bis fünf Sternen bewertet werden.

Um die Suche nach passenden Inhalten zu optimieren, können gesuchte Videoclips über eine Schlagwortsuche eingegrenzt werden. Dabei kann jeder Videoclip über mehrere Schlagworte gefunden werden. In Material 1 ist das unvollständige Diagramm zum Video-Portal dargestellt.

Material 1

Unvollständiges ER-Diagramm zum Videoportal

Material 2

Die Tabelle Kanal-Nutzer

Bezeichnung · Kanalinfo · Erstelldatum · Pseudonym · Passwort · EMail · Geburtsdatum

Antarktis · Leben in der Antarktis · 2017-07-01 · Robert · 54321 · ro@gmail.com · 1976-02-03

Klimawandel · Übers Klima · 2012-04-06 · Annalena · 12345 · al@gmx.de · 1989-09-02

Regenwald · Lateinamerikas Regenwälder · 2018-09-25 · Udo · 56789 · udo@gmx.com · 1999-08-23

Weltmeere · Verschmutzung der Meere · 2015-01-29 · Gretchen2001 · 23456 · gr2001@gmail.de · 2001-04-05

Luftverschmutzung · Neueste Daten · 2014-03-23 · Robert · 54321 · ro@gmail.com · 1976-02-03

Aufgabe 4

Implementieren Sie SQL-Anweisungen für die folgenden Abfragen:

4.1

Es soll die durchschnittliche Bewertung aller Videoclips ausgegeben werden. (1 BE)

4.2

Titel, Laufzeit und Uploaddatum aller Videoclips des Kanals „Antarktis“ sollen ausgegeben werden. Die zuletzt hochgeladenen Videoclips sollen zuerst angezeigt und danach absteigend sortiert werden. (3 BE)

4.3

Es sollen Anzahl und Gesamtlänge der Videoclips angezeigt werden, die von dem Nutzer „Robert“ hochgeladen wurden. (3 BE)

4.4

Ausgabe von ID, Titel und Durchschnittsbewertung der Videoclips mit dem Schlagwort „Klimawandel“, absteigend nach der Durchschnittsbewertung sortiert. (4 BE)

Aufgabe 5

Erläutern Sie den Aufbau und die inhaltliche Bedeutung der folgenden SQL-Anweisungen:

5.1

SELECT DISTINCT Titel

FROM bewertet, Videoclip

WHERE bewertet.ID = Videoclip.ID

AND Sterne > 4

[2 BE]

5.2

SELECT Kanal.Bezeichnung, Kanal.Pseudonym, Videoclip.Titel

FROM Kanal, Videoclip, bewertet

WHERE bewertet.ID = Videoclip.ID

AND Kanal.Bezeichnung = Videoclip.Bezeichnung

AND bewertet.Pseudonym = 'Udo'

[3 BE]

5.3

SELECT Pseudonym, SUM(Laufzeit) AS Summe

FROM bewertet, Videoclip

WHERE bewertet.ID = Videoclip.ID

GROUP BY Pseudonym

[3 BE]

Aufgabe 6

Erläutern Sie, welche Auswirkungen das Weglassen der Gruppierung in Aufgabe 5.3 auf das Ergebnis der SQL-Anweisung hätte. (3 BE)

Schachfiguren

Die erlaubten Züge einer Schachfigur auf einem Schachbrett können mit den Zeichen n, e, s, w (für north, east, south und west) beschrieben werden.

Schachfiguren bezeichnen wir mit P, T und K (für Pferd, Turm und König).

Das Pferd zieht immer zuerst zwei Felder nach Norden, Süden, Osten oder Westen und anschließend ein Feld senkrecht zu dieser Richtung (siehe Abbildung).

Ein Zug beginnt immer mit dem Zeichen für die Figur, danach folgen ein oder mehrere Zeichen für die Richtung. Zur Vereinfachung muss in keiner Aufgabe berücksichtigt werden, ob eine Schachfigur in einem Zug oder einer Zugfolge das Brett verlässt.

Material 1

Mögliche Züge eines Turms

Material 2

Akzeptor für Zugfolgen des Königs

$\Sigma = \{\text{K, n, s, e, w}\}$

$Z = \{z_0, \dots, z_{13}\}$

Startzustand $z_0$

$E = \{z_2, \dots, z_{13}\}$

$\delta\colon Z \times \Sigma \to Z$ gegeben durch folgende Übergangstabelle:

· K · n · e · s · w

$z_0$ · $z_1$

$z_1$ · · $z_2$ · $z_5$ · $z_8$ · $z_{11}$

$z_2$ · $z_1$ · · $z_3$ · · $z_4$

$z_3$ · $z_1$

$z_4$ · $z_1$

$z_5$ · $z_1$ · $z_6$ · · $z_7$

$z_6$ · $z_1$

$z_7$ · $z_1$

$z_8$ · $z_1$ · · $z_9$ · · $z_{10}$

$z_9$ · $z_1$

$z_{10}$ · $z_1$

$z_{11}$ · $z_1$ · $z_{12}$ · · $z_{13}$

$z_{12}$ · $z_1$

$z_{13}$ · $z_1$

1 Den dargestellten Zug (Abbildung) kann man mit Pnnw (Pferd zieht zweimal nach Norden und dann nach Westen) beschreiben. Pees oder Pwws sind ebenfalls gültige Züge. Nach jedem Zug kann ein weiterer Zug mit einer beliebigen Figur stattfinden. Mehrere Züge bilden eine Zugfolge.

1.1

Entscheiden Sie, ob PnnwPsswPeen und PwwnPeesPwwePeen gültige Zugfolgen sind. [3 BE]

1.3

Analysieren Sie die Sprache, die durch folgenden regulären Ausdruck definiert wird: [4 BE]

(P((nn|ss)(e|w)|((ee|ww)(n|s))))+

1.4

Entwerfen Sie eine Grammatik, welche die Sprache der gültigen Zugfolgen für das Pferd erzeugt. [6 BE]

1.5

Geben Sie für Ihre in Aufgabe 1.4 entworfene Grammatik den Ableitungsbaum für das Wort PnnePnnwPeen an. [4 BE]

Schachfiguren

Die erlaubten Züge einer Schachfigur auf einem Schachbrett können mit den Zeichen n, e, s, w (für north, east, south und west) beschrieben werden.

Schachfiguren bezeichnen wir mit P, T und K (für Pferd, Turm und König).

Das Pferd zieht immer zuerst zwei Felder nach Norden, Süden, Osten oder Westen und anschließend ein Feld senkrecht zu dieser Richtung (siehe Abbildung).

Ein Zug beginnt immer mit dem Zeichen für die Figur, danach folgen ein oder mehrere Zeichen für die Richtung. Zur Vereinfachung muss in keiner Aufgabe berücksichtigt werden, ob eine Schachfigur in einem Zug oder einer Zugfolge das Brett verlässt.

Material 1

Mögliche Züge eines Turms

Material 2

Akzeptor für Zugfolgen des Königs

$\Sigma = \{\text{K, n, s, e, w}\}$

$Z = \{z_0, \dots, z_{13}\}$

Startzustand $z_0$

$E = \{z_2, \dots, z_{13}\}$

$\delta\colon Z \times \Sigma \to Z$ gegeben durch folgende Übergangstabelle:

· K · n · e · s · w

$z_0$ · $z_1$

$z_1$ · · $z_2$ · $z_5$ · $z_8$ · $z_{11}$

$z_2$ · $z_1$ · · $z_3$ · · $z_4$

$z_3$ · $z_1$

$z_4$ · $z_1$

$z_5$ · $z_1$ · $z_6$ · · $z_7$

$z_6$ · $z_1$

$z_7$ · $z_1$

$z_8$ · $z_1$ · · $z_9$ · · $z_{10}$

$z_9$ · $z_1$

$z_{10}$ · $z_1$

$z_{11}$ · $z_1$ · $z_{12}$ · · $z_{13}$

$z_{12}$ · $z_1$

$z_{13}$ · $z_1$

1.2 Entwerfen Sie einen Akzeptor für die Sprache der gültigen Züge des Pferdes. [6 BE]

Schachfiguren

Die erlaubten Züge einer Schachfigur auf einem Schachbrett können mit den Zeichen n, e, s, w (für north, east, south und west) beschrieben werden.

Schachfiguren bezeichnen wir mit P, T und K (für Pferd, Turm und König).

Das Pferd zieht immer zuerst zwei Felder nach Norden, Süden, Osten oder Westen und anschließend ein Feld senkrecht zu dieser Richtung (siehe Abbildung).

Ein Zug beginnt immer mit dem Zeichen für die Figur, danach folgen ein oder mehrere Zeichen für die Richtung. Zur Vereinfachung muss in keiner Aufgabe berücksichtigt werden, ob eine Schachfigur in einem Zug oder einer Zugfolge das Brett verlässt.

Material 1

Mögliche Züge eines Turms

Material 2

Akzeptor für Zugfolgen des Königs

$\Sigma = \{\text{K, n, s, e, w}\}$

$Z = \{z_0, \dots, z_{13}\}$

Startzustand $z_0$

$E = \{z_2, \dots, z_{13}\}$

$\delta\colon Z \times \Sigma \to Z$ gegeben durch folgende Übergangstabelle:

· K · n · e · s · w

$z_0$ · $z_1$

$z_1$ · · $z_2$ · $z_5$ · $z_8$ · $z_{11}$

$z_2$ · $z_1$ · · $z_3$ · · $z_4$

$z_3$ · $z_1$

$z_4$ · $z_1$

$z_5$ · $z_1$ · $z_6$ · · $z_7$

$z_6$ · $z_1$

$z_7$ · $z_1$

$z_8$ · $z_1$ · · $z_9$ · · $z_{10}$

$z_9$ · $z_1$

$z_{10}$ · $z_1$

$z_{11}$ · $z_1$ · $z_{12}$ · · $z_{13}$

$z_{12}$ · $z_1$

$z_{13}$ · $z_1$

2 Der Turm (Zeichen T) läuft in einem Zug beliebig viele (mindestens 1 und maximal 7) Felder nach Norden, Süden, Osten oder Westen (Material 1).

Geben Sie einen regulären Ausdruck an, welcher die Sprache der gültigen Zugfolgen der Figuren Pferd und Turm erzeugt.

Schachfiguren

Die erlaubten Züge einer Schachfigur auf einem Schachbrett können mit den Zeichen n, e, s, w (für north, east, south und west) beschrieben werden.

Schachfiguren bezeichnen wir mit P, T und K (für Pferd, Turm und König).

Das Pferd zieht immer zuerst zwei Felder nach Norden, Süden, Osten oder Westen und anschließend ein Feld senkrecht zu dieser Richtung (siehe Abbildung).

Ein Zug beginnt immer mit dem Zeichen für die Figur, danach folgen ein oder mehrere Zeichen für die Richtung. Zur Vereinfachung muss in keiner Aufgabe berücksichtigt werden, ob eine Schachfigur in einem Zug oder einer Zugfolge das Brett verlässt.

Material 1

Mögliche Züge eines Turms

Material 2

Akzeptor für Zugfolgen des Königs

$\Sigma = \{\text{K, n, s, e, w}\}$

$Z = \{z_0, \dots, z_{13}\}$

Startzustand $z_0$

$E = \{z_2, \dots, z_{13}\}$

$\delta\colon Z \times \Sigma \to Z$ gegeben durch folgende Übergangstabelle:

· K · n · e · s · w

$z_0$ · $z_1$

$z_1$ · · $z_2$ · $z_5$ · $z_8$ · $z_{11}$

$z_2$ · $z_1$ · · $z_3$ · · $z_4$

$z_3$ · $z_1$

$z_4$ · $z_1$

$z_5$ · $z_1$ · $z_6$ · · $z_7$

$z_6$ · $z_1$

$z_7$ · $z_1$

$z_8$ · $z_1$ · · $z_9$ · · $z_{10}$

$z_9$ · $z_1$

$z_{10}$ · $z_1$

$z_{11}$ · $z_1$ · $z_{12}$ · · $z_{13}$

$z_{12}$ · $z_1$

$z_{13}$ · $z_1$

Der endliche Automat in Material 2 akzeptiert gültige Zugfolgen des Königs.

3.1

Erläutern Sie anhand der Übergangstabelle in Material 2 die Zugweise des Königs. (3 BE)

3.2

Begründen Sie anhand eines Beispiels, dass sich die Anzahl der Zustände des Automaten reduzieren lässt. (3 BE)

3.3

Entwickeln Sie aus dem Automaten in Material 2 einen vereinfachten Automaten mit möglichst wenigen Zuständen, indem Sie dessen Übergangstabelle und Zustandsgraphen angeben. (7 BE)

Olympische Winterspiele

Bei den Olympischen Winterspielen werden einheitlich strukturierte Sportlerdatenlisten angelegt, um Informationen über die Athleten zu speichern. Eine solche Liste beginnt mit dem Namen (n) des Sportlers gefolgt vom Land (l), für das der Sportler antritt. Jeder Sportler nimmt an genau einer Sportart (s) teil, die im Anschluss an das Land gespeichert wird. Wenn ein Sportler bei einer oder mehreren Disziplinen innerhalb einer Sportart zum Wettkampf antritt, stehen im Anschluss eine oder mehrere Disziplinbezeichnungen (d) mit den jeweils erzielten Ergebnissen (e) in den verschiedenen Wettkampfrunden. Die Rundenanzahl ist dabei auf maximal drei begrenzt, eine Runde findet in jedem Fall statt.

Während der Winterspiele werden täglich einige Athleten zufällig ausgewählt, denen eine Dopingprobe entnommen wird. Dabei kann es jeden Athleten mehrfach treffen, einige werden unter Umständen auch gar nicht geprüft. Die Ergebnisse der Dopingproben (p) werden am Ende der Liste gespeichert. Eine Dopingprobe kann positiv oder negativ ausfallen, das Ergebnis steht hinter dem Datum der Durchführung der Dopingprobe, getrennt durch ein Leerzeichen. Eine Beispielsportlerdatenliste mit zugehöriger Listenstruktur befindet sich im Material 1.

Material 1

Beispielsportlerdatenliste mit zugehöriger Listenstruktur

Felix Altreuther

Deutschland

Ski Alpin

Slalom

0:01:57,03

0:01:53,97

Riesenslalom

0:02:14,34

20.02.2018 negativ

22.02.2018 positiv

Die Struktur dieser Liste ist nlsdeedepp.

Material 2

Syntaxdiagramme für Datum

Aufgaben

Die Sprache $L$ besteht aus den Wörtern, die gültige Strukturen von Sportlerdatenlisten angeben.

1.1

Entscheiden Sie, ob die drei Wörter nls, nlsde und nlsdeedeedeeedpp der Sprache $L$ angehören. [3 BE]

1.2

Geben Sie zwei weitere Wörter der Sprache $L$ an, die innerhalb dieser Aufgabe nicht als Wörter der Sprache vorgegeben werden. [1 BE]

2.1

Entwerfen Sie für die Sprache $L$ eine Grammatik $G(L)$. [7 BE]

2.2

Geben Sie eine Ableitung des Wortes nlsdeep anhand Ihrer Grammatik $G(L)$ an. [3 BE]

2.3

Entscheiden Sie, ob Ihre Grammatik $G(L)$ regulär oder kontextfrei ist. [2 BE]

Olympische Winterspiele

Bei den Olympischen Winterspielen werden einheitlich strukturierte Sportlerdatenlisten angelegt, um Informationen über die Athleten zu speichern. Eine solche Liste beginnt mit dem Namen (n) des Sportlers gefolgt vom Land (l), für das der Sportler antritt. Jeder Sportler nimmt an genau einer Sportart (s) teil, die im Anschluss an das Land gespeichert wird. Wenn ein Sportler bei einer oder mehreren Disziplinen innerhalb einer Sportart zum Wettkampf antritt, stehen im Anschluss eine oder mehrere Disziplinbezeichnungen (d) mit den jeweils erzielten Ergebnissen (e) in den verschiedenen Wettkampfrunden. Die Rundenanzahl ist dabei auf maximal drei begrenzt, eine Runde findet in jedem Fall statt.

Während der Winterspiele werden täglich einige Athleten zufällig ausgewählt, denen eine Dopingprobe entnommen wird. Dabei kann es jeden Athleten mehrfach treffen, einige werden unter Umständen auch gar nicht geprüft. Die Ergebnisse der Dopingproben (p) werden am Ende der Liste gespeichert. Eine Dopingprobe kann positiv oder negativ ausfallen, das Ergebnis steht hinter dem Datum der Durchführung der Dopingprobe, getrennt durch ein Leerzeichen. Eine Beispielsportlerdatenliste mit zugehöriger Listenstruktur befindet sich im Material 1.

Material 1

Beispielsportlerdatenliste mit zugehöriger Listenstruktur

Felix Altreuther

Deutschland

Ski Alpin

Slalom

0:01:57,03

0:01:53,97

Riesenslalom

0:02:14,34

20.02.2018 negativ

22.02.2018 positiv

Die Struktur dieser Liste ist nlsdeedepp.

Material 2

Syntaxdiagramme für Datum

Aufgabe 3

Modellieren Sie das Zustandsdiagramm eines endlichen Automaten, der genau die Sprache L akzeptiert. (7 BE)

Olympische Winterspiele

Bei den Olympischen Winterspielen werden einheitlich strukturierte Sportlerdatenlisten angelegt, um Informationen über die Athleten zu speichern. Eine solche Liste beginnt mit dem Namen (n) des Sportlers gefolgt vom Land (l), für das der Sportler antritt. Jeder Sportler nimmt an genau einer Sportart (s) teil, die im Anschluss an das Land gespeichert wird. Wenn ein Sportler bei einer oder mehreren Disziplinen innerhalb einer Sportart zum Wettkampf antritt, stehen im Anschluss eine oder mehrere Disziplinbezeichnungen (d) mit den jeweils erzielten Ergebnissen (e) in den verschiedenen Wettkampfrunden. Die Rundenanzahl ist dabei auf maximal drei begrenzt, eine Runde findet in jedem Fall statt.

Während der Winterspiele werden täglich einige Athleten zufällig ausgewählt, denen eine Dopingprobe entnommen wird. Dabei kann es jeden Athleten mehrfach treffen, einige werden unter Umständen auch gar nicht geprüft. Die Ergebnisse der Dopingproben (p) werden am Ende der Liste gespeichert. Eine Dopingprobe kann positiv oder negativ ausfallen, das Ergebnis steht hinter dem Datum der Durchführung der Dopingprobe, getrennt durch ein Leerzeichen. Eine Beispielsportlerdatenliste mit zugehöriger Listenstruktur befindet sich im Material 1.

Material 1

Beispielsportlerdatenliste mit zugehöriger Listenstruktur

Felix Altreuther

Deutschland

Ski Alpin

Slalom

0:01:57,03

0:01:53,97

Riesenslalom

0:02:14,34

20.02.2018 negativ

22.02.2018 positiv

Die Struktur dieser Liste ist nlsdeedepp.

Material 2

Syntaxdiagramme für Datum

4.1

Beschreiben Sie die Syntaxdiagramme für Datum (Material 2).

[3 BE]

4.2

Erläutern Sie den Aufbau der Wörter dieser Sprache, die durch die Syntaxdiagramme für Datum erzeugt werden.

[3 BE]

5

Zeichnen Sie Syntaxdiagramme für Sportlerdatenlisten (nicht für die Listenstruktur) (Material 1). Dabei sind die Nichtterminale Name, Land, Sportart, Disziplin und Datum als Nichtterminale nicht weiter aufzulösen.

[7 BE]

Hinweise:

Vereinfachend sollen als Ergebnisse nur Zeiten mit dem Format h:mm:ss,HH (Stunden, Minuten, Sekunden und Hundertstelsekunden) betrachtet werden.

Formatierungen durch Zeilenumbruch oder Einrückung sind nicht zu beachten.

6

Das Syntaxdiagramm Datum lässt Daten wie den 31.04.2018 oder den 29.02.2017 zu.

Erläutern Sie jeweils die Ursache und diskutieren Sie jeweils, inwiefern formale Sprachen zur Lösung dieser Probleme geeignet sind.

[4 BE]