DIE CHALLENGE
Ein Film,
20 Fragen
Die Spielregeln sind schnell erklärt: Ich suche mir einen Film aus, ihr müsst mit maximal 20 Ja-Nein-Fragen herausbekommen, welchen ich im Kopf habe. Mit jeder Frage müsst ihr also möglichst viele falsche Filme ausschließen – bis nur noch der richtige Film übrig bleibt. Wie geht das? Mit Informatik natürlich. Nehmen wir an, gesucht wird der Film „Hackers – im Netz des FBI“ (1995). Wenn wir direkt mit einer guten Frage einsteigen, können wir die Anzahl der infrage kommenden Filme schon halbieren. Zum Beispiel: Ist der Film vor 2013 erschienen? Die Antwort wäre in diesem Film „Ja“ und wir hätten schon die Hälfte aller möglichen Filme ausgeschlossen. Denn laut der Filmdatenbank IMDb sind ungefähr genauso viele Filme vor 2013 erschienen als danach. Spannend, oder?
Wenn wir mit der nächsten Frage von den verbliebenen Filmen (also denen vor 2013) noch mal die Hälfte ausschließen können, bleibt nur noch ein Viertel der Filme übrig, dann ein Achtel, ein Sechzehntel und so weiter. Nach 20 Fragen landen wir bei nur noch einem 220-tel, oder anders gesagt einem 1.048.576-tel aller Filme – gerade genug, um mit ziemlicher Sicherheit aus allen möglichen Filmen den richtigen zu finden.
Der Prozess, der hinter diesem Spiel steckt, heißt binäre Suche und ist ungemein effizient – exponentiell effizient, um genau zu sein. Er ist eines der wichtigsten Prinzipien hinter effizienten Suchalgorithmen. Noch etwas nerdiger gesagt: Mit jeder Frage bekomme ich ein Bit an Information (eine 0 bei „Nein“, eine 1 bei „Ja“). 20 Fragen sind also 20 Bit oder etwas weniger als drei Byte. Und so wenig Speicherplatz reicht schon, um jeden Film der Welt eindeutig zu kodieren!
Wer jetzt Informatik nicht zumindest ein bisschen cool findet, der*dem kann ich auch nicht helfen.
