Stern – Brocotův strom - Stern–Brocot tree

Strom Stern – Brocot a sekvence Stern – Brocot řádu i pro i = 1, 2, 3, 4.

v teorie čísel, Stern – Brocotův strom je nekonečný kompletní binární soubor strom ve kterém vrcholy korespondovat jeden za jednoho do pozitivní racionální čísla, jehož hodnoty jsou seřazeny zleva doprava jako v a vyhledávací strom.

Strom Stern – Brocot objevil nezávisle na sobě Moritz Stern  (1858 ) a Achille Brocot  (1861 ). Stern byl německý teoretik čísel; Brocot byl Francouz hodinář který použil Stern – Brocotův strom k návrhu systémů ozubených kol s a převodový poměr blízko nějaké požadované hodnotě nalezení poměru plynulá čísla blízko této hodnoty.

Kořen stromu Stern – Brocot odpovídá číslu 1. Vztah rodič-dítě mezi čísly ve stromu Stern – Brocot lze definovat z hlediska pokračující zlomky nebo medianty a cestu ve stromu od kořene po jakékoli jiné číslo q poskytuje posloupnost aproximace na q s menšími jmenovatelé než q. Protože strom obsahuje každé kladné racionální číslo přesně jednou, a šířka první vyhledávání of the tree provides a method of listing all positive rationals that is close related Farey sekvence.

Strom pokračujících zlomků

Každé kladné racionální číslo q lze vyjádřit jako pokračující zlomek formy

${ displaystyle q = a_ {0} + { cfrac {1} {a_ {1} + { cfrac {1} {a_ {2} + { cfrac {1} {a_ {3} + { cfrac { 1} { ddots + { cfrac {1} {a_ {k}}}}}}}}}}} = [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k }]}$

kde k a A₀ jsou nezáporná celá čísla a každý následující koeficient A_i je kladné celé číslo. Toto znázornění není jedinečné, protože jeden má

${ displaystyle [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k-1}, 1] = [a_ {0}; a_ {1}, a_ {2}, ldots , a_ {k-1} +1]}$

pro každou posloupnost koeficientů A₀, ..., A_k−1Použitím této identity k přepsání jakéhokoli vyjádření původní formy do druhé lze získat, aby konečný koeficient splňoval A_k ≥ 2 (pokud k = 0, v takovém případě jeden získá A₀ ≥ 1); s tímto dalším požadavkem se reprezentace stává jedinečnou. Pak, pokud q = 1, číslo q má ve stromě Stern – Brocot nadřazený prvek daný pokračujícím zlomkovým výrazem

${ displaystyle [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k} -1],}$

což v případě A_k = 2 lze přepsat jako ${ displaystyle [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k-1} +1]}$Například racionální číslo²³⁄₁₆ má pokračující zlomkové zastoupení

${ displaystyle { frac {23} {16}} = 1 + { cfrac {1} {2 + { cfrac {1} {3 + { frac {1} {2}}}}}}} [ 1; 2,3,2],}$

takže jeho rodič ve stromu Stern – Brocot je číslo

${ displaystyle [1; 2,3,1] = [1; 2,4] = 1 + { cfrac {1} {2 + { frac {1} {4}}}} = { frac {13 } {9}}.}$

Tento nadřazený prvek je vytvořen snížením jmenovatele v nejvnitřnějším členu pokračujícího zlomku o 1 a smrštěním s předchozím členem, pokud se zlomek stane ${ displaystyle { tfrac {1} {1}}}$.

Naopak každé číslo q ve stromu Stern – Brocot má přesně dvě děti: pokud

${ displaystyle q = [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k}] = [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k} -1,1]}$

pak jedno dítě je číslo představované pokračujícím zlomkem

${ displaystyle displaystyle [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k} +1]}$

zatímco druhé dítě je reprezentováno pokračujícím zlomkem

${ displaystyle [a_ {0}; a_ {1}, a_ {2}, ldots, a_ {k} -1,2].}$

Jedno z těchto dětí je méně než q a toto je levé dítě; druhý je větší než q a je to pravé dítě (ve skutečnosti původní výraz dává levému dítěti, pokud k je liché a správné dítě, pokud k je sudé). Například pokračující zlomkové zastoupení¹³⁄₉ je [1; 2,4] a její dvě děti jsou [1; 2,5] =¹⁶⁄₁₁ (pravé dítě) a [1; 2,3,2] =²³⁄₁₆ (levé dítě).

Je zřejmé, že pro každý konečný zlomkový výraz lze opakovaně přejít na jeho rodiče a dosáhnout kořene [1;] =¹⁄₁ stromu v konečně mnoha krocích (v A₀ + ... + A_k − 1 přesné kroky). Každé kladné racionální číslo se proto v tomto stromu objeví právě jednou. Navíc všichni potomci levého dítěte libovolného počtu q jsou menší než qa všichni potomci pravého dítěte q jsou větší než q. Čísla v hloubce d ve stromu jsou čísla, pro která je součet koeficientů pokračujícího zlomku d + 1.

Medianty a binární vyhledávání

Strom Stern – Brocot tvoří nekonečno binární vyhledávací strom s ohledem na obvyklé řazení racionálních čísel.^[1][2] Sada racionálních čísel sestupujících z uzlu q je definován otevřeným intervalem (L_q,H_q) kde L_q je předchůdcem q to je menší než q a nejblíže tomu na stromě (nebo L_q = 0 pokud q nemá žádného menšího předka) H_q je předchůdcem q to je větší než q a nejblíže tomu na stromě (nebo H_q = + ∞ pokud q nemá většího předka).

Cesta od kořene 1 k číslu q na stromě Stern – Brocot lze najít a binární vyhledávání algoritmus, který lze vyjádřit jednoduchým způsobem pomocí medianty. Nezáporná racionální čísla rozšiřte o hodnotu 1/0 (představující + representing), která je ze své podstaty větší než všechny ostatní racionální hodnoty. The binární vyhledávací algoritmus postupuje takto:

• Inicializujte dvě hodnoty L a H na 0/1, respektive 1/0.
• Dokud q je nalezen, opakujte následující kroky:
  • Nechat L = A/b a H = C/d; spočítat mediant M = (A + C)/(b + d).
  • Li M je méně než q, pak q je v otevřeném intervalu (M,H); nahradit L podle M a pokračovat.
  • Li M je větší než q, pak q je v otevřeném intervalu (L,M); nahradit H podle M a pokračovat.
  • Ve zbývajícím případě q = M; ukončit vyhledávací algoritmus.

Posloupnost hodnot M vypočtené tímto hledáním je přesně posloupnost hodnot na cestě od kořene k q ve stromu Stern – Brocot. Každý otevřený interval (L,H) vyskytující se v určitém kroku vyhledávání je interval (L_M,H_M) představující potomky prostředníka M. Rodič q ve stromu Stern – Brocot je poslední nalezený prostředník, který se nerovná q.

Tento postup binárního vyhledávání lze použít k převodu plovoucí bod čísla do racionálních čísel. Zastavením, jakmile je dosaženo požadované přesnosti, lze čísla s plovoucí desetinnou čárkou aproximovat na libovolnou přesnost.^[3] Pokud skutečné číslo X je aproximováno jakýmkoli racionálním číslem A/b který není v posloupnosti mediánů nalezených výše uvedeným algoritmem, pak posloupnost mediánů obsahuje bližší přiblížení X který má jmenovatele maximálně roven b; v tomto smyslu tvoří tyto medianty nejlepší racionální aproximace na X.

Samotný strom Stern – Brocot lze definovat přímo z hlediska mediánů: levé dítě libovolného čísla q je prostředníkem q s nejbližším menším předkem a správným dítětem q je prostředníkem q s nejbližším větším předkem. V tomto vzorci q a jeho předchůdce musí být oba brány v nejnižších termínech, a pokud neexistuje žádný menší nebo větší předek, mělo by být použito 0/1 nebo 1/0. Jako příklad je třeba použít 7/5, jeho nejbližší menší předek je 4/3, takže jeho levé dítě je (4 + 7) / (3 + 5) = 11/8 a jeho nejbližší větší předek je 3/2, takže jeho pravé dítě je (7 + 3) / (5 + 2) = 10/7.

Vztah k Fareyovým sekvencím

The Farey sekvence řádu n je seřazená posloupnost zlomků v uzavřeném intervalu [0,1], které mají jmenovatele menší nebo rovný n. Stejně jako v binární vyhledávací technice pro generování Stern – Brocotova stromu lze Fareyovy sekvence konstruovat pomocí mediánů: Fareyova sekvence řádu n + 1 je vytvořeno z pořadí Farey pořadí n výpočtem mediant každé dvě po sobě jdoucí hodnoty v pořadí Farey pořadí n, udržující podmnožinu mediánů, které mají jmenovatele přesně rovny n + 1 a umístění těchto mediánů mezi dvě hodnoty, ze kterých byly vypočítány.

Podobný proces vložení média, počínaje odlišnou dvojicí koncových bodů intervalu [0 / 1,1 / 0], lze také popsat konstrukci vrcholů na každé úrovni stromu Stern – Brocot. The Stern – Brocotova sekvence objednávky 0 je sekvence [0 / 1,1 / 0] a Stern – Brocotova sekvence objednávky i je sekvence vytvořená vložením prostředku mezi každou po sobě jdoucí dvojici hodnot v pořadí Stern – Brocot pořadí i - 1. Stern – Brocotova posloupnost objednávky i se skládá ze všech hodnot na první i úrovně stromu Stern – Brocot společně s hraničními hodnotami 0/1 a 1/0 v číselném pořadí.

Sekvence Stern – Brocot se tedy liší od sekvencí Farey dvěma způsoby: nakonec zahrnují všechny pozitivní racionály, nejen racionály v intervalu [0,1], a na nv tomto kroku jsou zahrnuty všechny mediány, nejen ty, které mají stejného jmenovatele n. Fareyova sekvence řádu n lze najít inorderovým procházením levého podstromu stromu Stern – Brocot, zpětným sledováním vždy, když je číslo s jmenovatelem větším než n je dosaženo.

Další vlastnosti

Li ${ displaystyle {{ frac {p_ {1}} {q_ {1}}}, { frac {p_ {2}} {q_ {2}}}, dots, { frac {p_ {n}} {q_ {n}}}}}$ jsou tedy všechny racionály ve stejné hloubce ve stromu Stern – Brocot

${ displaystyle sum _ {k = 1} ^ {n} { frac {1} {p_ {k} q_ {k}}} = 1}$.

Navíc pokud ${ displaystyle {{ frac {p} {q}} <{ frac {p '} {q'}}}}$ jsou dva po sobě jdoucí zlomky na nebo nad určitou úrovní ve stromu (v tom smyslu, že jakýkoli zlomek mezi nimi musí být na nižší úrovni stromu), pak

${ displaystyle p'q-pq '= 1}$.^[4]

Spolu s výše popsanými definicemi ve smyslu pokračujících zlomků a mediánů lze strom Stern – Brocot definovat také jako Kartézský strom pro racionální čísla upřednostňovaná jejich jmenovateli. Jinými slovy je to jedinečný binární vyhledávací strom racionálních čísel, ve kterém je rodič jakéhokoli vrcholu q má menší jmenovatel než q (nebo když q a jeho rodič jsou obě celá čísla, ve kterých je rodič menší než q). Z teorie karteziánských stromů vyplývá, že nejnižší společný předek libovolných dvou čísel q a r ve stromu Stern – Brocot je racionální číslo v uzavřeném intervalu [q, r], který má nejmenší jmenovatel ze všech čísel v tomto intervalu.

Prostupující vrcholy na každé úrovni Stern – Brocotova stromu o a bit-reverzní permutace produkuje jiný strom, Calkin – Wilfův strom, ve kterém jsou děti každého čísla A/b jsou dvě čísla A/(A + b) a (A + b)/b. Stejně jako strom Stern – Brocot obsahuje strom Calkin – Wilf každé kladné racionální číslo přesně jednou, ale nejedná se o binární vyhledávací strom.

Viz také

• Funkce Minkowského otazníku, jehož definice racionálních argumentů úzce souvisí se stromem Stern – Brocot
• Calkin – Wilfův strom

Poznámky

Reference

• Brocot, Achille (1861), „Calcul des rouages ​​par aproximace, nouvelle méthode“, Revue Chronométrique, 3: 186–194.
• Stern, Moritz A. (1858), „Ueber eine zahlentheoretische Funktion“, Journal für die reine und angewandte Mathematik, 55: 193–220.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Kombinatorika slov. Christoffel slova a opakování slovSérie monografií CRM, 27, Providence, RI: Americká matematická společnost, ISBN  978-0-8218-4480-9, Zbl  1161.68043

externí odkazy

• Aiylam, Dhroova, Modifikované Stern-Brocotovy sekvence, arXiv:1301.6807, Bibcode:2013arXiv1301.6807A
• Austin, David, Stromy, zuby a čas: Matematika výroby hodin Sloupec funkcí z AMS
• Bogomolny, Alexander, Stern brocot-strom, cut-the-uzel, vyvoláno 2008-09-03.
• Sloane, N. J. A., Stern – Brocot nebo Farey Tree, On-line encyklopedie celočíselných sekvencí.
• Wildberger, Norman, MF96: Frakce a Stern-Brocotův strom.
• Weisstein, Eric W. „Stern – Brocot Tree“. MathWorld.
• Stern – Brocotův strom na PlanetMath.org.
• Nekonečné zlomky, Numberphile