BuK-Übung01 G2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Indirekter Beweis
Aufgabe
Zeigen Sie indirekt, dass x eine gerade Zahl ist, wenn x² gerade ist.
Lösung
Ausgang: ist eine gerade Zahl
Ziel: ist eine gerade Zahl
d.h.:
ist eine ungerade Zahl
ist eine ungerade Zahl
Der indirekte Beweis startet mit der Annahme und führt zu einem Widerspruch des Ausgangs
.
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.
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
Unter [1] 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
berechnet:
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 [2] ein Beispielprogramm für den idealisierten Computer, welches mittels einer Endlosschleife realisiert ist.
