Лекция
NP-полные задачи
Страница лекции на сайте Computer Science клуба
Вероятностные алгоритмы
Страница лекции на сайте Computer Science клуба
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Алгоритмы расщепления
Страница лекции на сайте Computer Science клуба
Алгоритмы расщепления
Страница лекции на сайте Computer Science Club
Алгоритмы расщепления
Страница лекции на сайте Computer Science клуба
Точные и FPT-алгоритмы
Страница лекции на сайте Computer Science клуба
Точные и FPT-алгоритмы
Страница лекции на сайте Computer Science Club
Классические алгоритмы интернет поиска наиболее эффективны для нахождения ключевых слов в текстовых документах. В последние годы в интернете растет доля и ...
Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом.
Криптография с закрытым ключом
Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC...
Криптография с открытым ключом I
Криптография с открытым ключом II.
Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...
Решётки в криптографии
Протоколы согласования ключа
Разложение чисел на множители
Введение: метод Ферма. Метод Крайчика. Гладкие числа. Оценка сложности метода Крайчика на базе обобщения теоремы Мертенса. Решето...
Задача дискретного логарифма I
Введение. Методы со сложностью O(sqrt(n)). Baby-step-giant–step. rho–метод Полларда. Алгоритмы поиска цикла: алгоритм Флойда и ...
Задача дискретного логарифма II
Метод index calculus: третья фаза и оценка сложности. Сложность решения линейной системы: алгоритм Видеманна. Идея решета...
Вычислимые функции, разрешимые и перечислимые множества, универсальный алгоритм, перечислимое неразрешимое множество, вычислимые вещественные числа.
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Теорема Успенского–Райса. Теорема о неподвижной точке. Машины Тьюринга. Предикатные формулы. Неразрешимость исчисления предикатов. Выразимость в арифметике....
Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя.
Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо.
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Локальная лемма Ловаса. Оценки Чернова.
Локальная лемма Ловаса. Оценки Чернова.
Метод второго момента. Порог для 4–клики. Сепараторы.
Метод второго момента. Порог для 4–клики. Сепараторы.
Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды.
Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды.
Коды, исправляющие ошибки. Границы Хэмминга, Гилберта. Случайные коды, линейные коды. Код Хэмминга. Неравенство Синглетона. Код Рида–Соломона. Каскадные коды.
Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах.
Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик....
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Равносильность двух определений конъюнктивных грамматик. Приведение конъюнктивной грамматики к нормальному виду: удаление пустых конъюнктов, удаление единичных...
Булевы грамматики, семантика единственного решения в сильном смысле. Нормальный вид булевых грамматик. Алгоритм Кокка-Касами–Янгера в редакции для булевых...
Узкое место алгоритма Кокка–Касами–Янгера. Разбор через умножение матриц.
Рекурсивный спуск для бесконтекстных грамматик, его обобщение для конъюнктивных и булевых грамматик. Достижение линейного времени выполнения. Понятие об ...
FPT-алгоритмы
Страница лекции на сайте Computer Science клуба
Первая лекция курса "Дизайн Проектов" посвящена формированию проектной идеи.
Селигер, 2009 г.
Вторая лекция курса "Дизайн проекта" посвящена планированию в рамках проекта.
Селигер, 2009 г.
Знаменитая лекция про то, почему утонул Титаник. На Селигере, на протяжении нескольких смен участники пересказывали друг другу эту историю Соколова. Это лекция...
Лекция посвящена ресурсному обеспечению проекта.
Селигер, 2009 г.
Лекция курса на тему: "Презентация проекта".
Селигер, 2009 г.