Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 17.11.2004
Norbert Heidenbluth Blatt 5






Allgemeine Informatik I für Mathematiker/Wirtschaftsmathematiker
(WS 2004/2005)


Abgabetermin: 24. November 2004

Aufgabe 9: BNF-Grammatik (2 Punkte)

Gegeben sei folgende BNF-Grammatik:

• $V_T = \{\mbox{\lq\lq A''}, \mbox{\lq\lq B''}, \mbox{\lq\lq C''}, \mbox{\lq\lq D''}, \mbox{\lq\lq ,''}, \mbox{\lq\lq (''}, \mbox{\lq\lq )''}\}$

• $V_N = \{\langle \mbox{List} \rangle,   \langle \mbox{Elements} \rangle,   \langle \mbox{Element} \rangle\}$

• Produktionsregeln $P$:
  $$\begin{eqnarray*} \langle \mbox{List} \rangle & \longrightarrow & \mbox{\lq\lq (''... ...e \mbox{Element} \rangle & \longrightarrow & \mbox{\lq\lq D''} \\ \end{eqnarray*}$$
  
  
  
  
  

Überprüfen Sie für jeden der folgenden Strings, ob es sich dabei um Sätze handelt, die von dieser Grammatik erkannt werden. Falls ja, dann geben Sie bitte die formelle Ableitung an!

1. ()
2. (())
3. (A)
4. (A,B)
5. ((A),B)
6. (A),(B)
7. (A)(B)
8. (A,(B,(C)))

Aufgabe 10: Frohe Ostern (5 Punkte)

Ihr persönlicher Karriereberater hat Ihnen geraten, sich immer antizyklisch zu verhalten, und seinem Rat folgend beschäftigen sich in diesen Tagen, wo es allerorts immer weihnachtlicher zugeht, zur Abwechslung mal mit dem Osterfest.

Irgendjemand hat Ihnen nämlich von der sogenannten Osterformel von Carl Friedrich Gauß erzählt, und Sie haben gewettet, daß Sie jetzt, wo Sie schon seit vier Wochen Informatik hören, diese Formel in Oberon umsetzen können. Und deshalb lautet -- Sie ahnen es schon -- Ihre Aufgabe nun:

``Implementieren Sie die Osterformel von C.F. Gauß in Oberon!''

Und so lautet die Osterformel:

``Sei $J$ das Jahr, $a$ der Rest von $J$ bei der Division durch 19, $b$ der Rest von $J$ bei der Division durch $4$, $c$ der Rest von $J$ bei der Division durch $7$. Ferner sei $d$ der Rest von $19a+M$ bei der Division durch $30$ und $e$ der Rest von $2b+4c+6d+N$ bei der Division durch $7$, wobei die Werte $N$ und $M$ der folgenden Tabelle zu entnehmen sind:

Jahre	M	N
1700 - 1799	23	3
1800 - 1899	23	4
1900 - 2099	24	5
2100 - 2199	24	6

Der Ostersonntag fällt dann entweder auf den $(22+d+e)$-ten März oder auf den $(d+e-9)$-ten April. Anstelle des 26. April ist aber stets der 19. April zu setzen, und für den 25. April ist nur dann der 18. April zu setzen, wenn $d=28$ und $a>10$ ist.''

Nachdem Sie nun wissen, mit was sich die Leute beschäftigt haben, als es noch keine Jamba-Monatspakete gab, steht Ihnen nichts mehr im Wege, die Osterformel in Oberon zu implementieren.

Anmerkungen

• Das Jahr, für das eine Berechnung durchgeführt werden soll, wird von der Standardeingabe eingelesen.

• Die Osterformel gilt zwar für die Jahre zwischen 1583 und 8202, aber da die obige Tabelle die Werte für $M$ und $N$ nur für den Zeitraum von 1700 bis 2199 angibt, sollte Ihr Programm auch nur diesen Bereich als gültige Eingabe akzeptieren.

• Von diesem Übungsblatt an werden Punkte auch für guten Programmierstil vergeben (also Kommentare, Einrücken, sprechende Variablennamen, etc.).

Beispiel:

Aber zuvor sehen wir uns noch ein Beispiel (für das Jahr 2004) an:

• $J=2004$
• Es gilt: $2004=105 \cdot 19 + 9$, also: $a=9$
• Es gilt: $2004=501 \cdot 4$, also: $b=0$
• Es gilt: $2004=286 \cdot 7 + 2$, also: $c=2$
• Es gilt: $19 \cdot a+M=19\cdot 9 + 24 = 195$, ferner gilt: $195=6 \cdot 30 + 15$, also: $d=15$
• Es gilt: $2b+4c+6d+N=0+8+90+5=103$; ferner gilt: $14 \cdot 7 = 98$, also: $e=5$
• $22+15+5 = 42$, der März hat aber nur 31 Tage. Damit fällt der Ostersonntag also in den April, und wir müssen daher die Formel für April anwenden.
• $15+5-9=11$, das bedeutet, daß wir die beiden Sonderfälle (25. und 26. April) nicht zu beachten brauchen.

• Also muß Ostern nach der Formel von Gauß im Jahr 2004 am 11. April gewesen sein!

Und ein Blick in den Kalender verrät: Das stimmt :-)))

Aufgabe 11: Die Gauß'sche Summenformel (3 Punkte)

Jetzt -- nachdem Sie Aufgabe 10 bearbeitet haben -- sind Sie dermaßen begeistert vom ``alten Gauß'', daß Sie gar nicht genug von seinen Formeln bekommen können. Und da begegnet Ihnen auch schon die nächste:

Vielleicht haben Sie in Ihrer Analysis-Vorlesung schon die Gauß'sche Summenformel bewiesen¹?

Diese Formel lautet wie folgt:

$$\sum^{n}_{l=1}l=\frac{n\cdot(n+1)}{2}$$

Auch wenn Sie sich als Mathematiker(in) natürlich auf die Beweismethode der vollständigen Induktion verlassen, möchten Sie diese Formel dennoch gerne empirisch überprüfen. Und da Sie ja jetzt in Oberon programmieren können, freuen Sie sich über die folgende Aufgabe:

``Schreiben Sie ein Oberon-Programm, das von der Standardeingabe eine ganze Zahl $n$ einliest und mit Hilfe der Gauß'schen Summenformel die Summe $\sum_{l=1}^{n}l$ berechnet. Von diesem Ergebnis subtrahieren Sie nun schrittweise die einzelnen Summanden, bis Sie am Ende (hoffentlich) $0$ erhalten.''

Nachstehend ein kleines Beispiel für die Eingabe 5:

   theseus$ ./gauss 
   Bitte die Zahl eingeben: 
   5
   Nach Gauss ist die Summe von 1 bis 5 gleich 15.
   Empirischer Beweis:
   15 -  5 = 10
   10 -  4 =  6
    6 -  3 =  3
    3 -  2 =  1
    1 -  1 =  0

Viel Erfolg!

Fußnoten

... bewiesen¹

Falls nicht, das geht über die vollständige Induktion. Aber pssst: Wenn das in der Klausur drankommt -- von mir haben Sie diesen Tipp nicht$\ldots$ :-)