Am Beispiel eines kleinen Spiels möchten wir einige Aspekte der Telekommunikationsinformatik bzw. der Informations- und Kommunikationstechnik illustrieren.
Spieler A denkt sich eine Zahl zwischen 1 und 16. Spieler B muss die Zahl erraten, darf dazu aber nur Fragen stellen, die Spieler A mit "Ja" oder "Nein" beantworten kann.
# Spieler A denkt sich eine zufällige Zahl zwischen 1 und 16
import random
geheimeZahl = random.randint(1, 16)
print (f'Die geheime Zahl ist {geheimeZahl}.')
Die geheime Zahl ist 9.
Bei einer einfache Taktik probiert Spieler B die Zahlen von 1 bis 15 systematisch durch. Bei einem "Ja" hat er die richtige Zahl gefunden. Werden alle Fragen mit "Nein" beantwortet, ist die gesuchte Zahl 16.
In der Informatik entwickeln und analysieren wir Algorithmen (z.B. Taktiken für das Zahlenratenspiel), die wir dann in Programmiersprachen (z.B. Python) implementieren und testen. Also implementieren wir die einfache Taktik in Python.
# Eine einfach Taktik für Spieler B: alle Zahlen systematisch durchprobieren
anzahlFragen = 0
for tipp in range (1,16):
anzahlFragen += 1
print (f'Ist die Zahl gleich {tipp}?')
if tipp == geheimeZahl:
print ('Ja!')
break
else:
print ('Nein')
print (f'Die geheime Zahl war {tipp if tipp == geheimeZahl else tipp+1} und Spieler B hat {anzahlFragen} Fragen gebraucht.')
Ist die Zahl gleich 1? Nein Ist die Zahl gleich 2? Nein Ist die Zahl gleich 3? Nein Ist die Zahl gleich 4? Nein Ist die Zahl gleich 5? Nein Ist die Zahl gleich 6? Nein Ist die Zahl gleich 7? Nein Ist die Zahl gleich 8? Nein Ist die Zahl gleich 9? Ja! Die geheime Zahl war 9 und Spieler B hat 9 Fragen gebraucht.
Die einfache Taktik ist leicht zu verstehen und auch leicht zu implementieren (wenig Code, nur eine Schleife und eine Bedinung). Allerdings benötigt sie unnötig viele Fragen, d.h. sie ist nicht sehr effizient. Bei einer cleveren Taktik halbiert Spieler B mit jeder Frage den gesuchten Zahlenbereich und steuert die gesuchte Zahl systematisch an. Auch das können wir implementieren.
# Clevere Taktik für Spieler B: durch sukzessive Intervallhalbierung die gesucht Zahl finden
anzahlFragen = 0
intervallGroesse = 16
intervallStart = 0
while (intervallGroesse > 1):
anzahlFragen += 1 # Anzahl der Fragen hochzählen
intervallGroesse //= 2 # Intervall halbieren
print (f'Ist die Zahl zwischen {intervallStart+1} und {intervallStart+intervallGroesse}?')
if geheimeZahl>=intervallStart+1 and geheimeZahl<=intervallStart+intervallGroesse:
print ('Ja!') # Zahl ist in der ersten Intervallhälfte
else:
print ('Nein!') # Zahl ist in der zweite Intervallhälfte
intervallStart += intervallGroesse
print (f'Die geheime Zahl war {intervallStart+1} und Spieler B hat {anzahlFragen} Fragen gebraucht.')
Ist die Zahl zwischen 1 und 8? Nein! Ist die Zahl zwischen 9 und 12? Ja! Ist die Zahl zwischen 9 und 10? Ja! Ist die Zahl zwischen 9 und 9? Ja! Die geheime Zahl war 9 und Spieler B hat 4 Fragen gebraucht.
Nun sind wir in der Informatik und Kommunikationstechnik immer daran großen und vielen Daten interessiert, d.h. es ist relavant, was passiert, wenn das Spiel mit größeren Zahlen gespiele wird. Was wäre, wenn das Spiel mit Zahlen von 1 bis 32 gespielt wird? Die einfache Taktik benötigt durchschnittlich 16 Fragen, während die clevere stets nur 5 Fragen benötigt ($32 = 2^5$), d.h. der Abstand zwischen den Taktiken wird größer.
Im Allgemeinen gilt: Sei $N$ die Anzahl der Zahlen, so benötigt die einfache Taktik durchschnittlich $\frac{N}{2}$ Fragen; die clevere Taktik lediglich $\lceil \log_{2} N \rceil$ Fragen.
Neben der Beobachtung des Laufzeitverhalten interessiert liefert uns die Informationstheorie auch den Grund für das unterschiedliche Verhalten. Der Informationsgehalt gibt an, "wieviel" Information in einer Nachricht (hier: in der Antwort) steckt. Er ist definiert als negativer Logarithmus der Auftrittswahrscheinlicht.
Für die einfache Taktik ist bei der ersten Frage die Wahrscheinlichkeit für ein "Ja" $\frac{1}{16} = 6.25\%$, für ein "Nein" $\frac{15}{16} = 93.75\%$. Der Informationsgehalt ist damit $ H_{ja}=-ld(\frac{1}{16})=4$ und $H_{nein} = -ld(\frac{15}{16}) \approx 0.09$. Der Informationsgehalt für die gesamte Antwort ist die (mit den Wahrscheinlichkeiten) gewichtete Summe, d.h. $ H_{Antwort1} = \frac{1}{16} \cdot H_{ja} + \frac{15}{16} \cdot H_{nein} \approx 0.34$.
Für die clevere Taktik sind (wegen der gleich großen Intervalle) die Wahrscheinlichkeiten für "Ja" und "Nein" jeweils 50%, d.h. $ H_{ja} = H_{nein} = -ld(\frac{1}{2})=1$. Der Informationsgehalt für jede Antwort ist damit $ H_{Antwort} = \frac{1}{2} \cdot H_{ja} + \frac{1}{2} \cdot H_{nein} = 1$.
Spieler B erhält also bei der cleveren Taktik mehr Informationen durch die Antworten und benötigt dadurch weniger Fragen, um die gesuchte Zahl zu ermitteln.
# Informationsgehalt der Antworten bei der einfachen Taktik für Spieler B
import math
for antwort in range (1,16):
p_ja = 1/(17-antwort)
p_nein = (16-antwort)/(17-antwort)
infGehalt = -p_ja * math.log(p_ja,2) - p_nein * math.log(p_nein,2)
print (f'Informationsgehalt für Antwort {antwort:2d} ist {infGehalt:.3f}.')
Informationsgehalt für Antwort 1 ist 0.337. Informationsgehalt für Antwort 2 ist 0.353. Informationsgehalt für Antwort 3 ist 0.371. Informationsgehalt für Antwort 4 ist 0.391. Informationsgehalt für Antwort 5 ist 0.414. Informationsgehalt für Antwort 6 ist 0.439. Informationsgehalt für Antwort 7 ist 0.469. Informationsgehalt für Antwort 8 ist 0.503. Informationsgehalt für Antwort 9 ist 0.544. Informationsgehalt für Antwort 10 ist 0.592. Informationsgehalt für Antwort 11 ist 0.650. Informationsgehalt für Antwort 12 ist 0.722. Informationsgehalt für Antwort 13 ist 0.811. Informationsgehalt für Antwort 14 ist 0.918. Informationsgehalt für Antwort 15 ist 1.000.
Wie verändern nun das Spiel und fügen eine weitere Regel hinzu: Spieler A darf bei (maximal) einer Frage lügen. Wie sähe jetzt eine clevere Taktik für Spieler B aus? Bei einer Antwort von A weiß Spieler B natürlich nicht, ob A gelogen hat.
Spieler A ist jetzt ein Informationskanal, in dem bei Übertragungen Störungen auftreten können. Wir müssen daher Redundanzen einbauen, um den Effekt einzelner Störungen (hier: einmaliges Lügen) zu bemerken bzw. auszugleichen.
Eine einfache Strategie wäre, jede Frage zweimal zu stellen. Erhält Spieler B jeweils die gleiche Antwort, handelt es sich um die korrekte Antwort. Erhält Spieler B ungleiche Antworten, fragt er ein drittes mal und kann per Mehrheitsentscheid die korrekte Antwort ableiten (2x Wahrheit vs. 1xLüge). Damit würde eine Spieltaktik, die ursprünglich $M$ Fragen benötigt, nun $2M+1$ Fragen benötigen.
Eine effektivere Redundanz kann mit dem Hamming-Code erzeugt werden. Dieser erkennt und korrigiert einen Bit-Fehler in 4 Bits durch Hinzunahme von 3 Bits, d.h. wir können mit 7 Fragen die geheime Zahl ermitteln -- und auch ermitteln, bei welcher Frage (wenn überhaupt) Spieler A gelogen hat. Der Code dafür ist schon etwas länger :-)
import random
zahlen = list (range(1,17))
schongelogen = False
def stelleFrage (frage):
global zahlen, schongelogen
werte = [z for z,f in zip (zahlen, frage) if f]
print (f'Ist die Zahl in folgender Menge? {werte}')
luegen = (not schongelogen) and (random.random()<0.15) # lügen mit 15% Wahrscheinlichkeit pro Frage
if (luegen):
print ("Achtung, ich lüge")
schongelogen = True
if (geheimeZahl in werte) ^ luegen:
print ("Ja")
return True
else:
print ("Nein")
return False
fragen = list (map (lambda x: [a & x > 0 for a,_ in enumerate(zahlen)], [1,2,4,8]))
fragen += list (map (lambda a,b,c: [x ^ y ^ z for x,y,z in zip (fragen[a], fragen[b], fragen[c])], *zip (*[(0,1,3), (0,2,3), (1,2,3)])))
antworten = list (map (stelleFrage, fragen))
for i, a in enumerate (zip(*fragen)):
abstandsvektor = [0 if x==y else 1 for x,y in zip (antworten, list(a))]
hammingabstand = sum (abstandsvektor)
if hammingabstand<2:
print (f'Die geheime Zahl war {zahlen[i]} und Spieler B hat {len(fragen)} Fragen gebraucht.')
if hammingabstand == 1:
luege = next(x+1 for x,y in enumerate(abstandsvektor) if y == 1)
print (f'Antwort {luege} war gelogen.')
Ist die Zahl in folgender Menge? [2, 4, 6, 8, 10, 12, 14, 16] Nein Ist die Zahl in folgender Menge? [3, 4, 7, 8, 11, 12, 15, 16] Nein Ist die Zahl in folgender Menge? [5, 6, 7, 8, 13, 14, 15, 16] Nein Ist die Zahl in folgender Menge? [9, 10, 11, 12, 13, 14, 15, 16] Achtung, ich lüge Nein Ist die Zahl in folgender Menge? [2, 3, 6, 7, 9, 12, 13, 16] Ja Ist die Zahl in folgender Menge? [2, 4, 5, 7, 9, 11, 14, 16] Ja Ist die Zahl in folgender Menge? [3, 4, 5, 6, 9, 10, 15, 16] Ja Die geheime Zahl war 9 und Spieler B hat 7 Fragen gebraucht. Antwort 4 war gelogen.
Das Beispiel "Zahlenraten" verdeutlicht schon einige Inhalte des Studiums der Telekommunikationsinformatik bzw. der Informations- und Kommunikationstechnik.