Informatik-Rätsel | Niveau 1

Adas Armband

Beim letzten Fest trug Ada Lovelace dieses

magische Armband aus hellen und dunklen Perlen. Danach hat sie es geöffnet und in ein Kästchen gelegt. Welches der vier Armbänder ist ihr magisches Armband?

• 
• 
• 
• 

Answer explanation

Das magische Armband hat 13 Perlen, davon 5 dunkle.

Zwei der dunklen Perlen liegen als Paar nebeneinander. Armband A ist falsch, es hat kein Paar dunkler Perlen. Armband C ist falsch, es hat nur 12 Perlen.

Armband D ist falsch, es hat 6 dunkle Perlen.

Dies ist Informatik!

Die Perlenkette wurde an einer beliebigen Stelle geöffnet und kann dann noch in zwei Varianten hingelegt werden. Es gibt also viele Folgen von „schwarz“ und „weiss“, die die gleiche Perlenkette darstellen. Das gilt auch für Daten wie z.B. Adressen, die in einem Computersystem gespeichert werden. Zum Beispiel kann Biberstrasse ausgeschrieben oder mit Biberstr. abgekürzt werden. Für einen Menschen ist es einfach zu sehen, dass die beiden unterschiedlichen Schreibweisen für das gleiche stehen. Es ist aber viel schwieriger, ein Computerprogramm zu schreiben, das solche unterschiedlichen Schreibweisen zuverlässig als gleich erkennt.

Ein einfaches Programm, das die Armbänder erkennen kann, besteht z.B. darin, das Armband einfach an jeder beliebigen Stelle zu öffnen und in beide Richtungen hinzulegen. Findet man einmal eine Übereinstimmung, sind die beiden Armbänder gleich. Dieses Programm ist zwar einfach, benötigt aber viel Aufwand, weil es so viele Möglichkeiten zu überprüfen gibt. Eine Aufgabe von Informatikern ist es daher, Programme und Methoden zu entwickeln, die wenig Aufwand benötigen, aber trotzdem mit Sicherheit immer das richtige Resultat liefern.

Grace Hoppers Blumen

Grace besucht einen Blumenladen. Da sind die links abgebildeten Blumenarten zu finden. Jede Blume ist in den folgenden Farben erhältlich: weiss, blau und gelb. Grace möchte einen Blumenstrauss mit sechs Blumen, der die folgenden Bedingungen erfüllt:

1. Jede Farbe gelb, weiss und blau soll genau zweimal vorkommen.

2. Blumen der gleichen Art sollen nicht die gleiche Farbe haben.

3. Jede Blumenart soll höchstens zweimal vorkommen.

Welcher Blumenstrauss erfüllt alle drei Bedingungen?

• 
• 
• 
• 

Answer explanation

Im Blumenstrauss A) gibt es drei weisse Blüten (Regel 1 ist verletzt), in B) drei Rosen (Regel 3 ist verletzt), und im Blumenstrauss C) haben zwei Blüten derselben Blumenart die gleiche Farbe (Regel 2 ist verletzt).

 

Dies ist Informatik!

Allgemeine Informatikprobleme werden durch eine Reihe von Einschränkungen beschrieben. Die Aufgabe besteht darin, eine Lösung zu finden, die all diese Einschränkungen oder so viele wie möglich erfüllt. In der Informatik hat man häufig komplexere Aufgaben, bei denen die Beschränkungen beispielsweise durch logische Operatoren wie die UND-Verknüpfung (A und B bedeutet, dass die beiden Bedingungen A und B gleichzeitig erfüllt werden müssen, wie die drei Regeln in unserer Aufgabe) oder die ODER-Verknüpfung (A oder B bedeutet, dass es genügt, wenn der Bedingungen erfüllt wird) gegeben sind.

Margarets Aliens!

Margaret liebt Geschichten über Aliens. Sie denkt sich das folgende Rätsel aus: Ein Alien besteht aus einem Kopf, einem Rumpf, zwei Armen und zwei Beinen. Ein Alien kann durch die Befehle links verändert werden, dabei ist es auch möglich, dass ein Körperteil mehrfach verändert wird. Die einzelnen Befehle werden von links nach rechts ausgeführt. Wie schaut das Alien nach den folgenden Befehlen aus?

K(3), B(+), R(3), A(+), K(r), A(-), R(r)

• 
• 
• 
• 

Answer explanation

Für jeden Körperteil gilt nur der letzte Befehl. Ein vorhergehender Befehl für denselben Körperteil ist in der Endform des Aliens nicht erkennbar, da ein folgender Befehl die Veränderung wirkungslos macht. Daher ist das Ergebnis ein Alien mit einem runden Rumpf (R(r)), kurzen Armen (A(−)), einem runden Kopf (K(r)) und langen Beinen (B(+)). Die anderen Aliens unterscheiden sich von der Lösung C) in mindestens zwei Eigenschaften, so dass sie offensichtlich falsch sind.

 

Dies ist Informatik!

Beim Ausführen eines Programms werden die Befehle der Reihe nach abgearbeitet. Nachfolgende Befehle können dabei die Wirkung vorhergehender Befehle wieder verändern. In Computerprogrammen passiert das häufig bei Variablen, in denen Werte gespeichert werden, die sich während der Laufzeit des Programms mehrfach verändern. Man kann daher die Form der vier Körperteile jeweils wie eine Variable ansehen, in der die aktuelle Form gespeichert ist. Der Befehl „K(r)“ bewirkt dann, dass in der Variablen für die Kopfform der neue Wert „r“ gespeichert wird. Die Notation „K(r)“ ist funktional gedacht. Man ruft die Funktion „K()“ auf und gibt ihr das Argument „r“ mit. Dies wird häufig verwendet, da die Funktion „K()“ nebenbei noch prüfen kann, ob das mitgegebene Argument überhaupt gültig ist. Wenn das nicht nötig ist oder wenn die Variable nur lokal verwendet wird, kann man sie auch direkt überschreiben, hierfür verwendet man häufig den Zuweisungsoperator „=“. Man würde dann beispielsweise „K = r“ im Programm schreiben.

Hedys Hunde

Hedy liebt Hunde. Eines Tages brachte ihre Dogge Duffy mehrere Freunde unterschiedlicher Arten nach Hause. Alle stellten sich artig in einer Reihe auf, so wie links abgebildet. Ein Tausch findet statt, wenn 2 Hunde, die nebeneinanderstehen, ihre Plätze tauschen. Nach einigen Vertauschungen sind die drei grossen Hunde nebeneinander.

Was ist die kleinste Anzahl Vertauschungen, welche nötig ist, dies zu erreichen?

• 5

• 6

• 7

• 8

Answer explanation

Zuerst muss man den ersten grossen Hund zweimal nach rechts tauschen und dann den letzten grossen Hund viermal nach links. Jeder kleine Hund wird dabei einmal getauscht, da jeder kleine Hund zwischen zwei grossen Hunden positioniert ist. Die Vertauschung von zwei kleinen Hunden hat keine Wirkung, so dass jeder nützliche Tausch zwischen einem kleinen Hund und einem grossen Hund stattfinden muss. Da es insgesamt 6 kleine Hunde gibt, bedeutet dies, dass es mindestens 6 Vertauschungen geben muss. Will man alle grossen Hunde ganz nach rechts oder nach links positionieren, so erfordert das mehr als 6 Vertauschungen.

 

Dies ist Informatik!

Normalerweise könnten die Hunde einfach wild durcheinanderlaufen bis die drei grossen Hunde nebeneinanderstehen. In dieser Aufgabe stehen die Hunde jedoch für Daten in einem Speicher. Wenn ein Computer Daten sortieren soll, und er nicht viel Platz zum Zwischenspeichern hat, tauscht er in der Regel nur zwei Daten (Hunde) miteinander aus. Dies nennt man einen swap.

In diesem Fall soll der Computer möglichst schnell, also mit möglichst wenigen swaps die drei grossen Hunde zusammenbringen. Dies ist ebenfalls typisch für Computer: auch wenn einige wenige swaps schneller stattfinden als wir Menschen es mitbekommen können, müssen Computer mit sehr viel mehr Daten arbeiten. Das bedeutet, dass ein schnellerer Algorithmus Daten vielleicht innerhalb von einer halben Sekunde sortiert hat, anstelle dass er dazu zwei Minuten bräuchte. Bei grossen Berechnungen kann der Unterschied tatsächlich zwischen „einige Tage rechnen“ und „mehrere Jahre rechnen“ liegen, wenn der Algorithmus gut oder schlecht programmiert ist.

Sophies Anhänger

Sophie Wilson produziert selbstgemachte Ketten. Dazu verwendet sie klammernförmige Ornamente, die immer paarweise verwendet werden. Um eine Kette herzustellen, beginnt sie mit einem der beiden Paare links. Danach werden wiederholt weitere Klammernpaare an einer beliebigen Stelle eingefügt, wie die drei Beispiele links. Welche der folgenden Ketten wurde mit der erwähnten Methode hergestellt?

• 
• 
• 
• 

Answer explanation

D ist die richtige Lösung: In das ursprüngliche Klammerpaar wurde ein zusätzliches Klammerpaar eingefügt und in dieses wiederum ein weiteres. Alle anderen Ketten wurden nicht mit der beschriebenen Methode hergestellt:

A) Von links beginnend ist der erste Fehler bei Position 3: eine Klammer wurde geschlossen, bevor die Klammer von Position 2 geschlossen wurde.

B) Von links beginnend ist der erste Fehler schon bei Position 1: Eine Klammer wurde geschlossen, bevor sie geöffnet wurde

C) Von links beginnend ist der erste Fehler bei Position 4: eine Klammer wurde geschlossen, bevor sie überhaupt geöffnet wurde.

 

Dies ist Informatik!

Die Regeln zur Herstellung von Ketten sind genau die gleichen Regeln wie für Klammerausdrücke in der Mathematik oder in der Informatik. Ausdrücke ohne Fehler nennt man wohlgeformt. Einen wohlgeformten Ausdruck nennt man auch syntaktisch korrekt in dem Sinne, dass sie die vorgegebenen syntaktischen Regeln, der Grammatik einer formalen Sprache, befolgen. Syntaxfehler sind in der Regel viel leichter zu beheben als Fehler, die zwar syntaktisch korrekt sind, aber andere, mitunter subtile, Denkfehler enthalten. Die letzteren nennt man semantische Fehler.

Dancing like the ENIAC Girls

Erdhörnchen Kathleen und der Biber Marlyn nehmen an einer Tanzshow teil. Je nach Reaktion der Zuschauermenge vollführen sie bestimmte Tanzschritte. Die Tabelle links zeigt, wie sie sich je nach Reaktion bewegen und an welcher Position sie starten. Welche der folgenden Aktionen der Zuschauer lassen das Erdhörnchen Kathleen und den Biber Marlyn am Ende auf einem gemeinsamen Feld landen?

• A:

  Buh! Kreisch!

• B:

  Klatsch! Kreisch!

• C:

  Wow! Kreisch!

• D:

  Kreisch! Kreisch!

Answer explanation

Dies ist Informatik!

Diese Aufgabe ist ein Beispiel für die Arbeit eines Parallelrechners. In diesem Fall handeln zwei Akteure unabhängig voneinander, jedoch nach vorher definierten Regeln. Wenn zwei Akteure kollidieren, also zur gleichen Zeit auf dieselbe Ressource zugreifen wollen (wie beispielsweise den Arbeitsspeicher oder ein angeschlossenes Gerät), muss geregelt werden, wer die Ressource zuerst nutzt. Dies kann man beispielsweise durch Semaphore regeln. Dies gibt einem Akteur die Möglichkeit, eine Ressource zu reservieren, zu nutzen und danach wieder freizugeben. Während der Reservierung darf kein anderer Akteur darauf zugreifen. Damit eine Ressource nicht gleichzeitig reserviert wird, gibt es in der Regel ein zentrales System (z.B. das Betriebssystem), das die Reservierungen der Ressourcen verwaltet und Anfragen in einer eindeutigen Reihenfolge abarbeitet.

Als Du Dir die Abfolge der Tanzschritte auf dem Bildschirm überlegt hast, hast Du übrigens eine Simulation der zwei Akteure vorgenommen. Computersimulationen helfen an sehr vielen Stellen in der Wirklichkeit, zum Beispiel werden Wetterprognosen mit Hilfe von Computersimulationen erstellt.