Mod-5.17 5.4 Modellierung mit Bäumen In einem ungerichteten Baum gibt es a c zwischen zwei beliebigen Knoten genau einen Weg. Ein gerichteter, azyklischer Graph G ist ein gerichteter Baum, b wenn alle Knoten einen Eingangsgrad lessequal 1 haben und es e genau einen Knoten mit Eingangsgrad 0 gibt, d f er ist die Wurzel von G. G ist ein gewurzelter Baum. c Wurzel Man kann aus einem ungerichteten Baum in b eindeutiger Weise einen gerichteten machen, e indem man einen Knoten zur Wurzel bestimmt. a d f Deshalb wird in gewurzelten Bäumen häufig die Kantenrichtung nicht angegeben. c In einem gewurzelten Baum ist die Höhe eines Knotens v b die größte Länge eines Weges von v zu einem Blatt. e Die Höhe der Wurzel heißt Höhe des Baumes. a d f Knoten, die weder Wurzel noch Blatt sind heißen innere Knoten. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 517 Ziele: Zusammenhang: ungerichtet, gerichtet, gewurzelt in der Vorlesung: * Erläuterung der Begriffe an dem Beispiel. * Andere Wurzeln zum selben ungerichteten Graphen * Höhen bestimmen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.18 Binärbäume Ein gewurzelter Baum heißt Binärbaum, wenn seine Knoten einen Ausgangsgrad von höchstens 2 haben. Ein Binärbaum heißt vollständig, wenn jeder Knoten außer den Blättern den Ausgangsgrad 2 hat und die Wege zu allen Blättern gleich lang sind. Höhe 2 Knoten: 7 Blätter: 4 Ein vollständiger Binärbaum der Höhe h hat 2h Blätter und 2h+1-1 Knoten (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 518 Ziele: Knotenzahlen in Binärbäumen verstehen in der Vorlesung: * Rekursive Struktur zeigen. * Rekursive Berechnung der Knotenzahlen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.19 Modellierung von Entscheidungsbäumen Knoten modelliert Zwischenstand einer mehrstufigen Entscheidungsfolge 1/3 1/3 Kante modelliert eine der wählbaren Alternativen 1/3 1 1. Wahrscheinlichkeiten, 1/3 2/3 1/4 3/4 z. B. erst Schachtel, dann Kugel ziehen: 2. Codierungen, E T Z. B. Morse-Code I A S U . . . H V F Ü a 3. Lösungsbaum für kombinatorische Probleme, z. B. Traveling Salesmanquotesingle s Problem (Mod-5.13) b c d Blätter repräsentieren einen Rundwege von a aus, c d b d b c Kanten sind mit Entscheidungen markiert d c d b c b 4. Spielzüge, z. B. Schach (ohne Bild) a a a a a a Wird derselbe Zwischenstand durch verschiedene Entscheidungsfolgen erreicht, 158 157 205 157 205 158 kann man Knoten identifizieren. Es entsteht ein azyklischer oder zyklischer Graph. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 519 Ziele: Verschiedene Einsatzgebiete von Entscheidungsbäumen kennenlernen in der Vorlesung: Erläuterungen zu den Beispielen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.20 Modellierung von Strukturen durch Bäume Knoten modelliert ein Objekt. Kante modelliert Beziehung "besteht aus", "enthält", "spezialisiert zu", ... Beispiele: * Typhierarchie: Typ - Untertypen * Klassenhierarchie: Oberklasse als Abstraktion ihrer Unterklassen (Mod-5.21) Vererbungshierarchie: Unterklassen erben von ihrer Oberklasse * Objektbaum: Objekt enthält (Referenzen auf) Teilobjekte * Kantorowitsch-Baum: Operator mit seinen Operanden (Mod-5.22) * Strukturbaum: (Programm-)Struktur definiert durch eine kontextfreie Grammatik (Mod-5.23) Identifikation gleicher Teilbäume führt zu azyklischen Graphen (DAGs). Vorsicht: Identifikation muss mit der Bedeutung der Kanten verträglich sein; z. B. Ein Gegenstand kann nicht dasselbe Objekt mehrfach als Teil enthalten, wohl aber mehrere Objekte derselben Art. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 520 Ziele: Varianten von Baumstrukturen in der Vorlesung: * Prinzip der Modellierung von Baumstrukturen * Varianten auf den folgenden 3 Folien nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 Verständnisfragen: Kennen Sie weitere Varianten von Baumstrukturen? -------------------------------------------------------------------------------- Mod-5.21 Klassen- und Objekthierarchien Kompositionsbeziehung im Klassendiagramm (UML, Folie 6.19ff): PC Knoten: Klassen Kanten: definieren, aus welcher Art von Objekten ein Objekt besteht Rechner z. B. ein Objekt der Klasse PC besteht aus Tastatur einem Rechner-Objekt, einem Tastatur-Objekt, ... Monitor Diese Beziehung zwischen den Klassen könnte Maus auch ein allgemeiner Graph sein Objektbaum im Objektdiagramm (fast UML): derPC Knoten: Objekte derRechner Kanten: definieren, aus welchen Objekten ein Objekt besteht dieTastatur z. B. dieser PC besteht aus, diesem Rechner, ... derMonitor Diese Beziehung muss konzeptionell ein Baum sein. dieMaus Vererbungsbeziehung im Klassendiagramm (UML Notation): Knoten: Klassen Figur Kanten: Unterklasse erbt von -> Oberklasse Oberklasse ist Abstraktion <- ihrer Unterklassen Kreis Kanten sind zur Wurzel hin gerichtet Rechteck Baum bei Einfachvererbung (Java) Linie azyklischer Graph bei Mehrfachvererbung (C++) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 521 Ziele: UML Klassendiagramme, Vorgriff auf Abschnitt 6.4 in der Vorlesung: Erläuterungen dazu: * UML Klassendiagramme: Wichtiges Beschreibungsmittel in der Software-Technik. * Klassendiagramme sind aus ER-Modell abgeleitet (siehe Kapitel 5) * Klassendiagramme: nicht nur Bäume * Unterscheidung von Objektiagrammen und Klassendiagrammen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.22 Kantorowitsch-Bäume Darstellung der Struktur von Termen, Formeln, Ausdrücken (a + b) * c (siehe Mod-3.6) * Knoten: Operator, Blattoperand Kanten: Verbindung zu den Operanden eines Operators + c Die Kanten sind geordnet (Kantenmarkierung): erster, zweiter, ... Operand a b Identifikation gleicher Teilbäume führt zu azyklischen Graphen (DAGs): Z. B. identifizieren Übersetzer gleiche Teilbäume, um Code zu erzeugen, der sie nur einmal auswertet: c * (a + b) - (a + b) - - * + * c + c + a b a b a b (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 522 Ziele: Erinnerung an Kantorowitsch-Bäume in der Vorlesung: Erläuterungen zu * Ordnung der Kanten * Identifikation von Teilbäumen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.23 Strukturbäume zu kontextfreien Grammatiken Kontextfreie Grammatiken definieren die Struktur von Programmen, Texten oder Daten. Ein Programm, Text oder strukturierte Daten werden als Strukturbaum dargestellt. Knoten:Programmkonstrukt (Nichtterminal der Grammatik) Kante: Bezug zu Bestandteilen des Programmkonstruktes (Produktion der Grammatik) Für die Repräsentation von Texten sind die Kanten geordnet (Kantenmarkierung) Strukturbaum: Produktionen aus der kontextfreien Grammatik: WhileStatement Statement ::= Assigment Statement ::= WhileStatement Expression Statement ... ... WhileStatement ::= Expression Statement Assignment Assignment ::= Variable Expression Variable Expression ... ... while(i<10) a[i] = 2*i ; (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 523 Ziele: Strukturbaum am Beispiel kennenlernen in der Vorlesung: Erläuterungen dazu: * Kontextfreie Grammatiken werden in Kapitel 6 eingeführt * Bedeutung von Produktionen informell: "WhileStatement besteht aus Expression und Statement". * Bezug zum Strukturbaum. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.4 -------------------------------------------------------------------------------- Mod-5.24 5.5 Zuordnungsprobleme Aufgabenklasse paarweise Zuordnung (Matching): Im ungerichteten Graphen G = (V, E) modelliert eine Kante {a, b} "a passt zu b", ggf. mit einer Kantenmarkierung als Abstufung Gesucht ist eine maximale Menge unabhängiger Kanten, das ist einTeilgraph M mit allen Knoten aus V und möglichst vielen Kanten aus E, so dass der Grad der Knoten höchstens 1 ist. M heißt ein Matching der Knoten von G. 6 7 1 3 7 5 1 2 Matching 4 3 2 4 6 9 8 5 9 8 bipartiter Graph Graph G heißt bipartit, wenn V in 2 disjunkte Teilmengen V = V1 union V2 zerlegt werden kann, so dass jede Kante zwei Knoten aus verschiedenen Teilmengen verbindet. Häufig liefert die Aufgabenstellung schon bipartite Graphen, sogenannte Heiratsprobleme: Mann - Frau Aufgabe - Bearbeiter Verbraucher - Produkte (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 524 Ziele: Paarweise Zuordnung verstehen in der Vorlesung: * Matching-Begriff erläutern, * bipartit erläutern, * Beispiele angeben nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.5 -------------------------------------------------------------------------------- Mod-5.25 Konfliktfreie Knotenmarkierung (Färbung) Aufgabenklasse konfliktfreie Knotenmarkierung (Färbung): Im ungerichteten Graphen G = (V, E) modelliert eine Kante {a, b} "a ist unverträglich mit b", Gesucht ist eine Knotenmarkierung Färbung: V -> Iota N ("Farben"), so dass durch eine Kante verbundene Knoten verschiedene Marken haben Die chromatische Zahl eines Graphen G ist die a b c minimale Zahl verschiedener "Farben", die nötig ist, 1 3 um G konfliktfrei zu markieren. 2 Es gilt: chromatische Zahl lessequal 1 + maximaler Knotengrad 3 2 3 f e d Anwendungen: Knoten: Kante: Farbe / Marke: Staat auf Landkarte gemeinsame Grenze Farbe Partygast unverträglich Tisch Kurs haben gemeinsame Teilnehmer Termin Prozess benötigen gleiche Ressource Ausführungszeitpunkt Variable im Programm gleichzeitig lebendig Registerspeicher (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 525 Ziele: Konzept der Färbung verstehen in der Vorlesung: * Erläuterung der Unverträglichkeitsrelation. * Chromatische Zahlen einer Graphen. * Erläuterung der Anwendungen. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.5 -------------------------------------------------------------------------------- Mod-5.26 5.6 Abhängigkeitsprobleme Graphen modellieren Abhängigkeiten zwischen Operationen und Ausführungsreihenfolgen von Operationen. Abhängigkeitsgraph: gerichtet, azyklisch, voneinander abhängige Operationen. Aufgaben dazu: sequentielle oder parallele Anordnungen finden (engl. scheduling). Knoten: Operation, Ereignis; ggf. mit Dauer markiert Kante: a -> b a ist Vorbedingung für b oder b d b benutzt Ergebnis von a oder a c e a liest oder schreibt Ressource bevor b sie überschreibt Anwendungen: * Projektplanung mit abhängigen Teilaufgaben (PERT, CPM) * abhängige Transaktionen mit einer Datenbank * Anordnung von Code für die parallele Auswertung von Ausdrücken (Übersetzer) Kritischer Pfad: längster Weg von einem Anfangsknoten zu einem Endknoten Duale Modellierung: d Knoten: Ereignis, Anfang und Ende einer Operation a b c Kante: Operation, ggf. mit Dauer markiert e (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 526 Ziele: Prinzip der Abhängigkeitsgraphen verstehen in der Vorlesung: Erläuterungen zu * Bedeutung von Knoten und Kanten * Markierungen * kritischem Pfad * dualer Modellierung nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.27 Anordnung von Abhängigkeitsgraphen Anordnungsaufgaben: a gegebener Abhängigkeitsgraph e b g h kritischer Pfad c f i d sequentielle Anordnung der Knoten, so dass alle Kanten vorwärts zeigen. a b c d e f g h i Meist sollen Randbedingungen erfüllt werden, 4 z. B. geringste Anzahl gleichzeitig benötigter Zwischenergebnisse im Speicher a b e g c d f h i 3 parallele Anordnung mit beschränkter Parallelität 3 a e g h Länge: 4 Schritte (Operationen) b c f i d (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 527 Ziele: Anordnungsaufgaben verstehen in der Vorlesung: Erläuterungen zu * Kanten nur vorwärts * sequentielle Anordnung: Anzahl der Operationen bestimmt die Länge * Anzahl der Zwischenergebnisse * parallele Anordnung: kritischer Pfad bestimmt die Länge nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.28 Operationen unterschiedlicher Dauer Zwei Knotenmarkierungen: Knoten Abschluss a Dauer der Operation und 2 Dauer 2 e frühester Abschlusstermin 5 b 3 2 = max. Abschluss der Vorgänger 3 g 6 + Dauer des Knotens 1 c 4 h Kritischer Pfad gemäß maximaler 9 4 2 Summe der Dauer der Operationen f 7 d 3 i 2 10 2 3 Duale Modellierung: Kante: Operation a 3 e mit Dauer als Marke 2 g 2 5 Mehrfachkanten, Multigraph b 3 1 7 h 0 2 Knoten: Ereignis c 0 10 "vorangehende Operationen d 4 4 f i sind abgeschlossen" 2 7 3 3 mit frühestem Abschlusstermin als Marke (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 528 Ziele: Ausführungsdauer modellieren in der Vorlesung: Erläuterungen zu * den Knotenmarkierungen, * der Berechnung des Abschlusstermins, * dem Kritischen Pfad, * der dualen Modellierung, * der Notwendigkeit der zusätzlichen (gestrichelten) Kante nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.29 Ablaufgraphen Gerichteter Graph (auch zyklisch) modelliert Abläufe. Knoten: Verzweigungsstelle, Zustand Kanten: Fortsetzungsmöglichkeit Jeder Weg durch den Graphen beschreibt einen potenziellen Ablauf Die Folge der Markierungen eines Weges kann einen Satz einer Sprache modellieren. Anwendungen: Buchstabe * Endlicher Automat (siehe Kapitel 6) modelliert Folgen von Zeichen, Symbolen, ... Knoten:Zustand Buchstabe Kante: Übergang markiert mit Zeichen * Syntaxdiagramm Ziffer modelliert Folgen von Zeichen, Symbolen, ... Knoten: markiert mit Zeichen Kante a->b:"auf a kann b folgen" Buchstabe dual zum endlichen Automaten Buchstabe * Aufrufgraphen (siehe Mod-5.30) Ziffer * Ablaufgraphen (siehe Mod-5.31) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 529 Ziele: Prinzip der Ablaufgraphen verstehen in der Vorlesung: * Erläuterungen am Beispiel des endlichen Automaten. * Die Zeichnung hat keine Knotennamen, nur eine Kantenmarkierung. * Syntaxdiagramme als dualen Beschreibung zum endlichen Automaten erklären, * Die Zeichnung hat keine Knotennamen, nur eine Knotenmarkierung. * Viele einzelne Kanten sind in der Zeichnung zu einem "Gleissystem" zusammengefasst. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.30 Aufrufgraphen Gerichteter Aufrufgraph: Aufrufbeziehung zwischen Funktionen in einem Programm; wird benutzt in Übersetzern und in Analysewerkzeugen zur Software-Entwicklung. Knoten: Funktion im Programm Kante a -> b: Rumpf der Funktion a enthält einen Aufruf der Funktion b; a könnte b aufrufen Zyklus im Aufrufgraph: Funktionen, die sich wechselweise rekursiv a aufrufen, z. B. (c, e, c) Fragestellungen z. B. * Welche Funktionen sind nicht rekursiv? b c * Welche Funktionen sind nicht (mehr) erreichbar? * Indirekte Wirkung von Aufrufen, d e z. B. nur e verändere eine globale Variable x; welche Aufrufe lassen x garantiert unverändert? b, d (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 530 Ziele: Prinzip des Aufrufgraphen verstehen in der Vorlesung: * Erläuterungen dazu * Weitere Eigenschaften und Anwendungen in der Vorlesung Übersetzer. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.31 Programmablaufgraphen Gerichteter Graph, modelliert Abläufe durch ein verzweigtes Programm (bzw. Funktion); wird benutzt in Übersetzern und in Analysewerkzeugen zur Software-Entwicklung. Knoten: unverzweigte Anweisungsfolge (Grundblock), mit Verzweigung (Sprung) am Ende Kante: potenzieller Nachfolger im Ablauf A ug = 0; A og = obereGrenze; while (ug <= og) B B { mitte = (ug + og) / 2; C if (a[mitte] == x) return mitte; H else if (a[mitte] < x) D C H ug = mitte + 1; E else og = mitte - 1; F } D return nichtGefunden; G E F Fragestellungen, z. B. * Menge von Wegen, die den Graph überdecken, Software-Testen G * Wege mit bestimmten Eigenschaften, Exit Datenflussanalyse (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 531 Ziele: Prinzip des Programmablaufgraphen verstehen in der Vorlesung: * Erläuterungen zum Prinzip, * Auch andere Abläufe als Programme können so modelliert werden. * Weitere Eigenschaften und Anwendungen in der Vorlesung Übersetzer. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 -------------------------------------------------------------------------------- Mod-5.32 Zusammenfassung zu Graphen Problemklassen: Kanten- und Knotenbedeutung: * Wegeprobleme * verbunden, benachbart, ... * Verbindungsprobleme * Entscheidung, Alternative, * Entscheidungsbäume Verzweigung * hierarchische Strukturen * Vorbedingung, Abhängigkeit * Zuordnungsprobleme * (Un-)Verträglichkeit * Abhängigkeitsprobleme * allgem. symmetrische Relation * Anordnungen in Folgen * besteht aus, enthält, ist-ein * verzweigte Abläufe * (Halb-)Ordnungsrelation Kanten-, Knotenmarkierungen: * Entfernung, Kosten, Gewinn, ... bei Optimierungsproblemen * "Färbung", disjunkte Knotenmengen bei Zuordnungsproblemen * Symbole einer Sprache (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 532 Ziele: Übersicht zu Modellierungsaspekten in der Vorlesung: * Stichworte zum Einordnen von Modellierungsaufgaben, * Hilfe zur Wahl einer passenden Variante von Graphen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 5.6 --------------------------------------------------------------------------------