Institut fuer Technische Informatik und Kommunikationsnetze
Back to TIK Homepage

TIK Lehrveranstaltungen

Diskrete Ereignissysteme

Zielsetzung:

Vermittlung von Modellierungs-, Simulations- und Entwurfsmethoden für verteilte und ereignisdiskrete Systeme. Anwendung auf Beispiele aus Computernetzwerken, automatischen Produktionssystemen, komplexen Softwaresystemen und integrierten Steuerungs-, Kommunikations- und Informationssystemen.

Inhalt:

Die rasante Entwicklung von Rechnertechnologien in den vergangenen Jahrzehnten hatte die Verbreitung neuer dynamischer und komplexer Systeme zu Folge. Wesentliche Charakteristika solcher Systeme sind Verteiltheit, Nebenläufigkeit und das asynchrone Auftreten diskreter Ereignisse. Der Prozess, neue Modelle und Methoden für ereignisgetriebene Systeme zu entwickeln, ist vergleichsweise jung. Der Rechner selbst spielt hierbei eine entscheidende Rolle als Werkzeug für Systementwurf, Analyse und Steuerung.
Im Einzelnen werden behandelt: Eigenschaften komplexer Systeme Überblick über Systeme und Modelle Zeitfreie und zeitbehaftete Modelle Stochastische Modelle Umsetzung in Programmiersprachen Simulation-, Entwurfs- und Testverfahren auf der Basis der vorgestellten Modelle.
In allen Abschnitten sind Beispiele aus unterschiedlichen Anwendungsbereichen eingegliedert.

 

Unterlagen:

Ein begleitendes Skript und ergänzende Artikel werden in der Vorlesung verkauft, die Übungsblätter werden jeweils nach den Vorlesung im Hörsaal ausgelegt. Wer sich nicht sicher ist, ob er über einen kompletten Satz von Unterlagen verfügt, findet hier (während des Semesters) ein nachgeführtes detailliertes Inhaltsverzeichnis. Das Skript ist während des Semesters auch auf der Assistenz während der Öffnungszeiten erhältlich.

Manuskripte

Skript mit Inhaltsverzeichnis, Literaturangaben [pdf]

Ausführliche Einleitung zu Diskreten Ereignissystemen [pdf]

Formal Languages and Automata Theory [pdf]

extern: Henrik Reif Andersen - An Introduction to Binary Decision Diagrams. [html][ps]

 

Folien zur Vorlesung

 

#

Termin

Dozent

Thema 

Kommentare

1

23.10.03

Thiele

·   Einleitung

·   Systeme und Modelle

 keine Übung

2

30.10.03

Thiele

·   Sprachen und Automaten

 

3

6.11.03

Thiele

·   Erweiterte Modelle endlicher Automaten

 

4

13.11.03

Platzner

·   Verifikation endlicher Automaten I

  

5

20.11.03

Thiele

·   Verifikation endlicher Automaten II

 

6+7

27.11.03

Thiele

·   Definition von Petri-Netzen

·   Erweiterung von Petri-Netzen

3h Vorlesung, keine Übung

 

4.12.03

Übung ersetzt die Vorlesung 

8

11.12.03

Thiele

·   Analyse von Petri-Netzen

·   Spezialisierung von Petri-Netzen

 

9

18.12.03

Thiele

·   Zeitbehaftete Petri-Netze und ihre Simulation

·   Analyse zeitbehafteter markierter Graphen

 

10

8.01.04

Erlebach

·   Stochastische diskrete Ereignissysteme (SDES), Teil 1: Markov-Ketten

 

11

15.01.04

Erlebach

·   SDES, Teil 2: Stationäre Analyse

 

12

22.01.04

Erlebach

·   SDES, Teil 3: Gesetz von Little

 

13

29.01.04

Erlebach

·   SDES, Teil 4: Warteschlangen

 

14

5.02.04

Erlebach

·   SDES, Teil 5: Birth and Death-Prozesse

 

 

Demos

Systembetrachtung [pdf]

Statemate [pdf]

Warteschlangen, Markov [pdf]

 

Übungen & Praktika

Übung

Assistent

Ausgabe

Thema 

Besprechung

 Zeit

Raum

1 (U)

JB 

30.10.03

· Systeme und Modelle [pdf]  

30.10.03

15-17h

ETF E1 

2 (U)

JG

30.11.03

·  Sprachen und Automaten [pdf]

6.11.03

15-17h

ETF E1

3 (U)

 JG

6.11.03

·  Formale Verifikation I

13.11.03

15-17h

ETF E1

4 (U)

SK 

13.11.03

·  Formale Verifikation II [pdf]

20.11.03 [pdf]

15-17h

ETF E1 

5+6 (P)

JB, SK, AM

27.11.03

·  MOSES I [pdf]

·  MOSES II [pdf]

·  Tutorial [pdf]

·  Moses [jar]

·  Repository [tar.gz]

4.12.03

13-17h

ETL F11 

7 (U)

SK

27.11.03

·  Petri-Netze [pdf]

11.12.03 [pdf]

15-17h

ETF E1 

8 (U)

JB 

11.12.03

·  Markierte Graphen [pdf]

18.12.03 [pdf]

15-17h

ETF E1 

9 (U)

MM

18.12.03

·  Wahrscheinlichkeitsrechnung [ps] [pdf]

8.01.04
[ps] [pdf]

15-17h

ETF E1 

10 (U)

MM

8.01.04

·  Markov-Ketten, Transientenanalyse [ps] [pdf]

15.01.04
[ps] [pdf]

15-17h

ETF E1 

11 (U)

MM

15.01.04

·  Markov-Ketten, Stationäre Analyse [ps] [pdf]

22.01.04
[ps][pdf]

15-17h

ETF E1 

12 (U)

MM

22.01.04

·  Markov-Ketten, Gesetz von Little [ps] [pdf]

29.01.04
[ps][pdf]

15-17h

ETF E1 

13 (U)

MM

29.01.04

·  Warteschlangen [ps] [pdf]

5.02.04
[ps][pdf]

15-17h

 ETF E1 
 

Termine, Kredite

Vorlesung: Do 13-15h, ETF E1

Übung: Do 15-17h, ETF E1

Die theoretischen Übungen werden in der Vorlesung in der Woche vor dem Übungstermins ausgeteilt. Während des Übungstermins besteht in der ersten Hälfte der Zeit die Möglichkeit, die Übungsaufgaben in Kleingruppen zu lösen. Assistenten stehen dabei für Fragen zur Verfügung. In der zweiten Hälfte des Übungstermins wird die Übung besprochen. Um einen Testatpunkt zu erhalten, muss zu Beginn der zweiten Übungshälfte ein schriftlicher Lösungsversuch vorliegen. Die praktischen Übungen werden ebenfalls in der Vorlesung vor der Übung ausgeteilt, um die eingehende Beschäftigung mit den Übungsbeschreibungen zu ermöglichen.

Kreditbedingung: 10 von 12 Übungen, wovon mindestens 1 praktische Übung, die Vorlesung ergibt 4 Krediteinheiten

Testatvergabe: Who wants a Testat and fulfills the conditions, please stop by MM with your "Testat Punkte" (at G78.2)  

Prüfung: schriftlich, 3h, Termin wird noch bekanntgegeben, bei der schriftlichen Prüfung sind alle Unterlagen zugelassen. Eine Fragestunde wird ca. 2 Wochen vor dem Prüfungstermin stattfinden.

 

Sample exam problems and their solutions are available now for download:

Thema

Problem

Sample Solution
   Sprachen und Automaten

[pdf]

[pdf]
   Systeme und Modelle

[pdf]

[pdf]
   Verifikation

[pdf]

[pdf]
   Petri-Netze

[pdf]

[pdf]
   Petri-Netze

[pdf]

[pdf]
   Stochastische diskrete
   Ereignissysteme

[pdf]

[pdf]
   Stochastische diskrete
   Ereignissysteme

[pdf]

[pdf]

 

 

  Weiterführende Literatur

[Cas93] C.G. Cassandras. Discrete Event Systems: Modelling and Performance Analysis. Aksen Associates Inc. Publishers, Homewood, IL and Boston, MA, 1993. ISBN 0-256-11212-6 Buch in der ETHbib bestellen

Das Buch ist in der Elektrotechnik Bibliothek sowie ider der ETH Bibliothek mehrfach vorhanden.

[Har87] D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, vol. 8, pp 231-274, 1987. Dokument ansehen [pdf]

[Mur89] T. Murata. Petri Nets: Properties, analysis and applications. Proceedings of the IEEE, vol. 77, issue 4, pp 541-580, April 1989. Dokument ansehen [pdf]

[CDQV85] G. Cohen, D. Dubois, J.P. Quadrat, and M. Voit. A linear system theoretic view of discrete-event processes and its use for performance evaluation. IEEE Transactions on Automatic Control, AC-30(3):210 - 220, 1985. Dokument ansehen [pdf]

[LM87] E.A. Lee and D.G. Messerschmitt. Synchronous Data Flow. Proceedings of the IEEE, 75:1235-1245, 1987.

 

In der Vorlesung erwähnte Software Tools

CodeSign
MOSES
StateMate Magnum
UML
Ptolemy
Cadence Signal Processing WorkSystem (SPW)
Synopsys COSSAP
Cadence SMV
Petri-Netz Informationen
Verschiedene Werkzeuge fuer Petri-Netze
Exorciser

Dozenten

Koordination

AM: Alexander Maxiaguine, ETZ G76 +41-1-632 7003 maxiagui@tik.ee.ethz.ch
 
Betreuung
Back to TIK Homepage
  Last updated  December 18, 2003 12:03 PM by maxiagui@tik.ee.ethz.ch