2A02:908:DF57:37C0:ED39:DD6B:78E:C28F: Tippfehler korrigiert Sume

2022-01-12T14:44:03Z

Tippfehler korrigiert Sume

Neue Seite

In der [[Theoretische Informatik|theoretischen Informatik]] ist ein '''Zustandsraum''' eine Beschreibung von [[diskret]]en Zuständen, um sie als einfaches Modell von Maschinen zu verwenden (z. B. [[Endlicher Automat|Endliche Automaten]]) (nicht zu verwechseln mit dem [[Zustandsraum (Neuronales Netz)]] in der Neuroinformatik). Er stellt die Summe aller Zustände eines betrachteten Systems dar.<ref>{{Literatur |Autor=Alexander Malkis |Titel=Logische und methodische Grundlagen der Programm- und Systementwicklung. Datenstrukturen, funktionale, sequenzielle und objektorientierte Programmierung |Hrsg= |Sammelwerk= |Band= |Nummer= |Auflage= |Verlag=Springer Fachmedien |Ort=Wiesbaden |Datum=2019 |ISBN=978-3-658-26301-0 |Seiten=264 |Online= |Abruf=}}</ref>

Formal wird er definiert als ein [[Tupel]] <math>[N, A, S, G]</math> wobei:
* <math>N</math> eine [[Menge (Mathematik)|Menge]] von Zuständen,
* <math>A</math> eine Menge von Übergangskanten zwischen den Zuständen,
* <math>S</math> eine nicht-leere [[Untermenge]] von <math>N</math>, welche die Startknoten enthält und
* <math>G</math> eine nicht-leere Untermenge von <math>N</math>, welche die Zielknoten enthält.
Die Darstellung kann über [[Zustandsübergangsdiagramm]]e erfolgen. Hilfreich beim Verständnis von Zustandsräumen ist die [[Graphentheorie]], die Mengen aus [[Knoten (Graphentheorie)|Knoten]] und [[Kante (Graphentheorie)|Kanten]] betrachtet.

Ein Zustandsraum kann mit folgenden Eigenschaften beschrieben werden:

* Die [[Zustandsraum-Komplexität|Komplexität]] entspricht der Größe der Menge <math>N</math>. Oft ist der Zustandsraum nicht beschränkt (z. B. bei [[Turingmaschine]]n). Abhängig von der Definition des Zustandsraumes ist diese Größe nicht immer leicht zu bestimmen.
* Die [[Struktur (Mathematik)|Struktur]] des Zustandraums, lässt sich mittels [[gerichteter Graph]] modellieren und so analysieren, ob diese [[Topologische Sortierung|topologisch sortierbar]] ist ([[Baum (Graphentheorie)|Baum]]) oder [[Zyklus (Graphentheorie)|zyklisch]].

== Siehe auch ==
* [[Endlicher Automat]]

== Einzelnachweise ==
<references />
[[Kategorie:Automatentheorie]]

Zustandsraum (Informatik) - Versionsgeschichte

2A02:908:DF57:37C0:ED39:DD6B:78E:C28F: Tippfehler korrigiert Sume