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

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


Что: Лекция
Когда: Воскресенье, 11 марта 2012, 18:30–20:05
Где: ПОМИ РАН

Описание

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

Видео