Logik und Formalisierung von Modellen Flashcards
Was bedeutet Erfüllbarkeit in der Aussagenlogik?
Eine Formel ist erfüllbar wenn es eine Bewertung der Formel (true/false) gibt.
Was bedeutet tautologisch in der Aussagenlogik?
Eine Formel ist tautologisch/allgemeingültig, wenn die Formel für jede Bewertung wahr ist.
Was bedeutet widerspruchsvoll in der Aussagenlogik?
Eine Formel ist widerspruchsvoll/unerfüllbar, wenn die Formel für jede Bewertung falsch ist.
Was bedeutet falsifizierbar in der Aussagenlogik?
Eine Formel ist falsifizierbar, wenn es für die Formel eine Bewertung gibt, deren Wert falsch ist.
Welche Operatoren gibt es in der Aussagenlogik?
- NICHT: Es regnet nicht. ¬R
- ODER: Es regnet oder die Straße ist nass. R ∨ S
- UND: Es regnet und die Straße ist nass. R ∧ S
- WENN/DANN: Wenn es regnet, ist die Straße nass. R → S
- GENAU WENN/DANN: Genau dann, wenn es regnet, ist die Straße nass. R ↔ S
- ENTWEDER/ODER: Entweder die Straße ist nass, oder es regnet. (R ∨ S) ∧ (¬R ∨ ¬S)
Wofür wird DEVS angewendet?
DEVS oder DES (discrete event simulation) wird zur Formalisierung und Modellierung ereignisbasierter diskreter Systeme verwendet.
Es können sowohl gekoppelte als auch atomare Modelle beschrieben werden.
Welche grundlegenden Bestandteile hat ein atomates Modell in DEVS?
AM = (X, Y, S, δint, δext, ta, λ)
- 7-er Tupel
- Bestmöglich mit hoher Kohäsion
X: Eingabemenge
Y: Ausgabemenge
S: Menge der Zustände
ta: S → R+: Zeitschrittfunktion, die jedem Zustand eine Zeitspanne assoziiert, in der der Zustand von alleine bestehen bleibt, bevor ein interner Zustandsübergang ausgelöst wird
δint : S → S: interne Übergangsfunktion auf Basis der Zeitspanne
δext : Q × X → S: externe Übergangsfunktion, getriggert durch äußere Ereignisse
λ : S → Y: Ausgabefunktion
Welche grundlegenden Bestandteile hat ein atomares Modell in PDEVS?
PDEVS - AM = (X, Y , S, ta, δint , δext , δcon, λ)
- 8-er Tupel
- Erweiterung von DEVS um gleichzeitig stattfindende Ereignisse
X: Eingabemenge
Y: Ausgabemenge
S: Menge der Zustände
ta: S → R+: Zeitschrittfunktion, die jedem Zustand eine Zeitspanne assoziiert, in der der Zustand von alleine bestehen bleibt, bevor ein interner Zustandsübergang ausgelöst wird
δint : S → S: interne Übergangsfunktion auf Basis der Zeitspanne
δext : Q × X → S: externe Übergangsfunktion, getriggert durch äußere Ereignisse
δcon: konfluente Übergangsfunktion, wird ausgeführt, wenn δint und δext auf gleichem Zeitpunkt liegen, durch Parallelität wird keine Select Funktion benötigt
λ : S → Y: Ausgabefunktion
Welche grundlegenden Bestandteile hat ein gekoppeltes Modell in DEVS?
CM = (X, Y, D, Md. EIC, EOC, IC, Select)
- 8-er Tupel
- welche Unterkomponenten gehören zum System und wie sind sie miteinander verbunden
- haben keinen internen Zustand, jeder ergibt sich aus der Menge aller Zustände aus den Subsystemen
X: Eingabemenge
Y: Ausgabemenge
D: Menge der Namen der Komponenten
M(d): DEVS-Modell als Bestandteil des gekoppelten Modells
EIC: Menge der externen Eingabekopplungen
EOC: Menge der externen Ausgabekopplungen
IC: Menge der internen Kopplungen
Select: 2^D → D: die Funktion, die bestimmt, welche der Komponenten Priorität hat, wenn mehrere Komponenten ein internes Ereignis ausführen wollen
Inwiefern unterscheiden sich atomare und gekoppelte Modelle?
Atomare Modelle zeigen ein System stets in einem bestimmten Zustand.
Gekoppelte Modelle haben keinen eigenen Zustand, dieser ergibt sich aus der Menge aller Zustände der Kindmodelle.
In beiden Fällen können die Folgezustände sicher berechnet werden.
Welche Vor- und Nachteile besitzt das klassische DEVS?
Vorteile:
- Ermöglicht die Modellierung und Simulation komplexer Systeme
- Längere Abläufe können in kurzer Zeit simuliert werden
- Genaue Berechenbarkeit der Zustände
Nachteile:
- Parallele Ereignisse können nur sequenziell ausgeführt werden
- Statische Struktur erlaubt keine Veränderung der Modellbestandteile, wenn sich das Modell verändert/es fortgeschrieben wird
=> Für die Nachteile gibt es jeweils entsprechende Erweiterungen des DEVS
Inwiefern unterscheidet sich PDEVS von DEVS?
PDEVS ermöglicht grundsätzlich die parallele Zustandsänderung.
Daher wird aus der Eingabemenge X statt einer Menge an Zuständen nun eine Menge aus Tupeln von Eingabeort p und Eingabewert v.
Parallel dazu wird aus der Ausgabemenge Y eine Menge aus Tupeln von Ausgabeort und Ausgabewert.
Entscheidend ist, dass die vergangene Zeit im PDEVS immer kleiner ist als die Summe der Zeitspannen einzelner Zustände. Ohne die parallele Verarbeitung kann sie zwar kleiner sein, kann aber auch der Summe entsprechen.
Was sind die grundlegenden Bestandteile eines zellulären Automaten?
L: d-dimensionaler Zellraum => L ist eine Menge an homogen über den Raum verteilter Zellen (Zellen sind also gleichmäßig angeordnet).
Nb(r): Liste der Nachbarn einer Zelle r, wobei b die Nummer im Koordinatensystem darstellt
S: endlicher Zustandsraum
G: aktueller Zustand des zellulären Automaten
Ginit: initialer Zustand des zellulären Automaten
R: Zustandsüberführungsregel
Wie funktioniert ein zellulärer Automat?
Zunächst werden für jede Zelle im Zellraum L alle Nachbarn betrachtet. Dann werden entsprechend der Zustandsübergangsregel (z.B. wenn 4 deiner 8 Nachbarn weiß sind, werde schwarz) alle Zellen quasi vorgemerkt und im letzten Schritt alle Zellen gleichzeitig auf ihren neuen Zustand geschaltet.
Was sind die Vor- und Nachteile eines zellulären Automaten?
Vorteile:
- Modellierung räumlich diskreter Systeme mit n Dimensionen möglich
- Modellierung teilweise komplexer biologischer oder chemischer Systeme möglich
Nachteile:
- Oft aufwendige Initialisierung der Dimensionen (jeder Zellzustand muss bei Simulationsbeginn bekannt sein)
- Simulation terminiert nicht zwangsläufig
- Statisch (zwar ändert sich der Zellraum fortlaufend, aber die Regeln verändern sich nicht)
Wofür werden Petrinetze verwendet und was ist das zentrale Konzept?
Petrinetze werden zur Modellierung zeitdiskreter Systeme mit nebenläufigen Prozessen verwendet. Dabei werden die Prozesse durch das Verbrauchen und Generieren von Ressourcen gesteuert.
Was sind die zwei zentralen Grundsätze beim Modellieren von Petrinetzen?
- Sicherheit (bad things never happen): Anforderungen an eine Stelle bzw. Markierungen, z.B. in Form von oberen und unteren Schranken
- Lebendigkeit (good things eventually happen): Anforderungen an die Transitionen, dass z.B. bestimmte Markierungen bewahrt werden und das System nicht stecken bleibt
Wie ist ein Petrinetz formell definiert?
Petrinetze sind gerichtete, bipartite Graphen.
Petrinetze haben 2 verschiedene Arten von Knoten - Stellen und Transitionen.
Ein Netz ist dabei definiert als ein Tripel aus Stellen, Transitionen und Flussrelationen:
N = (S, T, F)
S und T zusammen dürfen dabei nicht leer sein. F ergibt sich als Teilmenge der Wertepaare S x T und T x S => es kann nicht mehr Flussrelationen geben als Knoten Beziehungen zueinander haben.
Zusätzlich dazu gibt es noch Kantengewichte W für jede Flussrelation F, Kapazitäten K für jede Stelle S und jede Transition T und eine Anfangsmarkierung M0
Wann ist eine Transition aktiviert?
Eine Aktivierung ist quasi die Vorstufe der tatsächlichen Schaltung der Transition.
Eine Transition gilt als aktiviert, wenn ihr Vorbereich mindestens eine Marke hat und der Nachbereich noch mindestens eine Marke aufnehmen kann.
Wie entstehen bei einem Petrinetz Konflikte?
Konflikte entstehen z.B. bei der Zuordnung von Ressourcen, wenn eine Ressource durch einen fork nicht eindeutig einer Transition zugeordnet werden kann.
Wann gilt eine Transition als aktivierbar?
Eine Transition gilt als aktivierbar, wenn sie unter mindestens einer Folgemarkierung aktiviert ist.
Welche Formen der Lebendigkeit gibt es und wann sind diese gegeben?
Lebendige Transition: wenn alle Folgemarkierungen aktivierbar sind
Schwach lebendiges/deadlockfreies System: unter jeder erreichbaren Markierung ist mindestens eine Transition aktiviert.
Stark lebendiges System: aus jeder erreichbaren Markierung ist jede Transition aktivierbar.
Totes System: keine Transition ist aktivierbar.
Was sind die Vor- und Nachteile der Modellierung mit Petrinetzen?
Vorteile:
- Ressourcenverbrauch/Verteilung kann modelliert werden
- Es können Aussagen über ein Netz getroffen werden, ohne dass es berechnet werden muss
- Allgemeingültige Aussagen können über ein System getroffen werden
Nachteile:
- aufwendige Erstellung
- sehr hohe Komplexität bei vergleichsweise einfachen Sachverhalten
Welche Netzklassen gibt es bei Petrinetzen?
- Zustandsmaschine
- Synchronisationsgraph
- Kausalnetz
- Free Choice Netz
- Asymmetric Choice Netz
- Dissymmetric Choice Netz
Atomares Modell
Was ist XDEVS?
Alle möglichen Eingabewerte, die von außen reinkommen kommen
(Rauch beim Rauchmelder)
Atomares Modell
Was ist SDEVS?
Menge aller möglichen Zustände des Modells.
Beispiel Glühbirne:
S =
Atomares Modell
Wofür steht ta(s)(s ∈ S)
- Die Zeitschrittfunktion ta(s) assoziiert mit jedem Zustand eine Zeitspanne, die dieser Zustand von sich aus bestehen bleibt, bevor ein interner Zustandsübergang ausgelöst wird
Wofür steht dies im atomaren Modell?
δ ext(s, e, x)
Kombination der möglichen inneren Zustände. Daraus ergibt sich der äußere Zustand (Rückgabewert).
alarm_smoke, e, lowbat –> alarm_Smoke
Was beschreibt ein Metamodell?
- Aus welchen Elementen können Modelle bestehen und wie stehen sie in Beziehung zueinander
- Sind ebenfalls Modelle
- Beispiele: Archimate für die Möglichkeit, Geschäftsprozesse auf der Businesslayer darzustellen
- Welche Beziehungen sind zwischen den Entitäten grundsätzlich erlaubt
Was unterschiedet den Kellerautomaten vom NEA, DEA ?
- Der Kellerautomat (PDA) verfügt über einen Keller / Stack = Speicher
- Im Stack werden Zeichen abgelegt, die der Automat speichert und nach dem LIFO Prinzip ausgeben kann
- Der Stack ist unendlich groß, am Ende des Stacks steht immer ein #
Notation:
- q0 = aktueller Zustand
- a = gelesene Zeichen aus dem Wort
- A = gelesenes Zeichen aus dem Stack
- q1 = gewollter Zustand
- B = welche Zeichen sollen in den Stack geschrieben werden
Wie definiert sich uninformierte / informierte Suche?
- Algorithmen, die in einem Suchraum nach Mustern oder Objekten mit bestimmten Eigenschaften suchen
- Man unterscheidet einfache und heuristische Suchen (einfach = intuititv, heuristisch = Einbezug von Wissen über Suchraum)
- Als Lösung kann Zielzustand, Pfad zum Ziel oder Reihenfolge von Aktionen gelten
- Ist der Suchraum endlich, führt sie Suche mit geeigneter Strategie immer zu einem Ergebnis
- Informierte Suchen benötigen stets zusätzliche Informationen, uninformierte kommen dagegen mit dem Berechnungsalgorithmus an sich aus
Welche Beispiele für uninformierte Suche gibt es?
Uninformierte Suche
- Breitensuche
- Uniform Cost
- Tiefensuche
- Tiefenbeschränkte Suche
- Iterativ vertiefende Tiefensuche
- Bidirektionale Suche
Welche Beispiele für informierte Suche gibt es?
- Gierige Breitensuche
- A* Suche
- Speicherbegrenzte heuristische Suche
Was sind mögliche Transformationen von Modellen?
DSL → GPL (bspw. wenn sich Problemraum vergrößert hat)
Klassendiagram → XML (bspw. für Protokollerstellung für Datenaustausch Front- Backend)
Klassendiagramm → JSON (bspw. für Typen Definition)
BPMN → Petrinetz (bspw. um Ressourcenverbrauch modellieren zu können)
BPMN → Petrinetz (bspw. für Validierung von BPMN)
Endogene Transformation → gleiche Syntax (Java → Java)
Exogene Transformation → unterschiedliche Syntax
