Точные оценки сортировок и распределённый перебор алгоритмов (Иван Смирнов)

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