Stern Tree - Broko

Stern-Brokawův strom je způsob, jak uspořádat všechny nezáporné ireducibilní zlomky ve vrcholech uspořádaného nekonečného binárního stromu .

V každém uzlu Stern-Brockova stromu (někdy také nazývaného Fareyho strom ) je medián zlomků a , stojící v levém a pravém horním uzlu nejblíže k tomuto uzlu. Počáteční kus stromu Stern-Broco v tomto případě vypadá takto: ${\frac {m+m'}{n+n'))$ ${\frac {m}{n}}$ ${\frac {m'}{n'}}$

Konstrukčně blízký stromu Stern-Brocko je Calkin-Wilfův strom , ve kterém je zlomek kořenem a všechny ostatní uzly jsou vyplněny podle následujícího algoritmu: každý vrchol má dva potomky: left a right . ${\frac {1}{1))$ ${\frac {m}{n}}$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Historie

V knize Concrete Mathematics od R. Grahama , D. Knutha , O. Patashnika je objev „stromu Stern-Broko“ spojován se jmény Moritze Sterna (1858) a Achilla Broka (1860). Podobnou konstrukci v podobě „Calkin-Wilphova stromu“ však znali i starověcí řečtí matematici. Je popsána pod názvem „vytváření všech vztahů ze vztahu rovnosti jako od matky a kořene“ ve dvou matematických průzkumech 2. století. n. e. patřící Nikomachovi z Geras a Theonovi ze Smyrny . Theon uvádí, že tento design znal Eratosthenes z Kyrény , slavný vědec, který žil ve 3. století před naším letopočtem. před naším letopočtem E.

Vlastnosti

Všechny frakce ve stromech Culkin-Wilf a Stern-Brokaw jsou neredukovatelné.
Každý neredukovatelný zlomek se ve stromu objeví právě jednou.

U Culkin-Wilfova stromu lze tyto vlastnosti snadno prokázat poznámkou, že každý krok ve stromu směrem ke kořeni odpovídá elementárnímu kroku odečtení menšího čísla od většího v Euklidově algoritmu, abychom našli největšího společného dělitele.

Pro Stern-Brockův strom je důkaz založen na následujícím lemmatu: jestliže jsou zlomky ve dvou sousedních uzlech stromu, pak . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Stern-Broko číselný systém

K identifikaci levé a pravé větve můžete použít symboly L a R , když se pohybujete po stromu od kořene, zlomku 1/1, k nějakému konkrétnímu zlomku. Potom každý kladný zlomek dostane jedinečnou reprezentaci ve formě řetězce sestávajícího ze znaků " R " a " L " ( zlomek 1/1 odpovídá prázdnému řetězci ). Takové reprezentaci kladných racionálních čísel budeme říkat Sternův-Brokův číselný systém . Například zápis LRRL odpovídá zlomku 5/7.

Viz také

Literatura

Aigner M. , Ziegler G. Důkazy z knihy. Nejlepší důkaz od doby Euklida až po současnost . - M .: Mir, 2006. - S. 105 -109. — 256 s. — ISBN 5-03-003690-3 . .
Graham R., Knut D., Patashnik O. Concrete Mathematics. Základy informatiky. — M .: Mir, 1998. — 704 s. — ISBN 5-03-001793-3 . .
Shchetnikov AI Algoritmus pro rozvinutí všech numerických vztahů ze vztahu rovnosti a Platónových ideálních čísel // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .
Brocot A. Calcul des rouages par aproximace, nouvelle methode // Revue Chonométrique. - 1861. - T. 3 . - S. 186-194 .
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .

Odkazy

The Stern - Brocot nebo Farey Tree
Knop K. Nebinární systém // Domácí počítač. - 2001. - č. 8 . Archivováno z originálu 12. března 2007.
Online demonstrátor pro aproximaci racionálních čísel pomocí Sternova stromu - Brokaw