Stationen

Das Affenpuzzle I (Praktisch nicht lösbare Probleme)
Ein Durcheinandander beim 2 mal 2 AffenpuzzleEin Computer rechnet zwar sehr schnell, aber bei manchen Problemen leider nicht schnell genug. Beim sogenannten Affenpuzzle sind Puzzleteile gegeben, an dem an jedem Rand die obere oder untere Hälfte eines Affen aufgedruckt ist mit unterschiedlichen Farben. Die unterschiedlichen Teile müssen so angeordnet werden, dass Ober- und Unterteil zusammen passen müssen. Der Computer benötigt für diese auf den ersten Blick einfache Aufgabe knapp 1 Jahr um ein 6×6 Puzzle zu lösen. Bei einem 7×7 Puzzle sind es bereits etwa 51 Millionen Jahre.  Wie schnell schaffst du es? 

Das Affenpuzzle II (Auch theoretisch nicht lösbare Probleme)

Das unlösbare Affenpuzzle

Selbst wenn manche Probleme theoretisch lösbar sind, wenn genug Zeit gegeben ist, gibt es in der Informatik allerdings auch Probleme, die grundsätzlich nicht von einem Computer gelöst werden können. Das Affenpuzzle II stellt dem Besucher die Frage, ob es mit einem gegebenen Set an Puzzleteile möglich ist, eine unendliche Fläche auszufüllen, vorausgesetzt, man hat unendlich viele Puzzleteile. Dieses sogenannte Entscheidungsproblem lässt sich manchmal mit “Ja” beantworten, wenn eine Wiederholung des Musters gefunden werden kann oder mit “Nein”, wenn man ab einer Stelle das Puzzle nicht mehr weiter legen kann. Bei manchen Sets von Puzzleteilen gibt es allerdings darauf keine Antwort, denn es wird keine Wiederholung gefunden, aber das Puzzle kann dennoch immer weiter gelegt werden. Hier stößt der Computer an seine Grenzen

Binäruhr (Binäres Zahlensystem)

Karten des binären Zahlensystems

Das Dezimalsystem ist nicht das einzige Zahlensystem, das wir heute verwenden. Im Bereich der Informatik wird vor allem das Binärsystem verwendet. Statt zehn Ziffern besitzt das Binärsystem nur zwei, nämlich 0 oder 1. Das Zählen funktioniert genau wie im Dezimalsystem. Ist die erste Stelle voll, wird die nächste Stelle eingeführt (0, 1, 10, 11, 100, 101, 110, 111, etc.).
Die Ziffern 0 und 1 können auch als Zustände AUS und AN interpretiert werden. Die Binäruhr beispielsweise besteht nur aus ein paar Lämpchen, die entweder an oder aus sind. Auch mit 5 Fingern lässt sich auf diese Weise (Finger ausgestreckt, Finger nicht ausgestreckt) nicht nur bis fünf zählen, sondern bis 31.

Binärwaage (Rechnen in verschiedenen Zahlensystemen)
Die Binärwaage mit dezimalen und binären GewichtenJede Dezimalzahl lässt sich durch Zehnerpotenzen darstellen. So verhält es sich auch mit anderen Zahlensysteme. Beispielsweise lassen sich die Binärzahlen durch Zweierpotenzen darstellen. Auf einer Waage sollen Besucher anfangs ein Gefühl für das Verhältnis zwischen Zweier- und Zehnerpotenzen bekommen. Danach wird erklärt, wie man vom Dezimalsystem ins Binärsystem umrechnet und umgekehrt. Auch das Addieren im Binärsystem ist gar nicht so viel anders als im Dezimalsystem.

Äthiopische Multiplikation (so multiplizieren Computer)

Kalaha-Brett mit der Simulation der äthiopischen Multiplikation

Die Äthiopische Multiplikation (auch als “Russische Bauernmultiplikation” oder “Ägyptische” bzw. “Abessinische” Multiplikation bekannt) ist ein Algorithmus zum Multiplizieren von zwei Zahlen. Wüstenhändler vor einigen Jahrtausenden haben nicht so wie wir heute multipliziert, sondern viel einfacher! Und das Interessante ist, dass heutige Computer noch genauso rechnen.
Für das Äthiopische Multiplizieren wird lediglich das Halbieren, Verdoppeln und Addieren benötigt. Das aufwendige Lernen des uns bekannten kleinen Ein-Mal-Eins fällt dabei weg. Stattdessen wird nur das 1×1 des Binärsystems benötigt und dieses besteht nur aus 0 und 1.

Binärmagie (Fehlererkennung und Fehlerkorrektur)
Prüfbits als magischer TrickBei einer Kommunikation (zwischen Mensch-Mensch, Mensch-Computer oder Computer-Computer) kann es passieren, dass Information falsch verstanden wird oder falsche Daten übermittelt werden. Damit solche Fehler nicht unbemerkt bleiben und möglicherweise Schaden anrichten, muss auf irgendeine Art und Weise überprüft werden, ob die Daten gültig sind.
Das geschieht mit den sogenannten Prüfziffern. Prüfziffern kommen überall vor: CD / DVD, Kreditkartennummern, ISBN auf Büchern, EAN-Codes auf Produkten oder Übertragungen von Bildern für den Fernseher. Sie sind eine zusätzliche Information, die den eigentlichen Daten hinzugefügt bzw. angehängt wird. Durch bestimmte Berechnungen zwischen den Daten und den Prüfziffern kann herausgefunden werden, ob bei der Übermittlung der Daten Fehler passiert sind. Diese können im besten Fall korrigiert oder gegebenenfalls neu anfordert werden oder die Daten werden einfach nicht bearbeitet und ignoriert.

Codierung (Formen der Informationsdarstellung)
Das Flaggenalphabet als Beispiel für CodierungCodieren ist der Vorgang, Information in einer anderen Form darzustellen als wir es normalerweise kennen. Ein paar Beispiele für Codes sind der Morsecode, das Flaggenalphabet oder die Hieroglyphen. Aber auch Abkürzungen beim Chatten wie “gn8”, “gg” und “hdl” können als Codes aufgefasst werden.
Was hat das nun mit Informatik zu tun? In der Informatik benötigen wir eine Schnittstelle zum Computer. Da der Computer nur Nullen und Einsen versteht, müssen wir diesen Folgen von Nullen und Einsen eine Bedeutung geben, damit wir mit dem Computer kommunizieren können. Und das ist wieder eine Form von Codierung.

Sortierwaage (Algorithmisches Sortieren)
Balkenwaage mit Dosen unterschiedlichen GewichtsSortieren ist etwas, was im Alltag immer wieder vorkommt. Zum Beispiel werden in einer Klasse die Namen der Schüler und Schülerinnen nach dem Nachnamen sortiert. Zuhause werden beispielsweise Spielsachen oder auch Kleidungen sortiert.
Während wir Menschen viele Informationen gleichzeitig zur Verfügung haben und “willkürlich” sortieren können, ist der Computer in der Hinsicht beschränkt. Ein Computer braucht eine Anleitung, die Schritt für Schritt vorgibt, wie er zu sortieren hat. Diese Schritt für Schritt Anleitung nennt man in der Informatik auch “Algorithmus”. Ein paar Beispiele für Sortieralgorithmen sind Bubblesort, Insertionsort, Selectionsort und Quicksort.
Sortieren heißt allerdings nicht immer Zahlen und Buchstaben aufsteigend oder absteigend zu sortieren. Es gibt noch andere Arten der Sortierung. Beispielsweise kann man nach der Quersumme oder nach Divisionsrest sortieren. Diese für uns Menschen ungewöhnliche Sortierarten sind für Computer nicht aufwendig und bringen große Vorteile beim Wiederfinden der Daten.

Sortiernetzwerk (Paralleles Sortieren mit Hardware)
Das Sortiernetzwerk ist ein Verfahren zum Die beiden Sortiernetzwerke am Boden der AulaSortieren von Daten, z.B. Wörter oder Zahlen. Das Netzwerk ist fix verdrahtet, es kann einfach nur mit Hardware, ganz ohne Software,  realisiert werden. Dabei werden mehrere Wertepaare parallel (gleichzeitig) verglichen und in richtiger Reihenfolge in die nächste Ebene des Sortiernetzwerks weitergegeben. Wird der Vorgang dem vorgegebenen Plan entsprechend wiederholt, dann sind die Daten am Ende sortiert.

Maximaler Fluss  (Gerichteter Fluss durch ein Netzwerk)
Experimentierstation zur Ermittlung des maximalen FlussesIn einem existierenden Leitungsnetzwerk soll Wasser vom Wasserwerk zu einem bestimmten Ort gepumpt werden. Die einzelnen Leitungen des Netzwerkes haben unterschiedliche Kapazitäten. Durch welche Leitungen muss wieviel Wasser gepumpt werden, sodass am Ende möglichst viel Wasser ankommt? Es soll dabei kein Rückfluss entstehen, da das Wasser nicht zurück fließen kann.
Dieses Problem ist als “das Problem des maximalen Flusses” bekannt und ist mit Algorithmen lösbar. Die Lösung dieses Problems in vielen Bereichen des Alltags essentiell. Viele Probleme lassen sich nämlich auf das Flussproblem zurückführen. Zum Beispiel der Verkehrsfluss auf der Autobahn oder der Datenfluss im Internet. Auch die Partnersuche auf einer Börse oder das Erstellen von Flugplänen haben etwas mit dem Flussproblem zu tun.

Kürzeste Rundreise
Experimentierstation zur Ermittlung der kürzesten Rundreise durch einige österreichische und deutsche StädteFür eine Menge gegebener Städte soll die kürzeste Rundreise gefunden werden. Bei fünf Städten ist das noch keine große Herausforderung. Spätestens bei fünfzehn Städten wird es schwierig. Das Problem des Handlungsreisenden (auf engl. “Travelling Salesman Problem”) ist ein Problem aus der Klasse NP. Das bedeutet, das Problem ist allgemein für größere Anzahl an Städten nicht in praktikabler Zeit lösbar.
Eine optimale Route zu finden, ist nicht nur für Reisende interessant. In der Informatik kann das beispielsweise für Netzwerke zur Chipherstellung interessant sein, um Kosten zu sparen oder Zeit zu gewinnen.

Erkennungsdienst
Das „Teile und Herrsche“-Prinzip ist ein fundamentales Konzept der Informatik, bei dem Aufgabenstellungen in kleinere und übersichtlichere Teilaufgaben zerlegt werden.
Doch nach welcher Strategie soll dieser Zerlegung erfolgen? Ausgehend von dieser Fragestellung werden Entscheidungsbäume vorgestellt und zur Untersuchung verschiedener Zerlegungen herangezogen. Anhand des Spiels „Erkennungsdienst“ werden verschiedene Entscheidungsbäume erstellt und anschließend dahingehend analysiert, welche Aufteilung im Allgemeinen am besten ist.