Lösungsvorschlag "Beispielhafte Klausuraufgaben"

[Andrej]

A1
a)
Ich denke dass die Zustandsmenge soll so sein: S:= {l,r} x M* x M* x N

Interpretation der Wertebereiche:
{l,r} - TaschenLampe befindet sich auf der linken oder auf der rechten Seite
M* - Folge der Männer die links oder rechts auf der Brücke stehen
N - Zeit von langsameren Mann, die genommen wird, wenn Männer die Brücke überqueren.


Wenn wir einen Zustand von S interpretieren, dann sieht er z.B. so aus:
(l, (5,20),(10,25),5) -
d.h. zwei Männer 5 und 20 sind mit der Taschenlampe auf der linken Seite der Brücke, wobei die Zeit mit der die Brücke letztes Mal überquert war, 5 Minuten ist.
Die andere Männer 10 und 25 stehen auf der anderer Seite der Brücke stehen .


Kann man so interpretieren oder?

[Andrej]

A2
b) Startzustand S0:=(l,(5,10,20,25),(),0)
also Taschenlampe auf der linken Brückenseite
alle vier Männer (5,10,20,25) stehen auf der linken Brückenseite
Die Überquerungszeitzeit ist 0 da, niemand noch die Brücke überquert hat.

[Andrej]

oder besser so S0:={ (l,(5,10,20,25),(),0) ,(r,(),(5,10,20,25),0) }
Also am Anfang stehen Männer entweder auf der linken oder rechetn Brückenseite.

[eintopf]

A1
a)
Ich denke dass die Zustandsmenge soll so sein: S:= {l,r} x M* x M* x N

Interpretation der Wertebereiche:
{l,r} - TaschenLampe befindet sich auf der linken oder auf der rechten Seite
M* - Folge der Männer die links oder rechts auf der Brücke stehen
N - Zeit von langsameren Mann, die genommen wird, wenn Männer die Brücke überqueren.


Wenn wir einen Zustand von S interpretieren, dann sieht er z.B. so aus:
(l, (5,20),(10,25),5) -
d.h. zwei Männer 5 und 20 sind mit der Taschenlampe auf der linken Seite der Brücke, wobei die Zeit mit der die Brücke letztes Mal überquert war, 5 Minuten ist.
Die andere Männer 10 und 25 stehen auf der anderer Seite der Brücke stehen .


Kann man so interpretieren oder?

Ist wahrscheinlich auch möglich, allerdings finde ich, dass es sich mit Mengen für Männer etwas besser arbeiten lässt.
Folgen sind "overhead", diese sind ja dann interessant, wenn wir an einer Reihenfolge interessiert sind, was aber nicht der Fall ist.

[Andrej]

Ok. Danke für Hinweis.

[fscheepy]

Aufgabe 1
4.
E = {gehenRechts(m), gehenLinks(m) | \(m \subseteq M\) }
wobei gehenRechts bedeutet, dass die Männer m nach Rechts gehen und gehenLinks bedeutet, dass die Männer m nach Links gehen.

Könnte man hier nicht schon gehenLinks und gehenRechts so einschränken, dass die Bedingung "Über die Brücke können maximal zwei Personen gleichzeitig gehen" erfüllt ist? Sprich: man definiert gehenLinks und gehenRechts auf einem 2-Tupel von Männern. Da es außerdem nicht sinnvoll ist, dass mehrere Männer die Brücke nach links überqueren, könnte man doch eigentlich auch nachLinks auch als Aktion mit einem Mann definieren, sprich:
E = {gehenRechts(m1, m2), gehenLinks(m1) | \(m1, m2 \in M\) }

Wäre das eine sinnvolle/gültige Designentscheidung oder schon übers Ziel hinausgeschossen bzw. falsch?

[fscheepy]

Außerdem:

Aufgabe 1
5.
((s, \(m_1\), \(m_2\), z), gehenRechts(m), (s', \(m_1\)', \(m_2\)', z')) \(\in \rightarrow\), gdw.
|m| \(\leq\) 2 \(\land\) 1 \(\le\)|m| \(\land\) \(s = l \land s' = r \land m'_1 = m_1 \backslash m \land m'_2 = m_2 \cup m\) \(\land\) z' = z + max(m)

Muss hier nicht noch hinzugefügt werden, dass m eine Teilmenge von m1 sein muss?

[eintopf]

Aufgabe 1
4.
E = {gehenRechts(m), gehenLinks(m) | \(m \subseteq M\) }
wobei gehenRechts bedeutet, dass die Männer m nach Rechts gehen und gehenLinks bedeutet, dass die Männer m nach Links gehen.

Könnte man hier nicht schon gehenLinks und gehenRechts so einschränken, dass die Bedingung "Über die Brücke können maximal zwei Personen gleichzeitig gehen" erfüllt ist? Sprich: man definiert gehenLinks und gehenRechts auf einem 2-Tupel von Männern. Da es außerdem nicht sinnvoll ist, dass mehrere Männer die Brücke nach links überqueren, könnte man doch eigentlich auch nachLinks auch als Aktion mit einem Mann definieren, sprich:
E = {gehenRechts(m1, m2), gehenLinks(m1) | \(m1, m2 \in M\) }

Wäre das eine sinnvolle/gültige Designentscheidung oder schon übers Ziel hinausgeschossen bzw. falsch?

Wie machst du, dass nur einer von links nach rechts geht?

Außerdem:

Aufgabe 1
5.
((s, \(m_1\), \(m_2\), z), gehenRechts(m), (s', \(m_1\)', \(m_2\)', z')) \(\in \rightarrow\), gdw.
|m| \(\leq\) 2 \(\land\) 1 \(\le\)|m| \(\land\) \(s = l \land s' = r \land m'_1 = m_1 \backslash m \land m'_2 = m_2 \cup m\) \(\land\) z' = z + max(m)

Muss hier nicht noch hinzugefügt werden, dass m eine Teilmenge von m1 sein muss?

Ich denke es muss nicht rein, wäre aber ggf. sinnvoll um die Intuition der Formel zu verstärken.

Angeommen MännerLinks = {5, 10} MännerRechts = {20, 25}, Taschenlampe sei Links (Zeit sei unbeachtet)
Also haben wir den Zustand (l, {5, 10}, {20,25}, z). Nun machen wir folgende Transition mit dem Mann 5 und 25 (einer links, einer rechts):
(l, {5, 10}, {20,25}, z), gehenRechts({5,25}), (r, {5,10} \ {5,25} = {10}, {20, 25} \(\cup\) {5,25} = {5, 20, 25})

Das Ergebnis ist "korrekt", d.h. die 5 ist nun auf der rechten Seite und die 25 ist weiterhin auf der rechten Seite.

[r1chard]

Aufgabe 1
4.
E = {gehenRechts(m), gehenLinks(m) | \(m \subseteq M\) }
wobei gehenRechts bedeutet, dass die Männer m nach Rechts gehen und gehenLinks bedeutet, dass die Männer m nach Links gehen.

Könnte man hier nicht schon gehenLinks und gehenRechts so einschränken, dass die Bedingung "Über die Brücke können maximal zwei Personen gleichzeitig gehen" erfüllt ist? Sprich: man definiert gehenLinks und gehenRechts auf einem 2-Tupel von Männern. Da es außerdem nicht sinnvoll ist, dass mehrere Männer die Brücke nach links überqueren, könnte man doch eigentlich auch nachLinks auch als Aktion mit einem Mann definieren, sprich:
E = {gehenRechts(m1, m2), gehenLinks(m1) | \(m1, m2 \in M\) }

Wäre das eine sinnvolle/gültige Designentscheidung oder schon übers Ziel hinausgeschossen bzw. falsch?

Wie machst du, dass nur einer von links nach rechts geht?

Außerdem:

Aufgabe 1
5.
((s, \(m_1\), \(m_2\), z), gehenRechts(m), (s', \(m_1\)', \(m_2\)', z')) \(\in \rightarrow\), gdw.
|m| \(\leq\) 2 \(\land\) 1 \(\le\)|m| \(\land\) \(s = l \land s' = r \land m'_1 = m_1 \backslash m \land m'_2 = m_2 \cup m\) \(\land\) z' = z + max(m)

Muss hier nicht noch hinzugefügt werden, dass m eine Teilmenge von m1 sein muss?

Ich denke es muss nicht rein, wäre aber ggf. sinnvoll um die Intuition der Formel zu verstärken.

Angeommen MännerLinks = {5, 10} MännerRechts = {20, 25}, Taschenlampe sei Links (Zeit sei unbeachtet)
Also haben wir den Zustand (l, {5, 10}, {20,25}, z). Nun machen wir folgende Transition mit dem Mann 5 und 25 (einer links, einer rechts):
(l, {5, 10}, {20,25}, z), gehenRechts({5,25}), (r, {5,10} \ {5,25} = {10}, {20, 25} \(\cup\) {5,25} = {5, 20, 25})

Das Ergebnis ist "korrekt", d.h. die 5 ist nun auf der rechten Seite und die 25 ist weiterhin auf der rechten Seite.

das kannst du aber auch ausnutzen wenn du bei dem gleichen Beispiel
gehenRechts({25}) als Ereignis nimmst, sind alle Bedingungen erfüllt und der Endzustand auch gültig, aber die Taschenlampe läuft allein auf die andere Seite

[fscheepy]

Wie machst du, dass nur einer von links nach rechts geht?

Warum sollte er das tun?

Ich denke es muss nicht rein, wäre aber ggf. sinnvoll um die Intuition der Formel zu verstärken.

Angeommen MännerLinks = {5, 10} MännerRechts = {20, 25}, Taschenlampe sei Links (Zeit sei unbeachtet)
Also haben wir den Zustand (l, {5, 10}, {20,25}, z). Nun machen wir folgende Transition mit dem Mann 5 und 25 (einer links, einer rechts):
(l, {5, 10}, {20,25}, z), gehenRechts({5,25}), (r, {5,10} \ {5,25} = {10}, {20, 25} \(\cup\) {5,25} = {5, 20, 25})

Das Ergebnis ist "korrekt", d.h. die 5 ist nun auf der rechten Seite und die 25 ist weiterhin auf der rechten Seite.

Was wäre mit der Transition:
(l, {5, 10}, {20,25}, z), gehenRechts({25}), (r, {5,10} \ {25} = {5, 10}, {20, 25} \(\cup\) {25} = {20, 25})
dann sind zwar die Männer auf der richtigen Seite, aber die Taschenlampe ist von alleine gewandert. Außerdem wird z' falsch berechnet, wenn man Männer mit in der Menge hat, die gar nicht mitlaufen, weil sie schon auf der anderen Seite sind, oder nicht?

[fscheepy]

Dann hätte ich noch Fragen zur "Klausur Foundations Of Computing WS 07/08":

2a) Was genau ist hier gefordert? Mein erster Gedanke war, dass nationalität eine Funktion ist: DEL -> NATION. Was muss man ansonsten noch dazuschreiben? Muss man noch etwas über die Funktionsweise der Funktion aussagen (ich hätte nämlich keine Ahnung, wie ich das mit den oben gegebenen Mengen und Funktionen machen soll. In der Vorlesung hatten wir dafür ja noch eigene Mengen, die wiederum darauf basierten, dass wir wussten, welche Elemente in DEL sind) oder reicht es schon, zu sagen, was für eine Funktion es ist?

2b) Meine Lösung wäre \(\forall ak \in AKS . \forall d \in DEL . (d = vorsitzender(ak) => d \in ak)\). Ist das korrekt und vollständig?

2c) Hier komme ich nur mit Mühe und Not auf eine Anzahl langer Formeln, die ich dann irgendwie verknüpfen muss. Kann jemand vielleicht seine Lösung dazu posten?

2d) ?!

3b) Was genau ist hier gefordert und wie löse ich es?

[r1chard]

Dann hätte ich noch Fragen zur "Klausur Foundations Of Computing WS 07/08":

2a) Was genau ist hier gefordert? Mein erster Gedanke war, dass nationalität eine Funktion ist: DEL -> NATION. Was muss man ansonsten noch dazuschreiben? Muss man noch etwas über die Funktionsweise der Funktion aussagen (ich hätte nämlich keine Ahnung, wie ich das mit den oben gegebenen Mengen und Funktionen machen soll. In der Vorlesung hatten wir dafür ja noch eigene Mengen, die wiederum darauf basierten, dass wir wussten, welche Elemente in DEL sind) oder reicht es schon, zu sagen, was für eine Funktion es ist?

2b) Meine Lösung wäre \(\forall ak \in AKS . \forall d \in DEL . (d = vorsitzender(ak) => d \in ak)\). Ist das korrekt und vollständig?

2c) Hier komme ich nur mit Mühe und Not auf eine Anzahl langer Formeln, die ich dann irgendwie verknüpfen muss. Kann jemand vielleicht seine Lösung dazu posten?

2d) ?!

3b) Was genau ist hier gefordert und wie löse ich es?

2a) hätte ich genauso

2b) würde ich \(\forall ak \in AKS . (vorsitzender(ak)\ \in\ zuordnung(ak))\)
schreiben

2c) hier hab ich \(\forall n_1,\ n_2\ \in\ NATION.\ |\{ak \in AKS\ |\ nationalität(vorsitzender(ak)) = n_1\ \}| \ \leq \ 2 * |\{ak \in AKS\ |\ nationalität(vorsitzender(ak)) = n_2\ \} | + 1\)

[fscheepy]

2b) würde ich \(\forall ak \in AKS . (vorsitzender(ak)\ \in\ zuordnung(ak))\)
schreiben

Ohja, sehr gut, meine Lösung wäre aber auch korrekt gewesen?

2c) hier hab ich \(\forall n_1,\ n_2\ \in\ NATION.\ |\{ak \in AKS\ |\ nationalität(vorsitzender(ak)) = n_1\ \}| \ \leq \ 2 * |\{ak \in AKS\ |\ nationalität(vorsitzender(ak)) = n_2\ \} | + 1\)

Ui, reife Leisung

Hast du zu der 3b auch eine Antwort?

[r1chard]

Hast du zu der 3b auch eine Antwort?

da hab ich

\(rhd \Large { {}\over{<hd(a \ :: \ l),\ \sigma>\ \Downarrow \ a} }\)


aber das sieht irgentwie zu einfach aus =)


edit:

Ohja, sehr gut, meine Lösung wäre aber auch korrekt gewesen?

ich glaub die einzelnen ak \(\in\) AKS sind nicht durch die Deligierten definiert (weiß ich aber nicht genau),
also ist es richtig, wenn du d \(\in\) ak durch d \(\in\) zuordnung(ak) ersetzt

[fscheepy]

ich glaub die einzelnen ak \(\in\) AKS sind nicht durch die Deligierten definiert (weiß ich aber nicht genau),
also ist es richtig, wenn du d \(\in\) ak durch d \(\in\) zuordnung(ak) ersetzt

Hmm, ich vermute du hast Recht. Das Gleiche gilt für die 3b, es ergibt Sinn, aber sieht zu einfach aus