Vorlesung 5 Flashcards
SYPC, Erreichbarkeit
Was beschreibt das synchrone Produkt (SYPC) in der Komposition von Prozessen?
Das synchrone Produkt (SYPC) ist ein Kompositionsoperator, der zwei Komponenten so verbindet, dass sie bei gemeinsamen Ereignissen synchronisiert werden. Private Ereignisse, die nur in einer der Komponenten auftreten, sind jedoch jederzeit möglich, ohne dass sie die andere Komponente beeinflussen.
Was bedeutet partieller Gleichschritt im Kontext des SYPC-Operators?
Der partielle Gleichschritt im Kontext des SYPC-Operators bedeutet, dass die gekoppelten Komponenten nur bei gemeinsamen Ereignissen synchronisiert werden, während sie bei privaten Ereignissen unabhängig voneinander agieren können.
Welche Zustände enthält ein komponiertes System G, das mit dem SYPC-Operator erstellt wurde?
Ein komponiertes System G, das mit dem SYPC-Operator erstellt wurde, enthält nur die Zustandsübergänge, die durch die Synchronisation von gemeinsamen Ereignissen erreichbar sind. Nicht erreichbare Zustände aufgrund von fehlender Synchronisation sind nicht enthalten.
Was passiert im Spezialfall des synchronen Produkts, wenn die beiden Systeme keine gemeinsamen Ereignisse haben?
Was ist ein autonomes Petrinetz?
Wie lässt sich die Struktur eines Petrinetzes beschreiben?
Was sind Prästellen und Poststellen in einem Petrinetz?
Wie wird der aktuelle Zustand eines Petrinetzes dargestellt?
Der aktuelle Zustand eines Petrinetzes wird durch eine Markierung der Stellen mit Marken festgelegt. Diese Markierung zeigt die Verteilung der Ressourcen oder Zustände in einem Netz zu einem bestimmten Zeitpunkt an.
Was bedeutet es, dass ein Petrinetz reine Netze sind?
Reine Netze sind Petrinetze, die angenommen haben, dass keine Schlingen enthalten sind. Das bedeutet, dass keine Transition direkt mit sich selbst durch eine Stelle verbunden ist, was die Analyse und das Verständnis der Netzstruktur vereinfacht.
Wie entsteht die Netzwerkdynamik in autonomen Petrinetzen?
Die Netzwerkdynamik in autonomen Petrinetzen entsteht durch die Bewegung der Marken von den Prästellen über die Transitionen zu den Poststellen, was auch als Schalten oder Feuern von Transitionen bezeichnet wird.
Was ist die Schaltregel für autonome Petrinetze?
Eine Transition t ist aktiviert und kann schalten, wenn alle ihre Prästellen markiert sind und alle ihre Poststellen nicht markiert sind. Beim Schalten werden den Prästellen Marken entzogen und die Poststellen markiert.
Kann die Anzahl der Marken in einem autonomen Petrinetz durch Schalten verändert werden?
Ja, die Anzahl der Marken im Netz kann sich durch das Schalten verändern, was darauf hinweist, dass das Verhalten des Netzes nicht deterministisch sein kann, insbesondere wenn mehrere Transitionen gleichzeitig aktiviert sind.
Wie wird der aktuelle Zustand eines Petrinetzes dargestellt?
Der aktuelle Zustand eines Petrinetzes zu einem diskreten Zeitpunkt wird durch den Markierungsvektor
p(k)-> repräsentiert, dessen Elemente gleich Eins sind, wenn die entsprechende Stelle markiert ist, und sonst Null.
Was beschreibt der Schaltvektor in einem autonomen Petrinetz?
Der Schaltvektor t(k)-> zeigt an, welche Transitionen zum aktuellen Zeitpunkt schalten. Jedes Element des Vektors ist gleich Eins, wenn die entsprechende Transition schaltet, ansonsten ist es Null.
Wie lässt sich SPC kurz beschreiben?
nur gemeinsame Ereignisse finden synchron statt
was ist davon der erreichbare und nicht erreichbare Teil?
Was ist das Ergebnis der Anwendung von SPC auf dieses Beispiel?
Was beschreibt SYPC?
Den partiellen Gleichschritt zweier gekoppelter Komponenten. Keine strenge Synchronisation, wie bei SPC.
Was ist das Ergebnis der Anwendung von SPC auf dieses Beispiel?
Was von diesem Beispiel der Anwendung von SYPC gehört zu SPC spezifisch und was nicht?
Wann ist es etwas Ko-erreichbar?
Ko-Erreichbar, wenn ich
von einem aktuellen Zustand x aus einer Folge s in einen markierten Zustand komme
Was liefert die Ac-Operation? Nimm Bezug auf die Zustände und die Sprachen L(g) und L_m(G)
Es antwortet mit einem G auf einen G, mit der Menge der erreichbaren Zustände bedingt durch die Folge s. Nicht erreichbare Zustände werden gestrichen. Diese Operation hat keinen Einfluss auf die Sprache L(G) und L_m(G)
Was ist der Zweck der Erreichbarkeitsanalyse in der Analyse logischer DES?
Die Erreichbarkeitsanalyse dient dazu, zu bestimmen, welche System- oder Prozesszustände vom Anfangszustand aus erreichbar sind und ob ein System oder Prozess aus einem beliebigen Zustand heraus einen Zielzustand erreichen kann.
Was versteht man unter Deadlock, Livelock und Blockierung in der Analyse von DES?
Deadlock, Livelock und Blockierung sind Begriffe, die beschreiben, ob ein System oder Prozess immer adäquat beendet werden kann. Ein Deadlock bezeichnet eine Situation, in der keine Fortsetzung möglich ist, ein Livelock eine endlose Schleife ohne Fortschritt und eine Blockierung ein Zustand, in dem bestimmte Aktionen nicht mehr durchführbar sind.
Was ist die strukturelle Analyse und Invarianten in der Analyse von DES?
Strukturelle Analyse und Invarianten beziehen sich auf Methoden, um Analysefragen zu beantworten, die unabhängig von Parametereinstellungen wie dem Anfangszustand des Systems sind. Sie helfen zu verstehen, welche Eigenschaften des Systems unter allen Umständen erhalten bleiben.
Welche Vorteile bietet die Verwendung formaler Beschreibungsformen in der Analyse von DES?
Formale Beschreibungsformen wie formale Sprachen, Automaten und Petrinetze ermöglichen eine präzise und analytische Untersuchung verschiedener Aspekte von DES. Sie bieten Werkzeuge, um komplexe Systemzustände und deren Dynamik zu modellieren und zu analysieren.
Wie werden die Methoden der Erreichbarkeits- und Ko-Erreichbarkeitsanalyse, Deadlock/Livelock/Blockierung sowie strukturelle Analyse in Bezug auf DES angewendet?
Diese Methoden werden jeweils auf Generatoren und Petrinetze angewendet, um die dynamischen und strukturellen Eigenschaften von DES zu untersuchen. Sie ermöglichen es, die Machbarkeit von Prozessabläufen zu prüfen und potenzielle Probleme wie Deadlocks oder unerwünschte Endlosschleifen zu identifizieren.
Was bedeutet es, dass ein Zustand in einem Generator erreichbar ist?
Ein Zustand ist in einem Generator erreichbar, wenn es eine Sequenz von Ereignissen in Σ ∗ gibt, die, wenn sie auf den Anfangszustand x 0 angewendet wird, zum Zustand x führt.
Was ist die Ac-Operation in der Analyse von Generatoren?
Die Ac-Operation definiert eine reduzierte Form eines Generators, indem sie ihn auf seinen erreichbaren Teil beschränkt. Dies geschieht durch die Definition von X ac , der Menge der erreichbaren Zustände, und der Restriktion der Zustandsübergangsfunktion δ auf diese Menge.
Wie wird die Erreichbarkeit eines Generators bestimmt?
Warum ist es ausreichend, die reduzierte Form eines Generators zu betrachten, um Erreichbarkeit zu prüfen?
Es ist ausreichend, die reduzierte Form eines Generators zu betrachten, weil die Erreichbarkeit eines Zustandes impliziert, dass alle Zustände, die in der reduzierten Form vorhanden sind, vom Anfangszustand aus erreicht werden können. Nicht erreichbare Zustände haben keinen Einfluss auf die Erreichbarkeit und das Verhalten des Generators.
Was bedeutet Ko-Erreichbarkeit in Bezug auf Generatoren?
Was ist die CoAc-Operation bei der Analyse von Generatoren?
Die CoAc-Operation definiert eine reduzierte Form eines Generators, die nur die ko-erreichbaren Zustände umfasst. Diese Operation hat im Allgemeinen Einfluss auf die Menge L(G) der von G erzeugten Strings, da durch ihre Anwendung auch erreichbare Zustände eliminiert werden können.
Wie wird die Ko-Erreichbarkeit eines Generators bestimmt?
Ein Generator ist ko-erreichbar, wenn er gleich seiner durch die CoAc-Operation reduzierten Form ist, d.h., G=CoAc(G). Ist der Generator identisch mit seiner CoAc-Form, sind alle Zustände im Generator ko-erreichbar.
Was ist der Unterschied zwischen Erreichbarkeit und Ko-Erreichbarkeit in DES?
Während Erreichbarkeit sich darauf bezieht, dass ein Zustand vom Anfangszustand aus erreicht werden kann, impliziert Ko-Erreichbarkeit, dass der Zustand von jedem Zustand aus erreichbar ist. Die CoAc-Operation hilft, die Ko-Erreichbarkeit zu analysieren, indem sie den Generator auf Zustände reduziert, die von jedem anderen Zustand aus erreichbar sind.
Wann ist ein Generator ko-erreichbar?
Wie kann Ko-Erreichbarkeit sprachentheoretisch dargestellt werden?
Was bewirkt die Anwendung von CoAc und Ac Operationen nacheinander auf einen Generator?
Die sequenzielle Anwendung von CoAc und Ac Operationen auf einen Generator führt zu einem Generator, der weder nicht erreichbare noch nicht ko-erreichbare Zustände besitzt. Dieser Prozess wird als Trimmen des Generators bezeichnet.
Was ist die Trim-Operation in der Analyse von DES?
Wann gilt ein Generator G als ‘Trim’?
Was bedeutet das Ergebnis von Trim?
dass das Ergebnis weder nicht noch ko-erreichbar ist
Was ist die Präfix Hülle?
Die Sprache der eigenen Elemente
Was ist ein Deadlock in der Analyse von Generatoren?
Was ist ein Livelock in der Analyse von Generatoren?
Ein Livelock ist ein Zustand oder eine Zustandsmenge in einem Generator G, von dem aus das System zwar Ereignisse generieren kann, die aber nie zu einem markierten Zustand führen. Bei einem Livelock bleibt das System in einer Schleife von Zuständen gefangen, ohne einen Fortschritt zu machen.
Was haben Deadlock und Livelock gemeinsam?
Sowohl Deadlock als auch Livelock verhindern, dass der Generator einen markierten Zustand erreicht. Im Falle eines Deadlocks kann der Generator keine weiteren Zustände erreichen, während bei einem Livelock das System aktiv bleibt, aber keinen nützlichen Fortschritt erzielt.
Was bedeutet Blockierung in DES?
Blockierung bedeutet, dass der Generator aufgrund eines Deadlocks oder Livelocks in einem Zustand gefangen ist, in dem ein markierter Zustand, der einen fertigen Auftrag darstellt, nicht erreicht werden kann.
Was besagt die Definition von Nichtblockierung in Bezug auf DES?
Was sind stark zusammenhängende Zustände in DES?
Was definiert eine stark zusammenhängende Zustandsmenge in DES?
Wie wird die Eigenschaft “stark zusammenhängend” in Bezug auf Zustandspaare und Zustandsmengen verstanden?
Wie wird ein Livelock in einem DES identifiziert?
Unter welchen Bedingungen kann ein Deadlock in einem DES vorhanden sein?
Ein Generator G kann einen Deadlock enthalten, wenn die Menge der stark zusammenhängenden Zustände
∣X∣ genau eins beträgt.
Wie erfolgt die Erreichbarkeitsanalyse bei Petrinetzen?
Die Erreichbarkeitsanalyse erfolgt bei Petrinetzen mit Hilfe des Erreichbarkeitsgrafen
Wie erfolgt die Erstellung des Erreichbarkeitsgrafen?
1)
Anfangszustand = Initialmarkierung
2)
Bestimme die Menge aller aktivierten Transitionen
3)
Bestimme alle Nachfolgemarkierungen
4)
Erweitere Erreichbarkeitsgraf um entsprechende neue Knoten
5)
Benenne die Kanten entsprechend der geschalteten Transitionen
Wie erfolgt die Analyse des Erreichbarkeitsgrafen?
▪
Existieren im Erreichbarkeitsgrafen Blattknoten (Knoten ohne abgehende Kanten) existiert ein Deadlock.
▪
Existieren keine Blattknoten im Erreichbarkeitsgrafen, so ist Petrinetz schwach lebendig.
▪
Ist Erreichbarkeitsgraf stark zusammenhängend und kommt jede Transition an mindestens einer Kante des Erreichbarkeitsgrafen vor, ist das Petrinetz lebendig.
Was versteht man unter Invarianten in Petrinetzen?
Invarianten sind Eigenschaften eines Petrinetzes, die unabhängig von der Anfangsmarkierung konstant bleiben und sich aus der Netztopologie ergeben. Sie werden durch die Analyse des Netzes ohne die Erstellung eines Erreichbarkeitsgraphen bestimmt.
Welche Arten von Invarianten gibt es in Petrinetzen und was beschreiben sie?
Es gibt zwei Arten von Invarianten:
- Transitionsinvarianten (T-Invarianten): Mengen von Transitionen, die beim Schalten die Markierung des Netzes reproduzieren und somit die Erreichbarkeit bestimmter Zustände ermöglichen.
- Stelleninvarianten (S-Invarianten): Mengen von Stellen, bei denen der gewichtete Markenzahlvektor durch das Schalten von Transitionen konstant bleibt, was die Erhaltung bestimmter Ressourcen oder Bedingungen anzeigt.
Gib eine typische analytische Netzbeschreibung an
Was ist eine T-Invariante in Petrinetzen?
Eine T-Invariante ist eine ganzzahlige, elementare Lösung des linearen Gleichungssystems, das die Netzmatrix N und einen Transitionsvektor T(k) verwendet, um die unveränderte Markierung eines Netzes zu beschreiben, nachdem alle Transitionen in T(k) geschaltet haben.
Was impliziert das Vorhandensein einer T-Invariante in einem Petrinetz?
Das Vorhandensein einer T-Invariante deutet darauf hin, dass das Netz in der Lage ist, zu einer bestimmten Markierung zurückzukehren, nachdem eine bestimmte Sequenz von Transitionen geschaltet hat. Es bedeutet jedoch nicht, dass jede Anfangsmarkierung reproduziert werden kann.
Wie viele T-Invarianten existieren in einem Petrinetz?
Wenn die Netzmatrix N eines Petrinetzes die Dimension n x m hat und der Rang von N gleich r ist, dann gibt es genau m-r T-Invarianten.
Welche Bedeutung haben T-Invarianten für die Analyse von Petrinetzen?
T-Invarianten helfen dabei, zyklische Verhaltensweisen im Netz zu identifizieren und zu verstehen, welche Transitionen in einem Zyklus involviert sind, der die Markierung unverändert lässt.
Was versteht man unter einer S-Invariante in Petrinetzen?
Eine S-Invariante ist eine ganzzahlige, nichttriviale und nichtnegative Lösung des linearen Gleichungssystems, das die Netzmatrix
�
N eines Petrinetzes verwendet, um Bedingungen zu identifizieren, unter denen die gewichtete Summe der Marken konstant bleibt, unabhängig davon, welche Transitionen schalten.
Was impliziert das Vorhandensein einer S-Invariante in einem Petrinetz?
Das Vorhandensein einer S-Invariante zeigt, dass es eine feste Gewichtung der Stellen gibt, bei der die Gesamtzahl der Marken im Netz während der Ausführung des Netzes konstant bleibt. Dies hilft dabei, Erhaltungsgesetze oder balancierte Flüsse im Netzwerk zu identifizieren.
Wie viele S-Invarianten existieren in einem Petrinetz?
Wenn die Netzmatrix
�
N eines Petrinetzes die Dimension n x m hat und der Rang von
�
N gleich r ist, dann gibt es genau n-r S-Invarianten.
