Stern Tree - Broko

Arborele Stern-Brokaw este o modalitate de a aranja toate fracțiile ireductibile nenegative la vârfurile unui arbore binar infinit ordonat .

La fiecare nod al arborelui Stern-Brocko (uneori numit și arborele Farey ), există o mediană a fracțiilor și , stând în nodurile superioare stânga și dreapta cele mai apropiate de acest nod. Piesa inițială a arborelui Stern-Broco în acest caz arată astfel: ${\frac {m+m'}{n+n'))$ ${\frac {m}{n}}$ ${\frac {m'}{n'}}$

Aproape în construcție de arborele Stern-Brocko este arborele Calkin-Wilf , în care fracția este rădăcina, iar toate celelalte noduri sunt umplute conform următorului algoritm: fiecare vârf are doi descendenți: stânga și dreapta . ${\frac {1}{1))$ ${\frac {m}{n}}$ ${\frac {m}{m+n)}$ ${\frac {m+n}{n})$

Istorie

În cartea Concrete Mathematics de R. Graham , D. Knuth , O. Patashnik , descoperirea „arborelui Stern-Broko” este asociată cu numele lui Moritz Stern (1858) și Achilles Broko (1860). Cu toate acestea, o construcție similară sub forma unui „arbore Calkin-Wilph” era cunoscută chiar și de matematicienii greci antici. Este descrisă sub numele de „generarea tuturor relațiilor din relația de egalitate ca de la mamă și rădăcină” în două studii matematice din secolul al II-lea. n. e., aparținând lui Nicomachus din Gheras și Theon din Smirna . Theon relatează că acest design era cunoscut lui Eratosthenes din Cirene , un om de știință celebru care a trăit în secolul al III-lea î.Hr. î.Hr e.

Proprietăți

Toate fracțiile din arborii Culkin-Wilf și Stern-Brokaw sunt ireductibile.
Fiecare fracție ireductibilă apare exact o dată în arbore.

Pentru un arbore Culkin-Wilf, aceste proprietăți sunt ușor dovedite prin observând că fiecare pas din arbore spre rădăcină corespunde unui pas elementar de scădere a unui număr mai mic de la unul mai mare în algoritmul lui Euclid pentru a găsi cel mai mare divizor comun.

Pentru arborele Stern-Brocko, demonstrația se bazează pe următoarea lemă: dacă sunt fracții la două noduri vecine ale arborelui, atunci . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

Sistemul numeric Stern-Broko

Puteți folosi simbolurile L și R pentru a identifica ramurile din stânga și din dreapta pe măsură ce vă deplasați în jos în copac de la rădăcină, fracția 1/1, la o anumită fracție. Apoi fiecare fracție pozitivă primește o reprezentare unică sub forma unui șir format din caracterele „ R ” și „ L ” ( fracția 1/1 corespunde unui șir gol ). Vom numi o astfel de reprezentare a numerelor raționale pozitive sistemul numeric Stern-Broko . De exemplu, notația LRRL corespunde fracției 5/7.

Vezi și

Literatură

Aigner M. , Ziegler G. Dovezi din carte. Cele mai bune dovezi din vremea lui Euclid până în zilele noastre . - M . : Mir, 2006. - S. 105 -109. — 256 p. — ISBN 5-03-003690-3 . .
Graham R., Knut D., Patashnik O. Concrete Mathematics. Fundatia informaticii. — M .: Mir, 1998. — 704 p. — ISBN 5-03-001793-3 . .
Shchetnikov AI Algoritm pentru desfășurarea tuturor relațiilor numerice din relația de egalitate și numerele ideale ale lui Platon // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .
Brocot A. Calcul des rouages par approximation, nouvelle méthode // 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 .

Link -uri

The Stern - Brocot sau Farey Tree
Knop K. Sistem non-binar // Computer de acasă. - 2001. - Nr. 8 . Arhivat din original pe 12 martie 2007.
Demonstrator online pentru aproximarea numerelor raționale folosind arborele Stern - Brokaw