Max Home IndustryПо традиции, которой уже 20 лет, в начале этого месяца Дональд Кнут представил в Стэнфордском университете свою лекцию о рождественской елке 2014 года. Его тема, как всегда, связана с чем-то новым о деревьях, которые он узнал в течение года — в данном случае (3/2) -ричных деревьях.
Деревья важны в это время года, по крайней мере, в тех частях мира, где отмечается Рождество. Однако для программистов деревья всегда важны. Это фундаментальная продвинутая структура данных, которая, хотя и кажется простой, имеет множество удивительных и замечательных свойств.
Дональд Кнут должен быть вам известен, но на всякий случай — он изобрел компьютерную систему набора текста TeX, является автором монументального труда «Искусство компьютерного программирования» и множества алгоритмов. У него также странное чувство юмора, так что будьте осторожны, когда смотрите видео.
Примечания к лекции в значительной степени расскажут, о чем она:
В предыдущих лекциях профессор Кнут обсуждал бинарные деревья, троичные деревья, четверные деревья и т. Д., Которые нумеруются коэффициентами важных функций, называемых обобщенными биномиальными рядами порядка 2, 3, 4 и т. Д. Что происходит, когда мы рассматриваем обобщенные биномиальные ряды порядка 3/2 или других дробных порядков? Ответ довольно удивительный.
Сама лекция начинается примерно через 4 минуты — и имейте в виду, что она длится более часа, и за ней трудно следовать, если вы не знаете конечную математику, как описано в книге Кнута «Конкретная математика». Если математика вначале вас немного разочаровывает, попробуйте продолжить, потому что по мере продвижения она становится все более интересной и ориентированной на информатику: