RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Стохастический анализ в задачах
5 ноября 2016 г. 11:00–14:00, г. Москва, ауд.303 МЦНМО
 


Обзорный доклад по вероятностным алгоритмам

Г. О. Евстропов

Количество просмотров:
Эта страница:217
Youtube Video:





Аннотация: В рамках данного доклада планируется рассмотреть несколько принципиально различных примеров алгоритмов, в которых наличие рандомизации в том или ином виде позволяет добиться существенного ускорения по сравнению со случаем, когда такая рандомизация отсутствует. Все приводимые примеры можно разбить на три категории: детерминированные алгоритмы, применённые к случайным данным; рандомизированные алгоритмы, математическое ожидание времени работы которых для любого входа асимптотически оптимальнее, чем время работы в худшем случае; и, собственно, вероятностные алгоритмы, время работы которых определяется только размеров входных данных, но правильный ответ выдаётся лишь с некоторой константной вероятностью. Приведём некоторые из алгоритмов, которые планируется рассмотреть в докладе:
1. Сортировка последовательности случайных чисел за линейное время.
2. Вычисление результата антагонистической игры для двух игроков на полном двоичном дереве за сублинейное время (без посещения всех листьев).
3. Линейный алгоритм проверки непустоты пересечения множества полуплоскостей.
4. Алгоритм Каргера-Штайна поиска глобального минимального разреза.
5. Задача о поиске свидетелей булева умножения при перемножении двух булевых матриц.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018