Dlaczego liczby Fibonacciego są istotne w informatyce?

Question

Fibonacci numbers stały się popularnym wprowadzeniem do rekursji dla studentów informatyki i istnieje silny argument, że utrzymują się one w naturze. Z tych powodów wielu z nas je zna.

Występują również w ramach nauki o komputerach w innych miejscach; w zaskakująco wydajnych strukturach danych i algorytmach opartych na sekwencji.

Istnieją dwa główne przykłady, które przychodzą na myśl:

• Fibonacci heaps które mają lepsze amortyzowane czas pracy niż dwumiennych pryzmach.
• Fibonacci search który dzieli O (log N) czas pracy z binarnym wyszukiwanie w zamówionej tablicy.

Czy istnieje specjalna właściwość tych liczb, która daje im przewagę nad innymi sekwencjami liczbowymi? Czy to jest jakość przestrzenna? Jakie inne możliwe zastosowania mogą mieć?

Wydaje mi się to dziwne, ponieważ istnieje wiele sekwencji liczb naturalnych występujących w innych problemach rekurencyjnych, ale nigdy nie widziałem sterty Catalan.

Answer 1

Numery Fibonacciego mają wiele naprawdę fajnych właściwości matematycznych, które czynią je doskonałymi w informatyce. Oto kilka:

1. Rosną wykładniczo szybko. Interesującą strukturą danych, w której pojawia się seria Fibonacciego jest drzewo AVL, forma samowyważającego się drzewa binarnego. Intuicja za tym drzewem polega na tym, że każdy węzeł utrzymuje współczynnik równowagi, tak że wysokości lewego i prawego poddrzew różnią się co najwyżej o jeden. Z tego powodu można myśleć o minimalnej liczbie węzłów potrzebnych do uzyskania drzewa AVL o wysokości h zdefiniowanego przez powtarzanie się, które wygląda jak N (h + 2) ~ = N (h) + N (h + 1), który wygląda bardzo podobnie do serii Fibonacci. Jeśli rozwiążesz matematykę, możesz pokazać, że liczba węzłów potrzebna do uzyskania drzewa AVL o wysokości h to F (h + 2) - 1. Ponieważ seria Fibonacci rośnie wykładniczo szybko, oznacza to, że wysokość AVL drzewo jest co najwyżej logarytmiczne w liczbie węzłów, dając ci czas wyszukiwania O (lg n), który znamy i kochamy o zrównoważonych drzewach binarnych. W rzeczywistości, jeśli możesz związać rozmiar pewnej struktury z numerem Fibonacciego, prawdopodobnie uruchomisz O (lg n) podczas niektórych operacji. To jest prawdziwy powód, że stosy Fibonacciego są nazywane stosami Fibonacciego - dowód, że liczba stert po usunięciu z koperty oznacza związanie liczby węzłów, które możesz mieć na pewnej głębokości z liczbą Fibonacciego.
2. Dowolna liczba może być zapisana jako suma unikalnych liczb Fibonacciego. Ta właściwość numerów Fibonacciego ma kluczowe znaczenie, aby wyszukiwanie Fibonacciego działało w ogóle; gdyby nie można było dodać razem unikalnych liczb Fibonacciego do dowolnej liczby, to wyszukiwanie nie zadziałałoby. Porównaj to z wieloma innymi seriami, takimi jak 3 ⁿ lub numerami katalońskimi. Jest to również częściowo powodem, dla którego wiele algorytmów, takich jak moce dwóch, myślę.
3. Numery Fibonacciego są wydajnie obliczalne. Fakt, że seria może być generowana niezwykle wydajnie (możesz uzyskać pierwsze n terminów w O (n) lub dowolny dowolny termin w O (lg n)), wtedy wiele algorytmów, które z nich korzystają, nie byłoby praktyczne . Generowanie liczb katalońskich jest dość skomplikowane obliczeniowo, IIRC. Ponadto, liczby Fibonacciego mają ładną właściwość, gdzie, biorąc pod uwagę dowolne dwa kolejne numery Fibonacciego, powiedzmy F (k) i F (k + 1), możemy łatwo obliczyć następną lub poprzednią liczbę Fibonacciego przez dodanie dwóch wartości (F (k) + F (k + 1) = F (k + 2)) lub odejmowanie ich (F (k + 1) - F (k) = F (k - 1)). Właściwość ta jest wykorzystywana w kilku algorytmach, w połączeniu z właściwością (2), w celu rozbicia liczb na sumę liczb Fibonacciego. Na przykład, wyszukiwanie Fibonacci wykorzystuje to do lokalizowania wartości w pamięci, podczas gdy podobny algorytm może być użyty do szybkiego i wydajnego obliczania logarytmów.
4. Są przydatne pedagogicznie. Rekurencja w nauczaniu jest trudna, a seria Fibonacci to świetny sposób na jej wprowadzenie. Możesz mówić o prostej rekurencji, o zapamiętywaniu lub o dynamicznym programowaniu podczas wprowadzania serii. Dodatkowo zdumiewające closed-form for the Fibonacci numbers często nauczane mająca na indukcji lub w analizie szeregów nieskończonych i podobne matrix equation for Fibonacci numbers jest zwykle wprowadzane liniowo Algebra jako motywację wektorów własnych i wartości własnych. Myślę, że jest to jeden z powodów, dla których są oni tak wysoko postawieni w klasach wprowadzających.

Jestem pewien, że jest więcej powodów niż to, ale jestem pewien, że niektóre z tych powodów są głównymi czynnikami. Mam nadzieję że to pomoże!

Answer 2

Nie sądzę, że istnieje ostateczna odpowiedź, ale jedną z możliwości jest operacja podzielenia zbioru S na dwie partycje S1 i S2, z których jedna jest następnie podzielona na pod-partycje S11 i S12, z których jedna ma ten sam rozmiar co S2 - jest prawdopodobnym podejściem do wielu algorytmów, które można czasem opisać liczbowo jako sekwencję Fibonacciego.

Answer 3

Greatest Common Divisor inna magia; zobacz this dla zbyt wielu magii. Ale liczby Fibonacciego można łatwo obliczyć; również ma określoną nazwę. Na przykład liczby naturalne 1,2,3,4,5 mają zbyt wiele logiki; wszystkie liczby pierwsze są w nich; suma 1..n jest obliczalna, każdy może produkować z innymi, ale nikt się nimi nie opiekuje :)

Jedną z ważnych rzeczy, o których zapomniałem, jest Golden Ratio, która ma bardzo istotny wpływ na rzeczywistość. życie (na przykład lubisz szerokie monitory :)

Answer 4

Pozwól mi dodać kolejną strukturę danych do twoich: drzewa Fibonacciego. Są interesujące, ponieważ obliczanie następnej pozycji w drzewie można zrobić przez zwykłe dodanie poprzednich węzłów:

http://xw2k.nist.gov/dads/html/fibonacciTree.html

To wiąże dobrze się z dyskusji przez templatetypedef na AVL drzew (drzewa AVL może w najgorszym przypadku mieć strukturę fibonacci). W niektórych przypadkach widziałem również bufory wydłużone w etapach fibonacci, a nie moce dwóch.

Answer 5

Jeśli masz algorytm, który z powodzeniem może być wyjaśnione w prosty i zwięzły mannor ze zrozumiałych przykładów w CS i natury, co lepsze narzędzie nauka może ktoś wymyślić?

Answer 6

Sekwencje Fibonacciego znajdują się wszędzie w naturze/życiu. Są przydatne przy modelowaniu wzrostu populacji zwierząt, wzrostu komórek roślinnych, kształtu płatka śniegu, kształtu rośliny, kryptografii i oczywiście informatyki. Słyszałem, że nazywa się to naturą DNA.

Sterty Fibonacciego zostały już wymienione; liczba dzieci każdego węzła w stercie wynosi co najwyżej log (n). Również poddrzewo rozpoczynające węzeł z m dziećmi ma co najmniej (m + 2) liczbę fibonacci.

torrent jak protokoły, które wykorzystują system węzłów i supernodes używają Fibonacciego zdecydować, kiedy potrzebny jest nowy super węzeł i ile podwęzły będzie zarządzać.Zajmują się zarządzaniem węzłami w oparciu o spiralę fibonacci (złoty współczynnik). Zobacz zdjęcie poniżej, w jaki sposób węzły są dzielone/łączone (podzielone na jeden duży kwadrat na mniejsze i na odwrót). Zobacz zdjęcia: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Niektóre occurences w przyrodzie

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF

http://img.blogster.com/view/anacoana/post-uploads/finger.gif

http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif

http://2.bp.blogspot.com/-X5II-IhjXuU/TVbHrpmRnLI/AAAAAAAAABU/nv73Y9Ylkkw/s320/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879.jpg

Answer 7

Aby dodać ciekawostki na ten temat, liczby Fibonacciego opisują panierkę królika. Zaczynasz od (1, 1), dwóch królików, a następnie ich populacja rośnie wykładniczo.

Answer 8

Ich obliczenia jako mocy matrycy [[0,1], [1,1]] można uznać za najbardziej prymitywny problem badań operacyjnych (coś w rodzaju dylematu więźnia jest najbardziej prymitywnym problemem teorii gier) .