Теория вычислительной сложности

 
 
 
 
 
 
 
 
 
 
 
 
 
Г.П. Агибалов  
 
ТЕОРИЯ  
ВЫЧИСЛИТЕЛЬНОЙ 
СЛОЖНОСТИ 
 
Учебное пособие 

Министерство науки и высшего образования
Российской Федерации
Томский государственный университет

Г. П. Агибалов

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

Учебное пособие

Томск
2018

УДК 519.7
ББК 22.13я7

Агибалов Г. П. Теория вычислительной сложности: учеб.
пособие. — Томск: Издательский Дом Томского государственного
университета, 2018. — 42 с.

ISBN 978-5-94621-768-2

Пособие представляет собой курс лекций с тем же названием,
прочитанный автором в 2016/17 и 2017/18 учебных годах студентам кафедры защиты информации и криптографии по специальности «Компьютерная безопасность». Знакомство с курсом предполагает знание студентами основ дискретной математики и начальных понятий алгебры, теории алгоритмов и математической
логики.

УДК 519.7
ББК 22.13я7

c⃝ Г.П. Агибалов, 2018
c⃝ Томский государственный
ISBN 978-5-94621-768-2
университет, 2018

Предисловие
Теория вычислительной сложности (ТВС) — это наука о
сложности алгоритмов. Есть много книг о ней, в том числе исчерпывающего содержания. Наше учебное пособие этим свойством
не обладает и не претендует на полное изложение ТВС в её современном состоянии. Оно не рассчитано и на профессиональных специалистов по теории вычислительной сложности. Даже
название пособия не отражает его содержания. Оно просто повторяет название 36-часового курса лекций из образовательной
программы Томского государственного университета по специальности Компьютерная безопасность. Его цель — дать студентам этой специальности начальные понятия из теории временн´ой
сложности алгоритмов и важнейшие результаты из теории разрешимости алгоритмических задач в худшем и типичном случаях,
включая теоремы о NP-полноте задачи выполнимости, о генерической разрешимости задачи останова машины Тьюринга и о
генерической сложности задачи дискретного логарифмирования.

С благодарностью

Валентине Владимировне Быковой — за материал по асимптотическим оценкам сложности и основным сложностным классам алгоритмов;
Александру Николаевичу Рыбалову — за материал по генерической сложности алгоритмов;
Ирине Анатольевне Панкратовой — за редактирование и подготовку рукописи лекций к публикации в данном формате.

Геннадий Петрович Агибалов
01.09.2018

3