Zurück zum Index
Autoren-Aufruf! Ich habe seit Jahren keine Zeit und Lust mehr, die Inhalte von Mandalex zu pflegen, weswegen sie teilweise veraltet und inkorrekt sind. Wenn ein Wikipedia-Autor über diese Seite stolpert und Lust hat, meine Texte irgendwie in Wikipedia zu integrieren, darf er oder sie mir eine Email schreiben, ich würde die einzelnen Seiten dann gerne abgeben, auf dass ich die Seite irgendwann schliessen kann. Und bevor die Frage kommt: Nein, ich zahle nichts.
Dies ist ein Beispiel eines deterministischen und probabilistischen Automaten. Es geht um einen einfachen Münzwechsler, welcher die (Schweizer-)Münzen 10-, 20- und 50-Rappen akzeptiert und danach den exakt gleichen Betrag zurückgibt, jedoch nach dem Zufallsprinzip mit anderen Münzen.
In den Zuständen wird gespeichert, wieviel Geld insgesamt bereits eingeworfen wurde. Gestartet wird beim linken Status 0. Der Vorgang der Münzeingabe erfolgt deterministisch (links): Die Übergänge entsprechen den Münzen, die eingeworfen wurden. Sobald das Signal zum Geldauswerfen kommt (output), wird in den gleichen Status im rechten Teil gesprungen. Von dort aus wird wiederum nach unten traversiert, jedoch diesmal spontan, also ohne, dass ein Signal von aussen kommen muss. Der Automat kann bei einigen States verschiedene Wege wählen, die einzelnen Münzrückgaben sind dabei mit Wahrscheinlichkeiten (fett gedruckt) belegt (probabilistisch).
#====# #====#
/--------->| 50 |----------------------->| 50 |---------\
| #====#<--\ output /---#====# |
| ^ | | | |
| 10| | | |1/4 |
| | | | V |
| #====# |20 1/4| #====# |
| | 40 |-- | -------------- | ->| 40 | |
| /-->#====# | output | #====#---\ |
| | ^ | | | | |
| | 10| | | |1/2 | |
| | | | | V | |
| | #====#---/ \-->#====# | |
| 20| | 30 |----------------------->| 30 | |1/2 |
| | #====#<--\ output /---#====# | |
| | ^ | | | | |
|50 | 10| | | |1/2 | |1/2
| | | | | V | |
| \---#====# |20 1/2| #====#<--/ |
| | 20 |-- | -------------- | ->| 20 | |
| /-->#====# | output | #====#---\ |
| | ^ | | | | |
| | 10| | | |1/2 | |
| | | | | V | |
| | #====#---/ \-->#====# | |
| 20| | 10 |----------------------->| 10 | |1/2 |
| | #====# output #====# | |
| | ^ | | |
| | 10| |1 | |
| | | V | |
| \---#====# #====#<--/ |
| | 0 |<-----------------------| 0 | |
\----------#====# 1 #====#<--------/
Wenn also 50 Rappen im Automaten eingeworfen worden sind und die Rückgabetaste gedrückt wird, ist es möglich, dass folgende Münzen zurückkommen:
10 10 10 10 10 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 * 1/2 * 1 = 1/32 10 10 10 20 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 * 1/2 = 1/32 10 10 20 10 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 * 1 = 1/16 10 20 10 10 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 * 1 = 1/16 20 10 10 10 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 * 1 = 1/16 10 20 20 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 = 1/16 20 10 20 mit Wahrscheinlichkeit 1/4 * 1/2 * 1/2 = 1/16 20 20 10 mit Wahrscheinlichkeit 1/4 * 1/2 * 1 = 1/8 50 mit Wahrscheinlichkeit 1/2 = 1/2