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