Abitur Hessen Informatik 2021 · LK

Bogenschießen

Bei einem Volksfest soll ein Wettkampf im Bogenschießen stattfinden. Jeder Teilnehmer muss in drei Durchgängen je zehn Pfeile auf eine Scheibe schießen und dabei möglichst viele Ringe (als Trefferpunkte) erhalten. Die Ringe der einzelnen Durchgänge werden addiert.

Der Teilnehmer darf sich eine (noch nicht vergebene) Startnummer und einen Namen wählen, zudem wird die erreichte Zahl der Ringe gespeichert. Zu Beginn des Wettkampfes ist die Anzahl der Teilnehmer bekannt. Die Teilnehmer werden beim ersten Durchgang zusammen mit ihrer erreichten Anzahl von Ringen erfasst. Die Reihenfolge der Teilnehmer wird vor jedem Durchgang ausgelost.

Material 1

Quellcode der Klasse Ranking

01 public class Ranking {

02

03 private int AnzahlTeilnehmer;

04 private Teilnehmer[] dieTeilnehmer;

05

06 public Ranking(int AnzahlTeilnehmer) {

07 this.AnzahlTeilnehmer = AnzahlTeilnehmer;

08 dieTeilnehmer = new Teilnehmer[AnzahlTeilnehmer];

09 }

10

11 public int getAnzahlTeilnehmer() {

12 return AnzahlTeilnehmer;

13 }

14

15 public void fügeTeilnehmerHinzu(int Startnummer, String Name,

16 int AnzahlRinge) {

17 Teilnehmer einTeilnehmer = new Teilnehmer(Startnummer, Name);

18 aktualisiereRinge(einTeilnehmer, AnzahlRinge);

19 }

20

21 public Teilnehmer gibTeilnehmerAnStelle(int i) {

22 return dieTeilnehmer[i];

23 }

24

25 public void aktualisiereRinge(Teilnehmer einTeilnehmer, int neueRinge) {

26 einTeilnehmer.setAnzahlRinge(neueRinge + einTeilnehmer.getAnzahlRinge());

27 int i = 0, merke = 0;

28 while ((dieTeilnehmer[i] != null) && (einTeilnehmer.getAnzahlRinge() <=

29 dieTeilnehmer[i].getAnzahlRinge()))

30 i++;

31 if (dieTeilnehmer[i] != null) {

32 merke = i;

33 while ((dieTeilnehmer[i] != null) && (i < AnzahlTeilnehmer-1)) i++;

34 while (i > merke) {

35 dieTeilnehmer[i] = dieTeilnehmer[i-1];

36 i--;

37 }

38 }

39 dieTeilnehmer[i] = einTeilnehmer;

40 }

41

42 public void gibDieTeilnehmerAus() {

43... // gibt die aktuelle Ergebnisliste mit Namen und Startnummern aus

44 }

45 }

Aufgabe 1

Stellen Sie die Klasse Ranking (Material 1) und die Klasse Teilnehmer in einem UML-Klassendiagramm dar.

Erläutern Sie die Beziehung zwischen beiden Klassen. [5 BE]

a)

b)

Bogenschießen

Bei einem Volksfest soll ein Wettkampf im Bogenschießen stattfinden. Jeder Teilnehmer muss in drei Durchgängen je zehn Pfeile auf eine Scheibe schießen und dabei möglichst viele Ringe (als Trefferpunkte) erhalten. Die Ringe der einzelnen Durchgänge werden addiert.

Der Teilnehmer darf sich eine (noch nicht vergebene) Startnummer und einen Namen wählen, zudem wird die erreichte Zahl der Ringe gespeichert. Zu Beginn des Wettkampfes ist die Anzahl der Teilnehmer bekannt. Die Teilnehmer werden beim ersten Durchgang zusammen mit ihrer erreichten Anzahl von Ringen erfasst. Die Reihenfolge der Teilnehmer wird vor jedem Durchgang ausgelost.

Material 1

Quellcode der Klasse Ranking

01 public class Ranking {

02

03 private int AnzahlTeilnehmer;

04 private Teilnehmer[] dieTeilnehmer;

05

06 public Ranking(int AnzahlTeilnehmer) {

07 this.AnzahlTeilnehmer = AnzahlTeilnehmer;

08 dieTeilnehmer = new Teilnehmer[AnzahlTeilnehmer];

09 }

10

11 public int getAnzahlTeilnehmer() {

12 return AnzahlTeilnehmer;

13 }

14

15 public void fügeTeilnehmerHinzu(int Startnummer, String Name,

16 int AnzahlRinge) {

17 Teilnehmer einTeilnehmer = new Teilnehmer(Startnummer, Name);

18 aktualisiereRinge(einTeilnehmer, AnzahlRinge);

19 }

20

21 public Teilnehmer gibTeilnehmerAnStelle(int i) {

22 return dieTeilnehmer[i];

23 }

24

25 public void aktualisiereRinge(Teilnehmer einTeilnehmer, int neueRinge) {

26 einTeilnehmer.setAnzahlRinge(neueRinge + einTeilnehmer.getAnzahlRinge());

27 int i = 0, merke = 0;

28 while ((dieTeilnehmer[i] != null) && (einTeilnehmer.getAnzahlRinge() <=

29 dieTeilnehmer[i].getAnzahlRinge()))

30 i++;

31 if (dieTeilnehmer[i] != null) {

32 merke = i;

33 while ((dieTeilnehmer[i] != null) && (i < AnzahlTeilnehmer-1)) i++;

34 while (i > merke) {

35 dieTeilnehmer[i] = dieTeilnehmer[i-1];

36 i--;

37 }

38 }

39 dieTeilnehmer[i] = einTeilnehmer;

40 }

41

42 public void gibDieTeilnehmerAus() {

43... // gibt die aktuelle Ergebnisliste mit Namen und Startnummern aus

44 }

45 }

Aufgabe 2

2.1

Beschreiben Sie anhand des gegebenen Quelltextes in Material 1, wie die Teilnehmer in das Teilnehmerfeld aufgenommen und einsortiert werden. [5 BE]

2.2

Beurteilen Sie, inwiefern das implementierte Einfügeverfahren auch für die Erfassung der Durchgänge zwei und drei geeignet ist. [2 BE]

Als Alternative kann das Ranking in einem binären Suchbaum gespeichert werden (Material 2).

Material 2

Binärbaum mit Anzahl der Ringe als Sortierschlüssel nach dem ersten Durchgang

Material 3

Quellcode der Klassen Teilnehmerknoten und BinBaum

01 public class TeilnehmerKnoten {

02 // Die Klasse Teilnehmer ist wie in Aufgabenteil 1 definiert

03 private Teilnehmer derTeilnehmer;

04 private TeilnehmerKnoten Links, Rechts;

05

06 public TeilnehmerKnoten (Teilnehmer einTeilnehmer) {

07 derTeilnehmer = einTeilnehmer;

08 Links = null;

09 Rechts = null;

10 }

11... // die get- und set-Methoden können als gegeben angenommen werden

12 }

13

14 public class BinBaum {

15 private TeilnehmerKnoten Wurzel;

16 private int AnzahlTeilnehmer;

17 private Teilnehmer[] dieTeilnehmer;

18... // die verwendeten Methoden einfügen und löschen können als gegeben

19 // angenommen werden

20

21 public void optimiereBaum() {

22 überführeBaumNachFeld(Wurzel);

23 überführeFeldNachBaum(0, AnzahlTeilnehmer-1);

24 }

25

26 public void überführeBaumNachFeld(TeilnehmerKnoten einTeilnehmerKnoten) {

27 // siehe Aufgabe 4.1

28 }

29

30 public void überführeFeldNachBaum(int Anfang, int Ende) {

31 if (Anfang == Ende) {

32 einfügen(dieTeilnehmer[Anfang]);

33 } else if (Anfang < Ende) {

34 int pos = (Ende + Anfang) / 2;

35 einfügen(dieTeilnehmer[pos]);

36 überführeFeldNachBaum(Anfang, pos - 1);

37 überführeFeldNachBaum(pos + 1, Ende);

38 }

39 }

40 }

3.1

Stellen Sie die Klassen TeilnehmerKnoten und BinBaum (Material 3) in einem UML-Klassendiagramm dar und erläutern Sie die Beziehungen. Auf die Angabe der Methoden kann verzichtet werden.

[4 BE]

Als Alternative kann das Ranking in einem binären Suchbaum gespeichert werden (Material 2).

Material 2

Binärbaum mit Anzahl der Ringe als Sortierschlüssel nach dem ersten Durchgang

Material 3

Quellcode der Klassen Teilnehmerknoten und BinBaum

01 public class TeilnehmerKnoten {

02 // Die Klasse Teilnehmer ist wie in Aufgabenteil 1 definiert

03 private Teilnehmer derTeilnehmer;

04 private TeilnehmerKnoten Links, Rechts;

05

06 public TeilnehmerKnoten (Teilnehmer einTeilnehmer) {

07 derTeilnehmer = einTeilnehmer;

08 Links = null;

09 Rechts = null;

10 }

11... // die get- und set-Methoden können als gegeben angenommen werden

12 }

13

14 public class BinBaum {

15 private TeilnehmerKnoten Wurzel;

16 private int AnzahlTeilnehmer;

17 private Teilnehmer[] dieTeilnehmer;

18... // die verwendeten Methoden einfügen und löschen können als gegeben

19 // angenommen werden

20

21 public void optimiereBaum() {

22 überführeBaumNachFeld(Wurzel);

23 überführeFeldNachBaum(0, AnzahlTeilnehmer-1);

24 }

25

26 public void überführeBaumNachFeld(TeilnehmerKnoten einTeilnehmerKnoten) {

27 // siehe Aufgabe 4.1

28 }

29

30 public void überführeFeldNachBaum(int Anfang, int Ende) {

31 if (Anfang == Ende) {

32 einfügen(dieTeilnehmer[Anfang]);

33 } else if (Anfang < Ende) {

34 int pos = (Ende + Anfang) / 2;

35 einfügen(dieTeilnehmer[pos]);

36 überführeFeldNachBaum(Anfang, pos - 1);

37 überführeFeldNachBaum(pos + 1, Ende);

38 }

39 }

40 }

3.2

Geben Sie eine mögliche Reihenfolge an, in der die 13 Teilnehmer gestartet sein könnten. (2 BE)

3.3

Comanche darf den zweiten Durchgang beginnen und erreicht in diesem 37 Ringe. Danach folgt Amazone mit 48 Ringen.

Beschreiben Sie, wie der Knoten „Comanche“ aus dem vorliegenden Baum gelöscht und danach an der korrekten Stelle wieder eingefügt wird. Zeichnen Sie den Ergebnisbaum, nachdem die Ergebnisse von Comanche und Amazone eingetragen sind. (5 BE)

3.4

Im Verlauf des Turniers erhöht sich die Anzahl der Ringe für die einzelnen Teilnehmer.

Beschreiben Sie, wie der Baum beim zweiten und dritten Durchgang seine Gestalt verändert und was das für die Laufzeit des Einfügens, Löschens und Suchens von Teilnehmern im Baum bedeutet. (3 BE)

Als Alternative kann das Ranking in einem binären Suchbaum gespeichert werden (Material 2).

Material 2

Binärbaum mit Anzahl der Ringe als Sortierschlüssel nach dem ersten Durchgang

Material 3

Quellcode der Klassen Teilnehmerknoten und BinBaum

01 public class TeilnehmerKnoten {

02 // Die Klasse Teilnehmer ist wie in Aufgabenteil 1 definiert

03 private Teilnehmer derTeilnehmer;

04 private TeilnehmerKnoten Links, Rechts;

05

06 public TeilnehmerKnoten (Teilnehmer einTeilnehmer) {

07 derTeilnehmer = einTeilnehmer;

08 Links = null;

09 Rechts = null;

10 }

11... // die get- und set-Methoden können als gegeben angenommen werden

12 }

13

14 public class BinBaum {

15 private TeilnehmerKnoten Wurzel;

16 private int AnzahlTeilnehmer;

17 private Teilnehmer[] dieTeilnehmer;

18... // die verwendeten Methoden einfügen und löschen können als gegeben

19 // angenommen werden

20

21 public void optimiereBaum() {

22 überführeBaumNachFeld(Wurzel);

23 überführeFeldNachBaum(0, AnzahlTeilnehmer-1);

24 }

25

26 public void überführeBaumNachFeld(TeilnehmerKnoten einTeilnehmerKnoten) {

27 // siehe Aufgabe 4.1

28 }

29

30 public void überführeFeldNachBaum(int Anfang, int Ende) {

31 if (Anfang == Ende) {

32 einfügen(dieTeilnehmer[Anfang]);

33 } else if (Anfang < Ende) {

34 int pos = (Ende + Anfang) / 2;

35 einfügen(dieTeilnehmer[pos]);

36 überführeFeldNachBaum(Anfang, pos - 1);

37 überführeFeldNachBaum(pos + 1, Ende);

38 }

39 }

40 }

4 Um der Gestaltänderung des Baumes entgegenzuwirken, wird nach jedem Durchgang die Methode optimiereBaum() aufgerufen (Material 3).

4.1

Implementieren Sie die Methode überführeBaumNachFeld(...), die alle Teilnehmer aus dem Baum nach der Reihenfolge der erzielten Ringe in das Feld dieTeilnehmer überträgt und jeden Teilnehmer im Baum löscht, sobald er nicht mehr benötigt wird.

Hinweis: Die verwendeten Methoden einfügen(...) und löschen(...) können als gegeben angenommen werden.

[5 BE]

4.2

Analysieren Sie die Methode überführeFeldNachBaum(...) aus Material 3 und geben Sie an, welche Gestalt ein beliebiger Baum nach dem Aufruf von optimiereBaum() hat.

[4 BE]

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

1 Geben Sie in Bezug auf die Relationen in Material 1 und Material 2 Terme in der Relationenalgebra für folgende Abfragen an:

1.1

Ausgabe aller Gerätetypen und der von ihnen messbaren Parameter, die am 01.12.2018 an der Station mit der StationsID 2601 im Einsatz waren. (2 BE)

1.2

Ausgabe der Stationsnamen aller Stationen, bei denen schon einmal eine Messung im Rahmen des 10-Minuten-Werte-Programmes durchgeführt wurde, die mit einem Qualitätsniveau niedriger als 3 bewertet wurde. (2 BE)

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

2.1

Erläutern Sie den Aufbau und die inhaltliche Bedeutung des folgenden Terms der Relationenalgebra:

$$\pi_{\text{Messdatum}} (\pi_{\text{Messdatum}, \text{Messuhrzeit}, \text{TT\_10}}(\sigma_{\text{StationsID} = 1420}(\text{10\_min\_werte})) \bowtie \pi_{\text{Messdatum}, \text{Messuhrzeit}, \text{TT\_10}}(\sigma_{\text{StationsID} = 2601}(\text{10\_min\_werte})))$$

2.2

Begründen Sie, dass sich das Ergebnis aus 2.1 nicht ändert, wenn man den Natural-Join $\bowtie$ durch den Schnittoperator $\cap$ ersetzt.

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

Implementieren Sie SQL-Anweisungen für die folgenden Abfragen bzw. Anforderungen auf den Relationen in Material 1 und Material 2:

3.1

Für die Station mit der StationsID 1420 soll der Stationsname und der im Monat Dezember 2019 gemessene Höchstwert für den Luftdruck PP_10 ausgegeben werden.

3.2

In der Relation 10_min_werte soll für alle Messungen, die am 31.12.2019 an der Station mit der StationsID 1420 erfolgten, die Kennzahl für das Qualitätsniveau auf den Wert 3 gesetzt werden.

3.3

Für jeden Gerätetyp soll die Anzahl an Stationen, die diesen Typ schon einmal eingesetzt hat, ausgegeben werden. Dabei sollen nur solche Datensätze angezeigt werden, bei denen diese Anzahl mindestens 20 beträgt.

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

4.1

Begründen Sie, dass die Kombination der Attribute StationsID, vonDatum und Parameter ein möglicher Primärschlüssel der Relation Metadaten_Geraete ist.

4.2

Entscheiden Sie, in welcher Normalform sich die Relation Metadaten_Geraete befindet und überführen Sie die Relation in die dritte Normalform.

Beschreiben Sie Ihr Vorgehen.

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

Eine Messung nach dem 10_Minuten-Werte-Programm umfasst die Bestimmung der im Einleitungstext genannten Größen zu einem bestimmten Zeitpunkt (Uhrzeit und Datum) mit dem Qualitätsniveau und wird als 10-Minuten-Messung bezeichnet.

Modellieren Sie ein ER-Diagramm inklusive Kardinalitäten und Optionalitäten, das die Entitätstypen Station und 10-Minuten-Messung mit deren Attributen und dem Beziehungstyp zwischen diesen Entitätstypen umfasst.

Erläutern Sie den Zusammenhang Ihres ER-Diagramms mit dieser Relation:

10_min_werte ( ↑StationsID, Messdatum, Messuhrzeit, QN, PP_10, TT_10, TM5_10, RF_10, TD_10)

Klimadatenbank

Der Deutsche Wetterdienst (DWD) unterhält die relationale Datenbank MIRAKEL. In dieser Datenbank werden Wetterdaten zusammen mit den sie beschreibenden Metadaten verwaltet.

Automatisierte Messstationen führen unterschiedliche Messprogramme aus. Ein Messprogramm beschreibt, welche Daten wie und wann zu messen sind. Ein wichtiges Messprogramm ist das Programm 10-Minuten-Werte. In diesem Programm werden die folgenden Größen alle 10 Minuten gemessen und an MIRAKEL übertragen:

Größe · Einheit · Kodierung des Parameters in MIRAKEL

Luftdruck in Stationshöhe · hpa · PP_10

Momentane Temperatur in 2 m Höhe · °C · TT_10

Momentane Temperatur in 5 cm Höhe · °C · TM5_10

Relative Feuchte in 2 m Höhe · % · RF_10

Taupunkttemperatur in 2 m Höhe · °C · TD_10

Die Daten werden in MIRAKEL in der Relation 10_min_werte (Material 1) zusammen mit einer Kennzahl für das Qualitätsniveau (QN) gespeichert.

Über eine Webseite gestattet der DWD lesenden Zugriff auf die Relation 10_min_werte. Ergänzend kann man die Relation Metadaten_Geraete (Material 2) herunterladen, die Metadaten zu der Relation 10_min_werte enthält.

Material 1

Auszug aus der MIRAKEL-Relation 10_min_werte

StationsID · Messdatum · Messuhrzeit · QN · PP_10 · TT_10 · TM5_10 · RF_10 · TD_10

... ·... ·... ·... ·... ·... ·... ·... ·...

1420 · 2019-12-31 · 22:50:00 · 2 · 1023,5 · 0,3 · -1,5 · 88,3 · -1,4

... ·... ·... ·... ·... ·... ·... ·... ·...

2601 · 2019-12-31 · 22:50:00 · 3 · 935,2 · -3 · -3,4 · 97,5 · -3,3

2601 · 2019-12-31 · 23:00:00 · 5 · 935,3 · -3 · -3,3 · 98 · -3,3

2601 · 2019-12-31 · 23:10:00 · 3 · 935,2 · -2,9 · -3,6 · 97,2 · -3,3

2601 · 2019-12-31 · 23:20:00 · 3 · 935,2 · -2,8 · -3,5 · 97,3 · -3,2

... ·... ·... ·... ·... ·... ·... ·... ·...

Material 2

Auszug aus der Relation Metadaten_Geraete mit Metadaten zu Material 1

StationsID · Stationsname · vonDatum · bisDatum · Parameter · Geraetetyp · Messverfahren

... ·... ·... ·... ·... ·... ·...

1420 · Frankfurt/Main · 1992-10-02 · 2012-02-16 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

... ·... ·... ·... ·... ·... ·...

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2006-05-09 · RF_10 · HYGROMER MP100 · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2006-05-10 · 2015-03-22 · RF_10 · Feuchtesonde HMP45D · Feuchtemessung, elektr.

2601 · Kleiner Feldberg/Taunus · 2015-03-23 · 2020-02-04 · RF_10 · EE33 · monolith. Messzelle HMC1

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TD_10 · ComAir · Taupunktspiegel, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TM5_10 · PT 100 (Luft) · Temperaturmessung, elektr.

2601 · Kleiner Feldberg/Taunus · 1992-10-02 · 2020-02-04 · TT_10 · PT 100 (Luft) · Temperaturmessung, elektr.

... ·... ·... ·... ·... ·... ·...

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

6.1

CREATE TABLE 1_min_werte (

StationsID INT,

Messdatum DATE,

Messuhrzeit TIME,

QN INT,

RS_01 DOUBLE NOT NULL,

RS_IND_01 DOUBLE NOT NULL,

PRIMARY KEY (StationsID, Messdatum, Messuhrzeit),

FOREIGN KEY (StationsID) REFERENCES Station (StationsID)

)

6.2

GRANT SELECT

ON 1_min_werte

TO PUBLIC

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

Aufgabe 1

1.1

Erläutern Sie alle Beziehungstypen im dargestellten ER-Diagramm, die zwischen dem Entitätstyp Spieler und anderen Entitätstypen bestehen.

[3 BE]

1.2

Im ER-Diagramm wird die Kontaktperson des Vereins durch das Attribut Kontaktperson modelliert, in dem die Mitgliedsnummer der Kontaktperson gespeichert wird.

Diskutieren Sie diese Lösung und modellieren Sie im Material eine Alternative.

[3 BE]

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

Aufgabe 2

Modellieren Sie eine Erweiterung des ER-Diagramms im Material entsprechend der folgenden Angaben:

Jede Mannschaft gehört genau einer Liga an. Jede Liga wird mit einer Bezeichnung versehen. Diese Bezeichnungen sind jedoch nicht eindeutig, weshalb das zusätzliche Attribut Kürzel notwendig ist. Jede Liga hat einen verantwortlichen Staffelleiter, der zwar selbst nicht aktiv in einer Mannschaft spielen, aber zwingend in einem Verein gemeldet sein muss. Ein Staffelleiter darf nur eine Liga leiten.

Jede Mannschaft spielt gegen andere Mannschaften als Heim- und Gastmannschaft. Dabei wird für jede dieser Paarungen ein Datum, eine Uhrzeit, ein Ergebnis und der Austragungsort gespeichert.

[5 BE]

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

Aufgabe 3

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

[5 BE]

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

Aufgabe 4

Geben Sie für folgende Abfragen Terme in der Relationenalgebra an:

4.1

Gesucht werden alle Mannschaftsbezeichnungen des Vereins 'WS Taunus'.

[2 BE]

4.2

Gesucht sind Vorname und Nachname aller Vereinsmitglieder, die derzeit in keiner Mannschaft spielen.

[2 BE]

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

5 Erläutern Sie den Aufbau und die inhaltliche Bedeutung des folgenden Terms der Relationenalgebra:

$$\pi_{\text{Bezeichnung, Kürzel}}((\sigma_{\text{Name = 'UWF Frankfurt'}}(\text{Verein}) \bowtie_{\text{Nummer = Nummer}} \text{Mannschaft}) \bowtie \rho_{\text{Bezeichnung} \rightarrow \text{Ligabezeichnung}}(\pi_{\text{Kürzel, Bezeichnung}}(\text{Liga})))$$

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

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

6.1

Gesucht werden alle Spieler mit Vor- und Nachnamen, die mehr als 30 Punkte haben.

[2 BE]

6.2

Gesucht werden die Mannschaftsführer mit Nachname, Vorname, E-Mail-Adresse und Mannschaftsbezeichnung der Mannschaften 'UWF Frankfurt Herren' und 'WS Taunus Herren', sortiert nach den Nachnamen.

[3 BE]

Datenbank für Randsportarten

Vereine, die Randsportarten wie z. B. Unterwasser-Frisbee betreiben, besitzen oftmals keinen Dachverband, der Online-Plattformen oder Ergebnisdatenbanken zur Verfügung stellt. Eine Schülerfirma möchte daher eine Datenbank zur Verwaltung von Mitgliedern, Vereinen, deren Mannschaften und Spielern sowie den entsprechenden Spielbegegnungen entwerfen und diesen Vereinen zur Verfügung stellen. Der erste Entwurf der Datenbank in Form eines ER-Diagramms ist im Material angegeben.

Material

ER-Diagramm

7 Ein ortsansässiger Verein möchte eine eigene Datenbank erstellen, um seine Mitglieder und deren Mannschaftszugehörigkeiten zu verwalten. Darüber hinaus sollen noch Kontodaten gespeichert werden, um die Mitgliedsbeiträge verwalten zu können. Der Monatsbeitrag ist abhängig von der Kategorie des Vereinsmitglieds. Aktive Erwachsene zahlen 20 € (Kategorienummer 1), Minderjährige 10 € (Kategorienummer 2) und passive Mitglieder 5 € (Kategorienummer 3). Ein Vorstandsmitglied trifft folgende Aussage zur benötigten Datenbank: „Für unsere Zwecke ist es ausreichend und absolut unproblematisch, lediglich die folgenden zwei Relationen zu verwenden“:

Mitglied (Vorname, Nachname, Mitgliedsnummer, E-Mail, StraßeNr, PLZ, Ort, Mannschaft)

Beitrag (Mitgliedsnummer, IBAN, Kategorienummer, Kategoriebezeichnung, Monatsbeitrag)

7.1

Nennen Sie die Primärschlüssel der beiden Relationen und begründen Sie Ihre Wahl. [1 BE]

7.2

Nehmen Sie, im Hinblick auf die vom Vorstandsmitglied vorgeschlagenen Relationen, Stellung zu der Aussage „...absolut unproblematisch...“, indem Sie auf zwei mögliche Anomalien eingehen. [3 BE]

7.3

Entscheiden Sie, in welcher Normalform sich diese Relationen befinden. [3 BE]

LilyPond

LilyPond ist ein Notensatzprogramm. Es wandelt Buchstaben und Zeichen, die in Textform eingegeben werden, in grafisch gesetzte Musiknoten um.

Beispiel:

Die Eingabe von c d e f g a b <g e c> führt zu folgendem Ergebnis:

Hierbei gilt:

Die Noten heißen a, b, c, d, e, f, g (nach englischem Standard wird b anstatt h verwendet).

Mehrere gleichzeitig zu spielende Noten (Akkord) werden in <> geklammert.

Die sogenannte Dreitonmusik besteht aus beliebig oft aufeinander folgenden Permutationen der Noten a, b und c, wobei jede Note in einer Permutation genau einmal vorkommt, z. B. abc oder cba. Die Sprache der Dreitonmusik sei $L_3$. Das leere Wort ist kein Element von $L_3$.

1.1

Geben Sie an, ob es sich bei den folgenden Worten um Worte der Sprache $L_3$ handelt. [2 BE]

1.3

Geben Sie einen regulären Ausdruck für die Sprache $L_3$ an. [2 BE]

LilyPond

LilyPond ist ein Notensatzprogramm. Es wandelt Buchstaben und Zeichen, die in Textform eingegeben werden, in grafisch gesetzte Musiknoten um.

Beispiel:

Die Eingabe von c d e f g a b <g e c> führt zu folgendem Ergebnis:

Hierbei gilt:

Die Noten heißen a, b, c, d, e, f, g (nach englischem Standard wird b anstatt h verwendet).

Mehrere gleichzeitig zu spielende Noten (Akkord) werden in <> geklammert.

Die sogenannte Dreitonmusik besteht aus beliebig oft aufeinander folgenden Permutationen der Noten a, b und c, wobei jede Note in einer Permutation genau einmal vorkommt, z. B. abc oder cba. Die Sprache der Dreitonmusik sei $L_3$. Das leere Wort ist kein Element von $L_3$.

1.2

Modellieren Sie das Zustandsdiagramm eines Akzeptors für die Sprache $L_3$.

LilyPond

LilyPond ist ein Notensatzprogramm. Es wandelt Buchstaben und Zeichen, die in Textform eingegeben werden, in grafisch gesetzte Musiknoten um.

Beispiel:

Die Eingabe von c d e f g a b <g e c> führt zu folgendem Ergebnis:

Hierbei gilt:

Die Noten heißen a, b, c, d, e, f, g (nach englischem Standard wird b anstatt h verwendet).

Mehrere gleichzeitig zu spielende Noten (Akkord) werden in <> geklammert.

Die sogenannte Dreitonmusik besteht aus beliebig oft aufeinander folgenden Permutationen der Noten a, b und c, wobei jede Note in einer Permutation genau einmal vorkommt, z. B. abc oder cba. Die Sprache der Dreitonmusik sei $L_3$. Das leere Wort ist kein Element von $L_3$.

Material 1: Grammatik für Aufgabe 2

$N = \{S\}$

$T = \{a, b, c\}$

Startsymbol $= S$

$P = \{S \to aSbScS \mid aScSbS \mid bSaScS \mid bScSaS \mid cSaSbS \mid cSbSaS \mid \varepsilon\}$

Die Grammatik in Material 1 beschreibt eine weniger strenge Form der Dreitonmusik.

2.1

Geben Sie die Ableitung für das Wort aabccb an. [2 BE]

2.2

$L_{abc}$ sei die Sprache aller Worte, die die gleiche Anzahl der Terminale $a$, $b$ und $c$ enthält. Entscheiden Sie, ob die Grammatik aus Material 1 die Sprache $L_{abc}$ erzeugt. [3 BE]

2.3

Die Grammatik aus Material 1 ist kontextfrei. Nehmen Sie Stellung zur Aussage: „Eine kontextfreie Grammatik kann keine reguläre Sprache erzeugen.“ [2 BE]

Häufig wird es als interessant empfunden, wenn die Noten eines Akkords vorher schon einmal als Einzelnoten aufgetreten sind, der Klang gewissermaßen vorbereitet wurde. Im folgenden Beispiel ist der erste Akkord vorbereitet, der zweite nicht, weil das c im Akkord seit dem vorangegangenen Akkord nicht vorhanden ist.

Mit einer Registermaschine kann man feststellen, ob in einem Musikstück alle Akkorde auf diese Weise vorbereitet wurden. Der Anfang eines solchen Registermaschinenprogramms befindet sich in Material 2. Zu Beginn steht in Register R10 die Adresse des Registers mit der ersten Note. Die Notenfolge kann als syntaktisch korrekt angenommen werden. Als Ergebnis soll im Akkumulator eine 0 stehen, falls alle Akkorde vorbereitet wurden, ansonsten eine 1.

Material 2

Anfang des Registermaschinenprogramms

// Start: R10 = Adresse der ersten Note (das Ende der Noten ist beim

// Auftreten der ersten 0 erreicht)

// Ende: Akkumulator = 0: alle Dreiklänge sind vorbereitet.

// Akkumulator = 1: nicht alle Dreiklänge sind vorbereitet.

// Die Noten und Zeichen werden wie folgt codiert:

// a = 1, b = 2, c = 3, d = 4, e = 5, f = 6, g = 7

// < = 8 und > = 9

Start: LOAD #0

STORE 1

STORE 2

STORE 3

STORE 4

STORE 5

STORE 6

STORE 7

Note: LOAD *10

JZERO Ende

STORE 8

SUB #7

JNZERO Akkord

LOAD #1

STORE *8

ADD 10

STORE 10

GOTO Note

Akkord:... // zu implementieren in Aufgabe 3.2

Ende: END

3.1

Analysieren Sie den Quellcode in Material 2 und erklären Sie die Bedeutung der Register R1 bis R7. [6 BE]

3.2

Implementieren Sie eine kommentierte Erweiterung des Registermaschinenprogramms in Material 2, zur Entscheidung, ob alle Akkorde vorbereitet wurden. [7 BE]

Häufig wird es als interessant empfunden, wenn die Noten eines Akkords vorher schon einmal als Einzelnoten aufgetreten sind, der Klang gewissermaßen vorbereitet wurde. Im folgenden Beispiel ist der erste Akkord vorbereitet, der zweite nicht, weil das c im Akkord seit dem vorangegangenen Akkord nicht vorhanden ist.

Mit einer Registermaschine kann man feststellen, ob in einem Musikstück alle Akkorde auf diese Weise vorbereitet wurden. Der Anfang eines solchen Registermaschinenprogramms befindet sich in Material 2. Zu Beginn steht in Register R10 die Adresse des Registers mit der ersten Note. Die Notenfolge kann als syntaktisch korrekt angenommen werden. Als Ergebnis soll im Akkumulator eine 0 stehen, falls alle Akkorde vorbereitet wurden, ansonsten eine 1.

Material 2

Anfang des Registermaschinenprogramms

// Start: R10 = Adresse der ersten Note (das Ende der Noten ist beim

// Auftreten der ersten 0 erreicht)

// Ende: Akkumulator = 0: alle Dreiklänge sind vorbereitet.

// Akkumulator = 1: nicht alle Dreiklänge sind vorbereitet.

// Die Noten und Zeichen werden wie folgt codiert:

// a = 1, b = 2, c = 3, d = 4, e = 5, f = 6, g = 7

// < = 8 und > = 9

Start: LOAD #0

STORE 1

STORE 2

STORE 3

STORE 4

STORE 5

STORE 6

STORE 7

Note: LOAD *10

JZERO Ende

STORE 8

SUB #7

JNZERO Akkord

LOAD #1

STORE *8

ADD 10

STORE 10

GOTO Note

Akkord:... // zu implementieren in Aufgabe 3.2

Ende: END

Die Siebentonmusik mit Akkord besteht aus Permutationen der sieben Noten $a$ bis $g$, wobei jede Note in einer Permutation genau einmal vorkommt und einem abschließenden Akkord. Das Registermaschinenprogramm in Material 2 erhält als Eingabe Noten der Siebentonmusik mit Akkord.

Ermitteln Sie für dieses Registermaschinenprogramm die Anzahl der ausgeführten Registermaschinen-Befehle, bis erstmalig der Sprung JNZERO Akkord ausgeführt wird. [2 BE]

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

1 Berechnen Sie den Wert des Terms, der bei der Anwendung des Überprüfungsalgorithmus für den Beispielcode FTLU006293 entsteht.

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

2

Geben Sie einen regulären Ausdruck für syntaktisch korrekte Containercodes an. [2 BE]

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

3 Implementieren Sie den Überprüfungsalgorithmus durch ein kommentiertes Registermaschinenprogramm. Ist der Containercode korrekt, soll nach der Überprüfung eine 1 im Akkumulator stehen, andernfalls eine 0. Sie dürfen davon ausgehen, dass die Großbuchstaben bereits durch die entsprechenden Zahlen der Tabelle in Material 1 ersetzt sind und der Containercode in den Registern 1 bis 10 der Registermaschine steht.

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

4 Die Reederei „Hamburg Floyd“ führt für die Verwaltung ihrer Container einen eigenen erweiterten Containercode ein. Dieser Code beginnt mit vier Großbuchstaben, wobei der Reederei-Schlüssel HFL den Anfang oder das Ende dieser vier Zeichen darstellt. Der verbleibende Großbuchstabe des Viererblocks ist beliebig. Dann folgt der Produktgruppen-Schlüssel, ein Bindestrich und abschließend eine natürliche Zahl größer 0, die aus beliebig vielen Ziffern bestehen kann, wobei keine führenden Nullen vorkommen dürfen. Die Sprache der Erweiterungscodes bezeichnen wir mit L.

4.1

Geben Sie eine Grammatik für die Sprache L an. [3 BE]

4.2

Ordnen Sie Ihre Grammatik G(L) sowie die Sprache L begründet in die Chomsky-Hierarchie ein. [2 BE]

4.3

Geben Sie bezogen auf Ihre Grammatik einen Ableitungsbaum oder eine Ableitung für den Erweiterungscode AHFLZ-14 an. [2 BE]

4.4

Erläutern Sie, weshalb das Syntaxdiagramm in Material 2 die Sprache L nicht korrekt darstellt. [1 BE]

Containercodes

In der Containerschifffahrt erhält jeder Container einen weltweit eindeutigen Code aus zehn Zeichen. Die ersten drei Zeichen sind der Reederei-Schlüssel, der aus drei Großbuchstaben besteht. Das vierte Zeichen ist ein Produktgruppenschlüssel, der je nach Art des Containers eines der Zeichen U, J oder Z ist. Die letzten sechs Zeichen stellen die Registriernummer dar, wobei für Zahlen kleiner 100000 die Ziffernfolge vorne mit Nullen aufgefüllt wird. Ein möglicher Containercode ist beispielsweise FTLU006293.

Die letzte Ziffer der Registriernummer ist eine Kontrollziffer. Sie muss so gewählt sein, dass das Ergebnis des folgenden Überprüfungsalgorithmus ein Vielfaches von 10 ist.

Die Großbuchstaben werden anhand der Tabelle in Material 1 durch Zahlen ersetzt. Im Überprüfungsalgorithmus werden dann von links nach rechts die Stellen des Containercodes mit den Zahlen 1 bis 10 multipliziert; die erste Stelle mit 1 und die letzte mit 10. Die Ergebnisse werden aufsummiert und die entstehende Summe ganzzahlig durch 11 geteilt.

Material 1

Tabelle zur Codierung der Buchstaben in Containercodes

A · B · C · D · E · F · G · H · I · J · K · L · M

10 · 12 · 13 · 14 · 15 · 16 · 17 · 18 · 19 · 20 · 21 · 23 · 24

N · O · P · Q · R · S · T · U · V · W · X · Y · Z

25 · 26 · 27 · 28 · 29 · 30 · 31 · 32 · 34 · 35 · 36 · 37 · 38

5 In Material 3 sehen Sie das Zustandsdiagramm eines endlichen Automaten, der die Sprache L erkennt.

5.1

Begründen Sie, weshalb dieser Automat nichtdeterministisch ist. [2 BE]

5.2

Erläutern Sie das Verfahren der Potenzmengenkonstruktion. [4 BE]

5.3

Überführen Sie das Zustandsdiagramm des Automaten aus Material 3 in das Zustandsdiagramm eines deterministischen endlichen Automaten. Die Potenzmengenbildung soll in der Benennung der Zustände erkennbar werden. [4 BE]