Cantorsche Paarungsfunktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo! Bitte diesen Artikel nicht lesen!
Die von mir angegebene Lösung aus dem Skript ist falsch und für eine andere Nummerierung!
VG,
NIK
| Aufgabe | Es sei [mm] \summe :={a_1,a_2,a_3}.
[/mm]
Bestimmen Sie v(500) für die Nummerierung:
[mm] v_{C}_{k}: \IN \to \IN^{3}, v_{C}_k:=(\pi^{(k)})^{-1} [/mm] (siehe Satz 5.2.2)(die Cantorsche Nummerierung von [mm] \IN^{k} [/mm] |
Hallo!
Bei dieser Selbsttest Aufgabe komme ich einfach nicht auf den richtigen Lösungsweg.
Satz 5.2.2:
Für jedes [mm] k\ge1 [/mm] gelten die folgenden Eigentschaften:
1. [mm] \pi^{(k)} [/mm] ist bijektiv
[mm] 2.\pi^{(k)} [/mm] ist berechenbar.
3. [mm] \pi_i^{k} [/mm] := [mm] pr_i^{(k)} (\pi^{(k)})^{-1} [/mm] ist berechenbar für jedes i mit 1 [mm] \ge i\ge [/mm] k.
Kurzschreibweisen: [mm] \pi_1:=\pi_1^{(2)}, \pi_2:= pi_2^{(2)}
[/mm]
Offenbar lässt sich die Aufgabe recht einfach mit der Cantorschen Paarungsfunktion und dem Satz 5.2.2 Lösen.
Das Ergebnis ist:
[mm] 500=1*3^{5}+2*3^{4}+3*3^{3}+1*3^{2}+1*3^{1}+2*3^{0}
[/mm]
also [mm] v_\summe(500)=a_1a_2a_3a_1a_1a_2.
[/mm]
Ich verstehe nicht wie ich zu dieser Lösung komme. D.h mir ist der Lösungsweg überhaupt nicht klar.
Kann mir ielleicht jemand mal erklären wie ich zu dieser Lösung komme???
Offensichtlich kann ich nicht wirklich mit der Cantorschen Paarungsfunktion umgehen, denn auch nach 3h probieren bin ich noch nicht zur gewünschten Lösung gekommen :-(.
Danke für Eure Hilfe,
LG,
NIK
|
|
| |
|
Hallo Nicole,
sorry, dass ich mich jetzt erst melde. Also irgendwie scheint mir deine Frage zwei Sachen
zu enthalten:
Zum einen etwas dazu, wie man zu einem endlichen Alphabet [mm] \Sigma [/mm] eine bijektive Abbildung
[mm] v\colon \IN\to\Sigma^* [/mm] konstruiert, naemlich indem man jede natuerliche Zahl
n schreibt als [mm] n=\sum_{j=0}^m a_{i_j}3^j [/mm] (diese Darst. ist eindeutig) und dann
v(n)= [mm] a_{i_m}a_{i_{m-1}}\ldots a_{i_0} [/mm] setzt.
Zum anderen kommt etwas vor von den Funktionen [mm] \IN\to\IN^k [/mm] und den Projektionen
in die andere Richtung, und da wird sicherlich der Begriff Cantor'sche Numerierung
richtig sein. Die Definition dieser koenntest Du vielleicht nochmal geben, das
waere hilfreich.
Vielleicht handelt die Aufgabe ja auch von der Hintereinanderschaltung von
einer Abb. [mm] \Sigma^*\to\IN [/mm] und dem Inversen [mm] \IN\to\IN^3 [/mm] der Cantor'schen Funktion
von [mm] \IN^3 [/mm] nach [mm] \IN, [/mm] aber dann wuerd ich nicht verstehen, was das Argument 500 soll.
500 ist zum einen Bild unter der Cantor'schen Funktion von [mm] \IN^3 [/mm] nach [mm] \IN
[/mm]
eines Tripels [mm] (n_1,n_2,n_3), [/mm] das Du bestimmen koenntest.
Zum anderen ist es Bild eines Strings aus [mm] \Sigma^*, [/mm] wobei [mm] \Sigma=\{a_1,a_2,a_3\}
[/mm]
ist, und diesen String hast Du, denk ich, richtig bestimmt.
Schreib ruhig nochmal, ich werd mir das dann relativ schnell anschauen.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:06 Mi 11.01.2006 | | Autor: | Flugzwerg |
Halli Hallo!
Also Für M als höchstens abzählbare Menge wollen wir die Elemente durch Zahlen "benennen" oder "verschlüsseln". Es soll dabei jedes Element [mm] x\in [/mm] M
mindestens einen Namen enthalten. keine Zahl i [mm] \in \IN [/mm] darf Name von zwei oder mehr Elementen sein. (Ich nehme an das i dann sowas wie Index ist, und ich mit i nach der verschlüsselung dann direkt ein Element der Menge ansprechen kann?)
Dies führt zur Definition der Nummerierung :
Def. Nummerierung
Eine Nummerierung einer Menge M ist eine (möglicherweise partielle) surjektive Funktion [mm] v:\subseteq \IN \to [/mm] M
Wenn v(i) =x gilt, sagt man auch das i eine v -Nummer von x ist.
Eine v-Nummerierung muss nicht injektiv sein, auch nicht total.
Dann haben wir eine Definition von Standardnummerierungen, aus der auch die Standardnummerierung stammt zu der ich v(500) bestimmen soll.
(Ist i hier i=500? also ich habe 500 Elemente in M ????)
Es gibt ja auch die Standardnummerierung phi usw. (phi ist glaube ich diese Gödelnummerierung.)
Jetzt muss man irgendwie auf [mm] 500=1*3^{5}+2*^{4}..... [/mm] kommen.
Die def des Satzes habe ich ja oben schon becshrieben.
Hier noch die definition von der Cantorschen Tupelfunktion:
1. Die Cantorsche Tupelfunktion [mm] \pi:\IN^{2}\to\IN [/mm] sei definiert durch
[mm] \pi(x,y):=\summe_{i=0}^{x+y} i+y=\bruch{1}{2}(x+y)(x+y+1)+y
[/mm]
für alle [mm] x,y\in \IN
[/mm]
2. Für k=1,2,3,... seien [mm] \pi^{k}:\IN^{k}\to\IN [/mm] induktiv wie folgt definiert:
[mm] \pi^{(1)}(x):=x
[/mm]
[mm] \pi^{n+1}(x_1,...,x_{n+1}:=\pi(\pi^{(n)}(x_1,...,x_n),x_(n+1)
[/mm]
für alle [mm] n,x,x_1,...,x_{n+1} \in \IN [/mm] mit n [mm] \ge1
[/mm]
Schreibweise: [mm] :=\pi^{(n)}(x_1,...,x_n)
[/mm]
Die Funktionen [mm] \pi^{(k)} [/mm] heissen Cantorsche Tupelfunktionen.
Insbesondere gilt [mm] \pi^{(2)}=\pi. [/mm] Die CT.Fkt sind bijektiv und berechenbar. Auch die Inversen sind berechenbar.
Dieser Definition folgt dann der Satz den ich in der Frage geschrieben habe.
Ich verstehe einfach nicht wie ich auf die Formel komme.
Was sind denn diese Multiplikatoren 1,2,3,1,1,2 ?
Da steht ja auch [mm] a_1,a_2,a_3,a_1,a_1,a_2. [/mm] das scheinen ja die multiplikatoren zu sein? Wie komme ich denn darauf?
Und wo kommen meine Potenzen her? wie komme ich auf [mm] 3^5,3^4, [/mm] etc?
Die drei ist mein k oder?
Aber in welche Funktion oder was auch immer haben die das eingesetzt?
Puh. Da hab ich noch mehr von ( von den Nummerierungen für die ich v(500) bestimmen muss.
Wenn ich diese hier verstanden habe komme ich hoffentlich mit denen auch weiter!!!
Danke für Deine Hilfe!!!
LG,
NIK
|
|
|
| |
|
Hallo Nicole,
hab mir gerade Netscape zerschossen und musst mich neu einloggen, also nochmal von
vorne:
Also nehmen wir mal an, Du sollst [mm] {\pi^{3}}^{-1}(500) [/mm] berechnen.
Bemerkung: Dann versteh ich nicht, was dann das [mm] \Sigma [/mm] ueberhaupt soll. Koennt es nicht
auch sein, dass in Eurem Skript ein Dreher drin ist ?
Jedenfalls: Versuchen wir mal, mit der Cantor-Funktion weiterzumachen.
Um Inverse unter einer Funktion [mm] \pi^{(k)} [/mm] zu berechnen, reicht es ja voellig, Inverse unter
[mm] \pi [/mm] berechnen zu koennen und dies dann mehrfach anzuwenden.
In deinem Beispiel:
Wir suchen ja laut definition der Funktion [mm] \pi^{(3)} [/mm] Zahlen a,b,c mit [mm] \pi^{(3)}(a,b,c)=500,
[/mm]
also zunaechst Zahlen d und c mit
[mm] \pi(d,c)=500, [/mm] und dann nochmal Zahlen a,b mit [mm] \pi(a,b)=d.
[/mm]
Nach def suchen wir d,c so, dass
[mm] \frac{1}{2}\cdot (d+c)\cdot [/mm] (c+d+1) + c =500 gilt.
Hierfuer mag es tolle elegante Ansaetze geben oder explizite Formeln
, die ich momentan aber nicht weiss.
Also: probieren ! Multiplizieren wir mit 2, so haben wir
(d+c)(d+c+1) +2c = 1000, und (d+c)(d+c+1) ist ja ''fast'' eine Quadratzahl.
Es ist [mm] \sqrt{1000} \leq [/mm] 32, also schauen wir, was c+d=30 als erster Ansatz liefert:
[mm] 30\cdot [/mm] 31=930, dann muesst 2c=1000-930=70, geht nicht, also muessen wir 2y kleiner
kriegen: [mm] 31\cdot [/mm] 32 = 992, dann waere 2c=1000-992=8, also c=4 und
31=c+d also d= 28.
Klappt.
Weiter: d zerlegen !
d= [mm] \frac{1}{2}\cdot [/mm] (a+b)(a+b+1) +b = 28.
Probier mal, ich hab jetzt nen Termin, sonst frag nochmal nach - ruhig privat, das muss,
glaub ich, nicht unbedingt dann noch ins Forum.
Gruss,
Mathias
|
|
|
|
