Ebook: Сложность комбинаторных алгоритмов. Курс лекций

М.: Московский физико-технический институт, 2007. — 135 с.Элементы теории сложности.
Несложно о сложности. Примеры алгоритмов.
Формально об алгоритмах.
Сложность алгоритмов.
Вероятностные вычисления.
Вероятностно проверяемые доказательства.
Схемы и схемная сложность.
Коммуникационная сложность.
Диаграмма классов сложности.
Приближенные алгоритмы с гарантированными оценками точности.
Приближенные алгоритмы с фиксированными оценками точности.
Приближенные алгоритмы с выбираемыми оценками точности.
Вероятностные алгоритмы и вероятностный анализ.
Вероятностный анализ детерминированных алгоритмов.
Вероятностные алгоритмы.
Вероятностные методы в распределенных вычислениях.
Вероятностное округление и дерандомизация.
Криптография.
Генераторы.
Элементы криптографии с открытым ключом.