В курсе излагаются основные (начальные) разделы теории сложности алгоритмов. Различаются алгебраическая и битовая сложности, каждая из которых рассматривается в худшем случае и в среднем. Ряд основных понятий теории сложности, как-то: оценки снизу и сверху, нижняя граница сложности алгоритмов некоторого класса, оптимальный алгоритм и т.д., рассматривается не только в обычном функциональном, но и в асимптотическом смысле: асимптотические оценки, асимптотическая нижняя граница, оптимальность по порядку сложности и т.д. Показывается, что при исследовании существования алгоритма решения задачи, имеющего «не очень высокую» сложность, важную роль может играть сводимость одной задачи к другой.

Изложение сопровождается анализом сложности большого числа алгоритмов арифметики, сортировки и поиска, вычислительной геометрии, теории графов и др.

Список всех тем лекций

Лекция 1. Сложность в худшем случае.
Введение в понятие сложности алгоритма Сортировка простыми вставками и его сложность Временная и пространственная сложность Равнодоступная Адресная Машина Асимптотическая оценка сложности

Лекция 2. Асимптотические оценки.
Сравнение алгоритмов через О-символику Алгоритм пробных делений Асимптотические оценки Задачи Алгоритм Шеймоса

Лекция 3. Сложность в среднем.
Количество цифр в двоичной записи числа Постулат Бертрана Бинарный алгоритм возведения числа в степень Аддитивные цепочки Гипотеза Шольца-Брауна Задача построения циркулем Вероятностные пространства Временная сложность в среднем Соотношение Гаусса

Лекция 4. Сортировки и конечные вероятностные пространства.
Алгоритм простых делений Сортировки Перестановки Математическое ожидание Задача про шляпы Алгоритм поиска минимального элемента в массиве Сортировка простыми вставками Формула математического ожидания Сортировка простыми вставками через математическое ожидание

Лекция 5. Рандомизированные алгоритмы.
Элементарные сортировки Сортировка пузырьком Быстрая сортировка Пространственная сложность, сложность по памяти Рандомизированные алгоритмы

Лекция 6. Вероятностное пространство сценариев.
Введение Сортировка выбором Сложность рандомизированного алгоритма через сложность в среднем Рандомизированная быстрая сортировка Утверждение о битовой длине Сложность алгоритма Евклида Алгоритм Евклида

Лекция 7. Полиномиальные языки.
Машина Тьюринга (МТ) Полиномиальная МТ Оценка сложности алгоритма МТ Полиномиальные языки Утверждение  Язык выполнимости Язык клика Сведение языка выполнимости к языку клика Класс NP языков, распознаваемых за полиномиальное время Утверждение Определение полноты и трудности языка Утверждение о NP языках К-выполнимость

Лекция 8. Алгоритмы и задачи проектирования, интегральные схемы.
Интегральная схема и ее производство Уровни абстракции при проектировании Системный уровень Поведенческий уровень Логический уровень Транзисторный уровень Уровень топологии Основные стратегии проектирования Программируемые интегральные схемы Системы на кристалле Процесс проектирования Минимизация ДНФ Алгоритм еspresso Инверсно-конгруэнтные типы Области применения Проверка эквивалентности Функциональная нормализация Функциональная коррекция Сравнение Схемы из ФЭ Общая схема решения

Лекция 9. Схемы и сложность оценки.
Полный класс схемы Функционалы сложности Задача синтеза Функция Шеннона П- схемы и формулы функций Утверждение об оценке сложности Системы конъюнкций и дизъюнкций Утверждение о схеме из функциональных элементов Теорема о сложности оценки

Лекция 10. Машина Тьюринга.
Машина Тьюринга Машина Тьюринга Утверждение о тождестве перехода от базиса к базису

Лекция 11. Число шагов алгоритма.
Алгоритм Евклида Расширенный алгоритм Евклида Алгоритм бинарного поиска Сортировка фон Неймана Число шагов в бинарном алгоритме

Лекция 12. Завершимость алгоритма.
Точность оценки алгоритма Евклида Формула Бине Доказательство точности оценки Оценка алгоритма Евклида №2 Оценка сложности формулой Стирлинга Завершимость алгоритма Хорошо фундированные последовательности Рандомизированные алгоритмы

Лекция 13. Нижние границы сложности. Оптимальные алгоритмы.
Завершимость рандомизированных алгоритмов Сложность класса алгоритмов выбора наименьшего элемента Сложность сортировки Нижняя граница сложности Сравнение алгоритмов сортировки Асимптотическая нижняя граница Алгоритм Прима

Лекция 14. Оптимальность по сложности в среднем.
Алгоритм Прима Оптимальность алгоритма бинарных вставок Оптимальность по порядку сложности сортировки Сложность сортировки в среднем Лемма о сложности в среднем Нижняя граница для сложности в среднем Рандомизированные алгоритмы через матричные игры

Лекция 15. Битовая сложность.
Нижняя граница сложности рандомизированных алгоритмов Булевая (битовая) сложность Временная и пространственная сложность Оценка битовой сложности Перевод в К-ую систему счисления Битовая сложность алгоритма Евклида

Лекция 16. Сложность модулярных алгоритмов.
Битовая сложность алгоритма Евклида Общая оценка сверху для алгоритма Евклида Самые быстрые алгоритмы умножения Расширенный алгоритм Евклида Сравнимость алгоритмов Кольцо вычетов по модулю К Теорема Ферма. Метод пробных делений Алгоритм проверки простоты AKS

Лекция 17. Булева сложность.
Булева арифметика Булевы матрицы Сложность алгоритма Алгоритм Уолшера Пространственная сложность алгоритма Уолшера Рекуррентные соотношения Задачи и алгоритм Флойда Характеристическое уравнение

Лекция 18. Рекуррентные соотношения.
Рекурсивная сортировка слиянием Рекурсивные слияния Анализ сложности алгоритмов Асимптотические оценки Асимптотическая верхняя оценка / оценка снизу Теорема о рекуррентном неравенстве Критическая перестановка

Лекция 19. Принцип "Разделяй и властвуй".
Введение Алгоритм Карацубы Сложность алгоритма Карацубы Алгоритм Штрассена Замыкание булевой матрицы Обобщение (алгоритма Карацубы), алгоритм Тоома Алгоритм умножения Сводимость

Лекция 20. Линейная сводимость.
Линейная сводимость Алгоритм Тоома, алгоритм Шанхаге-Штрассе Алгоритм умножения матриц (самый быстрый) Графы, построение матриц с помощью графов Сводимость и нижние границы сложности алгоритмов

Лекция 21. Линейная сводимость и нижние границы сложности.
Асимптотическая нижняя граница сложности алгоритмов Сложность алгоритмов Рациональные функции Сведение рациональных функций