Einzelschrittfunktion

Manchmal ist es notwendig den Funktionswert einer Funktion zu berechnen. Die Funktion ist uns durch ein Flussdiagramm mit initialer Registerbelegung (Eingabewerte) gegeben und wir möchten nun das Ergebnis berechnen. Dazu ein Beispiel anhand eines Flussdiagramms aus dem Skript.

Beispiel (das - in Block 1 und 2 ist mangels mathematischer Zeichen in Open Office Draw als arithmetische Differenz zu deuten):

Wir möchten z.B. nun $f_M(2,1)$ berechnen (okay, das Beispiel ist etwas blöd, da das Ergebnis in $R_0$ immer 0 ist, aber sei es drum). Wir verwenden hierzu die Einzelschritt-Notation für die Berechnung um die Schritte nachvollziehbar zu machen. Diese haben die Form: $ES^n(Block,(R_0, R_1, R_2, 0, ...)$. Merke: in $R_0$ steht das Ergebnis. Block gibt an in welchem Block wir uns befinden, $n$ gibt uns die noch durchzuführenden Schritte an und in $R_1, ..., R_n$ ist die derzeitige Registerbelegung aller weiteren verwendeten Register (ohne das Ergebnisregister). Die restlichen Register sind mit 0 gefüllt und werden mit $0,...$ angedeutet.

Wir stellen also eine kleine Tabelle auf und füllen diese Schritt für Schritt. Da wir unser $n$ aus $ES^n$ noch nicht wissen, wird es als letztes gefüllt. Für die Berechnung von $f_M(2,1)$ starten wir also bei Block 0 mit der Belegung $R_0 = 0$ (unser Ergebnis, initial mit 0 belegt), $R_1 = 2$ (unser Register Nr. 1) und $R_2 = 1$ (unser Register Nr. 2). Das führt uns zur Tabelle:

Damit haben wir schon unseren ersten Schritt mit $ES^n(0(,0,2,1,...))$. $n$ können wir, wie gesagt, noch nicht füllen, da wir die Schritte noch nicht abzählen können. Nun schauen wir nach, was in Block 1 passiert. Hier wird das Register $R_1$ auf 0 getestet. Ist das wahr, so landen wir bei Block 3 (HALT). Ist es nicht wahr, bei Block 1. In unserem Fall landen wir bei Block 1 und füllen die zweite Spalte unserer Tabelle. Achtung: die einzutragende Registerbelegung ist die beim Eintritt gültige Belegung der Register, d.h. der Berechnungsschritt aus dem Block fand noch nicht statt. Wir füllen der Abkürzung halber noch schnell alle anderen Spalten:

Wir erreichen nach 7 Schritten den Block 3 (HALT) und beenden die Berechnung. Damit haben wir nun unser $f_M(2,1) = 0$ (Ergebnis steht ja am Ende Register $R_0$ wie wir wissen). Und auch unser $n$ aus $ES^n$ ist mittlerweile gefunden. Die Gesamtrechnung für den Lösungsweg sieht dann so aus:

$ES^7(0,(0,2,1,...) = ES^6(1,(0,2,1,...) = ES^5(2,(0,1,1,...) = ES^4(0,(0,1,0,...) = ES^3(1,(0,1,0,...) = ES^2(2,(0,0,0,...) = ES^1(0,(0,0,0,...) = (3,(0,0,0,...)$

und somit

$f_M(2,1) = 0$.

Schrittzahlfunktion

Die Schrittzahlfunktion $SZ(q,d)$ bedeutet nichts anderes, als die Anzahl der Schritte dir man ausgehend von der Konfiguration $d$ bei der Anfangsmarke $q$ benötigt um zu einer Endkonfiguration zu kommen. Nehmen wir einfach das beispiel von oben: Für $(q,d) = (0,(0,2,1))$ wäre $SZ(0,(0,2,1)) = 7$.

Gesamtschrittfunktion

Die Gesamtschrittfunktion $GS(q,d)$ ist die Endkonfiguration bei der Eingabe von $(q,d)$. Führen wir das beispiel von oben fort, so landen wir bei der Eingabe von $(0,(0,2,1))$ am Ende bei $(3,(0,0,0))$. Damit ist $GS(0,(0,2,1) = (3,(0,0,0))$.

Übergangsrelationen

Das wird uns noch häufiger begegnen, deswegen werde ich das mal hier noch in aller Deutlichkeit aufschreiben. Die Übergangsrelation ist auch definiert als:

$k_1 \vdash^t k_2\Longleftrightarrow{ES^t(k_1) = k_2}$

Hier bedeutet es, dass das Flussdiagramm mit der Eingabekonfiguration $k_1$ gestartet wird und in $t$ Schritten in die Endkonfiguration $k_2$ übergeht. Um das Beispiel von oben zu bemühen wäre das:

$(0,(0,2,1)) \vdash^7 (3,(0,0,0)) \Longleftrightarrow{ES^7(0,(0,2,1) =(3,(0,0,0))}$

That's it. Ggf. füge ich noch die anderen Definitionen der Übergangsrelation bei Gelegenheit ein. Die sollten aber ziemlich selbsterklärend sein wenn man das Beispiel sieht.

Wie immer gilt: bei Fehlern bitte melden!

Buchempfehlung

Update: im Hinblick auf die Lernziele zu Kurseinheit 1, habe ich diesen Eintrag etwas überarbeitet um ihn im neuen Beitrag verwenden zu können.

Wichtig vorab: lasst euch nicht von den mathematischen Definitionen erschrecken. Sie werden nach der Einführung der formalen Definition noch einmal informell (und hoffentlich verständlich) erläutert. Auch wenn euch die Definitionen unnötig erscheinen, ist es in der Mathematik üblich etwas unmissverständlich auszudrücken. Die formale Definition ist daher leider notwendig und durchaus hilfreich bei den Prüfungen und den Einsendeaufgaben. Aber mal Butter bei die Fische:

Wir unterscheiden die Maschinen in normale Registermaschinen und allgemeine Registermaschinen. Der Unterschied zwischen den beiden ist, dass die allgemeinen Registermaschinen zusätzliche, komplexe Funktionen anbieten. Diese müssen jedoch durch normale Registermaschinen ausgedrückt werden können. Als Beispiel dient der (komplexe) Vergleich von zwei Registern, welcher durch eine normale Registermaschine ausgedrückt werden kann.

Die Registermaschine verfügt über Register $R_0, R_1, R2, ...$ zum Speichern natürlicher Zahlen. Eine Belegung der Register wird mit einer Funktion $d: \mathbb{N} \rightarrow \mathbb{N}$ realisiert. $d(i)$ ist der Inhalt des Registers $R_i$. Die Datenmenge der Registermaschine ist damit $D := \mathbb{N}^{\mathbb{N}} = \{d \mid d : \mathbb{N} \rightarrow \mathbb{N}\}$. Die Funktion $d(i)$ lässt sich auch als konkrete Belegung der Register mit $(d(0), d(1), d(2), ...)$ darstellen, z.B. "(3, 1, 5, ...)". Man verwendet hier so viele Funktionswerte, d.h. belegte Register wie notwendig. Alle anderen Register sind mit 0 belegt. Zusätzlich wird mit der Ausgabecodierung $AC: D \rightarrow \mathbb{N}$ mit $AC(d) := d(0)$ definiert, dass das Ergebnis stets im Register $R_0$ stehen soll.

Die einzigen Operationen, die eine normale Registermaschine kann ist

1. addiere 1 in $R_i$ ($R_i := R_i + 1$)
2. subtrahiere 1 in $R_i$ ($R_i := R_i \dot{-} 1$), arithemtische Differenz ($a - b := ( a - b$ falls $a \geq b$, 0 sonst), z.B. 5 $\dot{-}$ 7 = 0, aber 7$\dot{-}$ 5 = 2
3. teste ob in $R_i$ eine 0 steht. ($R_i = 0$)

Alle anderen Operationen finden sich in einer allgemeinen Registermaschine wieder und werden, wie erwähnt, durch die drei Operationen der normalen Registermaschine ausgedrückt. Nun definieren wir die beiden Arten der Registermaschine formal und erklären die Definition. Anschließend folgt ein Beispiel für eine Funktion, deren Berechenbarkeit wir durch eine allgemeine Registermaschine beweisen. Ihre komplexen Funktionen bilden wir dann mit einer normalen Registermaschine nach.

Definition Registermaschine

Eine k-stellige ($k \in \mathbb{N}$) Registermachine ist wie folgt definiert: $M = (F, \mathbb{N}^k, \mathbb{N}, EC^{(k)}, AC)$. Stelligkeit bedeutet einfach nur die Anzahl der verwendeten Register. Ist die Stelligkeit mit $k = 0$ angegeben, gilt $D:=\{\}$, d.h. die Registerbelegung ist $(0,0,...)$.

• $D := \mathbb{N}^{\mathbb{N}} = \{d \mid d : \mathbb{N} \rightarrow \mathbb{N}\}$ als die Menge der Registerbelegungen.
• $F$: ist ein Flussdiagramm (siehe Beispiel im "berechenbare Zahlenfunktion")
• $EC^{(k)}: \mathbb{N}^k \rightarrow D$ mit $EC^{(k)}(x_1,...,x_k)=(0,x_1,...,x_k,0,...)$: Eingabecodierung mit $k$ Stellen und der Menge $D$ als Datenmenge auf der operiert wird.
  Beispiel: $EC^{(3)}(3,5,1)=(0,3,5,1,0,...)$
  Wir belegen die Register $1-3$ der Registermaschine also mit $3,5,1$, wobei das erste (Ausgaberegister) und alle anderen Register mit $0$ belegt werden.
• $AC : D \rightarrow \mathbb{N}$: als Ausgabecodierung mit $AC(a_0,a_1,...):=a_0$
  D.h. im 1. Register der Registermaschine $R_0$ steht die Ausgabe.
• Die Funktionen und Tests wie oben beschrieben.

Damit haben wir die Registermaschine auch schon definiert.

Verallgemeinerte Registermaschine

Die verallgemeinerte Registermaschine ist ebenfalls k-stellig und hat die gleiche Definition $M = (F, \mathbb{N}^k, \mathbb{N}, EC^{(k)}, AC)$. Der einzige Unterschied ist, dass statt den drei rudimentären Funktionen (Addition, Subtraktion/arithmetische Differenz, Test auf 0) zusätzlich noch weitere, komplexe Funktionen und Tests definiert sind. Wir lassen nun folgende Operationen zusätzlich zu:

• $R_n:=g(R_{i1},...,R_{im})$: das bedeutet nichts anderes, als dass wir ein Register auf ein Wert setzen können, der durch eine Funktion $g$ errechnet worden ist, wobei die Eingabeparameter für $g$ aus den Registern $R_{i1},...,R_{im}$ stammen.
  Beisipel: $g(x,y)=x+y$ mit Registermaschinenbelegung $EC^3(4,1,2)=(0,4,1,2,...)$
  Die Zuweisung $R_0=g(R_1,R_3)$ ist damit gültig und das Ergebnis ist $R_0=6$
• $R_i\neq R_j$: wir können nicht mehr nur auf $0$ testen, sondern können schauen ob der Registerinhalt von $R_i$ ungleich dem Registerinhalt von $R_j$ ist.

Im Beitrag  über berechenbare Zahlenfunktionen kommt ein Beweis einer dieser komplexen Funktionen der allgemeinen Registermaschine vor: der Multiplikation. Wer noch etwas Nachhilfe bei der vollständigen Induktion bei den Maschinen braucht, dem könnte der Beitrag vielleicht helfen.

Wie immer gilt: bei Fehlern bitte melden!

Buchempfehlung

Um mir das Lernen etwas zu erleichtern schreibe ich häufig Zusammenfassungen oder MindMaps der Skripte, welche wir in den Vorlesungen bekommen. Anstatt diese auf meiner Festplatte versauern zu lassen, stelle ich sie demnächst mal hier rein. Vielleicht zieht ja der ein oder andere etwas Nutzen aus diesen. Sollten Fehler vorkommen, würde ich mich um eine Nachricht freuen damit nicht falsche Informationen in die Welt getragen werden.

So, nachdem die Prüfungsergebnisse angekommen sind, sind nun auch die Kursinformationen zu 01697 (Mensch Computer Interaktion) online. Trotz des unbefriedigenden Klausuraufbaus im Stile MC, der Verwurstelung des Skripts mit -innen und -inninnen der politischen Korrektheit wegen und der suboptimalen Einsendeaufgaben-Thematik (Pflicht für Klausurzulassung), kann ich den Kurs vom Thema her empfehlen. Sehr interessannter Stoff und Wert es mal gelesen zu haben. Hilfreich für jeden, der mal in die Verlegenheit kommt ein GUI zu entwickeln.

Nun ist das Semester rum und die Prüfungen geschrieben. Leider konnte ich den Schnitt vom letzten Semester nicht halten, was wahrscheinlich eher an mir lag.

1697: Mensch Computer Interaktion

Bei habe ich trotz intensivem lernen keinen Gefallen an der Multiple Choice Klausur finden können. Es wurden in der Klausur Dinge nicht in der Tiefe der Selbsttestaufgaben abgefragt, dafür aber deutlich breiteres Wissen, welches ggf. nur in einem Nebensatz im 600 Seiten-Skript fiel. Auch waren die Antworten teilweise sehr irreführend: der Satz selbst ist eig. als Antwort korrekt, nur der Einschub eines Wortes macht aus diesem dann ein Rätselspiel (Korrekt ist: "Es wird Licht im infraroten Spektrum verwendet, um die Variabilität der natürlichen Beleuchtung im sichtbaren Spektrum zu vermeiden.", als mögliche Antwort steht: "Es wird Licht im infraroten elektromagnetischem Spektrum verwendet, um die Variabilität der natürlichen Beleuchtung im sichtbaren Spektrum zu vermeiden."). Besteht die richtige Antwort aus zwei anzukreuzenden Teilen und kreuzt man einen Teil richtig und einen falsch an, gibt es 0 Punkte.

Es werden 12 Fragen aus jeder Kurseinheit gestellt. Die Bestehensgrenze liegt bei 65%, da man durch bloßes Ankreuzen blind wohl 20 Punkte hätte holen können (Ewartungswert). Als Klausurvoraussetzung muss man in den Selbsttestaufgaben termingerecht für die Kurseinheiten 75% (in einer Kurseinheit darf man schludern und nur mehr als 50% holen) erreichen. Man hat nur einen Versuch, kann die Fragen aber vorher üben. Pro Kurseinheit sind im Pool etwa 150-200 Fragen angesammelt, so dass man Schwierigkeiten haben sollte alle auswendig zu lernen. Hat man z.B. in 6 Kurseinheiten seine 75% immer geholt und fleißig gelernt, schludert man in der letzten Kurseinheit jedoch unter 50% so ist die Klausurzulassung dahin... ob das dem Sinn eines flexiblen Fernstudiums nicht im Wege steht? Ach ja: die Klausurfragen kommen selbstverständlich aus einem anderen Pool. Auswendig lernen nützt also nichts.

Es ist viel Stoff und geht auch sehr in die Tiefe (Amakrin- und Ganglienzellen im Auge, laterale Inhibition, geschichtlicher Überblich mit historischen Details seit dem 16. Jahrhundert, etc.). Der Kurs ist aber trotzdem spannend und hat Potential. Was mich jedoch am Skript stört ist der "genermainstreamige" Wechsel zwischen Benutzern und Benutzerinnen, Anwendern und Anwenderinnen, Programmierer und Programmiererinnen, etc. Von mir aus kann man durchgehen Benutzerin schreiben (wobei ich Benutzer, Anwender, Programmierer, usw. in Literatur und Gesprächen immer als geschlechterneutral wahrgenommen habe. Ein Benutzer ist ein Benutzer, möchte ich das Geschlecht hervorheben sage ich "weibliche oder männliche Benutzer"). Aber "Das von Programmiererinnen und Programmierern entwickelte System, welches die Benutzer und Benutzerinnen verwenden, nachdem Probanden und Probandinnen es vorher unter Anleitung von Analystinnen und Analysten sowie Interviewerinnen und Interviewern gestetet haben, ..." stört doch etwas beim Lesefluss.

1793: Software Engineering 1

Hier könnte ich mich in den Hintern beißen. Super Kurs, sehr gut verständlich, sehr faire mündliche Prüfung (Prof. Desel, ausdrückliche Empfehlung) und dann bei so einfachen Sachen wie Geheimnisprinzip und Substituierbarkeitsprinzip geschludert obwohl ich die Definitionen 5 Minuten vorher auf Knopfdruck hätte vorbeten können.

Viel mehr ist dazu auch nicht zu sagen: die Aufgaben sind keine Voraussetzung für die Klausur. Aber "Einführung in die objektorientierte Programmierung" sollte man schon vorher gemacht haben. Der Kurs behandelt die Modellierung in UML, Sequenz- und Kollaborationsdiagramme, Anforderungsermittlung, Analyse, Entwurf (Grob-, Fein- und Architekturentwurf) und endet vor der Implementierung und behandelt leider aufgrund von Platzmangel nicht den Test. Hoffentlich wird das im Nachfolgerkurs 1794 (Software Engineering 2) nachgeholt. Die Kursbeschreibung findet ihr wie immer auf der entsprechenden Kursseite sobald sie online ist.

Dennoch: beide Kurse kann ich empfehlen. Und das MCI-Gedöns wird sich irgendwann einpendeln. Das Lehrgebiet von Prof. Dr. Gabriele Peters ist neu und Kurstext sowie Klausuren frisch. Da wird sicher noch einiges dran geändert (vielleicht wie in anderen Klausuren: teilweise MC, teilweise Freitext).