Лекция
Равносильность двух определений конъюнктивных грамматик. Приведение конъюнктивной грамматики к нормальному виду: удаление пустых конъюнктов, удаление единичных...
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах.
Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик....
Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя.
Криптография с открытым ключом II.
Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...
Решётки в криптографии
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Криптография с открытым ключом I
Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа.
Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом.
Криптография с закрытым ключом
Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC...
Обзор
Страница лекции на сайте Computer Science клуба
Обзор
Страница лекции на сайте Computer Science клуба
Классические алгоритмы интернет поиска наиболее эффективны для нахождения ключевых слов в текстовых документах. В последние годы в интернете растет доля и ...
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Содержание лекции
Нижние оценки для схем ограниченной глубины.
Теорема Разборова о нижней оценке на сложность монотонных схем.
Классы RP, BPP, PP. 2–раундовые интерактивные доказательства. Многораундовые интерактивные доказательства.
Классы RP, BPP, PP. 2–раундовые интерактивные доказательства. Многораундовые интерактивные доказательства.
Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память.
Теорема Карпа–Липтона. Схемы фиксированного полиномиального размера. P–полнота. NSPACE. Полиномиальные вычисления и логарифмическая память.
Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.
Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
В своей работе веб–дизайнеры должны принимать решения: (1) какие элементы разместить на странице и (2) какой приоритет дать тому или иному элементу. В...
Новые технологии (социальные сети, семантический веб, мобильный интернет) неизбежно приведут к появлению рекламных систем нового типа. Потребители хотят...
