Gedächtnisprotokoll FGI209-1

Aus Fachschaft_Informatik
Wechseln zu: Navigation, Suche

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

Inhaltsverzeichnis

[Bearbeiten] Aufgabe 1

Transitionssystem TS 

\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 ...
  1. Formale Definition angeben:
    1. S=
    2. A=
    3. tr=
    4. S0=
    5. SF=
  2. Wie ist die akzeptierte Sprache des Systems?
  3. Geben sie einen endlichen Automaten an, der diese Sprache akzeptiert.
  4. Geben sie die Omega-Sprache Lω(TS) an
  5. Gegeben das Transitionssystem Fehler beim Parsen (Unbekannter Fehlerhis is dvipng 1.13 Copyright 2002-2010 Jan-Ake Larsson

Usage: dvipng [OPTION]... FILENAME[.dvi] Options are chosen to be similar to dvips' options where possible: 

 -d #         Debug (# is the debug bitmap, 1 if not given)
 -D #         Output resolution
 -l #         Last page to be output
 -o f         Output file, '%d' is pagenumber
 -O c         Image offset
 -p #         First page to be output
 -pp #,#..    Page list to be output
 -q*          Quiet operation
 -T c         Image size (also accepts '-T bbox' and '-T tight')
 -v*          Verbose operation
 -            Interactive query of options

These do not correspond to dvips options: 

 -bd #        Transparent border width in dots
 -bd s        Transparent border fallback color (TeX-style color)
 -bg s        Background color (TeX-style color or 'Transparent')
 --depth*     Output the image depth on stdout
 --dvinum*    Use TeX page numbers in output filenames
 -fg s        Foreground color (TeX-style color)
 --follow*    Wait for data at end-of-file
 --freetype*  FreeType font rendering (default on)
 --gamma #    Control color interpolation
 --gif        Output GIF images (dvigif default)
 --height*    Output the image height on stdout
 --noghostscript*  Don't use ghostscript for PostScript specials
 --nogssafer* Don't use -dSAFER in ghostscript calls
 --palette*   Force palette output
 --picky      When a warning occurs, don't output image
 --png        Output PNG images (dvipng default)
 --strict     When a warning occurs, exit
 --t1lib*     T1lib font rendering (default on)
 --truecolor* Truecolor output
 -Q #         Quality (T1lib and PK subsampling)
 -z #         PNG compression level

  # = number   f = file   s = string  * = suffix, '0' to turn off
      c = comma-separated dimension pair (e.g., 3.2in,-32.1cm)

ccd226e3de3497e4c0e0092164085fa61<i>T</i><i>S</i><sub>2</sub>): TS_2 \rightarrow s_0' \overset{c}{\leftrightarrow} (s_1') 

wobei s1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS1 mit Sync = {(b,c)} und γ(b,c) = d an

[Bearbeiten] Aufgabe 2

  1. Geben sie die Definition einer Makierungsinvarianz an.
  2. Geben sie die Definition einer Lebendigkeitsinvarianz an.
  3. Geben sie die allgemeine Form eines Makierungsprädikates an.
  4. Vervollständigen sie m wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

[Bearbeiten] Aufgabe 3

  1. Geben sie die formale Definition von Beschränktheit eines Netzes an.
  2. Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.
  3. 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.
  4. Ändert es etwas, wenn das Netz unbeschränkt ist?

[Bearbeiten] Aufgabe 4

Hier gab es allgemeine Fragen zu einem Erreichbarkeitsgraphen RG( und einem Überdeckungsgraphen Fehler beim Parsen (Syntaxfehler): G(\mathcal N) 

eines Netzes.

Auch hier Ja/Nein Kreuze und begründen.

  1. Wenn das Netz beschränkt ist, ist dann Fehler beim Parsen (Syntaxfehler): RG(\mathcal N) 
endlich?
  1. Wenn das Netz unbeschränkt ist, ist dann Fehler beim Parsen (Syntaxfehler): RG(\mathcal N) 
unendlich?
  1. Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (\omega,\omega,\dots,\omega) in Fehler beim Parsen (Syntaxfehler): G(\mathcal N)

?

  1. Wenn ein Platz pi unbeschränkt ist, gilt dann (x0,x1,. (ω ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen Fehler beim Parsen (Syntaxfehler): G(\mathcal N)

?

  1. Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann sollte die Menge der unbeschränkten Plätze angegeben werden.

[Bearbeiten] Aufgabe 5

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

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

[Bearbeiten] Aufgabe 6

Gegeben war ein CPN.

  1. zeichne den Erreichbarkeitsgraphen
  2. Ist die Makierung (1'1 , \emptyset , 1'false) erreichbar?
  3. Gilt \forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1 ?

[Bearbeiten] Aufgabe 7

Gegeben war das Netz

FGI2-WS08-Klausur-Netz.gif

und die invarianten

  1. \forall m \in R(m_ {0} : m(p1) + m(p2) + m(p3) = n)
  2. \forall m \in R(m_ {0} : m(p2) + nm(p2) + m(p4) = n)

[Bearbeiten] Aufgabe 8

Hier gab es viele Punkte zur Prozessalgebra.

t1

t2

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

[Bearbeiten] Aufgabe 9

Noch eine Aufgabe zur Prozessalgebra.

  1. Was für Dinge werden im BPA-Kalkül bewiesen? Bzw. um was dreht es sich im BPA-Kalkül. (Ja/Nein Fragen)
  2. t1
    1. t1
    2. t1
    3. t1
  3. Ist t1 entscheidbar?
  4. Ist \neg (t_1 \underline{\leftrightarrow} t_2) entscheidbar?
  5. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?
  6. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

[Bearbeiten] Aufgabe 10

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

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

[Bearbeiten] Aufgabe 11

Aufgabe zum CTL-Modelchecking.

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

[Bearbeiten] Aufgabe 12

DTM und RAM

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

[Bearbeiten] Aufgabe 13

Vektorzeitstempel in eine vorhandene Struktur eintragen

Von „http://www.informatik.uni-hamburg.de/Fachschaft/wiki/index.php/Ged%C3%A4chtnisprotokoll_FGI209-1“
Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Fachschaft
Werkzeuge