Майкл Фредман¶

Майкл Фредман (англ. Michael Fredman; род. 18 июля 1945, Нью-Йорк) — американский учёный в области информатики, профессор компьютерных наук, известный своими работами в области анализа алгоритмов, структур данных и теории сложности вычислений. Наиболее значимые достижения включают создание структуры данных «куча Фредмана — Тарьяна» (Fibonacci heap) и разработку алгоритма Фредмана — Тарьяна для поиска минимального остовного дерева.

¶Биография

Майкл Фредман родился в 1945 году в Нью-Йорке. Получил степень бакалавра по математике в Принстонском университете в 1966 году, а затем степень доктора философии (Ph.D.) по математике в Стэнфордском университете в 1972 году под руководством Дональда Кнута. Тема диссертации была связана с анализом алгоритмов сортировки и поиска.

После защиты докторской Фредман работал в Исследовательском центре Xerox PARC (Palo Alto Research Center), а затем перешёл на факультет компьютерных наук Калифорнийского университета в Сан-Диего (UCSD), где проработал до выхода на пенсию. В разное время он также занимал должности в Массачусетском технологическом институте (MIT) и Университете Рутгерса.

¶Научный вклад

¶Куча Фибоначчи (Fibonacci heap)

В 1984 году совместно с Робертом Тарьяном Фредман предложил структуру данных, известную как куча Фибоначчи (Fibonacci heap). Это структура, реализующая приоритетную очередь с амортизированным временем выполнения операций. Основные характеристики:

Вставка элемента: O(1)
Удаление минимального элемента: O(log n)
Уменьшение ключа: O(1)

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

¶Алгоритм Фредмана — Тарьяна для минимального остовного дерева

В 1987 году Фредман и Тарьян разработали алгоритм, который находит минимальное остовное дерево (MST) во взвешенном неориентированном графе за время O(m log β(m,n)), где m — количество рёбер, n — количество вершин, а β(m,n) — медленно растущая функция, обратная функции Аккермана. Этот алгоритм использует структуру «куча Фибоначчи» и идею «разделяй и властвуй» для достижения почти линейного времени работы.

¶Другие работы

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

¶Признание и награды

В 1986 году совместно с Робертом Тарьяном получил премию Ассоциации вычислительной техники (ACM) за лучшую статью (ACM SIGACT Paper Award) за работу о куче Фибоначчи.
В 1990 году избран членом Ассоциации вычислительной техники (ACM Fellow) за вклад в анализ алгоритмов и структуры данных.
В 2002 году удостоен премии Кнута (Knuth Prize) за фундаментальные достижения в области информатики.

¶Основные публикации

Fredman, M. L., & Tarjan, R. E. (1984). «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the ACM, 34(3), 596–615.
Fredman, M. L., & Tarjan, R. E. (1987). «A data structure for dynamic trees». Journal of Computer and System Sciences, 34(3), 344–363.
Fredman, M. L. (1975). «On the complexity of sorting». SIAM Journal on Computing, 4(3), 283–292.

¶Влияние на современную информатику

Работы Фредмана заложили основы для многих современных алгоритмов и структур данных. Куча Фибоначчи используется в библиотеках стандартных алгоритмов (например, в Boost C++ Libraries), а его алгоритмы для минимального остовного дерева применяются в задачах проектирования сетей, кластеризации данных и анализа графов. Вклад Фредмана в теорию нижних оценок повлиял на развитие теории сложности и алгоритмов.

¶Интересные факты

Фредман является одним из немногих учёных, чьи работы напрямую повлияли на создание «библиотеки алгоритмов» STL (Standard Template Library) в C++.
В 1990-х годах он участвовал в разработке алгоритмов для поиска в больших базах данных, что предвосхитило современные методы индексации.