Игорь Пак

Сортировка чисел, многогранники и геометрические неравенства

И. М. Пак планирует провести 2 занятия.

Доступны 2 видеозаписи курса.

Предположим, имеется n чисел (a_1,...,a_n), которые требуется отсортировать. Предположим также, что имеется информация о сравнениях между некоторыми парами этих чисел, заданная как частичный порядок (poset). Можно ли придумать “оптимальную сортировку”, которая принимает во внимание этот частичный порядок и сортирует за наименьшее количество дополнительных сравнений? Оказывается, это сделать можно (с точностью до константы) — это теорема Кана и Сакса (Kahn–Saks theorem, 1984).

Доказательство, которое я расскажу, использует удивительную связь с геометрией многогранников, геометрические неравенства Брунна–Минковского и теорему Грюнбаума из функционального анализа. Заранее знать всего этого не требуется, я по порядку всё расскажу, ничего особенного и не используя.

Видео лекции:

Organization Committee e-mail:
dubna@mccme.ru