Лекция
Введение. FPT алгоритм. Связь FPT алгоритмов с другими типами алгоритмов. Кернелизация. Простейшие примеры. Вершинное покрытие (Vertex Cover). Feedback Arc Set...
Сэмплеры и их применения
Булев сэмплер из экспандера, сэмплер из булева сэмплера. Усредняющие сэмплеры, "самый лучший" сэмплер без графов Рамануджана. Хиттер...
Сэмплеры
Сэмплеры: наивный сэмплер, попарно-независимый сэмплер, сэмплер,основанный на медиане усреднений.
Страница лекции на сайте Computer Science Center
Экстракторы
Минимальная энтропия, экстракторы, существование экстракторов. Представление источника в виде выпуклой комбинации плоских. Построение экстрактора...
Экспандеры и случайные блуждания по экспандерам
Комбинаторный и алгебраические экспандеры. Матрица смежности графа. Лемма о перемешивании. Блуждание по...
Анализ Фурье
Представление функций мультилинейными многочленами, существование и единственность. Базис Фурье, скалярное произведение. Плотность распределения....
Конструкция и применение немного смещенных распределений
Доказательство существования маленького epsilon-мещенного множества вероятностным методом. Явная...
Литература
Kent Pitman "UNWIND-PROTECT vs. Continuations"
Лекция на тему рациональности и интерфейсов расскажет о том, кто такие UX-специалисты. UX – User eXperience: с английского «опыт взаимодействия». Это ощущения...
Лекция 10. Коммуникационная сложность.
Детерминированная модель коммуникационной сложности; доказательство нижних оценок методом трудного множества....
Лекция 9. Случайность по Мартин–Лёфу.
Префиксная сложность. Случайные по Мартин–Лёфу последовательности. Закон больших чисел в форме Харди и Литтлвуда. Дефект...
Лекция 8. Приложения колмогоровской сложности.
Метод несжимаемых слов. Оценка сложности распознавания языка палиндромов на одноленточной машине Тьюринга....
Лекция 7. Колмогоровская сложность.
Простая колмогоровская сложность: определение и теорема о существовании оптимального декомпрессора. Энтропия Шеннона как...
Лекция 6. Энтропия в классической криптографии.
Оценка Шеннона для длины ключа в симметричной схеме шифрования. Схемы совершенного разделения секрета....
Лекция 5. Энтропийные профили наборов случайных величин и информационные неравенства.
Энтропийные профили для пар и троек случайных величин. Классические...
Лекция 4. Блоковое кодирование.
Метод типичных последовательностей. Теорема о блоковом кодировании последовательности независимых одинаково распределенных...
Лекция 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-независимого...
Введение в теорию вероятностей и вероятностный метод