Читать онлайн «Теория алгоритмов»

В. Н. Крупскии В. Е. Плиско ТЕОРИЯ АЛГОРИТМОВ Прикладная математика и информатика УНИВЕРСИТЕТСКИЙ УЧЕБНИК СЕРИЯ «ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА» В. Н. КРУПСКИЙ,В. Е. ПЛИСКО ТЕОРИЯ АЛГОРИТМОВ Допущено Научно-методическим советом по математике Министерства образования и науки Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям «Информатика и вычислительная техника», «Информационные системы и технологии» ACADEMA Москва Издательский центр «Академия» 2009 УДК 510. 5(075. 8) ББК22. 12я73 К845 Рецензенты: д-р пед. наук, проф. кафедры математического анализа математического факультета Московского педагогического государственного университета И. Л. Тимофеева', д-р филос. наук, канд. физ. -мат. наук, проф. кафедры «Прикладная математика-2» Московского государственного университета путей сообщения В. Х. Хаханян Крупский В. Н. К845 Теория алгоритмов : учеб. пособие для студ. вузов/ В. Н. Крупский, В. Е. Плиско. — М. : Издательский центр «Академия», 2009. — 208 с. (Университетский учебник. Сер. Прикладная математика и информатика). ISBN 978-5-7695-5293-9 В учебном пособии изложены основы качественной и количественной теории алгоритмов; рассмотрены основные модели вычислений (машины Тьюринга, машины с неограниченными регистрами, рекурсивные функции) и связанные с ними подходы к формализации понятия алгоритма; даны начала алгоритмической теории множеств; представлены наиболее известные результаты об алгоритмической неразрешимости, а также элементы теории сложности вычислений. Для студентов высших учебных заведений. Может быть полезно широкому кругу читателей, интересующихся основами теории вычислимости. УДК 510. 5(075. 8) ББК22. 12я73 Оригинал-макет данного издания является собственностью Издательского центра «Академия», и его воспроизведение любым способом без согласия правообладателя запрещается ©Крупский B. H. , Плиско B. E. , 2009 ©Образовательно-издательский центр «Академия», 2009 ISBN 978-5-7695-5293-9 ©Оформление. Издательский центр «Академия», 2009 ПРЕДИСЛОВИЕ Формирование теории алгоритмов как самостоятельного раздела математики, изучающего общие свойства алгоритмов, началось в 30-е годы XX в. Однако само понятие алгоритма использовалось в математике на протяжении всей истории ее развития. В неявном виде это понятие присутствует всякий раз, когда речь идет о правилах и инструкциях, позволяющих решать ту или иную математическую задачу «в общем виде». Иногда эти правила сами называются алгоритмами (например, известный алгоритм Евклида для нахождения наибольшего общего делителя двух целых чисел). До определенного времени математика обходилась интуитивными представлениями об алгоритмах как точных предписаниях, определяющих вычислительный процесс, позволяющий на основе исходных данных получить искомый результат. Роль и место алгоритмов в математике впервые в явном, но все еще довольно расплывчатом виде были сформулированы в 20-е годы XX в. в работах голландского математика Л.