BuK/IIm11/Studenten/sijeheid/hilbert

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<language>Scheme</language>
== 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.

<code id="4f774a106346f">
;; Selektoren
(define stream-car car)
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))

;; Konstruktoren
(define-syntax stream-cons
  (syntax-rules ()
    ((_ head tail) (cons head (delay tail)))))

;; 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>

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

<run id="4f774a1063e80">
(zeig-mir hilberthotel 12)
</run>

== kleine Reisegruppe ==
<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 (list stream)
    (if (null? list)
        stream
        (if (eq? (stream-car stream) #f)
            (stream-cons (car list) (kleingruppenbuchung (cdr list) (stream-cdr stream)))
            (stream-cons (stream-car stream) (kleingruppenbuchung list (stream-cdr stream)))
        )
    )
  )
)
(define zeig-mir-kleinbus
  (lambda (list)
    (display list)
  )
)

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

Kleinbus kommt angefahren:
<run id="4f774a1063f3a">
(zeig-mir-kleinbus kleinbus815)
</run>

Zimmerbelegung nach Check-In:
<run id="4f774a1064002">
(zeig-mir hilberthotel 15)
</run>

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

groooßer Hilbertbus kommt angefahren:
<run id="4f774a10640ee">
(zeig-mir bus3813 8)
</run>

Zimmerbelegung nach Check-In:
<run id="4f774a10641b6">
(zeig-mir hilberthotel 20)
</run>

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

Gäste müssen umziehen:
<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>
<run id="4f774a106433e">
(zeig-mir hilberthotel 30)
</run>

Zimmerbelegung nach Check-In:
<code id="4f78907d533f5">
(set! hilberthotel (check-in bus33 hilberthotel))
</code>
<run id="4f774a1064424">
(zeig-mir hilberthotel 30)
</run>

<language>Scheme</language>
<language>Scheme</language>
== Hilbertbus-Konvoi ==

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

Macrohard macht Betriebsausflug mit folgenden Bussen (eine Zeile = 1 Bus):

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

<language>Scheme</language>
== Konvoi->Stream ==

Mathematische Hilfsfunktionen, um aus einen Stream von Hilbertbussen, einen einzelnen Stream von Hotelgästen zu definieren.

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

Passagiere treten in folgender Reihenfolge zum Check-In an:

<run id="4f78971c01c9a">
(zeig-mir (konvoi->kette k1) 20)
</run>


Hotelgäste müssen 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>

Zimmerbelegung nach Check-In:
<run id="4f789838b01a0">
(zeig-mir hilberthotel 42)
</run>

== Wer wohnt in Zimmer 234? ==

<run id="4f789838b01f1">
(zimmer 234 hilberthotel)
</run>