Abbildung N x N -> N < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:40 Do 06.11.2008 | | Autor: | fin129 |
| Aufgabe | Geben Sie eine (algorithmisch effiziente) Bijektion f: [mm] \IN \times \IN \to \IN [/mm] an.
Warum ist die von Ihnen angegebene Abbildung bijektiv? Wie berechnet man algorithmisch die Urbilder [mm] f^{-1}(z) [/mm] für beliebige z [mm] \in \IN. [/mm] |
Mir ist klar, was eine bijektive Abbildung ist und auch, wie man Bijektivität zeigt, aber ich komme auf keine Abbildung die oben genanntes leistet.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:17 Do 06.11.2008 | | Autor: | koepper |
Hallo fin,
ordne die Elemente von [mm] $\IN \times \IN$ [/mm] in einer Tabelle an und durchlaufe diese mit parallelen Diagonalen. Damit werden alle Tabelleneinträge irgendwann erreicht und jeder Eintrag wird abgebildet auf die Position in der Reihenfolge des Durchlaufs.
Schaue auch mal im Internet nach "Abzählbarkeit von [mm] $\IQ$". [/mm] Dort findest du die selbe Idee.
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:45 Do 06.11.2008 | | Autor: | fin129 |
Hm, ich glaube das Verfahren habe ich schon mal beim Beweis der Abzählbarkeit der natürlichen Zahlen gesehen, danke für die Antwort, aber ist das algorithmisch effizient umzusetzen?
Mir fiele dazu nur eine "Simulationslösung" ein, bei der der Wert von f(x,y) durch "Durchlaufen und Mitzählen" gefunden wird.
Ich kenne keine explizite Formel f(x,y), die (x,y) ihren Platz in der Folge der derart angeordneten Elemente durch Berechnung und nicht durch Simulation zuweist, bzw. [mm] f^{-1}, [/mm] welche das ganze wieder umkehrt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:15 Do 06.11.2008 | | Autor: | koepper |
Hallo,
> Hm, ich glaube das Verfahren habe ich schon mal beim Beweis
> der Abzählbarkeit der natürlichen Zahlen gesehen, danke für
du meinst sicher die rationalen Zahlen, denn die natürlichen sind per Definition abzählbar (die Identität ist trivialerweise bijektiv)
> die Antwort, aber ist das algorithmisch effizient
> umzusetzen?
ja.
> Mir fiele dazu nur eine "Simulationslösung" ein, bei der
> der Wert von f(x,y) durch "Durchlaufen und Mitzählen"
> gefunden wird.
Betrachte einmal die Längen der "Diagonalen".
Wie findet man zu einem natürlichen Zahlenpaar heraus, auf der wievielten Diagonale es sich befindet? (ganz einfach!)
Um jetzt die Position zu errechnen müssen nur noch die Längen der davor liegenden Diagonalen addiert werden und dann die Position des Paars auf der aktuellen Diagonale dazu. Das geht am einfachsten wenn man die Diagonalen immer von links unten nach rechts oben (oder umgekehrt) durchläuft. Probiers mal aus 
LG
Will
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:00 Fr 07.11.2008 | | Autor: | fin129 |
Bitte mal Korrekturlesen:
Annahme: 0 ist keine natürliche Zahl und folgende Verteilung der Zahlen auf den Diagonalen (Ausschnitt):
[mm] \vmat{ 6 & 9 & 13 \\ 3 & 5 & 8 \\ 1 & 2 & 4 }
[/mm]
Also zähle ich immer von rechts unten nach links oben. Die Länge der Diagonalen nimmt in jeder Stufe um eins zu. Die erste Diagonale [mm] D_1 [/mm] sei diejenige mit nur einem Element, nämlich (1,1) -> 1.
In dieser Denkweise ist die Nummer der Diagonale immer 1 weniger als die Summe x+y eines beliebigen elements (x,y) auf ihr.
Um beliebige Positionsnummern herauszufinden, müssen also die Längen der vorhergehenden Diagonalen aufsummiert werden und dazu noch die Position des elements auf der aktuellen Diag, diese entspricht genau y.
Ich komme auf:
[mm]
\summe_{i=1}^{x+y-2} (i) +y
= \frac{(x+y-2)(x+y-1)}{2} +y
= \frac{1}{2}(x^2+y^2+2xy-3x-3y+2)+y
[/mm]
Danke.
Ich hab mal versucht, die Umkehrfunktion durch Umstellen nach x bzw. y zu bilden, schaff's aber nicht. Eigentlich müsste sie existieren, denn die Abbildung ist ja umkehrbar eindeutig.
Meine andere Idee, anhand von z die Nummer der Diagonale, auf der z liegt zu ermitteln, dann wäre
y gleich der anzahl der zuvor kommenden elemente von "unten rechts" + 1 sowie
x entsprechend die differenz zwischen (Nummer der Diagonale + 1) und y.
Dabei fällt mir aber nix ein, wie ich auf die Nummer der Diagonale komme ohne von 1 an alle zu berechnen und elemente hochzuzählen, bis der zähler über z liegt, was allerdings nicht algorithmisch effizient ist.
Mir ist gerade noch eingefallen, man könnte auch die jeweils kleinsten und größten Elemente der Diagonalen als zwei Zahlenfolgen auffassen, beide hochlaufen lassen und berechnen, bis der gegebene Wert dazwischen liegt. Ich komme da auf:
[mm]
unten(1)=1
unten(n+1)=unten_n + n
oben(1)=1
oben(n+1)=oben_n + (n-1)
[/mm]
Das wäre allerdings auch nicht wirklich effizient, glaub ich.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Di 11.11.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> Geben Sie eine (algorithmisch effiziente) Bijektion f: [mm]\IN \times \IN \to \IN[/mm] an.
> Warum ist die von Ihnen angegebene Abbildung bijektiv? Wie
> berechnet man algorithmisch die Urbilder [mm]f^{-1}(z)[/mm] für
> beliebige z [mm]\in \IN.[/mm]
hallo fin,
wir hatten hier gerade vor ein paar Tagen eine Diskussion um
eine derartige Abbildung. Schau dir dies mal an: f: NxN --> N
Dies könnte insbesondere für eine Implementation im
Binärsystem sehr gut passen.
LG
|
|
|
|
