Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Семинар по сублинейным алгоритмам
Санкт-Петербург / осень 2016, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Долгое время считалось, что алгоритм с линейным временем работы является естественным пределом мечтаний для любой нетривиальной вычислительной задачи. Действительно, сложно представить ситуацию, когда алгоритм не должен читать весь свой вход для ответа на поставленную задачу. Однако, современный мир и растущие объемы данных ставят более амбициозные цели: решить задачу, прочитав лишь малую долю входа. Для некоторых задач известны точные алгоритмы с сублинейным временем работы, но зачастую для естественных задач алгоритмам требуется использовать случайные биты для в некотором смысле приближенного ответа на задачу. Данная область активно развивается, и границы таких алгоритмов пока остаются размытыми. Для создания сублинейных алгоритмов используется множество интересных комбинаторных и алгебраических техник. Для многих задач найдены оптимальные алгоритмы (в некоторых гарантиях), но ещё больше остается открытых задач как в доказательстве нижних оценок, так и в улучшении верхних оценок. Область связана со многими разделами теоретической информатики: коды исправляющие ошибки, потоковые алгоритмы, коммуникационная сложность, приближенные алгоритмы, вероятностно проверяемые доказательства.

В течение семинара планируется разобрать техники и основные результаты в данной области, полученные за последние годы. Формат семинара предполагает еженедельные доклады и обсуждение материала, доклады будут делаться студентами-участниками семинара. Предполагается, что участники будут знакомы с дискретной теорией вероятностей и базовым курсом алгоритмов.

Семинар входит в магистерскую программу теоретическая информатика Академического университета.

Дата и время Занятие Место Материалы
16 сентября
19:00–20:20
Введение (Николай Карпов), Лекция ПОМИ РАН, аудитория 106 Нет
23 сентября
19:00–20:20
Тестирование на монотонность (Артур Рязанов), Лекция ПОМИ РАН, аудитория 106 Нет
30 сентября
19:00–20:20
Тестирование на монотонность 2 (Александр Логунов), Лекция ПОМИ РАН, аудитория 106 Нет
07 октября
19:00–20:20
Тестирование на линейность и многочлены ограниченной степени (Петр Смирнов), Лекция ПОМИ РАН, аудитория 106 Нет
14 октября
19:00–20:20
Методы доказательства нижних оценок на число запросов (Людмила Глинских), Лекция ПОМИ РАН, аудитория 106 Нет
21 октября
19:00–20:20
Еще про нижние оценки на количество запросов (Олег Вайнзихер), Лекция ПОМИ РАН, аудитория 106 Нет
28 октября
19:00–20:20
Тестирование свойств графа в модели плотных графов (Святослав Грязнов), Лекция ПОМИ РАН, аудитория 106 Нет
11 ноября
19:00–20:20
Обзор поточных алгоритмов (Всеволод Опарин), Лекция ПОМИ РАН, аудитория 106 Нет
18 ноября
19:00–20:20
Графы ограниченной степени и тестирование их свойств (Надежда Воронова), Лекция ПОМИ РАН, аудитория 106 Нет
25 ноября
19:00–20:20
Поиск паросочетания в регулярных двудольных графах (Николай Карпов), Лекция ПОМИ РАН, аудитория 106 Нет
02 декабря
19:00–20:20
Тестирование свойств распределений (Кирилл Симонов), Лекция ПОМИ РАН, аудитория 106 Нет
09 декабря
19:00–20:20
L_p-тестирование (Марсель Матдинов), Лекция ПОМИ РАН, аудитория 106 Нет
16 декабря
19:00–20:20
Spot-Checkers (Никита Гаевой), Лекция ПОМИ РАН, аудитория 106 Нет