Волосевич А.А. Основы теории алгоритмов

Учебно-методическое пособие по курсу «Теория алгоритмов» для студентов специальности «Информатика» всех форм обучения. — Минск: БГУИР, 2007. — 54 с. Учебно-методическое пособие составлено в соответствии с рабочей программой курса «Теория алгоритмов». В него включены базовые определения и основные результаты классической теории алгоритмов, а также теории сложности вычислений.
Описаны различные математические уточнения понятия «алгоритм», приведен численный анализ сложности некоторых алгоритмов.
Пособие может быть рекомендовано студентам и магистрантам технических специальностей для изучения математических основ теории алгоритмов и сложности вычислений. Неформальное определение алгоритма.
Арифметические и интуитивно вычислимые функции.
Машины Тьюринга.
Машины Шёнфилда.
Частично вычислимые функции.
Кодирование алгоритмов.
Алгоритмически неразрешимые задачи.
Универсальные функции.
Некоторые теоремы теории алгоритмов.
Сложность алгоритмов и массовых проблем.
Классы сложности P и EXP.
Класс сложности NP.
Сводимость и NP-полные задачи.
Анализ сложности рекурсивных алгоритмов.
Точная оценка сложности алгоритмов.
Алгоритмы сортировки и их анализ.
Алгоритмы вычислительной математики.