Vorlesung“Modellierung” Wintersemester2013/14 ... · Modellierung Vorlesung“Modellierung” Wintersemester2013/14 (FolienvonProf.B.König) Prof.NorbertFuhr Übungsleitung:ThomasBeckers

Modellierung

Vorlesung “Modellierung”

Wintersemester 2013/14

(Folien von Prof. B. König)

Prof. Norbert FuhrÜbungsleitung: Thomas Beckers

Modellierung

Das heutige ProgrammOrganisatorisches

VorstellungAblauf der Vorlesung und der ÜbungenPrüfungLiteratur & Folien

Einführung und Motivation: Was ist Modellierung?Inhalt der weiteren Vorlesung

Modellierung

Wer sind wir?

Dozent: Prof. Dr.-Ing. Norbert FuhrRaum LF 135E-Mail: [email protected]: nach Vereinbarung

Übungsleitung:Dipl.-Inform. Thomas Beckers

Raum LF 138E-Mail: [email protected]

Modellierung

Wer sind wir?

Studentische Hilfskräfte (Korrektur & Betreuung vonÜbungsgruppen):Sebastian Schweitzer

E-Mail: [email protected] Reichwein

E-Mail: [email protected] Wohland

E-Mail: [email protected] Weiß

E-Mail: [email protected]

Modellierung

Wer sind wir?

Web-Seite:http://www.is.inf.uni-due.de/courses/mod_ws13/

Regelmäßig vorbeischauen!

Modellierung

Vorlesungstermine

Vorlesungstermin:Mittwoch, 14:00-16:00 Uhr, im Raum LB 104

Modellierung

Aktives Lernen

Was von einer Vorlesung ’hängenbleibt’Am Ende der Stunde: 50%Nach einer Woche: 15%Am Ende des Semesters: Nicht messbar

„Sage es mir, und ich vergesse es.Zeige es mir, und ich erinnere mich.Lass es mich tun, und ich behalte es ein Leben lang“

Modellierung

Hinweise zu den Übungen

Besuchen Sie die Übungen und machen Sie die Hausaufgaben!Diesen Stoff kann man nur durch regelmäßiges Üben erlernen.Auswendiglernen hilft nicht besonders viel.Die Übungen beginnen in der zweiten Semesterwoche amMittwoch, den 23. Oktober.

Modellierung

Termine der Übungsgruppen/Tutorien

Übungsgruppen:

Mo, 16:00 - 17:00 Uhr, Raum LE 120 (Gruppe 1)Mo, 17:00 - 18:00 Uhr, Raum LE 120 (Gruppe 2)Di, 10:00 - 11:00 Uhr, Raum LE 120 (Gruppe 3)Di, 11:00 - 12:00 Uhr, Raum LE 120 (Gruppe 4)Di, 12:00 - 13:00 Uhr, Raum LK 051 (Gruppe 5)Di, 13:00 - 14:00 Uhr, Raum LK 051 (Gruppe 6)Do, 10:00 - 11:00 Uhr, Raum LF 125 (Gruppe 7)Do, 11:00 - 12:00 Uhr, Raum LF 125 (Gruppe 8)Do, 14:00 - 15:00 Uhr, Raum LE 120 (Gruppe 9)Do, 15:00 - 16:00 Uhr, Raum LE 120 (Gruppe 10)

Modellierung


Anmeldung über Webseite zur Vorlesung (bis einschließlich17.10.)Endgültige Gruppenaufteilung wird nach Ablauf derAnmeldefrist auf der Webseite bekanntgegeben.

Modellierung

Hinweise zu den ÜbungenMatrikelnummern

Nummern auf Studentenausweis, z.B.DS0075432100 ES0212345601Nur der grün markierte Teil ist die Matrikelnummer.

Modellierung


Das Übungsblatt wird jeweils am Montag ins Netz gestellt.Das erste Übungsblatt wird am 15. Oktober bereitgestellt.Die schriftlichen Aufgaben müssen bis spätestens Sonntag,23:59 Uhr, abgegeben werden.Abgabe durch Formular auf Webseite zur Vorlesung (nur alsPDF)Besprechung in der darauffolgenden WocheBitte geben Sie auf Ihrer Lösung deutlich Ihren Namen, IhreMatrikelnummer und Ihre Gruppennumer an.Sie dürfen in Einer- oder Zweier-Gruppen abgeben.Plagiate werden mit 0 Punkten bewertet.

Modellierung

Klausur

Die Vorlesung wird durch eine Klausur am Ende des Semestersgeprüft:

Termin: Siehe Webseite

Die Anmeldung erfolgt über das Prüfungsamt

Modellierung

Klausur

Es gibt folgende Bonusregelung:

50% der Hausaufgabenpunkten80% der Hausaufgaben bearbeitet (Aufgaben mit > 0Punkten)Auswirkung: Verbesserung um eine Notenstufe; z.B. von 2,3auf 2,0

Modellierung

Literatur

Bernd Baumgarten: Petri-Netze.Grundlagen und Anwendungen,Spektrum, 1996.

Das Buch ist vergriffen, ist aber in der Bibliothek verfügbar.

Modellierung

Literatur

Wolfgang Reisig: Petri-Netze –Eine Einführung, Springer, 1985.

Ebenfalls vergriffen und in der Bibliothek verfügbar. Es gibt jedochelektronisch eine neue Version unter:http://www2.informatik.hu-berlin.de/top/pnene_buch/

Modellierung

Literatur

L. Priese, H. Wimmel:Petri-Netze, Springer, 2008.

Online verfügbar unterhttp://www.springerlink.com/content/n54711/(Zugriff über Uni-Rechner)

Modellierung

Literatur

Tadao Murata: Petri Nets: Properties, Analysis and Applications.Proc. of the IEEE, 77(4), 1989.

Online verfügbar als PDF:http://www.cs.unc.edu/˜montek/teaching/spring-04/murata-petrinets.pdf

Modellierung

Literatur

G. Booch, J. Rumbaugh, I.Jacobson: The Unified ModelingLanguage User Guide, AddisonWesley, 2005.

Modellierung

Literatur

M. Jeckle, C. Rupp, J. Hahn, B.Zengler, S. Queins: UML 2glasklar, Hanser Fachbuch, 2007.

Modellierung

Literatur

R. Miles, K. Hamilton: LearningUML 2.0, O’Reilly, 2006.

Online verfügbar unterhttp://proquest.safaribooksonline.com/0596009828(Zugriff über Uni-Rechner)

Modellierung

Literatur

Christoph Kecher: UML 2.0 - Dasumfassende Handbuch. GalileoPress, 2006.

Buch ist in der Bibliothek verfügbar.

Modellierung

Literatur

Perdita Stevens, Rob Pooley:UML - Softwareentwicklung mitObjekten und Komponenten.Pearson, 2001.

Buch (vor allem das englische Original) ist in der Bibliothekverfügbar.

Modellierung

Literatur

David Harel: Statecharts: a visual formalism for complex systems.Science of Computer Programming 8, pp 231-274. North-Holland1987.

Online verfügbar als PDF:http://www.wisdom.weizmann.ac.il/˜dharel/

SCANNED.PAPERS/Statecharts.pdf

Modellierung

Literatur

Hinweise:

Die Bücher sind als Ergänzung gedacht, sie präsentieren denStoff oft aus einem anderen Blickwinkel.Sehen Sie sich die Bücher erst an, bevor Sie sie kaufen. Nichtjede/r kommt mit jedem Buch zurecht.Die Bibliothek (LK) ist ein guter Platz um nach Büchern zustöbern (Informatik-Abteilung im 1. Stock, Lehrbuchsammlungim Keller)Wagen Sie sich auch an englische Literatur, englischeFachsprache ist zumeist gut verständlich

Modellierung

Folien

Folien werdenim Web als PDF bereitgestelltbei Bedarf aktualisiert /korrigiert

ModellierungEinführung in die Modellierung

Was ist Modellierung?

ModellEin Modell ist eine Repräsentation eines Systems von Objekten,Beziehungen und/oder Abläufen. Ein Modell vereinfacht undabstrahiert dabei im allgemeinen das repräsentierte System.

SystemDer Begriff System wird hier sehr allgemein verwendet. Er kannentweder

einen Teil der Realität oderein noch nicht bestehendes Gebilde, das noch erstellt werdenmuss,

bezeichnen.


Was ist Modellierung?

ModellierungModellierung ist der Prozess, bei dem ein Modell eines Systemserstellt wird.

Warum sollte man modellieren? Um ein System zu entwerfen, besser zu verstehen, zuvisualisieren, zu simulieren, . . .

Um etwas konkreter zu werden betrachten wir den Begriff derModellierung in verschiedenen Disziplinen (Physik, Biologie,Klimaforschung, . . . )


Modellierung in der Physik

AtommodelleAtome bestehen aus Protonen, Neutronen und Elektronen. Wiediese Teilchen zusammenwirken, wird in verschiedenenAtommodellen beschrieben, die sich im Laufe der Zeit immerwieder geändert haben.


Modellierung in der Biologie

ZitronensäurezyklusDer Zitronensäurezyklus oder Citratzyklus modelliert den Abbauorganischer Stoffe im Körper.


Modellierung in der Klimaforschung

Modell des Transports von Gasen in der Atmosphäre


Arten von Modellen

visuell vs. textuellNicht alle Modelle sind visuell bzw. graphisch. Auch mit textuellenBeschreibunge und Formeln kann man modellieren (siehebeispielsweise mathematische Modelle).Dennoch werden häufig graphische Darstellungen benutzt, auch ausdidaktischen Gründen und um sich besser über die Modelleverständigen zu können.


Arten von Modellen

qualitativ vs. quantitativqualitative Modelle: Welche Objekte gibt es? Was passiert?Warum passiert es? In welcher Reihenfolge geschehen dieEreignisse? Was sind die kausalen Zusammenhänge? WelchePhänomene treten auf?quantitative Modelle: Wieviele Objekte gibt es? Wie langedauert ein Vorgang? Wie wahrscheinlich ist ein bestimmtesEreignis?


Arten von Modellen

black box vs. white boxblack box: nur das von außen beobachtbare Verhalten wirdbeschriebenwhite box: es wird auch beschrieben, wie das von außenbeobachtbare Verhalten im “Inneren” des Systems erzeugt wird


Arten von Modellen

statisch vs. dynamischein statisches Modell beschreibt einen Zustand des Systems zueinem bestimmten Zeitpunktein dynamisches Modell beschreibt hingegen auch, wie dasSystem sich entwickelt (ein oder mehrere mögliche Abläufeoder sogar das gesamte Systemverhalten)


Arten von Modellen

nicht-formell vs. semi-formal vs. formalJe nach Exaktheit der Modelle erhält man:

formale Modelle, die vollkommen exakt in ihren Aussagen sind(vor allem mathematische Modelle)semi-formale Modelle, die teilweise exakt sind, jedoch nichtalles vollständig spezifierennicht-formale Modelle, die als grobe Richtlinie dienen können,jedoch eher vage Aussagen machen


Probleme mit nicht-formalen Modellen

Natürliche Sprache ist nicht immer eindeutig.

Beispiel:

Ich sah den Mann auf dem Berg mit dem Fernrohr.



(((Ich sah den Mann) auf dem Berg) mit dem Fernrohr)



((Ich sah (den Mann auf dem Berg)) mit dem Fernrohr)



((Ich sah den Mann) (auf dem Berg mit dem Fernrohr))



(Ich sah ((den Mann auf dem Berg) mit dem Fernrohr))



(Ich sah (den Mann (auf dem Berg mit dem Fernrohr)))



(((Ich sah den Mann) auf demBerg) mit dem Fernrohr)

((Ich sah (den Mann auf demBerg)) mit dem Fernrohr)

((Ich sah den Mann) (auf demBerg mit dem Fernrohr))

(Ich sah ((den Mann auf demBerg) mit dem Fernrohr))

(Ich sah (den Mann (auf demBerg mit dem Fernrohr)))

5 möglicheInterpretationen!



Auch graphische Darstellungen können uneindeutig sein:


Modellierung in der Informatik

In dieser Vorlesung geht es um Modellierungsmethoden in derInformatik. Diese werden zum Entwurf folgender Systemeeingesetzt:

(Objekt-orientierte) Programme(Große) Software-SystemeBenutzeroberflächenDatenbankenVirtual Reality, Computer-Spiele. . .


Wozu ist Modellierung gut?

Wozu benötigt man Modelle?

je komplexer ein System ist, desto wichtiger ist es, einen Plan zuerstellen, bevor man beginnt das System zu konstruieren

dies führt zu:Vermeidung von Fehlernbesserer Qualitätniedrigeren Kostenbesserer Dokumentation und Wiederverwendbarkeit



Analogie: Bau eines Hauses

Beim Bau einer Hundehütte kannman zumeist ohne große Planungvorgehen. Die Hütte kann voneiner einzelnen Person erstelltwerden und ein Hund hat zumeistkeine großen Anforderungen.




Beim Bau eines Einfamilienhausesist Planung viel wichtiger. DieFamilie ist anspruchsvoller als einHund, Bauvorschriften müsseneingehalten werden undvermutlich werden nicht alleArbeiten von derselben Persondurchgeführt.




Beim Bau eines Hochhauses istohne Erstellung eines detailliertenPlans bzw. Modells nichtmöglich. Das Risiko, Fehler zumachen ist sehr groß, und Fehlerkönnen extrem kostspielig werden.



Modellierung ist in der Informatik weniger verbreitet als in denIngenieurwissenschaften, aber ebenso wichtig.

Schwierigkeiten beim Entwurf komplexer SystemeMenschen können sich komplexe Systeme normalerweise nichtin vollem Umfang vorstellenBei mehreren Menschen/Entwicklern gibt es unterschiedlicheMeinungen darüber, wie das System aussehen muss Modelle dienen zu Kommunikation!Es ist schwer ein System zu dokumentieren und zu warten, dasnicht explizit modelliert ist.

Feststellung (nach Glinz)

Die Entwicklung von Klein-Software unterscheidet sich fundamentalvon der Entwicklung größerer Software.


Probleme bei der Entwicklung großer Systeme

Klein-Groß-Gegensätze in der Software-Entwicklung:

klein großProgramme bis ungefähr 300Zeilen Längere Programme

Für den Eigengebrauch Für den Gebrauch durchDritte

Vage Zielsetzung genügt, dasProdukt ist seine eigeneSpezifikation

Genaue Zielbestimmung, d.h.die Spezifikation vonAnforderungen, erforderlich



klein groß

Ein Schritt vom Problem zurLösung genügt: Lösung wirddirekt programmiert

Mehrere Schritte vomProblem zur Lösungerforderlich: Spezifikation,Konzept, Entwurf undProgrammieren der Teile,Zusammensetzen,Inbetriebnahme

Validierung(Überprüfung/Testen) undnötige Korrekturen finden amEndprodukt statt

Auf jeden Entwicklungsschrittmuss ein Prüfschritt folgen,sonst kann Endergebnisunbrauchbar werden



klein groß

Eine Person entwickelt: keineKooperation undKommunikation erforderlich

Mehrere Personen entwickelngemeinsam: Koordination undKommunikation notwendig

Komplexität des Problems inder Regel klein, Strukturierenund Behalten der Übersichtnicht schwierig

Komplexität des Problemsgrößer bis sehr groß, expliziteMaßnahmen zurStrukturierung undModularisierung erforderlich



klein großSoftware besteht aus wenigenKomponenten

Software besteht aus vielenKomponenten, die spezielleMaßnahmen zurKomponentenverwaltungerfordern

In der Regel wird keineDokumentation erstellt Dokumentation dringend

erforderlich, damit Softwarewirtschaftlich betrieben undgepflegt werden kann



klein groß

Keine Planung undProjektorganisationerforderlich

Planung undProjektorganisation zwingenderforderlich für einezielgerichtete, wirtschaftlicheEntwicklung



Explosion der Anzahl der Kommunikationspfade bei Anstieg derEntwicklerzahl:

Quantensprung:Kommunikationwird erforderlich

Quantensprung:Zahl der Komm.pfadeübersteigt Zahlder Personen

1 2 3 4 5 6

0 1 3 6 10 15

Anzahl Personen:

Anzahl Komm.pfade:



Die Problematik bei der Erstellung großer Programme sieht manauch an folgenden Zahlen (nach Boehm 1981):

40% der Zeit wird mit der Entwicklung verbracht (davon:15% Spezifikation; 8% Codierung; 16% Test)60% der Zeit wird für die Wartung aufgewendet(12% Anpassung; 36% Erweiterung und Verbesserung;12% Fehlerbehebung)



Aus diesen Fakten und Zahlen ergibt sich folgende Konsequenz:

Vor allem bei der Erstellung großer Systeme ist es unbedingterforderlich, zunächst das System zu modellieren, bevor esimplementiert bzw. konstruiert wird.

Meistens sind auch mehrere verschiedene Modelle erforderlich.

Aus Gründen der Übersichtlichkeit und Didaktik werden wir uns inder Vorlesung jedoch hauptsächlich mit kleinen Modellen befassen.


Beispiel: Wolf, Ziege, Kohlkopf

Wir modellieren folgendes System, um eine möglich Lösung zufinden.

Wolf-Ziege-Kohlkopf-ProblemEin Bauer will einen Fluss überqueren. Er hat einen Wolf, eineZiege und einen Kohlkopf bei sich. Wenn sie alleingelassen werden,so frisst der Wolf die Ziege, und die Ziege den Kohlkopf. ZurÜberquerung des Flusses steht ein Boot mit zwei Plätzen zurVerfügung. Nur der Bauer kann rudern und er kann das Bootentweder allein benutzen oder ein Tier oder den Kohlkopfmitnehmen.



Statisches Modell I: Beteiligte Akteure/Objekte



Statisches Modell II: Fress- und Eigentumsbeziehungen zwischenden Akteuren

besitzt

��

besitzt�� besitzt

��

frisst // frisst //



Ausgangssituation: vor Überquerung des Flusses

Boot



Zielsituation: nach Überquerung des Flusses

Boot



Dynamisches Modell: Beispielablauf, erster SchrittBauer und Wolf setzen gemeinsam über

→

→ Boot



Dynamisches Modell: Beispielablauf, zweiter SchrittZiege frisst Kohlkopf

Boot


Syntax und Semantik

Man unterscheidet bei der Modellierung zwischen:

Syntax: Symbole und Diagramme, die für die Darstellung desModells genutzt werden dürfenIm Beispiel: Bild der Ziege, blaue Fläche, etc.Semantik: Bedeutung, die sich hinter den Symbolen verbirgtIm Beispiel: Die blaue Fläche symbolisiert den Fluss.

Die Pfeile bedeuten: “Fluss wird überquert”

Zu einer Syntax gibt es nicht immer eine dazugehörige Semantik(im Beispiel ist die Semantik sehr vage).Wünschenswert ist jedoch im allgemeinen, dass die Bedeutung allerSymbole möglichst präzise festgelegt wird.Einigung auf eine gemeinsame Sprache/Notation, auf gemeinsamevisuelle Beschreibungen zur Vermeidung von Missverständnissen.


Weitere Aspekte

Weitere wichtige Gesichtspunkte sind:

Analyse:Ist das Modell korrekt? Ist es in sich konsistent?Stimmt das Modell mit der späteren Implementierungüberein? (Hier werden Verfahren zum Testen und zurVerifikation benötigt)

Werkzeuge, Software-Tools: werden benötigt zum Zeichnen,zum Darstellen (Wechsel zwischen verschiedenenDarstellungen), zum Archivieren, zur Code-Generierung, zurAnalyse, . . .


Inhalt der Vorlesung

InhaltMathematische GrundlagenGraphen für statische und dynamische SystembeschreibungenPetrinetzeUML (Unified Modeling Language)


Graphen

Graphen bestehen aus Knoten undKanten.Sie können eingesetzt werden für

Statische Modellierung:Komponenten undBeziehungen zwischen denKomponentenDynamische Modellierung:Zustände undZustandsübergänge in FormeinesZustandsübergangsdiagramms

1 2

3

a

bc


Petrinetze

Modell für nebenläufige undverteilte Systeme, das diegemeinsame Nutzung vonRessourcen beschreibt.Schwerpunkt liegt auf derModellierung des dynamischenVerhaltens.Etabliertes Modell, das vielfältigeingesetzt wird.Formale Semantik.Erfunden von Carl Adam Petri(1962).

MarkeStelle

Transition


UML: Unified Modeling Language

Standard-Modellierungssprache fürSoftware Engineering.Basiert auf objekt-orientiertenKonzepten.Sehr umfangreich, enthält vieleverschiedene Typen von Modellen.Entwickelt von Grady Booch,James Rumbaugh, Ivar Jacobson(1997).


Inhalt der Vorlesung

Die vorgestellten Modellierungsmethoden sind nicht die einzigenModellierungsmethoden in der Informatik.

Hier: Fokus auf visuelle Modellierung mit Hilfe von Diagrammen

Mögliche Alternative: algebraische Modellierungsmethoden, die sichstärker an der Mathematik orientieren


Ein weiteres Beispiel: Einschreiben an der Universität

Szenario: Eine Reorganisation der Universität, und insbesondere desStudiensekretariats, das für Einschreibungen zuständig ist, steht an.

Hierzu soll der Ablauf des Einschreibens neuer Studierendermodelliert werden . . .



Darstellung des zeitlichen Ablaufs durch Symbolisieren derbeteiligten Partner als Linien und der Kommunikation durch Pfeile(Ausschnitt).

Universität Student/in Studiensekretariat

Studieninformation anfordern

Studieninformation

AufstellenBonautomat

Anfordern Bon

Ausgeben BonUnterlagen schicken

Besuch der Einführungs-veranstaltung

. . . . . . . . .

zeitlicherAblauf



Solche Diagramme sind übrigens Bestandteil von UML. Sie werdenSequenzdiagramme (engl. sequence diagrams, auch messagesequence charts) genannt.


Notation: Mengen und Funktionen

MengeMenge M von Elementen, wird beschrieben als Aufzählung

M = {0, 2, 4, 6, 8, . . . }

oder als Menge von Elementen mit einer bestimmten Eigenschaft

M = {n | n ∈ N0 und n gerade}.

Allgemeines Format:M = {x | P(x)}

(M ist Menge aller Elemente x , die die Eigenschaft P erfüllen.)



Bemerkungen:

Die Elemente einer Menge sind ungeordnet, d.h., ihre Ordnungspielt keine Rolle. Beispielsweise gilt:

{1, 2, 3} = {1, 3, 2} = {2, 1, 3} = {2, 3, 1} = {3, 1, 2} = {3, 2, 1}

Ein Element kann nicht “mehrfach” in einer Menge auftreten.Es ist entweder in der Menge, oder es ist nicht in der Menge.Beispielsweise gilt:

{1, 2, 3} 6= {1, 2, 3, 4} = {1, 2, 3, 4, 4}



Element einer MengeWir schreiben a ∈ M, falls ein Element a in der Menge M enthaltenist.

Anzahl der Elemente einer Menge

Für eine Menge M gibt |M| die Anzahl ihrer Elemente an.

TeilmengenbeziehungWir schreiben A ⊆ B , falls jedes Element von A auch in Benthalten ist. Die Relation ⊆ heißt auch Inklusion.



VereinigungDie Vereinigung zweier Mengen M1,M2 ist die Menge M, die dieElemente enthält, die in M1 oder M2 vorkommen. Man schreibtdafür M1 ∪M2.

M1 ∪M2 = {a | a ∈ M1 oder a ∈ M2}

SchnittDer Schnitt zweier Mengen M1,M2 ist die Menge M, die dieElemente enthält, die sowohl in M1 als auch in M2 vorkommen.Man schreibt dafür M1 ∩M2.

M1 ∩M2 = {a | a ∈ M1 und a ∈ M2}



KreuzproduktSeien A,B zwei Menge. Die Menge A× B is die Menge aller Paare(a, b), wobei das erste Element des Paars aus A, das zweite aus Bkommt.

A× B = {(a, b) | a ∈ A, b ∈ B}

Beispiel:{1, 2} × {3, 4, 5} = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}

Es gilt: |A× B| = |A| · |B| (für endliche Menge A,B).



Bemerkungen:

Wir betrachten nicht nur Paare, sondern auch sogenannteTupel, bestehend aus mehreren Elementen. Ein Tupel(a1, . . . , an) bestehend aus n Elementen heißt auch n-Tupel.In einem Tupel sind die Elemente geordnet! Beispielsweise gilt:

(1, 2, 3) 6= (1, 3, 2) ∈ N0 × N0 × N0

Ein Element kann “mehrfach” in einem Tupel auftreten. Tupelunterschiedlicher Länge sind immer verschieden. Beispielsweise:

(1, 2, 3, 4) 6= (1, 2, 3, 4, 4)

Merke: Runde Klammern (, ) und geschweifte Klammern {, } stehenfür ganz verschiedene mathematische Objekte!



Potenzmenge

Sei M eine Menge. Die Menge P(M) ist die Menge allerTeilmengen von M.

P(M) = {A | A ⊆ M}

Beispiel:P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Es gilt: |P(M)| = 2|M| (für eine endliche Menge M).



Funktion

f : A → Ba 7→ f (a)

Die Funktion f bildet ein Element a ∈ A auf ein Element f (a) ∈ Bab. Dabei ist A der Definitionsbereich und B der Wertebereich.

Beispiel (Quadratfunktion):

f : Z→ N0, f (n) = n2

. . . ,−3 7→ 9,−2 7→ 4,−1 7→ 1, 0 7→ 0, 1 7→ 1, 2 7→ 4, 3 7→ 9, . . .

Dabei ist N0 die Menge der natürlichen Zahlen (mit der Null) undZ die Menge der ganzen Zahlen.


Graphen

Graphen sind netzartige Strukturen, bestehend aus Knoten undKanten. Sie bilden die Grundlagen vieler diagrammatischerModellierungstechniken.

Gerichteter Graph

Sei L eine Menge von Beschriftungen (oder Labels). Ein gerichteter(beschrifteter) Graph G = (V ,E ) besteht aus

einer Knotenmenge V undeiner Kantenmenge E ⊆ V × L× V .

Bemerkung: V steht für vertices und E für edges.


Graphen

Beispiel (Bauer, Wolf, Ziege, Kohlkopf):

V = {B,W ,Z ,K} L = {besitzt, frisst}

E = {(B, besitzt,W ), (B, besitzt,Z ), (B, besitzt,K ),

(W , frisst,Z ), (Z , frisst,K )}

Graphische Darstellung:

B

W Z K

besitztbesitzt

besitzt

frisst frisst


Graphen

Weitere Arten von Graphen:

Ungerichtete GraphenBei ungerichteten Graphen spielt die Richtung der Kanten keineRolle. Formal sind Kanten zweielementige Teilmengen derKnotenmenge (statt Tupel).

A

B C D

ab

c c


Graphen

Graphen mit KnotenbeschriftungAuch Knoten können Beschriftungen tragen, wobei zweiverschiedene Knoten auch gleich beschriftet sein dürfen.

B

W Z K

besitztbesitzt

besitzt

frisst frisst

Tier GemüseTier

Mensch


Graphen

Hypergraphen

Bei Hypergraphen kann eine Kante (symbolisiert durch ein Quadratoder Rechteck) mit einer beliebigen Anzahl von Knoten verbundensein. Evtl. sind dabei die Knoten im Bezug auf die Kante geordnet(wie bei gerichteten Graphen).

a

A

b

c

C DB


Graphen

Graphen können in vielfältiger Weise zur Modellierung eingesetztwerden. Wir betrachten zwei typische Fälle.

Graphen zur statischen ModellierungKnoten sind Komponenten oder Objekte, die untereinander überKanten verbunden sind bzw. in Beziehung stehen.

Beispiel: Beziehungen zwischen Bauer, Wolf, Ziege, Kohlkopf


Zustandsübergangsdiagramme

Graphen zur dynamischen ModellierungKnoten sind Zustände und Kanten sind Zustandsübergänge.Klassischer Vertreter: Zustandsübergangsdiagramme (auchTransitionssysteme genannt)

ZustandsübergangsdiagrammEin Zustandsübergangsdiagramm besteht aus einem gerichtetenGraphen (Z ,U), wobei Z (= Zustände) die Knotenmenge desGraphen und U (= Übergänge) die Kantenmenge der Graphen ist,und außerdem aus einem Startzustand z0 ∈ Z .Zustandsübergangsdiagramme werden graphisch wie gerichteteGraphen dargestellt. Der Startzustand (auch Anfangszustandgenannt) wird dabei meist durch eine eingehende Pfeilspitzegekennzeichnet.



Beispiel: Zustandsübergangsdiagramm für die Übergänge beimWolf-Ziege-Kohlkopf-Problem.

BZK|W

Misserfolg! ZK|BW WK|BZ

BWZK|

K|BWZ W|BZK

BWZ|K

BWK|Z

Z|BWK

BZ|WK

BK|WZMisserfolg! BW|ZK Misserfolg!

Misserfolg!WZ|BK

WZK|B Misserfolg!

Misserfolg!B|WZK|BWZKErfolg!


Zustandsübergangsdiagramm

Bemerkungen:

Der senkrechte Strich | steht für den Fluss. Links und rechtsdavon befinden sich die Akteure/Objekte (B = Bauer, W =Wolf, Z = Ziege, K = Kohlkopf)Übergänge sind aus Gründen der Übersichtlichkeit nichtbeschriftet. Sinnvolle Beschriftungen wären die ausgeführtenAktionen (“Bauer bringt Ziege über den Fluss”, etc.)Eckige (rote) Zustände symbolisieren hier Misserfolg (z.B.“Ziege frisst Kohlkopf”).Kanten, die aus solchen Zuständen herausführen, wurdenweggelassen.Die doppelte (blaue) Ellipse symbolisiert hier Erfolg(erwünschter Zielzustand ist erreicht)



Weitere Bemerkungen:

Es gibt mehrere (sogar unendlich viele) Wege zum Zielzustand.Die zwei kürzesten enthalten jeweils sieben Übergänge.Zustandsübergangsdiagramme selbst relativ einfacher Systemewerden oft erstaunlich groß (sogenannte Zustandsexplosion).

Wichtig:Zustandsübergangsdiagramme stellen im allgemeinen alle Zuständeund alle Übergänge eines Systems dar.

ModellierungPetrinetzeGrundlagen und Erreichbarkeitsgraphen

Motivation: Petrinetze

Petrinetze sind ein Formalismus zur Modellierung von nebenläufigenSystemen mit folgenden Eigenschaften:

Vorstellung von Systemübergängen, bei denen gemeinsameRessourcen konsumiert und neu erzeugt werden können.Einfache Modellierung von räumlicher Verteilung derRessourcen, Nebenläufigkeit, Parallelität und(Zugriffs-)Konflikten.Intuitive graphische Darstellung.Petrinetze werden in der Praxis vielfach benutzt. In UML sindsie abgewandelt als sogenannte Aktivitätsdiagramme (engl.activity diagrams) eingegangen.Eingeführt wurden Sie in der Doktorarbeit von Carl AdamPetri: “Kommunikation mit Automaten”, Bonn, 1962.



Parallelität versus Nebenläufigkeit:

ParallelitätZwei Ereignisse finden parallel statt, wenn sie gleichzeitigausgeführt werden.

NebenläufigkeitZwei Ereignisse sind nebenläufig, wenn sie parallel ausgeführtwerden können (jedoch nicht müssen), das heißt, wenn zwischenihnen keine kausale Abhängigkeit besteht.

Das bedeutet: Nebenläufigkeit ist der allgemeinere Begriff.



Anwendungen für Petrinetze:

Modellierung von Büroabläufen (work flow, business processes)Modellierung und Analyse von Web ServicesBeschreibung von graphischen BenutzeroberflächenProzessmodellierung bei BetriebssystemenAblaufbeschreibungen in ingenieurwissenschaftlichenAnwendungen. . .



Beispiel für ein Petrinetz:

Notation:

Stellen (dargestellt als Kreise): Mögliche Plätze für RessourcenMarken (dargestellt als kleine ausgefüllte Kreise): RessourcenTransitionen (dargestellt durch Rechtecke): Systemübergänge



Darstellung einer Transition:

Vorbedingung (Marken, die konsumiert werden)

Nachbedingung (Marken, die erzeugt werden)

Die Entfernung der Marken der Vorbedingung und Erzeugung derMarken der Nachbedingung nennt man Schalten bzw. Feuern derTransition.




























Beispiel: Dining Philosophers

Wir betrachten das Beispiel der Dining Philosophers (speisendePhilosophen):

Es sitzen drei Philosophen um einen runden Tisch, zwischen jezwei Philosophen liegt eine Gabel.Philosophen werden von Zeit zu Zeit hungrig und benötigenzum Essen beide benachbarte Gabeln.Jeder Philosoph nimmt zu einem beliebigen Zeitpunkt beideGabeln nacheinander auf (die rechte zuerst), isst und legtanschließend beide Gabeln wieder zurück.

P2P1

P3

F2F3

F1


Beispiel: Dining Philosophers

Modellierung alsPetrinetz:

In dem Netz ist einDeadlock(Verklemmung)erreichbar, d.h.,eine Markierung, beider keine Transitionmehr geschaltetwerden kann.

E1

W1

E2F1

H1

W2

H2

W3

H3

E3

F2

F3


Petrinetze: Definitionen

Petrinetz (Definition)

Ein Petrinetz ist ein Tupel N = (S ,T , •(), ()•,m0), wobeiS eine Menge von Stellen undT eine Menge von Transitionen ist.Außerdem gibt es für jede Transition t zwei Funktionen•t : S → N0, t• : S → N0, die angeben, wieviele Marken t auseiner Stelle entnimmt und in eine Stelle legt.m0 : S → N0 ist die Anfangsmarkierung (oder initialeMarkierung).

Der Wert •t(s) bzw. t•(s) wird auch als Gewicht bezeichnet.


Petrinetze: Definitionen

MarkierungEine Markierung ist eine Abbildung m : S → N0, die festlegt,wieviele Marken in jeder Stelle liegen.Falls eine Reihenfolge s1, . . . , sn der Stellen fixiert wurde, kann eineMarkierung m auch durch ein Tupel (m(s1), . . . ,m(sn)) dargestelltwerden.


Petrinetze: Darstellung

Eine andere Definition stellt die Verbindungen zwischen Stellen undTransitionen und die dazugehörigen Gewichte als Graph dar:

F ⊆ (S ∪ T )× (N0\{0})× (S ∪ T ) (Flussrelation),

wobei nur Kanten der Form (s, n, t) (von Stelle zu Transition) und(t, n, s) (von Transition zu Stelle) mit s ∈ S , t ∈ T erlaubt sind.

Zusammenhang zur eingeführten Notation:

(s, n, t) ∈ F ⇐⇒ •t(s) = n 6= 0(t, n, s) ∈ F ⇐⇒ t•(s) = n 6= 0

Manchmal werden auch unbeschriftete Kante eingeführt, denendann mit Hilfe einer Funktion W ein Gewicht zugeordnet wird.



Graphische Darstellung:

Stellen werden als Kreise, Transitionen als Quadrate oderRechtecke, Marken als kleine schwarze ausgefüllte KreisedargestelltKanten zwischen Stellen und Transitionen werden als Pfeiledargestellt.Das Gewicht als Kantenbeschriftung kann weggelassen werden,falls es den Wert eins hat. Die Kante wird ganz weggelassen,falls das Gewicht den Wert 0 hat.



Wir betrachten den Zusammenhang zwischen der mathematischenNotation und der graphischen Darstellung genauer:

s1 s2

t1

2

t3

s3

t2

Stellenordnung: s1, s2, s3

S = {s1, s2, s3}T = {t1, t2, t3}•t1(s1) = 1 •t1(s2) = 1 •t1(s3) = 0t1•(s1) = 0 t1•(s2) = 0 t1•(s3) = 2oder: •t1 = (1, 1, 0) t1• = (0, 0, 2)

. . .

m0(s1) = 1 m0(s2) = 2 m0(s3) = 0oder: m0 = (1, 2, 0)



Wir betrachten den Zusammenhang zwischen der mathematischenNotation und der graphischen Darstellung genauer:

s1 s2

t1

2

t3

s3

t2

Stellenordnung: s1, s2, s3

Alternative Darstellung (mit Flussrelati-on):

S = {s1, s2, s3}T = {t1, t2, t3}F = {(s1, 1, t1), (s2, 1, t1), (t1, 2, s3),

(s3, 1, t2), (t2, 1, s1),(s3, 1, t3), (t3, 1, s2)}

m0 = (1, 2, 0)


Petrinetze: Dynamik

Operationen auf Markierungen:

Seien m,m′ : S → N0 zwei Abbildungen von Stellen auf natürlicheZahlen.

Ordnung

Es gilt m ≤ m′, falls für alle s ∈ S gilt: m(s) ≤ m′(s).

AdditionWir definieren m′′ = m ⊕m′, wobei m′′ : S → N0 mitm′′(s) = m(s) +m′(s) für alle s ∈ S .

SubtraktionWir definieren m′′ = m m′, wobei m′′ : S → N0 mitm′′(s) = m(s)−m′(s) für alle s ∈ S . Dabei gilt n − k = 0, fallsn, k ∈ N0, n < k (modifizierte Subtraktion).


Petrinetze: Dynamik

Weitere Definitionen:

AktivierungEine Transition t ist unter einer Markierung m aktiviert, falls•t ≤ m gilt. (D.h., falls genug Marken vorhanden sind, um dieTransition zu schalten.)

SchaltenSei m eine Markierung und t eine Transition, die für m aktiviert ist.Dann kann t schalten, was zu der Nachfolgemarkierungm′ = m •t ⊕ t• führt. Symbolisch m[t〉m′.


Petrinetze: Dynamik

Weitere Definitionen:

ErreichbarkeitEine Markierung m heißt erreichbar in einem Netz, falls es eineFolge von Transitionen t1, . . . , tn gibt mit m0[t1〉m1 . . .mn−1[tn〉m,wobei m0 die Anfangsmarkierung ist.

In diesem Fall schreibt man auch m0[t1 . . . tn〉m oder m0[t̃〉m mitt̃ = t1 . . . tn.

Die Sequenz t̃ heißt auch Schaltfolge. Auch die leere Schaltfolget̃ = ε is möglich. In diesem Fall ändert sich die Markierung nicht(m[ε〉m, für jede Markierung m).


Petrinetze: Dynamik

s1 s2

t1

2

t3

s3

t2

Die Markierung m2 = (1, 1, 1) ist in zweiSchritten erreichbar:

•t1 = (1, 1, 0) ≤ (1, 2, 0) = m0

m1 = m0 •t1 ⊕ t1• = (1, 2, 0)(1, 1, 0)⊕ (0, 0, 2) = (0, 1, 2)

•t2 = (0, 0, 1) ≤ (0, 1, 2) = m1

m2 = m1 •t2 ⊕ t2• = (0, 1, 2)(0, 0, 1)⊕ (1, 0, 0) = (1, 1, 1)

Es gilt also: m0[t1〉m1[t2〉m2


Petrinetze: Dynamik

Zustandsübergangsdiagramm eines Petrinetzes

Sei N = (S ,T , •(), ()•,m0) ein Petrinetz. Dann besteht das zu Ngehörende Zustandsübergangsdiagramm aus folgendenKomponenten:

Menge der Beschriftungen L: Menge aller TransitionenZustandsmenge Z : Menge aller erreichbaren MarkierungenÜbergangsmenge U: (m, t,m′) ∈ U ⇐⇒ m[t〉m′.Startzustand z0: die Anfangsmarkierung m0

Das Zustandsübergangsdiagramm eines Petrinetzes heißt auchErreichbarkeitsgraph.


Petrinetze: Dynamik

Beispiel: Bestimme den Erreichbarkeitsgraph für das folgendeBeispielnetz

s1 s2

t1

2

t3

s3

t2


Petrinetze: Dynamik

Erreichbarkeitsgraph für das Beispielnetz:

��

(1, 2, 0)

t1��

(0, 1, 2)t3 //

t2

##

(0, 2, 1)t3 //

t2pp

(0, 3, 0)

(1, 1, 1)t2 //

t1��

t3

DD

(2, 1, 0)

t1��

(0, 0, 3)

t3

MM

t2// (1, 0, 2) t2

//

t3cc

(2, 0, 1) t2//

t3pp

(3, 0, 0)


Petrinetze: Dynamik

Frage: Wie kann ein beliebiges Zustandsübergangsdiagramm in einPetrinetz umgewandelt werden, das als Erreichbarkeitsgraph wiederdas ursprüngliche Zustandsübergangsdiagramm besitzt?

Idee:Zustände werden zu StellenÜbergänge werden zu Transitionendie Stelle, die den Anfangszustand darstellt, ist als einzige zuBeginn markiert

Aber:

das entstandene Petrinetz enthält keinerlei Nebenläufigkeitbei der Umwandlung

Petrinetz → Zustandsübergangsdiagramm → Petrinetzwird das zweite Petrinetz im allgemeinen viel größer als daserste


Petrinetze: Dynamik

Beispiel: Umwandlung eines Zustandsübergangsdiagramms in einPetrinetz

c

e bd

aa

bd e

c

ModellierungPetrinetzeEigenschaften von Petrinetzen, Überdeckbarkeitsgraphen

Petrinetze: Beschränktheit

Sichere, beschränkte und unbeschränkte NetzeSei N ein Petrinetz. Das Netz N heißt

beschränkt, wenn es eine Konstante c ∈ N0 gibt, so dass fürjede erreichbare Markierung m und jede Stelle s gilt, dassm(s) ≤ c .sicher (oder auch 1-sicher), wenn

Für jede Transition t und für jede Stelle s gilt •t(s) ≤ 1und t•(s) ≤ 1, d.h., alle Gewichte sind höchstens 1 undfür jede erreichbare Markierung m und jede Stelle s gilt,dass m(s) ≤ 1.

unbeschränkt, falls es für jede Konstante c ∈ N0 eineerreichbare Markierung m und eine Stelle s gibt mit m(s) > c .

Aufgabe: Finde ein Beispiel für ein unbeschränktes Netz.


Petrinetz-Beispiel: Keksautomat

Wir modellieren einen Keksautomaten mit folgenden Bestandteilen:

extern: Einwurfschlitz, Entnahmefachintern: Keksspeicher, Kasse, Signalweiterleitung (der Einwurfeiner Münze soll ein Signal erzeugen, das die Ausgabe einesKekses triggert)

Nach: “Petrinetze – Modellierungstechnik, Analysemethoden,Fallstudien” von W. Reisig



Münze einwerfen

Einwurfschlitz Signal

Einwurf möglich kein Signal

Kasse

Entnahmefach

Schachtel entnehmen

Keksspeicher



Ist der Keksautomat so in Ordnung?

Problem: Sobald der Keksspeicher leer ist, kann immer noch eineMünze eingeworfen werden, die dann nicht zurückgegeben wird.

Es gibt verschiedene Lösungen für dieses Problem: Rückgabe derMünze, Keks-Zähler, . . .


Petrinetze: Lebendigkeit und Verklemmungen

Wir betrachten nun Begriffe wie Lebendigkeit und Deadlock (=Verklemmung).

(Starke) Lebendigkeit

Ein Petrinetz N heißt (stark) lebendig, wenn es für jede Transitiont und für jede erreichbare Markierung m eine Markierung m′ gibt,die von m erreichbar ist und unter der t aktiviert ist.Für den Erreichbarkeitsgraph bedeutet dies: von jedem Knoten desGraphen aus ist ein Übergang erreichbar, der mit der Transition tbeschriftet ist.



Schwache LebendigkeitEin Petrinetz N heißt schwach lebendig, wenn es für jede Transitiont eine erreichbare Markierung m gibt, unter der t aktiviert ist.Für den Erreichbarkeitsgraph bedeutet dies: für jede Transition gibtes mindestens einen Übergang, der mit der Transition t beschriftetist.



VerklemmungEin Petrinetz N enthält ein Deadlock oder eine Verklemmung, wennes eine erreichbare Markierung m gibt, unter der keine Transitionaktiviert ist.Für den Erreichbarkeitsgraph bedeutet dies: es gibt einen Knoten,von dem aus es keinen Übergang gibt.

Ein Netz, das keine Verklemmung enthält, heißt verklemmungsfrei.



Eigenschaften der (starken) Lebendigkeit

Für Netze, deren Transitionsmenge nicht leer ist, gilt: jedes (stark)lebendige Netz ist sowohl verklemmungsfrei, als auch schwachlebendig.



Beispiele für Lebendigkeit und Verklemmungen:

Ein Beispiel für ein (stark)lebendiges Netz . . .



Ein Beispiel für einschwach lebendiges undverklemmungsfreies Netz,das jedoch nicht (stark)lebendig ist . . .



Ein Beispiel für einverklemmungsfreies Netz,das jedoch nicht schwachlebendig ist . . .



Ein Beispiel für einschwach lebendiges Netz,das jedoch eineVerklemmung enthält . . .



Ein Beispiel für ein Netz,das eine Verklemmungenthält und das auch nichtschwach lebendig ist . . .



Überblick über die verschiedenen Netzklassen (unter derVoraussetzung, dass jedes Netz mindestens eine Transition enthält):

verklemmungs-freie Netze

schwach lebendigeNetze

Netzelebendigestark

alle Petrinetze


Petrinetze: Überdeckbarkeitsgraph

Beobachtung: Ein Petrinetz ist unbeschränkt genau dann, wennsein Erreichbarkeitsgraph unendlich groß ist.

Gibt es in diesem Fall trotzdem noch eine graphische Darstellung,die “in gewisser Weise” alle erreichbaren Markierungenrepräsentiert?

Überdeckbarkeitsgraph



Zugrundeliegende Ideen:

Das Verhalten von Petrinetzen ist “monoton”, d.h., jedeSchaltfolge ist auch dann noch möglich, wenn man zusätzlicheMarken hinzufügt.Wenn im Erreichbarkeitsgraph zwei Markierungen m,m′existieren, so dass gilt:

m ist echt kleiner als m′ (in Zeichen m < m′, d.h.,m ≤ m′ und m 6= m′) undes gibt einen Pfad von m zu m′,

dann kann man die Transitionsfolge von m zu m′ noch einmalschalten und erhält wiederum eine größere Markierung m′′.



Konstruktion des ÜberdeckbarkeitsgraphenFühre zunächst wie gewohnt die Konstruktion desErreichbarkeitsgraphen aus.Sobald eine neue Markierung m′ hinzugefügt wird, wobei eseine Vorgängermarkierung m mit m < m′ gibt . . .

m0 m′m

. . . ersetze m′ durch eine (ω-)Markierung m̂ mit folgendenEigenschaften:

m̂(s) = m′(s), falls m(s) = m′(s), undm̂(s) = ω, falls m(s) < m′(s), wobei s ∈ S .

Mache dann mit der Konstruktion weiter, solange bis keineMarkierungen mehr hinzugefügt werden können.



Bemerkungen:

Die neu erzeugten besonderen ω-Markierungen ordnen einerStelle “unendlich” viele Marken (repräsentiert durch ω).Dies nimmt das wiederholte Schalten der Transitionsfolge vonm zu m′ vorweg, die in den ω-Stellen beliebig viele Markenproduzieren kann.Für ω-Markierungen gilt beim Schalten von Transitionen:ω + k = ω und ω − k = ω. Außerdem gilt ω als größer als jedenatürliche Zahl.

Der englische Name für Überdeckbarkeitgraphen ist coverabilitygraphs.



Beispiel:

s1

t2

t1

s3

s2

t3

Reihenfolge der Stellen:s1, s2, s3

��

(1, 0, 0)t3 //

t1��

(0, 0, 0)

(0, 1, 0)

t2��

(1, 0, ω)t3 //

t1��

(0, 0, ω)

(0, 1, ω)

t2

ZZ



Eigenschaften des Überdeckbarkeitsgraphen (I)

Die Konstruktion des Überdeckbarkeitsgraphen terminiertimmer nach endlich vielen Schritten.ω-Markierungen treten genau dann auf, wenn das Netzunbeschränkt ist. (D.h., der Überdeckbarkeitsgraph kann auchdazu verwendet werden, um zu überprüfen, ob ein Netzunbeschränkt ist.)



Eigenschaften des Überdeckbarkeitsgraphen (II)

Sei N ein Netz und G der dazugehörige Überdeckbarkeitsgraph.Dann gilt:

Für jede erreichbare Markierung m von N gibt es einen Knotenm′ in G , mit m ≤ m′.Für jeden Knoten m′ in G und jedes i ∈ N0 gibt es eineerreichbare Markierung m in N, so dass für alle Stellen s gilt:

m(s) = m′(s), falls m′(s) 6= ωm(s) ≥ i , falls m′(s) = ω.

Frage: Ist für eine ω-Markierung m′ in G vielleicht sogar jedeMarkierung m von N mit m ≤ m′ erreichbar?



Nein! Gegenbeispiel:

s1

t1

s2

2

Reihenfolge der Stellen:s1, s2

��

(1, 0)

t1��

(1, ω)

t1

HH

Die Markierung (1, 1) ist kleiner als (1, ω), ist aber in dem Netznicht erreichbar.


Petrinetze: Kausalität, Nebenläufigkeit, Konflikt

Wichtige Begriffe bei Petrinetzen sind Nebenläufigkeit, Konflikt undKausalität. Wir beschäftigen uns damit etwas genauer.

KausalitätIn einem Petrinetz N ist die Transition t1 notwendige Bedingung fürdas Schalten von t2 genau dann, wenn für alle Schaltfolgen t̃ gilt:

falls m0[t̃t2〉m für eine Markierung m, dann enthält t̃ die Transitiont1.



Beispiel für Kausalität:

t1

t2

t3

t4

t1 ist eine notwendige Bedingung für t4,aber t2 ist keine notwendige Bedingung für t4. Denn nicht jedeSchaltfolge, die zu t4 führt, enthält t2 (z.B. t̃ = t1t3).Das gleiche gilt für t3.



Eigenschaften der KausalitätWenn t1 eine notwendige Bedingung für t2 ist, und t2 einenotwendige Bedingung für t3 ist, dann ist t1 eine notwendigeBedingung für t3. (Transitivität)



Nebenläufigkeit

Eine Menge T ′ = {t1, . . . , tn} ⊆ T von Transitionen heißtnebenläufig aktiviert unter der Markierung m, wenn

•t1 ⊕ · · · ⊕ •tn ≤ m.

D.h., die Markierung m enthält genug Marken, um alle Transitionen“gleichzeitig” zu feuern.

Eigenschaften der Nebenläufigkeit

Wenn die Transitions-Menge T ′ unter der Markierung mnebenläufig ist, so ist auch jede Teilmenge von T ′ unter mnebenläufig.



Beispiele für Nebenläufigkeit:

t1

t2

t3

t4

Die Menge {t2, t3} ist nebenläufig unter der Anfangsmarkierung.



t2t1 t3

Die Menge T ′ = {t1, t2, t3}ist nebenläufig unter derAnfangsmarkierung.



t2t1 t3

Die Mengen {t1, t2} {t2, t3}und {t1, t3} sind allenebenläufig unter derAnfangsmarkierung. Dies giltjedoch nicht für {t1, t2, t3}.



t1 t3t2

Die Mengen {t1, t3} und{t2, t3} sind alle nebenläufigunter der Anfangsmarkierung.Dies gilt jedoch nicht für dieMengen {t1, t2} und{t1, t2, t3}.

Dieses Beispiel zeigt auch, dass Nebenläufigkeit nicht transitiv ist:t1 ist nebenläufig zu t3, t3 ist nebenläufig zu t2, jedoch sind t1 undt2 nicht nebenläufig.



Nebenläufigkeit (Konsequenzen)

Wenn eine Menge T ′ von Transitionen nebenläufig ist, so ist jedebeliebige Anordnung dieser Transitionen eine Schaltfolge ausgehendvon m.Das heißt, für jede Sequenz t̃, in der jede Transitionen aus T ′

genau einmal vorkommt, gibt es eine Markierung m′ mit m[t̃〉m′.Die Markierung m′ ist durch T ′ eindeutig bestimmt.



Nebenläufige Transitionen führen daher in Erreichbarkeitsgraphenzu Strukturen, die die Form eines Quadrats (Diamond) oder(höherdimensionalen) Würfels haben.

Beispiel für ein Quadrat:

t1 t2

s1 s2 (1, 1)t1 //

t2��

(0, 1)

t2��

(1, 0)t1 // (0, 0)



Beispiel für einen Würfel:

t1 t2

s2s1 s3

t3

(1, 1, 1)t1 //

t2

��

t3 %%

(0, 1, 1)

t2

��

t3 %%

(1, 1, 0)t1 //

t2

��

(0, 1, 0)

t2

��

(1, 0, 1)t1 //

t3 %%

(0, 0, 1)

t3 %%

(1, 0, 0)t1 // (0, 0, 0)



Frage: Wenn jede Anordnung von Transitionen in T ′ eineSchaltfolge darstellt, ist dann T ′ automatisch nebenläufig (untereiner Markierung m)?

Nein! Gegenbeispiel:

t1 t2



Schlinge

Ein Schlinge (oder Schleife) in einem Netz N besteht aus einerTransition t und einer Stelle s mit •t(s) > 0 und t•(s) > 0.

Graphisch:t s

n

m

Für schlingenfreie Netze gilt:

Sei N ein schlingenfreies Netz, sei m eine Markierung und T ′ eineMenge von Transitionen, so dass jede Anordnung der Transitionenin T ′ von m aus schaltbar ist. Dann ist T ′ nebenläufig.



KonfliktZwei Transitionen t, t ′ ∈ T stehen unter der Markierung m inKonflikt genau dann wenn:

t und t ′ sind beide unter m aktiviert unddie Menge {t, t ′} ist unter m nicht nebenläufig.

Anschaulich: nur eine der beiden Transitionen kann schalten.Das liegt immer daran, dass sie eine gemeinsame Stelle in denVorbedingungen haben. D.h., es gibt eine Stelle s mit •t(s) ≥ 1und •t ′(s) ≥ 1.



Beispiel für einen Konflikt:

t1 t2 t3

Unter der Anfangsmarkierung steht t1 in Konflikt mit t2. Außerdemsteht t2 in Konflikt mit t3.Jedoch steht t1 nicht in Konflikt mit t3 (keine Transitivität derKonfliktrelation).



Bemerkung: auf bestimmten Arten von azyklischen Netzen(sogenannte Occurrence-Netze) kann man Begriffe wie Kausalität,Nebenläufigkeit und Konflikt noch klarer herausarbeiten.

Zwei Transitionen sind in solchen Netzen immer entweder kausalabhängig, nebenläufig oder in Konflikt, unabhängig von derMarkierung.

ModellierungPetrinetzeInzidenzmatrizen und Invarianten

Petrinetze: Invarianten

Kurze Einführung in Matrizen und Vektorrechnung:

MatrixSeien m, n ∈ N0. Eine m×n-Matrix C (über den ganzen Zahlen Z)besteht aus m · n Einträgen

Ci ,j ∈ Z für i ∈ {1, . . . ,m}, j ∈ {1, . . . , n}

Sie wird folgendermaßen dargestellt:

C =

C1,1 . . . C1,n...

. . ....

Cm,1 . . . Cm,n



Bemerkungen:Eine m×n-Matrix besteht also aus m Zeilen der Länge n, oder –anders ausgedrückt – aus n Spalten der Länge m.

Dabei heißt m Zeilendimension und n Spaltendimension der Matrix.

Eine Matrix, für die m = n gilt, heißt quadratisch. Die Matrizen,die wir im Folgenden betrachten werden, sind nichtnotwendigerweise quadratisch.



Spaltenvektor

Ein Spaltenvektor (oder Vektor) ~u der Dimension n ist einen×1-Matrix, d.h., er hat folgendes Aussehen.

~u =

u1...un

Wir betrachten im Folgenden immer Spaltenvektoren mit Einträgenaus Z.



Bemerkungen:

Gegeben sei eine Markierung m = (m(s1), . . . ,m(sn)). Dannentspricht dieser Markierung der Spaltenvektor

~m =

m(s1)...

m(sn)

Spaltenvektoren kann man – wie Markierungen – addieren.Dabei werden die Komponenten paarweise addiert:u1

...un

+

v1...vn

=

u1 + v1...

un + vn



Matrizen können miteinander multipliziert werden. Wir betrachtenzunächst die Multiplikation einer Matrix mit einem Spaltenvektor.

Multiplikation einer Matrix mit einem SpaltenvektorSei C eine m×n-Matrix und ~u ein Spaltenvektor der Dimension n.Dann ist C · ~u folgender Spaltenvektor:

C ·~u =

C1,1 . . . C1,n...

. . ....

Cm,1 . . . Cm,n

·u1

...un

=

C1,1 · u1 + · · ·+ C1,n · un. . .

Cm,1 · u1 + · · ·+ Cm,n · un

Das heißt, in der i-ten Zeile des Spaltenvektors steht der Eintrag∑n

j=1 Ci ,j · uj .



ZeilenvektorEin Zeilenvektor u der Dimension n ist eine 1×n-Matrix, d.h., erhat folgendes Aussehen.

u =(u1 . . . un

)Wir betrachten im Folgenden immer Zeilenvektoren mit Einträgenaus Z.



Zeilenvektoren und Tupel:Im folgenden werden wir Zeilenvektoren im wesentlichen mitn-Tupeln gleichsetzen. Eine Markierung m = (m(s1), . . . ,m(sn)),d.h., ein Tupel aus Nn

0 schreiben wir auch als folgendenZeilenvektor:

m =(m(s1) . . . m(sn)

)



Multiplikation einer Matrix mit einem ZeilenvektorSei C eine m×n-Matrix und u ein Zeilenvektor der Dimension m.Dann ist u · C folgender Zeilenvektor der Dimension n:

u · C =(u1 . . . um

)·

C1,1 . . . C1,n...

. . ....

Cm,1 . . . Cm,n

=(u1 · C1,1 + · · ·+ um · Cm,1 . . . u1 · C1,n + · · ·+ um · Cm,n

)Das heißt, in der j-ten Spalte des Zeilenvektors steht der Eintrag∑n

i=1 ui · Ci ,j .



Merkregel:

Die Multiplikation einer m×n-Matrix mit einer n×1-Matrix(Spaltenvektor der Dimension n) ergibt eine m×1-Matrix(Spaltenvektor der Dimension m).Die Multiplikation einer einer 1×m-Matrix (Zeilenvektor derDimension m) mit einer m×n-Matrix ergibt eine 1×n-Matrix(Zeilenvektor der Dimension n).



Wir betrachten nun die Inzidenzmatrix (oder einfach Matrix) einesPetrinetzes.

Sei S = {s1, . . . , sm} die Stellenmenge, T = {t1, . . . , tn} dieTransitionsmenge des Petrinetzes N.Die Inzidenzmatrix C von N ist eine m × n-Matrix mit Einträgender Form:

Ci ,j = tj•(si )− •tj(si ) ∈ Z

Dabei handelt es sich um die herkömmliche Subtraktion (nicht diemodifizierte) und das Ergebnis liegt in den ganzen Zahlen.

Der Eintrag Ci ,j gibt an, wie sich die Anzahl der Marken in Stelle siändert, wenn die Transition tj geschaltet wird.



Beispiel für eine Matrix:

s1 s2

t1

2

t3

s3

t2

Berechnung der Matrix-Einträge:

t1 t2 t3s1 C1,1 = 0 − 1 C1,2 = 1 − 0 C1,3 = 0 − 0s2 C2,1 = 0 − 1 C2,2 = 0 − 0 C2,3 = 1 − 0s3 C3,1 = 2 − 0 C3,2 = 0 − 1 C3,3 = 0 − 1

Resultierende Matrix:

C =

−1 1 0−1 0 12 −1 −1



s2

s1

s3

t1 s2

s1

s3

t1

Die beiden Netze sind verschieden, haben aber dieselbeInzidenzmatrix:

C =

−101

Dieses Phänomen kann nicht auftreten, wenn wir nur schlingenfreieNetze betrachten.



Angenommen, es gibt eine Schaltfolge, bei der die Transition tjuj -mal geschaltet wird (uj ∈ N0). Wie kann man die dadurchverursachte Änderung der Markierung mit Hilfe der Inzidenzmatrixbestimmen?

Man multipliziert die Spalte j , die für die Transition tj steht,mit uj .Damit erhält man den Effekt des uj -maligen Schaltens von tjfür jede einzelne Stelle.Man addiert alle Werte der Zeile i , die für die Stelle si steht,auf.Damit erhält man den Effekt des Schaltens aller Transitionenfür eine einzelne Stelle.

Multiplikation der Matrix mit einem Vektor!



Sei

~u =

u1...un

der sogeannte Schaltvektor, der angibt, wie oft jede Transitiongeschalten werden soll.

Schaltvektor für das Beispielnetz: t1 und t2 werden zweimalgeschaltet, t3 einmal (dieser Schaltvektor ist von derAnfangsmarkierung aus realisierbar, z.B. durch die Schaltfolget1t2t3t1t2).

~u =

221

C · ~u =

2 · (−1) + 2 · 1+ 1 · 02 · (−1) + 2 · 0+ 1 · 1

2 · 2+ 2 · (−1) + 1 · (−1)

=

0−11



D.h., die Schaltfolge hat den Effekt, die Anzahl der Marken inStelle s1 gleichzulassen, in s2 um eins zu verringern und in s3 umeins zu erhöhen.

Wenn wir diese Änderung zu dem Spaltenvektor addieren, der derAnfangsmarkierung entspricht, ergibt sich:

~m0 + C · ~u =

120

+

0−11

=

111



MarkierungsgleichungFür jede erreichbare Markierung m gibt es einen Schaltvektor ~u mit

~m = ~m0 + C · ~u

Das heißt, jede erreichbare Markierung kann in obiger Formdargestellt werden.

Aber: nicht jede Markierung, die so dargestellt werden kann, istauch erreichbar.



s2

s1

s3

t1

C =

−101

100

+

−101

· (1) =001

Diese Markierung ist jedochnicht erreichbar, da t1 nichtaktiviert ist.



t1

s1

s3

s2

t2

C =

−1 0−1 11 −1

100

+

−1 0−1 11 −1

·(11

)=

000

Diese Markierung ist jedochnicht erreichbar, da dieSchaltfolgen t1t2 und t2t1beide nicht möglich sind.



Die Markierungsgleichung kann also nicht dazu genutzt werden, umzu zeigen, dass eine bestimmte Markierung erreichbar ist.

Aber: man kann damit manchmal zeigen, dass eine Markierungnicht erreichbar ist.

Beispiel: Ist in folgendem Netz die Markierung m = (2, 2, 0)erreichbar?

s1 s2

t1

2

t3

s3

t2

Wir überprüfen, ob die Gleichung220

=

120

+

−1 1 0−1 0 12 −1 −1

·u1u2u3

eine Lösung in den natürlichenZahlen hat.



Lösen eines Gleichungssystems

Hier sieht man leicht durch Addition aller Gleichungen, dass dasGleichungssystem keine Lösung hat.

2 = 1 −u1 +u22 = 2 −u1 +u30 = 2u1 −u2 −u3

4 = 3 Widerspruch!

Das heißt, die Markierung m = (2, 2, 0) ist nicht erreichbar.



Achtung: Als Lösungen des Gleichungssystem interessieren uns hierLösungen in den in den natürlichen Zahlen.

Daher ist das zum Lösen von Gleichungssystemen üblicherweiseverwendete Gaußsche Eliminationsverfahren nur begrenzteinsetzbar. In manchen Fällen muss es noch durch andereTechniken (z.B. Lösungsverfahren für diophantische Gleichungen)erweitert werden.

In unserem Fall werden wir die Beispiele jedoch immer so wählen,dass die entstehenden Gleichungssysteme einfach zu lösen sind.



Aufgabe: Stelle die Markierungsgleichung für folgendes(unbeschränkte) Netz auf.

s1

2

t1

t2

s3s2

Kann man mit Hilfe der Markierungsgleichung überprüfen,dass die Markierung (1, 20, 0) nicht erreichbar ist?Kann das gleiche Ergebnis auch mit demÜberdeckbarkeitsgraph erzielt werden?



Wir kommen nun zu einer weiteren Verwendung vonInzidenzmatrizen: sogenannte T- und S-Invarianten.

T-InvarianteGegeben sei ein Netz N und seine m×n-Inzidenzmatrix C . EinSpaltenvektor ~u der Dimension n heißt T-Invariante, falls

C · ~u = ~0

Dabei ist ~0 ein Spaltenvektor, der nur Einträge der Form 0 hat.

Bedeutung: eine T-Invariante beschreibt mögliche Schaltfolgen, dieeine Markierung unverändert lassen. Im Erreichbarkeitsgraph ergibtsich dann ein Kreis.



Bemerkung zu T-Invarianten:

Wie bei der Markierungsgleichung müssen solche Schaltfolgennicht notwendigerweise realisierbar sein.Wenn es einen Kreis im Erreichbarkeitsgraphen gibt, soentspricht dieser aber auf jeden Fall einer T-Invariante.Wie bei der Markierungsgleichung interessieren uns hier nurT -Invarianten mit Einträgen aus N0.



Aufgabe: Bestimme die T-Invarianten des folgenden Netzes:

s1 s2

t1

2

t3

s3

t2

Welche Bedeutung haben die T-Invarianten für denErreichbarkeitsgraph?

Erreichbarkeitsgraph



S-InvarianteGegeben sei ein Netz N und seine m×n-Inzidenzmatrix C . EinZeilenvektor v der Dimension m heißt S-Invariante, falls

v · C =(0 . . . 0

)



Bedeutung: sei ~m eine erreichbare Markierung. Dann gilt nach derMarkierungsgleichung, dass es einen Schaltvektor ~u gibt mit:

~m = ~m0 + C · ~u

Wenn man die Gleichung auf beiden Seiten von links mit vmultipliziert, so erhält man:

v · ~m = v · ~m0 + v · C · ~u = v · ~m0 + 0 = v · ~m0

Also gilt v · ~m = v · ~m0 für jede S-Invariante v und für jedeerreichbare Markierung m.

Eine Markierung, die diese Gleichung nicht erfüllt, kann daher nichterreichbar sein!



Aufgabe: Bestimme die S-Invarianten des folgenden Netzes:

s1 s2

t1

2

t3

s3

t2

Kann man mit Hilfe der S-Invarianten überprüfen, ob dieMarkierung (2, 2, 0) erreichbar ist?



Löse die Gleichung(v1 v2 v3

)·

−1 1 0−1 0 12 −1 −1

=(0 0 0

).

Es ergibt sich folgendes Gleichungssystem:

−v1 −v2 +2v3 = 0v1 −v3 = 0

v2 −v3 = 0

Durch Vereinfachung erhalten wir v1 = v2 = v3, d.h., die Lösungensind genau die Zeilenvektoren, bei denen alle Einträge gleich sind.Sie sind also alle von der Form

v =(v1 v1 v1

)= v1 ·

(1 1 1

)All diese Vektoren ergeben äquivalente S-Invarianten, wirbetrachten daher nur die S-Invariante v =

(1 1 1

).



Für eine allgemeine Markierung m = (m1,m2,m3) desBeispielnetzes gilt also:

v · ~m = m1 +m2 +m3 = 3 = v · ~m0

Die Gleichung besagt, dass die Summe der Marken in den dreiStellen konstant bzw. invariant ist und immer drei beträgt.

Im allgemeinen haben Invarianten die Form

v1 ·m1 + · · ·+ vm ·mm = k ,

wobei v1, . . . , vm, k ∈ Z Konstanten sind.



Für die spezielle Markierung m = (2, 2, 0) ergibt sich:

2+ 2+ 0 = 4 6= 3

D.h., diese Markierung ist in dem Netz auf jeden Fall nichterreichbar (ausgehend von der Anfangsmarkierung).



Bemerkungen:

Bei der Lösung des Gleichungssystems zur Berechnung vonS-Invarianten sind prinzipiell auch Lösungen außerhalb dernatürlichen Zahlen (negative Zahlen, Brüche, etc.) interessant.Da es sich jedoch um ein homogenes Gleichungssystem handelt(auf der rechten Seite steht der Nullvektor), kann man durchMultiplikation mit dem Hauptnenner (kleinstes gemeinsamesVielfaches der Nenner) zumindest immer eine Darstellung allerLösungen als Vielfaches von ganzzahligen Vektoren erhalten.Es gibt im allgemeinen unendlich viele S-Invarianten:insbesondere sind alle Vielfache einer S-Invariante wiederS-Invariante. Diese Vielfachen liefern jedoch keine zusätzlichenInformationen über das Netz.




s2

t1

3

2

s1

Kann man mit Hilfe der S-Invarianten überprüfen, ob dieMarkierung (0, 5) erreichbar ist?



Löse die Gleichung(v1 v2

)·(−23

)=(0).

Es ergibt sich folgendes Gleichungssystem:

−2v1 +3v2 = 0

Durch Vereinfachung erhalten wir v1 = 32 · v2.

D.h., die Lösungen sind von der Form v = v2 ·(3

2 1)

Wenn man nur Lösungen in den ganzen Zahlen betrachten will, somultipliziert man mit dem Hauptnenner 2 und erhält:

v = ` ·(3 2

), für ` ∈ Z.

Im Folgenden betrachten wir nur die S-Invariante, die man erhält,wenn man ` = 1 setzt.



Für eine erreichbare Markierung m = (m1,m2) des Beispielnetzesgilt also:

v · ~m = 3 ·m1 + 2 ·m2 = 12 = v · ~m0

Für die spezielle Markierung m = (0, 5) erhalten wir:

v · ~m = 3 · 0+ 2 · 5 = 10 6= 12

und damit ist diese Markierung nicht erreichbar.




s4

t4s3

t1

s1

t2 t3

s2

s5

Kann man mit Hilfe der S-Invarianten überprüfen, ob dieMarkierung (0, 0, 1, 1, 1) erreichbar ist?



Aufgabe: Mit Hilfe des folgenden Beispiels soll gezeigt werden, dassInvarianten auch für unbeschränkte Netze sehr nützlich sein können.Bestimmen Sie dazu die S-Invarianten des folgenden Netzes:

s1

s3

t1

s2

2



Aufgabe: Wir hatten mit Hilfe der Markierungsgleichung gezeigt,dass die Markierung (1, 20, 0) in folgendem Netz nicht erreichbarist.

s1

2

t1

t2

s3s2

Kann man das gleiche Ergebnis auch mit Hilfe von S-Invariantenerzielen?



Bemerkungen:

Für beschränkte Netze sind folgende Techniken zum Testen derNicht-Erreichbarkeit geeignet. Sie werden der Reihe nachaufwändiger und exakter:

1 S-Invarianten2 Markierungsgleichung3 Erreichbarkeitsgraph

(exakt, kann auch zur Überprüfung der Erreichbarkeitverwendet werden).



Bemerkungen:

Auch für unbeschränkte Netze ist die Markierungsgleichungaufwändiger und exakter als S-Invarianten.

Der Überdeckbarkeitsgraph ist jedoch, im Gegensatz zumErreichbarkeitsgraph, keine exakte Technik und erlaubt nurbegrenzt Aussagen über die Erreichbarkeit von Markierungen.



Für unbeschränkte Petrinetze haben wir also bisher nurapproximative, unvollständige Methoden für dasErreichbarkeitsproblem. Es gilt jedoch:

Entscheidbarkeit des Erreichbarkeitsproblems

Es gibt ein Verfahren, das für ein gegebenes (unbeschränktes) NetzN und eine Markierung m entscheidet, ob m in N erreichbar ist.(Mayr, 1984)



Dieses Verfahren ist jedoch extrem aufwändig und in derPraxis derzeit nicht einsetzbar.Die obige Aussage bedeutet jedoch auch, dass Petrinetze nichtzu den mächtigsten Berechnungsmodellen gehören. Es gibtnämlich Berechnungsmodelle, für die dasErreichbarkeitsproblem nicht entscheidbar ist.Anders ausgedrückt: Petrinetze sind nicht Turing-mächtig ( Vorlesung “Berechenbarkeit und Komplexität”).Das liegt vor allem daran, dass Petrinetze keine Nulltestsfolgender Form erlauben: “Die Transition t kann nur feuern,wenn in der Stelle s keine Marken liegen.”


Petrinetze: Fallstudien (Wechselseitiger Ausschluss)

Wir betrachten nun noch einige größere Fallstudien . . .

Zunächst behandeln wir das Konzept des wechselseitigenAusschlusses (engl. mutual exclusion oder mutex).

Wir betrachten zwei Akteure, die jeweils einen kritischenBereich haben.Beide Akteure dürfen nicht gleichzeitig in ihren kritischenBereich kommen, da sie sich dort gegenseitig behindern undunerwünschtes Verhalten auslösen würden (z.B. indem beideAkteure in dieselbe Datei schreiben).Es darf sich also immer höchstens ein Akteur im kritischenBereich befinden.



Ursprüngliches System:

K1NK 1

nk1

k1

kritischer Bereich

NK 2K2

nk2

k2

Bedeutung der Stellen: K1 (krit. Bereich Akteur 1), NK 1(nicht-krit. Bereich Akteur 1), K2 (krit. Bereich Akteur 2), NK 2(nicht-krit. Bereich Akteur 2)



Erweitertes System mit Mechanismen zum wechselseitigen Aus-schluss:

K1NK 1

nk1

k1

NK 2K2

k2

nk2

S

Bedeutung der Stellen: K1 (krit. Bereich Akteur 1), NK 1(nicht-krit. Bereich Akteur 1), K2 (krit. Bereich Akteur 2), NK 2(nicht-krit. Bereich Akteur 2), S (Hilfsstelle, sog. Semaphor)



Wir möchten zeigen, dass in den Stellen K1, K2 niemals gleichzeitigMarken liegen.

Reihenfolge der Stellen: K1, NK 1, K2, NK 2, SReihenfolge der Transitionen: k1, nk1, k2, nk2

Inzidenzmatrix:

C =

1 −1 0 0−1 1 0 00 0 1 −10 0 −1 1−1 1 −1 1



Wir bestimmen die S-Invarianten, nach der Gleichung

v · C =(0 . . . 0

)Entstehendes Gleichungssystem:

v1 −v2 −v5 = 0−v1 +v2 +v5 = 0

v3 −v4 −v5 = 0−v3 +v4 +v5 = 0



Vereinfacht ergibt sich:

v1 = v2 + v5v3 = v4 + v5

Das heißt, die Lösungen haben genau die Form:(v2+v5 v2 v4+v5 v4 v5

)= v2 ·

(1 1 0 0 0

)+ v4 ·

(0 0 1 1 0

)+ v5 ·

(1 0 1 0 1

)für v2, v4, v5 ∈ Z. Die drei Vektoren bilden eine Basis desLösungsraums.



Für uns ist vor allem der letzte Vektor interessant. Für jedeerreichbare Markierung m = (m1,m2,m3,m4,m5) muss gelten:

m1 +m3 +m5 = v · ~m = v · ~m0 = 1

Angenommen, in der Stelle K1 liegt mindestens eine Marke(m1 ≥ 1) und in der Stelle K2 liegt mindestens eine Marke(m3 ≥ 1).Dann gilt:

2 ≤ m1 +m3 +m5 = 1,

was ein Widerspruch ist.

Also liegt in den Stellen K1, K2 zusammen immer höchstens eineMarke.


Petrinetze: Fallstudien (Speisende Philosophen)

Wir kommen nochmal auf die speisenden Philosophen zurück:

Diesmal sitzen nur zwei Philosophen an einem Tisch (damitdas Beispiel nicht zu groß wird).Einer davon ist ein Linkshänder (und nimmt die linke Gabelzuerst), der andere ein Rechtshänder (und nimmt die rechteGabel zuerst).



Petrinetz: links- und rechtshändige Philosophen

w1

e1

h1

F1 F2

E2

W1 E1

W2

H2

H1

h2w2

e2

Reihenfolge derStellen:F1,F2,H1,H2,W1,W2,E1,E2

Reihenfolge derTransitionen:w1, e1, h1,w2, e2, h2



Zu zeigen: in diesem Netz gibt es keine Verklemmung, bei der beidePhilosophen im Wartezustand sind.D.h., folgende Markierung soll nicht erreichbar sein:

m = (0, 0, 0, 0, 1, 1, 0, 0)

Dazu betrachten wir die Inzidenzmatrix des Netzes:

C =

−1 0 1 −1 0 10 −1 1 0 −1 1−1 0 1 0 0 00 0 0 −1 0 11 −1 0 0 0 00 0 0 1 −1 00 1 −1 0 0 00 0 0 0 1 −1



Eine S-Invariante ist

v =(1 0 0 0 1 1 1 1

)Und es gilt:

v · ~m0 = 1 v · ~m = 2

Daraus folgt v · ~m0 6= v · ~m. Damit ist m nicht erreichbar und eskann daher kein Deadlock dieser Form geben.


Fallstudie: Leser-Schreiber-Problem

Beliebig viele Prozessedürfen gleichzeitig lesenWenn geschrieben wird,darf nur ein Schreiberund keine Leser imkritischen Abschnitt seinDie Schreiber’verhungern’, solangenoch jemand lesen will


Fallstudie: Leser-Schreiber-Problem(2)

Bessere Lösung:Sobald jemandschreiben will, müssenalle Leser warten


Petrinetze: Weitere Arten von Netzen

Wir betrachten zuletzt noch zwei weitere Arten von Netzen:

Netze mit KapazitätenAttributierte Netzeauch bekannt unter den Namen: Netze mit individuellenMarken, Prädikat-Transitions-Netze, engl. coloured Petri nets



Netze mit Kapazitäten

Ein Petrinetz mit Kapazitäten besteht aus einem (herkömmlichen)Petrinetz N (mit Stellenmenge S) und einer Kapazitätsfunktionk : S → N0. Für die Anfangsmarkierung m0 muss gelten: m0 ≤ k .

Intuition: die Stelle s darf höchstens k(s) Marken enthalten.Kapazitäten werden neben die Stellen geschrieben.

Schalten von Transitionen bei KapazitätenEine Transition t kann unter einer Markierung m schalten, wenngilt:

1 •t ≤ m2 und m •t ⊕ t• ≤ k .

D.h., eine Transition darf nur dann schalten, wenn dadurch dieKapazitäten nicht überschritten werden.



Beispielnetz mit Kapazitäten

s2s1

2 1

t1

t2

t3


// (1, 1)t3 //

t2��

(1, 0)

t1��

(2, 0)

t1

DD

(0, 1)

t2

DD

t3 // (0, 0)

Insbesondere: unter der Anfangsmarkierung (1, 1) ist die Transitiont1 nicht schaltbar.



Umwandlung eines Netzes mit Kapazitäten in ein Netz ohneKapazitäten

1 Füge zu jeder Stelle s eine sogenannte Komplementstelle shinzu. In der Anfangsmarkierung enthält s genau k(s)−m0(s)Marken.Idee: die Summe der Marken in der Stelle und derKomplementstelle ergibt immer die Kapazität.

2 Falls eine Transition in der Summe Marken aus einer Stelleherausnimmt (n = t•(s)− •t(s) < 0) füge eine Kante von tnach s mit Gewicht −n ein.

3 Falls eine Transition in der Summe Marken in eine Stellehineinlegt (n = t•(s)− •t(s) > 0) füge eine Kante von s nacht mit Gewicht n ein.



Mit dieser Konstruktion ist für jedes Paar s, s von Stellensichergestellt, dass

m(s) +m(s) = k(s) für jede erreichbare Markierung s;eine Transition t nur schaltbar ist, wenn die Kapazität derStellen in der Nachbedingung noch nicht ausgeschöpft ist. Daswird dadurch überprüfen, dass die benötigte Kapazität überdie Komplementstellen abgefragt wird.



Umgewandeltes Beispielnetz

s1 s2

s2s1 t1

t2

t3

Reihenfolge der Stellen: s1, s1, s2, s2


// (1, 1, 1, 0)t3 //

t2��

(1, 1, 0, 1)

t1��

(2, 0, 0, 1)

t1

DD

(0, 2, 1, 0)

t2

DD

t3 // (0, 2, 0, 1)


Fallstudie: Erzeuger-Verbraucher-Problem

Ein Prozess erzeugt Objekte, der andere verbraucht dieseEs steht nur eine begrenzte Anzahl Speicherplätze zurVerfügung


Fallstudie: Erzeuger-Verbraucher-Problem (2)

Ein Prozess erzeugt Objekte, der andere verbraucht dieseEs steht nur eine begrenzte Anzahl Speicherplätze zurVerfügungDas Schreiben/Lesen der Objekte muss im kritischenAbschnitt erfolgen



Obige Lösung ignoriert, dass bei der Programmierung dieBedingungen (kritischer Abschnitt, freie Plätze/Objektevorhanden) nacheinander überprüft werden müssenVariante 1: Erst kritischer AbschnittEs kommt zum Deadlock, wenn die zweite Bedingung nichterfüllt ist



Korrekte Lösung: Erst die Anzahl überprüfen, danach in denkritischen Abschnitt



Bei attributierten Netzen (oder coloured nets) haben die MarkenFarben. Die Transitionen geben an, Marken welcher Farbeentnommen und erzeugt werden sollen.

Beispielsweise entnimmt folgende Transition eine blaue und einerote Marke und erzeugt zwei grüne Marken.

2×



Farben können dabei auch Elemente eines bestimmten Datentypssein (z.B. Zahlen). Die Transitionen werden dabei symbolischannotiert und an den Transitionen können auch Bedingungenstehen.

Beispielsweise hat folgendes Netz natürliche Zahlen als “Farben”.Die Transition entnimmt der ersten Stelle eine natürliche Zahl xund der zweiten Stelle eine Zahl y . In die Stelle der Nachbedingungwird dann die Zahl x + y gelegt. Die Transition darf nur schalten,wenn x > 3.

27

45

x + yx

yx > 3

ModellierungUnified Modeling Language (UML)

UML: Einführung

UML = Unified Modeling Language

Standard-Modellierungssprache fürSoftware Engineering.Basiert auf objekt-orientiertenKonzepten.Sehr umfangreich, enthält vieleverschiedene Typen von Modellen.Entwickelt von Grady Booch,James Rumbaugh, Ivar Jacobson(1997).

ModellierungUnified Modeling Language (UML)Klassen- und Objektdiagramme

UML und Objekt-Orientierung

Was bedeutet Objekt-Orientierung?

GrundideeDie reale Welt besteht aus Objekten, die untereinander inBeziehungen stehen. Diese Sichtweise wird auch auf Modellierungund Softwareentwicklung übertragen.

Etwas genauer . . .

Daten (= Attribute) werden zusammen mit der Funktionalität (=Methoden) in Objekten organisiert bzw. gekapselt. Jedes Objekt istin der Lage Nachrichten (= Methodenaufrufe) zu empfangen,Daten zu verarbeiten und Nachrichten zu senden.Diese Objekte können – einmal erstellt – in verschiedenenKontexten wiederverwendet werden.



Geschichte der Objekt-OrientierungEntwicklung von objekt-orientierten Programmiersprachen:

60er Jahre: Simula (zur Beschreibung und Simulation vonkomplexen Mensch-Maschine-Interaktionen)80er Jahre: C++90er Jahre: Java

Verbreitung von objekt-orientierten Entwurfsmethoden:70er Jahre: Entity-Relationship-Modell90er Jahre: Vorläufer von UML:OOSE (Object-Oriented Software Engineering),OMT (Object Modeling Technique)Seit 1997: UMLSeit 2005: UML 2.0



Vorteile der objekt-orientierten Programmierung und ModellierungLeichte Wiederverwendbarkeit dadurch, dass Daten undFunktionalität zusammen verwaltet werden und es Konzeptezur Modifikation von Code (Stichwort: Vererbung) gibt.Nähe zur realen Welt: viele Dinge der realen Welt können alsObjekte modelliert werden.Verträglichkeit mit Nebenläufigkeit und Parallelität:Kontrollfluss kann nebenläufig in den Objekten ablaufen unddie Objekte können durch Nachrichtenaustausch bzw.Methodenaufrufe untereinander kommunizieren.



Ein Beispiel für die Modellierung vonObjekten der realen Welt:

FahrkartenautomatDaten: Fahrtziele, Zoneneinteilung,FahrtkostenFunktionalität: Tasten drücken,Preise anzeigen, Münzen einwerfen,Fahrkarte auswerfen



KonzepteKlassen: definiert einen Typ von Objekten mit bestimmtenDaten und bestimmter Funktionalität.Beispiel: die Klasse der VRR-FahrkartenautomatenObjekte: Instanzen der Klasse.Beispiel: der Fahrkartenautomat am Duisburger Hauptbahnhof,Osteingang


UML: Einführung

Einsatzgebiete von UMLVisualisierungSpezifikationKonstruktion (z.B. zur Codegenerierung)Dokumentation


UML: Einführung

Vokabular der UML (nach Booch/Rumbaugh/Jacobson)

Dinge (things)Beziehungen (relationships)Diagramme (diagrams)

Dinge

Strukturen (structural things)Verhalten (behavioral things)Gruppen (grouping things)Annotationen (annotational things)


UML: Einführung

Beziehungen

Abhängigkeiten (dependencies)Assoziationen (associations)Generalisierungen (generalizations)Realisierungen (realizations)


UML: Einführung

UML-Diagramme

Verhaltens-diagramme

Interaktions-diagramme

Objekt-diagramm

Kompositions-strukturdiagramm

diagrammeStruktur-

Klassen-

diagrammKomponenten-

diagramm

Verteilungs-diagramm

Paket-diagramm

Diagrammeder UML

diagramm diagramm

diagramm

Aktivitäts- Anwendungsfall-

Zustands-

diagrammdiagramm

Interaktionsüber-sichtsdiagramm

Zeitverlaufs-/Timing-Diagramm

Kommunikations-Sequenz-


UML: Einführung

Diagramme (I)

StrukturdiagrammeKlassendiagramme (class diagrams)Objektdiagramme (object diagrams)Kompositionsstrukturdiagramme (composite structurediagram)Paketdiagramme (package diagram)Verteilungsdiagramme (deployment diagram)Komponentendiagramme (component diagrams)


UML: Einführung

Diagramme (II)

VerhaltensdiagrammeAktivitätsdiagramme (activity diagrams)Zustandsdiagramme (state diagrams)Anwendungsfalldiagramm (use case diagrams)Interaktionsdiagramme

Sequenzdiagramme (sequence diagrams)Kommunikationsdiagramm (communication diagram)Zeitverlaufsdiagramm (timing diagram)Interaktionsübersichtsdiagramm (interaction overviewdiagram)

Wir werden im Folgenden einige dieser Begriffe mit Leben füllen.


Klassen- und Objektdiagramme

Wir beginnen mit Klassen- und Objektdiagrammen . . .

Beispiel: Klasse der zweidimensionalen Punkte mit x-,y -Koordinaten und Operationen zum Auslesen der Koordinaten

Graphische Darstellung einer Klasse

x: inty: int

Klassenname

Attribute (evtl. mit Typ)

Operationen/Methodenget_x(): intget_y(): int

Point



Bemerkungen:

Bei den Attributen handelt es sich um sogenannteInstanzattribute, d.h., sie gehören zu den Instanzen einerKlasse (nicht zur Klasse selbst).Man kann die Sichtbarkeit eines Attributes bzw. einer Methodespezifieren, indem man + (öffentlich/sichtbar) oder −(privat/nicht sichtbar) vor den Attribut-/Methodennamenschreibt.Auch die Angabe # (geschützt/protected) ist möglich. Indiesem Fall ist das Attribut nur für Klassen sichtbar, die vonder entsprechenden Klasse erben.



Bemerkungen:

Attribute haben im allgemeinen Typen, manchmal auchVorgabewerte (= initiale Werte). Dies wird dannfolgendermaßen notiert:

x: int = 0

Mehrstellige Operationen mitRückgabewert, werden mit ihren Typen folgendermaßen notiert:

add(m: int, n: int): int



Graphische Darstellung einer Instanz einer Klasse

x: inty: int

get_x(): intget_y(): int

«instantiate»

x = 0y = 0

Point mypoint :Point



Graphische Darstellung von Generalisierung/Spezialisierung

c: stringx: inty: int


color(): stringsetcolor(c: string)

Colored_PointPoint

Die Klasse Colored_Point spezialisiert die Klasse Point.Umgekehrt generalisiert Point die Klasse Colored_Point.



Bemerkungen:

In einer solchen Situation nennt man Point Superklasse undColored_Point Subklasse.Da die Subklasse die Attribute, Methoden und Assoziationender Superklasse erbt (und diesen noch weitere hinzufügenkann), spricht man auch von Vererbung. Außerdem kann manin der Subklasse Methoden der Superklasse überschreiben unddurch neue ersetzen.



Wie kann man Beziehungen zwischen Klassen in UML darstellen?Es gibt folgende mögliche Beziehungen:

AssoziationAggregationKomposition



Wir beginnen mit der schwächsten Relation zwischen zwei Klassen:der Assoziation.

AssoziationEs gibt eine Assoziation zwischen den Klassen A und B, wenn

es eine semantische Beziehung zwischen den Klassen gibt.

Üblicherweise werden Assoziationen durch Referenzen realisiert(d.h., eine der Klassen hat ein Attribut vom Typ der anderenKlasse).



Beispiel für eine AssoziationEine Person besitzt ein Auto.

besitzt

Person Auto



Bemerkungen:

Es kann eine Leserichtung der Assoziation eingeführt werden:

besitzt

Person Auto

Die Navigationsrichtung (beschrieben durch eine Pfeilspitze)kann von der Leserichtung abweichen. Sie beschreibt, welcheKlasse ihren Assoziationspartner kennt (und daher seineMethoden aufrufen kann).

besitzt

Person Auto

Hier kennen sich beide Klassen gegenseitig.



Multiplizitäten: an beide Enden der Assoziationen könnenMultiplizitäten in Form von Intervallen m..n (oder einfach nurm für m..m) angegeben werden. Hier besitzt eine Person biszu fünf Autos. Ein Auto ist im Besitz genau einer Person.

besitzt

Person Auto1 0..5

Falls die Multiplizität größer als eins ist, muss dies in derImplementierung durch eine Liste (oder Menge oder Array)von Referenzen realisiert werden.



Multiplizitäten allgemein: in folgendem Diagramm können iInstanzen von A (mit m ≤ i ≤ n) mit einer Instanz von Bassoziert sein. Umgekehrt können j Instanzen von B (mitk ≤ j ≤ l) mit einer Instanz von A assoziiert sein.

A Bm..n k..l

Falls es keine obere Schranke gibt, wird ein Stern (=unendlich) verwendet. Beispielsweise steht 2..∗ für “mindestenszwei”.

Die Multiplizität 0..∗ wird als Standardwert angenommen,wenn keine Angabe vorhanden ist.



Rollen: Klassen können in verschiedenen Assoziationenverschiedene Rollen spielen. Rollen werden auch an denAssoziationen notiert (und können alle Bestandteile einesAttributs enthalten).

Haendler Kaeufer EndkundeVerkaeuferKaeuferVerkaeuferGrosshandel



Die nächste Relation – Aggregation – ist etwas stärker.

AggregationEs gibt eine Aggregation zwischen den Klassen A und B, wenn

Instanzen der Klasse A Instanzen der Klasse B als Teileenthalten. (Ein “Ganzes” enthält mehrere “Teile”.)



Beispiel für eine AggregationEin Parkplatz “enthält” mehrere Autos.

AutoParkplatz

enthaelt

0..1 0..∗



Die stärkste Relation ist die sogenannte Komposition.

KompositionEs gibt eine Komposition zwischen den Klassen A und B, wenn

Instanzen der Klasse A Instanzen der Klasse B als Teileenthalten und die Lebenszeit der Teile wird vom “Ganzen”kontrolliert. Das heißt, die Teile können (müssen) gelöschtwerden, sobald die Instanz der Klasse A gelöscht wird.



Beispiel für eine KompositionEin Auto besteht aus vier Rädern.

Auto Rad

besteht_aus

1 4

Die Räder werden zerstört, sobald das Auto zerstört wird.

Bemerkung: In diesem Fall muss die Multiplizität, die an derschwarzen Raute steht, immer 0 oder 1 sein. Jedes Teil kannhöchstens zu einem Ganzen gehören.



In Klassendiagrammen befinden sich normalerweise nicht nur zweiKlassen mit einer Assoziationen, sondern verschiedene Klassen einesProgramms oder Moduls, mit ihren Beziehungen untereinander.

Beispiel:

AutoParkplatz

enthaelt

0..1 0..∗

besitzt

Person1

0..5

Rad

besteht_aus

1 4



n-äre AssoziationNeben binären (zweistelligen) Assoziationen gibt es auch n-äreAssoziationen, die eine Beziehung zwischen n Klassen beschreiben.

1..∗

0..∗

Vorspeise

0..∗ Dessert

Menue

Hauptgericht



GeneralisierungsgruppenKlassen können in unterschiedlicher Weise spezialisiert bzw.unterteilt werden. Daher können Generalisierungen zu Gruppenzusammengefasst werden.

Person

Frau

Mann

AlterGeschlecht

Erwachsener

Kind

Dabei wird die jeweilige Generalisierungsgruppe (hier: Alter bzw.Geschlecht) im Diagramm angegeben.



Den Generalisierungsgruppen können Eigenschaften (ingeschweiften Klammern) zugeordnet werden.

complete/incomplete:complete: die Generalisierungsgruppe ist vollständig, d.h.,sie überdeckt alle Instanzen der Klasse.incomplete: die Generalisierungsgruppe ist unvollständig.

disjoint/overlapping:disjoint: die spezialisierenden Klassen besitzen keinegemeinsamen Instanzen (keine Überlappung).overlapping: die spezialisierenden Klassen könnengemeinsame Instanzen besitzen.



Beispiele für die Eigenschaften complete/incomplete unddisjoint/overlapping:

{complete,disjoint}

Person

Frau

Mann

Geschlecht

{complete,disjoint}

Hier handelt es sich um eine Partitionierung der Instanzen derKlasse.



{incomplete,disjoint}

Alter

Person

{incomplete,disjoint}

Kind

Erwachsener

Warum unvollständig? es fehlt eine Klasse Jugendlicher.



{complete,overlapping}

Lebensraum

Tier

{complete,overlapping}

Fliegendes_Tier

Meerestier

Landtier

Schildkröten sind sowohl Land- als auch Meerestiere.



{incomplete,overlapping}

Tier

LebensraumLandtier

Meerestier

{incomplete,overlapping}

Fliegende Tiere fehlen.



MehrfachvererbungEs ist auch möglich, dass eine Klasse von mehreren Klassen erbt,d.h., eine Spezialisierung verschiedener Klassen ist. Dies bezeichnetman als Mehrfachvererbung.

Frau Kind

Erwachsener

AlterGeschlecht

Person

Mann

Maedchen

Ein Mädchen ist sowohl ein Kind als auch ein weiblicher Mensch (=Frau).



Basierend auf diesen graphischen Notation sollte man einobjekt-orientiertes System modellieren, bevor es implementiert wird.Dabei stellen sich insbesondere folgende Fragen:

Welche Objekte und Klassen werden benötigt?Welche Merkmale haben diese Klassen und welcheBeziehungen bestehen zwischen Ihnen?Wie sollen die Klassen eingesetzt werden?Welche Methoden stellen diese Klassen zur Verfügung? Wiewirken diese Methoden zusammen?In welchen Zuständen können sich Objekte befinden undwelche Nachrichten werden wann an andere Objekte geschickt?


Beispiel: Modellierung einer Bank

Ein größeres Beispiel für objekt-orientierte Modellierung undProgrammierung: Wir modellieren eine Bank.

Folgende Anforderungen werden gestellt:Eine Bank

hat mehrere Kundenund mehrere Angestellteund führt eine Menge von Konten.

Konten könnenGiro- oder Sparkonten sein. (Ein Sparkonto wirft höhereZinsen ab, darf aber nicht ins Minus absinken.)in Euro oder in Dollar geführt werden.



Auf den Konten sollen folgende Operationen ausgeführtwerden können:

EinzahlenAbhebenVerzinsenUmbuchen

Außerdem sollen alle Objekte (inklusive der Bank) ihreDarstellung ausdrucken können. Dazu hat jedes Objekt eineeigene print-Methode.Das bezeichnet man auch als Overloading: eine Methodegleichen Namens kann bei Objekten verschiedener Klassenaufgerufen werden und erzielt dort unterschiedliche Effekte.



Klasse Bank:

Bank

neuen_kunden_anlegen()

name: string

konten_verzinsen()print()

angestellten_einstellen()

Methoden: neuen Kunden anlegen;neuen Angestellten einstellen; alleKonten verzinsen

Außerdem: Eine Bank besteht (inKompositionsrelation) aus einerMenge von Konten, dieverschwinden, wenn die Bankverschwindet. Außerdem gibt esAggregationen mit einer Liste vonKunden und von Angestellten.



Klasse Konto:

Konto

nummer: stringzins: float

verzinsen()print()

einzahlen(wert: Betrag)

umbuchen_auf(kto: konto,abheben(wert: Betrag)

kontostand: Betrag

wert: Betrag)

Attribute: Kontonummer, Zins

Methoden: Kontostand abfragen,einzahlen, abheben, umbuchen einesBetrags auf ein anderes Konto,Konto verzinsen

Außerdem: Konto steht in einerKompositionsrelation mit Betrag,d.h., jedes Konto enthält einenBetrag (siehe Klassendiagramm).



Klasse Girokonto:

Girokonto

Konto

zins: float = 0.005

Die Klasse Girokonto wird von Kontoabgeleitet. Typischerweise ist derZins bei Girokonten niedriger als beiSparkonten. Von daher wird dieserauf einen niedrigeren Anfangswertgesetzt.



Klasse Sparkonto:

Konto

Sparkonto

zins: float = 0.02

abheben(wert: Betrag)

wert: Betrag)umbuchen_auf(kto: Konto,

Bei der Klasse Sparkonto muss – wiebeim Girokonto – ein neuerAnfangswert für den Zins gesetztwerden.

Außerdem: es muss darauf geachtetwerden, dass das Konto nicht insMinus abgleitet. Dazu werden dieentsprechenden Methodenüberschrieben (in derImplementierung muss die Bedingungentsprechend getestet werden).



Klasse Betrag:

wert: float

Betrag

negativ(): bool

print()mult(faktor: float)

plus(wert: Betrag)minus(wert: Betrag)

Methoden: Test, ob Konto im Minus;Betrag addieren, subtrahieren;Multiplikation mit einerGleitpunktzahl (zum Verzinsen!)

Beträge müssen im allgemeinen in einer Währung angegebenwerden. Daher werden von der Klasse Betrag die Unterklassen Euround Dollar abgeleitet.



Klasse Euro:

Euro

betrag_in_euro():float

Betrag

Von Betrag wird zunächst die KlasseEuro abgeleitet.

Methoden: Betrag in Euro ausgeben



Klasse Dollar:

Betrag

Dollar

betrag_in_dollar():float

Von Betrag wird außerdem dieKlasse Dollar abgeleitet.

Methoden: Betrag in Dollar ausgeben



Klasse Person:

Person

name: string

print()

Methoden: nur die print-Methode,weitere Methoden werden in denUnterklassen definiert

Außerdem: Person steht in einerAssoziationsrelation mit einer Listevon Konten, die entweder dieserPerson gehören (Kunde) oder auf diediese Person Zugriff hat(Angestellte/r).



Klasse Angestellter (erbt von Person):

Angestellter

zugriff_auf_konto(kto:Konto)

Methoden: Zugriff auf ein Kontoerlangen



Klasse Kunde (erbt von Person):

Kunde

konto_eroeffnen()

Methoden: Konto eröffnen (hierkönnte noch ein Parameter übergebenwerden, der beschreibt, ob das Kontoein Giro- oder Sparkonto sein soll undob es in Euro oder Dollar geführtwerden soll)

Außerdem: Ein Kunde steht in einerAssoziationsrelation mit seinemBetreuer.



hat_Zugriff_aufKontotyp

Status

Waehrung

Betrag

Euro

betreut

name: string

Person

wert: float

Girokonto Sparkonto

Konto1

1

Bank

Dollar

Kunde Angestellterbesteht_aus

besitzt1

1



Abstrakte KlasseEine Klasse heißt abstrakt, wenn sie selbst keine Instanzen habenkann. Dazu wird die Eigenschaft {abstract} unter demKlassennamen angegeben. Manchmal wird stattdessen auch derKlassenname kursiv geschrieben.

Beispiel: in dem Bank-Beispiel möchte man beispielsweise nie eineInstanz der Klasse Person bilden, sondern nur von Kunde oderAngestellter.

Person{abstract}



Wir betrachten nun Objektdiagramme. Ein Objekt ist eine Instanzoder Ausprägung einer Klasse.

Objekte und Klassen

x: inty: int


«instantiate»

x = 0y = 0

Point mypoint :Point

Ein Objektdiagramm beschreibt eine Art Momentaufnahme desSystems: eine Menge von Objekten, wie sie zu einem bestimmtenZeitpunkt vorhanden sind.



Bemerkungen:

Ein Objekt kann, muss aber keinen Namen haben. Es mussaber die Klasse angegeben werden, von der dieses Objekt eineInstanz ist. (In der Form: :Point.)Die Klassen müssen in dem Diagramm nicht graphischdargestellt werden. Es kann aber manchmal angemessen sein,“Bauplan” und “Produkt” gemeinsam darzustellen.Nicht alle Attributbelegungen des Objekts müssen angegebenwerden.



LinksEin Link beschreibt eine Beziehung zwischen zwei Objekten. Er isteine Instanz einer Assoziation auf Klassenebene.

Bemerkungen:

Links sind nicht mit Multiplizitäten beschriftet, ein Linkrepräsentiert genau eine Beziehung.Es ist jedoch darauf zu achten, dass dieMultiplizitätsbedingungen des Klassendiagramms eingehaltenwerden. D.h., die Anzahl der Objekte, die miteinander inBeziehung stehen, müssen innerhalb der jeweiligen Schrankensein.



Zurück zum Beispiel: Autos, Parkplatz, Räder

Wir betrachten zunächst noch einmal das Klassendiagramm:

AutoParkplatz

enthaelt

0..1 0..∗

besitzt

Person1

0..5

Rad

besteht_aus

1 4



Dieses Objektdiagramm passt zum vorherigen Klassendiagramm:

:Rad

:Rad

:Rad

:Rad

enthaelt

enthaeltbesitzt

besteht_ausbesitzt

besteht_aus

peter

:Rad

:Rad

:Rad

:Rad

gruenerAudi

gabi:Person

:Person

:AutoparkplatzLBereich:Parkplatz

schwarzerVW:Auto



Bemerkungen:

Auch Aggregations- und Kompositionssymbole dürfen inObjektdiagrammen auftauchen.Achtung: Beziehungen (Assoziationen, Aggregationen,Kompositionen) zwischen Klassen werden vererbt und müssendann auch entsprechend im Objektdiagramm bei den Instanzender Unterklassen auftauchen.

Beispiel:

besitzt

besitzt

:Sparkonto

:Girokonto

klaus :Kunde

ModellierungUnified Modeling Language (UML)Verhaltensdiagramme

Aktivitätsdiagramme

Wir betrachten nun sogenannte Aktivitätsdiagramme (activitydiagrams), das sind UML-Diagramme mit denen man Ablaufpläne,Reihenfolgen von Aktivitäten, parallele Aktivitäten, etc. modellierenkann.

Sie werden beispielsweise verwendet, um Geschäftsprozesse (auchWorkflow-Prozesse) des Auftraggebers zu modellieren. Sie könnenebenso eingesetzt werden, um interne Systemprozesse zubeschreiben.

Aktivitätsdiagramme sind in vielen Aspekten ähnlich zuPetri-Netzen. Im Unterschied zu Petri-Netzen bieten sie zusätzlicheModellierungsmöglichkeiten, haben jedoch keine formale Semantik.



Plan einreichen

Plan erstellen

Phase parallelerAktivitäten

Bauplatz wählen

Startknoten

Architekt suchen

Arbeit im Büro

[angenommen]

Plan

[nicht angenommen]

Arbeit auf Baustelle

Aktivitätsende

Haus fertigstellen

Beispiel:

Hausbau



Wir vergleichen nun die Bestandteile von Aktivitätsdiagrammen mitPetrinetzen (angelehnt an die Semantik von Störrle):

AktionEine Aktion wird durch ein Rechteck mit abgerundeten Eckendargestellt. Es entspricht einer Transition eines Petrinetzes.

Plan erstellen Plan erstellen



KontrollflussDer Kontrollfluss, d.h. die Kanten, zwischen den Aktionen wird indem entsprechenden Petrinetz durch Hilfsstellen dargestellt.

Architekt suchen

Bauplatz wählen

Plan erstellen

Bauplatz wählen

Architekt suchen

Plan erstellen



Objektknoten

Objektknoten beschreiben Speicher für die Übergabe von Objektenbzw. Ressourcen. Sie entsprechen den Stellen des Petrinetzes.

Plan

Plan

Plan erstellen

Plan einreichen

Plan erstellen

Plan einreichen

Bemerkung: Objektknoten sind mit Klassennamen beschriftet. Siekönnen mehrere Instanzen dieser Klasse enthalten.



Entscheidungsknoten (auch: Verzweigungsknoten)

Entscheidungsknoten (decision nodes) beschreiben eineVerzweigung des Kontrollflusses, wobei aus den möglichenKontrollflüssen genau einer ausgewählt wird. Sie werden durchHilfsstellen repräsentiert, die sich in der Vorbedingung mehrererTransitionen befinden.

Plan einreichen

Hilfstransition[angenommen]

[nicht angenommen]

Plan einreichen

Bei Bedarf (v.a. bei nachfolgenden Entscheidungs- oderObjektknoten) muss noch eine Hilfstransition eingeführt werden.



Bemerkung zu Entscheidungsknoten:

Überwachungsbedingungen (Guards), die den Kontrollfluss steuern,werden in eckigen Klammern an den ausgehenden Kontrollflüssennotiert. Ähnliche Guards existieren auch in attributierten Netzen.



Verbindungsknoten

Es gibt auch sogenannte Verbindungsknoten (merge nodes), diemehrere alternative Kontrollflüsse zusammenfassen. Sie könnendurch Hilfsstellen dargestellt werden, die sich in der Nachbedingungmehrerer Transitionen befinden.

Es gibt auch Knoten, die sowohl Entscheidungs- als auchVerbindungsknoten sind, d.h., mehrere eingehende und mehrereausgehende Kontrollflüsse haben.



Gabelung (auch: Parallelisierungsknoten)

Eine Gabelung (fork node) teilt einen Kontrollfluss in mehrereparallele Kontrollflüsse auf.Sie entspricht einer Transition mit mehreren Stellen in derNachbedingung.



Vereinigung (auch: Synchronisationsknoten)

Analog dazu gibt es die Vereinigung (join node), die mehrereparallele Kontrollflüsse zusammenfasst. Sie wird durch eineTransition dargestellt, die mehrere Stellen in der Vorbedingung hat.

Wie Entscheidungs- und Verbindungsknoten kann man Gabelungenund Vereinigungen zu einem Element zusammenfassen.



Bitte beachten:

Kontrollflüsse dürfen nur an Objektknoten, Entscheidungsknotenund Gabelungen aufgespalten und an Objektknoten,Verbindungsknoten und Vereinigungen wieder zusammengeführtwerden.

Folgendes ist nicht erlaubt:

AktionAktion



StartknotenEin Startknoten entspricht einer initial markierten Stelle. EinAktivitätsdiagramm darf nur einen Startknoten haben, in den keinKontrollfluss hineinführt



AktivitätsendeDas Aktivitätsende signalisiert, dass alle Kontrollflüsse beendetwerden. Es gibt keine Entsprechung in Petrinetzen.

Es gibt auch ein Symbol für das Flussende, das nur den in eshineinlaufenden Kontrollfluss beendet.



Plan einreichen

fork

Arbeit im BüroArbeit auf Baustelle

join

Architekt suchen

PlanPlan erstellen

Bauplatz wählen

Hilfstransition

Haus fertigstellen

ÜbersetztesPetrinetz



Aktivitätsdiagramme enthalten noch mehr Anleihen ausPetrinetzen. Beispielsweise können auch die Kapazität einesObjektknotens und das Gewicht eines Kontrollflusses spezifiziertwerden.

Gericht

{upperBound=6}

2Gericht zubereiten Gericht servieren

6

Gericht zubereiten Gericht servieren

Gericht

{weight=2}

Dabei beschreibt upperBound die Kapazität einer Stelle (maximal 6Gerichte dürfen gleichzeitig fertig sein) und weight das Gewicht(immer 2 Gerichte werden gleichzeitig serviert).

In Aktivitätsdiagrammen darf noch zusätzlich spezifiziert werden, inwelcher Reihenfolge die Objekte aus dem Objektknoten genommenwerden (unordered, ordered, LIFO, FIFO).



Vorsicht:

Die Entsprechung zwischen Aktivitätsdiagrammen undPetrinetzen ist nicht immer ganz exakt. Nicht alle Konzepteentsprechen einander.Das liegt teilweise auch daran, dass Aktivitätsdiagramme nurein semi-formales Modell sind und nicht alle Aspektevollständig spezifiziert sind.



Es gibt auch die Möglichkeit zur weiteren Strukturierung vonAktivitätsdiagrammen:

Aktivitätsbereiche (activity partitions/swimlanes)

Zusammenfassung mehrerer Knoten (Aktionen, Objektknoten, etc.)zu einer Einheit. Dies dient im allgemeinen dazu, um dieVerantwortung für bestimmte Aktionen festzulegen.

Gast Kellner

Gericht bestellen

Gericht servierenGericht verspeisen

Bestellung aufnehmen


Aktivitätsdiagramm mit Aktivitätsbereichen



Weitere Elemente von Aktivitätsdiagrammen:

Pins: Parameter und Parametersätze für AktionenSenden und Empfang von SignalenKontrollstrukturen: Schleifenknoten, BedingungsknotenUnterbrechungsbereiche (interruptible activity region) zurBehandlung von Ausnahmen (Exceptions)Expansionsbereiche (expansion region) zur wiederholtenAusführung von Aktivitäten für mehrere übergebene Objekte


Zustandsdiagramme

Zustandsdiagramme (state diagrams, auch state machine diagramsoder statecharts) genannt, sind eng verwandt mit den bereitseingeführten Zustandsübergangsdiagrammen.

Sie werden eingesetzt, wenn bei der Modellierung der Fokus auf dieZustände und Zustandsübergänge des Systems gelegt werden soll.

Im Gegensatz zu Aktivitätsdiagrammen werden auch weniger dieAktionen des Systems, sondern eher die Reaktionen des Systemsauf die Umgebung beschrieben.


Zustandsdiagramme

Anwendungen sind die Modellierung von:

Protokolle, Komponenten verteilter SystemenBenutzeroberflächenEingebettete Systemen. . .

Zustandsdiagramme wurden 1987 von David Harel unter demNamen Statecharts eingeführt. Harel modellierte damit vollständigseine Armbanduhr.


Zustandsdiagramme

Eigenschaften von Zustandsdiagrammen:

Zustände und Zustandsübergänge (Transitionen)Hierarchisch aufgebaute Zustände“Parallelschalten” von Zustandsdiagrammen durch RegionenHistorien, um sich früher besuchte Zustände zu merken und indiese zurückzukehren

Viele dieser Eigenschaften dienen dazu, unübersichtlicheZustandsdiagramme mit vielen Zuständen und Übergängenübersichtlicher und kompakter zu gestalten.


Zustandsdiagramme

Wir lernen Zustandsdiagramme am Beispiel der Modellierung einerArmbanduhr kennen (stark vereinfacht gegenüber HarelsArmbanduhr).

Die Armbanduhr hat zwei Knöpfe (a,b) und zwei Modi(Zeitanzeige, Alarmeinstellung). Zwischen diesen Modi wechseltman mit Hilfe von Knopf a.Der Alarm kann aus (off) oder an (on) sein. Man kann zwischenden Alarmzuständen mit Hilfe von Knopf b wechseln.

ba 9:21 ba baAlarm Alarm

a

a

a

b

b

on off


Zustandsdiagramme

Wir beginnen zunächst mit der Modellierung der Minutenanzeige.

10 . . .

. . .

after(1 min) after(1 min)

after(1 min) after(1 min)after(1 min)

2

575859


Zustandsdiagramme

ZustandEin Zustand eines Zustandsdiagramms wird durch ein Rechteck mitabgerundeten Ecken dargestellt.

0

StartzustandDer Startzustand wird durch einen schwarzen ausgefüllten Kreisgekennzeichnet (ähnlich wie bei Aktivitätsdiagrammen).

0


Zustandsdiagramme

EndzustandEndzustände werden wie das Aktivitätsende inAktivitätsdiagrammen gekennzeichnet.

A

Für den Fall, dass man ein System modelliert, das nicht terminierensoll, gibt es keinen Endzustand (wie in unserem Beispiel).


Zustandsdiagramme

Transition (= Zustandsübergang)

Eine Transition ist ein Pfeil, der mit Ereignis [Bedingung]/Effektbeschriftet ist. (Bedingung und Effekt sind optional.)

Ereignis: Signal oder Nachricht, die die entsprechendeTransition auslösen.

10after(1 min)

Bedingung: Überwachungsbedingung (auch Guard genannt).Effekt: Effekt, der durch die Transition ausgelöst wird .

Im obigen Beispiel (Minutenanzeige) gibt es nur Ereignisse(sogennante time events), die die Zeitspanne spezifizieren, nach derdie Transition ausgelöst wird. Es gibt aber auch andere Ereignisse,beispielsweise Methodenaufrufe.


Zustandsdiagramme

Neben den Effekten, die durch Transitionen ausgelöst werden,können in einem Zustand weitere Aktionen bei Eintritt, Verweilenoder Verlassen ausgelöst werden.Sie haben den gleichen Aufbau wie die Beschriftung einerTransition: Ereignis [Bedingung]/Effekt. Dabei kann Ereignis unteranderem folgendes sein:

entry: der entsprechende Effekt wird bei Eintritt in denZustand ausgelöst.do: der Effekt ist eine Aktion, die nach Betreten des Zustandsausgeführt wird und die spätestens dann endet, wenn derZustand verlassen wirdexit: der entsprechende Effekt wird bei Verlassen des Zustandsausgelöst.


Zustandsdiagramme

Beispiel: die Uhr soll zu jeder vollen Stunden ein Signal von sichgeben. Daher wird die Aktion beep bei Eintritt in den Zustand 0ausgelöst.

0

entry/beep


Zustandsdiagramme

Wie sieht es mit der Stundenanzeige aus? Diese soll parallel zurMinutenanzeige laufen, d.h., die Uhr ist in zwei Zuständengleichzeitig, ein Zustand für die Stunden, der andere für dieMinuten. Diese Situation wird durch Regionen modelliert.

RegionRegionen unterteilen ein Zustandsdiagramm in zwei Bereiche, dieparallel zueinander ausgeführt werden.

Dies erlaubt uns, insgesamt nur 24+ 60 = 84 Zustände, anstatt24 · 60 = 1440 Zustände zu zeichnen.


Zustandsdiagramme

So sieht das modifizierte Zustandsdiagramm für die Uhr jetzt aus:

1 . . .

. . .

1 . . .

. . .

0

entry/beepafter(1 min) after(1 min)


2

575859

after(1 min)/h

20

22 2123

h h

hhh

Stunden

Minuten


Zustandsdiagramme

Bemerkungen:

Es gibt jetzt zwei Startzustände, die beide zu Beginn betretenwerden (Uhrzeit: 0:00).Da Stunden- und Minutenanzeige nicht vollkommenunabhängig voneinander arbeiten, ist eine Synchronisationeingebaut. Die Transition in den Minutenzustand 0 löst einenEffekt h (h für “hour”) aus.Dieser Effekt ist dann ein Trigger, der das entsprechendeEreignis triggert und den Übergang in den nächstenStundenzustand verursacht. Die beiden Transitionen werdensynchronisiert und finden gleichzeitig statt.


Zustandsdiagramme

Bemerkungen:

Transitionen verbrauchen im allgemeinen keine Zeit (imGegensatz zum Aufenthalt in Zuständen).Neben Triggern, die direkt ausgeführt werden, gibt es auchEvents, die zunächst in einer Event Queue (= Warteschlange)abgelegt werden. Diese Warteschlange wird schrittweiseabgearbeitet, wobei die entsprechenden Ereignisse ausgelöstwerden. Damit kann asynchrone Kommunikation beschriebenwerden.Effekte können direkte Kommunikation bedeuten(beispielsweise Methodenaufrufe), können aber auchsogenannte Broadcasts (= Rundrufe) sein. Diese sind überallim Zustandsdiagramm sichtbar. (Die ursprünglicheStatecharts-Semantik von Harel verwendete nur Broadcasts.)


Zustandsdiagramme

Nun soll noch die Möglichkeit hinzugefügt werden, das Alarmsignalzur vollen Stunden aus- und wieder einzuschalten. Dazu führen wirweitere Zustände (Alarm on, off) ein, in die man durch Drückenvon a gelangt.

Problem: wir brauchen mindestens 84 mit a beschrifteteTransitionen, die aus den Stunden-/Minutenzuständen ausgehen!Das sind ziemlich viele . . .

Dafür bieten Zustandsdiagramme folgende Lösung:

Zusammengesetzte ZuständeZusammengesetzte Zustände dienen dazu, um Hierarchien vonZuständen zu modellieren und damit ein- und ausgehendeTransitionen zusammenzufassen.


Zustandsdiagramme

Damit ergibt sich folgendes Diagramm:

1 . . .

. . .

1 . . .

. . .

20

22 2123

h h

hhh

Stunden

Minuten



2

575859

after(1 min)/h

0

entry/beep

on

off

a

ab b

Alarm


Zustandsdiagramme

Um eine gewisse Flexibilität bei der Modellierung zu haben, werdenverschiedene Eintritts- und Austrittsmöglichkeiten bereitgestellt.

Eintrittsmöglichkeiten in einen Zustand (graphisch)

C

B

D E

A H H∗

Eintritt über dietiefe Historie

Eintritt über die

flache Historie

EintrittExpliziter

Standard-Eintritt


Zustandsdiagramme

Beschreibung der Eintrittsmöglichkeiten:

Standard-Eintritt: dabei wird der Startzustand deszusammengesetzten Zustands angesprungen.(Forsetzung bei B , was schließlich zu einer Fortsetzung bei Dführt)Expliziter Eintritt: es wird bei dem explizit angegebenenFolgezustand fortgesetzt.(Fortsetzung bei C .)


Zustandsdiagramme

Beschreibung der Eintrittsmöglichkeiten (Fortsetzung):

Eintritt über die tiefe Historie: Wurde der zusammengesetzteZustand bereits früher besucht, so wird der letzte vor demVerlassen des Zustands aktive Unterzustand dertiefstmöglichen Ebene betreten.(Falls also der zusammengesetzte Zustand das letzte Mal vonE aus verlassen wurde, so wird jetzt wieder bei E fortgesetzt.)Falls man noch niemals zuvor diesen zusammengesetztenZustand betreten hat, so wird der Zustand betreten, der mitder Kante gekennzeichnet ist, die aus dem H∗-Knoten ausgeht.


Zustandsdiagramme

Beschreibung der Eintrittsmöglichkeiten (Fortsetzung):

Eintritt über die flache Historie: Wurde der zusammengesetzteZustand bereits früher besucht, so wird der letzte vor demVerlassen des Zustands aktive Unterzustand der oberstenEbene betreten.(Falls also der zusammengesetzte Zustand das letzte Mal vonE aus verlassen wurde, so wird jetzt bei B fortgesetzt, wasletztendlich zu einer Fortsetzung bei D führt.)

Außerdem: Eintritt über einen Eintrittspunkt (wird hier nichtbehandelt).


Zustandsdiagramme

Wenn ein Zustand in mehrere Regionen unterteilt ist, so ergebensich bei den Eintrittsmöglichkeiten einige Besonderheiten.

Eintrittsmöglichkeiten bei Regionen (graphisch)

A B

C D

Standard-Eintritt

ExpliziterEintritt

Eintrittüber Gabelung


Zustandsdiagramme

Beschreibung der Eintrittsmöglichkeiten bei Regionen:

Standard-Eintritt: dabei werden die jeweiligen Startzuständeder Regionen angesprungen.(Fortsetzung bei A und C )Expliziter Eintritt: ein Zustand einer Region wird direktangesprungen. In der anderen Region wird bei dementsprechenden Startzustand fortgesetzt.(Fortsetzung bei B und C .)Eintritt über Gabelung: ähnlich wie bei Aktivitätsdiagrammenwird eine Gabelung eingesetzt, um die beiden anzuspringendenZustände in den Regionen zu kennzeichnen.(Fortsetzung bei B und D.)


Zustandsdiagramme

Austrittsmöglichkeiten aus einem Zustand (graphisch)

C

B

D E

A

Austritt aus eineminneren Zustand

Austritt auseinem zusammengesetzten Zustand


Zustandsdiagramme

Beschreibung der Austrittsmöglichkeiten:

Austritt aus einem zusammengesetzten Zustand: sobald dasmit der Transition assoziierte Ereignis stattfindet, wird jederbeliebige (Unter-)Zustand von A verlassen.Austritt aus einem inneren Zustand: die Transition wird nurgenommen, wenn man sich gerade im entsprechenden Zustand(hier: Zustand E) befindet (und das entsprechende Ereignisstattfindet).

Außerdem: Austritt über einen Austrittspunkt, über einenEndzustand oder Terminator (wird hier nicht behandelt).


Zustandsdiagramme

Beispiel zu Austrittsmöglichkeiten:

B C

A

D

E

a

entspricht B C

A

D

E

a aa


Zustandsdiagramme

Auch für Austrittsmöglichkeiten müssen wir untersuchen, was sichbei Regionen ändert.

Austrittsmöglichkeiten bei Regionen (graphisch)

A B

C D

Austritt aus einemzusammengesetzten

Zustand

Austritt aus eineminneren Zustand

Austrittüber Vereinigung


Zustandsdiagramme

Beschreibung der Austrittsmöglichkeiten bei Regionen:

Austritt aus einem zusammengesetzten Zustand: dabei wirdder zusammengesetzte Zustand verlassen, egal in welchenUnterzuständen man sich gerade befindet.Austritt aus einem inneren Zustand: der zusammengesetzteZustand wird nur verlassen, wenn man sich in der jeweiligenRegion in dem Zustand befindet, der durch den Pfeil verlassenwird. In den anderen Regionen kann man sich in beliebigenZuständen befinden.(Austritt nur, wenn man sich in der ersten Region in Bbefindet.)


Zustandsdiagramme

Beschreibung der Austrittsmöglichkeiten bei Regionen(Fortsetzung):

Austritt über Vereinigung: ähnlich wie beiAktivitätsdiagrammen wird eine Vereinigung eingesetzt, ummehrere Regionen zusammenzuführen. Der zusammengesetzteZustand kann nur verlassen werden, wenn man sich in denZuständen befindet, von denen Pfeile in die Vereinigunghineinführen.(Austritt nur, wenn man sich in B und D befindet.)


Zustandsdiagramme

Wieder zurück zur Arbanduhr. Es gibt ein weiteres Problem: wennman aus der Alarmeinstellung zurückkehrt, ist die Zeit auf 0:00zurückgesetzt!

Lösung: Verwendung des Eintritts über die (flache) Historie.Da man im Fall der Zeitanzeige in zwei Regionen gleichzeitigeintreten muss, verwenden wir eine Gabelung.


Zustandsdiagramme

1 . . .

. . .

1 . . .

. . .

on

off

b b

20

22 2123

h h

hhh

Stunden

Minuten



2

575859

after(1 min)/h

0

entry/beep

a

Alarma

H

H

H


Zustandsdiagramme

Weiteres Problem: wenn man längere Zeit im Alarm-Zustandverbringt, so wird in dieser Zeit die Minuten-/Stundenanzeige nichtentsprechend aktualisiert. Das Time Event (after(1 min)) beziehtsich nur auf die Zeit, die seit dem Eintritt in den entsprechendenZustand vergangen ist.

Die Zeitanzeige müsste deshalb entsprechend aktualisiert werden.Dieses Problem wird hier nicht gelöst.


Zustandsdiagramme

Was fehlt noch?

Beim Wechseln zwischen den Alarm-Zuständen (on,off) mussein Flag (genannt al) gesetzt werden, um damit den beep-Effekt zukontrollieren.

Dieses Flag muss mit Hilfe einer Bedingung im Minutenzustand 0abgefragt werden.

Außerdem betreten wir den Zustand Alarm nun nicht mehr über dieflache Historie, sondern fragen mit Hilfe von Bedingungen ab, wieal belegt ist. (Damit ist die Markierung des Anfangszustandseigentlich überflüssig geworden.)


Zustandsdiagramme

1 . . .

. . .

. . .

. . .

1

20

22 2123

h h

hhh

Stunden

Minuten

after(1 min) after(1 min)575859

after(1 min)/h

a

Alarm

on

off

b/al=1

entry[al==1]/beepafter(1 min) after(1 min)

0

b/al=0

a[al==1]

a[al==0]

H

H


Zustandsdiagramme

Wir modellieren, dass die Batterie der Uhr kaputtgehen kann undgewechselt werden muss.

In diesem Fall will man den zusammengesetzten Zustand nicht überdie flache oder tiefe Historie betreten! Es wird also hier tatsächlichdie Zeit auf 0:00 zurückgesetzt.Außerdem setzen wir das Flag al beim Einsetzen der Batteriezurück auf den Anfangswert 1.


Zustandsdiagramme

1 . . .

. . .

. . .

. . .

1

Uhr

20

22 2123

h h

hhh

Stunden

Minuten

after(1 min) after(1 min)575859

after(1 min)/h

a

Alarm

on

off

b/al=1

entry[al==1]/beepafter(1 min) after(1 min)

0

a[al==1]

a[al==0]

b/al=0 H

H

Batterie kaputt

Batterie geht kaputt Neue Batterie wird eingesetzt/al=1


Zustandsdiagramme

Ein großer Teil der Modellierungsmöglichkeiten vonZustandsautomaten dient dazu, Zustandsdiagramme kompakt undübersichtlich zu notieren.

Oft kann man Zustandsdiagramme “flachklopfen” undzusammengesetzte Zustände auflösen, wodurch man äquivalenteZustandsdiagramme erhält, die die gleichen Übergänge erlauben.Dabei erhält man jedoch im allgemeinen mehr Zustände und/oderTransitionen.

Wir sehen uns einige Beispiele an . . .


Zustandsdiagramme

Beispiel 1: Wandeln Sie folgendes Zustandsdiagramm in ein“flaches” Zustandsdiagramm um:

A

B

C

D

a

b

e

c df


Zustandsdiagramme

Lösung zu Beispiel 1:

A

B

C

D

e

c d

a

b

f

e

Idee: die Transition, die von dem zusammengesetzten Zustandwegführt, durch mehrere Transitionen ersetzen, die von den innerenZuständen ausgehen.


Zustandsdiagramme


A B C D

E F

a b c

e

gG

h


Zustandsdiagramme


b c

g

h

a

b c

e e e

(D,F)(C,F)(B,F)

(B,E) (C,E) (D,E)

G

A

h

Idee: Kreuzprodukt der Zustandsmengen der Regionen bilden.


Zustandsdiagramme


H

A

B

C

Db

e

c da f

Xx


Zustandsdiagramme


Xx

C

D

c da f a f

A(C)

B(C)

A(D)

B(D)b

e

e

b

Idee: in den äußeren Zuständen muss man sich merken, auswelchem Zustand man den zusammengesetzten Zustand verlassenhat. Dies führt zu zusätzlichen Zuständen.


Zustandsdiagramme

Weitere Elemente von Zustandsdiagrammen:

Unterscheidung zwischen verschiedenen Arten von Ereignissen:call event, signal event, change event, time event, any receiveeventVerzögern und Ignorieren von EreignissenEntscheidungen und KreuzungenRahmen und Wiederverwendung von Zustandsdiagrammen

Außerdem: Generalisierung und Spezialisierung vonZustandsdiagrammen


Zustandsdiagramme

Zusammenfassung:Nach Harel werden Zustandsdiagramme bzw. deren Eigenschaftendurch folgende “Formel” beschrieben:

UML-Zustandsdiagramme =Zustandsübergangsdiagramme + Tiefe + Orthogonalität(+ Broadcast-Kommunikation)

Dabei steht “Orthogonalität” für die Parallelität, die durchRegionen erreicht werden kann.


Sequenzdiagramme

Sequenzdiagramme (sequence diagrams) sind die bekanntestenVertreter von Interaktionsdiagrammen in UML.

Sie dienen dazu, um Kommunikation und Interaktion zwischenmehreren Kommunikationspartnern zu modellieren und beruhen aufdem Basiskonzept der Interaktion:

InteraktionEine Interaktion ist das Zusammenspiel von mehrerenKommunikationspartnern.Typische Beispiele: Versenden von Nachrichten, Datenaustausch,Methodenaufruf


Sequenzdiagramme

Sequenzdiagramme waren bereits vor Aufnahme in die UML unterdem Namen message sequence charts bekannt.

Im Gegensatz zu Aktivitätsdiagrammen oder Zustandsdiagrammenbeschreiben sie im allgemeinen nicht alle Abläufe eines Systems,sondern nur einen oder mehrere mögliche Abläufe.


Sequenzdiagramme

Sequenzdiagramme beschreiben Interaktionen in zwei Dimensionen:

Von links nach rechts: Anordnung der Kommunikationspartnerals LebenslinienOft wird der Partner, der den Ablauf initiiert ganz linksangegeben.Von oben nach unten: Zeitachse


Sequenzdiagramme

Beispiel Restaurant

Petra:Gast

Robert:Kellner

Ina:Köchin

Mustafa:Kassierer

Menü bringen

bestellenbestellen

Getränk servieren

Essen abholenEssen servieren

bezahlen


Sequenzdiagramme

KommunikationspartnerDie Kommunikationspartner in einem Sequenzdiagramm werdenähnlich wie in Objektdiagrammen als Rechtecke notiert.Manchmal werden die Rechtecke auch weggelassen. MenschlichePartner werden auch durch ein Strichmännchen symbolisiert:

Von jedem Kommunikationspartner führt eine gestrichelteLebenslinie nach unten.


Sequenzdiagramme

AusführungsbalkenAktivitäten eines Kommunikationspartners werden durchsogenannte Ausführungsbalken dargestellt.

Parallele Tätigkeiten eines Kommunikationspartners werden dabeidurch übereinander liegende Ausführungsbalken beschrieben (sieherechts oben).Während die Balken aktive Zeit anzeigen, symbolisieren diegestrichelten Linien passive Zeit.


Sequenzdiagramme

NachrichtenDie Nachrichten beschreiben die Kommunikationen bzw.Interaktionen der Kommunikationspartner und werden durch Pfeiledargestellt. Eine Nachricht hat einen Sender und einen Empfänger.Die Stellen, an denen die Pfeile auf den Lebenslinien auftreffen,nennt man auch Sendeereignis und Empfangsereignis.

EmpfängerSender

Name der NachrichtEmpfangs-ereignis

Sende-ereignis


Fallstudie: Fahrkartenautomat - Klassendiagramm

FA-Controller

+F_Stufe: char

+F_Preis: float

+Einnahme: float

+F_anfordern(Stufe:char)

+Preis_ber(Stufe:char): float

+bezahlt(Einnahme:float)

FA-Display

+Betrag: float

+Text: String

+Betrag_anz(Preis:float)

+Text_anz(Text:string)

FA-Geldannahme

+Einnahme: float

+Annahme_öffnen()

+Annahme schließen()

+Einwurf(Betrag:float)

+Restgeld(Betrag:float)

FA-Drucker

+F-Stufe: char

+F-Preis: float

+F_drucken(S:char,P:float)


Fallstudie: Fahrkartenautomat - Sequenzdiagramm

Kunde

F_anfordernPreis_ber

Betrag_anz

Annahme_öffnen

Einwurf

bezahlt

Betrag_anz

Einwurf

bezahlt

Betrag_anz

Text_anz

Annahme_schließen

Restgeld

F_drucken

C: FA-Controller G: FA_Geldannahme D: FA-DruckerA: FA-Display


Sequenzdiagramme

Synchrone und asynchrone NachrichtenBei synchroner Kommunikation warten Sender und Empfängeraufeinander. Der Sender macht erst dann weiter, wenn er weiß, dassder Empfänger die Nachricht erhalten hat. Sie wird durch eineschwarze ausgefüllte Pfeilspitze dargestellt.


Sequenzdiagramme

Synchrone und asynchrone Nachrichten (Fortsetzung)

Bei asynchroner Kommunikation wartet der Sender nicht darauf,dass der Empfänger die Nachricht erhalten hat. Er arbeitet einfachweiter. Die Nachricht wird durch eine einfache Pfeilspitze wirddargestellt.

Bei asynchronen Nachrichten kann es zu einer Zeitverzögerungzwischen Sende- und Empfangsereignis kommen, die durch einengeneigten Pfeil beschrieben wird (siehe oben rechts).


Sequenzdiagramme

Bei asynchroner Kommunikation (aber nicht bei synchronerKommunikation) kann auch der Fall eintreten, dass sichNachrichten überholen oder kreuzen.

Das Überholen der Nachrichten (oben links) ist nur dann nichtmöglich, wenn man explizit einen FIFO-Kanal fordert.


Sequenzdiagramme

Was jedoch nicht möglich ist, ist eine Nachricht, die “rückwärts” inder Zeit läuft und vor dem Senden ankommt.


Sequenzdiagramme

Es ist jedoch möglich, eine Nachricht an sich selbst zu schicken.

:Gast

Gericht aussuchen

Bei einer synchronen Nachricht sollte man dabei paralleleAusführungsbalken verwenden, da das Sende- und Empfangsereignisparallel stattfinden müssen.


Sequenzdiagramme

Nachrichten, die als Antworten auf frühere Nachrichten gedachtsind, werden durch gestrichelte Pfeile notiert. Dabei sollte derName der ursprünglichen Nachricht wiederholt werden.

Nachfrage

Antwort auf Nachfrage


Sequenzdiagramme

Wir machen uns nun Gedanken über die Reihenfolge der Ereignissein einem Sequenzdiagramm. Dazu ist es nützlich sich klarzumachen,was eine (partielle) Ordnung ist.

Partielle OrdnungGegen sei eine Menge X . Eine partielle Ordnung auf X ist eineRelation R ⊆ X × X mit folgenden Eigenschaften:

Reflexivität: für jedes x ∈ X gilt (x , x) ∈ RTransitivität: aus (x1, x2) ∈ R und (x2, x3) ∈ R fürx1, x2, x3 ∈ X folgt (x1, x3) ∈ R .Antisymmetrie: aus (x1, x2) ∈ R und (x2, x1) ∈ R fürx1, x2 ∈ X folgt x1 = x2.


Sequenzdiagramme

Weitere Bezeichnungen:

Partielle Ordnung bezeichnet man oft mit dem Zeichen ≤ undnotiert in Infix-Schreibweise (x1 ≤ x2 statt (x1, x2) ∈ R).Wir schreiben x1 < x2, falls x1 ≤ x2 und x1 6= x2.

Vorsicht: Die Relation < ist selbst keine partielle Ordnung.


Sequenzdiagramme

Totale OrdnungEine partielle Ordnung ≤ heißt total, wenn für zwei beliebigeElemente x1, x2 ∈ X immer x1 ≤ x2 oder x2 ≤ x1 gilt.

Beispiele:

Die ≤-Relation auf den ganzen Zahlen Z ist eine totaleOrdnung.Ein typisches Beispiel für eine partielle Ordnung, die nicht totalist, ist die Inklusionsordnung ⊆ auf Mengen.


Sequenzdiagramme

Reflexiv-transitive HülleFür eine gegebene Relation R ⊆ E × E beschreiben wir derenreflexiv-transitive Hülle R∗. Man erhält sie aus R , indem man

alle Paare (e, e) mit e ∈ E zu R hinzufügt undbei (e1, e2), (e2, e3) ∈ R auch (e1, e3) zu R hinzufügt. DieserProzess wird so lange wiederholt, bis keine neuen Paare mehrhinzukommen.

Die reflexiv-transitiv Hülle R∗ einer Relation R ist immerreflexiv und transitiv. Sie ist jedoch nicht immerantisymmetrisch und daher nicht notwendigerweise eineOrdnung.Die Relation R∗ ist die kleinste reflexive und transitiveRelation, die R enthält.


Sequenzdiagramme

Beispiel:

Die reflexiv-transitive Hülle von

R = {(1, 2), (2, 3), (3, 4), (3, 5)}

ist

R∗ = {(1, 2), (2, 3), (3, 4), (3, 5),(1, 1), (2, 2), (3, 3), (4, 4), (5, 5),(1, 3), (1, 4), (1, 5), (2, 4), (2, 5)}


Sequenzdiagramme

Die Elemente von Sequenzdiagrammen, die nun geordnet werden,sind die Ereignisse, d.h., Sende- und Empfangsereignisse.

In den Sequenzdiagrammen, wie wir sie bisher kennengelernt haben,sind die Ereignisse immer total geordnet, nach folgendem Schema:

(Sendeereignis der Nachricht N) < (Empfangsereignis von N)Die restlichen Ereignisse sind entsprechend dem zeitlichenVerlauf geordnet.


Sequenzdiagramme

Petra:Gast

Robert:Kellner

Ina:Köchin

Mustafa:Kassierer

Menü bringen

bestellenbestellen

Getränk servieren

Essen abholenEssen servieren

bezahlen

R5

P1

P2

P3

P4

P5

R1

R2R3

R4

R6

I1

I2

M1

R1 < P1 < P2 <R2 < R3 < I1 < R4< P3 < I2 < R5 <R6 < P4 < P5 <M1


Sequenzdiagramme

In einem einfachen Sequenzdiagramm (Erweiterungen werden nochbesprochen) werden daher die Ereignisse immer in eine Reihenfolgegebracht. Die Ordnung ist daher total. Im folgenden Diagramm giltbeispielsweise:

A1 < B1 < C1 < D1

A1

A B C D

B1

C1 D1


Sequenzdiagramme

Nicht so günstig sind Diagramme, aus denen die Reihenfolge vonNachrichten nicht klar hervorgeht:

A BA1

A B C D

B1 C1 D1

Insbesondere ist die Darstellung echter Parallelität inSequenzdiagrammen nicht vorgesehen.


Sequenzdiagramme

Äquivalenz von SequenzdiagrammenZwei Sequenzdiagramme sind äquivalent, wenn sie die gleichenEreignisse enthalten und die Reihenfolge der Ereignisse identisch ist.Dabei können die Diagramme durchaus verschieden gezeichnet sein(andere Reihenfolge der Kommunikationspartner, verschiedeneAbstände zwischen den Ereignissen, . . . ).


Sequenzdiagramme

Bisher haben wir gesehen, wie man mit einem Sequenzdiagrammeinen möglichen Ablauf beschreiben kann. In manchen Fällenmöchte man jedoch mehrere (vielleicht sogar alle) Abläufebeschreiben.

Dazu gibt es die Möglichkeit, kombinierte Fragmente zu verwenden,bei denen mehrere (Interaktions-)Operanden (=Teil-Sequenzdiagramme) mit Hilfe von Interaktions-Operatorenzusammengesetzt werden.

Wir betrachten im folgenden einige dieser Interaktions-Operatoren.


Sequenzdiagramme

Interaktionsoperator par (Parallelität)

Hier sind die Operanden in beliebiger Reihenfolge ausführbar. DieReihenfolge der Ereignisse in den Operanden muss aber gewahrtwerden, ansonsten gibt es keine Bedingungen.

:X :Y

par

X1 Y1

X2 Y2

X3 Y3

Dabei wird der Operator parlinks oben in der Eckeangegeben.

Eine gestrichelte waagrechteLinie trennt die verschiedenenOperanden.


Sequenzdiagramme

Nachrichten, die von einem Operanden in einen anderen laufen,sind nicht zugelassen.

:X :Y

par

X1

Y1


Sequenzdiagramme

Ordnung auf den Ereignissen:X1 < Y1 < Y2 < X2 (Operand 1)X3 < Y3 (Operand 2)

Ansonsten gibt es keine weiteren Einschränkungen

Dieses Sequenzdiagramm beschreibt insgesamt fünfzehn Abläufe,beispielsweise:

X1, Y1, X3, Y3, Y2, X2X3, X1, Y1, Y2, X2, Y3. . .


Sequenzdiagramme

Weitere Bemerkungen: um die Ereignis-Ordnung innerhalb einespar-Operators zu bestimmen . . .

verwendet man die partiellen Ordnungen der einzelnenOperanden (≤1, ≤2)und vereinigt diese. Die Vereinigung ≤1 ∪ ≤2 ist ebenfalls einepartielle Ordnung und beschreibt alle möglichen Reihenfolgenvon Ereignissen.

Jede Ereignisreihenfolge, bei der ein Ereignis X immer vor einemEreignis Y auftritt, falls X<Y gilt, ist eine mögliche Reihenfolge.


Sequenzdiagramme

Interaktionsoperator seq (schwache Sequenz)

Die Reihenfolge der Ereignisse in den Operanden muss wiedergewahrt werden, außerdem ist die Reihenfolge der Ereignisse aufden Lebenslinien (von oben nach unten) festgelegt.

:X

X1

:Y :Z :W

seq

Y1

Z1 Z2

Y2X2


Sequenzdiagramme

Ordnung auf den Ereignissen:X1 < Y1 < Z1 < Z2 (Operand 1)X2 < Y2 (Operand 2)X1 < X2 (Lebenslinie von X)Y1 < Y2 (Lebenslinie von Y)

Dieses Sequenzdiagramm beschreibt neun verschiedene Abläufe,beispielsweise:

X1, X2, Y1, Z1, Z2, Y2X1, Y1, X2, Y2, Z1, Z2. . .


Sequenzdiagramme

Weitere Bemerkungen: um die Ereignis-Ordnung innerhalb einesseq-Operators zu bestimmen . . .

verwendet man die partiellen Ordnungen der einzelnenOperanden (≤1, ≤2),außerdem die partiellen Ordnungen der einzelnen Lebenslinien(≤X , ≤Y , . . . ),vereinigt diese und bestimmt die reflexiv-transitive Hülle.Dabei entsteht eine partielle Ordnung, die alle möglichenReihenfolgen von Ereignissen beschreibt.


Sequenzdiagramme

Bei Interaktions-Operanden ist es außerdem möglich, zusätzlicheOrdnungsbeziehungen einzuführe, die ansonsten nicht abgedecktsind. (Durch gestrichelte Linien mit Pfeil in der Mitte.)

:X

X1

:Y :Z :W

Y1

Z1 Z2

Y2

par

X2

Die neue partielle Ordnung kann man hier dadurch bestimmen,indem man die neuen Paare hinzufügt und die reflexiv-transitiveHülle der Gesamtrelation bildet.


Sequenzdiagramme

Weitere Interaktions-Operatoren (Liste ist nicht vollständig):

strict (Strikte Sequenz): Die Reihenfolge der Ereignisse wirdvon oben nach unten strikt eingehalten (wie in einem einzelnenOperanden).alt (Alternative): entsprechend einer If-Then-Else-Anweisung(mit Bedingungen)neg (Negation): beschreibt eine ungültigeNachrichtenreihenfolgeloop (Schleife): beschreibt die Wiederholung eines Operanden


Sequenzdiagramme

Beispiel: wir modellieren ein Protokoll, bei dem einClient-Rechner S einen E-Mail an einen anderen Client R verschickt.

Weitere Beteiligte sind der Mail-Server von S, der Mail-Servervon R und der DNS-Server, der benötigt wird, um Mail-Adressen indie IP-Adressen des entsprechenden Servers umzuwandeln (DNS =domain name system).


Sequenzdiagramme

par Mail ausliefern

Bestätigung Ausliefern

Bestätigung Einliefern

IP-Adresse von E2

Mail einliefernFrage nach IP-Adresse

Kontaktaufnahme

Verifiziere, ob

:ClientS1

:ServerS2

:DNS :ServerE2

:ClientE1

Name von S2 korrekt

Antwort Verifikation

Bestätigung der Kontaktaufnahme

Verschicken der Mail

Bestätigen der Mail


Sequenzdiagramme

Bemerkung: dieses Sequenzdiagramm ist an den Ablauf imSMTP-Protokoll angelehnt (SMTP = send mail transportprotocol), ist jedoch erheblich vereinfacht.

Sequenzdiagrammen zu vielen TCP/IP-Netzwerkprotokollen findetman unter:

http://www.eventhelix.com/Realtimemantra/Networking/


Sequenzdiagramme

Es gibt noch einige weitere Arten von Nachrichten:

Gefundene und verlorene NachrichtenBei gefundenen und verlorenen Nachrichten werden das Sende-bzw. das Empfangsereignis nicht explizit modelliert. DieNachrichten tauchen quasi aus der Umgebung auf undverschwinden wieder dorthin.

Solche Nachrichtenwerden benötigt, wenndie entsprechendenKommunikationspart-ner nicht mitmodelliertwerden.

:Fenster

schließen

Gefundene Nachricht

Lärm

Ruhe!

Verlorene Nachricht

:Person


Sequenzdiagramme

Erzeugung und Dekonstruktion von ObjektenAußerdem kann es passieren, dass Objekte nicht während desganzen Ablaufs zur Verfügung stehen. Sie können während desAblaufs dynamisch erzeugt und wieder zerstört werden.

Dies erfolgt zumeist durchsogenannte Erzeugungs- undDekonstruktionsnachrichtenund wird folgendermaßendargetellt:

:Zentrale

:Filialeeröffnen

Erzeugungsnachricht

Dekonstruktionsnachricht

schließen


Kommunikationsdiagramme

Kommunikationsdiagramme enthalten dieselbe Information wieSequenzdiagramme, werden jedoch anders dargestellt.

Während bei Sequenzdiagrammen der Fokus eher auf demzeitlichen Ablauf liegt, heben Kommunikationsdiagramme eher dieKommunikationsbeziehungen der Teilnehmer hervor.

Kommunikationsdiagramme gehören – genau wieSequenzdiagramme – zur Klasse der Interaktionsdiagramme.



Das Sequenzdiagramm Restaurantbesuch Diagramm wirdfolgendermaßen als Kommunikationsdiagramm dargestellt:

Robert:Kellner

Ina:Köchin

3: bestellen5: Essen abholen

Petra:Gast

Mustafa:Kassierer

7: bezahlen

1: Menü bringen2: bestellen

4: Getränk servieren6: Essen servieren



Dabei werden die Kommunikationspartner wie bisher durchRechtecke oder Strichmännchen dargestellt. Es wird jedoch keinzeitlicher Ablauf mehr dargestellt.

Die Interaktionen bzw. Nachrichten werden durch Linien notiert, andenen die Namen der Nachrichten und die Senderichtung (→)stehen.

Die Nummerierung der Nachrichten (1,2,3,. . . ) gibt die Reihenfolgean. Durch Buchstaben hinter den Nummern (2a,2b,. . . ) beschreibtman parallele Nachrichten, die in beliebiger Reihenfolge angeordnetsein können.

ModellierungUnified Modeling Language (UML)Überblick über weitere UML-Diagramme

Überblick über weitere UML-Diagramme

Wir schließen die Vorlesung mit einem kurzen Überblick über dienoch fehlenden Typen von UML-Diagrammen ab.

Zuletzt gibt es dann noch ein paar Abschlussbemerkungen.



UML-Diagramme Liste


Interaktions-diagramme

Objekt-diagramm

Kompositions-strukturdiagramm

diagrammeStruktur-

Klassen-


diagramm


Paket-diagramm

Diagrammeder UML

diagramm diagramm

diagramm


Zustands-

diagrammdiagramm






UML-Diagramme (blau: bereits behandelte Diagramme)

Objekt-diagramm


Interaktions-diagrammeKompositions-

strukturdiagramm

Struktur-

Klassen-


diagramm


Paket-diagramm

Diagrammeder UML

diagramm diagramm

diagramm


Zustands-

diagrammdiagramm




diagramme



Wir beginnen zunächst mit den beiden noch fehlenden Arten vonInteraktionsdiagrammen:

Timing-Diagramme bzw. ZeitverlaufsdiagrammeInteraktionsübersichtsdiagramme


Timing-Diagramme

Timing-Diagramme sind in der Elektrotechnik weit verbreitet undzeigen an, zu welchem Zeitpunkt welcher Kommunikationspartnerwelchen Zustand einnimmt.

Dabei wird von links nach rechts (horizontal) die Zeit aufgetragenund von oben nach unten werden die Kommunikationspartner undderen Zustände aufgetragen.


Timing-Diagramme

Beispiel: Ampelschaltung

gruen

rot

Sekunden0 10 20 30

gruen

gelbrot

gelb

rot:Autoampel

:Fussgaeng

eram

pel


Interaktionsübersichtsdiagramme

Interaktionsübersichtsdiagramme sind im wesentlichenAktivitätsdiagramme, die – anstatt der Aktionen – hierarchischweitere Interaktionsdiagramme (Sequenzdiagramme,Kommunikationsdiagramme, Timing-Diagramme) enthalten können.

Sie werden eingesetzt, wenn es eine größere Menge verschiedenerArten von Aktionen gibt, über die man sonst nur schwer denÜberblick behalten kann.

Als Beispiel betrachten wir ein Interaktionsübersichtsdiagramm, dasden Ablauf eines Freistoßes in einem Fussballspiel modelliert.



ref

:Torwart

sd Linkssprung

nach linksspringen

positionieren

sd Fussball positionieren

:Fussball[ruhend]

0 1 2 3sec

fliegendruhend

positionierenMauer

:Schuetze

Freistossfreigeben

0..3 sec

schiessendlaufendstehend

sd Freistoss ausfuehren

ref

springen

sd Rechtssprung

nach rechts

sd Stehenbleiben

stehenbleiben

[Fussball gerade]

[Fussball nach rechts][Fussball nach links]

:Fussball

sd Fussball fangen

:Torwart[fliegend]

fangen

:Torwart :Torwart

:Fussball

:Schuetze



Bemerkungen:

Interaktionsreferenzen (Schlüsselwort ref) werden verwendet,um an anderer Stelle definierte Interaktionsdiagrammewiederzuverwenden.Anstatt der Aktionen wie in Aktivitätsdiagrammen werdenganze Interaktionsdiagramme verwendet, die alle sd alsDiagrammtyp für Interaktionsdiagramme erhalten.


Anwendungsfalldiagramme

In frühen Stadien der Entwicklung und bei der Kommunikation mitdem Auftraggeber spielen auch Anwendungsfalldiagramme (engl.use case diagrams) eine grosse Rolle.

Anwendungsfalldiagramme modellieren die Funktionalität desSystems

auf einem hohen Abstraktionsniveau;aus der Black-Box-Sicht des Anwenders (d.h., nur das vonaußen Sichtbare soll beschrieben werden, nicht die interneRealisierung);durch Spezifikation der Schnittstellen.

Die Anwender bzw. Nutzer tauchen als sogenannte Akteure in denDiagrammen auf.



Beispiel: Restaurant

Gericht bestellen

Gast

Gericht verspeisen

Rechnung bezahlen

Mit Kreditkartebezahlen

Kreditkarte prüfen«include»

1

1

1..*

1..*

Kellner

Restaurant

Kreditkarten-gesellschaft

«actor»



Anwendungsfalldiagramme bestehen aus folgenden Komponenten:

SystemgrenzeDie Systemgrenze ist ein Rechteck, das beschreibt, was sichaußerhalb und innerhalb des zu erstellenden Systems befindet.

Restaurant



AkteurEin Akteur ist ein Typ oder eine Rolle, die ein externer Benutzeroder ein externes System während der Interaktion mit dem Systemeinnimmt. Menschliche Akteur werden durch Strichmännchensymbolisiert, andere Akteure durch ein Rechteck, das mit demSchlüsselwort «actor» gekennzeichnet ist

Gast

Kreditkarten-gesellschaft

«actor»



AnwendungsfallEin Anwendungsfall ist eine Menge von Aktionen, die von demSystem bereitgestellt werden und die einen Nutzen für einen odermehrere Akteure bringen. (D.h., es handelt sich dabei um eine Art“Service” des Systems.) Ein Anwendungsfall wird durch eine Ellipsedargestellt.




AssoziationWie bei Klassendiagrammen gibt es Assoziationen, vor allemzwischen Akteuren und Anwendungsfällen (welcher Akteur kannwelchen Anwendungsfall nutzen?).Assoziationen dürfen die üblichen Beschriftungen besitzen(Multiplizitäten, etc.).

Gericht bestellen

Restaurant

1 1..*

Gast



Generalisierung/Spezialisierung

Anwendungsfälle können andere Anwendungsfälle spezialisieren,d.h., sie können von ihnen erben. Dabei werden – wie bei Klassen –auch alle Assoziationen geerbt.


Rechnung bezahlen

Auch Spezialisierungsbeziehungen zwischen Akteuren sind möglich.



Include-BeziehungBei einer Include-Beziehung wird modelliert, dass einAnwendungsfall die Funktionalität eines anderen Anwendungsfallesauf jeden Fall nutzt. D.h., der zweite Anwendungsfall wird immerals eine Art “Unterprozedur” aufgerufen.


Kreditkarte prüfen«include»

Es gibt auch sogenannte Extend-Beziehungen, bei denen einAnwendungsfall nur unter bestimmten Bedingungen in einenanderen Anwendungsfall eingebunden wird.



Bemerkungen:

Anwendungsfalldiagramme sollten nicht zu viele Detailsenthalten.Sie sind ein einfaches Mittel, um Anwenderwünsche zudiskutieren und sollten nur eine grobe Sicht auf dieFunktionalität des Systems darstellen.Bei Bedarf müssen bestimmte Anwendungsfälle dann nochtextuell oder mit Hilfe anderer UML-Diagramme genauerbeschrieben werden.


Strukturierte, textuelle Beschreibung einesAnwendungsfalls

Af.-Nr. Name des Anwendungsfalles

Vorbedingungen:Nachbedingungen:Nicht-funktionale Anforderungen:Beschreibung: ..Variationen:Regeln:Services:Ansprechpartner:Anmerkungen / offene Fragen:Dialogbeispiele oder - muster:Diagramme:


Beispiel: Formular zur Beschreibung einesAnwendungsfalls


Formular zur Beschreibung eines Anwendungsfalls (2)



Wir sehen uns nun noch (ganz kurz) die fehlenden vier Typen vonStrukturdiagrammen an. UML-Übersicht

KompositionsstrukturdiagrammePaketdiagrammeVerteilungsdiagrammeKomponentendiagramme

Im weitesten Sinne dienen sie alle dazu die (übergeordnete)Struktur bzw. Architektur eines Systems darzustellen.


Kompositionsstrukturdiagramme

Kompositionsstrukturdiagramme (engl. composite structurediagrams) beschreiben die interne Struktur von Komponenten (z.B.Klassen) in einer White-Box-Darstellung. Instanzen von durchKomposition verbundenen Klassen werden dabei als sogenannteParts innerhalb der Klasse dargestellt.

:Fernsehgeraet

Antenneneingang

Antennenkabel

SatAusgang

:SatReceiver

SatKabel

:SatAntenne

SatEmpfangsAnlage

Part

Part


Paketdiagramme

Ein großes Softwaresystem muss in Pakete bzw. Module gegliedertwerden. Paketdiagramme (engl. package diagrams) beschreiben diestatische Struktur eines großen Systems durch Zusammenfassenvon Klassen in Paketen.

Kunde

kundenverwaltung personalverwaltung

Angestellter

kontenverwaltung

Konto

Girokonto Sparkonto

bank


Verteilungsdiagramme

Verteilungsdiagramme (engl. deployment diagrams) beschreiben dieHardware-Komponenten, die in einem System benutzt werden undwie diese in Beziehung stehen.

Sie können auch konkrete physische Informationseinheiten (Dateien,etc.) enthalten, die als Artefakte bezeichnet werden.

:PC0..50

:Laptop0..10

:PC0..50Host «LAN»

«Internet»

«WLAN»

1:Mehrprozessorsystem

1

1:DBClient

«deploy»

«deploy»

«deploy» «artifact»


Komponentendiagramme

Komponentendiagramme (engl. component diagrams) beschreibenim Gegensatz dazu die Software-Architektur eines Systems. Esbeantwortet die Frage, wie Klassen zur Laufzeit zu größerenKomponenten zusammengefasst werden und welche Schnittstellenangeboten und genutzt werden.

«component»

MailEingang

«component»

MailAusgang

«component»

MailManagement

Betriebüberwachen

Mailabholen

«use»


UML-Vorgehensweise

a) Von den Anforderungen zu Klassendiagrammenund dann über Anwendungsfalldiagrammen zuInteraktionsdiagrammen zu Zustandsdiagrammenparallel Übergang zu OO-Design mit Hilfe vonKomponentendiagrammenAktivitätsdiagramme nahezu beliebig zurAblaufveranschaulichung

b) Von den Anforderungen zu Use Case-Diagrammenund dann Aktivitätsdiagrammen zur Detailbeschreibung vonAnwendungsfällenund dann über Klassendiagramme zu Interaktionsdiagrammenund dann zu Zustandsdiagrammenparallel Übergang zum OO-Design mit Hilfe vonKomponentendiagrammen

Beide Ansätze nur als grobe Richtlinien, nicht als Dogmen!


Abschließende Bemerkungen

UML als semi-formale ModellierungsmethodeUML ist eine semi-formale Modellierungsmethode, d.h., nicht beijedem Sprachelement gibt es vollständige Einigkeit über dieBedeutung.Trotz dieser Kritik ist die UML ein großer Fortschritt, da sievereinheitlichte Diagramme bereitstellt, die von jedem Beteiligtenam Softwareentwicklungsprozess verstanden werden können.



Konsistenz von ModellenBei der Beschreibung eines großen Systems durch mehrere Modelleist auch darauf zu achten, dass die Modelle untereinander konsistentsind. (Beispielsweise: Klassennamen, die in einem Sequenzdiagrammverwendet werden, tauchen auch im Klassendiagramm auf.)

Es gibt Ansätze, solche Konsistenz (halb-automatisch) zu erreichen,indem man sogenannte Modelltransformationen durchführt undverschiedene Diagramme ineinander übersetzt.



Es gibt noch viele Aspekte in der UML, die wir nicht betrachtethaben. Ein wichtiger Teil der UML ist beispielsweise die OCL(Object Constraint Language), eine formale Beschreibungssprache,in der man zusätzliche Bedingungen und Invarianten ausdrückenkann.

Weitergehende Informationen über UML gibt es in zahllosenBüchern (siehe Literaturliste) und auf den Seiten der OMG (ObjectManagement Group):

http://www.omg.org/technology/documents/formal/uml.htm

Und natürlich gibt es neben UML und Petri-Netzen noch zahlreicheandere Modellierungsmethoden!

Documents

Vorlesung“Modellierung” Wintersemester2013/14 ... · Modellierung Vorlesung“Modellierung” Wintersemester2013/14 (FolienvonProf.B.König) Prof.NorbertFuhr Übungsleitung:ThomasBeckers