Stern Tree - Broko

A Stern-Brokaw fa az összes nemnegatív irreducibilis tört elrendezésének módja egy rendezett végtelen bináris fa csúcsaiban .

A Stern-Brocko-fa (néha Farey-fának is nevezik) minden egyes csomópontján van a és a tört mediánja , amely a csomóponthoz legközelebb eső bal és jobb felső csomópontban áll. A Stern-Broco fa kezdeti darabja ebben az esetben így néz ki: ${\frac {m+m'}{n+n'))$ ${\frac {m}{n}}$ ${\frac {m'}{n'}}$

A Stern-Brocko fához közel áll a Calkin-Wilf fa , amelyben a tört a gyökér, és az összes többi csomópont a következő algoritmus szerint van kitöltve: minden csúcsnak két leszármazottja van: bal és jobb . ${\frac {1}{1))$ ${\frac {m}{n}}$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Történelem

R. Graham , D. Knuth , O. Patashnik Concrete Mathematics című könyvében a "Stern-Broko fa" felfedezése Moritz Stern (1858) és Achilles Broko (1860) nevéhez fűződik. Azonban egy hasonló konstrukciót a "Calkin-Wilph fa" formájában még az ókori görög matematikusok is ismertek. A 2. század két matematikai felmérésében „minden reláció létrehozása az egyenlőség viszonyából, mint az anya és a gyökér” néven írja le. n. e., amely Gerasi Nikomákhoszhoz és Szmirnai Theonhoz tartozik . Theon beszámol arról, hogy ezt a tervet a cirénei Eratoszthenész ismerte , egy híres tudós, aki a Kr.e. 3. században élt. időszámításunk előtt e.

Tulajdonságok

A Culkin-Wilf és Stern-Brokaw fák összes frakciója redukálhatatlan.
Minden irreducibilis tört pontosan egyszer jelenik meg a fában.

Egy Culkin-Wilf-fánál ezek a tulajdonságok könnyen bizonyíthatók, ha megjegyezzük, hogy a fában a gyökér felé vezető minden lépés egy elemi lépésnek felel meg, amikor az Euklidész algoritmusában egy kisebb számot kivonunk egy nagyobbból, hogy megtaláljuk a legnagyobb közös osztót.

A Stern-Brocko fa esetében a bizonyítás a következő lemmán alapul: ha a fa két szomszédos csomópontjában törtek vannak, akkor . $p_1/q_1<p_2/q_2$ $q_1p_2-q_2p_1=1$

A Stern-Broko számrendszer

Az L és R szimbólumok segítségével azonosíthatja a bal és jobb oldali ágakat, miközben a fán lefelé halad a gyökértől, az 1/1-es törttől egy bizonyos tört felé. Ezután minden pozitív tört egyedi megjelenítést kap egy karakterlánc formájában, amely " R " és " L " karakterekből áll ( az 1/1-es tört egy üres karakterláncnak felel meg ). A pozitív racionális számok ilyen ábrázolását Stern-Broko számrendszernek nevezzük . Például az LRRL jelölés az 5/7 törtnek felel meg.

Lásd még

Irodalom

Aigner M. , Ziegler G. Bizonyítékok a könyvből. A legjobb bizonyítékok Eukleidész korától napjainkig . - M . : Mir, 2006. - S. 105 -109. — 256 p. — ISBN 5-03-003690-3 . .
Graham R., Knut D., Patashnik O. Konkrét matematika. Az informatika megalapozása. — M .: Mir, 1998. — 704 p. — ISBN 5-03-001793-3 . .
Shchetnikov AI Algoritmus minden numerikus reláció kibontására az egyenlőségi relációból és Platón ideális számaiból // ΣΧΟΛΗ . - 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 .

Linkek

A Stern - Brocot vagy Farey Tree
Knop K. Nem bináris rendszer // Otthoni számítógép. - 2001. - 8. sz . Az eredetiből archiválva: 2007. március 12.
Online bemutató a racionális számok közelítéséhez a Stern fa segítségével - Brokaw