TU Wien:Formale Modellierung VU (Salzer)/Prüfung 2014-12-16

Lösung der Prüfung vom 16.12.2014

Aufgabe 1

Aufgabe 1 (10 Punkte)

Die Attraktionen eines Indoorspielplatzes werden durch Einwurf sogenannter Tokens (Plastikmünzen) bezahlt, die zuvor bei einem Automaten gekauft werden. Der Automat akzeptiert Münzen im Wert von 5, 10 und 20 Cent. Immer wenn der eingeworfene Geldbetrag 25 Cent oder mehr beträgt, gibt der Automat ein Token aus. War das Guthaben höher als 25 Cent, wird der Restbetrag auf den Kauf des nächsten Token angerechnet; Geld wird keines zurückgegeben.
Modellieren Sie den Token-Automaten durch einen Mealy-Automaten, der bei jeder ein- geworfenen Münze entscheidet, ob ein Token ausgegeben (J) oder nicht ausgegeben (N) werden soll. Der Einwurf der Münzen 5 Cent, 5 Cent, 10 Cent, 20 Cent, 5 Cent und 10 Cent führt beispielsweise zur Ausgabe NNNJNJ.

-- DaJu (Diskussion) 14:13, 20. Mai 2015 (CEST)

Aufgabe 2

Aufgabe 2 (10 Punkte)

Die lineare Optimierung (auch lineare Programmierung ge- nannt) beschäftigt sich mit der Optimierung linearer Zielfunktionen über Mengen, die durch lineare Gleichungen und Ungleichungen beschrieben werden können, das heißt, durch Gleichungen und Ungleichungen folgenden Typs:

a1 · v1 + a2 · v2 + a3 · v3 + · · · = b
a1 · v1 + a2 · v2 + a3 · v3 + · · · ≤ b

wobei a1, a2, a3 , . . . und b reelle Konstanten und v1 , v2 , v3 Variablen sind.
Damit solche Optimierungsprobleme durch den Computer verarbeitet werden können, müssen die (Un)Gleichungen in maschinenlesbare Form gebracht werden. Variablen werden dabei durch das Symbol v gefolgt von einer oder mehreren Dezimalziffern dargestellt. Die reellen Konstanten werden durch arithmetische Ausdrücke dargestellt, die aus ganzzahli- gen Numeralen und Konstantensymbolen mittels Addition, Subtraktion, Multiplikation, Division und Klammern gebildet werden können. Konstantensymbole werden durch das Symbol c gefolgt von einer oder mehreren Dezimalziffern dargestellt. Die arithmetischen Operationen werden durch die Symbole +, -, *, /, = bzw. <= dargestellt. Die einzelnen Gleichungen und Ungleichungen werden durch einen Strichpunkt (;) getrennt.

Beispiel eines linearen Programms:

7*v1 + 1*v2 + c3*v3 <= 30;

(3*c100)*v3 + ((1-c1)/2)*v2 = 42;

41*v1 + (1-c1)*v2 <= (c2+1/(10-c3))

Beschreiben Sie derartige lineare Programme durch eine kontextfreie Grammatik. Verwenden

Sie so weit wie möglich Ebnf-Notationen, um die Grammatik übersichtlich zu halten.

Aufgabe 3

Aufgabe 3 (10 Punkte)

Professor John Frink organisiert eine internationale Konferenz und sucht zur Unterstützung Student Volunteers. Nach zahlreichen Vorstellungsgesprächen schränkt er die Auswahl auf Bart, Janey, Lisa, Milhouse und Richard ein, wobei allerdings nur Lisa und Richard auch Fremdsprachen beherrschen. Er stellt folgende Überlegungen an:
• Janey möchte ich auf jeden Fall, sie hat bei der letzten Konferenz schon erfolgreich mitgearbeitet.
• Ich kann höchstens drei Volunteers anstellen.
• Ich brauche jedenfalls mindestens einen Volunteer, der Fremdsprachen spricht.
• Richard und Milhouse kennen die Räume, in denen die Konferenz stattfinden soll. Einen der beiden sollte ich auf jeden Fall nehmen, aber beide zu nehmen ist nicht notwendig.
• Richard will nur mitmachen, wenn ich auch Bart anstelle.
• Milhouse und Lisa wollen nur gemeinsam genommen werden, da sie andernfalls zu- sammen auf Urlaub fahren wollen.

a) Formalisieren Sie die beschriebene Situation inklusive aller Anhaltspunkte mittels aus- sagenlogischer Formeln. Geben Sie die Bedeutung der von Ihnen verwendeten Aussa- genvariablen an.
b) Wen stellt Professor Frink als Student Volunteer an? Begründen Sie die Antwort mit Hilfe Ihrer aussagenlogischen Modellierung.

ist auch hier gelöst Datei:TU Wien-Formale Modellierung VU (Salzer) - Übung 1 - Musterlösung (2015S).pdf
a)

B ... Bart kommt mit
J ... Janey kommt mit
L ... Lisa kommt mit
M ... Millhouse kommt mit
R ... Richard kommt mit

$F0:=J$
• Janey möchte ich auf jeden Fall
$F1:=\neg (B\wedge J\wedge L\wedge M)\wedge \neg (J\wedge L\wedge M\wedge R)\wedge \neg (B\wedge L\wedge M\wedge R)\wedge \neg (B\wedge J\wedge M\wedge R)\wedge \neg (B\wedge J\wedge L\wedge R)$
• Ich kann höchstens drei Volunteers anstellen.
$F2:=L\lor R$
• Ich brauche jedenfalls mindestens einen Volunteer, der Fremdsprachen spricht.
$F3:=R\oplus M$
• Richard und Milhouse kennen die Räume, in denen die Konferenz stattfinden soll. Einen der beiden sollte ich auf jeden Fall nehmen, aber beide zu nehmen ist nicht notwendig.
$F4:=R\equiv B$
• Richard will nur mitmachen, wenn ich auch Bart anstelle.
$F5:=M\equiv L$
• Milhouse und Lisa wollen nur gemeinsam genommen werden, da sie andernfalls zu- sammen auf Urlaub fahren wollen.

b)
Anhand der Aufstellung einer Wahrheitstabelle kann man leicht die Lösung heraus finden:

B	J	L	M	R		F0	F1	F2	F3	F4	F5
0	1	0	0	0		1	1
0	1	0	0	1		1	1	1	1	0
0	1	0	1	0		1	1	0
0	1	0	1	1		1	1	1	0
0	1	1	0	0		1	1	1	1	0
0	1	1	0	1		1	1	1	1	0
0	1	1	1	0		1	1	1	1	1	1
1	1	0	0	0		1	1
1	1	0	0	1		1	1	1	1	1	1
1	1	0	1	0		1	1	0
1	1	1	0	0		1	1	1	1	1	0

Da in der 3. letzten Zeile alle Formeln F0, ... F5 wahr sind, stellt Professor Fring folgende Student Volonteer an: Bart, Janey und Richard oder Jeaney, Milhouse und Lisa.
-- DaJu (Diskussion) 14:05, 20. Mai 2015 (CEST)