Введение в теорию алгоритмов (120,00 руб.)

Рассмотрены машины Тьюринга, вопросы алгоритмической разрешимости, основные классы сложности, NP-полнота, схемная сложность. <...> Решая любую конкретную задачу, человек выполняет некоторую последовательность действий. <...> Общие свойства алгоритмов изучает теория алгоритмов, которой и посвящено настоящее учебное пособие. <...> Теория алгоритмов представляет собой область дискретной математики, находящуюся на стыке математической логики и информатики. <...> В частности, почти все современные криптографические алгоритмы и протоколы базируются на однонаправленных функциях, т. е. на функциях, которые можно быстро вычислить, но для обращения которых требуется очень много времени. <...> Эта теория непрерывно развивается и накопила знания, далеко выходящие за рамки этого пособия. <...> ОСНОВНЫЕ ПОНЯТИЯ Учебное пособие рассчитано на читателя, который освоил теорию булевых функций, теорию графов и теорию вероятностей. <...> Назовем функцию  полиномиальной, если существует такое k∈, что () ( ).k f : → f nO n= Дадим теперь более строгое определение понятия задачи, с тем чтобы это понятие можно было теоретически исследовать. <...> Задачи, у которых множество решений состоит из двух элементов (например, ДА и НЕТ), будем называть задачами распознавания. <...> Примером задачи распознавания может служить следующая задача: определить, является ли данный граф гамильтоновым. <...> Слово принадлежит этому языку тогда и только тогда, когда для этого входного слова ответ задачи – ДА. <...> Условие задачи можно некоторым разумным образом закодировать над конечным алфавитом (следовательно, и над двоичным алфавитом). <...> Например, рациональное число всегда можно закодировать над двоичным алфавитом, используя представление с плавающей точкой. <...> Граф можно закодировать с помощью матрицы смежности, матрицы инцидентности или списка вершин. <...> Было предложено большое число различных алгоритмических моделей. <...> Машина Тьюринга состоит из головки и ленты, по которой эта головка перемещается <...>