hilbert

Aus ProgrammingWiki

Archivierte Version vom 2012-04-09T10:21:58+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Hintergrund
2 Arbeiten mit Streams
3 Hilberthotel
4 einzelne Gäste
5 kleine Reisegruppe
6 Hilbertbus
7 Hilbertbus-Konvoi
8 Konvoi->Stream
9 Wer wohnt in Zimmer 234?

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.

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

Hilberthotel

Zunächst wird das Hilberthotel errichtet. Leere Zimmer werden mit "#f" gekennzeichnet.

(define baue-hilberthotel
  (lambda ()
    (stream-cons #f (baue-hilberthotel))
  )
)

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

(define hilberthotel (baue-hilberthotel))

Zeigt man sich die ersten 11 Zimmer an, so sieht man, dass bisher noch kein Gast eingezogen ist.

(zeig-mir hilberthotel 11)

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.

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

Nachdem die ersten drei Gäste eingezogen sind, sieht die Zimmerbelegung folgendermaßen aus:

(zeig-mir hilberthotel 12)

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.

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

Die Passagiere des Kleinbusses treten in folgender Reihenfolge zum Check-In an:

(zeig-mir-kleinbus kleinbus815)

Nach dem Bezug der Zimmer ergibt sich folgende Zimmerbelegung:

(zeig-mir hilberthotel 15)

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.

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

Vor dem Check-In betrachten wir zunächst die Gäste:

(zeig-mir bus3813 8)

Die Zimmerbelegung nach dem Check-In gestaltet sich wie folgt:

(zeig-mir hilberthotel 20)

Es scheinen keine freien Zimmer mehr zu sein, doch da kommt noch ein Bus gefahren:

(zeig-mir bus33 8)

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.

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

Nach dem Umzug der bisherigen Gäste stehen wieder unendlich viele freie Zimmer zur Verfügung:

(zeig-mir hilberthotel 30)

Nun können die neuen Gäste ihr Zimmer beziehen.

(set! hilberthotel (check-in bus33 hilberthotel))

Sobald alle Gäste ihr Zimmer bezogen haben, ergibt sich nachfolgende Zimmerbelegung:

(zeig-mir hilberthotel 30)

Hilbertbus-Konvoi

(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"))

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

(zeig-mir-konvoi k1 4 8)

Konvoi->Stream

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

(define calculate-t
  (lambda (w)
    (/ (* (+ w 1) w) 2)
  )
)
(define calculate-w
  (lambda (z)
    (floor (/ (- (sqrt (+ (* 8 z) 1)) 1) 2))
  )
)

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

Passagiere treten in folgender Reihenfolge zum Check-In an:

(zeig-mir (konvoi->kette k1) 20)

Hotelgäste müssen umziehen, damit die ungeraden Zimmer frei werden. Danach beziehen die Konvoi-Gäste ihre Zimmer.

(set! hilberthotel (gehe-in-gerade hilberthotel))
(set! hilberthotel (check-in (konvoi->kette k1) hilberthotel))

Zimmerbelegung nach Check-In:

(zeig-mir hilberthotel 42)

Wer wohnt in Zimmer 234?

(zimmer 234 hilberthotel)

hilbert

Inhaltsverzeichnis

Hintergrund

Arbeiten mit Streams

Hilberthotel

einzelne Gäste

kleine Reisegruppe

Hilbertbus

Hilbertbus-Konvoi

Konvoi->Stream

Wer wohnt in Zimmer 234?

Suche