Где используются “Особые числа”, упомянутые в конкретной математике?
https://stackoverflow.com/questions/901761
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я просматривал содержание Concrete Maths онлайн.Я, по крайней мере, слышал о большинстве упомянутых функций и приемов, но есть целый раздел, посвященный специальным номерам.Эти числа включают Числа Стирлинга, Эйлеровы числа, Гармонические числа и так далее.Теперь я никогда не сталкивался ни с одним из этих странных чисел.Как они помогают в решении вычислительных задач?Где они обычно используются?
Решение
Большинство из этих чисел учитывают определенные виды дискретных структур (например, числа Стирлинга учитывают подмножества и циклы).Такие структуры, и, следовательно, эти последовательности, неявно возникают в анализ алгоритмов.
Есть обширный список в OEIS это перечисляет почти все последовательности, которые появляются в конкретной математике.Краткое резюме из этого списка:
- Последовательность Голомба
- Биномиальные Коэффициенты
- Номера Отказов
- Числа Стирлинга
- Эйлеровы числа
- Гиперфакториалы
- Числа Генокки
Вы можете просмотреть страницы OEIS для соответствующих последовательностей, чтобы получить подробную информацию о "свойствах" этих последовательностей (хотя и не совсем приложений, если это то, что вас больше всего интересует).
Кроме того, если вы хотите увидеть реальное применение этих последовательностей при анализе алгоритмов, просмотрите указатель книги Кнута "Искусство компьютерного программирования", и вы найдете много ссылок на "приложения" этих последовательностей.Джон Д.Кук уже упоминал о применении чисел Фибоначчи и гармоник;вот еще несколько примеров:
Номера циклов Стирлинга возникают при анализе стандартного алгоритма, который находит максимальный элемент массива ( TAOCP , Раздел .1.2.10):Сколько раз необходимо обновлять текущее максимальное значение при нахождении максимального значения?Получается, что вероятность того, что максимум нужно будет обновить k раз, когда нахождение максимума в массиве n элементы - это p[n][k] = StirlingCycle[n, k+1]/n!.Из этого мы можем вывести, что в среднем, приблизительно Log(n) обновления будут необходимы.
Числа Генокки возникают в связи с подсчетом количества БДДс которые являются "тонкими" (TAOCP 7.1.4 Упражнение 174).
Другие советы
Гармонические числа появляются почти везде!Музыкальные гармонии, анализ Быстрой сортировки...Числа Стирлинга (первого и второго рода) возникают в различных задачах комбинаторики и разбиения.Эйлеровы числа также встречаются в нескольких местах, в первую очередь в перестановках и коэффициентах полилогарифмических функций.
Многие из упомянутых вами чисел используются при анализе алгоритмов.Возможно, у вас нет этих цифр в вашем коде, но они вам понадобятся, если вы хотите оценить, сколько времени потребуется для выполнения вашего кода.Возможно, вы тоже увидите их в своем коде.Некоторые из этих чисел связаны с комбинаторикой, подсчитывающей, сколькими способами что-то может произойти.
Иногда недостаточно знать, сколько существует возможностей, потому что вам нужно перечислять над возможностями. Том 4 TAOCP Кнута, в процессе выполнения, предоставляет необходимые вам алгоритмы.
Вот пример использования Числа Фибоначчи как часть задачи численного интегрирования.
Гармонические числа являются дискретным аналогом логарифмов, и поэтому они возникают в разностных уравнениях точно так же, как логарифмы возникают в дифференциальных уравнениях.Вот пример того, как физические применения гармонических средств, относящийся к гармоническим числам.Смотрите книгу Гамма для многих примеров гармонических чисел в действии, особенно для главы "Это гармоничный мир".
Эти специальные числа могут помочь в вычислительных задачах многими способами.Например:
Вы хотите выяснить, когда вашей программе для вычисления GCD из 2 чисел потребуется наибольшее количество времени:Попробуйте 2 последовательных числа Фибоначчи.
Вы хотите получить приблизительную оценку факториала большого числа, но ваша факториальная программа занимает слишком много времени:Использование Приближение Стирлинга.
Вы тестируете на простые числа, но для некоторых чисел вы всегда получаете неправильный ответ:Возможно, вы используете простой тест Ферма, и в этом случае Кармические числа это ваши виновники.
Самый распространенный общий случай, о котором я могу думать, - это зацикливание.Большую часть времени вы указываете цикл, используя (start;stop;step) тип синтаксиса, в этом случае может оказаться возможным сократить время выполнения, используя свойства задействованных чисел.
Например, суммирование всех чисел от 1 до n, когда n велико в цикле, определенно медленнее, чем использование идентификатора sum = n*(n + 1)/2.
Существует большое количество подобных примеров.Многие из них относятся к криптографии, где безопасность информационных систем иногда зависит на таких трюках, как эти.Они также могут помочь вам с проблемами производительности, с проблемами памяти, потому что, зная формулу, вы можете найти более быстрый и эффективный способ вычислять другие вещи - вещи, которые вас действительно волнуют.
Для получения дополнительной информации загляните в википедию или просто попробуйте Project Euler.Вы начнете находить закономерности довольно быстро.
Не обязательно a магическое число из ссылки, которую вы упомянули, но тем не менее --
0x5f3759df
-- пресловутое магическое число, используемое для вычисления обратного квадратного корня из числа, давая хорошую первую оценку ньютоновскому Аппроксимация корней, часто приписываемый работе Джона Кармака - более подробная информация здесь.
Не связано с программированием, да?:)
Связано ли это напрямую с программированием?Наверняка связаны, но я не знаю, насколько тесно.
Специальные числа, такие как e, pi и т.д., появляются повсюду.Я не думаю, что кто-то стал бы спорить по поводу этих двоих.В Золотая_рация также встречается с удивительной частотой, во всем, начиная с рисунков и заканчивая самими другими особыми числами (посмотрите на соотношение между последовательными числами Фибоначчи).
Различные последовательности и семейства чисел также встречаются во многих местах в математике, а следовательно, и в программировании.Прекрасное место для осмотра - это Энциклопедия целочисленных последовательностей.
Я предположу, что это вопрос опыта.Например, когда я изучал линейную алгебру много-много лет назад, я узнал о собственных значениях и собственных векторах матрицы.Я признаю, что я совсем не понимал значения собственных значений / eigenvectors, пока не увидел, как они используются в самых разных местах.В статистике, с точки зрения того, что они говорят вам о неопределенности оценки из ковариационной матрицы, размере и форме доверительного эллипса, с точки зрения анализа главных компонент или долгосрочного состояния марковского процесса.В численных методах, где они рассказывают вам о сходимости метода, будь то в оптимизации или решателе ODE.В машиностроении, где вы рассматриваете их как основные напряжения и деформации.
