Das XO-Spiel

Das XO-Spiel geht auf die Idee von Jens Gal­len­ba­cher¹ zu­rück. Das, was hier­bei als „Zau­be­rei in der In­for­ma­tik“ ge­zeigt wird, be­inhal­tet eine sehr schö­ne Er­klä­rung der Be­grif­fe „Red­un­danz von In­for­ma­tio­nen“, „Feh­ler­kor­re­kur“ und „Feh­ler­er­ken­nung“. Man be­nö­tigt für die­ses Spiel le­dig­lich beid­sei­tig be­schrif­te­te Kärt­chen, wobei eine Seite eines Kärt­chens mit dem Sym­bol „X“ und die an­de­re Seite mit dem Sym­bol „O“ ge­kenn­zeich­net ist. Eine Ko­pier­vor­la­ge fin­det man unter 02_­ko­pier­vor­la­gen/02_­duc_­ko­pier­vor­la­ge_xo_­spiel.pdf. Idea­ler­wei­se wer­den die X- und O-Kärt­chen auf un­ter­schied­lich far­bi­gem Pa­pier ge­druckt und an­schlie­ßend zu­sam­men mit Vor­der- und Rück­sei­te la­mi­niert. Auch im Buch von Jens Gal­len­ba­cher, Aben­teu­er In­for­ma­tik, ist im An­hang eine kar­to­nier­te Vor­la­ge zu fin­den. Be­nö­tigt wer­den min­des­tens 36 sol­cher Kärt­chen. Hat man mehr die­ser Kärt­chen, lässt sich die „Zau­be­rei“ etwas über­zeu­gen­der durch­füh­ren. In der Ar­beits­pha­se be­kommt jede Grup­pe ein sol­ches Kar­ten­set. Zum Vor­füh­ren vor der ge­sam­ten Grup­pe eig­nen sich auch Wen­de­ma­gne­te, die an Ta­feln haf­ten blei­ben. Diese kön­nen im In­ter­net be­stellt wer­den.

1. Ab­lauf des Spiels

2. Feh­ler­er­ken­nung und Feh­ler­kor­rek­tur (1-bit, 2-bit, 3-bit-Feh­ler)

Ge­mein­sam oder in klei­ne­ren Grup­pen soll nun der Zau­ber­trick ge­lüf­tet wer­den. Die Idee, die hin­ter die­sem Trick steckt, ist, dass das Legen der schein­bar zu­fäl­li­gen Kar­ten zu einem 6x6-Mus­ter einer strik­ten Regel folgt. Jede Zeile und jede Spal­te wird so er­gänzt, dass die An­zahl der „X“-Kar­ten und die An­zahl der „O“-Kar­ten in allen Zei­len und Spal­ten stets ge­ra­de ist.

Die XO-Kar­ten kön­nen na­tür­lich auch binär in­ter­pre­tiert wer­den. Ein X ent­spricht dabei einer 1, ein O ent­spricht einer 0. Es liegt nun die Frage auf der Hand, ob sich der In­for­ma­ti­ons­ge­halt der zu­nächst ge­leg­ten 25 Kar­ten nach dem Er­gän­zen zu einem 6x6-Mus­ter mit 36 Kar­ten auch er­höht hat. Die Ant­wort ist: nein. Denn man kann je­der­zeit die zu­sätz­li­chen Kar­ten wie­der weg­neh­men und die ur­sprüng­li­che In­for­ma­ti­on bleibt er­hal­ten. Ge­nau­so kann auch je­der­zeit das Mus­ter nach der vor­ge­ge­ben Regel wie­der er­gänzt wer­den. Man kann fest­stel­len, dass sogar jede be­lie­bi­ge Spal­te und jede be­lie­bi­ge Zeile ent­fernt wer­den kann, um dar­aus wie­der ein­deu­tig das Mus­ter zu er­gän­zen. Hier­bei lässt sich der Be­griff der „Red­un­danz“ er­klä­ren. Die zu­sätz­li­chen Kar­ten (in der In­for­ma­tik ent­spre­chen diese den Bits) än­dern den In­for­ma­ti­ons­ge­halt nicht.

Damit stellt sich aber nun die Frage, wozu man dann diese zu­sätz­li­chen Kar­ten (Bits) be­nö­tigt. Die­ser Fra­ge­stel­lung soll nun im Fol­gen­den und mit­hil­fe des Ar­beits­blat­tes (02_­duc_a­b_xo_­spiel.odt) nach­ge­gan­gen wer­den.

In Part­ner­ar­beit oder in Klein­grup­pen kann das Ar­beits­blatt von den Schü­le­rin­nen und Schü­lern er­ar­bei­tet wer­den. Nach­dem in den Grup­pen das Spiel selbst­stän­dig und mit un­ter­schied­li­chen 5x5-Aus­gangs­mus­tern durch­ge­führt wurde, sol­len nun zu einem nicht mehr zu än­dern­den 6x6-Mus­ter ent­spre­chen­de Fra­gen ge­löst wer­den.

Das Ziel dabei ist, dass die Schü­le­rin­nen und Schü­ler fest­stel­len, dass mit­hil­fe der Red­un­dan­zen man­che Feh­ler er­kannt wer­den kön­nen. In be­stimm­ten Fäl­len kann ein Feh­ler nicht nur er­kannt, son­dern sogar kor­ri­giert wer­den. Auf den Ar­beits­blät­tern sol­len die Schü­le­rin­nen und Schü­ler die­je­ni­gen Po­si­tio­nen in den vor­ge­druck­ten Ras­tern far­big mar­kie­ren, die je­weils für die Lö­sung der Auf­ga­be re­le­vant sind, ver­gleich­bar mit den Ab­bil­dun­gen 3 bis 7.

Der erste Fall ent­spricht dem oben durch­ge­führ­ten Zau­ber­spiel. Egal wie das 5x5-Aus­gangs­mus­ter ge­legt und nach der vor­ge­ge­ben Regel zu einem 6x6-Mus­ter er­gänzt wurde, es lässt sich an jeder Po­si­ti­on eine falsch ge­leg­te Karte fin­den und durch Um­dre­hen kor­ri­gie­ren. Das be­deu­tet, dass hier­bei 1-bit-Feh­ler stets er­kannt und kor­ri­giert wer­den kön­nen.

1-bit Feh­ler sind feh­ler­er­ken­nend und feh­ler­kor­ri­gie­rend.

Im zwei­ten Fall soll über­prüft wer­den, ob sich auch 2-bit-Feh­ler, also das Um­dre­hen von zwei Kar­ten, eben­falls fin­den und kor­ri­gie­ren las­sen. Bei dem 6x6-Mus­ter aus Abb. 2 wer­den nun hier­für zwei be­lie­bi­ge Kar­ten um­ge­dreht. Diese sind in der Abb. 3 mit einem roten Rah­men mar­kiert. Man kann nun fest­stel­len, dass so­wohl in der 2. und 5. Zeile als auch in der 2. und 4. Spal­te die An­zahl der X-Kärt­chen und die An­zahl der O-Kärt­chen nicht mehr ge­ra­de ist. Man weiß nun also, dass in der Tat zwei Feh­ler vor­lie­gen. Das be­deu­tet, dass Feh­ler­er­ken­nung bei zwei fal­schen Bits mög­lich ist. Lässt sich die­ser 2-bit-Feh­ler aber auch kor­ri­gie­ren? Dies wird in der Abb. 4 ver­deut­licht. Es gibt näm­lich zwei mög­li­che Paare von Bits, die für eine Kor­rek­tur in­fra­ge kom­men, so­dass nach deren Um­dre­hen die ge­for­der­te Regel wie­der ein­ge­hal­ten wird: das rote Pär­chen und das gelbe Pär­chen. Die vier Bits bil­den zu­sam­men die Ecken eines Recht­ecks. Somit kann es also pas­sie­ren, dass bei einem 2-bit-Feh­ler falsch kor­ri­giert und damit alles ver­schlim­mert wird.

Wer­den zwei di­rekt ne­ben­ein­an­der lie­gen­de Kärt­chen um­ge­dreht, bei­spiels­wei­se in einer Zeile, so kann man zwar in den bei­den be­tref­fen­den Spal­ten er­ken­nen, dass zwei Feh­ler vor­lie­gen müs­sen, je­doch bleibt die An­zahl der X- und O-Kärt­chen in der be­trof­fe­nen Zeile ge­ra­de, so dass jede Zeile für eine Kor­rek­tur in­fra­ge kom­men kann.

2-bit-Feh­ler sind feh­ler­er­ken­nend, je­doch nicht feh­ler­kor­ri­gie­rend.

Im drit­ten Fall be­schäf­tigt man sich mit 3-bit-Feh­lern. Es kön­nen wie­der ver­schie­de­ne Sze­na­ri­en durch­ge­spielt wer­den, die sich darin un­ter­schei­den, wo die feh­ler­haf­ten Bits im Mus­ter ver­teilt sind. Ein Sze­na­rio wird in den Ab­bil­dun­gen 5 und 6 ge­zeigt. Wie­der sind die feh­ler­haf­ten Bits rot mar­kiert. In den Spal­ten 2, 3 und 5 sowie in der Zeile 2 wird die Regel ver­letzt. Eine Ver­mu­tung könn­te sein, dass somit die Feh­ler ge­fun­den und kor­ri­giert wer­den kön­nen. Je­doch zeigt die Ab­bil­dung 6 eben­falls ein feh­ler­haf­tes Mus­ter, wie­der in den Spal­ten 2, 3 und 5 und in der Zeile 2. Of­fen­sicht­lich ist dies aber ein an­de­rer Feh­ler.

Somit ist klar, dass die­ses feh­ler­haf­te Mus­ter nicht kor­ri­giert wer­den kann. Der 3-bit-Feh­ler ist in die­sem Fall er­ken­nend, aber nicht kor­ri­gie­rend.

Noch viel dra­ma­ti­scher zeigt sich das Sze­na­rio, das in Abb. 7 ge­zeigt wird. Die drei Feh­ler lie­gen so, dass sie drei Ecken eines Recht­ecks bil­den. Hier liegt zwar ein 3-bit-Feh­ler vor, er wird je­doch fälsch­li­cher­wei­se als 1-bit-Feh­ler er­kannt und somit auch ent­spre­chend falsch kor­ri­giert (gelb um­ran­det). In die­sem Fall wird der 3-bit-Feh­ler als sol­cher gar nicht er­kannt.

Zu­sam­men­ge­fasst kann man daher sagen:

• Will man Feh­ler­kor­rek­tur be­trei­ben, so kön­nen 1-bit-Feh­ler er­kannt und kor­ri­giert wer­den, 2-bit-Feh­ler kön­nen hin­ge­gen nur er­kannt wer­den.
• Nur wenn man auf die Feh­ler­kor­rek­tur ver­zich­tet, ist es mög­lich bis zu drei Feh­ler zu er­ken­nen.

Als Zu­satz­auf­ga­be im Rah­men der Bin­nen­dif­fe­ren­zie­rung kann über­legt wer­den, wie man mit­hil­fe zu­sätz­li­cher Red­un­dan­zen die Zahl der kor­ri­gier­ba­ren bzw. er­kenn­ba­ren Feh­ler stei­gern könn­te.

---

¹ Jens Gal­len­ba­cher, Aben­teu­er In­for­ma­tik, Ka­pi­tel 11 „In­form­aGik“

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][408 KB]

Un­ter­richts­ver­lauf: Her­un­ter­la­den [pdf][1 MB]

 

Wei­ter zu Das Sen­der-Emp­fän­ger-Spiel