Matthias Spohrer · TU München
Modul „Ablaufmodellierung“
5. Präsenzveranstaltung – 13.02.2003 – TU Stammgelände Innenstadt
Nachqualifizierungskurs für Informatiklehrkräfte
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 2
Inhaltsübersicht
Infos und Neuigkeiten
• Übungsbetrieb
• Klausur Wiederholung:
• Aktionsstruktur
• Zustandsmodelle
• Algorithmen Kleine Einführung in Java
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 3
Übungsbetrieb
Ablauf (momentaner Stand ;-)
Donnerstag oder Freitag: neues Material (Skript Prof. Hubwieser sowie mathematische Grundlagen dazu von Margret Bauer) und neues Übungsblatt (wie bisher im Kursbrief integriert)
Dienstag eine Woche später Abgabetermin Bitte um Nachsicht bei Fehlern – dieser Kurs ist der „Testlauf“...
Anmerkungen, Wünsche, Fehler etc. bitte per E-Mail an mich – ich leite alles weiter
Umfrage am Ende des Kurses (auch DB-Umfrage folgt noch!) Am Ende des 2. Moduls wird es evtl. eine verbesserte Version 1.x des
Gesamtmaterials geben, für Interessierte kein neues Blatt in den Winterferien (Pause!)
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 4
Übungsbetriebauf den Übungsblättern wird es ab Kapitel 5 auch Programmieraufgaben (P)
geben.Die Lerninhalte zur Einführung in Java befinden sich auf der ausgeteilten CD
Onlinekurs: „Objektorientierte Modellierung und Programmierung“Im Rahmen dieser Einführung
-erhalten Sie im Kursbrief ggf. auch kurze Informationen, welche Teilkapitel „der CD“ zu lesen sind, ggf. bekommen sie auch Codefragmente Irgendwas.java mitgeliefert, die die Schreibarbeit bei den (P)-Übungsaufgaben erleichtern.-wird für manche Kapitel x auf dem BSCW ein Ordner Tippsx bereitgestellt, der mehrere Dateien mit immer detaillierteren Hinweisen zu den Programmieraufgaben enthält. Diese Dateien bitte erst nach hinreichendem eigenen Knobeln anschauen!
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 5
Klausur
Sorry, sie war zu lang, den Fehler werden wir (hoffentlich) nicht noch einmal machen…
Trotzdem war eine Angleichung des Notenschlüssels (80 Punkte sind 100%) wohl gar nicht notwendig
Das Ergebnis hat mich sehr gefreut: (wir haben sogar den besten Schnitt – ich will das auch so im Staatsexamen haben ;-)
Die Zuordnung Einzelnoten – Kursteilnehmer wird von mir nicht an Dritte (außer an Prof. Hubwieser) weitergegeben.
Im ersten Studienjahr wird es nur noch eine weitere Klausur geben!
Thema: Ablaufmodellierung und OOM
Klausurtermin: Donnerstag 26.Juni
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 6
Weitere Infos
Arbeitsbelastung?
Fehlende Unterstützung durch Schulleitung?
Fragen, Probleme, Wünsche?
Literatur:• Steger, Angelika: Diskrete Strukturen• Schöning, Uwe: Theoretische Informatik kurzgefasst• Kröger, Fred: Einführung in die Informatik (Algorithmik?)• Java-Literatur
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 7
Modellierung von Abläufen
Möglichkeiten, Abläufe zu beschreiben
Aktionsstrukturen
Zustandsmodell
Algorithmische Modelle
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 8
Aktionsstruktur
Beschreibung von kausaler Abhängigkeit von Ereignissen,Nebenläufigkeit Betriebssysteme
Was muss alles passiert sein?Was kann noch passiert sein?
GleisanlageZwei Züge fahren im Uhrzeigersinn
Zug 1 will Punkt C passieren.
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 9
Aktionsstruktur
Die Kausalitätsrelation einer Aktionsstruktur ist definiert als partielle Ordnung über der Ereignismenge.
Eine partielle Ordnung ist transitiv. Diese Eigenschaft haben wir verwendet, als wir in vorherigem Beispiel alle Ereignisse ermittelt haben die vor „transC“ stattfinden müssen.
Eine partielle Ordnung ist antisymmetrisch. D. h. e1 e2 und e2 e1 ist nur genau dann möglich, wenn die beiden Ereignisse identisch sind. Wenn man Kausalität ausdrücken möchte ist dies eine sehr sinnvolle Bedingung.
Eine partielle Ordnung ist reflexiv. Eine partielle Ordnung kann total (=linear) sein.
reflexiv irreflexiv Symmetr. antisymm transitiv linear
Partielle Ordnung
Totale Ordnung Strenge
Ordnung
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 10
Aktionsstruktur
Ist die Kausalitätsrelation der Aktionsstruktur aus der Fahrstuhlaufgabe (Übung Aufg. 3) bzw. von eben gesehenem Beispiel (Gleisanlage) eine totale Ordnung?
Nein, 1 und 3 stehen nicht in Relation zueinander. (Es ist vollkommen egal, in welcher Reihenfolge die beiden Ereignisse stattfinden.)
Nein, auch beim Gleisverkehr gibt es Ereignisse, die nicht in Relation zueinander stehen.
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 11
Aktionsstruktur
Angenommen, eine Kausalitätsrelation einer Aktionsstruktur ist total. Was sagt das über die Aktionsstruktur aus?
Man sagt, eine solche Aktionsstruktur ist sequentiell.
e4e3e2e1e8e7e6e5
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 12
Erweitertes ZustandsmodellAktionsstrukturen können Verhalten / Interaktion verschiedener Objekte beschreiben(vgl. zwei Personen fahren Lift)
Zustandsmodelle (= Automaten) beschreiben i. a. das Verhalten eines einzelnen Objekts(Lift hält /fährt /defekt …)
Erweitertes Zustandsmodell ( Softwareentwicklung): ZM = (Z,E,A,B,δ,z0,F)7-Tupel: Zustände, Ereignisse, Aktionen, Bedingungen, Übergangsfunktion (Transition) δ : (Z×E×B)(A×Z), ein Startzustand, Endzustände
Bsp. aus Blatt 2 Bankautomat (ein Übergang aus dem Zustandsdiagramm):P3: Automat erwartet 3. Eingabe der Pin KE: (neue) Karte wird erwartet
P3 KEPin [not(korrekt(Pin))] / zieheKarteEin
Kein B, kein A (5-Tupel) endlicher Automat
UML – Notation(Unified Modeling Language)
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 13
Endlicher Automat
• Ein abstraktes Rechnermodell ( theoretische Informatik) weist auf endlich viele Zustände, „endliche Gedächtnisleistung“ hin
• Ein endlicher Automat „kann“ genauso viel wie jeder Computer!• Erkennungsmechanismus für eine bestimmte Klasse von Sprachen (sog. „reguläre
Sprachen“)
Anwendung endlicher Automaten?z.B.• Syntaxprüfung mit endlichen Automaten (Kapitel 4 dieses Moduls),• Teilworterkennung -> Suchen, Suchmaschinen (vgl. auch Aufgabe 7 Molekülanalyse
des 2. Übungsblatts)
Die Zuweisung (von Werten an Variablen) im imperativen Programmierstil kann als Zustandsübergang aufgefasst/modelliert werden.
x=5x := x+1
x=6
Zustand Zustand
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 14
Motivation:Motivation:
Worterkennung /
Mustererkennung(Pattern matching)
Bsp.: Suchfunktion in MS Windows
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 15
Suchfunktion in MS Word
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 16
Endlicher Automat
Ein (deterministischer) endlicher Automat M (kurz DFA) ist gegeben durch ein 5-Tupel , wobei
Z := endliche Menge der Zustände, := Eingabealphabet (endlich!), es gilt Z : Z Z heißt Überführungsfunktion,z0 := Startzustand (z0Z),
E := Menge der Endzustände (E Z).
EzZM ,,,, 0
Bsp.: Gesucht wird ein Automat, der erkennt, ob eine (als Binärzahl) eingegebene Zahl durch 4 teilbar ist.
Z:={Z0; Z1; Z2}
:={0; 1}
z0:=Z0
E:={Z2}
: (Z0,0)Z1 (Z0,1)Z0 (Z1,0)Z2 (Z1,1)Z0 (Z2,0)Z2 (Z2,1)Z0
0 1
Z0 Z1 Z0
Z1 Z2 Z0
Z2 Z2 Z0
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 17
Endlicher Automat
Aufgabe 6...
„partieller Automat“
„Minimalautomat“
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 18
Endlicher Automat – Formale Sprachen
Formale Sprache: Jede Teilmenge von AA*, wobei AA ein Alphabet
Beispiel: Sei AA = {A,B,C,...,X,Y,Z,Ä,Ü,Ö,a,b,c,...,x,y,z,ä,ü,ö} =der „deutsche Zeichensatz“
A*A* = die Menge aller Zeichenketten mit Zeichen aus A.A.Dann liegen z.B. die Wörter „jkxoö“, „AKakLL“ und „yes“ in AA*, aber auch die Wörter „Automat“, „Schweinebraten“ und „römisch“.
Eine mögliche Teilmenge von A*A* wäre dann beispielsweise die Menge aller im Duden vorkommenden Wörter. Diese Menge bildet dann eine formale Sprache, die wir wohl als „deutsche Sprache“ oder kurz „Deutsch“ bezeichnen würden.
Um mit solchen Sprachen, die i.a. unendliche Objekte sind, algorithmisch umgehen zu können, benötigen wir jedoch endliche Beschreibungsmöglichkeiten für Sprachen. Dazu dienen sowohl die Grammatiken als auch die Automaten.
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 19
Grammatik
Eine Grammatik ist ein 4-Tupel G = (N,T,P,S) mit:
N:=endliche Menge von Variablen (Nicht-Terminalzeichen)
T:= endliche Menge von Terminalzeichen
P:=endliche Menge der Regeln oder Produktionen
S ist die Startvariable (und muss in N liegen)
Außerdem muss gelten N T
T={a,b}
N={A,B}
P = { A aA, A aB, B bB, B b}
S=A
Es gilt zum Beispiel:A => aA => aaA => aaaB => aaabB => aaabb
( ) { | , 1}m nL G a b m n
Vermutung:Die Sprache L(G) über der Grammatik G lässt sich schreiben als
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 20
BNF
T={a,b}
N={A,B}
P = { A aA, A aB, B bB, B b}
S=A
Es gilt zum Beispiel:A => aA => aaA => aaaB => aaabB => aaabb
( ) { | , 1}m nL G a b m n
Vermutung:Die Sprache L(G) über der Grammatik G lässt sich schreiben als
:: |
:: |
:: { } { }
A aA aB
B bB b
Sprache a a b b
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 21
BNF
T={a,b}
N={A,B}
P = { A aA, A aB, B bB, B b}
S=A
( ) { | , 1}m nL G a b m n
Vermutung:Die Sprache L(G) über der Grammatik G lässt sich schreiben als
In diesem Beispiel handelt es sich um eine sog. reguläre reguläre SpracheSprache. Das sind genau diejenigen Sprachen, dessen Worte von endlichen Automaten erkannt werden können.
Aufgabe: konstruiere einen EA, der genau diese Worte erkennt. Das Eingabealphabet soll {a,b,x} sein, wobei x für jedes beliebige andere Zeichen stehen soll.
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 22
Endlicher Automat
CharonCharon
Simulationsprogramm für endliche Automaten:
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 23
Erweiterung des endlichen Automaten
Mealy-Automat (Mealy-Maschine)„endlicher Automat und zusätzlich Ausgabe A und Ausgabefunktion : (Z×E)A und ohne Endzustände” (6-Tupel)
z1e / a
z2
Moore-Automat (Moore-Maschine)„Mealy-Automat nur : Z A ” (6-Tupel)
z1e
z2
a
Prinzip des ZÜD:
Prinzip des ZÜD:
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 24
Algorithmus
Ein Algorithmus stellt eine bestimmte Lösung für eine Klasse von Aufgaben dar.Für eine Klasse von Aufgaben gibt es meist recht unterschiedliche Algorithmen.
Bsp. aus Kapitel 3 des ModulsKlasse von Aufgaben: SortierenUnterschiedliche Algorithmen: Bubblesort, Quicksort, Sortieren durch Einfügen, …
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 25
Algorithmus „Bubblesort“
Pseudocode des Algorithmus aus dem Material:
Wiederhole (Anzahl der Elemente der Liste -1) malWiederhole für alle Zahlen von der ersten bis zur vorletzen
Falls die betrachtete Zahl größer ist als die folgendeVertausche die beiden Zahlen
Ende FallsEnde Wiederhole
Ende Wiederhole
Äußere WiederholungInnere Wiederholung
5 8 2 7 3 1 9 4 6
Es folgt eine Animation nach Prof. Kemper:
Betrachtete Zahl
(„der unsort. Liste“)
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 26
1. äußere Wiederholung5 8 2 7 3 1 9 4 6
5 2 8 7 3 1 9 4 6
5 2 7 8 3 1 9 4 6
5 2 7 3 8 1 9 4 6
5 2 7 3 1 8 9 4 6
5 2 7 3 1 8 4 9 6
5 2 7 3 1 8 4 6 9
1. und 2. innere Wiederh.:
3. innere Wiederh.:
4. innere Wiederh.:
5. innere Wiederh.:
6. und 7. innere Wiederh.:
8. innere Wiederh.:
9. innere Wiederh.:
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 27
2. äußere Wiederholung
5 2 7 3 1 8 4 6 9
2 5 7 3 1 8 4 6 9
2 5 3 7 1 8 4 6 9
2 5 3 1 7 8 4 6 9
2 5 3 1 7 4 8 6 9
2 5 3 1 7 4 6 8 9
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 28
3. äußere Wiederholung
2 5 3 1 7 4 6 8 9
2 3 5 1 7 4 6 8 9
2 3 1 5 7 4 6 8 9
2 3 1 5 4 7 6 8 9
2 3 1 5 4 6 7 8 9
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 29
4. äußere Wiederholung
2 3 1 5 4 6 7 8 9
2 1 3 5 4 6 7 8 9
2 1 3 4 5 6 7 8 9
2 1 3 4 5 6 7 8 9
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 30
5. äußere Wiederholung
2 1 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 31
Sortieren: Bubblesort
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
6. äußere W.:
7. äußere W.:
8. äußere W:
Ergebnis:
Ergebnis:
Endergebnis:
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 32
Kleiner Ausblick
Fragen: Wie gut ist der Sortier-Algorithmus Bubblesort?Wie könnte er (ein bisschen) verbessert werden?Was heißt „gut“, wovon kann das evt. auch abhängen? Gibt es „bessere“ Sortier-Algorithmen?-> 2. Studienjahr Modul „Algorithmen und Datenstrukturen“
Vergleich der beiden Sortier-Algorithmen Bubblesort und QuicksortQuicksort werden sie in Kapitel 7 dieses Moduls noch kennenlernen
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 33
Einführung in Java
• Programmieren lernt man nur durch Üben!• Besonders am Anfang wird man dabei oft mehr oder weniger einfache Fehler
machen. Die Fehlersuche ist oft sehr nervtötend. Sie können aber davon ausgehen, dass jeder, der mit einer Programmiersprache beginnt, ähnliche Erfahrungen macht bzw. gemacht hat.
• Verzweifelt also nicht in solchen Situationen!!!!!• Oft ist hier die Verbindungsaufnahme (E-Mail, Telefon, ...) mit einer/m
Kurskollegen/in oder mir sehr hilfreich.
Einfuehrung_in_Java.pdf (Autor des Originals: Herr Dreßler aus Würzburg)
Nachqualifizierungskurs für Informatiklehrkräfte© 2003 Matthias Spohrer · TU München
Seite 34
Fragen
?