IIm18-Kreativaufgabe1

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
== Aufgabenstellung ==


Modellieren Sie die skurrilen Deutungen von Unendlichkeit am Beispiel [https://web1.hszg.de/cwagenknecht-lehre/TI/Berechenbarkeitstheorie/VL/hilbertbus-CW.pdf ”Hilbertbus“] im ProgrammingWiki.

Wer wohnt in Zimmer 234? Hinweis: Verwenden Sie streams.

Arbeiten Sie im Team an Verbesserungen und ggf. an Erweiterungen.


=== Hilfsfunktionen ===

Einige Hilfsfunktionne die benötigt werden für die Aufgabe.

<code id="5cfd7282efed6">
;Streambehandlung
(define stream-car car)

(define stream-cdr
  (lambda (stm)
    (force (cdr stm))))


;; Konstruktoren

(define-macro (stream-cons head tail)
  `(cons ,head (delay ,tail)))

(define stream-item
  (lambda (str k)
    (if (= k 0)
        (stream-car str)
        (stream-item (stream-cdr str) (- k 1)))))


</code>

=== Hotel bauen ===


Die Zimmer des unendlichen Hotels werden fortlaufend durchnummeriert. Das erste Zimmer besitzt die Nummer 0. Außerdem gibt es in unserem Hilberthotel nur Einzelzimmer. Als Erstes wird das Hotel gebaut und bis jetzt ist noch kein Gast eingezogen und deshalb werden die Zimmer mit false vorbelegt.

<code id="5cfd7282eff44">(define baue-hilberthotel
  (lambda ()
    (stream-cons #f (baue-hilberthotel)))
  )
</code>

<code id="5cfd7282effa7">(define hilberthotel (baue-hilberthotel))</code>

<code id="5cfd7282f0006">(define zeig-mir
  (lambda (stm n)
    (cond
      ((= n 0)
       (cond
         ((null? stm) (display ""))
         (else
          (display "...\n"))))
      (else
       (display (stream-car stm))
       (zeig-mir (stream-cdr stm) (- n 1))))))
</code>
<run id="5cf7eff092710">(zeig-mir hilberthotel 12)</run>

=== Einzelbuchung ===

Die ersten Gäste treffen ein und jedem Gast wird ein Zimmer zugeordnet.  Falls das Zimmer bereits belegt ist, wird eine Meldung ausgegeben, wer das Zimmer bereits bezogen hat. Mittels set  wird die Buchung im Hilberthotel übernommen.

<code id="5cfd781038155">(define einzelbuchung
  (lambda (s str roomold)
    (let ([s s] [str str] [room roomold])
      (letrec
          ((helper
            (lambda (s str room)
              (cond ((= room 0)
                     (cond ((eq? (stream-car str) #f)
                            (stream-cons s (stream-cdr str)))
                           (else
                            (string-append "Error in einzelbuchung: Zimmer " (format "~a " roomold) " ist belegt. Hier wohnt " (stream-car str) ".")
                            )))
                    (else
                     (stream-cons  (stream-car str) (helper s (stream-cdr str) (- room 1)) 
                                   )))
              )))
        (helper s str room)))))

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


<run id="5cfd781038385">(zeig-mir hilberthotel 15)</run>

=== Baue Kleinbus ===

Hier wird eine Funktion definiert, die einen Kleinbus erstellt. Der Kleinbus hat eine Nummer und eine feste Anzahl an Sitzplätzen. Der Kleinbus wird hier wieder als Stream repräsentiert.

<code id="5cfd781038203">

(define baue-kleinbus
  (lambda (nr anzahl)
    (let ([anz anzahl] [nr nr] )
      (letrec
          ((helper
            (lambda (anz)
              (cond
                ((< anz 1)
                 (display ""))
                (else (stream-cons (cons nr (- anzahl anz)) (helper ( - anz 1)))))
              )))
        (helper anz)
        ))))

(define kleinbus0815 (baue-kleinbus 815 8))</code>
Die Belegung von Kleinbus 0815 sieht folgendermaßen aus:

<run id="5cfd781038469">(zeig-mir kleinbus0815 8)</run>

=== Kleingruppenbuchung ===

Der soeben erstellte Kleinbus fährt vor dem Hotel vor. Die Gäste müssen nun in die Zimmer untergebracht werden. Dafür wird festgelegt, dass das erste freie Zimmer als nächstes vergeben wird.

<code id="5cfd7810382cc">(define kleingruppenbuchung
  (lambda (bus hotel)
    (cond ((js-undefined? bus) hotel)
          (else
           (cond ((eq? (stream-car hotel) #f)
                  (stream-cons (stream-car bus) (kleingruppenbuchung (stream-cdr bus) (stream-cdr hotel)))
                  )
                 (else
                  (stream-cons (stream-car hotel) (kleingruppenbuchung bus (stream-cdr hotel)))))))))


(set! hilberthotel (kleingruppenbuchung kleinbus0815 hilberthotel))</code>

Die Belegung vom Hilberthotel nach dem Einchecken der Gäste vom Kleinbus:
<run id="5cfdf3b680ae5">(zeig-mir hilberthotel 15)</run>

=== baue Hilbertbus ===

Als nächstes werden sogenannte Hilbertbusse gebaut. Dies sind Busse die unendlich viele Sitzplätze haben und somit unendlich viele Personen befördern können. Der Bus bekommt als Parameter wieder eine Nummer.

<code id="5cfdf3b680991">; Hilbertbus

(define baue-hilbertbus
  (lambda (nr)
    (let ([anz 0] [nr nr] )
      (letrec
          ((helper
            (lambda (anz)
                (stream-cons (cons nr anz) (helper (+ anz 1)))))
              )
        (helper anz)
        ))))

(define bus3813 (baue-hilbertbus 3813))</code>

=== check-in Hilbertbusgäste ===

Der Hilbertbus 3813 fährt vor dem Hotel vor und den Gästen wird ein Zimmer zugeordnet. Dazu wird ein spezielles Check-In verwendet, welches den Stream des Hilbertbusses nimmt und  jeden Gast in das nächste freie Zimmer einquartiert.
<code id="5cfdf3b680a45">(define check-in
  (lambda (bus hotel)
    (cond ((js-undefined? bus) hotel)
          (else
           (cond ((eq? (stream-car hotel) #f)
                  (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)))))))))


(set! hilberthotel (check-in bus3813 hilberthotel))</code>

Die Belegung des Hotels nach der Ankunft des Hilbertbusses

<run id="5cfdf3b680b51">(zeig-mir hilberthotel 30)</run>

=== Umzug nach gerade ===

Nach der Ankunft des Hilbertbusses, könnte man glauben das Hilberthotel sei ausgebucht. Doch dem ist nicht so. Es hat sich schon ein weiterer Bus angekündigt. Um die zukünftigen Gäste aufnehmen zu können, müssen die bisherigen Hotelgäste einen Umzug in Kauf nehmen.Dazu wird jeder Gast aus Zimmer n in das Zimmer 2n umziehen. Damit ist sichergestellt, dass alle Gäste ein Zimmer bekommen, da es unendlich viele gerade Zahlen gibt. Die ungeraden Zimmernummern sind somit wieder frei und der nächste Bus kann entspannt erwartet werden.
<code id="5cfe385e8dbe9">(define gehe-in-gerade
  (lambda (stm)
    (let ([stm stm] [index 0])
      (letrec
          ((helper
            (lambda (stm index)
              (cond
                ([even? index]  (stream-cons (stream-car stm) (helper (stream-cdr stm) (+ index 1))))
                (else  (stream-cons #f (helper stm (+ index 1)))))   
              )))
        (helper stm index))))) 

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

Das Hotel nach dem Umzug der Gäste in die geraden Zimmernummern.
<run id="5cfe385e8dd24">(zeig-mir hilberthotel 30)</run>

<code id="5cfe385e8dc80">(define bus33 (baue-hilbertbus 33))

(set! hilberthotel (check-in bus33 hilberthotel))</code>

Die Belegung des Hotels nach der Ankunft des Bus 33
<run id="5cfe385e8dd9a">(zeig-mir hilberthotel 30)</run>

=== Konvoi ===

Jetzt kündigt sich ein Konvoi von Hilberbussen an. Die Firma MacroHard (Abkz. "MH")möchte einen Betriebsausflug machen und mit ihrer gesamten Firma in dem Hilberhotel einchecken. Die Firma ist sehr groß. Die Firma hat unendlich viele Abteilungen und in den einzelnen Abteilungen arbeiten unendlich viele Mitarbeiter. Der Konvoi sieht folgendermaßen aus: Jeder Bus repräsentiert eine Abteilung von MAcroHard mit deren Abteilungsmitarbeiter. Beginnend mit der Abteilung 0. Das Ergbnis ist ein Stream von Hilbertbussen.

<code id="5d02a4d9315a5">(define konvoimacher
  (lambda (str)
    (let ([str str] [index 0] [anz 0])
      (letrec
          ((helper
            (lambda (str index)
              (stream-cons (baue-hilbertbus (string-append str (format "~a " index))) (helper str (+ index 1))))))
        (helper str index)))))

(define k1 (konvoimacher "MH"))

(define zeig-mir-konvoi
  (lambda (stm n platz)
       (let ([stm stm][ n n ][n2 platz] [z 0])
         (letrec
             ((helper
               (lambda (z)
                 (cond
                   ((= n 0)(display ""))
                   (else
                    (cond
                      ((= z n2) (display "...\n")(zeig-mir-konvoi (stream-cdr stm) (- n 1) platz))
                      (else
                       (display (stream-item (stream-car stm) z) )
                       (helper (+ z 1)))))
                   ))))
           (helper z )))))</code>


So sieht der Konvoi aus, wenn er sich auf dem Weg zum Hilberhotel macht:
<run id="5d02a4d9317e3">(zeig-mir-konvoi k1 6 4)</run>

=== Konvoi zu Kette ===

Wenn der Konvoi am Hilberthotel ankommt, wäre es problemaitsch wenn Abteilung nacheinander eincheckt im Hilberthotel. Das würde bedeuten, dass die Gäste im Hilberthotel unendlich oft ihr Zimmer wechseln müssten. Das wollen wir den Hotelgästen nicht zumuten und es muss eine Reihenfolge gefunden werden mit der die Mitarbeiter von MacroHard eingecheckt werden können. Dafür werden die einzelnen Streams der Hilbertbusse zu einem großen Zusammengefasst. Wie kann aber sichergestellt werden, dass kein Gast vergessen wird?  Wir haben einmal den Index der Abteilung und die Platznummer innerhalb des Busses. Wenn wir dann die Summe der beiden Indices bilden, haben wir eine Reihenfolge gefunden, in der die Gäste einchecken können, ohne das ein Gast vergessen wird. Die theoretische Basis bildet das  Cantorsche Diagonalisierungsverfahren 1. Art.
====Hilfsfunktionen ====

<code id="5d02a4d931646">

(define get_element
        (lambda (stm platznummer)
          (stream-item stm platznummer)))

(define get_busstream
  (lambda (konvoi busnummer)
    (stream-item konvoi busnummer)))


(define baue_zeilealsliste
  (lambda (stm zeile start test)
    (cond
      ([= zeile 0] (append test  (list(get_element (get_busstream stm 0) start)) ))
      (else
       (append test   (list(get_element (get_busstream stm zeile) start)) (baue_zeilealsliste stm (- zeile 1)(+ start 1) test))
       ))))

</code>



<code id="5d02a4d9316f0">
(define konvoi->kette
  (lambda (stm)
    (let ( [stm stm][liste '()] [index 0])
      (letrec
          ((helper
            (lambda ( liste index stm)
              (cond
                ( [null? liste]
                  (helper (baue_zeilealsliste stm index 0 '() ) (+ index 1) stm))
                (else
                 (stream-cons (car liste)(helper (cdr liste) index stm)))))))
                 (helper  liste index stm)
    ))))</code>

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

=== Einchecken der Kette ===

Die Hotelgäste müssen jetzt einmal umziehen und wieder von ihrer Zimmernummer n in das Zimmer  mit der Nummmer 2n umziehen. Anschließend können die Mitarbeiter von MAcroHard einchecken.

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


Das Hotel nach der Ankunft und einchecken von dem Konvoi
<run id="5d02a6d1bb3fa">
(zeig-mir hilberthotel 42)
</run>

=== Wer wohnt in Zimmer 234?===

Die eingangsgestellte Frage kann nun beantwortet werden:

<run id="5d02a7874187e">(get_element hilberthotel 234)</run>