Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Летняя школа «Современная математика» имени Виталия Арнольда, 2021
28 июля 2021 г. 11:15, Московская область, г. Дубна, дом отдыха «Ратмино»
 


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

И. М. Пак
Видеозаписи:
MP4 3,457.9 Mb

Количество просмотров:
Эта страница:196
Видеофайлы:63
Youtube:

И. М. Пак



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

Website: https://mccme.ru/dubna/2021/courses/pak.html
Цикл лекций
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024