Почему числа Фибоначчи значимы в информатике?

Question

числа Фибоначчи стали популярным введением в рекурсию для студентов, изучающих информатику, и существует сильный аргумент, что они сохраняются в природе. По этим причинам многие из нас знакомы с ними.

Они также существуют в информатике в других местах; в удивительно эффективных структурах данных и алгоритмах, основанных на последовательности.

На ум приходят два основных примера:

• Кучи Фибоначчи , которые лучше амортизированное время работы, чем бином отвалы.
• поиск Фибоначчи , который разделяет O (log N) время работы с двоичным поиск в упорядоченном массиве.

Есть ли какое-то специальное свойство этих чисел, которое дает им преимущество перед другими числовыми последовательностями? Это пространственное качество? Какие еще возможные приложения они могут иметь?

Мне кажется странным, что существует много последовательностей натуральных чисел, возникающих в других рекурсивных задачах, но я никогда не видел кучу каталонскую .

Answer 1

Числа Фибоначчи обладают множеством действительно хороших математических свойств, которые делают их превосходными в информатике.Вот некоторые из них:

1. Они растут экспоненциально быстро. Одна интересная структура данных, в которой возникает ряд Фибоначчи, - это дерево AVL, форма самобалансирующегося двоичного дерева.Интуиция за этим деревом состоит в том, что каждый узел поддерживает коэффициент баланса, так что высоты левого и правого поддерева отличаются не более чем на единицу.Из-за этого вы можете думать о минимальном количестве узлов, необходимом для получения дерева AVL с высотой h, которое определяется повторением, которое выглядит как N (h + 2) ~ = N (h) + N (h + 1),который очень похож на серию Фибоначчи.Если вы поработаете над математикой, вы можете показать, что число узлов, необходимое для получения дерева AVL с высотой h, равно F (h + 2) - 1. Поскольку ряд Фибоначчи растет экспоненциально быстро, это означает, что высота AVLДерево максимально логарифмически по числу узлов, что дает вам время поиска O (lg n), которое мы знаем и любим о сбалансированных бинарных деревьях.Фактически, если вы можете связать размер какой-либо структуры с числом Фибоначчи, вы, скорее всего, получите время выполнения O (lg n) для какой-либо операции.Это реальная причина того, что кучи Фибоначчи называются кучами Фибоначчи - доказательство того, что количество куч после минимума очереди включает в себя ограничение числа узлов, которые вы можете иметь на определенной глубине, числом Фибоначчи.
2. Любое число может быть записано как сумма уникальных чисел Фибоначчи. Это свойство чисел Фибоначчи имеет решающее значение для обеспечения работы поиска Фибоначчи вообще;Если вы не можете сложить уникальные числа Фибоначчи в любое возможное число, этот поиск не будет работать.Сравните это с множеством других серий, таких как 3 ⁿ или каталонские числа.Это также частично объясняет, почему многие алгоритмы, такие как степени двух, я думаю.
3. Числа Фибоначчи эффективно вычисляются. Тот факт, что ряды могут быть сгенерированы чрезвычайно эффективно (вы можете получитьпервые n слагаемых в O (n) или любой произвольный слагаемый в O (lg n)), тогда многие алгоритмы, которые их используют, не будут практичными.Генерация каталонских чисел довольно сложна в вычислительном отношении, IIRC.Кроме того, числа Фибоначчи имеют приятное свойство, при котором, учитывая любые два последовательных числа Фибоначчи, скажем, F (k) и F (k + 1), мы можем легко вычислить следующее или предыдущее число Фибоначчи, добавив два значения(F (k) + F (k + 1) = F (k + 2)) или вычитать их (F (k + 1) - F (k) = F (k - 1)).Это свойство используется в нескольких алгоритмах в сочетании со свойством (2) для разбиения чисел на сумму чисел Фибоначчи.Например, поиск Фибоначчи использует это для поиска значений в памяти, в то время как аналогичный алгоритм может использоваться для быстрого и эффективного вычисления логарифмов.
4. Они полезны с педагогической точки зрения. Обучение рекурсии сложно,и ряд Фибоначчи - отличный способ представить это.Вы можете говорить о прямой рекурсии, о запоминании или о динамическом программировании при представлении серии.Кроме того, удивительная замкнутая форма для чисел Фибоначчи часто преподается как упражнение в индукции или в анализе бесконечных рядов, и обычно вводится соответствующее матричное уравнение для чисел Фибоначчи в линейной алгебре как мотивация собственных векторов и собственных значений.Я думаю, что это одна из причин того, что они так громко говорят на вводных уроках.

Я уверен, что есть больше причин, чем просто это, но я уверен, что некоторые изэти причины являются основными факторами.Надеюсь, это поможет!

Answer 2

Величайший общий делитель - еще одна магия; см это слишком много магии. Но числа Фибоначчи легко вычислить; также у этого есть определенное имя. Например, натуральные числа 1,2,3,4,5 имеют слишком много логики; все простые числа внутри них; сумма 1..n вычислима, каждый может производить с другими, ... но никто не заботится о них:)

Одна важная вещь, которую я забыл об этом, - Golden Ratio , которая имеет очень важное влияние в реальной жизни (например, вам нравятся широкие мониторы:)

Answer 3

Последовательности Фибоначчи действительно встречаются повсюду в природе / жизни. Они полезны для моделирования роста популяций животных, роста клеток растений, формы снежинок, формы растений, криптографии и, конечно, информатики. Я слышал, что это называется паттерном ДНК природы.

Кучи Фибоначчи уже упоминались; число дочерних элементов каждого узла в куче не более log (n). Также поддерево, начинающее узел с m дочерними элементами, имеет не менее (m + 2)-го числа Фибоначчи.

Торрентоподобные протоколы, которые используют систему узлов и суперузлов, используют Фибоначчи, чтобы решить, когда нужен новый суперузел и сколько подузлов он будет управлять. Они осуществляют управление узлами на основе спирали Фибоначчи (золотое сечение). Посмотрите на фото ниже, как узлы разделяются / объединяются (разбиваются от одного большого квадрата на меньшие и наоборот). Смотрите фото: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Некоторые случаи в природе

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 4

Если у вас есть алгоритм, который может быть успешно объяснен простым и лаконичным образом с понятными примерами в области КС и природы, какой лучший инструмент обучения может кто-нибудь придумать?

Answer 5

Символы с частотами, которые являются последовательными числами Фибоначчи, создают деревья Хаффмана с максимальной глубиной, которые соответствуют исходным символам, кодируемым двоичными кодами максимальной длины. Частоты символов не-Фибоначчи создают более сбалансированные деревья с более короткими кодами. Длина кода напрямую влияет на сложность описания конечного автомата, который отвечает за декодирование заданного кода Хаффмана.

---

Гипотеза: 1-е (fib) изображение будет сжато до 38 бит, а 2-е (равномерное) - с 50 битами. Кажется, что чем ближе ваши исходные символьные частоты к числам Фибоначчи, тем короче конечная двоичная последовательность, тем лучше сжатие, возможно, оптимальное в модели Хаффмана.

Дополнительная литература:

Buro, M. (1993). О максимальной длине кодов Хаффмана. Информация Обработка писем, 45 (5), 219-223. DOI: 10.1016 / 0020-0190 (93) 90207-р

Answer 6

Их вычисление в виде степени [[0,1], [1,1]] матрицы можно рассматривать как наиболее примитивную проблему исследования операций (вроде как дилемма заключенного является самой примитивной проблемой теории игр).

Answer 7

Просто чтобы добавить мелочи к этому, числа Фибоначчи описывают разведение кроликов. Вы начинаете с (1, 1) двух кроликов, а затем их популяция растет в геометрической прогрессии.

Answer 8

Позвольте мне добавить еще одну структуру данных к вам: деревья Фибоначчи.Они интересны, потому что вычисление следующей позиции в дереве может быть сделано простым добавлением предыдущих узлов:

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

Это хорошо согласуется с обсуждением templatetypedef на AVL-деревья (дерево AVL в худшем случае может иметь структуру Фибоначчи).Я также видел буферы, расширенные с шагом по Фибоначчи, а не степенью двойки в некоторых случаях.

Answer 9

Не думаю, что есть однозначный ответ, но одна возможность состоит в том, что операция деления множества S на два раздела S1 и S2, один из которых затем делится на подразделы S11 и S12, один из которых имеет тот же размер, что и S2 - это вероятный подход ко многим алгоритмам, который иногда можно численно описать как последовательность Фибоначчи.