hilbert
Aus ProgrammingWiki
Inhaltsverzeichnis |
Hintergrund
Ein wirkliches Hotel verfügt über genau n, also endlich viele Zimmer, und bietet folglich Platz für höchstens n Gäste.
Dem sehr bekannten Mathematiker David Hilbert (23.01.1862-14.02.1943) verdanken wir die Geschichte von einem Hotel mit unendlich vielen Zimmern. Wie viele Gäste können in dem "unendlichen Hotel" untergebracht werden?
Die Zimmer des unendlichen Hotels werden fortlaufend durchnummeriert. Darüber hinaus verabreden wir, dass die Nummerierung mit der Zahl 0 beginnt. Zur Vereinfachung gehen wir hier davon aus, dass das Hotel ausschließlich über Einzelzimmer verfügt.
Arbeiten mit Streams
Um das Hilberthotel zu realisieren, ist es nötig, mit Streams zu arbeiten. In Scheme kann dies mit Hilfe der verzögerten Evaluation implementiert werden. Dafür ist es zunächst nötig, einige Grundfunktionen zur Verfügung zu stellen. Diese basieren auf dem Buch Programmierparadigmen Seite 63 ff.
Hilberthotel
Zunächst wird das Hilberthotel errichtet. Leere Zimmer werden mit "#f" gekennzeichnet.
Zeigt man sich die ersten 11 Zimmer an, so sieht man, dass bisher noch kein Gast eingezogen ist.
einzelne Gäste
Als erstes ziehen einzelne Gäste in das Hotel ein. Diesen wird eine feste Zimmernummer zugewiesen. Bei der Buchung wird überprüft, ob das gewünschte Zimmer frei ist, wenn nicht, wird ein Fehler ausgegeben.
Nachdem die ersten drei Gäste eingezogen sind, sieht die Zimmerbelegung folgendermaßen aus:
kleine Reisegruppe
Anschließend fährt ein Kleinbus mit acht Passagieren vor. Da immer freie Zimmer zur Verfügung stehen, wird der jedem Gast der Reihe nach das nächste freie Zimmer zugewiesen.
Die Passagiere des Kleinbusses treten in folgender Reihenfolge zum Check-In an:
Nach dem Bezug der Zimmer ergibt sich folgende Zimmerbelegung:
Hilbertbus
Als nächstes kommt ein weiterer Bus gefahren. Diesmal handelt es sich um einen Hilbertbus. Das heißt, dass dieser eine unendliche Menge von Passagieren befördert.
Wie das Hotel, ist der Bus auch als Stream realisiert. Das Verfahren zum Check-In verläuft analog der kleinen Reisegruppe: Jedem Gast wird der Reihe nach das nächste freie Zimmer zugewiesen.
Vor dem Check-In betrachten wir zunächst die Gäste:
Die Zimmerbelegung nach dem Check-In gestaltet sich wie folgt:
Es scheinen keine freien Zimmer mehr zu sein, doch da kommt noch ein Bus gefahren:
Um den neuen Gästen trotzdem ein Zimmer anbieten zu können, müssen die bisherigen Gäste umziehen. Dabei wechselt jeder Gast aus Zimmer n in das Zimmer mit der Nummer 2n. Somit ist jedes zweite Zimmer wieder unbelegt.
Nach dem Umzug der bisherigen Gäste stehen wieder unendlich viele freie Zimmer zur Verfügung:
Nun können die neuen Gäste ihr Zimmer beziehen.
Sobald alle Gäste ihr Zimmer bezogen haben, ergibt sich nachfolgende Zimmerbelegung:
Hilbertbus-Konvoi
Um das ganze zu komplettieren, kommt nun ein Hilbertbus-Konvoi angefahren. Dieser besteht aus unendlich vielen Hilbertbussen. Nun soll jedem Gast aus diesem Konvoi auch ein Zimmer zugeteilt werden.
Zuerst wird der Konvoi erstellt. Dieser ist ein Stream von Hilbertbussen. Also Streams innerhalb eines Streams.
Folgender Konvoi kommt angefahren (eine Zeile = 1 Bus):
Konvoi->Stream
Damit die Gäste des Konvois ihre Zimmer beziehen können, müssen sie der Reihe nach antreten. Da pro Bus unendlich viele Gäste befördert werden, können nicht zunächst nur Gäste eines Busses der Reihe nach einchecken, sondern alle Gäste (aus allen Bussen) müssen sich zu einer einzigen Kette zusammenschließen. So tritt zunächst Passagier 0 aus Bus 0, gefolgt von Passagier 0 aus Bus 1 und dann Passagier 1 aus Bus 0 usw. an.
Um für jeden Index der Kette den jeweiligen Bus und darin den entsprechenden Passagier zu ermitteln, wird die Cantorsche Paarungsfunktion angewandt. Damit ist es möglich, zwei abzählbar unendliche Mengen auf eine abzählbar unendliche Menge abzubilden und für jedes Element der neuen Menge den Index zu bestimmen. Mit Hilfe der Umkehrfunktion kann nun für den jeweiligen Index die Indizes der beiden Ursprungsmengen ermittelt werden. (x = Bus, y = Passagier innerhalb des Busses )
Nachdem das oben beschriebene Prinzip angewandt wurde, ergibt sich eine einzige Kette an Passagieren. Diese treten in folgender Reihenfolge zum Check-In an:
Damit die neuen Gäste einchecken können, müssen die bisherigen Hotelgäste erneut umziehen, damit die ungeraden Zimmer frei werden. Danach beziehen die Konvoi-Gäste ihre Zimmer.
Nach dem Check-In ergibt sich folgende Zimmerbelegung:
Wer wohnt in Zimmer 234?
Auch wenn das Hotel unendlich viele Zimmer besitzt und bereits unendlich viele Gäste ein Zimmer gebucht haben, kann genau angegeben werden, wer in welchem Zimmer wohnt. So ist folgender Gast in das Zimmer 234 eingezogen:
