Лекция
Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память.
Локальная лемма Ловаса. Оценки Чернова.
Алгоритмы расщепления
Страница лекции на сайте Computer Science клуба
Булевы грамматики, семантика единственного решения в сильном смысле. Нормальный вид булевых грамматик. Алгоритм Кокка-Касами–Янгера в редакции для булевых...
Дуэль n лиц
Содержание лекции
Задача дискретного логарифма I
Введение. Методы со сложностью O(sqrt(n)). Baby-step-giant–step. rho–метод Полларда. Алгоритмы поиска цикла: алгоритм Флойда и ...
Алгоритм и оценки времени его работы в худшем и среднем случае.
Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память.
Метод второго момента. Порог для 4–клики. Сепараторы.
В своей работе веб–дизайнеры должны принимать решения: (1) какие элементы разместить на странице и (2) какой приоритет дать тому или иному элементу. В...
Точные и FPT-алгоритмы
Страница лекции на сайте Computer Science клуба
Узкое место алгоритма Кокка–Касами–Янгера. Разбор через умножение матриц.
Рекуррентная устойчивость
Introduction to model checking: system modeling and logic specifications.
Содержание лекции
Задача дискретного логарифма II
Метод index calculus: третья фаза и оценка сложности. Сложность решения линейной системы: алгоритм Видеманна. Идея решета...
Introduction to model checking: system modeling and logic specifications.
Алгоритм Кармаркара
Классы RP, BPP, PP. 2–раундовые интерактивные доказательства. Многораундовые интерактивные доказательства.
Обзор
Страница лекции на сайте Computer Science клуба
Метод второго момента. Порог для 4–клики. Сепараторы.
Страница лекции на сайте Computer Science клуба
Новые технологии (социальные сети, семантический веб, мобильный интернет) неизбежно приведут к появлению рекламных систем нового типа. Потребители хотят...
Точные и FPT-алгоритмы
Страница лекции на сайте Computer Science Club
Рекуррентная устойчивость
Abstraction in model checking: Predicate abstraction; CEGAR–based software model checking.
Содержание лекции
Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа.
Abstraction in model checking: Predicate abstraction; CEGAR-based software model checkin.
Постановка задачи полуопределённого программирования, приближённый алгоритм для задачи о максимальном разрезе, раскраска 3–раскрашиваемого графа.
Классы RP, BPP, PP. 2–раундовые интерактивные доказательства. Многораундовые интерактивные доказательства.
Обзор
Страница лекции на сайте Computer Science клуба
Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды.
Страница лекции на сайте Computer Science клуба
