BuK/IIm11/BuK-KA-Hilbertbus

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
'''Arbeit mit Streams in ExtraSeite auslagern, s. Anleitung, und hier importieren.'''

'''Idee für Erweiterung: HilbertParkhaus: unendlich viele Parkdecks mit jeweils unendlich vielen Parkplätzen für Busse mit unendlich vielen Reisenden'''

== 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.


Die Prozedur "stream-cons" dienst zum Erzeugen eines Streams. In Anlehnung an Listen wird auch der Stream als ein Paar aus dem ersten Element und dem Rest-Stream gebildet. Wichtig ist zu beachten, dass die Verarbeitung des Rest-Streams mittels "delay" verzögert wird.

Ebenfalls wie bei Listen werden die Prozeduren "stream-car" und "stream-cdr" definiert, wobei vor allem letztere Interessant ist. Mittels "force" wird die Verzögerung der Abarbeitung des Rest-Streams aufgehoben.

<code id="4f774a106346f">
;; Konstruktoren
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

;; Selektoren
(define stream-car car)
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

;; Praedikat
(define stream?
  (lambda (stm)
    (and (pair? stm)(promise? (cdr stm)))))

;; Operationen mit streams
(define print-stream
  (lambda (stm n)
    (cond
      ((<= n 0) (display "...\n"))
      (else
       (display (stream-car stm))
       (display ", ")
       (print-stream (stream-cdr stm) (- n 1))))))
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))
</code>

Zunächst wollen wir uns mit der Benutzung dieser Stream-Methoden vertraut machen. Als Beispiel dient ein Stream von zufälligen Zahlen:

<code id="53594d842da78">
(define random-stream-maker
  (lambda ()
    (stream-cons (randomInt 101) (random-stream-maker))))
(define random-stream random-stream-maker)
</code>

Der einfache aufruf des Stream liefert das erste Element (eine zufällige Zahl) und den in der Auswertung unterdrückten Rest-Stream.
<run id="53594d842dd77">
(random-stream)
</run>

Mit der oben definierten Prozedur <tt>print-stream</tt> können wir uns nun die ersten x Elemente des Streams anzeigen lassen:

<run id="53594d842de58">
(print-stream (random-stream) 10)
</run>

Ein weiteres Beispiel ist ein Stream, der die natürlichen Zahlen enthält:

<code id="53594d842db51">
(define nat-stream-maker
  (lambda (start)
    (stream-cons start (nat-stream-maker (+ start 1)))))
(define nat-stream (nat-stream-maker 0))
</code>

<run id="53594d842df1c">
(print-stream nat-stream 10)
</run>

Mit Streams können auch Berechnungen durchgeführt werden. Die folgende Prozedur ''stream-opp'' (für Operation) erhält als Argumente zwei Streams und eine Funktion übergeben und führt die Operation jeweils auf die i-ten Elemente der Streams aus.

<code id="53594d842dc2c">
(define stream-opp
  (lambda (stream1 stream2 opp)
    (stream-cons
     (opp (stream-car stream1) (stream-car stream2))
     (stream-opp (stream-cdr stream1) (stream-cdr stream2) opp))))
</code>

Beispiel Addition:
<run id="53594d842dff5">
(print-stream (stream-opp nat-stream nat-stream +) 20)
</run>

Beispiel Multiplikation:
<run id="53594d842e0ad">
(print-stream (stream-opp nat-stream nat-stream *) 20)
</run>

== Hilberthotel ==
Zunächst wird das Hilberthotel errichtet. Leere Zimmer werden mit "#f" gekennzeichnet.
<code id="4f774a1063a00">
(define baue-hilberthotel
  (lambda ()
    (stream-cons #f (baue-hilberthotel))))

(define zeig-mir
  (lambda(hotel n)
    (print-stream hotel n)))

(define hilberthotel (baue-hilberthotel))
</code>

Zeigt man sich die ersten 11 Zimmer an, so sieht man, dass bisher noch kein Gast eingezogen ist.
<run id="4f774a1063dbe">
(zeig-mir hilberthotel 11)
</run>

== Einzelne Gäste ==
Anfangs 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.
<code id="4f774a1063ac2">
(define einzelbuchung
  (lambda (gast stream index)
    (if (<= index 0)
        (if (eq? (stream-car stream) #f)
            (stream-cons gast (stream-cdr stream))
            (error (string-append "Error in einzelbuchung: Dieses Zimmer ist schon durch " (stream-car stream) " belegt."))
        )
        (stream-cons (stream-car stream) (einzelbuchung gast (stream-cdr stream) (- index 1)))
    )
  )
)

(set! hilberthotel (einzelbuchung "Otto Grundmann" hilberthotel 3))
(set! hilberthotel (einzelbuchung "Hella Milkel" hilberthotel 2))
(set! hilberthotel (einzelbuchung "Heribert Wuischke" hilberthotel 7))
</code>

Nachdem die ersten drei Gäste eingezogen sind, sieht die Zimmerbelegung folgendermaßen aus:
<run id="4f774a1063e80">
(zeig-mir hilberthotel 12)
</run>

== Kleine Reisegruppe ==
Anschließend fährt ein Kleinbus mit acht Passagieren vor. Da immer freie Zimmer zur Verfügung stehen, wird jedem Gast der Reihe nach das nächste freie Zimmer zugewiesen.
<code id="4f774a1063b65">
(define baue-kleinbus
  (lambda (name count)
    (if (> count 0) 
        (append (baue-kleinbus name (- count 1)) (list (cons name count)))
        (list (cons name count))
    )
  )
)
(define kleingruppenbuchung
  (lambda (liste stream)
    (if (null? liste)
        stream
        (if (eq? (stream-car stream) #f)
            (stream-cons (car liste) (kleingruppenbuchung (cdr liste) (stream-cdr stream)))
            (stream-cons (stream-car stream) (kleingruppenbuchung liste (stream-cdr stream)))
        )
    )
  )
)
(define zeig-mir-kleinbus
  (lambda (liste)
    (display liste)
  )
)

(define kleinbus815 (baue-kleinbus 815 8))
(set! hilberthotel (kleingruppenbuchung kleinbus815 hilberthotel))
</code>

Die Passagiere des Kleinbusses treten in folgender Reihenfolge zum Check-In an:
<run id="4f774a1063f3a">
(zeig-mir-kleinbus kleinbus815)
</run>

Nach dem Bezug der Zimmer ergibt sich folgende Zimmerbelegung:
<run id="4f774a1064002">
(zeig-mir hilberthotel 15)
</run>



== 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. 
<code id="4f774a1063c09">
(define baue-hilbertbus
  (lambda (name)
    (letrec 
      ((fabrik 
        (lambda (start)
          (stream-cons (cons name start) (fabrik (+ start 1)))
        )
      ))
      (fabrik 0)
    )
  )
)
(define check-in
  (lambda (bus-stream hotel-stream)
    (if (eq? (stream-car hotel-stream) #f)
        (stream-cons (stream-car bus-stream) (check-in (stream-cdr bus-stream) (stream-cdr hotel-stream)))
        (stream-cons (stream-car hotel-stream) (check-in bus-stream (stream-cdr hotel-stream)))
    )
  )
)

(define bus3813 (baue-hilbertbus 3813))
(set! hilberthotel (check-in bus3813 hilberthotel))
(define bus33 (baue-hilbertbus 33))
</code>

Vor dem Check-In betrachten wir zunächst die Gäste:
<run id="4f774a10640ee">
(zeig-mir bus3813 8)
</run>

Die Zimmerbelegung nach dem Check-In gestaltet sich wie folgt:
<run id="4f774a10641b6">
(zeig-mir hilberthotel 20)
</run>

Es scheinen keine freien Zimmer mehr vorhanden zu sein, doch da kommt noch ein Bus gefahren:
<run id="4f774a1064279">
(zeig-mir bus33 8)
</run>

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.
<code id="4f78907d5331b">
(define gehe-in-gerade
  (lambda (hotel-stream)
    (stream-cons (stream-car hotel-stream) (stream-cons #f (gehe-in-gerade (stream-cdr hotel-stream))))
  )
)

(set! hilberthotel (gehe-in-gerade hilberthotel))
</code>

Nach dem Umzug der bisherigen Gäste stehen wieder unendlich viele freie Zimmer zur Verfügung:
<run id="4f774a106433e">
(zeig-mir hilberthotel 30)
</run>

Nun können die neuen Gäste ihr Zimmer beziehen.
<code id="4f78907d533f5">
(set! hilberthotel (check-in bus33 hilberthotel))
</code>

Sobald alle Gäste ihr Zimmer bezogen haben, ergibt sich nachfolgende Zimmerbelegung:
<run id="4f774a1064424">
(zeig-mir hilberthotel 30)
</run>

== 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. 
<code id="4f7893099718e">
(define konvoimacher
  (lambda (name)
    (letrec 
      ((fabrik 
        (lambda (abteilung)
          (stream-cons (baue-hilbertbus (string-append name (number->string abteilung))) (fabrik (+ abteilung 1)))
        )
      ))
      (fabrik 0)
    )
  )
)

(define zeig-mir-konvoi
  (lambda (stream n m)
    (if (<= n 0)
      (if (<= m 0)
        (display "...\n")
        (begin
          (display "..., ")
          (zeig-mir-konvoi stream 0 (- m 1))
        )
      )
     (begin
       (print-stream (stream-car stream) m)
       (zeig-mir-konvoi (stream-cdr stream) (- n 1) m)
      )
    )
  )
)

(define k1 (konvoimacher "MH"))
</code>
Folgender Konvoi kommt angefahren (eine Zeile = 1 Bus):

<run id="4f7893099721e">
(zeig-mir-konvoi k1 4 8)
</run>

== 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 )

<code id="4f78971c01ba5">
(define calculate-t
  (lambda (w)
    (/ (* (+ w 1) w) 2)
  )
)
(define calculate-w
  (lambda (z)
    (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2))
  )
)
</code>

<code id="4f78971c01c20">
(define zimmer
  (lambda (nr stream)
    (if (<= nr 0)
        (stream-car stream)
        (zimmer (- nr 1) (stream-cdr stream))
    )
  )
)

(define konvoi->kette
  (lambda (konvoi)
    (letrec 
      ((platzanweiser 
        (lambda (z)
          (letrec (
            (hole-person
              (lambda (busse bus-nr platz-nr)
                (if (<= bus-nr 0)
                  (zimmer platz-nr (stream-car busse)) ;; zimmer-funktion hat gleiches Prinzip :-)
                  (hole-person (stream-cdr busse) (- bus-nr 1) platz-nr)
                )
              )
            ))
            (let ((w (calculate-w z)))
              (let ((y (- z (calculate-t w))))
                (let ((x (- w y)))
                  (stream-cons (hole-person konvoi x y) (platzanweiser (+ z 1)))
                 )
               )
             )
           )
         )
       ))
      (platzanweiser 0)
    )
  )
)
</code>

Nachdem das oben beschriebene Prinzip angewandt wurde, ergibt sich eine einzige Kette an Passagieren. Diese treten in folgender Reihenfolge zum Check-In an:
<run id="4f78971c01c9a">
(zeig-mir (konvoi->kette k1) 20)
</run>

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. 
<code id="4f789838b013e">
(set! hilberthotel (gehe-in-gerade hilberthotel))
(set! hilberthotel (check-in (konvoi->kette k1) hilberthotel))
</code>

Nach dem Check-In ergibt sich folgende Zimmerbelegung:
<run id="4f789838b01a0">
(zeig-mir hilberthotel 42)
</run>

== 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:
<run id="4f789838b01f1">
(zimmer 234 hilberthotel)
</run>