Reguläre Sprachen, Automatentheorie

Übungsblatt 1 & 2 WS 2006
JFlap - Editor für endliche Automaten
Konstruktion eines NEA
Exorciser
- Erstellung von Automaten, die bestimmte Sprachen erkennen
- Ableitung von Worten aus gegebenen Grammatiken
- Teilmengenkonstruktion NEAs->DEAs
- reguläre Ausdrucke in Automaten überführen und umgekehrt
- weitere Aufgaben im Zusammenhang mit NEAs/DEAs/Sprachen/regulären Ausdrücken und Grammatiken.

Tutorial
- Definition von endlichen Automaten
- Teilmengenkonstruktion
- Erzeugung regulärer Ausdrücke
- Erzeugung regulärer Grammatiken

RegEx
- Testtool für reguläre Ausdrücke

Logik

Bäume und Netzwerke

The Figaro

The "Framework for Implicit Graph Algorithms and Representations by OBDDs" (Figaro) automatically manages experiments with input generator and algorithm plugins. It already contains some generators and algorithms for graph and scheduling problems. Infos zur korrespondierenden Diplomarbeit

Dijstra Algorithmus on youtube

Graphenspiele
- Problem des fahrenden Handlungsreisenden
- Steinerbaum-Problem
- Finden von minimal spannenden Bäumen
- Färben von Graphen
- lange Kreise finden

Preface Contents Chapter 1: Graphs and Subgraphs Chapter 2: Trees Chapter 3: Connectivity Chapter 4: Euler Tours and Hamilton Cycles Chapter 5: Matchings Chapter 6: Edge Colourings Chapter 7: Independent Sets and Cliques Chapter 8: Vertex Colourings Chapter 9: Planar Graphs Chapter 10: Directed Graphs Chapter 11: Networks Chapter 12: The Cycle Space and Bond Space Appendix 1: Hints to Starred Exercises Appendix II: Four Graphs and a Table of their Properties Appendix III: Some Interesting Graphs Appendix IV: Unsolved Problems Appendix V: Suggestions for Further Reading Glossary of Symbols Index

Fundamente der Graphentheorie von L. Volkman

Graph Theory Resources von D.P. Sanders erstellte Seiten zur Graphentheorie, hier findet man zahlreiche Graphentheoretiker (White Pages), Infos zu Konferenzen, Journalen, Forschung,... Solving Traveling Salesman Problems Die Traveling-Salesman-Problem Homepage Mathematik für die Müllabfuhr: das chinesische Postbotenproblem Einführung des Chinese Postman-Problem (Pdf-File, daß Folien zu einem Vortrag über das Thema enthält), leicht verständlich Die optimierte Odyssee Odysseus hätte es wohl leichter haben können, hätte er die Graphentheorie gekannt The Hamiltonian Page Liste von Artikeln, Preprints, usw. über Hamiltonkreise und Hamiltonwege TSPBIB Home Page Liste von Artikeln, Preprints, usw. über das Travelling Salesman Problem Bücher Graph Theory with Applications Die elektronische Ausgabe des Buches "Graph Theory with Applications" von J.A. Bondy und U.S.R. Murty Vorlesungen zur Graphentheorie Die elektronische Ausgabe des Buches "Fundamente der Graphentheorie" von L. Volkmann --> Graphentheorie Die elektronische Ausgabe des Buches "Graphentheorie" von R. Diestel "Farbige Graphentheorie" The Four Color Theorem Zur Geschichte des 4-Farben Problems und zum neuesten Beweis Graph Colorings with Local Constraints A Survey Kurzer Überblick über Varianten der Knotenfärbung, z.B. Listenfärbungen oder vorgefärbte Graphen Graphentheorie (mit dem Computer) Graph Theory Tutorials Hier findet man kleine Online-Kurse, die die Grundideen der Graphentheorie vermitteln. Enthält z.B. die Grundbegriffe, Eulerkreise - und Wege und Färbungen

Graphentheorie von R.Diestel

Petri-Netze

The following interactive tutorials introduce Petri nets, state spaces, and place/transition invariants. The tutorials are created by Wil van der Aalst, Vincent Almering, and Hermen Wijbenga from TU Eindhoven, the Netherlands. The tutorials originate from A Course On Workshop Management (see interactive examples).

Note that you need a Flash player in order to view the interactive tutorials.

Petri Nets Models

- Elevator (1)
- Elevator (2)
- Elevator (3)
- One Traffic Light
- Two Traffic Lights
- One Philosopher
- Four Philosophers
- Four Philosophers
- Assembly

Reachability Graphs / State Spaces

- Two Traffic Lights
- Four Philosophers
- Place Invariants
- Two Traffic Lights
- Four Philosophers
- Transition Invariants
- Two Traffic Lights
- Four Philosophers

Petri Net Tutorial with solutions
- Petri nets can be used for modelling, analysing and verifying reactive and distributed systems. Their strength are their simple but precise semantics, their clear garphical notation, and many methods and algorithms for analysis and verification.

The course introduces Petri nets and their theory by the help of examples from different application domains. The focus, however, will be on traditional Petri net theory, in particular on Place/Transition-Systems and on concepts such as place and transition invariants, deadlocks and traps, and the coverability tree. The course also covers different versions and variants of Petri nets as well as different modelling and analyisis techniques for particular application areas.

Material The material covering this course in particular the assigmnents and solutions will be available at http://www.upb.de/cs/kindler/Lehre/SS06/PN/material.html.

Moreover, there is a German manuscript covering the complete material of this course: Manuscript "Petrinetze" (in German).

PetriEdiSim

Dieses Tutorial zum Thema Petri-Netze basiert auf dem Skript von Prof. Dr. E.-R. Olderog zu der Stammvorlesung "Netze und Prozeße". Es enthält die wichtigsten Definitionen, Erläuterungen sowie eine große Anzahl an Beispielen. Auf die Beweise wurde in diesem Tutorial verzichtet. Weiterführende Informationen können direkt dem Skript der Vorlesung entnommen werden. Die einzelnen hier enthaltenen Themen sind in der folgenden Übersicht aufgelistet und können direkt angeklickt werden. Zusätzlich existiert noch ein Index, in dem nach speziellen Begriffen gesucht werden kann (Icon oben rechts).

Petrinetze

Das Petri-Netz ist ein Modell zur Beschreibung und Analyse von Abläufen mit nebenläufigen Prozessen und nichtdeterministischen Vorgängen. Im Jahre 1962 legte Carl Adam Petri mit seiner Dissertation den Grundstein zur Netztheorie. Mittlerweile hat sich das Petri-Netz in seinen unterschiedlichen Varianten als wichtiges Entwurfs- und Darstellungsinstrument in den verschiedensten Bereichen etabliert. Sie eignen sich für die Beschreibung dynamischer Systeme, die eine feste Grundstruktur besitzen wie beispielsweise Rechenanlagen, Betriebssysteme, Organisationsabläufe (in Büros oder bei Herstellungsverfahren). Sie sind somit für viele unterschiedliche Fragestellungen einzusetzen.

Der Schwerpunkt dieser Arbeit liegt bei den Bedingungs-/Ereignis-Netzen (B-/E-Netze). Neben den Besonderheiten und Regeln dieses Netztyps, können Sie in den Kapiteln Beispiele und Konventionen Netzabläufe simulieren und Ihr Wissen über die Funktionsweise testen.

Um einen Überblick über die weiteren Möglichkeiten der Netztheorie zu geben, werden unter dem Punkt Netzvarianten die restlichen 3 Netztypen vorgestellt.

Petri Net Simulator

1. Fork/Join Petri Net. This Petri net demonstrates how concepts like concurrency and synchronisation can be modelled easily. 2. Dining Philosophers Petri Net. This Petri net correctly models the classic dining philosophers problem. 3. Mutual Exclusion Petri Net. This Petri net shows how mutual exclusion (where two processes can not be in the same state) is modelled. 4. Empty Browser. Create and simulate your own Petri net.

SimPRES

PRES+ stands for Petri net Representation for Embedded Systems. It is a model intended to represent embedded systems, which extends Petri nets adding data and real-time information to tokens, and associating functions and delays to transitions. Delays may be expressed as lower and upper limits.

SimPRES is a simulator for a subset of this particular computational model. The class of systems that may be validated using SimPRES corresponds to time Petri nets.

TimeNet - Werkzeug für Stochastische Petri-Netze