Fachschaft Informatik - Benutzerbeiträge [de]

Gedächtnisprotokoll FGI209-2

2009-04-06T16:35:34Z

Olli: Aufgehübscht

Zum zweiten Versuch der FGI2-Klausur wurde in PhilA geschrieben, Aufsichten hatten Herr Valk und Herr Köhler. Insgesamt waren 181Punkte zu erreichen, der Schwierigkeitsgrad war ähnlich hoch wie zur ersten Klausur.

== Aufgabe 1 ==

# Gegen waren zwei Transitionssysteme mit Sync = *leereMenge*. Geben sie das synchrone TS an.
# Geben sie L(TS_1) und L(TS_2) an, bestimmen sie auch L(TS_3) = L(TS_1) \cap L(TS_2)
[[Bild:A1.jpg]]
# Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
# Geben sie die Synchronisationsmenge an.

== Aufgabe 2 ==

Gegeben war ein (Workflow-)Netz <math>\mathcal N_1</math>, wo die letzte Stelle mit einer Transition mit der ersten verbunden war, sowie <math>\mathcal N</math>, wo diese Transition weggelassen wurde.

# Zeichnen sie den Erreichbarkeitsgraphen zu <math>\mathcal N_1</math>
# ...
# Geben sie drei Eigenschaften an, die ein Workflownetz ausmachen. Wahlweise formal oder informal.
# Wann ist ein Workflownetz ''korrekt''?
# Ist diese Workflownetz korrekt?
# Ein paar Multiple-Choice Fragen (so oder so ähnlich)
## Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=1</math>?
## Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=2</math>?
## Ist <math>\mathcal N_1</math> reversibel?
## Ist <math>\mathcal N_1</math> lebendig?

== Aufgabe 3 ==

Gegeben ist dieses Netz
[[Bild:FGI2-Modulo-Netz.png]]

und eine Schaltsequenz <math>m_1 \rightarrow^{t_1}
m_2 \rightarrow^{t_2}
m_3 \rightarrow^{t_3}
m_4 \rightarrow^{t_2}
m_5 \rightarrow^{t_3}
m_6 \rightarrow^{t_4} m_7</math> mit der Anfangsmarkierung a = 8, b = 2.

#Gebe die folgenden Markierungen an:
## <math>m_1(p_1) = \dots</math>
## <math>m_2(p_2) = \dots</math>
## <math>m_3(p_3) = \dots</math>
## <math>m_4(p_2) = \dots</math>
## <math>m_5(p_3) = \dots</math>
## <math>m_6(p_2) = \dots</math>
## <math>m_7(p_4) = \dots</math>
# Welche allgemeine Beziehung besteht auf <math>p_4</math> zwischen a, b, r, y, q?
# Ist das Netz k-beschrenkt für k=1? Begründe.

== Aufgabe 4 ==

== Aufgabe 5 ==

Gegeben war ein Lückentext-Baum, etwa so:

_ _ _ _ _ _ _ _
/ \
_ _ _ _ _ _ _ _
/ \ / \
_ _ _ _ _ _ _ _

der die Zwischenergebnisse eines bekannten Sortieralgorithmus aus der Vorlesung einzutragen waren. Es war eine Zeichenfolge, etwa 5 8 6 4 9 2 7 1, gegeben.

Außerdem gab es noch ein Paar Fragen
# Wann ist ein Algorithmus optimal?
# Ist dieser [Sortieralgorithmus] optimal?
# Wie ist die Zeitkomplexität dieses Algorithmus?
# Wie ist die Operatorenkomplexität des Algorithmus?

== Aufgabe 6 ==

Zwei BPA-Terme waren gegeben.

# Zeichnen sie die Prozessgraphen.
# Kennzeichnen sie die bisimilaren Knoten.
# Bestimmen sie die Normalformen mit den Regeln R1-R5.
# Sind die Terme bisimilar?

== Aufgabe 7 ==

Hier kam eine Aufgabe zum rekursiven Ableiten dran.

# Zeichnen sie den Prozessgraphen <X|E> mit {X=Ya+c, Y=Xc}.
# Leiten sie <X|E> mit für die Aktion a ab.
# Wann ist eine Spezifikation geschlossen?
# Ist diese Spezifikation geschützt?

== Aufgabe 8 ==
20 Punkte zu LTL und CTL

# Gegeben war eine Kripkestruktur. Geben sie alle PLätze an wo die Formel gilt.
# Wo liegen die Syntaktischen Unterschiede zwischen CTL und LTL?
# Geben sie je eine Formel an die für CTL oder LTL nicht korrekt ist.
# Geben sie Vor- und Nachteile von LTL- und CTL-Formeln an.
# ...

== Aufgabe 9 ==

Man musste die logischen, nicht die vektoriellen, Zeitstempel eintragen.

== Aufgabe 10 ==

# Wie unterscheiden sich der Ausfallalgorithmus von dem des byzantinischen Konsenses?
# Was ist Nachrichtenkomplexität?
# Geben Sie die Nachrichtenkomplexität des Ausfallalgorithmuses an.
# Warum ist der erste Algorithmus aus der Vorlesung exponentiell?
# Warum ist der zweite Algorithmus aus der Vorlesung polinomiell?

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Gedächtnisprotokoll FGI209-1

2009-04-06T16:26:36Z

Olli: aufgehübscht

Die Klausur war wesentlich schwieriger als die im letztem Jahr (sofern man das an dem Gprot erkennen konnte)
Man musste vorallem viele Definitionen können, und es kam vieles dran was so direkt nicht in den Übungsaufgaben besprochen wurde.

Auffallend war wieder die Personenkontrolle am Eingang.

Insgesamt gab es 192 Punkte zu erreichen

== Aufgabe 1 ==
Transitionssystem TS

<math>\rightarrow \overset{\overset{a}{\curvearrowleft}}{(s_0)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_1)} \rightarrow^b \overset{\overset{a}{\curvearrowleft}}{(s_2)} \rightarrow^b ...</math>

# Formale Definition angeben:
## S=
## A=
## tr=
## <math>S^0</math>=
## <math>S^F</math>=
# Wie ist die akzeptierte Sprache des Systems?
# Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
# Geben sie die Omega-Sprache <math>L^\omega(TS)</math> an
# Gegeben das Transitionssystem <math>TS_2 \rightarrow s_0' \leftrightarrow^c (s_1')</math> wobei <math>s_1'</math> Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem <math>TS_1 \times TS_2</math> mit <math>Sync=\{(b,c)\}</math> und <math>\gamma(b,c)=d</math> an

== Aufgabe 2 ==

# Geben sie die Definition einer Makierungsinvarianz an.
# Geben sie die Definition einer Lebendigkeitsinvarianz an.
# Geben sie die allgemeine Form eines Makierungsprädikates an.
# Vervollständigen sie <math>m \rightarrow^t \Leftrightarrow \dots</math> wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

# Geben sie die formale Definition von Beschränktheit eines Netzes an.
# Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.
# Beweisen oder widerlegen sie die Behauptung: ''Wenn ein Netz beschränkt ist, und der Erreichbarkeitsgraph zwei oder mehr strenge Zusammenhangskomponenten besitzt, dann ist das Netz nicht reversibel.''
# Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

Hier gab es allgemeine Fragen zu einem Erreichbarkeitsgraphen <math>RG( \mathcal N)</math> und einem Überdeckungsgraphen <math>G(\mathcal N)</math> eines Netzes.
Auch hier Ja/Nein Kreuze und begründen.

# Wenn das Netz beschränkt ist, ist dann <math>RG(\mathcal N)</math> endlich?
# Wenn das Netz unbeschränkt ist, ist dann <math>RG(\mathcal N)</math> unendlich?
# Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten <math>(\omega,\omega,\dots,\omega)</math> in <math>G(\mathcal N)</math>?
# Wenn ein Platz <math>p_i</math> unbeschränkt ist, gilt dann <math>(x_0,x_1, \dots,\omega,...,x_n)</math>. (<math>\omega</math> ist an der Stelle <math>i</math>) für jeden Knoten im Überdeckungsgraphen <math>G(\mathcal N)</math>?
# ''Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann sollte die Menge der unbeschränkten Plätze angegeben werden.''

== Aufgabe 5 ==

''(ich glaube man musste bei den Fragen Ja/Nein ankreuzen und begründen.)''

# Ist es entscheidbar ob ein P/T Netz beschränkt ist?
# Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?
# Ist die Erreichbarkeit für CPN entscheidbar?
# Gegeben ist ein P/T Netz mit <math>|P|</math> Plätzen und <math>|T|</math> Transitionen. Wir wissen, dass es <math>k</math>-beschränkt ist. Geben sie eine obere Abschätzung für die Anzahl der Knoten an, die der Erreichbarkeitsgraph hat!

== Aufgabe 6 ==

Gegeben war ein CPN.

# zeichne den Erreichbarkeitsgraphen
# Ist die Makierung (1'1 , <math> \emptyset </math>, 1'false) erreichbar?
# Gilt <math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

Gegeben war das Netz

[[Bild:FGI2-WS08-Klausur-Netz.gif]]

und die invarianten

# <math>\forall m \in R(m_ {0} : m(p1) + m(p2) + m(p3) = n)</math>
# <math>\forall m \in R(m_ {0} : m(p2) + nm(p2) + m(p4) = n)</math>

== Aufgabe 8 ==

''Hier gab es viele Punkte zur Prozessalgebra.''

<math>t1 = d((ac + b)e) + d((b + c)a) + ba</math>

<math>t2 = d((ac)e + be) + d(ba + ca) + (db)a</math>

# Menge der BPA-Terme definieren.
# Zwei Terme aus BPA gegeben, und Prozessgraphen zeichnen.
# Alle bisimilaren Knoten identifizieren.
# Reduktionskalkül anwenden.
# Sind sie bisimilar(Ja/Nein) Frage.
# Ja/Nein Fragen zur Gewichtsfunktion.
## Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?
## Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?
## Wenn t=t' gilt dann dann gew(t)=gew(t')?
## Sind Prozessgraphen in BPA immer endlich?

== Aufgabe 9 ==

Noch eine Aufgabe zur Prozessalgebra.

# Was für Dinge werden im BPA-Kalkül bewiesen? Bzw. um was dreht es sich im BPA-Kalkül. (Ja/Nein Fragen)
# <math>t_1 + t_2</math>
## <math> t_1 \rightarrow t_2 </math>
## <math> t_1 \underline{\leftrightarrow} t_2 </math>
## <math> t_1 = t_2 </math>
# Ist <math> t_1 \underline{\leftrightarrow} t_2 </math> entscheidbar?
# Ist <math> \neg (t_1 \underline{\leftrightarrow} t_2) </math> entscheidbar?
# Was bedeutet es, wenn das BPA-Kalkül korrekt ist?
# Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Folgender Harelgraph war gegeben: [[Bild:FGI2-WS08-Klausur-1-Statechart.png]]

# Male das Zustandsdiagram zu dem Harelgraphen.
# Um was erweitern Harel-Graphen endliche Automaten?

== Aufgabe 11 ==

Aufgabe zum CTL-Modelchecking.

# Beweisen sie, dass zu einer gegebenen CTL-Formel <math> \phi </math> der Model-Checking Algorithmus die Laufzeit O( <math>|\phi|*(|S|+|R|)</math>) hat.
# Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt.

== Aufgabe 12 ==

DTM und RAM

6 Multiple Choice Fragen
Komplexitaetsklassen von ''irgendwas'' (uniformes Mass und logarithmischens foo fuer Stellen und Plaetze)

== Aufgabe 13 ==

Vektorzeitstempel in eine vorhandene Struktur eintragen

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Gedächtnisprotokoll FGI209-2

2009-04-03T12:40:01Z

Olli: /* Aufgabe 2 */

Zum zweiten Versuch der FGI2-Klausur wurde in PhilA geschrieben, Aufsichten hatten Herr Valk und Herr Köhler. Insgesamt waren 181Punkte zu erreichen, der Schwierigkeitsgrad war ähnlich hoch wie zur ersten Klausur.

== Aufgabe 1 ==

* 1) Gegen waren zwei Transitionssysteme mit Sync = *leereMenge*. Geben sie das synchrone TS an.
* 2) Geben sie L(TS_1) und L(TS_2) an, bestimmen sie auch L(TS_3) = L(TS_1) \cap L(TS_2)
[[Bild:A1.jpg]]
* 3) Formen sie TS_3 so um, dass es den Schnitt akzeptiert.
* 4) Geben sie die Synchronisationsmenge an.

== Aufgabe 2 ==

Gegeben war ein (Workflow-)Netz <math>\mathcal N_1</math>, wo die letzte Stelle mit einer Transition mit der ersten verbunden war, sowie <math>\mathcal N</math>, wo diese Transition weggelassen wurde.

# Zeichnen sie den Erreichbarkeitsgraphen zu <math>\mathcal N_1</math>
# ...
# Geben sie drei Eigenschaften an, die ein Workflownetz ausmachen. Wahlweise formal oder informal.
# Wann ist ein Workflownetz ''korrekt''?
# Ist diese Workflownetz korrekt?
# Ein paar Multiple-Choice Fragen (so oder so ähnlich)
## Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=1</math>?
## Ist <math>\mathcal N_1</math> k-beschränkt für <math>k=2</math>?
## Ist <math>\mathcal N_1</math> reversibel?
## Ist <math>\mathcal N_1</math> lebendig?

== Aufgabe 3 ==

Gegeben ist dieses Netz
[[Bild:FGI2-Modulo-Netz.png]]

und eine Schaltsequenz <math>m_1 \rightarrow^{t_1}
m_2 \rightarrow^{t_2}
m_3 \rightarrow^{t_3}
m_4 \rightarrow^{t_2}
m_5 \rightarrow^{t_3}
m_6 \rightarrow^{t_4} m_7</math> mit der Anfangsmarkierung a = 8, b = 2.

*Gebe die folgenden Markierungen an:
** <math>m_1(p_1) = \dots</math>
** <math>m_2(p_2) = \dots</math>
** <math>m_3(p_3) = \dots</math>
** <math>m_4(p_2) = \dots</math>
** <math>m_5(p_3) = \dots</math>
** <math>m_6(p_2) = \dots</math>
** <math>m_7(p_4) = \dots</math>
* Welche allgemeine Beziehung besteht auf <math>p_4</math> zwischen a, b, r, y, q?
* Ist das Netz k-beschrenkt für k=1? Begründe.

== Aufgabe 4 ==

== Aufgabe 5 ==

== Aufgabe 6 ==

Zwei BPA-Terme waren gegeben.

* 1) Zeichnen sie die Prozessgraphen.
* 2) Kennzeichnen sie die bisimilaren Knoten.
* 3) Bestimmen sie die Normalformen mit den Regeln R1-R5.
* 4) Sind die Terme bisimilar?

== Aufgabe 7 ==

Hier kam eine Aufgabe zum rekursiven Ableiten dran.

* 1) Zeichnen sie den Prozessgraphen <X|E> mit {X=Ya+c, Y=Xc}.
* 2) Leiten sie <X|E> mit für die Aktion a ab.
* 3) Wann ist eine Spezifikation geschlossen?
* 4) Ist diese Spezifikation geschlossen?

== Aufgabe 8 ==
20 Punkte zu LTL und CTL

* 1) Gegeben war eine Kripkestruktur. Geben sie alle PLätze an wo die Formel gilt.
* 2) Wo liegen die Syntaktischen Unterschiede zwischen CTL und LTL?
* 3) Geben sie je eine Formel an die für CTL oder LTL nicht korrekt ist.
* 4) Geben sie Vor- und Nachteile von LTL- und CTL-Formeln an.
* 5) ...
* ...

== Aufgabe 9 ==

Man musste die logischen, nicht die vektoriellen, Zeitstempel eintragen.

== Aufgabe 10 ==

* 1) Wie unterscheiden sich der Ausfallalgorithmus von dem des byzantinischen Konsenses?
* 2) Was ist Nachrichtenkomplexität?
* 3) Geben Sie die Nachrichtenkomplexität des Ausfallalgorithmuses an.
* 4) Warum ist der erste Algorithmus aus der Vorlesung exponentiell?
* 5) Warum ist der zweite Algorithmus aus der Vorlesung polinomiell?

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Gedächtnisprotokoll FGI209-2

2009-04-03T12:28:23Z

Olli: /* Aufgabe 3 */

Olli: Assembler 2 eingefügt

== Aufgabe 1 ==
Wandeln sie die Dezimalzahl 17,125 in eine Binärzahl um mit 6 Vorkomma und 4 Nachkomma.

== Aufgabe 2 ( Extraaufgabe ) ==
Geben Sie die Dezimalzahl 0,9 als Binärbruch an. Geben Sie dazu die Vorperiode und die Periode sowie die Zahl auf 6 Stellen gerundet an.

Vorperiode:

Periode:

Gerundet:

== Aufgabe 3 ==
Berechnen Sie zur Nachricht 1101001011 die Schutzkette nach dem CRC verfahren. Das Divisionspolynoms ist 10011.
Geben Sie die geschützte Nachricht (Nachricht + Schutzkette) an.

== Aufgabe 4 ( Extraaufgabe ) ==
Die Hamming Codierung lässt sich als CRC Codierung auffassen. Das Divisionspolynoms sei 1101. Berechnen Sie ob folgende Nachrichten korrekt übertragen wurden. Ansonsten geben sie die korrigierten Nachrichten an.

a) 0111001

b) 1010000

c) 0100110

d) 1111101

== Aufgabe 5 ==
Gegeben sind folgende Relative Häufigkeiten 5, 7, 11, 18, 19, 23 eines Zeichensatzes. Geben Sie die Längen der Codewörter eines zugehörigen Huffmancodes an.

== Aufgabe 6 ==

Gegeben sind folgende DNF

X = .....

Y = .....

Dadraus wurden mithilfe von KV-Diagrammen die folgenden minimierten DNF erstellt:

a)

X = ....

Y = .....

Kreuzen Sie alle zutreffenden Aussagen an:

<pre>
[ ] Die minimierten Terme sind richtig
[ ] Die minimierten Terme sind falsch
[ ] Nur X ist richtig
[ ] Nur Y ist richtig
[ ] Die minimierten Terme sind richtig, aber vertauscht
[ ] Die minimierten Terme sind richtig, aber in der falschen Reinfolge
</pre>

b)

Aus den minimierten DNF wurde folgende Schaltung gebaut:

.....

Kreuzen Sie alle richtigen Aussagen an:
<pre>
[ ] Die Schaltung ist richtig.
[ ] Die Schaltung ist falsch.
[ ] Die Schaltung ist richtig, aber alle Ausgänge wurden vertauscht.
[ ] Die Schaltung ist richtig, aber alle Eingänge wurden vertauscht.
[ ] Die Schaltung ist richtig, aber aber die Eingäng A und B wurden vertauscht.
...
</pre>

c)

Geben Sie an welche Bedeutung die in der Schaltung verwendeten Symbole als elementare Schaltglieder haben.

d)

Geben Sie an wie oft die elementaren Schaltglieder in der Schaltung verwendet wurden.

== Aufgabe 7 ==
Zustansautomat:
a) http://theoneandonlyfoo.th.funpic.de/rs-aufgabe7.png

b)

c)

d)

== Aufgabe 8 ==
Die Ausgabe der Sparc (inklusive Flags) für folgende Aufgaben

// UNVOLLSTÄNDIG

...

0xFFFFFF9C + 0x6C

...

...

0x0 - 0x80000000

...

== Aufgabe 9 ==
Assembler 1

== Aufgabe 10 ( Extraaufgabe ) ==
.global psum
.section ".rodata"
.null: .word 0, 0
.section ".text"
! double psum( int n, double x[], double y[] )
! %i0 -> n
! %i1 -> x[]
! %i2 -> y[]
psum:
save %sp, -120, %sp

sethi %hi(.null), %o0
ldd [%o0 + %lo( .null )], %f4
st %f4, [%fp-16]
st %f4, [%fp-12]

mov %g0, %i5
cmp %g0, %i0
bge .ende
nop

.schleife:
ld [%fp-16], %f8
ld [%fp-12], %f9

mov %i5, %o0
sll %o0, 3, %o1

add %i1, %o1, %g1
ld [%g1], %f4
ld [%g1+4], %f5

add %i2, %o1, %g1
ld [%g1], %f6
ld [%g1+4], %f7

fmuld %f4, %f6, %f4
faddd %f8, %f4, %f4

st %f4, [%fp-16]
st %f5, [%fp-12]

add %i5, 1, %i5
cmp %i5, %i0
bl .schleife
nop

.ende:

ld [%fp-16], %f4
ld [%fp-12], %f5
fmovs %f4, %f0
fmovs %f5, %f1

jmp %i7+8
restore

== Aufgabe 11 ==
Cache LRU und Beladys

Anzahl Seitenalarme

== Aufgabe 12 ==
Haupspeichergröße = 2^18

Cacheblöcke = 32

Cacheblockgröße = 16

In welchem Cacheblock werden die Werte folgender Adressen abgelegt:

a) 10101001001010

b) 10101001011101

c) 01010011101001

d) 01111010111010

Geben Sie an wie viele Bit der Adresse auf was verfallen:
<pre>
Tag: Bit
Index: Bit
Offset: Bit
</pre>

[[Kategorie:Gedaechtnisprotokoll]]