BuK-Kreativaufgabe02 G2
Aus ProgrammingWiki
Inhaltsverzeichnis |
Hilbert Bus
Das Hilbert Hotel und der Hilbert Bus gehen auf Betrachtungen des Mathematikers David Hilbert (1862-1943) zurück. Sie werden benutzt, um zu veranschaulichen, welche Unterschiede sich im Umgang mit (abzählbar) unendlich großen Mengen gegenüber den dem Menschen viel vertrauteren endlichen Mengen ergeben.
So wird angenommen, dass das Hilbert Hotel über abzählbar unendlich viele Zimmer verfügt und ein Hilbert Bus unendlich viele Gäste zum Hotel bringen kann.
Das Problem, welches letztlich entsteht, liegt in der Zuordnung von Gast und Zimmer. Leicht zu verstehen ist die Verfahrensweise beim Eintreffen einzelner Gäste oder Gruppen mit endlich vielen Personen. Man merkt sich das zuletzt vergebene Zimmer und weist neuen Gästen die entsprechenden nachfolgenden Zimmer zu. Ebenso verfährt man beim Eintreffen des ersten Hilbert Buses mit unendlich vielen Gästen. Der erste Fahrgast bekommt das nächste freie Zimmer, der zweite Fahrgast das übernächste und so weiter.
Da stellen sich schon die ersten Fragen. Das Hotel hat unendlich viele Zimmer und angenommen es hatten bereits 10 Gäste eingecheckt als der Bus ankam. Sind nun mehr als unendlich viele Gäste im Hotel? Hat wirklich jeder Businsasse ein Zimmer beziehen können?
Betrachten wir aber gleich ein neues Szenario. Ein weiterer Gast fragt nach einem Zimmer. Welches ist aber nun das letzte Zimmer, um dessen Nachfolger zu ermitteln? Ist das Hotel ausgebucht?
Erläuterungen, wie diese Probleme umgangen werden können, so dass keine Gäste abgewiesen werden müssen, finden sich u.a. auf folgender Seite Wer wohnt in Zimmer 234?. Dabei werden die Hotelgäste aufgefordert in andere Zimmer umzuziehen. Die Zuweisung der neuen Zimmernummer erfolgt dabei durch eine relative Angabe zur aktuellen. (wie ziehe 3 Zimmer weiter)
Da ein Zimmerwechsel eine unangenehme Belastung für einen Hotelgast darstellen kann, möchten wir hier einen anderen Weg der Zimmerzuteilung beschreiben.
Das obige Modell geht davon aus, dass die Zimmernummern mit Hilfe der natürlichen Zahlen gebildet werden. Wir verwenden in unserem Hotel Zimmernummern aus der Menge der rationalen Zahlen. Das ist möglich, da es sich dabei, wie im ersten Modell, ebenfalls um eine abzählbar unendliche Menge handelt (siehe Beweis). Unser Hotel hat demnach die gleiche Größe (oder in Bezug auf Mengen die gleiche Mächtigkeit), besitzt unendlich viele Stockwerke mit jeweils unendlich vielen Zimmern. Der Nenner der Zimmernummer gibt das Stockwerk an und der Zähler bezeichnet den zugehörigen Raum. Die Zahl gibt an, dass es sich hier um das 3. Zimmer in der 4. Etage handelt. Also alles wie gehabt nur eine neue Beschriftung der Zimmer.
Unsere Vorgehensweise bei der Zuteilung der Zimmer ist folgende:
- Beim Eintreffen einer endlichen Anzahl von Gästen erhalten diese ausschließlich Zimmer in der ersten Etage. Damit ist es stets möglich sich das zuletzt vergebene Zimmer zu merken und neue Gäste in den nachfolgenden Zimmern unterzubringen.
- Trifft ein Hilbert Bus mit unendlich vielen Gästen ein, bekommen diese die nächste freie Etage zugewiesen. Der erste Fahrgast Zimmer 1 dieser Etage, der zweite Zimmer 2 und so weiter. Hier merken wir uns immer die zuletzt zugewiesene Etage und können so neuen Gästen die nächstfolgende Etage zuweisen.
So muss kein Gast abgewiesen werden, es ist sehr leicht zu ermitteln welches Zimmer durch welchen Gast belegt ist und ein Umzug innerhalb des Hotels ist nicht mehr erforderlich. Wir denken, dass sich die Gäste bei uns wohlfühlen.
Streams
Beschreibung des Datentyps und Umsetzung in C#
Streams (Ströme) sind potentiell unendliche Daten. In einem Programmiersystem können sie nur dann repräsentiert werden, wenn man das Konzept der verzögerten Evaluation (lazy evaluation) verwendet. Anderenfalls würde sich eine Endlosschleife ergeben.
Anders als in Scheme, wo Streams als rekursive Datenstrukturen benutzt werden, kann der Stream in C# als iterierbare Liste dargestellt werden. Statt diese Liste aber zu Beginn der Ausführung zu erstellen, was praktisch nicht machbar ist, wird die Liste dynamisch erweitert. Einem Iterator ist es möglich, in dieser potenziell unendlichen Liste, die Elemente nacheinander abzurufen. Durch das anfangs erwähnte Konzept der verzögerten Evaluation werden die Elemente der Liste erst berechnet wenn sie auch wirklich verwendet werden.
Die hier gezeigten Codebeispiele benötigen mindestens Version 3.5 von C# (plattformunabhängig).
Strom der natürlichen Zahlen
Um einen Stream zu beschreiben wird die Schnittstelle IEnumerable verwendet. Sie sorgt dafür, dass wir einen Iterator zur Verfügung bekommen. Die Initialisierung eines Streams der natürlichen Zahlen sieht so aus:
IEnumerable natNumbers = NatNumbers();
Wobei die Funktion NatNumbers() gegeben ist durch:
static IEnumerable NatNumbers()
{
int n = 1;
while (true)
{
yield return n;
n++;
}
}
Die yield Anweisung zeigt dem Compiler an, dass sich die Methode in einem Iteratorblock befindet. Zusammen mit dem return wird yield verwendet, um das Enumeratorobjekt bereitzustellen MSDN. Die while-Schleife wiederum wird ewig weiterlaufen.
Anzeige des Streams
Um sich jetzt den ersten Teil des Streams anzuzeigen wird die folgende Funktion benutzt:
static IEnumerable GetStreamPart(IEnumerable stream, int number)
{
int cnt = 0;
IEnumerator ie = stream.GetEnumerator();
while (ie.MoveNext() && cnt < number)
{
yield return ie.Current;
cnt++;
}
}
Die Funktion nimmt einen Stream und die Anzahl der anzuzeigenden Elemente und liefert einen Stream zurück. Dieser ist allerdings endlich. In einer alternativen Implementierung könnten die Elemente auch direkt ausgegeben werden. Das Durchiterieren des endlichen Streams entfällt dann.
Die Ausgabe der ersten 4 Elemente wird durch
foreach (var v in GetStreamPart(natNumbers, 4))
Console.WriteLine(v);
realisiert und lautet: 1 2 3 4
Abbildung eines Streams auf einen anderen
Auch ist es vorstellbar, dass wenn eine Funkion gegeben ist, die Folgen auf die Funktionswerte abgebildet werden können. Diese Abbildung wird mit der Funktion StreamMap() realisiert. StreamMap() nimmt einen Stream und eine Abbildungsfunktion mapFunction und liefert einen Stream.
static IEnumerable StreamMap<T, R>(IEnumerable stream, Func<T, R> mapFunction)
{
foreach (var v in stream) // alternativ var -> object
{
yield return mapFunction((T)v);
}
}
Die geraden Zahlen lassen sich Beispielsweise durch die Verwendung von StreamMap und der Funktion evenF erzeugen. ShowStream wird verwendet um die ersten 4 Element aus dem Stream anzuzeigen. Die Ausgabe lautet: 2 4 6 8
Func<int, int> evenF = x => 2 * x; ShowStream(StreamMap(natNumbers, evenF), 4);
Operationen auf Streams
Neben der eben betrachteten Abbildung von Streams ist es auch denkbar, dass Streams direkt verknüpft werden. Diese Aufgabe wird von der Funktion StreamCombine gelöst. Als Eingabe dienen zwei Streams deren Elemente mit einer Verknüpfungsfunktion combineFunction zusammen geführt werden. Die Ausgabe ist wieder ein Stream.
static IEnumerable StreamCombine<TA, TB, R>(IEnumerable streamA, IEnumerable streamB, Func<TA, TB, R> combineFunction)
{
IEnumerator ie = streamA.GetEnumerator();
IEnumerator ie2 = streamB.GetEnumerator();
while (ie.MoveNext() && ie2.MoveNext())
{
yield return combineFunction((TA)ie.Current, (TB)ie2.Current);
}
}
In dem folgenden Beispiel wird der Stream der natürlichen Zahlen mit dem Stream der Quadratzahlen addiert. StreamMap mit den natürlichen Zahlen und der Abbildungsfunktion squareF bilden den Stream der Quadratzahlen. Die Funktion StreamCombine vereint die beiden Streams, in dem eine elementweise Addition durchgeführt wird. Das Ergebnis für die ersten 4 Elemente lautet: 2 6 12 20
Func<int, int> squareF = x => x * x; Func<int, int, int> addC = (x, y) => x + y; IEnumerable combine = StreamCombine(natNumbers, StreamMap(natNumbers, squareF), addC);
