Введение в теорию алгоритмов

Московский государственный технический университет  
имени Н.Э. Баумана 
 
 
 
П.Г. Ключарев,  Д.А. Жуков 
 
 
 
 
ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ 
 
 
Рекомендовано  
Научно-методическим советом МГТУ им. Н.Э. Баумана  
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва 
Издательство МГТУ им. Н.Э. Баумана 
2012 

УДК 510.5(075.8) 
ББК  22.12 
   К52 
 
Рецензенты: А.Н. Велигура, А.Ю. Голубков  
 
К52 
 
 
Ключарев П. Г. 
Введение в теорию алгоритмов : учеб. пособие / П.Г. Ключарев, Д.А. Жуков. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2012. 
–  37, [3] с.: ил. 
 
Рассмотрены машины Тьюринга, вопросы алгоритмической 
разрешимости, основные классы сложности, NP-полнота, схемная 
сложность. 
Для студентов МГТУ им. Н.Э. Баумана, обучающихся по специальностям «Информационная безопасность автоматизированных 
систем» и «Компьютерная безопасность». Пособие может быть 
полезно студентам других специальностей, связанных с информатикой, вычислительной техникой и информационной безопасностью. 
УДК 510.5(075.8) 
           ББК 22.12 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
                     
 
 
 
   © МГТУ им. Н.Э. Баумана, 2012 

ВВЕДЕНИЕ 
В любой области науки и техники и просто в повседневной 
жизни человек постоянно сталкивается с решением различных задач. Примерами задач могут быть подсчет стоимости продуктов 
для банкета, выбор оптимального маршрута для поездки в другой 
конец города, вычисление квадратного корня из заданного числа, 
расчет оптимальной траектории космического аппарата, шифрование файла.  
Решая любую конкретную задачу, человек выполняет некоторую последовательность действий. Формальное описание такой 
последовательности действий называют алгоритмом. Несмотря на 
то что алгоритмы могут быть предназначены для решения совершенно разных задач и быть совсем непохожими друг на друга, существуют свойства, характерные для всех алгоритмов.  
Общие свойства алгоритмов изучает теория алгоритмов, которой и посвящено настоящее учебное пособие. Теория алгоритмов 
представляет собой область дискретной математики, находящуюся 
на стыке математической логики и информатики. Изучение общих 
свойств задач и алгоритмов с математической точки зрения имеет 
огромное значение как для чистой математики, так и для большинства областей информатики, прежде всего для программирования 
и информационной безопасности. 
Одним из краеугольных камней информационной безопасности является криптография. Многие методы криптографии основаны на тех или иных свойствах алгоритмов. В частности, почти все 
современные криптографические алгоритмы и протоколы базируются на однонаправленных функциях, т. е. на функциях, которые 
можно быстро вычислить, но для обращения которых требуется 
очень много времени. 
В учебном пособии приведены основные понятия теории алгоритмов. Эта теория непрерывно развивается и накопила знания, 
далеко выходящие за рамки этого пособия. Заинтересованный читатель найдет много дополнительных сведений в книгах, приведенных в списке литературы [1–16]. 
3 

1. ОСНОВНЫЕ ПОНЯТИЯ 
Учебное пособие рассчитано на читателя, который освоил теорию булевых функций, теорию графов и теорию вероятностей. Читателю, не изучавшему эти разделы математики, мы рекомендуем 
ознакомиться с ними, используя, например, работы [6, 11, 15]. 
Далее мы будем применять некоторые стандартные обозначения, в частности: 
{
}
1; 2; 3; ...
=
`
 – множество натуральных чисел; 
\  – множество действительных чисел. 
Сначала введем основные термины и определения.  
Определение 1.  Рассмотрим две функции: 
,
:
.
f g
→
`
`  Формула 
( )
f
O g
=
 означает, что существуют такие c∈\  и 
0
,
n ∈`  
что при любом 
0
n
n
>
 выполняется 
( )
( ).
f n
cg n
≤
 
Определение 2.  Формула 
( )
f
g
= Ω
 означает, что 
( ).
g
O f
=
 
Определение 3. Формула 
( )
f
g
= Θ
 означает, что 
( )
f
O g
=
 и 
( ).
g
O f
=
 
Определение 4.  Назовем функцию 
:
f
→
`
`  полиномиальной, если существует такое k ∈\ , что 
( )
(
).
k
f n
O n
=
 
Дадим теперь более строгое определение понятия задачи, с тем 
чтобы это понятие можно было теоретически исследовать.  
Определение 5.  Назовем абстрактной задачей некоторое бинарное отношение между элементами двух множеств: множества 
условий и множества решений.  
Примером является задача об умножении двух чисел: условие –  
пара чисел, а решение – одно число.  
Определение 6.  Задачи, у которых множество решений состоит из двух элементов (например, ДА и НЕТ), будем называть задачами распознавания.  
Примером задачи распознавания может служить следующая 
задача: определить, является ли данный граф гамильтоновым.  
Понятие задачи тесно связано с понятием языка. 
4