Ereignisdiskrete Systeme, 3rd Edition

Book description

Dieses Lehrbuch gibt eine Einführung in die Beschreibung und Analyse ereignisdiskreter Systeme.

Es zeigt, wie man dynamische Systeme mit wertdiskreten Signalen durch Automaten, Markovketten und Petrinetze darstellen und analysieren kann. Die behandelten Modellformen bilden die Grundlage für vielfältige Beschreibungsmittel, die heute in der Elektronik für die Spezifikation und die Modellierung von Schaltkreisen, in der Automatisierungstechnik für die Analyse diskreter Systeme und den Steuerungsentwurf oder in der Informatik für die Definition von Berechnungsmodellen und die Analyse und Übersetzung von Programmen verwendet werden.

Beispiele aus den genannten sowie weiteren Gebieten zeigen das breite Anwendungsfeld der hier behandelten Modelle und Methoden. Mit der fachübergreifenden Darstellung der Theorie ereignisdiskreter Systeme ist dies – zumindest im deutschsprachigen Bereich – das erste Lehrbuch, das alle grundlegenden Phänomene und eigenschaften der ereignisdiskreten Dynamik unabhängig vom Anwendungsgebiet beschreibt. Es entstand aus einer Lehrveranstaltung des dritten Semesters des Studienganges Elektrotechnik und Informationstechnik der Ruhr-Universität Bochum, die die Studenten vor ihrer Entscheidung für einen Studienschwerpunkt, der entweder stärker auf die Elektronik, die Informationstechnik oder die Informatik ausgerichtet ist, besuchen. Das breite Interessengebiet dieser Hörer schlägt sich in der Breite der Darstellung nieder.

Die dritte Auflage verbessert, ergänzt und erweitert die Darstellung der Methoden, die Beispiele und die Übungsaufgaben sowie die im Anhang angegebenen Lösungen. Außerdem werden die Querbezüge zu den Methoden der kontinuierlichen Systemtheorie vertieft, die den Ingenieuren geläufiger ist als die ereignisdiskrete Betrachtungsweise. Vorkenntnisse zu kontinuierlichen Systemen werden allerdings für das Verständnis nicht vorausgesetzt.

Table of contents

  1. Cover
  2. Title Page
  3. Copyright
  4. Vorwort
  5. Inhaltsverzeichnis
  6. Verzeichnis der Anwendungsbeispiele
  7. Hinweise zum Gebrauch des Buches
  8. 1 Einführung in die Modellierung und Analyse ereignisdiskreter Systeme
    1. 1.1 Ereignisdiskrete Systeme
    2. 1.2 Anwendungsgebiete der Theorie ereignisdiskreter System
      1. 1.2.1 Verarbeitung formaler und natürlicher Sprachen
      2. 1.2.2 Beschreibung eingebetteter Systeme
      3. 1.2.3 Entwurf digitaler Schaltungen und Schaltkreise
      4. 1.2.4 Modellierung und Analyse von Fertigungssystemen
      5. 1.2.5 Automatisierung diskreter Prozesse
      6. 1.2.6 Modellierung und Analyse von Kommunikations- und Rechnernetzen
      7. 1.2.7 Analyse von Wartesystemen
      8. 1.2.8 Zusammenfassung: Charakteristika ereignisdiskreter Systeme
    3. 1.3 Überblick über die Modellformen und Analysemethoden
    4. Literaturhinweise
  9. 2 Diskrete Signale und Systeme
    1. 2.1 Grundbegriffe der Systemtheorie
    2. 2.2 Blockschaltbild
      1. 2.2.1 Elemente des Blockschaltbildes
      2. 2.2.2 Kompositionale Modellbildung
      3. 2.2.3 Hierarchische Modellbildung
    3. 2.3 Diskrete Signale
      1. 2.3.1 Klassifikation von Signalen
      2. 2.3.2 Diskrete Signale und Ereignisse
      3. 2.3.3 Logische und zeitbewertete Werte- und Ereignisfolgen
      4. 2.3.4 Vektorielle Eingangs- und Ausgangssignale
    4. 2.4 Diskrete Systeme
      1. 2.4.1 Grundidee der ereignisdiskreten Modellbildung
      2. 2.4.2 Zustandsraumdarstellung
    5. 2.5 Eigenschaften diskreter Systeme
      1. 2.5.1 Asynchrone und getaktete Arbeitsweise
      2. 2.5.2 Kommunikation und Synchronisation
      3. 2.5.3 Kausalität
      4. 2.5.4 Nichtdeterminismus
      5. 2.5.5 Komplexität
    6. 2.6 Unterschiede und Gemeinsamkeiten diskreter und kontinuierlicher Systeme
      1. Literaturhinweise
  10. 3 Deterministische Automaten
    1. 3.1 Autonome deterministische Automaten
      1. 3.1.1 Definition
      2. 3.1.2 Automatengraph
      3. 3.1.3 Matrixdarstellung
      4. 3.1.4 Verhalten
      5. 3.1.5 Weitere Eigenschaften
      6. 3.1.6 Zustand deterministischer Automaten
    2. 3.2 Σ–Automaten
      1. 3.2.1 Definition
      2. 3.2.2 Verhalten
      3. 3.2.3 Modellierung ereignisdiskreter Systeme durch Σ–Automaten
    3. 3.3 Deterministische Automaten und reguläre Sprachen
      1. 3.3.1 Automaten als Akzeptoren und Sprachgeneratoren
      2. 3.3.2 Formale Sprachen
      3. 3.3.3 Verallgemeinerte Zustandsübergangsfunktion
      4. 3.3.4 Sprache deterministischer Automaten
    4. 3.4 Deterministische E/A-Automaten
      1. 3.4.1 Definition
      2. 3.4.2 Verhalten
      3. 3.4.3 Automatenabbildung
      4. 3.4.4 Mealy-Automat und Moore-Automat
      5. 3.4.5 Echtzeitautomaten
    5. 3.5 Analyse deterministischer Automaten
      1. 3.5.1 Erreichbarkeitsanalyse
      2. 3.5.2 Strukturelle Analyse deterministischer Automaten
      3. 3.5.3 Verifikation
    6. 3.6 Beziehungen zwischen Automaten
      1. 3.6.1 Äquivalenz von Σ–Automaten
      2. 3.6.2 Homomorphie und Isomorphie
      3. 3.6.3 Automaten mit äquivalenten Zuständen
      4. 3.6.4 Minimierung deterministischer Automaten
      5. 3.6.5 Erweiterung der Methoden auf E/A-Automaten
    7. 3.7 Erweiterungen
    8. Literaturhinweise
  11. 4 Nichtdeterministische Automaten
    1. 4.1 Erweiterung deterministischer Automaten zu nichtdeterministischen Automaten
      1. 4.1.1 Zustandsübergangsrelation nichtdeterministischer Automaten
      2. 4.1.2 Verhalten nichtdeterministischer Automaten
    2. 4.2 Nichtdeterministische Automaten und reguläre Sprachen
      1. 4.2.1 Nichtdeterministische Automaten als Akzeptoren
      2. 4.2.2 Nichtdeterministische Automaten mit ε-Übergängen
      3. 4.2.3 Reguläre Sprachen
      4. 4.2.4 Akzeptoren für reguläre Sprachen
      5. 4.2.5 Pumping-Lemma
      6. 4.2.6 Vergleich der Sprachen von deterministischen und nichtdeterministischen Automaten
      7. 4.2.7 Ableitung des regulären Ausdrucks aus dem Automatengraphen
    3. 4.3 Nichtdeterministische E/A-Automaten
    4. 4.4 Analyse nichtdeterministischer Automaten
      1. 4.4.1 Erreichbarkeitsanalyse
      2. 4.4.2 Homomorphie und Isomomorphie nichtdeterministischer Automaten
      3. 4.4.3 Minimierung nichtdeterministischer Automaten
    5. 4.5 Formale Sprachen und Grammatiken
      1. 4.5.1 Zielstellung
      2. 4.5.2 Darstellung regulärer Sprachen durch Typ-3-Grammatiken
      3. 4.5.3 Chomsky-Hierarchie formaler Sprachen
      4. 4.5.4 Kontextfreie Sprachen
      5. 4.5.5 Turingmaschinen
    6. Literaturhinweise
  12. 5 Automatennetze
    1. 5.1 Kompositionale Modellbildung diskreter Systeme
    2. 5.2 Zusammenschaltung von Σ–Automaten
      1. 5.2.1 Modellierungsziel
      2. 5.2.2 Produkt von Automaten
      3. 5.2.3 Parallele Komposition
      4. 5.2.4 Eigenschaften der Kompositionsoperatoren
    3. 5.3 Zusammenschaltung von E/A-Automaten
      1. 5.3.1 Modellierungsziel
      2. 5.3.2 Reihenschaltung
      3. 5.3.3 Rückführautomat
      4. 5.3.4 Allgemeine Automatennetze
      5. 5.3.5 Asynchrone Automatennetze
  13. Literaturhinweise
  14. 6 Petrinetze
    1. 6.1 Autonome Petrinetze
      1. 6.1.1 Grundidee
      2. 6.1.2 Definition
      3. 6.1.3 Verhalten
      4. 6.1.4 Matrixdarstellung
      5. 6.1.5 Modellierung ereignisdiskreter Systeme durch Petrinetze
      6. 6.1.6 Synchronisationsgraphen und Zustandsmaschinen
      7. 6.1.7 Beziehungen zwischen Petrinetzen und Automaten
    2. 6.2 Analyse von Petrinetzen
      1. 6.2.1 Erreichbarkeitsanalyse
      2. 6.2.2 Invarianten
    3. 6.3 Interpretierte Petrinetze
      1. 6.3.1 Sprache von Petrinetzen
      2. 6.3.2 Steuerungstechnisch interpretierte Petrinetze
    4. 6.4 Erweiterungen
      1. 6.4.1 Petrinetze mit Test- und Inhibitorkanten
      2. 6.4.2 Petrinetze mit Stellen- und Kantenbewertungen
      3. 6.4.3 Hierarchische Petrinetze
  15. Literaturhinweise
  16. 7 Markovketten und stochastische Automaten
    1. 7.1 Modellierungsziel
    2. 7.2 Methoden der Wahrscheinlichkeitsrechnung
      1. 7.2.1 Zufallsvariable
      2. 7.2.2 Erwartungswert
      3. 7.2.3 Bedingte Wahrscheinlichkeitsverteilung
      4. 7.2.4 Wahrscheinlichkeitsverteilungen mit mehr als zwei Zufallsgrößen
      5. 7.2.5 Unabhängigkeit von Zufallsgrößen
    3. 7.3 Markovketten
      1. 7.3.1 Nichtdeterministische Automaten mit Wahrscheinlichkeitsbewertung
      2. 7.3.2 Berechnung der Zustandswahrscheinlichkeitsverteilung
      3. 7.3.3 Markoveigenschaft
      4. 7.3.4 Verhalten von Markovketten
      5. 7.3.5 Strukturelle Eigenschaften
      6. 7.3.6 Verweilzeit der Markovkette in einem Zustand
      7. 7.3.7 Stationäre Wahrscheinlichkeitsverteilung
    4. 7.4 Stochastische Automaten
      1. 7.4.1 Definition
      2. 7.4.2 Verhalten
      3. 7.4.3 Stochastischer Operator
      4. 7.4.4 Spezielle stochastische Automaten
      5. 7.4.5 Viterbi-Algorithmus zur Lösung von Detektionsproblemen
    5. Literaturhinweise
  17. 8 Zeitbewertete Petrinetze
    1. 8.1 Ziele der Modellerweiterung
    2. 8.2 Petrinetze mit zeitbewerteten Transitionen
    3. 8.3 Zeitbewertete Synchronisationsgraphen
      1. 8.3.1 Zeitbewertete Synchronsationsgraphen ohne Eingang
      2. 8.3.2 Grundlagen der Max-plus-Algebra
      3. 8.3.3 Darstellung zeitbewerteter Synchronisationsgraphen mit Hilfe der Max-plus-Algebra
      4. 8.3.4 Verhalten zeitbewerteter Synchronisationsgraphen
      5. 8.3.5 Synchronisationsgraphen mit Eingang
      6. 8.3.6 Zusammenfassung
    4. Literaturhinweise
  18. 9 Zeitbewertete Automaten
    1. 9.1 Modellierungsziel
    2. 9.2 Zeitbewertete Automaten mit deterministischen Verweilzeiten
      1. 9.2.1 Autonome zeitbewertete Automaten
      2. 9.2.2 Erweiterung auf Σ–Automaten und E/A-Automaten
      3. 9.2.3 Zeitbewertete Beschreibung paralleler Prozesse
      4. 9.2.4 Ereignisse mit veränderlicher Lebensdauer
    3. 9.3 Zeitbewertete Automaten mit stochastischen Verweilzeiten
      1. 9.3.1 Punktprozesse
      2. 9.3.2 Definition und Verhalten des Poissonprozesses
      3. 9.3.3 Markoveigenschaft des Poissonprozesses
      4. 9.3.4 Punktprozesse mit zustandsabhängigen Übergangsraten
      5. 9.3.5 Punktprozesse mit beliebigen Wahrscheinlichkeitsverteilungen der Verweilzeiten
    4. 9.4 Wartesysteme
      1. 9.4.1 Grundgleichungen
      2. 9.4.2 Wartesysteme mit deterministischen Ankunfts- und Bedienzeiten
      3. 9.4.3 Wartesysteme mit stochastischen Ankunfts- und Bedienzeiten
      4. 9.4.4 Gesetz von LITTLE
      5. 9.4.5 Klassifikation von Wartesystemen
      6. 9.4.6 Poissonsche Wartesysteme
    5. Literaturhinweise
  19. 10 Kontinuierliche Markovketten und Semi-Markovprozesse
    1. 10.1 Modellierungsziel
    2. 10.2 Kontinuierliche Markovketten
      1. 10.2.1 Definition
      2. 10.2.2 Verhalten
      3. 10.2.3 Markoveigenschaft
      4. 10.2.4 Eingebettete diskrete Markovkette
    3. 10.3 Semi-Markovprozesse
      1. 10.3.1 Definition
      2. 10.3.2 Zustandsraumdarstellung
      3. 10.3.3 Interpretation von Semi-Markovprozessen
    4. 10.4 Strukturelle Eigenschaften von Markov- und Semi-Markovprozessen
    5. Literaturhinweise
  20. Literaturverzeichnis
  21. Anhänge
    1. Anhang 1: Lösung der Übungsaufgaben
    2. Anhang 2: Mengen, Relationen, Graphen, Matrizen
      1. A2.1 Mengen
      2. A2.2 Relationen
      3. A2.3 Graphen
        1. A2.3.1 Gerichtete Graphen
        2. A2.3.2 Erreichbarkeitanalyse
        3. A2.3.3 Bipartite Graphen
      4. A2.4 Stochastische Matrizen
      5. A2.5 Grundbegriffe der Komplexitätstheorie
    3. Anhang 3: Beschreibung kontinuierlicher Systeme
      1. A3.1 Zeitkontinuierliche Systeme
      2. A3.2 Zeitdiskrete Systeme
    4. Anhang 4: Fachwörter deutsch – englisch
  22. Sachwortverzeichnis
  23. Fußnoten

Product information

  • Title: Ereignisdiskrete Systeme, 3rd Edition
  • Author(s): Jan Lunze
  • Release date: May 2017
  • Publisher(s): De Gruyter Oldenbourg
  • ISBN: 9783110485011