hilbert

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Streams
2 Errichten des Hilbert-Hotels
3 Die ersten Gäste erscheinen
4 Weitere Hotelgäste werden erwartet
- 4.1 Der Hilbert-Bus
5 Eine Vielzahl von Hilbertbussen

TODO: Erläuterungen hinzufügen

Streams

Zunächst einmal einige Funktionen, um mit den Streams umgehen zu können. (Herausgenommen aus streams.ss von Prof. Wagenknecht, Programmierparadigmen). Einige davon mussten auf den vom Wiki verwendeten Interpreter angepasst werden.

;Liefert das erste Element im Stream
(define stream-car car)

; Liefert den Rest-Stream
(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))


;; Konstruktoren

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

; Liefert das k.te Element im Stream  
(define stream-item
  (lambda (str k)
    (if (= k 0)
      (stream-car str)
      (stream-item (stream-cdr str) (- k 1)))))

; Ausgabe der ersten n Elemente des 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))))))

Errichten des Hilbert-Hotels

Das Hilberthotel besteht, wie in der Beschreibung zu lesen ist, aus unendlich Zimmern. Die Funktion baue-hilberthotel sorgt für das Errichten der Hotels - die noch leeren Zimmer werden mit #f gekennzeichnet.

; Funktion zum Erstellen des Hotel-Streams. Die zunächst noch leeren Zimmer werden mit #f belegt.
(define baue-hilberthotel 
  (lambda()
   (stream-cons #f (baue-hilberthotel))))

; Funktion zum Anzeigen der ersten n Zimmer des Hotels
(define zeige-mir
  (lambda(hotel n)
    (print-stream hotel n)))

; Erstellen eines Hotels
(define hilberthotel (baue-hilberthotel))

Es erfolgt nun die Anzeige der ersten 5 (noch leeren) Zimmer.

(zeige-mir hilberthotel 5)

Die ersten Gäste erscheinen

Obwohl unendlich Zimmer bereitstehen, sollten seltverständlich auch Einzelbuchungen möglich sein. Die Funktion einzelbuchung ermöglicht das Setzen des Gastes an einer beliebigen Stelle in den abzählbar vielen Hotelzimmern. Ist ein Zimmer bereits belegt, so erscheint die entsprechende Fehlermeldung.

Als erster Gast zieht Otto Grundmann in das Zimmer 3 ein.

Hinweis für mich: setzegast mit letrec realisieren

(define setzegast
   (lambda(name hotel nr)
    (cond 
      ((and (= 0 nr) (not (stream-car hotel))) (stream-cons name (stream-cdr hotel)))
      (else (stream-cons (stream-car hotel) (setzegast name (stream-cdr hotel) (- nr 1)))))))

(define einzelbuchung
  (lambda(name hotel nr)
    (if (not (stream-item hotel nr)) (setzegast name hotel nr)
        ((error "Error in einzelbuchung: Zimmer ~a ist belegt! Hier wohnt ~a" nr (stream-item hotel nr)))
    )))

(set! hilberthotel (einzelbuchung "Otto Grundmann" hilberthotel 3))

(zeige-mir hilberthotel 12)

Weitere Hotelgäste werden erwartet

Der zuvor eingezogene Gast hat gute Kontakte und empfiehlt unser Hotel. Es erscheint eine endliche Anzahl von Gästen - transportiert von einem Kleinbus. Da noch viele viele Zimmer leer stehen, ist es kein Problem diese endlich vielen Personen nacheinander in die freien Zimmer unterzubringen. Herr Grundmann muss nicht umziehen.

; Anzeige-Methode
(define kleinbusfabrik
  (lambda (busnummer anzahl nr)
     (if (= nr anzahl) (cons (cons busnummer nr) '())
     (cons (cons busnummer nr) (kleinbusfabrik busnummer anzahl (+ nr 1)))
   )
)) 

(define zeige-mir-kleinbus
  (lambda (bus)
    (display bus)))

(define baue-kleinbus
  (lambda(busnummer anzahl)
    (kleinbusfabrik busnummer anzahl 0)))



(define kleingruppenbuchung
  (lambda (bus hotel)
      (cond
        ((and (null? (cdr bus)) (not (stream-car hotel))) (stream-cons (car bus) (stream-cdr hotel))) ;Letztes Element und nicht belegt
        ((and (not (null? (cdr bus))) (not (stream-car hotel))) (stream-cons (car bus) (kleingruppenbuchung (cdr bus) (stream-cdr hotel)))) ;Nicht das letzte Element und Hotelzimmer nicht belegt
        (else (stream-cons (stream-car hotel)(kleingruppenbuchung bus (stream-cdr hotel)))) ;Sonst, es wohnt jemand im Zimmer
   )
))

(define kleinbus815 (baue-kleinbus 815 8))
(set! hilberthotel (kleingruppenbuchung kleinbus815 hilberthotel))

(zeige-mir hilberthotel 10)

Der Hilbert-Bus

Als neue Herausforderung erscheint nun ein Hilbert-Bus, der eine abzählbar (unendliche) Menge an Gästen transportiert. Wir benötigen eine Unterbringung, die möglichst unkompliziert abläuft - auch in weiser Voraussicht, dass noch mehr Hilbert-Busse erscheinen.

Wir bitten die bereits eingecheckten Gäste so umzuziehen, dass nur die geraden Zimmer belegt werden. Wir erhalten folglich mit Garantie leere (noch keinem Gast zugeordnete) Zimmer, auch wenn sich schon unendlich viele Gäste bei uns aufhalten.

; Hilbert-Bus
(define baue-hilbertbus
  (lambda (busname)
     (letrec
         ((hilbertbusfabrik
           (lambda (platznummer)
             (stream-cons (cons busname platznummer) (hilbertbusfabrik (+ platznummer 1)))
           )
         )) 
       (hilbertbusfabrik 0)
       )
    )
) 


; Check-In für hilbertbus
(define check-in
  (lambda (bus hotel)
     (cond
       ((not (stream-car hotel)) (stream-cons (stream-car bus) (check-in (stream-cdr bus) (stream-cdr hotel))))
       (else (stream-cons (stream-car hotel) (check-in bus (stream-cdr hotel))))
     )
   )
)  

; Gehe in Gerade
(define gehe-in-gerade
  (lambda (hotel)
    (letrec
        ((gehe-in-gerade-helfer
          (lambda (hotel zimmernummer)
            (if (even? zimmernummer) (stream-cons (stream-car hotel) (gehe-in-gerade-helfer (stream-cdr hotel) (+ zimmernummer 1)))
                (stream-cons #f (gehe-in-gerade-helfer hotel (+ zimmernummer 1)))
          )
         )))
      (gehe-in-gerade-helfer hotel 0)
    
    )    
  )
)

(set! hilberthotel (gehe-in-gerade hilberthotel))
(zeige-mir hilberthotel 10)
(define hilbertbus1 (baue-hilbertbus "X"))
(set! hilberthotel (check-in hilbertbus1 hilberthotel))
(zeige-mir hilberthotel 10)

Eine Vielzahl von Hilbertbussen

Unser Erfolg hat sich herumgesprochen, am nächsten Tag steht ein Konvoi, der aus unendlich viele Hilbert-Busse besteht, zum Einchecken vor unserer Tür. Unsere Gäste lassen zwar einiges mit sich machen, aber unendlich oft umziehen, um alle Insassen der Busse unterbringen zu können, ist zu viel verlangt.

Es wird folglich ein Verfahren benötigt, das die Insassen in einer Schlange aufstellt, um das zuvor erfolgreich angewendete check-in-Verfahren anwenden zu können. Kurz gesagt, wir müssen beweisen (und umsetzen), dass die jeweils unendlich vielen Passagiere in den unendlich vielen Bussen abzählbar sind - also jedem Passagier eine eindeutige Nummer zuordbar ist. Ähnlich wie beim Beweis der Abzählbarkeit von rationalen Zahlen (siehe Übungsaufgabe) wird die Strategie des Cantorsches Diagonalisierungsverfahren verwendet.

; Konvoi-Macher
(define konvoimacher
  (lambda (konvoiname)
    (letrec
        ((konvoifabrik
          (lambda (konvoinummer)
            (stream-cons (baue-hilbertbus (string-append konvoiname (number->string konvoinummer))) (konvoifabrik (+ konvoinummer 1)))
          )))
     (konvoifabrik 0))   
  )
)  

; Konvoi-Anzeiger
(define zeige-mir-konvoi
  (lambda (konvoi busse leute)
    (cond
      ((<= busse 0) (display "...\n"))
      (else
        (print-stream (stream-car konvoi) leute)
        (zeige-mir-konvoi (stream-cdr konvoi) (- busse 1) leute)))))

(define konvoi->kette
  (lambda (konvoi)
    (letrec
        ((konvoi->kettehelfer
          (lambda (zeile relzeile spalte)
            (cond
              ((= relzeile 0) (stream-cons (stream-item (stream-item konvoi relzeile) spalte) (konvoi->kettehelfer (+ zeile 1) (+ zeile 1) 0) ))
              (else (stream-cons (stream-item (stream-item konvoi relzeile) spalte) (konvoi->kettehelfer zeile (- relzeile 1) (+ spalte 1))))
            )
          )  
          ))
      
    (konvoi->kettehelfer 0 0 0))
   )
) 


(define zeige-konvoikette
  (lambda (kette anzahl)
    (letrec
        ((zeige-konvoikettehelfer
          (lambda (kette anz aktzeile aktspalte)
            (cond 
              ((<= anz 0) (display "\n...\n"))
              ((= aktzeile aktspalte) (display (stream-car kette)) (display ", \n") (zeige-konvoikettehelfer (stream-cdr kette) (- anz 1) (+ aktzeile 1) 0))
              (else (display (stream-car kette)) (zeige-konvoikettehelfer (stream-cdr kette) (- anz 1) aktzeile (+ aktspalte 1)))
              ))))
    (zeige-konvoikettehelfer kette anzahl 0 0))
         
  )
)

(define k (konvoimacher "M"))
(zeige-konvoikette (konvoi->kette k) 20)
(set! hilberthotel (gehe-in-gerade hilberthotel))
(set! hilberthotel (check-in (konvoi->kette k) hilberthotel))
(zeige-mir hilberthotel 20)

Wie man sehen kann, befinden sich die Personen aus dem Konvoi M in den ungerade Zimmern. Wir haben die unendlich Gäste aus den unendlich Bussen unterbringen können und haben gleichzeitig wieder Platz für weitere unendlich Gäste - unter der Voraussetzung, dass unsere Gäste dazu bereit sind umzuziehen.

Die ursprüngliche Frage, wer denn in Zimmer 234 wohnt, kann nun beantwortet werden:

(define zimmer
 (lambda (nr hotel)
    (stream-item hotel nr)
  )
)

(define k (konvoimacher "M"))
(set! hilberthotel (gehe-in-gerade hilberthotel))
(set! hilberthotel (check-in (konvoi->kette k) hilberthotel))
(zimmer 234 hilberthotel)