BuK/IIm10/BuK-Übung01 G2

Wiki-Quelltext dieser Seite.

== Indirekter Beweis ==
=== Aufgabe ===
Zeigen Sie indirekt, dass x eine gerade Zahl ist, wenn x² gerade ist.

=== Lösung ===
Ausgang: <math>D \dots x^2</math> ist eine gerade Zahl<br>
Ziel: <math>Z \dots x</math> ist eine gerade Zahl<br>
d.h.:<br>
<math>\bar{D} \dots x^2</math> ist eine ungerade Zahl<br>
<math>\bar{Z} \dots x</math> ist eine ungerade Zahl<br>

Der indirekte Beweis startet mit der Annahme <math>\bar{Z}</math> und führt zu einem Widerspruch des Ausgangs <math>D</math>.<br>

<math>\bar{Z} \Rightarrow x = ( 2n + 1 ), \mbox{ wobei } n \in N</math><br>
<math>\Rightarrow x^2 = ( 2n + 1 )^2</math> <br>
<math>\Rightarrow x^2 = 4n^2 + 4n + 1</math> <br>
<math>\Rightarrow x^2 = 2(2n^2+2n) + 1</math> <br>
<math>\Rightarrow x^2 \mbox{ ist eine ungerade Zahl} = \bar{D}</math><br>

<math>\mbox{Es gilt also }\bar{Z} \Rightarrow \bar{D}.\mbox{ Da laut Ausgangssituation aber }D \mbox{ gilt, folgt daraus, dass }Z\mbox{ gilt.}</math>

== Idealisierter Rechner ==
=== Aufgabe ===
Entwickeln Sie einen Interpreter für den in der Vorlesung angegebenen idealisierten
Computer. Verwenden Sie AtoCC.

=== Lösung ===
Die Grammatik für den gewünschten Interpreter wird im Folgenden dargestellt.
<pre>
P -> K
K ->  inst K | EPSILON
inst -> read nr
inst -> readn nr const
inst -> add nr nr nr
inst -> sub nr nr nr
inst -> mul nr nr nr
inst -> div nr nr nr
inst -> sqr nr nr
inst -> zero? nr
inst -> le nr nr nr
inst -> goto nr
inst -> out nr
inst -> out text
inst -> stop
</pre>

Unter [http://michael-hielscher.de/compilerwiki/index.php/Compiler_30815_Demo] kann der aus dieser Grammatik generierte Interpreter getestet werden.
Bei der Implementation der S-Ausdrücke gibt es einige interessante Überlegungen.

Die erste besteht in der Angabe der Zeilennummern innerhalb der zu interpretierenden Quelltexte. Dabei gibt es zwei Möglichkeiten. 
Entweder die jeweilige Zeilennummer wird vom Programmierer an den Anfang jeder Zeile geschrieben oder die Zeilennummern werden nicht mitgeschrieben.
Beide Möglichkeiten haben Vor- und Nachteile. 

Schreibt man die Zeilennummern mit, so können Sprunganweisungen leichter implementiert werden, dass der Programmierer
stets sieht, in welcher Zeile der Befehl steht, zu dem gesprungen werden soll. Andererseits ist es kompliziert, neue Quelltextzeilen einzufügen, da dadurch die Nummerierung ab der Einfügestelle
angepasst werden müssen. 

Lässt man die Zeilennummern weg, so muss der Programmierer die Zeilen per Hand abzählen, um die gewünschten Sprünge zu realisieren. Dafür können neue Quelltextzeilen einfacher zwischen bereits bestehenden
Zeilen eingefügt werden.

Da das Einfügen neuer Zeilen in der Programmierung sehr oft vorkommt, verzichten wir auf die explizite Angabe von Zeilennummern. Dadurch kann ein Programmierer indirekt dazu "gezwungen" werden,
nicht willkürlich hin und her zu springen, sondern Sprünge immer in einem kleinen Abstand innerhalb des Quelltextes vorzunehmen.

Eine weitere Überlegung kommt bei der Behandlung von Sprüngen zum Tragen. Um die S-Ausdrücke möglichst einfach zu halten ist man geneigt, sofort beim Auftreten eines bestimmten Tokens dieses auch zu behandeln - also den entsprechenden Befehl auszuführen. Die Interpretation des Quelltextes erfolgt also bereits während des Parsens. Dadurch können Sprünge aber nur vorwärts durchgeführt werden. Wir haben uns für eine andere Möglichkeit entschieden. Die S-Ausdrücke dienen
dabei dafür, eine Liste mit auszuführenden Befehlen zu erstellen. Wenn das Parsen beendet ist, steht somit eine Befehlsliste zur Abarbeitung zur Verfügung.
Dadurch können Sprünge sowohl vorwärts als auch rückwärts durchgeführt werden. Daraus ergibt sich die Möglichkeit der Implementation von Schleifen.

=== Aufgabe ===
Entwerfen und testen Sie ein Programm, dass die folgende Funktion 
<math>f: N \mapsto N</math> berechnet:

<math>f(n) = \begin{cases} n, & \mbox{wenn } n<4\\ n.d., &\mbox{sonst} \end{cases}</math>

=== Lösung ===
Bei der Lösung der Aufgabe sind wir innerhalb der Gruppe auf unterschiedliche Meinungen getroffen.
Die Meinungen reichen von: "Eine Endlosschleife zeigt, dass ein Wert nicht definiert ist" bis "Man kann kein Programm schreiben dessen Ausgabe bei bestimmten Parametern nicht definiert ist".
Für die erste Meinung spricht das Argument, dass der Benutzer nicht weiß, wann das Programm terminiert und somit davon "ausgeht", dass das Ergebnis nicht definiert ist. Heißt "davon ausgehen" aber auch
das die Ausgabe wirklich nicht definiert ist? 

In der Mathematik ist z.B. die Division durch 0 nicht definiert. Innerhalb eines Computers aber sehr wohl. Tritt eine Division durch 0 auf, so wird ein bestimmtest
Flag im Prozessor gesetzt. Durch dieses Flag ist es zum Beispiel innerhalb von Java möglich, eine ArithmeticException mit der Meldung "/ by zero" zu werfen. Das Verhalten der Division einer Ganzahl durch 0 ist in Java also sehr wohl definiert und besteht darin, eine Ausnahme zu werfen. Bei der Division einer Gleitkommazahl durch 0 ist in Java nicht einmal die Exception vorhanden sondern ein "echtes" Ergebnis: "Infinity" - also unendlich. Dieser Ansatz geht der zweiten Meinung voraus (kein Programm mit nicht definiertem Verhalten möglich). Selbst eine Endlosschleife kann ein definiertes Verhalten sein. Denn die Aussage "für n>=4 läuft das Programm endlos weiter" ist ein definiertes Verhalten. Obwohl das Verhalten definiert ist, ist die Lösung aber nicht definiert, da eine Endlosschleife kein Element der Menge der natürlichen Zahlen ist. Die gegebene Funktion ist aber eine Abbildung einer natürlichen Zahl auf eine natürliche Zahl.

Uunter [http://michael-hielscher.de/compilerwiki/index.php/Compiler_30815_Demo] ein Beispielprogramm für den idealisierten Computer, welches mittels einer Endlosschleife realisiert ist.