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