Funkce párování - Pairing function

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Funkce párování"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Srpna 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, a funkce párování je proces jedinečného kódování dvou přirozená čísla do jediného přirozeného čísla.

Lze použít libovolnou funkci párování teorie množin dokázat to celá čísla a racionální čísla mít stejné mohutnost jako přirozená čísla. v teoretická informatika používají se ke kódování funkce definované na vektoru přirozených čísel ${ displaystyle f: mathbb {N} ^ {k} rightarrow mathbb {N}}$ do nové funkce ${ displaystyle g: mathbb {N} rightarrow mathbb {N}}$.

Definice

A funkce párování je vypočítatelný bijekce

${ displaystyle pi: mathbb {N} krát mathbb {N} až mathbb {N}.}$

Funkce párování Cantor

Funkce párování Cantor přiřadí každé dvojici přirozených čísel jedno přirozené číslo

The Funkce párování Cantor je primitivní rekurzivní funkce párování

${ displaystyle pi: mathbb {N} krát mathbb {N} až mathbb {N}}$

definován

${ displaystyle pi (k_ {1}, k_ {2}): = { frac {1} {2}} (k_ {1} + k_ {2}) (k_ {1} + k_ {2} + 1) + k_ {2}.}$

Prohlášení, že se jedná o jedinou funkci kvadratického párování, se nazývá Věta Fueter – Pólya. Zda je to jediná polynomiální párovací funkce, je stále otevřená otázka. Když použijeme párovací funkci na k₁ a k₂ výsledné číslo často označujeme jako ⟨k₁, k₂⟩.

Tuto definici lze induktivně zobecnit na Funkce n-tice Cantor

${ displaystyle pi ^ {(n)}: mathbb {N} ^ {n} do mathbb {N}}$

pro ${ displaystyle n> 2}$ tak jako

${ displaystyle pi ^ {(n)} (k_ {1}, ldots, k_ {n-1}, k_ {n}): = pi ( pi ^ {(n-1)} (k_ { 1}, ldots, k_ {n-1}), k_ {n})}$

s výše definovaným základním případem pro pár: ${ displaystyle pi ^ {(2)} (k_ {1}, k_ {2}): = pi (k_ {1}, k_ {2}).}$

Invertování funkce párování Cantor

Nechat ${ displaystyle z in mathbb {N}}$ být libovolné přirozené číslo. Ukážeme, že existují jedinečné hodnoty ${ displaystyle x, y in mathbb {N}}$ takhle

${ displaystyle z = pi (x, y) = { frac {(x + y + 1) (x + y)} {2}} + y}$

a proto to π je invertibilní. Je užitečné definovat některé mezilehlé hodnoty ve výpočtu:

${ displaystyle w = x + y !}$

${ displaystyle t = { frac {1} {2}} w (w + 1) = { frac {w ^ {2} + w} {2}}}$

${ displaystyle z = t + y !}$

kde t je číslo trojúhelníku z w. Pokud vyřešíme kvadratická rovnice

${ displaystyle w ^ {2} + w-2t = 0 !}$

pro w jako funkce t, dostaneme

${ displaystyle w = { frac {{ sqrt {8t + 1}} - 1} {2}}}$

což je striktně rostoucí a nepřetržitá funkce, když t je nezáporné skutečné. Od té doby

${ displaystyle t leq z = t + y$

máme to

${ displaystyle w leq { frac {{ sqrt {8z + 1}} - 1} {2}}$

a tudíž

${ displaystyle w = left lfloor { frac {{ sqrt {8z + 1}} - 1} {2}} right rfloor.}$

kde ⌊ ⌋ je funkce podlahy Takže vypočítat X a y z z, my ano:

${ displaystyle w = left lfloor { frac {{ sqrt {8z + 1}} - 1} {2}} right rfloor}$

${ displaystyle t = { frac {w ^ {2} + w} {2}}}$

${ displaystyle y = z-t !}$

${ displaystyle x = w-y. !}$

Protože funkce párování Cantor je invertibilní, musí být jedna ku jedné a na.

Příklady

Vypočítat π(47, 32):

47 + 32 = 79,

79 + 1 = 80,

79 × 80 = 6320,

6320 ÷ 2 = 3160,

3160 + 32 = 3192,

tak π(47, 32) = 3192.

Najít X a y takhle π(X, y) = 1432:

8 × 1432 = 11456,

11456 + 1 = 11457,

√11457 = 107.037,

107.037 − 1 = 106.037,

106.037 ÷ 2 = 53.019,

⌊53.019⌋ = 53,

tak w = 53;

53 + 1 = 54,

53 × 54 = 2862,

2862 ÷ 2 = 1431,

tak t = 1431;

1432 − 1431 = 1,

tak y = 1;

53 − 1 = 52,

tak X = 52; tím pádem π(52, 1) = 1432.

Derivace

K prokázání spočitatelnosti racionálních čísel se často používá úhlopříčně se zvyšující „hadí“ funkce ze stejných principů jako Cantorova párovací funkce.

Grafický tvar Cantorovy párovací funkce, diagonální postup, je standardní trik při práci nekonečné sekvence a spočitatelnost.^{[poznámka 1]} Algebraická pravidla této funkce ve tvaru úhlopříčky mohou ověřit její platnost pro řadu polynomů, z nichž se kvadratický ukáže jako nejjednodušší, pomocí způsob indukce. Ve skutečnosti lze stejnou techniku ​​použít také k pokusu o odvození libovolného počtu dalších funkcí pro libovolnou paletu schémat výčtu roviny.

Funkci párování lze obvykle definovat indukčně - tedy vzhledem k nten pár, co to je (n+1)ten pár? Způsob, jakým Cantorova funkce postupuje diagonálně napříč rovinou, lze vyjádřit jako

${ displaystyle pi (x, y) + 1 = pi (x-1, y + 1)}$.

Funkce musí také definovat, co dělat, když narazí na hranice 1. kvadrantu - Cantorova párovací funkce se resetuje zpět na osu x, aby se obnovil její diagonální postup o krok dále, nebo algebraicky:

${ displaystyle pi (0, k) + 1 = pi (k + 1,0)}$.

Také musíme definovat výchozí bod, jaký bude počáteční krok v naší indukční metodě: π(0, 0) = 0.

Předpokládejme, že existuje kvadratický 2-dimenzionální polynom, který může vyhovovat těmto podmínkám (pokud by neexistoval, dalo by se opakovat pokusem o polynom vyššího stupně). Obecná forma je tedy

${ displaystyle pi (x, y) = ax ^ {2} + od ^ {2} + cxy + dx + ey + f}$.

Připojte naše počáteční a okrajové podmínky, abyste získali F = 0 a:

${ displaystyle bk ^ {2} + ek + 1 = a (k + 1) ^ {2} + d (k + 1)}$,

abychom mohli odpovídat našim k podmínky získat

b = A

d = 1-A

E = 1+A.

Takže každý parametr lze zapsat z hlediska A až na C, a máme konečnou rovnici, náš diagonální krok, který je bude souviset:

${ displaystyle { begin {zarovnáno} pi (x, y) + 1 & = a (x ^ {2} + y ^ {2}) + cxy + (1-a) x + (1 + a) y + 1 & = a ((x-1) ^ {2} + (y + 1) ^ {2}) + c (x-1) (y + 1) + (1-a) (x-1) + ( 1 + a) (y + 1). End {zarovnáno}}}$

Rozbalte a znovu spárujte podmínky, abyste získali pevné hodnoty A a C, a tedy všechny parametry:

A = 1/2 = b = d

C = 1

E = 3/2

F = 0.

Proto

${ displaystyle { begin {aligned} pi (x, y) & = { frac {1} {2}} (x ^ {2} + y ^ {2}) + xy + { frac {1} { 2}} x + { frac {3} {2}} y & = { frac {1} {2}} (x + y) (x + y + 1) + y, end {zarovnáno}} }$

je Cantorova párovací funkce, a také jsme prostřednictvím derivace prokázali, že toto splňuje všechny podmínky indukce.

Poznámky

externí odkazy

• Steven Pigeon. "Funkce párování". MathWorld.
• Elegantní funkce párování