Семинар по алгоритмам и структурам данных ФКН
Задача сортировки сравнениями изучена давно и хорошо. Известна как нижняя оценка в 𝛀(n log n) сравнений, так и алгоритмы, достигающие времени работы 𝓞(n log n). На семинаре мы выберемся за пределы 𝓞-большого. Точное необходимое число сравнений для произвольного n неизвестно до сих пор, однако к уточнению оценки было сделано немало подходов: как со стороны разработок алгоритма с минимальным зазором относительно нижней оценки, так и к уточнению нижних оценок.
В 1950-х годах был опубликован алгоритм Форда - Джонсона со временем работы n log n + 𝓞(n), то есть с линейным отличием от оптимума. Мы разберём основные идеи этого алгоритма и его дальнейшие модификации - алгоритм Манакера и другие.
В области точных нижних оценок для небольших значений n существенная работа была проделана Печарски за прошедшие 20 лет. Он предложил двухфазный способ перебора алгоритмов сортировки, позволивший уточнить нижнюю оценку для n = 15 и ряда других значений.
Мы обсудим метод Печарски, недавнее (2022) продвижение, с помощью которого получилось улучшить оценки для n = 16-18, а также рассмотрим подходы к параллелизации алгоритмов перебора и их реализацию в модели распределенных вычислений.
Докладчик: Иван Смирнов, приглашенный преподаватель ФКН ВШЭ.
5 марта 2024
Семинар по алгоритмам и структурам данных ФКН: cs.hse.ru/seminarfknaads
ФКН: cs.hse.ru
Подписывайтесь на нас:
📍 vk.com/cshse
📍 t.me/fcs_hse
📍 dzen.ru/cshse
Негізгі бет Точные оценки сортировок и распределённый перебор алгоритмов (Иван Смирнов)
Пікірлер