ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и математика»
Соликамск
2011
УДК 51
ББК 22.1я73
Б 39
Учебное издание
БЕЗУСОВА Татьяна Алексеевна
Рецензенты: <...> Основные
подходы к формализации алгоритма [Текст] : учебное пособие / Т. А. Безусова. <...> В пособии рассмотрены различные подходы к
формализации понятия алгоритм: машина Тьюринга, алгоритмы Маркова, рекурсивные функции. <...> © Т. А. Безусова, 2011
© ГОУ ВПО «Соликамский государственный
педагогический институт», 2011
2
ТЕОРИЯ АЛГОРИТМОВ. <...> ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
.
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и Математика»
Зав. <...> Для освоения дисциплины
«Теория алгоритмов» используются знания, умения и виды
деятельности, сформированные в ходе изучения таких
дисциплин, как «Алгебра», «Математический анализ»,
«Теория функций действительного переменного», «Теория
чисел». <...> Цель дисциплины – формирование систематизированных знаний в области теории алгоритмов, ознакомление с общими свойствами алгоритмов, с математическими
уточнениями интуитивного понятия алгоритма, с алгоритмически неразрешимыми проблемами; развитие алгоритмического мышления, алгоритмической культуры, алгоритмической интуиции. <...> Для достижения данной цели необходимо решить следующие задачи:
– сформировать представление об интуитивном понятии алгоритма и понимание необходимости его математического уточнения;
– изучить основные математические уточнения понятия алгоритма: частично-рекурсивные функции, машины
Тьюринга и нормальные алгоритмы Маркова;
– построить примеры алгоритмически неразрешимых
проблем в теории алгоритмов;
4
М* - потенциальное бесконечное множество слов алфавита М. <...> Ограничением функции ｆ на множестве Х называется
функция с областью определения Х ∩Ｄｏｍ(ｆ), значение <...>
Теория_алгоритмов._Основные_подходы_к_формализации_алгоритма.pdf
УДК 51
ББК 22.1я73
Б 39
Рецензенты:
В. Н. Кобзев, кандидат физико-математических наук,
профессор кафедры математических и естественнонаучных
дисциплин филиала Уральского государственного экономического
университета в г. Березники.
Л. Г. Шестакова, кандидат педагогических наук, доцент
кафедры математики и физики Соликамского государственного
педагогического института.
Б 39
Безусова, Т. А. Теория алгоритмов. Основные
подходы к формализации алгоритма [Текст] : учебное пособие
/ Т. А. Безусова. – Соликамск : издательство Соликамского
государственного педагогического института,
2011. – 72 с.
В пособии рассмотрены различные подходы к
формализации понятия алгоритм: машина Тьюринга,
алгоритмы Маркова, рекурсивные функции.
Пособие ориентировано на студентов 3-4 курсов
математических факультетов педагогических вузов,
обучающихся по специальности «Математика
и информатика» и «Информатика и математика».
УДК 51
ББК 22.1я73
Рекомендовано к изданию решением редакционно-издательского
совета СГПИ от 20.10.2010, протокол №16.
© Т. А. Безусова, 2011
© ГОУ ВПО «Соликамский государственный
педагогический институт», 2011
.
Зав. РИО
Редактор
Корректор
Макет и компьютерная верстка
Дизайн обложки
Л. В. Малышева
Л. Г. Абизяева
Л. В. Кравченко
А. М. Вахрушевой
А. М. Вахрушевой
ТЕОРИЯ АЛГОРИТМОВ.
ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и Математика»
Учебное издание
БЕЗУСОВА Татьяна Алексеевна
Сдано в набор 14.12.2010 г. Подписано в печать21.02.2011 г.
Бумага для копировальной техники. Формат 60х84/16.
Гарнитура «Arial». Печать цифровая.
Усл. печ. листов 4,2. Тираж 50 экз. Заказ № 257.
Отпечатано в редакционно-издательском отделе
ГОУ ВПО.
«Соликамский государственный педагогический институт»
618547, РОССИЯ, Пермский край
г. Соликамск, ул. Северная, 44.
2
63
Стр.2
Примерные вопросы к экзамену
1. Алгоритмы в математике. Основные черты алгоритмов.
2. Формализация понятия алгоритма. Необходимость уточнения
понятия алгоритма.
3. Массовые проблемы. Классификация. Примеры.
4. Обобщенные критерии оценки качества алгоритма, понятие
трудоемкости алгоритма.
5. Числовые функции и алгоритмы их вычисления.
6. Алгоритмы Маркова.
7. Конструктивное двоичное кодирование.
8. Двоичное моделирование машин Тьюринга.
9. Понятие вычислимой функции, разрешимого множества.
10. Частично рекурсивные функции и рекурсивные предикаты.
Класс частично рекурсивных функций.
11. Базисные функции. Операторы подстановки, примитивной
рекурсии, минимизации.
12. Рекурсивные предикаты.
13. Кусочное задание функции.
14. Машины Тьюринга. Понятие машины Тьюринга Операции
с машинами. Тезис Черча-Тьюринга.
15. Рекурсивные и рекурсивно-перечислимые множества.
16. Универсальная функция. Теорема Клини.
17. Неразрешимые алгоритмические проблемы. Алгоритмическая
сводимость.
18. Композиция машин Тьюринга. Основные теоремы.
19. Тезис Тьюринга. Функции, вычислимые по Тьюрингу.
20. Алгоритмически неразрешимые проблемы.
21. Понятие сложности алгоритма.
22. Отличие алгорифмов Маркова от МТ.
23. Понятие рекурсии и рекурсивное задание функции.
24. Отличие машины Поста от МТ.
25. Конечные автоматы. Способы задания.
26. Геделева нумерация МТ.
62
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ………………………………………………………….4
1. ПОНЯТИЕ АЛГОРИТМА. МАССОВЫЕ ПРОБЛЕМЫ.......8
1.1. Неформальное понятие алгоритма...........................8
1.2. Формализация понятия «алгоритм»........................12
1.3. Массовые проблемы.
Сложность массовых проблем........................................13
2. МАШИНА ТЬЮРИНГА.....................................................18
3. НОРМАЛЬНЫЕ АЛГОРИТМЫ (алгорифмы) МАРКОВА 30
4. РЕКУРСИВНЫЕ ФУНКЦИИ ............................................33
5.1 Общие сведения........................................................33
5.2. Понятие простейших функций.................................34
5.2.1. Оператор суперпозиции..................................35
5.2.2. Оператор примитивной рекурсии..................35
5.2.3. Оператор минимизации ..................................36
5.2.4. Ограниченный оператор минимизации..........36
5.3. Примитивно-рекурсивные и частично-рекурсивные
функции ...........................................................................37
5.4. Типы рекурсивных алгоритмов................................38
ЗАКЛЮЧЕНИЕ.....................................................................41
СПИСОК ЛИТЕРАТУРЫ......................................................42
ПРИЛОЖЕНИЯ....................................................................43
Тест № 1 «Основные понятия теории алгоритмов»......43
Тест № 2 «Машина Тьюринга».......................................45
Тест № 3 «Нормальные алгоритмы Маркова» ..............48
Тест № 4 «Рекурсивные функции».................................52
Тест № 5 «Некоторые вопросы теории алгоритмов» ........55
Тест № 6 «Сложность вычисления»...Ошибка! Закладка
не определена.
Тест № 7 «Эффективные операции на множество
частичных функций»Ошибка! Закладка не определена.
Тест № 8 «Вычислимость и разрешимость».......Ошибка!
Закладка не определена.
Тест № 9 «Машина с неограниченными регистрами»
..................................Ошибка! Закладка не определена.
Общие сведения..............................................................60
Примерные вопросы к экзамену.....................................62
3
Стр.3