Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо.

Приближенные алгоритмы Страница лекции на сайте Computer Science клуба

Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик....

Страница лекции на сайте Computer Science клуба

Содержание лекции

Криптография с открытым ключом II. Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...

Наибольшая возрастающая подпоследовательность, стоимость редактирования, рюкзак, перемножение нескольких матриц, кратчайшие пути, независимые множества в...

Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.

Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...

Приближенные алгоритмы Страница лекции на сайте Computer Science клуба

Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...

Содержание лекции

Решётки в криптографии

Задача о выборе заявок, коды Хаффмена, покрытие множествами, вершинное покрытие, локальный поиск для задачи выполнимости.

Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.

Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...

Алгоритмы расщепления Страница лекции на сайте Computer Science клуба

Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...

Проблема изоморфизма простых графов

Содержание лекции

Протоколы согласования ключа