Pohon Stern–Brocot

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Loncat ke navigasi Loncat ke pencarian
The Stern–Brocot tree, and the Stern–Brocot sequences of order i for i = 1, 2, 3, 4.

Dalam teori bilangan, Pohon Stern-Brocot adalah pohon biner lengkap yang tak terbatas di mana simpul-simpulnya bersesuaian satu-satu dengan bilangan rasional positif, yang nilainya disusun dari kiri ke kanan seperti pada pohon pencarian.

Pohon Stern-Brocot ditemukan secara independen oleh Moritz Stern (1858) dan Achille Brocot (1861). Stern adalah ahli teori bilangan Jerman; Brocot adalah pembuat jam Prancis yang menggunakan pohon Stern-Brocot untuk merancang sistem roda gigi dengan rasio roda gigi mendekati nilai yang diinginkan dengan menemukan rasio angka halus di dekat nilai itu.

Akar pohon Stern-Brocot sesuai dengan angka 1. Hubungan orangtua-anak antara angka dalam pohon Stern-Brocot dapat didefinisikan dalam hal pecahan berlanjut, dan jalur di pohon dari akar ke akar lainnya angka q memberikan urutan perkiraan ke q dengan penyebut yang lebih kecil dari q. Karena pohon berisi setiap bilangan rasional positif tepat sekali, pencarian pertama yang luas dari pohon menyediakan metode daftar semua rasional positif yang terkait erat dengan urutan Farey.