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

Министерство образования и науки Российской Федерации Федеральное агентство по образованию Южно-Уральский государственный университет Кафедра «Электронные вычислительные машины» 51 (07) Е804 С. С. Ершов ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ Учебное пособие Челябинск Издательский центр ЮУрГУ 2009  УДК 510. 5 (075. 8) Е804 Одобрено учебно-методической комиссией приборостроительного факультета Рецензенты: Г. Э. Бауэр, Л. А. Полякова. Ершов, С. С. Е804 Элементы теории алгоритмов: учебное пособие/ С. С. Ершов. — Челябинск: Издательский центр ЮУрГУ, 2009. — 64 с. В пособии рассматриваются общие особенности теории алгоритмов, а также конкретные алгоритмические системы, такие как «Рекурсивные функции», «Машины Поста и Тьюринга», «Нормальные алгоритмы Марко- ва» и т. п. В соответствии с предметом дисциплины «Математическая логи- ка и теория алгоритмов». Для студентов специальности 230101 («Вычислительные машины, комплексы, системы и сети») и направления 010400 («Информационные технологии»), а также для студентов родственных специальностей и на- правлений. УДК 510. 5 (075. 8) ©Издательский центр ЮУрГУ, 2009. 2  ВВЕДЕНИЕ Понятия, определения и термины теории алгоритмов в какой-то степени наследуют соответствующим категориям теории множеств. И если там можно было говорить: «Множества, только множества и ничего, кроме множеств», то и здесь, имея в виду, что алгоритмы, в конце концов, тоже множества, можно говорить: «Алгоритмы, только алгоритмы и ничего, кроме алгоритмов». Так подчеркивается безграничная, фактически, общ- ность рассматриваемых далее вопросов. В вычислительной технике, кроме широко известных понятий hardware (жесткое, аппаратное обеспечение), software (мягкое, программное обеспе- чение), иногда предлагается третье обеспечение — brainware (алгоритми- ческое обеспечение). В конце концов, разработка алгоритмов предшествует процессу практи- ческого программирования. И различают: язык алгоритмический и язык программирования (сугубо конкретный). Далее рассмотрены разнообразные алгоритмические системы. Однако, как, к сожалению, выясняется, существуют и принципиально (алгоритми- чески) не разрешимые проблемы (п. 9). Таким образом, здесь проявляет се- бя значимая общефилософская сторона теории алгоритмов. 3  1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ 1. 1. Термин «алгоритм» и первичное определение алгоритма Главное понятие, определяющее название теории алгоритмов, обязано своим появлением математику–узбеку аль-Хорезми («из Хорезма»), форма- лизовавшему в IX веке 4 действия десятичной арифметики [2, 4, 7, 8]. Итак, «алгоризм», «алгорисмус» (1747 г. ), алгорифм (1950 г. ) и, наконец, алгоритм нестрого определяются как конечная совокупность точно сфор- мулированных правил для решения некоторого класса задач [1].