Рассмотрены машины Тьюринга, вопросы алгоритмической разрешимости, основные классы сложности, NP-полнота, схемная сложность. <...> Решая любую конкретную задачу, человек выполняет некоторую последовательность действий. <...> Общие свойства алгоритмов изучает теория алгоритмов, которой и посвящено настоящее учебное пособие. <...> Теория алгоритмов представляет собой область дискретной математики, находящуюся на стыке математической логики и информатики. <...> В частности, почти все современные криптографические алгоритмы и протоколы базируются на однонаправленных функциях, т. е. на функциях, которые можно быстро вычислить, но для обращения которых требуется очень много времени. <...> Эта теория непрерывно развивается и накопила знания, далеко выходящие за рамки этого пособия. <...> ОСНОВНЫЕ ПОНЯТИЯ Учебное пособие рассчитано на читателя, который освоил теорию булевых функций, теорию графов и теорию вероятностей. <...> Назовем функцию полиномиальной, если существует такое k∈, что () ( ).k f : → f nO n= Дадим теперь более строгое определение понятия задачи, с тем чтобы это понятие можно было теоретически исследовать. <...> Задачи, у которых множество решений состоит из двух элементов (например, ДА и НЕТ), будем называть задачами распознавания. <...> Примером задачи распознавания может служить следующая задача: определить, является ли данный граф гамильтоновым. <...> Слово принадлежит этому языку тогда и только тогда, когда для этого входного слова ответ задачи – ДА. <...> Условие задачи можно некоторым разумным образом закодировать над конечным алфавитом (следовательно, и над двоичным алфавитом). <...> Например, рациональное число всегда можно закодировать над двоичным алфавитом, используя представление с плавающей точкой. <...> Граф можно закодировать с помощью матрицы смежности, матрицы инцидентности или списка вершин. <...> Было предложено большое число различных алгоритмических моделей. <...> Машина Тьюринга состоит из головки и ленты, по которой эта головка перемещается <...>
_Введение_в_теорию_алгоритмов.pdf
УДК 510.5(075.8)
ББК 22.12
К52
Рецензенты: А.Н. Велигура, А.Ю. Голубков
К52
Ключарев П. Г.
Введение в теорию алгоритмов : учеб. пособие / П.Г. Ключарев,
Д.А. Жуков. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2012.
– 37, [3] с.: ил.
Рассмотрены машины Тьюринга, вопросы алгоритмической
разрешимости, основные классы сложности, NP-полнота, схемная
сложность.
Для студентов МГТУ им. Н.Э. Баумана, обучающихся по специальностям
«Информационная безопасность автоматизированных
систем» и «Компьютерная безопасность». Пособие может быть
полезно студентам других специальностей, связанных с информатикой,
вычислительной техникой и информационной безопасностью.
УДК
510.5(075.8)
ББК 22.12
© МГТУ им. Н.Э. Баумана, 2012
Стр.2
ОГЛАВЛЕНИЕ
Введение ............................................................................................. 3
1. Основные понятия ......................................................................... 4
2. Алгоритмически неразрешимые задачи ...................................... 10
3. Классы сложности ......................................................................... 15
4. NP-полнота ..................................................................................... 16
5. Схемы из функциональных элементов ........................................ 23
6. Вероятностные алгоритмы ............................................................ 32
7. Защита информации и теория алгоритмов .................................. 34
Задачи для самостоятельного решения............................................ 35
Литература .......................................................................................... 37
38
Стр.38