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