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

k-независимые хеш-функции и их применения
Вероятностные методы в вычислениях


Что: Лекция
Когда: Воскресенье, 22 февраля 2015, 13:00–14:35
Где: ПОМИ РАН

Описание

Использование матрицы Теплица для построения 2-независимого множества. Семейство k-независимых хеш-функций, конструкции. Основная лемма о хешировании для попарно независимых хеш-функций. Сравнение сложности NP-задач. Приближенный подсчет числа подсказок.

Домашнее задание, срок сдачи 15.03.2015 (27 апреля исправлены задачи 6б и 9).

Видео

Приложенные файлы