Fachschaft Informatik - Benutzerbeiträge [de]

STO

2010-09-27T16:40:42Z

Jackeraner: /* Inhalt */

'''Stochastik (STO)''' ist ein Bachelormodul, das dem alten [[M4]] aus dem Diplomstudiengang entspricht.

== Aktuelles ==

== Inhalt ==
[[Bild:Stochastik.jpeg|900px]]

[[media:Stochastik.mm.tar|Hier]] die Mindmap dazu. Bearbeitbar z.B. mit FreeMind.

== Allgemeines zur Lehrveranstaltung ==
* Modulart: [[Pflichtmodul]]
* [[Referenzsemester]]: 6
* [[Leistungspunkte]]: 9
=== Stattgefundene Veranstaltungen ===
* [[STO-SS-07]]
* [[STO-SS-08]]
* [[STO-SS-09]]

== Lehrveranstaltungsform ==
* 4 SWS Vorlesung
* 2 SWS Übung

== Voraussetzungen ==
* Verbindlich: keine
* Empfohlen: [[DM]], [[ALA I]]

== Literatur ==
* http://www.amazon.de/exec/obidos/ASIN/3528354437/unimatix-21

[[Kategorie:Pflichtmodul]]
[[Kategorie:dba]]

STO

2010-09-27T16:40:14Z

Jackeraner: /* Inhalt */

'''Stochastik (STO)''' ist ein Bachelormodul, das dem alten [[M4]] aus dem Diplomstudiengang entspricht.

== Aktuelles ==

== Inhalt ==
[[Bild:Stochastik.jpeg|900px]]
[[media:Stochastik.mm.tar|Hier]] die Mindmap dazu. Bearbeitbar z.B. mit FreeMind.

== Allgemeines zur Lehrveranstaltung ==
* Modulart: [[Pflichtmodul]]
* [[Referenzsemester]]: 6
* [[Leistungspunkte]]: 9
=== Stattgefundene Veranstaltungen ===
* [[STO-SS-07]]
* [[STO-SS-08]]
* [[STO-SS-09]]

== Lehrveranstaltungsform ==
* 4 SWS Vorlesung
* 2 SWS Übung

== Voraussetzungen ==
* Verbindlich: keine
* Empfohlen: [[DM]], [[ALA I]]

== Literatur ==
* http://www.amazon.de/exec/obidos/ASIN/3528354437/unimatix-21

[[Kategorie:Pflichtmodul]]
[[Kategorie:dba]]

Datei:Stochastik.mm.tar

2010-09-27T16:31:02Z

Jackeraner: Mindmap zum Inhalt des Stochastik-Moduls. Bearbeitbar z.B. mit Freemind.

Mindmap zum Inhalt des Stochastik-Moduls. Bearbeitbar z.B. mit Freemind.

Datei:Stochastik.jpeg

2010-09-27T16:18:05Z

Jackeraner: Mindmap zur Übersicht des Stochastikstoffes.

Mindmap zur Übersicht des Stochastikstoffes.

Gedächtnisprotokoll STO09-1

2009-07-28T12:38:00Z

Jackeraner:

[[Kategorie:Gedaechtnisprotokoll|STO]]
Die Klausur von Herrn Drees fand am 28.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit war 120 Minuten. Als Hilfsmittel waren nur nicht-programmierbare Taschenrechner erlaubt. Skripte, Notizen oder Buecher waren nicht erlaubt. 
Es gab insgesamt 80 Punkte zu erreichen. Zum Bestehen benoetigt man 40 Punkte (Punkte der Teilaufgaben sind in Klammern angegeben).

== Aufgabe 1) ==

Seien A, B, C drei Ereignisse in einem Wahrscheinlichkeitsraum, so dass P(A) = 0,6, <math>P(A \cap B \cap C) = 0,3</math> und <math>P((A \cup B) \setminus C) = 0,7</math> . Wie groß ist die Wahrscheinlichkeit <math>P(B \setminus A)</math> ? Begründen sie ihre Antwort! (8 Punkte)

== Aufgabe 2) ==

Ein Würfel werde zwei mal geworfen. Sei A das Ereignis, dass im 1. Wurf eine Augenzahl von höchstens 3 fällt, B das Ereignis, dass die Summe der beiden Augenzahlen gerade ist. Berechnen sie die bedingte Wahrscheinlichkeit <math>P(A \setminus B)</math>! Sind A und B stochastisch unabhängig? Begründen sie ihre Antwort! (12 Punkte)

== Aufgabe 3) ==

Sei X eine <math>\lbrace 1, 2 \rbrace</math>- wertige Zufallsvariable und Y eine <math>\lbrace 3, 4 \rbrace</math>- wertige Zufallsvariable. In der nachfolgenden Tabelle sind die Wahrscheinlichkeiten P<math>\lbrace X = x, Y = y \rbrace</math> gegeben.

Tabelle ....

a) Bestimmen Sie die Zähldichte von X und Y. 
b) Sind X und Y stochastisch unabhängig. Begründen Sie! 
c) Berechnen sie die Kovarianz von X und Y. 
(16 Punkte)

== Aufgabe 4) ==

40 % aller Handyverträge werden von weiblichen Personen abgeschlossen, 60 % von männlichen Personen. Für eine Umfrage werden 100 Verträge rein zufällig ausgewählt. Geben Sei eine Approximation für die Wahrscheinlichkeit an, dass von den entsprechenden Vertragsinhabern mindestens 40 und höchstens 50 Personen weiblich sind! (8 Punkte)

== Aufgabe 5) ==

Sei <math>f(x) = cx (1-x)1_{(0,1)}(x)</math> , <math>x \in \R</math> 
a) Wie ist c zu wählen damit f eine Dichte ist ? 
b) Sei X eine Zufallsvariable mit Dichte f. Berechnen sie E(X) und Var(X). 
c) Berechnen sie <math>P \lbrace \frac{1}{4} \leq X \leq \frac{3}{4} \rbrace</math>. Bestimmen sie dann mit Hilfe der Chebyshev'schen Ungleichung eine untere Scranke für diese Wahrscheinlichkeit. 
(16 Punkte)

== Aufgabe 6) ==

Es werden n unabhängige, identisch verteilte Zufallsvariablen <math>X_{1}, ..., X_{n}</math> mit Verteilungsfunktion <math>F_{\vartheta } (x) = (1 - (\frac{x}{\vartheta})^{-2})1_{ [ \vartheta , \infty )}(x)</math>, <math>x \in \R</math> , beobachtet, wobei der Parameter <math>\vartheta > 0</math> unbekannt sei.

a) Bestimmen sie einen Maximum Likelihood Schätzer <math>\hat{\vartheta_{n}}</math> für <math>\vartheta</math> 
b) Zeigen, sie dass für den Maximum Likelihood Schätzer <math>\hat{\vartheta_{n}}</math> und alle <math>t \leq 1</math> gilt: <math>P \lbrace \frac{\hat{\vartheta_{n}}}{\vartheta} > t \rbrace = t^{-2n}</math>. Ist <math>\hat{\vartheta_{n}}</math> ein erwartungstreuer Schätzer? 
c) Verwenden sie b) um zwei einseitige konfidenzintervall der Form <math>(0, T_{1}]</math> bzw. <math>[T_{2}, \infty )</math> jeweils zum Niveau <math>\alpha \in (0, 1)</math> für <math>\vartheta</math> zu konstruieren, wobei <math>T_{1}</math> und <math>T_{2}</math> geeignete von den Beobachtungen abhängige Zufallsvariablen sind. 
(20 Punkte)

Gedächtnisprotokoll GSS09-1

2009-07-28T12:06:19Z

Jackeraner:

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbot die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
[[Bild:Prozessdiagramm.png]] 
a) Trage die fehlenden Beschriftungen im Diagramm ein(Zustaende waren nicht beschriftet) 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
[[Bild:Riskdiagramm.png]] 
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften (Kastchen waren leer und Kanten nicht beschriftet) 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentisierung</li>
Unterschied zwischen Identifizierung und Authentisierung erklaeren. 
Was versteht man unter einer starken Authentisierung?

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow? 
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Gedächtnisprotokoll STO09-1

2009-07-28T12:05:00Z

Jackeraner:

[[Kategorie:Gedaechtnisprotokoll|STO]]
Die Klausur von Herrn Drees fand am 28.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit war 120 Minuten. Als Hilfsmittel waren nur nicht-programmierbare Taschenrechner erlaubt. Skripte, Notizen oder Buecher waren nicht erlaubt.

== Aufgabe 1) ==

Seien A, B, C drei Ereignisse in einem Wahrscheinlichkeitsraum, so dass P(A) = 0,6, <math>P(A \cap B \cap C) = 0,3</math> und <math>P((A \cup B) \setminus C) = 0,7</math> . Wie groß ist die Wahrscheinlichkeit <math>P(B \setminus A)</math> ? Begründen sie ihre Antwort!

== Aufgabe 2) ==

Ein Würfel werde zwei mal geworfen. Sei A das Ereignis, dass im 1. Wurf eine Augenzahl von höchstens 3 fällt, B das Ereignis, dass die Summe der beiden Augenzahlen gerade ist. Berechnen sie die bedingte Wahrscheinlichkeit <math>P(A \setminus B)</math>! Sind A und B stochastisch unabhängig? Begründen sie ihre Antwort!

== Aufgabe 3) ==

Sei X eine <math>\lbrace 1, 2 \rbrace</math>- wertige Zufallsvariable und Y eine <math>\lbrace 3, 4 \rbrace</math>- wertige Zufallsvariable. In der nachfolgenden Tabelle sind die Wahrscheinlichkeiten P<math>\lbrace X = x, Y = y \rbrace</math> gegeben.

Tabelle ....

a) Bestimmen Sie die Zähldichte von X und Y. 
b) Sind X und Y stochastisch unabhängig. Begründen Sie! 
c) Berechnen sie die Kovarianz von X und Y.

== Aufgabe 4) ==

40 % aller Handyverträge werden von weiblichen Personen abgeschlossen, 60 % von männlichen Personen. Für eine Umfrage werden 100 Verträge rein zufällig ausgewählt. Geben Sei eine Approximation für die Wahrscheinlichkeit an, dass von den entsprechenden Vertragsinhabern mindestens 40 und höchstens 50 Personen weiblich sind!

== Aufgabe 5) ==

Sei <math>f(x) = cx (1-x)1_{(0,1)}(x)</math> , <math>x \in \R</math>
a) Wie ist c zu wählen damit f eine Dichte ist ? 
b) Sei X eine Zufallsvariable mit Dichte f. Berechnen sie E(X) und Var(X). 
c) Berechnen sie <math>P \lbrace \frac{1}{4} \leq X \leq \frac{3}{4} \rbrace</math>. Bestimmen sie dann mit Hilfe der Chebyshev'schen Ungleichung eine untere Scranke für diese Wahrscheinlichkeit.

== Aufgabe 6) ==

Es werden n unabhängige, identisch verteilte Zufallsvariablen <math>X_{1}, ..., X_{n}</math> mit Verteilungsfunktion <math>F_{\vartheta } (x) = (1 - (\frac{x}{\vartheta})^{-2})1_{ [ \vartheta , \infty )}(x)</math>, <math>x \in \R</math> , beobachtet, wobei der Parameter <math>\vartheta > 0</math> unbekannt sei.

a) Bestimmen sie einen Maximum Likelihood Schätzer <math>\hat{\vartheta_{n}}</math> für <math>\vartheta</math> 
b) Zeigen, sie dass für den Maximum Likelihood Schätzer <math>\hat{\vartheta_{n}}</math> und alle <math>t \leq 1</math> gilt: <math>P \lbrace \frac{\hat{\vartheta_{n}}}{\vartheta} > t \rbrace </math>

Gedächtnisprotokoll GSS09-1

2009-07-21T14:42:57Z

Jackeraner: /* 1. Teil Betriebssystem/Rechnernetze/Agenten */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbot die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
[[Bild:Prozessdiagramm.png]] 
a) Trage die fehlenden Beschriftungen im Diagramm ein(Zustaende waren nicht beschriftet) 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
[[Bild:Riskdiagramm.png]] 
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften (Kastchen waren leer und Kanten nicht beschriftet) 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentisierung</li>
Unterschied zwischen Identifizierung und Authentisierung erklaeren. 
Was versteht man unter einer starken Authentisierung?

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow? 
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Gedächtnisprotokoll GSS09-1

2009-07-21T14:42:23Z

Jackeraner: /* 2. Teil IT-Security */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbot die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
[[Bild:Prozessdiagramm.png]] 
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
[[Bild:Riskdiagramm.png]] 
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften (Kastchen waren leer und Kanten nicht beschriftet) 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentisierung</li>
Unterschied zwischen Identifizierung und Authentisierung erklaeren. 
Was versteht man unter einer starken Authentisierung?

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow? 
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Datei:Riskdiagramm.png

2009-07-21T14:40:59Z

Jackeraner: Beschreibt die Beziehung von Risiko mit anderen IT-Security Begriffen. Quelle: Skript zum Teil IT-Security von GSS

Beschreibt die Beziehung von Risiko mit anderen IT-Security Begriffen.
Quelle: Skript zum Teil IT-Security von GSS

Gedächtnisprotokoll GSS09-1

2009-07-21T14:33:14Z

Jackeraner: /* 1. Teil Betriebssystem/Rechnernetze/Agenten */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbot die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
[[Bild:Prozessdiagramm.png]] 
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften. 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentisierung</li>
Unterschied zwischen Identifizierung und Authentisierung erklaeren. 
Was versteht man unter einer starken Authentisierung?

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow? 
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Datei:Prozessdiagramm.png

2009-07-21T14:30:45Z

Jackeraner: Zustandsdiagramm fuer die Zustaende eines Prozesses im Betriebssystem. Quelle: GSS-Skript

Zustandsdiagramm fuer die Zustaende eines Prozesses im Betriebssystem.
Quelle: GSS-Skript

Gedächtnisprotokoll GSS09-1

2009-07-21T14:19:22Z

Jackeraner: /* 2. Teil IT-Security */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbot die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften. 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentisierung</li>
Unterschied zwischen Identifizierung und Authentisierung erklaeren. 
Was versteht man unter einer starken Authentisierung?

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow? 
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Gedächtnisprotokoll GSS09-1

2009-07-21T12:15:48Z

Jackeraner: /* 2. Teil IT-Security */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbietete die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften. 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentikation</li>
Unterschied zwischen Identifizierung und Authentikation erklaeren.

<li>Software-Sicherheit </li>
a) Was ist ein Buffer Overflow?
b) Was sind Canaries?

<li>Firewalls/Netzwerksicherheit</li>
Erklaeren warum TCP-Protokolle gut gefiltert werden koennen von Firewalls/Routern. 
Dann statische vs dynamische Filterung erklaeren. 
Proxies erklaren und 3 Anwendungsgebiete von Proxies angeben.

Gedächtnisprotokoll GSS09-1

2009-07-21T12:14:49Z

Jackeraner: /* 2. Teil IT-Security */

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbietete die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften. 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

<li>Kryptographie</li>
Vergleich von symmetrischer Verschluesselung, asymmetrischer Verschluesselung (Public Key), Hashfunktionen und Hashfunktionen mit Private Key.
Man sollte immer Ja angeben, wenn eine Aussage zutraf zu einem Verfahren. Gefragt waren nur 2 Aussagen:
<ul> <li>Schnell bei Verarbeitung grosser Daten? </li> <li>Beide Partner muessen ein Geheimnis kennen </li> </ul>
Den kompletten Namen von ECB und CBC Verschluesselung ausschreiben. Dann den Unterschied erklaeren und den Vorteil von CBC.

<li>Authentikation</li>
Unterschied zwischen Identifizierung und Authentikation erklaeren.

<li>Software-Sicherheit </li>
Buffer Overflow erklaeren.
<li>Buffer Overflow (\FIXME)</li>
a) Was ist ein Buffer Overflow?
b) Was sind Canaries?

<li>Proxies</li>
Wofür ist ein Proxy? Nennen Sie drei Beispiele für Proxies.

Gedächtnisprotokoll GSS09-1

2009-07-21T12:03:30Z

Jackeraner:

[[Kategorie:Gedaechtnisprotokoll|GSS]]
Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbietete die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

== 1. Teil Betriebssystem/Rechnernetze/Agenten ==

<ol>
<li>Zustandsdiagramm von Prozessen</li>
a) Trage die fehlenden Beschriftungen im Diagramm ein 
b) Ordne Saetze zu den jeweiligen Zustaenden zu 
c) Angenommen, dem Betriebssystem fehlt ein synchroner blockierender Systemaufruf, was veraendert sich dann am Zustandsdiagramm? 
d) Was unterscheidet Threads von Prozessen? 

<li>Scheduling</li>
Gegeben waren 3 periodische Prozesse mit den Perioden P1=4, P2=6, P3=3 und den Bedienzeiten T1=1 , T2=x, T3=1 . 
a) Gebe die Reihenfolge der Prozesse im Intervall 0-12 an, wenn Scheduling nach rate monotonic benutzt wird und x=2 sei. 
b) Wie a nur nun mit Earliest Deadline First 
Wieviele Verdraengungen treten im Fall a) und b) auf? 
c) Fuer welche x existiert noch ein Scheduling mit Echtzeitanforderungen? 
d) Wie ist die Auslastung, abhaengig von x, im Intervall 0-24 ?

<li>Semaphoren</li>
Gegeben war folgendes Beispiel: 3 Kinder wollen mitten im Winter nach draussen. Dafuer benoetigen sie aber einen Schal, eine Muetze und Handschuhe, damit sie sich nicht erkaelten. Kind 1 besitzt eine Muetze, Kind 2 einen Schal, und Kind 3 Handschuhe. In einem Schrank gibt es aber noch einen Schal, noch eine Muetze und noch ein Paar Handschuhe. 
a) Implementieren sie in Pseudocode die 3 Prozesse (je eins pro Kind), wobei sie die Semaphoren Operationen P und V benutzen koennen. 
b) Kann in ihrem Beispiel eine Verklemmung auftreten? 
c) Streichen sie den Prozess fuer Kind 1. Ist ihre Implementation nun ok? 
d) Was sind kritische Abschnitte? 
e) Ja/Nein Ankreuzaufgaben zu Semaphoren

<li>Datenrate</li>
Gegeben war ein Beispiel mit Tauben, die IP Pakete verschickt haben (also die Information die in ein IP Paket reinpasst ;) ). 9 Tauben wurden losgeschickt, und nach 87 Minuten kamen 4 Tauben wieder zurueck. 
a) Sie wollten 13,5 KByte Nutzdaten auf TCP Ebene verschicken. Wieviele Tauben muessten sie losschicken, um diese Daten zu versenden (ein IP Paket trage die Nutzdaten von 1,5 Kbyte wobei Kilo = 10^3 zu verstehen sei). 
b) Welche Nutzdatenrate (Header vernachlaessigen) hat der Transport ueber die Tauben, wenn sie das TCP Segment verschicken? 
c) Wieviele IP Pakete muesste eine Taube tragen koennen, um mit der GPRS-Datenrate ( 40 KByte/sek) gleichzuziehen?

<li>Speicher</li>
a) Erklaeren sie die Begriffe Kachel, Seite, Segment und die Umsetzung von Speicheradressen vom logischen in den physischen Adressraum. 
b) Wie schuetzt man Speicherbereiche voreinander (also dass ein Datenbereich z.B. Stack nicht in einen Programmcodebereich reinlaeuft) 
c) Was waere eine optimale Verdraengungsstragie fuer einen Cache? Ist sie praktisch realisierbar? Wenn ja wie, wenn nein warum nicht?

<li>CSMA/CD</li>
a) Erklaeren sie die Funktionsweise von CSMA/CD in Bezug auf die Kollisionserkennung und -behandlung. 
b) Wie wird dafuer gesorgt, dass nach einer erkannten Kollision die Wahrscheinlichkeit, dass es wieder zu einer Kollision kommt, gedrueckt? 
c) Rechenaufgabe. Formel aufstellen fuer Mindestdatenrate in einem CSMA/CD System. Dann waren Datenrate v_D, Abstand d_max gegeben und L_min beziehungsweise Mindestanteil der Nutzdaten wurde gefragt (Kontrolldaten waren mit 25 Bytes angegeben).

<li>Agenten</li>
a) Erklaeren sie die Eigenschaften, die Agenten besitzen muessen: autonom, reaktiv, proaktiv, sozialfaehig 
b) Erklaeren sie die drei ''stance'' Begriffe von D. Dennet und geben sie Beispiele dafuer an. 
c) Wie kommunizieren Agenten?
</ol>

== 2. Teil IT-Security ==

<ol>
<li>Risiko</li>
Im Diagramm zu Risiko die Begriffe wie Schwachstellen, Massnahmen,etc. eintragen und die Kanten beschriften. 
Den Begriff Risiko und den Begriff Wert erklaeren und ein Beispiel geben.

<li>Datenschutz</li>
Erklaeren, wie vorgegangen wird, wenn man ein Datenschutzproblem hat, und welche Gesetze (Landesdatenschutzgesetz,etc) beruecksichtigt muessen. Es koennte auch ein Ablaufdiagramm (wie im Skript) angegeben werden. 
Ueberbegriffe fuer technische Massnahmen angeben, mit denen in einer Organisation Datenschutz betrieben werden kann (die ganzen Kontrollen wie Zugangskontrolle, Zugriffskontrolle,...) 
Ja oder Nein eintragen, ob der IT-Sicherheitsbeauftragte oder der Datenschutzbeauftragte sich um ein Gebiet kuemmern. Angeboten waren
<ul> <li> Unternehmensgeheimnisse und Patente </li> <li>Persoenliche Daten elektronisch gespeichert </li> <li> Persoenliche Daten auf Papier</li> <li>Backup und Redundanzen</li> </ul>

Gedächtnisprotokoll GSS09-1

2009-07-21T11:56:57Z

Jackeraner:

Gedächtnisprotokoll GSS09-1

2009-07-21T11:56:09Z

Jackeraner:

Gedächtnisprotokoll GSS09-1

2009-07-21T11:35:03Z

Jackeraner: /* 1. Teil Betriebssystem/Rechnernetze/Agenten */

Gedächtnisprotokoll GSS09-1

2009-07-21T11:29:50Z

Jackeraner:

Gedächtnisprotokoll GSS09-1

2009-07-21T11:21:09Z

Jackeraner:

Gedächtnisprotokoll GSS09-1

2009-07-21T11:18:59Z

Jackeraner: Die Seite wurde neu angelegt: Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abg...

Die Klausur fand am 21.07.2009 im Zeitraum von 9.00 bis 12.00 Uhr statt. Die Bearbeitungszeit für beide Teile war 150 Minuten (2 1/2 Stunden). Handys mussten vorne abgebeben werden, Hilsmittel waren zwar offiziel keine erlaubt, aber man durfte fuer die Rechenaufgaben aus dem ersten Teil einen Taschenrechner benutzen, was fuer Verwirrung sorgte, denn der Security Teil verbietete die Benutzung von Taschenrechnern. Für den ersten Teil gab es 100, für den zweiten Teil 50 Punkte. Die GBIler haber nur den zweiten Teil geschrieben.

Gedächtnisprotokoll AD09-1

2009-02-19T16:02:55Z

Jackeraner: /* Kurskal */

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

Gliederung muss nicht unbedingt korrekt sein.

=== O-Notation ===
Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung
* <math>2^{n+3} \in O( 2^{n-3} )</math>
* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>

=== Aufagbe 2 ===
* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?

=== NP ===
* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
* Welche Eigenschaften muss eine Abbildung <math>f : L \rightarrow M</math> mit <math>L \in \Sigma*</math> und <math>M \in \Tau*</math> besitzen, damit es eine polynominalle Reduktion ist?

=== Rekurrenzgleichung ===
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

=== Suchbäume ===
* Wenn sie in einem Suchbaum alle Elemente aufsteigend ausgeben wollen, in welcher Reihenfolge müssen sie dann suchen? Ankreuzmöglichkeiten: preorder inorder postorder
* Anzahl innerer Knoten eines Binärbaums der Höhe h

a) wenn der Baum minimal
b) wenn der Baum maximal
ist. Jeweils eine geschlossene Form(d.h. ohne Summenzeichen) angeben und begründen!
* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
* Ist jeder Suchbaum eine spezielle Form des Heaps?

=== Aufgabe 6 ===
* Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.
| Schlange | Keller | Feld | stack | array | queue
--------+----------+--------+------+-------+-------+--------
fifo | | | | | |
--------+----------+--------+------+-------+-------+--------
lifo | | | | | |
--------+----------+--------+------+-------+-------+--------
random | | | | | |
access | | | | | |

* Wann wird ein Sortierverfahren als stabil bezeichnet?

=== Kurskal ===
''Gegeben ist ein Graph''
* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.
* Mit welcher Datenstruktur würden sie Kruskal implementieren, ohne groß Laufzeit zu verschenken?

=== Aufgabe 8 ===
* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
** den Median
** den Mittelwert
* Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
** Heapsort
** Radixsort
** Sortieren durch Einfügen

=== Heap ===
''Gegeben ist ein Heap in Array-Darstellung''
* Zeichnen sie den Heap

=== Aufgabe 10 ===
* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
[[Bild:avl.png]]

[[Kategorie: Gedaechtnisprotokoll|AD]]

Gedächtnisprotokoll AD09-1

2009-02-19T16:01:30Z

Jackeraner: /* Suchbäume */

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

Gliederung muss nicht unbedingt korrekt sein.

=== O-Notation ===
Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung
* <math>2^{n+3} \in O( 2^{n-3} )</math>
* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>

=== Aufagbe 2 ===
* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?

=== NP ===
* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
* Welche Eigenschaften muss eine Abbildung <math>f : L \rightarrow M</math> mit <math>L \in \Sigma*</math> und <math>M \in \Tau*</math> besitzen, damit es eine polynominalle Reduktion ist?

=== Rekurrenzgleichung ===
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

=== Suchbäume ===
* Wenn sie in einem Suchbaum alle Elemente aufsteigend ausgeben wollen, in welcher Reihenfolge müssen sie dann suchen? Ankreuzmöglichkeiten: preorder inorder postorder
* Anzahl innerer Knoten eines Binärbaums der Höhe h

a) wenn der Baum minimal
b) wenn der Baum maximal
ist. Jeweils eine geschlossene Form(d.h. ohne Summenzeichen) angeben und begründen!
* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
* Ist jeder Suchbaum eine spezielle Form des Heaps?

=== Aufgabe 6 ===
* Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.
| Schlange | Keller | Feld | stack | array | queue
--------+----------+--------+------+-------+-------+--------
fifo | | | | | |
--------+----------+--------+------+-------+-------+--------
lifo | | | | | |
--------+----------+--------+------+-------+-------+--------
random | | | | | |
access | | | | | |

* Wann wird ein Sortierverfahren als stabil bezeichnet?

=== Kurskal ===
''Gegeben ist ein Graph''
* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.

=== Aufgabe 8 ===
* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
** den Median
** den Mittelwert
* Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
** Heapsort
** Radixsort
** Sortieren durch Einfügen

=== Heap ===
''Gegeben ist ein Heap in Array-Darstellung''
* Zeichnen sie den Heap

=== Aufgabe 10 ===
* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
[[Bild:avl.png]]

[[Kategorie: Gedaechtnisprotokoll|AD]]

Gedächtnisprotokoll AD09-1

2009-02-19T15:58:59Z

Jackeraner: /* Aufagbe 2 */

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

Gliederung muss nicht unbedingt korrekt sein.

=== O-Notation ===
Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung
* <math>2^{n+3} \in O( 2^{n-3} )</math>
* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>

=== Aufagbe 2 ===
* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?

=== NP ===
* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
* Welche Eigenschaften muss eine Abbildung <math>f : L \rightarrow M</math> mit <math>L \in \Sigma*</math> und <math>M \in \Tau*</math> besitzen, damit es eine polynominalle Reduktion ist?

=== Rekurrenzgleichung ===
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

=== Suchbäume ===
* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
* Ist jeder Suchbaum eine spezielle Form des Heaps?

=== Aufgabe 6 ===
* Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.
| Schlange | Keller | Feld | stack | array | queue
--------+----------+--------+------+-------+-------+--------
fifo | | | | | |
--------+----------+--------+------+-------+-------+--------
lifo | | | | | |
--------+----------+--------+------+-------+-------+--------
random | | | | | |
access | | | | | |

* Wann wird ein Sortierverfahren als stabil bezeichnet?

=== Kurskal ===
''Gegeben ist ein Graph''
* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.

=== Aufgabe 8 ===
* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
** den Median
** den Mittelwert
* Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
** Heapsort
** Radixsort
** Sortieren durch Einfügen

=== Heap ===
''Gegeben ist ein Heap in Array-Darstellung''
* Zeichnen sie den Heap

=== Aufgabe 10 ===
* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
[[Bild:avl.png]]

[[Kategorie: Gedaechtnisprotokoll|AD]]

Gedächtnisprotokoll AD09-1

2009-02-19T15:58:22Z

Jackeraner: /* O-Notation */

Die erste AD Klausur im WS 08/09 fand am 16.02.2009 statt. Bearbeitungszeit waren 2 Stunden (120 Minuten) und es gab 100Punkte.
Die Klausur war eine gute Mischung aus Multiple-Choice-Fragen und Anwendungsaufgaben. Wenn man das Tutorium bei Frank Heitmann besucht hatte, war es gut möglich die Klausur zu bestehen.

Gliederung muss nicht unbedingt korrekt sein.

=== O-Notation ===
Jeweils Ja/Nein ankreuzen, ein Zusatzpunkt für kurze Begründung
* <math>2^{n+3} \in O( 2^{n-3} )</math>
* <math>\Omega( 2^{2^n} ) \cap O( 4^n) \in \Theta( 4^n )</math>
* Kann für zwei Funktionen f,g f <math>\in O(g) \Rightarrow g \in \Omega(f)</math> gelten?
* Gilt <math>o(n^2) \cap O(n^2) = \emptyset</math> ?
* Gilt <math>7^{log_2 n} \in \Theta(n^3)</math>?
* Ist folgende Behauptung richtig? Schlechteste Laufzeit von QuickSort ist <math>n\cdot log(n)</math>

=== Aufagbe 2 ===
* Zeigen sie durch ein Gegenbeispiel, dass der kürzeste Pfad zwischen zwei Punkten nicht zwingend eine Kante des minimalen Spannbaums des Graphen nutzen muss.
* Was bedeutet es, wenn ein NP-schweres Problem in P liegt?
* Gilt <math>7^{\log_2(n)} \in \Theta(n^3)</math>

=== NP ===
* Formulieren sie das Problem des Eulerkreis (Euler) für einen Graphen G = (V, E) als formale Sprache.
* Welche Eigenschaften muss eine Abbildung <math>f : L \rightarrow M</math> mit <math>L \in \Sigma*</math> und <math>M \in \Tau*</math> besitzen, damit es eine polynominalle Reduktion ist?

=== Rekurrenzgleichung ===
* Gegeben ist eine rekursive Gleichung <math>T(n) = \begin{cases}0 & n = 0\\3T(n-1)+3 & n > 0\end{cases}</math>. Trages Sie die ersten 5 Werte in eine Tabelle ein, finden sie eine Formel in geschlossener Form (also ohne Summmenzeichen) und beweisen sie diese anschließend durch Induktion.

=== Suchbäume ===
* Kann ein Rot-Schwarz-Baum ein AVL-Baum sein?
* Zeichnen sie alle binären Suchbäume der Menge {1,2,3}.
* Ist jeder Suchbaum eine spezielle Form des Heaps?

=== Aufgabe 6 ===
* Kreuzen sie in der Tabelle die Zugriffsmethoden auf die einzelnen Datenstrukturen an.
| Schlange | Keller | Feld | stack | array | queue
--------+----------+--------+------+-------+-------+--------
fifo | | | | | |
--------+----------+--------+------+-------+-------+--------
lifo | | | | | |
--------+----------+--------+------+-------+-------+--------
random | | | | | |
access | | | | | |

* Wann wird ein Sortierverfahren als stabil bezeichnet?

=== Kurskal ===
''Gegeben ist ein Graph''
* Bestimmen sie den minimalen Spannbaum und tragen sie in die Tabelle ein, wann sie welche Kante zum Spannbaum hinzugefügt haben, und welche ausgelassen wurden.

=== Aufgabe 8 ===
* ''Gegeben sind 13 ganze Zahlen'' Geben sie an
** den Median
** den Mittelwert
* Geben sie in O-Notation die Laufzeit von X im schlechtesten Fall an.
** Heapsort
** Radixsort
** Sortieren durch Einfügen

=== Heap ===
''Gegeben ist ein Heap in Array-Darstellung''
* Zeichnen sie den Heap

=== Aufgabe 10 ===
* Geben sie die Komplexität an, imt dem der Median aus einer Teilmenge von N berechnet werden kann.
* ''Gegeben ist ein verletzer AVL-Baum''. Führen sie die notwendigen Rotationen durch, um den AVL-Baum zu korrigieren.
[[Bild:avl.png]]

[[Kategorie: Gedaechtnisprotokoll|AD]]

Gedächtnisprotokoll SE-3LP09-1

2009-02-19T15:26:01Z

Jackeraner:

Die Logik- und die [[Gedächtnisprotokoll SE-3FP09-1|Funktionale-Klausur]] waren im selben Raum.

weitere Infos bitte - war es schwer?

=== Softwareentwicklung III - Logik Programmierung, Klausur 1 WS08/09 ===

Bearbeitungszeit: 120 Minuten

Insgesamt 60 Punkte.

==== Aufgabe 1 ====
Geben Sie die Ausgabe am Systempromt an.

1.?- add(3,5,Summe) = add(Summand1,Summand2,7).

2.?- member(X,[1,2,3,4]), X is floor(X/2)*2.

3.?- X is member(X,[1,2,3,4]).

==== Aufgabe 2 ====

1.Was bewirkt ein cut?

2.Erläutern Sie an einem Beispiel die Wirkungsweise eines Cuts.

==== Aufgabe 3 ====

Es wurde eine Datenbank für eine kleine Videothek gegeben.

%kunde(Name, Vorname, Kundennummer, Straße, Stadt)

%film(Filmnummer, Name, Kategorie)

%datentraeger(Datentraegernummer, Medium(vhs oder dvd), Filmnummer)

%ausleihe(Vorgangsnummer, Kundennummer, Datentraegernummer, Gefordertes_rueckgabedatum)

%rueckgabe(Datentraegernummer, Gefordertes_rueckgabedatum, Eventuelle_schaeden)

Zunächst sollte man Anfragen stellen.

1. Hat Susi Sorglos schoneinmal einen Film ausgeliehen?

2. Welche Filme gibt es nur auf vc und nicht auf dvd?

3. Von welchem Film gibt es nur ein Exemplar?

4. Von welchem Film sind alle Exemplare ausgeliehen?

==== Aufgabe 4 ====
Es mussten zu obiger Datenbasis nun selber Prädikate geschrieben werden. Die Überschrift der Aufgabe lautete Resultatsaggregation, was ein Hinweis darauf ist, dass man findall/3 benutzen sollte.

1. Schreiben sie ein Prädikat, was zu einer gegebenen Kategorie, die Anzahl der bisher ausgeliehenen Filme ausgibt.

2. Schreiben sie ein Prädikat, was zu einem gegebenem Monat die Kategorie ausgibt, von der die meisten Filme ausgeliehen wurden. Es gibt die Kategorien: action, erotik, horror, kinder, krimi

Hinweis: Sortieren ist mit dem Prädikat sort/2 möglich, die Ausgabereihenfolge ist aber aufsteigend.

==== Aufgabe 5 ====

Es sollten wieder Prädikate geschrieben werden.

1. Schreiben sie ein Prädikat, was zu gegebenem Kunden eine Liste absoluter Häufigkeiten der Ausleihung pro Kategorie zurückgibt. Z.B. bedeutet [0,0,0,1,4] dass ein Kunde 1 Kinderfilm und 4 Krimis bereits ausgeliehen hat.

2. Wandeln sie eine solche Liste absoluter Häufigkeiten in eine Liste relativer Häufigkeiten um, indem sie ein '''rekursives''' Prädikat verwenden. Zu der vorherigen Liste wäre z.B. [0,0,0,0.2,0.8] eine solche relative Liste.

3. Wie 2., nur verwenden sie nun ein Prädikat höherer Ordnung.

4. Vergleichen sie dass in 2. und 3. geschriebene Prädikat auf Effizienz und Verständlichkeit.

==== Aufgabe 6 ====

1.
Hier gab es eine schicke Formel mit der der Videotheks-chef nun seine Kundenprofile auswerten wollte. Formel dürfte in etwa folgende sein:

<math> z = {{1}\over{\sqrt{\sum^n_{i=1} (x_i-y_i)^2}}}</math>

Mit den aus der Aufgabe 5 berechneten Nutzerprofilen(die Listen relativer Häufigkeiten) sollte nun dieser Wert da berechnet werden. Dabei sollte einmal eine '''endrekursive''' und einmal eine '''nicht-endrekursive''' Variante verwendet werden.

2. Kann man auch dies mit einem Prädikat höherer Ordnung berechnen(analog wie bei Aufgabe 5 Teilaufgabe 3.)? Begründen sie!

==== Aufgabe 6 ====

1.
Diese Aufgabe bestand daraus, auszuwerten was ein kleines Scheme Programm macht:

Zu was evaluiert

(list (+ (* 2 2)
(+ 1 2)
(- (8/4) 2)
)

2.
Drei andere kleine Scheme Programme, aus denen wir herausfinden sollten, welches bedeutungsgleich zu dem aus der vorherigen Teilaufgabe ist.

3.
Was ist der Unterschied zwischen specialform expressions und Funktionen? Erläutern sie an einem Beispiel.

4.
Was berechnet folgende Scheme Funktion?
x ist Liste von Atomen, y ist ein Atom

( define (blub x y)
( if
(null? x)
quote ()
(if (eq? (car x) y)
blub( (cdr x) y)
(cons (car x) (blub (cdr x) y) )
)
)
)

5.
Das Scheme-Programm aus 4. in Prolog programmieren.

[[Kategorie: Gedaechtnisprotokoll|SE3]]

Gedächtnisprotokoll SE-3LP09-1

2009-02-19T15:06:23Z

Jackeraner: /* Aufgabe 2 */

Gedächtnisprotokoll SE-3LP09-1

2009-02-19T15:05:39Z

Jackeraner: /* Aufgabe 1 */

Gedächtnisprotokoll FGI209-1

2009-02-19T13:33:12Z

Jackeraner: /* Aufgabe 11 */

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 ==
1. Transitionssystem TS

<math>\rightarrow(s_0) \rightarrow^b (s_1) \rightarrow^b (s_2) \rightarrow^b ...</math>

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

<math>S^0</math>=

<math>S^F</math>=

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 <math>L^\omega(TS)</math> an

5. Gegeben das Transitionssystem <math>TS_2 ->(s_0') <->^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 Sync={(b,c) } und <math>\gamma(b,c)=d</math> an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

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

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

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

== Aufgabe 7 ==

Gegeben war das Netz

http://snuk.sn.funpic.de/netz.gif

== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

Aufgabe zum CTL-Modelchecking.

1. Beweisen sie, dass zu einer gegebenen CTL-Formel <math> \phi </math> der Model-Checking Algorithmus die Laufzeit O( <math>|\phi|*(|S|+|R|)</math>) hat.

2. Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt.

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:32:48Z

Jackeraner: /* Aufgabe 11 */

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 ==
1. Transitionssystem TS

<math>\rightarrow(s_0) \rightarrow^b (s_1) \rightarrow^b (s_2) \rightarrow^b ...</math>

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

<math>S^0</math>=

<math>S^F</math>=

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 <math>L^\omega(TS)</math> an

5. Gegeben das Transitionssystem <math>TS_2 ->(s_0') <->^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 Sync={(b,c) } und <math>\gamma(b,c)=d</math> an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

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

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

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

== Aufgabe 7 ==

Gegeben war das Netz

http://snuk.sn.funpic.de/netz.gif

== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

Aufgabe zum CTL-Modelchecking.

1. Beweisen sie, dass zu einer gegebenen CTL-Formel <math> \phi </math> der Model-Checking Algorithmus die Laufzeit O( <math>\phi*(|S|+|R|)</math>) hat.

2. Man musste die Formel EGa auf einer Kripkestruktur anwenden, und zeigen, wo sie gilt.

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:14:20Z

Jackeraner: /* Aufgabe 1 */

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 ==
1. Transitionssystem TS

<math>\rightarrow(s_0) \rightarrow^b (s_1) \rightarrow^b (s_2) \rightarrow^b ...</math>

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

<math>S^0</math>=

<math>S^F</math>=

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 <math>L^\omega(TS)</math> an

5. Gegeben das Transitionssystem <math>TS_2 ->(s_0') <->^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 Sync={(b,c) } und <math>\gamma(b,c)=d</math> an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

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

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:09:52Z

Jackeraner: /* Aufgabe 6 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

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

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:09:21Z

Jackeraner: /* Aufgabe 6 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

b) Ist die Makierung (1'1 , false , <math> \emtpyset </math>) erreichbar?
c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:07:01Z

Jackeraner: /* Aufgabe 9 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math> (Bisimilarität gemeint)

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:06:22Z

Jackeraner: /* Aufgabe 10 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math>

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

Ein Harelgraph war gegeben. Man sollte das Zustandsdiagramm dazu malen.

Weiterhin sollte man erklären, um was Harel-Graphen endliche Automaten erweitern.

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:05:31Z

Jackeraner: /* Aufgabe 9 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== 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)

a) <math>t_1 + t_2</math>

b)<math> t_1 \rightarrow t_2 </math>

c) <math> t_1 \leftrightarrow t_2 </math>

d) <math> t_1 = t_2 </math>

2. Ist <math> t_1 \leftrightarrow t_2 </math> entscheidbar?

3. Ist <math> \neg t_1 \leftrightarrow t_2 </math> entscheidbar?

4. Was bedeutet es, wenn das BPA-Kalkül korrekt ist?

5. Was bedeutet es, wenn das BPA-Kalkül vollständig ist?

== Aufgabe 10 ==

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T13:01:43Z

Jackeraner: /* Aufgabe 8 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

a)Wenn t-> t' reduziert werden kann , gilt dann gew(t) > gew(t')?

b) Wenn t->* t' reduziert werden kann, gilt dann gew(t) > gew(t')?

c) Wenn t=t' gilt dann dann gew(t)=gew(t')?

7. Sind Prozessgraphen in BPA immer endlich?

== Aufgabe 9 ==

== Aufgabe 10 ==

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T12:58:54Z

Jackeraner: /* Aufgabe 8 */

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 ==
1. Transitionssystem TS
->(s_0) -> b (s_1) ->b (s_2) -> b ...

wobei jeder Zustand noch eine Schleife mit a's hat und jeder Zustand Endzustand ist.
Formale Definition angeben:

S=

A=

tr=

S^0=

S^F=

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^omega(TS) an

5. Gegeben das Transitionssystem TS_2 ->(s_0') <->c (s_1')
wobei s_1' Endzustand ist. Geben sie das Zustandsdiagramm des synchronen Transitionssystem TS_1 X TS_2 mit Sync={(b,c) } und gamma(b,c)=d an

== 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->t (t ist in m aktiviert) <=>

wobei auf der rechten Seite ein Makierungsprädikat angegeben werden soll.

== Aufgabe 3 ==

a)
Geben sie die formale Definition von Beschränktheit eines Netzes an.

b)
Geben sie die formale Definition von struktureller Beschränktheit eines Netzes an.

c) 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.

d) Ändert es etwas, wenn das Netz unbeschränkt ist?

== Aufgabe 4 ==

== Aufgabe 5 ==

(ich glaube man musste bei den fragen ja/nein ankreuzen und begründen.)

a)
Ist es entscheidbar ob ein P/T Netz beschränkt ist?

b)
Ist es entscheidbar ob ein P/T Netz k-beschränkt ist?

c)
Ist die Erreichbarkeit für CPN entscheidbar?

d)
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!

== Aufgabe 6 ==

Gegeben war ein CPN.

a) zeichne den Erreichbarkeitsgraphen

...

c) Gilt
<math>\forall p \in P : \forall m \in R(N) : \mid m(p)\mid \leq 1</math> ?

== Aufgabe 7 ==

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

a) Wenn das Netz beschränkt ist, ist dann RG(N) endlich?

b) Wenn das Netz unbeschränkt ist, ist dann RG(N) unendlich?

c) Wenn das Netz unbeschränkt ist, gibt es dann zwingend den Knoten (omega,omega,...,omega) in G(N)?

d) Wenn ein Platz p_i unbeschränkt ist, gilt dann (x_0,x_1,...,omega,...,x_n) (omega ist an der Stelle i) für jeden Knoten im Überdeckungsgraphen G(N)?

e) Hier war ein Petrinetz gegeben, und es sollte der Überdeckungsgraph gezeichnet werden. Dann soltle die Menge der unbeschränkten Plätze angegeben werden.
== Aufgabe 8 ==

Hier gab es viele Punkte zur Prozessalgebra.

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.

7. Sind Prozessgraphen in BPA immer endlich?

== Aufgabe 9 ==

== Aufgabe 10 ==

== Aufgabe 11 ==

== Aufgabe 12 ==

DTM und RAM

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

== Aufgabe 13 ==

[[Kategorie:Gedaechtnisprotokoll|FGI2]]

Vektorzeitstempel in eine vorhandene Struktur eintragen

Gedächtnisprotokoll FGI209-1

2009-02-19T12:56:19Z

Jackeraner: /* Aufgabe 6 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:50:14Z

Jackeraner: /* Aufgabe 5 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:48:02Z

Jackeraner: /* Aufgabe 3 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:43:58Z

Jackeraner: /* Aufgabe 2 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:43:32Z

Jackeraner: /* Aufgabe 2 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:43:14Z

Jackeraner: /* Aufgabe 2 */

Gedächtnisprotokoll FGI209-1

2009-02-19T12:40:42Z

Jackeraner: /* Aufgabe 1 */