Лекция
Лекция 3. Вокруг теоремы Шеннона об оптимальном кодировании.
Однозначно декодируемые и префиксные коды, неравенство Крафта. Теорема Шеннона об оптимальном...
Лекция 2. Вероятностный подход к определению понятия информации, информация по Шеннону.
Определение энтропии Шеннона; относительная энтропия и взаимная...
Лекция 1. Комбинаторный подход к определению понятия информации, информация по Хартли.
Определение комбинаторной информации по Хартли; относительная информация...
Комбинаторная сложность. Классы сложности. Слова/языки ограниченной сложности. Слово Фибоначчи и слова Штурма. Фибоначчи, Зимин и нетрадиционные системы...
Комбинаторная сложность. Классы сложности. Слова/языки ограниченной сложности. Слово Фибоначчи и слова Штурма. Фибоначчи, Зимин и нетрадиционные системы...
Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (...
Бесповторность. Квадраты и кубы. Слова Туэ-Морса, теорема о сильной бескубности. Избегаемые экспоненты. Слова Аршона, теорема о 7/4. Граничная теорема (...
Повторы. Что считать повтором? Разбиение Лемпеля-Зива и метод LZ77. Online square detection. Максимальные повторения. Runs theorem: опять слова Линдона. Поиск...
Повторы. Что считать повтором? Разбиение Лемпеля-Зива и метод LZ77. Online square detection. Максимальные повторения. Runs theorem: опять слова Линдона. Поиск...
Перестановки. Элементарные свойства. Преобразование Барроуза-Уилера (BWT). Эффективность обратного преобразования. Проверка корректности. “Параллельное” BWT:...
Перестановки. Элементарные свойства. Преобразование Барроуза-Уилера (BWT). Эффективность обратного преобразования. Проверка корректности. “Параллельное” BWT:...
Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова....
Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова....
Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова....
Символьные последовательности в различных областях науки и практики, виды задач о символьных последовательностях. Уравнение коммутирования. Примитивные слова....
Немного смещенные распределения
Статистическое расстояние между распределениями. epsilon-смещенные распределения, их расстояние от равномерного. (epsilon, k)-...
Применения хеш-функций: генерация равномерного распределения на множестве подсказок
Лемма о хешировании для 2t-независимых хеш-функций. Генерация равномерного...
В лекции будет показано, что система команд традиционных машинных языков неадекватно описывает поток управления в исключительных ситуациях. Эти системы команд...
В лекции было рассказано про интерпретаторы, предложенные McCarthy в работах [1, 2]. Была затронута тема представления в языке булевских значений.
Литература:
В лекции будет проанализирована функция репрезентации для M-выражений. Будет показано, что на основе S-выражений можно построить более выразительный язык, чем...
Протоколы согласования ключа
Криптография с открытым ключом: протоколы согласования ключа. Протокол Диффи-Хеллмана. AKEP, протокол Шамира, протокол Отвея-Рииса...
Доказательства с неразглашением
Пещера Али–Бабы и Усама бен–Али. Определения: доказательства, системы доказательств. Изоморфизм и неизоморфизм графов. Как...
Эллиптические кривые в криптографии
Групповой закон на эллиптических кривых. Алгоритм Ленстры (ECM) на эллиптических кривых. Вычисления на эллиптических кривых...
Другие задачи криптографии
Oblivious transfer: протокол Рабина, 1–2–OT протокол, их эквивалентность. Секретное вычисление функции. Бросание монетки в колодец,...
Эллиптические кривые
Основные определения. Сингулярные и несингулярные кривые, проективная плоскость и проективные кривые. Результанты. Числа пересечения,...
Криптосистемы
Криптосистемы с открытым ключом: RSA. Атаки на RSA. Криптосистемы Рабина, Эль-Гамаля, Мак-Элиса, Меркле-Хеллмана.
Вероятностные алгоритмы для бесконечных задач, машины с переписыванием ответа
Страница лекции на сайте Computer Science Center
Протоколы с секретным ключом
Криптография с секретным ключом. Как использовать один и тот же ключ много раз? Блочные шифры: ECB, CBC, CFB, OFB. Имитовставки.
Введение в криптографические примитивы
Введение. Предмет и история криптографии. Виды криптографических атак. Чем вообще занимается криптография сегодня? Виды...
k-независимые хеш-функции и их применения
Использование матрицы Теплица для построения 2-независимого множества. Семейство k-независимых хеш-функций,...
Маленькие k-независимые множества
Маленькие k-независимые множества и их применение для поиска набора, выполняющего 7/8 дизъюнктов. Конструкция 2-независимого...
Введение в теорию вероятностей и вероятностный метод
Введение в теорию вероятностей и вероятностный метод
Вероятностное пространство. Простейшие свойства вероятности. Вероятностный метод. Эффективная монотонная...
Общий алгоритм Мозера-Тардоша и его оценка
Страница лекции на сайте Computer Science Center
Вероятностный метод: оценка суммы
Страница лекции на сайте Computer Science Center
Вероятностный метод: средние
Страница лекции на сайте Computer Science Center
Применения леммы Ловаса, ещё о запрещённых подсловах, выполнимость n-кнф с 2n−3 соседей у каждого клоза
Страница лекции на сайте Computer Science Center
Доказательство леммы Ловаса
Страница лекции на сайте Computer Science Center
Лемма Ловаса: формулировка
Страница лекции на сайте Computer Science Center
Дерандомизация
Страница лекции на сайте Computer Science Center
Ещё о вероятностных доказательствах
Страница лекции на сайте Computer Science Center
Вероятностные оценки: метод сжатия
Страница лекции на сайте Computer Science Center
В лекции было рассказано о историческом синтаксисе языка Lisp – M-выражениях. Была введена функция репрезентации и показано, что списки представимы cons-...
В лекции мы расскажем о хроматических числах графов, т.е. об экстремальных характеристиках графов, равных наименьшему количеству цветов, в которые можно так...
Вычисления и структуры данных во внешней памяти
Полупотоковые алгоритмы на графах. Эскизы, разрезы, спарсификаторы.
Полупотоковые алгоритмы на графах. Базовые алгоритмы.