close

Вход

Забыли?

вход по аккаунту

?

1401.Теория алгоритмов

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Соликамский государственный педагогический институт»
Т. А. Безусова
ТЕОРИЯ АЛГОРИТМОВ.
ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и математика»
Соликамск
2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 51
ББК 22.1я73
Б 39
Учебное издание
БЕЗУСОВА Татьяна Алексеевна
Рецензенты:
В. Н. Кобзев, кандидат физико-математических наук,
профессор кафедры математических и естественнонаучных дисциплин филиала Уральского государственного экономического университета в г. Березники.
Л. Г. Шестакова, кандидат педагогических наук, доцент кафедры математики и физики Соликамского государственного педагогического института.
Б 39
Безусова, Т. А. Теория алгоритмов. Основные
подходы к формализации алгоритма [Текст] : учебное пособие / Т. А. Безусова. – Соликамск : издательство Соликамского государственного педагогического института,
2011. – 72 с.
В пособии рассмотрены различные подходы к
формализации понятия алгоритм: машина Тьюринга, алгоритмы Маркова, рекурсивные функции.
Пособие ориентировано на студентов 3-4 курсов
математических факультетов педагогических вузов, обучающихся по специальности «Математика
и информатика» и «Информатика и математика».
УДК 51
ББК 22.1я73
Рекомендовано к изданию решением редакционно-издательского
совета СГПИ от 20.10.2010, протокол № 16.
© Т. А. Безусова, 2011
© ГОУ ВПО «Соликамский государственный
педагогический институт», 2011
2
ТЕОРИЯ АЛГОРИТМОВ.
ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
.
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и Математика»
Зав. РИО
Редактор
Корректор
Макет и компьютерная верстка
Дизайн обложки
Л. В. Малышева
Л. Г. Абизяева
Л. В. Кравченко
А. М. Вахрушевой
А. М. Вахрушевой
Сдано в набор 14.12.2010 г. Подписано в печать21.02.2011 г.
Бумага для копировальной техники. Формат 60х84/16.
Гарнитура «Arial». Печать цифровая.
Усл. печ. листов 4,2. Тираж 50 экз. Заказ № 257.
Отпечатано в редакционно-издательском отделе
ГОУ ВПО.
«Соликамский государственный педагогический институт»
618547, РОССИЯ, Пермский край
г. Соликамск, ул. Северная, 44.
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Примерные вопросы к экзамену
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
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВВЕДЕНИЕ
Курс теории алгоритмов для математических специальностей педагогических вузов, наряду с другими математическими дисциплинами, относится к тем дисциплинам,
которые формируют у студента-математика математическую культуру и создают вместе с такими дисциплинами,
как математическая логика, базу для понимания математики в общенаучном контексте. Для освоения дисциплины
«Теория алгоритмов» используются знания, умения и виды
деятельности, сформированные в ходе изучения таких
дисциплин, как «Алгебра», «Математический анализ»,
«Теория функций действительного переменного», «Теория
чисел». Дисциплина «Теория алгоритмов» является теоретической основой понимания общих свойств алгоритмов,
изучаемых в других математических дисциплинах.
Цель дисциплины – формирование систематизированных знаний в области теории алгоритмов, ознакомление с общими свойствами алгоритмов, с математическими
уточнениями интуитивного понятия алгоритма, с алгоритмически неразрешимыми проблемами; развитие алгоритмического мышления, алгоритмической культуры, алгоритмической интуиции.
Для достижения данной цели необходимо решить следующие задачи:
– сформировать представление об интуитивном понятии алгоритма и понимание необходимости его математического уточнения;
– изучить основные математические уточнения понятия алгоритма: частично-рекурсивные функции, машины
Тьюринга и нормальные алгоритмы Маркова;
– построить примеры алгоритмически неразрешимых
проблем в теории алгоритмов;
4
М* - потенциальное бесконечное множество слов алфавита М.
М+ - М* / { α}, без пустого слова.
Область определения функции f(x) - это множество
вида{х/f(x) определенно}.
Обозначение: Domf(x) или Dom(f).
Множество значений функции f(x) – это множество
вида{f(x) / х принадлежит Dom(f) }. Обозначение:
Ram(f).
Ограничением функции f на множестве Х называется
функция с областью определения Х ∩Dom(f), значение
которой х принадлежит Х ∩Dom(f) совпадает с f(x).
Обозначение: f\ Х.
В теории алгоритмов преимущественно имеют дело с
функцией от натуральных чисел. Функция fиз Nn называется n- местной.
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) при установлении конструктивного неоднозначного
соответствия между множеством конструктивных объектов
А и некоторым множеством М натуральных чисел;
4) правильного ответа нет.
23. Абстрактная модель устройства, функционирующего в дискретное время, которая перерабатывает
последовательные входные и выходные сигналы и превращает их в последовательность выходных сигналов,
называется:
1) М П;
2) М Т;
3) автомат;
4) все ответы верные.
Общие сведения
Множество будем обозначать заглавными латинскими
буквами А, В, С, … То, что х и у являются элементами
множества, записывается в виде х, у  М.
N - множество натуральных чисел, N+ - множество положительных натуральных чисел.
Алфавит – конечное линейно упорядоченное множество некоторых объектов.
М = { m 0, m 1, …, m i }, где m i– буква.
Слова будем записывать греческими буквами α… (α =
m1 m2 m3 m4).
Под длиной слова будем понимать количество букв в
этом слове.
Слова записываются на стандартном носителе, разделенной на клетки ленты.
α
α
m1
m2
m3
Пустые буквы, которые не видны.
60
m4
– познакомить с некоторыми алгоритмически неразрешимыми проблемами не из теории алгоритмов.
В соответствии с примерной программой, разработанной УМО по педагогическому образованию, процесс изучения дисциплины направлен на формирование следующих
специальных компетенций:
– владение основными положениями классических
разделов математической науки, базовыми идеями и методами математики, системой основных математических
структур и аксиоматическим методом;
– владение культурой математического мышления, логической и алгоритмической культурой, способность понимать общую структуру математического знания, взаимосвязь между различными математическими дисциплинами,
реализовывать основные методы математических рассуждений на основе общих методов научного исследования и
опыта решения, учебных и научных проблем, пользоваться
языком математики, корректно выражать и аргументировано обосновывать имеющиеся знания;
– способности понимать универсальный характер законов логики математических рассуждений, их применимость в различных областях человеческой деятельности,
роль и место математики в системе наук, значение математической науки для решения задач, возникающих в теории и практике, общекультурное значение математики;
– владение математикой как универсальным языком
науки, средством моделирования явлений и процессов, способность пользоваться построением математических моделей для решения практических проблем, понимать критерии
качества математических исследований, принципы экспериментальной и эмпирической проверки научных теорий;
– владение содержанием и методами элементарной
математики, умение анализировать элементарную математику с точки зрения высшей математики;
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
– способность ориентироваться в информационном
потоке, использовать рациональные способы получения,
преобразования, систематизации и хранения информации,
актуализировать ее в необходимых ситуациях интеллектуально-познавательной деятельности;
– владение основными положениями истории развития математики, эволюции математических идей и концепциями современной математической науки.
В результате изучения дисциплины студент должен
знать:
– важнейшие свойства алгоритмов в математике;
– математические уточнения понятия алгоритма и вычислимой функции;
– примеры неразрешимых алгоритмических проблем
из теории алгоритмов и других разделов математики;
– основные алгоритмические характеристики множеств;
уметь:
– грамотно формулировать алгоритмические проблемы;
– строить алгоритмы, разрешающие и перечисляющие
известные арифметические множества;
– доказывать рекурсивность простейших арифметических функций, предикатов и множеств;
– строить алгоритмы Тьюринга, вычисляющие простейшие арифметические функции;
владеть:
– методом сведения для доказательства алгоритмической неразрешимости проблем.
В процессе изучения данной дисциплины студенты
сталкиваются с тем, что учебный материал находится в
разных источниках, написан сложным математическим
языком. Поэтому при работе над пособием автор старался
совместить строгость изложения основных понятий с доходчивостью восприятия.
которое множество натуральных чисел есть само множество
натуральных чисел;
2) отображение g некоторого множества натуральных
чисел на множество конструктивных объектов Е;
3) нумерация (кодирование) программ в теории вычислений;
4) нумерация объектов множества Е, являющаяся и
сюръекцией, и инъекцией.
6
59
20. Что показывает теорема о двоичном моделировании?
1) в теории МТ нельзя ограничиться рассмотрением
только МТ, работающих в унарном алфавите;
2) в теории МТ нельзя ограничиться рассмотрением
только МТ, работающих в двоичном алфавите;
3) в теории МТ можно ограничиться рассмотрением
только МТ, работающих в унарном алфавите;
4) в теории МТ можно ограничиться рассмотрением
только МТ, работающих в двоичном алфавите.
21. Конструктивными объектами являются (выберите только один ответ):
1) конечные объекты;
2) объекты, имеющие конечное число частей с некоторой, присущей только этим объектам, системой координат,
позволяющей различать их части;
3) записываемые в определенной системе счисления
натуральные числа и линейно упорядоченные конечные
последовательности натуральных чисел;
4) все ответы правильные.
22. В каком случае говорят о том, то осуществлена
арифметизация множества А и числа n из множества М?
1) при установлении конструктивного взаимно однозначного соответствия между множеством конструктивных объектов А и некоторым множеством М натуральных чисел;
2) при установлении конструктивного однозначного
соответствия между множеством конструктивных объектов
А и некоторым множеством М натуральных чисел;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) функцию построения по числу «нуль» как угодно
большого отрезка множества натуральных чисел;
2) функцию «непосредственно следующее натуральное число»;
3) функции суперпозиции и примитивной рекурсии;
4) функции введения фиктивных переменных.
16. Класс частично-рекурсивных функций есть:
1) транзитивное замыкание множества базисных функций относительно операторов суперпозиции функции,
примитивной рекурсии и μ-оператора;
2) всюду
определенная
примитивно-рекурсивная
функция;
3) транзитивное замыкание множества базисных функций относительно операторов суперпозиции функции и
примитивной рекурсии;
4) правильного ответа нет.
17. Найдите форулировку-1 в терминах статьи Поста:
1) существует финитный 1-процесс, что будучи применимым к натуральному n в качестве исходной конфигурации ящиков, он задает n-ую конкретную проблему;
2) финитный 1-процесс для общей проблемы есть одно решение, если ответ для каждой конкретной проблемы
правильны;
3) если общая проблема 1-задана 1-разрешима, то,
соединяя наборы инструкций по заданию проблемы ее
решения, мы получаем ответ по номеру проблемы;
4) программа (набор инструкций в терминах Поста)
является одной и той же для всех конкретных проблем,
соотнесена с общей проблемой.
Теоретический материал по каждому разделу сопровождается примерами, приводятся задания для самостоятельной работы, тест. При написании учебного пособия широко
использовались книги, указанные в списке литературы, без
специальных ссылок на них в тексте пособия.
Пособие содержит введение, четыре раздела, заключение и приложение. В первом разделе рассмотрены основные понятия теории алгоритмов и необходимость математического определения алгоритма. Разобраны понятия массовой проблемы, алгоритмически неразрешимых
проблем теории алгоритмов, введено понятие вычислительной сложности алгоритмов. Во втором разделе дано
описание машин Тьюринга, рассмотрены способы их представления, операции над машинами Тьюринга, В третьем
разделе представлены основные понятия теории алгоритмов Маркова; в четвертом – рекурсивные функции, понятие простейших функций и приемы построения сложных
арифметических функций с помощью операций суперпозиции, примитивной рекурсии и минимизации.
В приложении приводятся варианты тестов по разным
разделам теории алгоритмов, а также по темам, которые не
представлены в пособии.
В пособии изложены только основные подходы к формализации понятия «алгоритм». Заметим, что это лишь
часть тем, которые необходимо освоить студентам в рамках указанной дисциплины.
18. Укажите наиболее важное, на ваш взгляд, отличие
М.П. от МТ
19. Отметьте верное определение однозначной Геделевой нумерации объектов множества Е, где Е – множество конструктивных объектов:
1) нумерация объектов множества Е в случае, когда не58
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. ПОНЯТИЕ АЛГОРИТМА.
МАССОВЫЕ ПРОБЛЕМЫ
1.1. Неформальное понятие алгоритма
Понятие «алгоритм» принадлежит к числу основных
понятий математики и занимает одно из центральных мест
в организации вычислительных процессов и в проектировании разнообразных дискретных устройств.
Еще в IX веке ученый Мухаммед бен-муса альХорезми разработал систему правил четырех арифметических действий над числами в десятичной позиционной
системе счисления. Эти правила предписывали строгую
последовательность действий для получения искомого результата. Так возникло понятие «алгоритм» в честь арабского имени аль-Хорезми.
Позднее это название было принято для обозначения
совокупности правил вычислительных процессов, в которых
искомые результаты практических задач находят последовательно из исходных данных по определенным правилам и
инструкциям.
Процесс создания компьютерной программы для решения какой-либо практической задачи включает в себя
формализацию этой задачи, разработку вычислительного
алгоритма её решения, написание и отладку программы,
решение поставленной задачи.
С точки зрения современной практики, алгоритм – это
программа, а критерием алгоритмичности процесса является возможность ее запрограммировать.
Если алгоритм используется для вычисления значения числовой функции, то эта функция называется эффективно вычислительной, или вычислимой.
Следует различать:
1) описание алгоритма (программа);
2) механизм реализации алгоритма (компьютер);
3) процесс реализации алгоритма (последователь8
3) одна ячейка ленты МТ;
4) одно слово α из алфавита М.
12. Выберите из предложенных утверждений формулировку тезиса Тьюринга:
1) вычислимые по Тьюрингу функции могут быть частично определенными;
2) любой вербальный алгоритм в алфавите М может
быть реализован некоторой МТ, работающей над алфавитом М;
3) МТ является одной из возможных формализаций содержательного представления о вербальных алгоритмах;
4) все ответы правильные.
13. Отметьте основные компоненты, которые задают нормальный алгорифм N:
1) произвольный алфавит М, в котором
N, и слова этого алфавита;
2) произвольный алфавит М, в котором
N, и пустое слово;
3) произвольный алфавит М, в котором
N, и список подстановок;
4) произвольный алфавит М, в котором
N, пустое слово λ и список подстановок.
работает НА
работает НА
работает НА
работает НА
14. Найдите ошибочное отличие алгорифмов Маркова
от алгоритмов Тьюринга:
1) алгоритмы Тьюринга являются вербальными, алгорифмы Маркова – не вербальные;
2) МТ обладает свойством локальности, НА свойством
локальности не обладает;
3) теории НА и алгоритмов Тьюринга строятся на основе разных планов и используют разную терминологию;
4) пустая буква не входит в алфавит М, в котором работает алгорифм N.
15. Множество базисных функций, используемых при
построении класса примитивно-рекурсивных функций,
включает:
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4) общий метод, позволяющий решить любую задачу
этой проблемы.
6. Продолжите тезис формализации:
«Любой содержательно описанный алгоритм…»
7. Перечислите формализации понятия алгоритм,
предложенные в терминах А. М. Тьюринга, Э. Поста,
А. Черча и С. К. Клини, А. А. Маркова, соответственно.
8. Пусть дано некоторое множество М, состоящее из
элементов a, b, c,… Является ли множество М разрешимым, если:
1) существует алгоритм, по которому можно упорядочить все элементы данного множества;
2) перечислимо само множество, но его дополнение
не перечислимо;
3) для любого слова х алфавита данного множества
можно определить, входит ли данное слово х в это множество;
4) не перечислимо само множество, но его дополнение перечислимо.
ность шагов, которые выполняются при применении
алгоритма к конкретным данным).
Пример: Дана последовательность Р из n положительных чисел. Требуется упорядочить их и построить последовательность R, в которой эти числа располагаются в
порядке возрастания.
1. Ищем в Р наименьшее число.
2. Найденное число приписываем с право в R и вычеркиваем его из Р.
3. Если в Р нет чисел, то переходим к шагу 4 в противном случае – к шагу 1.
4. Конец. Результатом считается последовательность R.
Блок-схема алгоритма
Связи между шагами можно изобразить в виде графа.
нет
Начало
Шаг 1
Шаг 2
9. Какие из предоставленных утверждений являются
верными:
1) одна и та же буква может входить в слово только
один раз;
2) слово может входить в другое слово несколько раз;
3) операция конкатенации слов α и β выполняется
приписыванием к слову α справа слова β;
4) верных ответов нет.
10. Изобразите схематически взаимоотношение массовых проблем В и С, где В – массовая проблема, сведенная к массовой проблеме С, и С* - некоторое подмножество задач массовой проблемы С.
11. Укажите вид, в котором хранятся исходные данные, решаемые машиной Тьюринга задачи, все промежуточные и конечные результаты:
1) алфавит М;
2) лента МТ;
56
Шаг 3
Конец
да
Граф, в котором вершины соответствуют шагам, а ребра
– переходам между шагами, называется блок-схемой. Вершины, из которых выходит 1 ребро – операторы, 2 ребра – логические условия, или предикаты. Описание алгоритма – это
граф, а процесс реализации – это путь в графе.
Отметим несколько общих черт алгоритмов (основных
требований):
Дискретность алгоритма – процесс последовательного построения величин, идущий в дискретном времени;
Детерминированность алгоритма – система величин,
получаемых в какой-то неначальный момент времени, однозначно определяющийся системой величин, полученных в
предшествующие моменты времени;
Элементарность шагов алгоритма – закон получения
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
последующей системы величин из предшествующей, который должен быть простым и локальным;
Результативность алгоритма – если способ получения последующей величины из какой-нибудь заданной
величины не дает результата, то должно быть указано, что
считается результатом алгоритма;
Массовость алгоритма – начальная система величин
может выбираться из некоторого потенциально бесконечного множества.
Нестрогое понятие алгоритма принято обозначать как
интуитивное понятие алгоритма.
Алгоритм как программа компьютера
Вход
Выход
S
1) содержит единственный вход в функциональный блок;
2) содержит единственный выход;
3) не содержит бесполезных фрагментов;
4) не содержит бесконечных циклов.
Схема следования:
Вход
S1
S2
..…
Sn
10
1. Назовите логическую среду, в которой строится
теория алгоритмов.
2. Понятие функции в теории алгоритмов вводится
двумя способами, отметьте их:
1) определяется множество простейших функций с
нужными свойствами – базис дальнейших построений;
2) искомый класс вычислимой функции определяется
как транзитивное замыкание множества базисных функций
относительно рассматриваемых операторов построения новых функций;
3) вначале определяется понятие алгоритма А как процесса определенного вида, ведущего от варьируемых исходных данных m к результату l, т. е. l = A(m). Затем каждый такой
алгоритм А объявляется функцией, определенной на множестве тех m, к которым он применим;
4) непосредственно строится класс функций, объявляемых вычислимыми, и понятие алгоритма отождествляется с понятием вычислимой функции, реализующей этот
алгоритм при некоторой нумерации рассматриваемых
объектов.
3. Сформулируйте определение неформализованного
понятия «алгоритм».
4. Соотнесите характерные черты алгоритмов:
А. Общие.
В. Выделенные А. А. Марковым:
1) детерминированность; 4) элементарность шага;
2) универсальность;
5) массовость;
3) результативность;
6) дискретность.
5. Алгоритм, решающий массовую проблему – это:
n
Si – производимая обработка,
Выход
ТЕСТ № 5 «Некоторые вопросы теории алгоритмов»
.
1) частный метод, позволяющий решить любую задачу
этой проблемы;
2) общий метод, позволяющий решить только одну задачу этой проблемы;
3) частный метод, позволяющий решить только одну
задачу этой проблемы;
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
х-1
12. Чему будет равно значение функции f{x) = 2
1
a) 0 ;
b) ½;
в нуле?
Схема развилки:
Т
c) 0".
S1
у
13. Примитивно-рекурсивная функция fехр(х,у) = х определяется схемой:
Р
Вход
Выход
a) fexp (х, 0) = 0', fехр(x,y +1)
b) fexp(x,O)=O, fexp(x,y +1) =
c) fexp (x, 0) = 0', fexp (х, у +1) = f.(fexp(x, у), 0');
d) fexp (x, 0) = 0', fexp (х, у +1) = f+( fexp(x,y),U11(x)).
= f.(fexp(x,y),U12(x))
f.( x,y), U 11(x));
F
14. Является ли функция Аккермана А{х) прими-тивнорекурсивной?
S2
Схема повторения:
а) цикл пока (с предусловием)
F
a) Да;
b) Нет.
15. Функции Ро, P1 связаны следующими соотношениями:
Вход
Р0(а, х) = а + х,
Рх(а, 1) = а,
Рг(а, х) = ах,
Р1(а, х+1) = Р0(а, Р1(а, х)).
Чему равно Р1(2, 3)?
a) 4;
b) 5;
c) 6.
Р
Т
S
б) цикл до (с постусловием)
16. Определенность в вычислении простейших функ-
Вход
S
n
рекурсии
и
Т
Р
Выход
F
ций 0, х + 1, U m и полная заданность в действиях операторов суперпозиции, примитивной
оператора – это требование:
Выход;
-
a) массовости;
b) детерминированности;
c) результативности.
Вход
54
S
S
Р
11
Выход.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.2. Формализация понятия «алгоритм»
Формализация понятия алгоритма – это описание
стандартной, универсальной формы записи информации и
ограниченного, четко определённого набора простейших
элементарных действий человека по её переработке, необходимых и достаточных для реализации любого содержательно описанного алгоритма.
Выделяют три основных подхода к формализации:
– машину Тьюринга – связывает понятие алгоритма
с механическим устройством, способным выполнять строго
фиксированное множество элементарных действий над
простейшими символами;
– рекурсивные функции – связывает понятие алгоритма с элементарными вычислительными операциями на
множестве целых положительных чисел;
– нормальный алгоритм Маркова – связывает понятие алгоритма с элементарными преобразованиями
слов произвольного алфавита, замещая части слова или
все слово другим словом.
В теории вычислительных алгоритмов доказана сводимость одного типа формализации (модели) к другому,
т.е. всякий алгоритм, описанный средствами одной модели, может быть описан также средствами другой.
В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение
теории алгоритмов осуществляется как в использовании
самих результатов, так и в обнаружении новых понятий и в
уточнении старых.
В теории алгоритмов принят подход, основанный на
конкретной алгоритмической модели, в которой все черты
алгоритмов выполняются очевидным образом. Основные
типы алгоритмических моделей различаются трактовками
понятия алгоритма.
12
7. Поставить в соответствие:
a)  ;
b) Snm;
c) Rn;
d) X1;
e) Unm.
1) оператор минимизации;
2) оператор суперпозиции;
3) оператор примитивной рекурсии;
4) функция следования;
5) функция проекции;
6) оператор тождества.
8. Верно ли, что оператор примитивной рекурсии Rn
определяет n-местную функцию f через (n+1)-местную
функцию g (n+2)-местную функцию n?
а) нет;
b) да.
9. Какие значения будут у оператора суперпозиции
для функции f(x1, х2) = h(gx(x1, х2, х3), gi(x1, х2, x3))?
a) S22;
b) R2; c) S32;
d) S32; e) S23.
10. Поставить в соответствие:
a) H1(x1, х2, х3) = f(x3, x2> х1);
b) h2(x) = f{x, x);
c) h3(x1 х2, х3) = f(x2, х3)
1) циклическая перестановка аргументов;
2) отождествление;
3) добавление фиктивных переменных;
4) перестановка аргументов.
11. Числа натурального ряда можно получить с помощью:
a) константы 0 и функции следования;
b) функции следования и оператора проекции;
c) константы 0, функции следования и оператора проекции;
d) константы 0 и оператора минимизации.
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕСТ № 4 «Рекурсивные функции»
1. Среди требований к алгоритмам одно лишнее:
a) простота;
b) детерминированность;
c) дискретность;
d) результативность.
2. Среди перечисленных средств описания примитивно-рекурсивных функций одно лишнее:
a) оператор минимизации;
b) оператор суперпозиции;
c) оператор примитивной рекурсии;
d) константа 0;
e) функция следования;
g) функция проекции.
3. Частично-рекурсивная функция называется общерекурсивной, если она:
a) всюду определена;
b) может быть получена с помощью константы 0,
функции следования и оператора проекции;
c) все ответы верные.
4. Чему равно значение функции проекции:
5
U 2(x1,x2,x3,x4,x5) ?
a) x2;
b) 2;
c) 5;
d) x5.
5. Примитивно-рекурсивная функция J(x) = х -1 определяется схемой:
a) f (0) = 0, f (1) = 0, f (х + 1) = f (х) + 1;
b) f (0) = 1, f (1) = 0, f (х + 1) =х;
c) f (0) = 0, f (х+1) = f (х)-1.
6. Всякая эффективно вычислимая функция частично-рекурсивна. Это высказывание принадлежит:
a) Черчу;
b) Тьюрингу;
52
с) Раису.
1 тип: трактует алгоритм как некоторое детерминированное устройство, способное выполнять в каждый
момент лишь строго фиксированное множество операций.
Основной теоретической моделью такого типа является
машина Тьюринга.
2 тип: связывает понятие алгоритма с традиционным
представлением – процедурами вычисления значения числовых функций. Основной моделью являются рекурсивные функции.
3 тип: преобразование слов в произвольных алфавитах, в которых операциями являются замены кусков слов
другими словами. Основной моделью является алгоритмы
Маркова.
1.3. Массовые проблемы.
Сложность массовых проблем
Под массовой проблемой будем понимать бесконечное множество однотипных задач. Алгоритм, решающий
массовую проблему – это общий метод, позволяющий решать любую задачу этой проблемы. Чаще всего массовая
проблема – это задача с варьируемыми исходными данными. Выбор задачи из массовой проблемы осуществляется указанием исходных данных этой задачи.
Рассмотрим понятие вычислительной сложности
решения задачи алгоритмом. Затраты труда и время решения пропорциональны числу повторений цикла (многократное повторение одинаковых действий). Очевидно, что
при разных исходных данных задачи различны и являются
функцией от исходных данных. Чем объемнее задача массовой проблемы, тем больше будут сложность выполнения
и число действий, необходимых для ее решения. Для того
чтобы сделать рассмотрения более конкретными, введем
число r, характеризующее размеры задач массовой проблемы. Например, в решении системы n простейших ли13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нейных уравнений с n неизвестными и в вычислении определителя n-го порядка r=n.
Рассматривая массовые проблемы P={z}, где z – задача размера r (Обозначение: [Z,r] P). Имеется множество
алгоритмов А={A} – решение массовой проблемы P. Каждый алгоритм А работает дискретным образом, тактами.
Вычислительной сложностью алгоритма А при решении
задач [Z,r]  P в наиболее простом случае является число
шагов для получения ответа.
Для записи вычислительной сложности используется
обозначение n=WSA ([Z,r]) . Связь между r и сложностью
WS прямо пропорциональная.
Пример 1: Имеются 4 алгоритма: A1, A2, A3, A4. Решение задачи z со следующими сложностями:
WS A1 Z , r   r ,
WS A2 Z , r   r 2 ,
WS A3 Z , r   r 3 ,
WS A 4 Z , r   2 r.
Под сложностью WSA будем понимать число единиц
времени, требующихся для решения задачи размера r.
Единицей времени может являться, например, миллисекунда (10-3 с.)
Ai
A1
A2
A3
A4
WSAi
([Z,r])
r
r2
r3
2r
Максимальный размер задачи
1 с.
1000
31
10
9
14
1 мин.
6·104
244
39
15
1 ч.
3,6·106
1897
15321
21
c) abbbbb;
d) алгоритм неприменим к данному слову.
12. Операция над упорядоченной парой слов (Р, Q) называется:
a) марковской подстановкой;
b) результатом применения марковской подстановки;
c) схемой нормального алгоритма.
13. Функция f, заданная на некотором множестве слов
алфавита А, называется нормально вычислимой, если:
a) найдется такое расширение В данного алфавита А (А
 В) и такой нормальный алгоритм в В, что каждое слово Р
в алфавите А из области определения функции / этот алгоритм перерабатывает в слово f(P);
b) найдется такой нормальный алгоритм в А, что каждое слово Р в алфавите А из области определения функции f этот алгоритм перерабатывает в слово f(Р);
c) существует схема нормального алгоритма, вычисляющая эту функцию.
14. Верно ли, что функции f{x) = х + 1 и 
но вычислимы?
3(x)
нормаль-
a) да;
b) нет.
15. Какое из высказываний не является истинным?
a) проблема определения общерекурсивности алгоритмов разрешима;
b) универсальный алгоритм существует;
c) не существует общего алгоритма для отладки программ;
d) частный случай алгоритмически неразрешимой
проблемы разрешим.
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
b)
c)
.
8. Нормальный алгоритм определяет схема:
a)
.
9. Что получится в результате применения данного к
слову 11?
a) 1111;
b) 111111;
c) 11111;
d) 11.
10. Что получится в результате подстановки (  , ма)
в слово:
«мапа»?
a) Мамапа;
b) па;
c) мапама;
d) мапа.
Рассмотрим понятие сложности массовых проблем. Пусть имеется массовая проблема P, каждая задача z которой имеет определённый размер r и множество алгоритмов А={A} для её решения. Решение задачи z размера r имеет вычислительную сложность WSA
([Z,r]). Если при решении задачи алгоритмами A1 и A2
WS A1 Z , r   WS A2 Z , r , то алгоритм A1 «лучше» A2.
Под сложностью Sr  массовой проблемы P понимается вычислительная сложность WSA0 ([z0,r]) решения
наилучшим алгоритмом A0  А своих наиболее трудных
задач z0  P.
Сложностью массовой проблемы называется функция S(r), определённая равенствами S[Z,A,r]=WSA([Z,r]);
S A, r   max S Z , A, r  ; S[r]=minAS[A,r].
Z , r 
Пусть алгоритмом А решается множество задач [Z,r]
массовой проблемы, имеющих один и тот же размер. Оценка
размеров задач одним числом r не позволяет учесть все
особенности исходных данных и процессов решения этих
задач. Поэтому разные задачи одного и того же размера r
будут иметь различные вычислительные сложности.
В соответствии со вторым условием определения со
сложностью S[A,r] алгоритмом А может быть решена любая задача массовой проблемы r.
WSA ([Z,r])≤ S[A,r].
11. Нормальный алгоритм определяет схема:
Что получится в результате применения данного алгоритма к слову abbbb?
a) bbbb;
b) aaaaa;
50
Для каждого алгоритма А имеются наиболее трудные
задачи. При решении задач массовой проблемы P различными алгоритмами будут получаться различные оценки
S[A,r]. Для различных алгоритмов наиболее трудоёмкими
будут различные задачи. Очевидно, что для лучших алгоритмов имеет место S(r)=S(A0,r).
Сложность S(r) массовой проблемы рассматривается
как функция размера задач r.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Классификация массовых проблем по их сложности:
1. Проблемы, сложность которых пропорциональна r или
меньше S(r) ≤ Cr. Например, проверка планарности графа1.
2. Проблемы, сложность которых полиноминальна
S(r)  p k (r ) . Например, вычисление определителей, решение систем линейных уравнений.
3. Проблемы, сложность которых не больше, чем экспоненциальная, для которых не известны алгоритмы решения полиномиальной сложности, но не доказано, что
таких алгоритмов нет S(r)  exp(r ) . Например, разложение
натурального числа на простые множители.
4. Проблемы, сложность которых не меньше, чем экспоненциальная S(r)  exp(r ) .Например, проблемы порождения всех перестановок их r элементов, всех циклов или остовов графа.
Примеры решения задач
Пример 2. Составить алгоритм Евклида нахождения
наибольшего делителя двух чисел.
1. Обозначь большее число через n, меньшее m.
2. Найди выражение числа n через число m по формуле n = lm + p, где 0  p <m.
3. Если p = 0, то работа алгоритма окончена. НОД равен
значению m.
4. Если p  0, положим n:=m, m:=p.
5. Переходи к выполнению пункта 2.
3. Что получится в результате марковской подстановке (пано, рама) в слово «панорама»?
a) рамарама;
b) панопано;
c) панорама;
d) рама.
4. Восстановить правильную последовательность
команд схеме алгоритма, определяющего, делится число
в унарной системе на 3 или не делится.
a)   1 ;
b) 111   ;
c) 1  ;
d) 11  .
5. Если А и В — два алфавита, причем A
 В, то:
a) алфавит В называется расширением алфавита A;
b) алфавит А называется расширением тем алфавита B;
c) алфавит В содержится в А;
d) нет верного ответа.
6. Поставить в соответствие:
a) (Р, Q);
b) Р  Q;
c) Р   Q;
1) заключительная подстановка;
2) формула подстановки;
3) схема нормального алгоритма;
4) упорядоченная пара слов.
7. В процессе работы алгоритма получилась следующая последовательность:
badca  bdca  bdc  dc  d    
Выбрать соответствующую схему.
1
Граф называется планарным, если его можно изобразить на плоскости
так, что его рёбра не пересекаются.
16
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c) считывание и запись символов, сдвиг на
ячейку влево или вправо, а также переход
управляющего устройства в следующее состояние;
1) детерминированность машины;
2) данные машины Тьюринга;
3) память машины Тьюринга;
4) элементарные шаги машины.
17. Что является исходными данными машины Т2 для
композиции машин Т2(Т1)?
a) система команд машины Т1;
b) система команд машины Т2;
c) результат работы машины Т1;
d) результат работы машины Т2.
18. Пусть функция f(a) задана описанием: «пока истинно Р(а), вычислять g(a), иначе f(a) = g2(a)». Тогда f(а) называется:
a) композицией;
b) развилкой;
c) повторением.
ТЕСТ № 3 «Нормальные алгоритмы Маркова»
1. Какая из трех основных алгоритмических моделей занимается переработкой слов в произвольных алфавитах?
a) нормальные алгоритмы Маркова;
b) рекурсивные функции;
c) машины Тьюринга.
2.Функция вычислима машиной Тьюринга тогда и
только тогда, когда она частично-рекурсивна. Это высказывание:
a) Тьюринга-Чёрча;
b) Тьюринга;
c) Чёрча.
48
Вопросы для самоконтроля
1. Каковы основные требования к алгоритмам?
2. Назовите различия между описанием алгоритма,
механизмом реализации алгоритма и процессом реализации алгоритма.
3. Каковы отличия в основных типах универсальных
алгоритмических моделей?
4. Являются ли тождественными понятия «вычислительная сложность» и «сложность массовой проблемы»?
Назовите, в чем их сходство или отличие?
5. Зависит ли сложность массовой проблемы от того,
какие действия алгоритма при решении задач считаются
основными?
Упражнения
Во всех заданиях необходимо разработать схемы алгоритмов и проанализировать процесс реализации алгоритма,
т.е. последовательность шагов, которая будет порождена
при применении алгоритма к конкретным исходным данным.
1. Разработать словесные алгоритмы вычитания из некоторого числа А последовательности n чисел b1, b2, ..., bn:
а) алгоритм вычисления по формуле:
C = (...((A - b1) - b2) - ... - bn)
б) алгоритм вычисления по формуле: С  А 
n
b
i 1
i
.
2. Разработать алгоритм поиска максимального (минимального) элемента из последовательности, заданной в
виде одномерного массива А = {a1, a2, ... , ak}.
3. Разработать алгоритм определения количества
одинаковых чисел в последовательности, заданной в виде
одномерного массива А = {a1, a2, . . . , ak}.
4. Разработать алгоритм умножения матрицы на вектор.
5. Разработать алгоритм умножения матрицы на матрицу.
6. Разработать алгоритм транспонирования матрицы.
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. МАШИНА ТЬЮРИНГА
Понятие алгоритма было предложено в 1936 году математиком А. М. Тьюрингом.
Часто формой записи информации в формализованном
алгоритме являются слова в алфавитах. Какова бы не была
массовая проблема, всегда можно её описать в виде переработки слов в некотором специальном алфавите.
Алгоритмы, перерабатывающие слова в алфавитах,
называются вербальными. Исходные данные задач, решаемые вербальными алгоритмами, задаются одним словом, обозначающимся 0. Работа вербальных алгоритмов
осуществляется тактами, в каждом из которых имеющееся
слово i перерабатывается в новое слово i+1:
 ….
Заключительное слово , после получения которого
работа алгоритма прекращается, называется ответом к
задаче.
Устройство и функционирование машины Тьюринга (МТ)
МТ состоит из следующих элементов:
1. Ленты, разбитой на ячейки и бесконечной в обе
стороны. В каждой ячейке может быть записан один из
символов конечного алфавита, называемого внешним алфавитом.
2. Управляющего устройства, которое находится в одном из конечного числа внутренних состояний:
Q´= {q0, q1, q2,…, qn}.
Число элементов Q´ характеризует объём внутренней
памяти машины. Во множестве Q´ выделены два специальных состояния: q0 = $ и q1, называемые заключительным (конечным) и начальным состоянием соответственно.
18
c) pk;
d) q1;
e) q0;
1) направление сдвига головки;
2) машинное слово;
3) состояние управляющего устройства;
4) символ из алфавита А;
5) конечное состояние управляющего устройства;
6) начальное состояние управляющего устройства;
7) текущая конфигурация.
13. Что получится в результате выполнения следующей последовательности команд?
Q11  q11R
Q1   q11R
а) машина остановится, поставив вторую 1;
b) машина остановится, все стирая;
c) машина не остановится, заполняя ленту 1.
14. В текущей конфигурации a1 ak qi a j a2 выполнена
команда qi aj  qi' aj' L. Какая конфигурация получится в
результате выполнения данной команды?
a) a1 ak a'j q' i a2;
b) a1 q'i ak a' i a2;
c) a1 ak q'j a'ja2.
15. Функция f называется вычислимой по Тьюрингу,
если:
a) для f существует правильная система команд;
b) для f существует машина Т, которая ее
вычисляет;
c) нет верного ответа.
16. Поставить в соответствие:
a) слова в алфавите ленты;
b) конечное множество состояний и ленту;
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Какой алгоритм реализован следующей машиной
Тьюринга (в унарной системе)?
Q1*  qz*E
Q11  q2  R
Q21  q21R
Q2*  q31L
Q31  q31L
Q3   qz  R
a) вычисление функции f(x) x + 1;
b) вычитание двух чисел;
c) сложение двух чисел;
d) вычисление функции f(x) x - 1.
8. Какая из машин Тьюринга вычисляет функцию f(x) =
х + 1 (в унарной системе)?
а) Q11  qz  R;
b) Q11  q11L, Q1   qz1E;
c) Q11  q21L, Q2   q11E.
9. Внутренняя память машины Тьюринга – это:
a) лента;
b) конечное множество состояний;
c) нет верного ответа.
10. Внешняя память машины Тьюринга – это:
a) лента;
b) конечное множество состояний;
c) нет верного ответа.
11. Машинное слово, обозначаемое a1qiа2, называется:
a) системой команд;
b) конфигурацией или полным состоянием;
c) нет верного ответа.
12. Поставить в соответствие:
a) aj;
b) qi;
46
3. Считывающей (пишущей) головки, которая может
перемещаться вдоль ленты и в каждый момент времени
обозревать одну из ячеек ленты.
Структура работы машины Тьюринга
Каждая машина имеет свой алфавит:
М = {m0, m1,…, mn}, где n≥2.
Исходные данные решаемой МТ задачи, все промежуточные и окончательные результаты хранятся в машине на
ленте в виде одного слова  в алфавите М. Для каждой
ячейки ленты известны соседние с ней слева и справа
ячейки.
m1
В ячейку ленты может быть записана одна буква алфавита М, которая хранится там неограниченно долго до записи в этой ячейке новой буквы. Ячейка ленты находится в
состоянии записанной в ней буквы.
В каждом такте работы машины её головка находится в
некоторой ячейке ленты и может:
 прочитать имеющуюся в ячейке букву;
 записать в ячейку новую букву, предварительно стерев старую;
 по поступившему от устройства управления указания сдвинуться вдоль ленты в соседнюю ячейку влево или
вправо.
Для передачи головке указаний о сдвиге имеется
стандартный для всех машин алфавит:
P = {┘, ↓,└ }
┘– поворот налево
↓ – на месте
└ – поворот направо.
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алфавиты машины Тьюринга
Q´= {$, q1, q2,…, qn }
Q = {q1, q2,…, qn }
М = {m0, m1,…, mn }
m0 = λ (пустая буква)
P = {┘, ↓, └ }
M∩Q = Ø, M∩P = Ø, Q∩P = Ø.
Работа МТ
Во всех тактах, кроме нулевого и конечного, машина
последовательно выполняет следующие действия:
1. Головка считывает в обозреваемой ячейке ленты
букву mi и передает ее в устройство управления.
2. Устройство управления, получившее букву mi, зная
свое внутреннее состояние qs и руководствуясь определенными правилами, находит свое новое состояние: qs 
Q, рi  P¸ mi  M.
3. Символы mi и Pi передаются устройством управления головке.
4. Головка расписывает букву mi в обозреваемую ею
ячейку и после этого, руководствуясь символом рi¸ сдвигается по ленте на одну ячейку вправо или влево, или остается на месте.
5. Устройство управления переходит в новое состояние qs.
Правила, по которым МТ по буквам qi и mi находит буквы qs¸ ms¸ ps, называются функциональной схемой машины.
Формально эта схема задается всюду определенными
на декартовом множестве Q×M функциями:
qj m i → qs m s p s.
Каждая МТ имеет свой алфавит, но в алфавитах всех
машин имеется специальная буква λ – пустая буква. Тогда
М = {λ, m1, m2, …, mi}.
Будем предполагать, что перед началом работы машины лента пуста, то есть во всех ячейках пустые буквы.
Все элементы, появляющиеся в процессе работы машины,
не содержат пустой буквы.
20
ТЕСТ № 2 «Машина Тьюринга»
1. Машина Тьюринга – это:
a) алгоритм, позволяющий решать транспортные задачи;
b) устройство, представленное в виде бесконечной ленты, управляющего устройства и головки;
c) набор команд, определяющих ее состояние в
каждый конкретный момент.
2. Система правил
q i aj  q' i a' i dk описывает:
a) конфигурацию;
b) полное состояние;
c) последовательность шагов.
3. Натуральные числа в машине Тьюринга представляются:
a) в унарном коде;
b) в двоичном коде;
c) в троичном коде.
4. Можно ли построить универсальную машину Тьюринга?
a) да;
b) нет.
5. Можно ли построить универсальную машину Тьюринга с двумя символами на ленте и двумя состояниями?
а) да;
b) нет.
6. Смысл проблемы остановки (с точки зрения программирования) заключается в следующем:
a) существует алгоритм воспроизведения работы по заданному алгоритму;
b) не существует алгоритма, который бы по номеру алгоритма определял результат;
c) не существует общего алгоритма для отладки
программ;
d) нет верного ответа.
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Поставить в соответствие. Если для всех х, у, z  А
имеет место:
a) иррефлексивность;
b) транзитивность,
то R называется:
1)
2)
3)
4)
отношением эквивалентности;
отношением порядка;
частичным порядком;
n-местным отношением.
Порядок выполнения нулевого такта
8. Поставить в соответствие:
a) следование;
b) развилка;
c) повторение;
1) служит для выбора одной из двух альтернатив;
2) управление передается от одного функционального блока к следующему;
3) управление передается от одного функционального блока к другому и обратно;
4) используется для многократно повторяющегося
действия.
9. Какая структура изображена на схеме?
вход
a)
b)
c)
d)
s
P T
F
выход
цикл-до;
цикл-пока;
структура, эквивалентная структуре цикл-пока;
развилка.
44
Замечание: во время работы МТ во всех ячейках ленты, не занятых словом α, записана пустая буква λ. Когда
головка МТ в процессе работы движется вдоль ленты, то
символ λ будет являться признаком конца заданного на
ленте слова.
Каждая МТ предназначена для решения задач определенной массовой проблемы. Каждую задачу этой проблемы будет решать машина, определяемая словом 0.
1. Исходное слово α0 записывается на ленту.
2. Головка машины устанавливается так, что она обозревает ячейку, содержащую первую букву слова α0.
3. Устройство управления переводится в начальное
состояние q1.
4. Машина выполняет первый такт.
Ситуация, когда в начале работы машины ее головка
обозревает ячейку с первой буквой исходного слова α0, а
устройство управления находится в начальном состоянии
q1, называется стандартной начальной конфигурацией.
Порядок выполнения конечного такта
Конечный такт работы наступает тогда, когда устройство управления машины переходит в конечное внутреннее состояние $. Переходя в это состояние, МТ останавливается. Находящееся на ленте в конечном такте слово
k считывается с ленты и является кодом ответа.
Стандартная конечная конфигурация – это ситуация,
при которой головка МТ обозревает ячейку, содержащую
первую букву находящегося на ленте слова k . Конечная
конфигурация - $k , начальная конфигурация - q1α0.
Конфигурация – это информация, полностью определяющая работу МТ в данном такте. Она включает сведения:
– о слове , имеющемся на ленте,
– о положении головки на ленте относительно слова ,
– о состоянии q, в котором находится устройство
управления.
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 3:
α=abcde. Устройство управления находится в состоянии
q и обозревает ячейку с буквой d: abcqde. Если же головка
обозревает первую слева или справа пустую ячейку, то запись конфигурации имеет вид: qλabcde (или abcdeq). Возникающая при работе МТ последовательность конфигураций
будем называть протоколом работы машины. Для того чтобы
МТ могла решать задачи массовой проблемы, надо задать:
- алфавиты М, Q;
- способ кодирования словами алфавита М информации, включая исходные данные;
- функциональную схему машины.
Алфавит Р является стандартным для всех МТ. Способы кодирования информации в каждой массовой проблеме свои.
Рассмотрим способы задания функциональной схемы.
Функции, отражающие работу МТ, зависят от двух переменных, и пробегают значения множества М и Q.
q1
...
qs
...
Qn
λ
m1
...
ms
...
mn
qs ps ms
Конечное внутреннее состояние $ не включено в первый столбец таблицы. При записи функциональных таблиц
конкретных машин используются следующие сокращения.
Если внутреннее состояние qs, в котором находится машина, совпадает с исходным значением qi (qs=qi), то в этом
случае qs можно не писать. Аналогично для ms. Если в процессе работы машины не встретится qi mi, в котором устройство управления находится в состоянии qi, а головка
МТ обозревает ячейку с буквой mi, то соответствующая
клетка остается пустой. Заметим, что при создании функциональной таблицы отдельно алфавиты Q и M можно не
вписывать, так как они входят в состав таблицы.
22
ПРИЛОЖЕНИЯ
ТЕСТЫ
ДЛЯ ОРГАНИЗАЦИИ КОНТРОЛЯ ЗНАНИЙ СТУДЕНТОВ
ТЕСТ № 1 «Основные понятия теории алгоритмов»
1. Множество {х | f(x) определено} – это:
a) множество значений функции f ;
b) область определения функции f;
c) ограничение функции f.
2. Если из х, у  Dom(f) и х
функция называется:

у следует f(x)
 f(y), то
a) инъективной;
b) сюръективной;
c) биективной.
3. Функция f из А в В называется сюръективной, если:
а) Dom(f) = A;
b) Ran(f) =B;
c) Dom(f) = Ran(f).
4. Поставить в соответствие. Функция f называется:
a) инъективной;
b) сюръективной;
1) если из х, у  Dom(f) и х  у следует f(x)  f(y);
2) если Ran(f) ) =B;
3) Dom(g) =Ran(f) и g(f(x)=x).
5. Множество f
-1
(Y) = {x | f(x)  У} называется:
a) прообразом Y относительно f;
b) ограничением функции f на множестве Y;
c) продолжением функции f.
n
6. Функция f из N в N, область определения которой
n
не обязательно совпадает с N , называется ...
a) n-местной функцией;
b) частичной функцией;
c) тотальной функцией.
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СПИСОК ЛИТЕРАТУРЫ
1. Бильгаева, Н. Ц. Теория алгоритмов, формальных
языков, грамматик и автоматов : учебное пособие
[Текст] / Н. Ц. Бильгаева. – Улан-Удэ : Изд-во
ВСГТУ, 2000. – 51 с.
2. Верещагин, Н. К. Математическая логика и теория
алгоритмов. Вычислимые функции [Текст] / Н. К.
Верещагин, А. Шень. – М. : МЦНМО, 2008. – 193 с.
3. Верещагин, Н. К. Начала теории множеств. Математическая логика и теория алгоритмов [Текст] / Н. К.
Верещагин, А. Шень. М. : МЦНМО, 2008. – 128 с.
4. Игошин, В. И. Задачи и упражнения по математической логике и теории алгоритмов [Тест] / В. И. Игошин. – М. : Академия, 2007. – 304 с.
5. Матрос, Д. Ш. Теория алгоритмов : учебник [Текст] /
Д. Ш. Матрос, Г. Б. Поднебесова. – М. : БИНОМ. Лаборатория знаний, 2008. – 202 с.
6. Пономарев, В. Ф. Основы теории алгоритмов : учебное пособие [Текст] / В. Ф. Пономарев. – Калининград : Изд-во КГТУ, 2005. – 53 с.
7. Фалевич, Б. Я. Теория алгоритмов : учебное пособие
[Текст] / Б. Я. Фалевич. – М. : Машиностроение, 2004.
– 160 с.
8. Шелупанов, А. А. Математическая логика и теория алгоритмов : учебное пособие для вузов
[Тест] / А. А. Шелупанов А. А., В. М. Зюзьков. –
М. : Академия, 2008. – 176 с.
42
Другим способом задания функциональной таблицы
МТ является выписывание списка всех соотношений вида
qimj → qsms ps. Эти соотношения называются списком команд. Команды с пустой правой частью, соответствующие
пустым клеткам функциональной таблицы, в список команд не включаются.
При решении задач на МТ вся исходная и текущая
информация кодируется на ленте одним словом в некотором алфавите. Например, если в задаче используются десятичные числа, то достаточно алфавита: М1={0,1, …,9}.
Но если приходится оперировать одновременно двумя
числами m и n, то для их изображения в виде самого слова
нужен разделительный знак (*). Тогда М2={*}  M1.
Введение дополнительных букв в исходный алфавит
может потребоваться и для формулировки алгоритма решения задач.
О ситуации, когда задача формулируется в алфавите
М1, а решается машиной, работающей в более широком
алфавите М2, говорят, что МТ работает над алфавитом М1.
Может оказаться, что не все слова в алфавите М2 имеют
смысл в решаемой машиной задаче.
Примеры машин Тьюринга
1. Машина Т1 работает в алфавите М={λ,0,1}. Множество внутренних состояний Q={q1,q2}.
Функциональная схема:
q1
q2
λ
1П
1П
0
$
1П
Список команд:
q1λ→1П
q10→$
q11→q2П
q2λ→1П
q20→1П
q21→П.
23
1
q2П
П
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. МТ с внешним алфавитом А={α0,1} определяется
программой :
А\Q
α0
1
q1
q2α0└
q1└
q2
q2α0└
q31└
q3
q0α0
q31└
Остановится ли когда-нибудь эта машина, если она
перерабатывает слово: а)1111; б) 11111; в)
111111? В начальный момент в состоянии q1 машина обозревает ячейку с самой левой буквой. Если остановка происходит, то какое слово получается и какая ячейка обозревается?
ЗАКЛЮЧЕНИЕ
Всякий алгоритм можно рассматривать как некоторое
универсальное средство для решения целого класса задач. Но существуют такие классы задач, для решения которых нет общего универсального алгоритма. Проблемы
решения такого рода задач называются алгоритмически
неразрешимыми. Однако алгоритмическая неразрешимость проблемы решения задач того или иного класса не
означает невозможность решения любой частной задачи
из этого класса. Переход от интуитивного понятия алгоритма к формальному определению алгоритма позволяет
доказать алгоритмическую неразрешимость ряда проблем.
Конструирование машин Тьюринга
Создание (синтез) машин Тьюринга (т.е. написание
соответствующих программ) является задачей значительно более сложной, нежели процесс применения данной
машины к данным словам.
Пример 4. Попытаемся построить такую машину Тьюринга, которая из п записанных подряд единиц оставляла
бы на ленте (n – 2) единицы, также записанные подряд,
если n > 2, и работала бы вечно, если n = 0 или n = 1.
В качестве внешнего алфавита возьмем двухэлементное множество А = {0,1}. Количество необходимых внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать
из начального положения, когда в состоянии q1 обозревается крайняя правая единица из n записанных на ленте.
Начнем с того, что сотрем первую единицу, если она
имеется, перейдем к обозрению следующей левой ячейки
и сотрем там единицу, если она в этой ячейке записана.
На каждом таком переходе машина должна переходить в
новое внутреннее состояние, либо в противном случае будут стерты вообще все единицы, записанные подряд.
24
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8. Может ли примитивно-рекурсивная функция быть
частично-рекурсивной?
9. Проверьте выполняются ли основные требования к
алгоритмам в классе частично-рекурсивных функций.
10. Когда частично-рекурсивная функция называется
общерекурсивной?
11. Всякая ли функция, вычислимая некоторым алгоритмом, частично-рекурсивна?
Упражнения
Доказать примитивную рекурсивность следующих функций.
1. Нахождение минимального значения из двух заданных чисел f(x, y) = min(x, y).
2. Нахождение максимального значения из двух заданных чисел f(x, y) = max(x, y).
3. Функция r(x, y) - остаток от деления y на x.
4. Функция q(x, y) - частное от деления y на x.
5. Доказать, что предикат «x делится на n» примитивнорекурсивен для любого n.
6. Доказать, что предикат «x делится на n и m» примитивно-рекурсивен для любых n и m.
7. Доказать, что отношение x1 > x2 примитивнорекурсивно.
8. Доказать, что предикат f(x) = g(x) примитивнорекурсивен, если функции f(x) и g(x) примитивно-рекурсивны.
9. Дано множество слов одинаковой длины, причем первые два слова выделены. Построить цепь от первого выделенного слова ко второму так, чтобы все слова этой цепи
были только из заданного множества. Соседние слова построенной цепи должны отличаться только одной буквой.
10. Дано множество слов. Построить из них кроссворд
заданной конфигурации (число слов может быть больше
требуемого количества для заполнения кроссворда).
40
Запишем команды, осуществляющие описанные действия:
q11→ q20Л; q21→ q30Л.
Машина находится в состоянии q3 и обозревает третью справа ячейку из тех, в которых записано данное слово (n единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние q0, независимо от содержимого ячейки.
Вот эти команды:
q30→ q00; q31→ q01.
Теперь остается рассмотреть ситуации, когда на ленте
записана всего одна единица или не записано ни одной.
Если на ленте записана одна единица, то после первого
шага (выполнив команду q11→ q20Л) машина будет находиться в состоянии q2 и будет обозревать вторую справа
ячейку, в которой записан 0. По условию, в таком случае
машина должна работать вечно. Это можно обеспечить,
например, такой командой:
q20→ q20П.
Выполняя эту команду шаг за шагом, машина будет
двигаться по ленте неограниченно вправо (или протягивать ленту через считывающую головку справа налево).
Наконец, если на ленте не записано ни одной единицы, то
машина, по условию, также должна работать вечно. В этом
случае в начальном состоянии q1 обозревается ячейка с
содержимым 0, и вечная работа машины обеспечивается
следующей командой:
q10→ q10П.
Запишем составленную программу (функциональную
схему) построенной машины Тьюринга в виде таблицы:
Q
A
q1
q2
q3
0
q10П
q20П
q00
1
q00Л
q20Л
q01
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В заключение отметим следующее. Созданная нами
машина Тьюринга может применяться не только к словам в
алфавите А - {0, 1}, представляющим собой записанные
подряд n единиц (n > 2), но применима и ко многим другим
словам в этом алфавите, например, к словам: 1011, 10011,
111011, 11011, 1100111, 1001111, 10111, 10110111,
10010111 и т.д. (исходя из заданного начального положения). С другой стороны, построенная машина не применима (т. е. при подаче этих слов на вход машины она работает вечно) не только к слову «1» или к слову, состоящему
из одних нулей. Она не применима и к следующим словам:
101, 1001, 11101, 101101, 1100101101 и т. д.
Тезис Тьюринга
Любой алгоритм путем анализа и его детальной проработки может быть превращен в алгоритм, перерабатывающий слова в некотором алфавите. МТ является одной из
возможных формализаций содержательного представления
о вербальных алгоритмах. Этот факт формируется в виде
тезиса Тьюринга (конкретизация общего принципа формализации).
Тезис Тьюринга: любой вербальный алгоритм в алфавите М может быть реализован некоторой МТ, работающей над алфавитом М.
Не всегда есть возможность проводить построение
всех интересующих МТ, но, опираясь на тезис, будем считать, что любой алгоритм, описанный нами содержательно, может быть реализован некоторой МТ.
Основные теоремы о машинах Тьюринга
Если две машины в результате работы дают один и
тот же результат, то Т1(α)=Т2(α). Если одна из машин применима к слову α, то есть Т1(α)=y, то и вторая машина к
нему применима и Т2(α)=у.
26
Примеры решения задач
Пример 6. Доказать примитивную рекурсивность
функции f(x, y) = x + y.
Решение. Рассмотрим способ рекурсивного определения данной функции:
f(x, 0) = x,
f(x, y+1) = x + y + 1 = f(x, y) +1.
Чтобы показать соответствие данной рекурсивной
схемы схеме примитивной рекурсии, воспользуемся функциями выбора и следования:
f(x, 0) = x = I(x),
f(x, y+1) = f(x, y) + 1 = S(f(x, y)) = S(I 33 (x, y, f(x, y))).
Пример 7. Доказать примитивную рекурсивность
функции f(x, y) = x ∙ y.
Решение. Рассмотрим способ рекурсивного определения данной функции:
f(x, 0) = 0,
f(x, y+1) = x ∙ (y + 1) = x ∙ y + x = f(x, y) + x, из которого
следует, что Z(x) = x ∙ 0.
Обозначим x ∙ y = p(x, y), тогда:
p(x, 0) = Z(x);
p(x, y+1) = p(x, y) +x = S(p(x, y), x) = S(I 13 (x, y, p(x, y)),
I 33 (x, y, p(x, y))).
Вопросы для самоконтроля
1. Какие функции считаются базисными?
2. В чем особенность действия оператора суперпозиции?
3. В чем особенность действия оператора примитивной рекурсии?
4. Что такое примитивно-рекурсивная функция?
5. Что такое примитивно-рекурсивный оператор?
6. Как действует оператор минимизации?
7. Сформулируйте определение частично-рекурсивной
функции?
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
мизации. Указанные операции могут быть выполнены в
любой последовательности и любое конечное число раз.
Если такие функции оказываются всюду определенными,
то они называются общерекурсивными функциями. Частично-рекурсивные функции вычислимы путем определенной процедуры механического характера. Практически понятием частично-рекурсивных функций пользуются для
доказательства алгоритмической разрешимости или неразрешимости проблем.
Приведем тезис Черча, который связывает понятие
алгоритма и строгое математическое понятие частичнорекурсивной функции.
Тезис Черча: всякий алгоритм может быть реализован частично-рекурсивной функцией.
Утверждение о несуществовании частично-рекурсивной
функции эквивалентно несуществованию алгоритма решения соответствующей задачи.
5.4. Типы рекурсивных алгоритмов
Эффективность разработки рекурсивного алгоритма
определяется наличием некоторых условий:
1) если исходные данные имеют рекурсивную структуру, то процедуры анализа таких структур будут более эффективны, если они сами рекурсивны;
2) если алгоритм обработки некоторого набора данных
построить, разбивая данные на части и обрабатывая в отдельности каждую часть, то из частичных решений можно
получить общее;
3) если по условию задачи необходимо выбрать оптимальный вариант из некоторого множества решений, то
искомое решение может быть найдено через конечное
число шагов.
Поиск решения завершается после окончания данных
либо при нахождении искомого решения на текущем наборе данных.
38
Теорема 1. О композиции МТ
Каковы бы ни были машины Т1 и Т2 в алфавите М, может
быть построена работающая в этом алфавите МТ, такая,
что для всех слов α  M: Т(α)=Т2(Т1(α)).
При конструировании внутренние состояния машин Т1 и
Т2 надо обозначить разными буквами. Заменив в функциональной схеме Т1 переход в заключительное состояние $ переходом на начальное внутреннее состояние Т2, объединяют
таблицы в одну.
Теорема 2. Об объединении МТ
МТ Т заменяет параллельную работу двух имеющихся
машин Т1 и Т2, работающих в алфавитах М1 и М2, не содержащих буквы Δ. Построенная машина Т будет работать
над алфавитом М=М1 U M2 U {Δ}. T(α1Δα2)=T1(α1)ΔT2(α2).
Машину Т1 изменяют так, чтобы она работала в левой
полуленте, то есть сдвигала переработанное слово влево
на одну ячейку каждый раз перед тем, как вписать букву в
ячейку правее нее. Аналогично, машину Т2 изменяют так,
чтобы она работала в правой полуленте. Работа МТ организуется таким образом, что вначале слово α1Δα2 машиной
Т1 перерабатывается в слово Т1(α1)Δ(α2), а затем машиной
Т2 – в слово Т1(α1)ΔТ(α2).
Теорема 3. О разветвлении МТ
Каковы бы ни были работающие в алфавите М машины Т1 и Т2 и машина Т', может быть построена машина Т,
работающая на алфавитом М, такая, что для всех α  M+ :
Т(α)
Т1(α), если Т'(α)=1,
Т2(α), если Т'(α)=0.
Вначале запускается машина Т', и результат ее работы Т'(α) записывается в определенную ячейку. Затем, в
зависимости от того, что записано в этой ячейке, в работу
включаются или машина Т1, или Т2.
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема 4. О циклическом повторении работы МТ
Речь идет о МТ Т, которая многократным повторным
применением машины Т1 строит последовательность слов
α0, α1, … αn, αi=T1(αi-1), до тех пор, пока не будет найдено
первое слово αn, такое, что Т'(αn)=1.
Какова бы ни была машина Т1 в алфавите М, слова
р,q,  M+, и машина Т', может быть построена машина Т,
работающая над алфавитом М, для которой Т(р)=q тогда и
только тогда когда существует конечная последовательность слов α0, α1, … αn  M+, удовлетворяющая условиям :
1) α0=р, αn=q;
2) αi=T1(αi-1), где 0 < i ≤ n;
3) Т'(αi)=0, при 0≤i<n;
4) Т'(αn)=1.
Вопросы для самоконтроля
1. Что такое машина Тьюринга?
2. Назовите способы представления информации в
машине Тьюринга?
3. Существует ли универсальная машина Тьюринга?
4. Всякий ли алгоритм может быть реализован машиной
Тьюринга?
5. С какими алфавитами работает Машина Тьюринга?
Упражнения
1. Машина Тьюринга определяется следующей функциональной схемой:
а0
1

q1
q1 а0П
q2 а0Л
q0 а0
q2
q3 а0П
q2 1Л
q3  Л
q3
q3 а0Л
q4 а0П
q4
q1 а0Л
q4 1П
Определите, в какое слово перерабатывает машина
каждое из следующих слов, исходя из того, что установочная головка стоит на первой справа букве:
28
Данное определение записывается следующим образом:
f(x1, x2, ..., xn) = μ z < U(x) (P(x1, x2, ..., xn, z)).
Ограничение z в ограниченном операторе минимизации
дает гарантию окончания вычислений, поскольку оно оценивает сверху число вычислений предиката P. Возможность
оценить сверху количество вычислений является существенной особенностью примитивно-рекурсивных функций.
5.3. Примитивно-рекурсивные
и частично-рекурсивные функции
Большинство вычислимых функций относится к классу
примитивно-рекурсивных функций.
Функция называется примитивно-рекурсивной, если
она может быть получена из простейших функций с помощью конечного числа операторов суперпозиции и примитивной рекурсии.
Если некоторые функции являются примитивнорекурсивными, то в результате применения к ним операторов суперпозиции или примитивной рекурсии можно получить новые примитивно-рекурсивные функции.
Существует три возможности доказательства того, что
функция является примитивно-рекурсивной:
а) показать, что заданная функция является простейшей;
б) показать, что заданная функция построена с помощью оператора суперпозиции;
в) показать, что заданная функция построена с помощью оператора примитивной рекурсии.
Тем не менее примитивно-рекурсивные функции не
охватывают все вычислимые функции, которые могут быть
определены конструктивно. При построении этих функций
могут использоваться другие операции. Функция называется частично-рекурсивной, если она может быть получена из простейших функций с помощью конечного числа
операторов суперпозиции, примитивной рекурсии и мини37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
только по одной переменной у. Остальные n переменных
x1, x2, ..., xn на момент применения схемы () зафиксированы и играют роль параметров.
5.2.3. Оператор минимизации
а) 11111;
г) 11111111;
2. Для машины Тьюринга, определяемой следующей
функциональной схемой:
Отношение P(x1, x2, ..., xn) называется примитивнорекурсивным, если примитивно-рекурсивна его характеристическая функция:
X(x1,x2,…,xn) =
а0
1
а
в
0, если P(x1 ,x2 ,..., xn ) – «ложь»
1, если P(x1 ,x2 ,..., xn) – «истина»
Предикат называется примитивно-рекурсивным, если
его характеристическая функция примитивно-рекурсивна.
Функция f(x1, x2, ..., xn) получается посредством оператора минимизации из предиката P(x1, x2, ..., xn, z), если в
любой точке значением функции f(x1, x2, ..., xn) является
минимальное значение z, обращающее предикат P(x1, x2,
..., xn, z) в значение «истина»:
f(x1, x2, ..., xn) = μz (P(x1, x2, ..., xn, z)),
где μz – оператор минимизации.
5.2.4. Ограниченный оператор минимизации
Функция f(x1, x2, ..., xn) получается ограниченным оператором минимизации из предиката P(x1, x2, ..., xn, z) и
функции U(x1, x2, ..., xn), если в любой точке значение этой
функции определено следующим образом:
1) для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ...,
xn, z) = «истина», значение функции f(x1, x2, ..., xn) = μz
(P(x1, ..., xn, z));
2) не для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2,
..., xn, z) = «истина», значение функции f(x1, x2, ..., xn) = U
(x1, x2, ..., xn).
36
б) 1111;
в) 11111;
д) 111111111.
q1
q4 а0П
q2 а
q1 аЛ
q1 вЛ
q2
q3 а0Л
q1 в
q2 аП
q2 вП
q3
q1 а0П
q1 1П
q3 1Л
q3 а0Л
q4
q0 а0Л
q1 1Л
q4 а0П
q4 1П
определите для следующих слов, в какое слово перерабатывается каждое из них данной машиной, исходя из
начального положения, при котором машина находится в
состоянии q1 и обозревается указываемая ячейка:
а) 11111 (обозревается ячейка 2, считая слева);
б) 111 (обозревается ячейка 1);
в) 1111111111 (обозревается ячейка 4);
г) 111111 (обозревается ячейка 2).
3. Для машины Тьюринга из задачи 2 запишите функциональную схему в виде сокращенной таблицы, в виде
сокращенной последовательности команд и графа.
4. Проверьте, что машина Тьюринга с внешним алфавитом А {а0 , 1} и программой
q1
q2
q3
а0
*
q1 П
*
q2 П
*
q3 П
1
q3 Л
q3Л
q1Л
*
q1
q0
а0
q4
*
q1 П
q4
*
q2
q5
q01
*
q2 П
q5а0
*
q3
q6
q71
*
q3 П
q6а0
q7
q01
q7П
каждое слово длиной n в алфавите А1 ={1} перерабатывает в слово длиной r, где r – остаток от деления на 3.
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Построить машину Тьюринга для получения следующего натурального числа в унарной системе, т.е. вычислить функцию f(x)=x+1, А={1,  }.
6. Построить машину Тьюринга, которая правильно вычисляет функцию f(x)=x+1 в десятичной системе счисления.
7. Построить машину Тьюринга, которая вычитает единицу из числа в десятичной системе счисления.
8. Даны два набора единиц, разделенные *. Построить
машину Тьюринга, которая выбирала бы больший из этих
наборов, а меньший стирала.
9. Построить машину Тьюринга, которая выполняет деление на два в унарной системе счисления.
3. НОРМАЛЬНЫЕ АЛГОРИТМЫ
(АЛГОРИФМЫ) МАРКОВА
Формализация понятия алгоритма в терминах нормальных алгоритмов (НА) была предложена А. А. Марковым в 1951 году. Благодаря своей простоте и удобству использования НА наряду с МТ и рекурсивными функциями
стали неотъемлемой частью современной теории алгоритмов. Теория нормальных алгоритмов строится по тому
же принципу, что и теория МТ. В ней используется те же
обозначения.
Будем рассматривать слова в произвольном алгоритме. В частности, М1={m1, m2, … mn}. Считается, что пустое
слово λ входит в любое слово α рядом с каждой его буквой.
λ m1 λ m2 λ m3= m1 m2 m3.
Первым вхождением λ в слово Х является вхождение,
находящееся перед первой буквой слова α.
Записи  →τ и   τ, где  , τ  М*, называются подстановками:
 →τ – простой подстановкой;
  τ – заключительной подстановкой.
Слово  называют посылкой подстановки. Говорят,
30
5.2.1. Оператор суперпозиции
Оператором суперпозиции S называется подстановка
в функцию от m переменных m функций от n одних и тех же
переменных. Она дает новую функцию от n переменных.
Например, из функций f(x1, x2, ..., xm), f1(x1, x2, ..., xn), f2(x1, x2,
..., xn), . . ., fm(x1, x2, ..., xn) можно получить новую функцию:
Sm+1(f, f1, f2, ..., fm) = g(x1, x2, ..., xn) = f(f1(x1, x2, ..., xn),
f2(x1, x2, ..., xn), ..., fm(x1, ..., xn)).
При помощи оператора суперпозиции и функции выбора можно выразить любую подстановку функции в функцию.
Например, осуществляя операцию суперпозиции
функций f(x) = 0 и g(x) = x+1, получим функцию: h(x) =
g(f(x)) = 0 + 1 = 1.
При суперпозиции функции g(x) с этой же функцией
получим функцию h(x)= g(g(x)) = x+2.
5.2.2. Оператор примитивной рекурсии
Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию f по двум заданным функциям, одна из которых является n - местной функцией g, а
другая (n+2) - местной функцией h.
Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функций g(x1, x2, ..., xn) и функции
h(x1, x2, ..., xn, y, z), если:
f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);
f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)). ()
Приведенная пара равенств () называется схемой
примитивной рекурсии. Для понимания операции примитивной рекурсии необходимо заметить, что всякую функцию от меньшего числа аргументов можно рассматривать
как функцию от большего числа аргументов. Существенным в операторе примитивной рекурсии является то, что
независимо от числа переменных в f рекурсия ведется
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
располагая слова в порядке возрастания их длин, а слова,
имеющие одинаковую длину, - в произвольном порядке.
После нумерации входных и выходных слов в произвольном алфавитном операторе этот оператор превращается в функцию y = f(x), в которой аргумент х и функция y
принимают неотрицательные целочисленные значения.
Функция f(x) может быть определена не для всех значений
х, а лишь для тех, которые составляют область определения этой функции.
5.2. Понятие простейших функций
Числовые функции, значение которых можно установить посредством некоторого алгоритма, называются вычислимыми функциями.
Для того чтобы описать класс функций с помощью рекурсивных определений, рассмотрим набор простейших
функций:
1) Z(x1, x2, ..., xn) = 0 - нуль-функция, которая определена для всех неотрицательных значений аргумента;
2) s(x) = x+1 - функция непосредственного следования,
также определенная для всех целых неотрицательных значений своего аргумента;
I n ( x ,..., x ,..., x )
m
n
3) m 1
= хm - функция выбора (тождества), повторяющая значения своих аргументов.
Используя простейшие функции в качестве исходных
функций, можно с помощью небольшого числа общих конструктивных приемов строить сложные арифметические
функции. В теории рекурсивных функций особо важное
значение имеют три операции: суперпозиции, примитивной
рекурсии и минимизации.
34
что подстановка активна на α, если ее посылка  входит в
слово α.
Действие «переработка подстановкой слова α» состоит в том, что слово α заменяется на слово р.
Список подстановок – линейно-упорядоченная последовательность подстановок.
Обычно подстановки списка записывают в столбик одну
под другой, считают упорядоченными сверху вниз. Список
подстановок может переработать слово α, если в нем есть
подстановка, активная на слово α. Список просматривается
по порядку, и первая активная на слове α подстановка осуществляет действие переработки слова α. Нормальный алгоритм N задается алфавитом М, в котором он работает, и
списком подстановок.
Отличия Нормальных алгоритмов
от машин Тьюринга.
1. Пустая буква не входит в алфавит М, в котором работает нормальный алгоритм; в нормальном алгоритме λ –
это пустое слово.
2. МТ может перерабатывать любое находящееся на
ленте слово. Для НА возможна ситуация, когда он не может перерабатывать слово.
3. МТ обладают свойством локальности, т. е. на каждом
шаге их работы в имеющемся на ленте слове изменяется не
более одной буквы. НА свойством локальности не обладают.
Сходства НА и МТ
Так же, как МТ, каждый НА предназначен для решения определенной массовой проблемы. Исходные данные
задач кодируются одним словом α 0.
Пример 5. Построить нормальный алгоритм Маркова,
заменив в алфавите А = {a,b,c} все буквы а на с. Используем символ ∆ для расширения алфавита А.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Схема алфавита:
∆ а→с ∆
∆ b→b∆
∆ c→c∆
∆ →∙ 
→∆
Вопросы для самоконтроля
1. Что называется схемой нормального алгоритма?
2. Какие объекты необходимы для задания нормального
алгоритма?
3. Как вы думаете, можно ли «соединить» работу двух
нормальных алгоритмов. Приведите примеры.
4. Всякий ли алгоритм можно реализовать нормальным алгоритмом Маркова?
5. Раскройте понятие «Марковская подстановка».
Упражнения
1. Что получится в результате следующих Марковских
подстановок в слове «апельсин»:
а) (  ,к);
б) (пельс, спир);
в) (ль,  ).
2. Построить нормальный алгоритм Маркова для вычисления функции f(x)=x-1 (x>1) в унарной системе счисления.
3. Построить нормальный алгоритм Маркова для вычисления функции f(x)=x-1 (x>1) в десятичной системе
счисления.
4. Дано слово в алфавите А={a,b,c}. Построить нормальный алгоритм Маркова, присоединяющий слово Q к
данному слову.
5. Построить нормальный алгоритм Маркова, удваивающий слово в унарной системе счисления.
32
6. Построить нормальный алгоритм Маркова, который переворачивает любое заданное слово в алфавите
А = {0,1,2,3}.
7. Дан алфавит А = {a,b,c}. Построить нормальный алгоритм Маркова, заменяющий все а на с в некотором слове.
8. Построить нормальный алгоритм Маркова, который
в слове из алфавита {a,b,c,d,e,f} все вхождения последовательности abc заменяет на символ f.
9. Построить нормальный алгоритм Маркова, который
в слове из алфавита {a,b,c,d,e,f} все символы а заменяет
на f, а все f – на аf.
10. Построить нормальный алгоритм Маркова, который в слове из алфавита {a,b,c,d,e,f} удаляет все вхождения последовательности bc.
4. РЕКУРСИВНЫЕ ФУНКЦИИ
Формализация понятия алгоритма (вычислимой
функции) в терминах рекурсивной функции была предложена в середине 30-х годов в работах Черча («Общерекурсивные функции», 1936 год) и Клини («Частичнорекурсивные функции», 1938 год), которые основывались
на более ранних работах Геделя и Эрбрана.
5.1. Общие сведения
Рекурсией называется способ задания функции, при
котором значение определяемой функции для произвольных значений аргументов выражается известным образом
через значения определяемой функции для меньших значений аргументов.
Применение рекурсивных функций в теории алгоритмов основано на идее нумерации слов в произвольном
алфавите последовательными натуральными числами.
Наиболее просто такую нумерацию можно осуществить,
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
располагая слова в порядке возрастания их длин, а
слова, имеющие одинаковую длину, - в произвольном
порядке.
После нумерации входных и выходных слов в
произвольном алфавитном операторе этот оператор
превращается в функцию y = f(x), в которой аргумент х и
функция y принимают неотрицательные целочисленные
значения. Функция f(x) может быть определена не для всех
значений х, а лишь для тех, которые составляют область
определения этой функции.
5.2. Понятие простейших функций
Числовые функции, значение которых можно
установить
посредством
некоторого
алгоритма,
называются вычислимыми функциями.
Для того чтобы описать класс функций с помощью
рекурсивных определений, рассмотрим набор простейших
функций:
1) Z(x1, x2, ..., xn) = 0 - нуль-функция, которая
определена для всех неотрицательных значений
аргумента;
2) s(x) = x+1 - функция непосредственного следования,
также определенная для всех целых неотрицательных
значений своего аргумента;
I n ( x ,..., x ,..., x )
m
1
m
n
3)
= хm - функция выбора
(тождества), повторяющая значения своих аргументов.
Используя простейшие функции в качестве исходных
функций, можно с помощью небольшого числа общих
конструктивных
приемов
строить
сложные
арифметические функции. В теории рекурсивных функций
особо
важное
значение
имеют
три
операции:
суперпозиции, примитивной рекурсии и минимизации.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5.2.1. Оператор суперпозиции
Оператором суперпозиции S называется подстановка
в функцию от m переменных m функций от n одних и тех же
переменных. Она дает новую функцию от n переменных.
Например, из функций f(x1, x2, ..., xm), f1(x1, x2, ..., xn), f2(x1, x2,
..., xn), . . ., fm(x1, x2, ..., xn) можно получить новую функцию:
Sm+1(f, f1, f2, ..., fm) = g(x1, x2, ..., xn) = f(f1(x1, x2, ..., xn),
f2(x1, x2, ..., xn), ..., fm(x1, ..., xn)).
При помощи оператора суперпозиции и функции
выбора можно выразить любую подстановку функции в
функцию.
Например, осуществляя операцию суперпозиции
функций f(x) = 0 и g(x) = x+1, получим функцию: h(x) =
g(f(x)) = 0 + 1 = 1.
При суперпозиции функции g(x) с этой же функцией
получим функцию h(x)= g(g(x)) = x+2.
5.2.2. Оператор примитивной рекурсии
Оператор примитивной рекурсии Rn позволяет
определить (n+1) - местную функцию f по двум заданным
функциям, одна из которых является n - местной функцией
g, а другая (n+2) - местной функцией h.
Функция f(x1, x2, ..., xn, y) получается оператором
примитивной рекурсии из функций g(x1, x2, ..., xn) и функции
h(x1, x2, ..., xn, y, z), если:
f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);
f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)). ( * )
Приведенная пара равенств ( * ) называется схемой
примитивной рекурсии. Для понимания операции
примитивной рекурсии необходимо заметить, что всякую
функцию от меньшего числа аргументов можно
рассматривать как функцию от большего числа
аргументов. Существенным в операторе примитивной
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
рекурсии является то, что независимо от числа
переменных в f рекурсия ведется только по одной
переменной у. Остальные n переменных x1, x2, ..., xn на
момент применения схемы ( * ) зафиксированы и играют
роль параметров.
5.2.3. Оператор минимизации
Отношение P(x1, x2, ..., xn) называется примитивнорекурсивным, если примитивно-рекурсивна его
характеристическая функция:
X(x1,x2,…,xn) =
0, если P(x1 ,x2 ,..., xn ) – «ложь»
1, если P(x1 ,x2 ,..., xn) – «истина»
Предикат называется примитивно-рекурсивным, если
его характеристическая функция примитивно-рекурсивна.
Функция f(x1, x2, ..., xn) получается посредством
оператора минимизации из предиката P(x1, x2, ..., xn, z),
если в любой точке значением функции f(x1, x2, ..., xn)
является минимальное значение z, обращающее предикат
P(x1, x2, ..., xn, z) в значение «истина»:
f(x1, x2, ..., xn) = μz (P(x1, x2, ..., xn, z)),
где μz – оператор минимизации.
5.2.4. Ограниченный оператор минимизации
Функция f(x1, x2, ..., xn) получается ограниченным
оператором минимизации из предиката P(x1, x2, ..., xn, z) и
функции U(x1, x2, ..., xn), если в любой точке значение этой
функции определено следующим образом:
1) для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2, ...,
xn, z) = «истина», значение функции f(x1, x2, ..., xn) = μz
(P(x1, ..., xn, z));
2) не для любого z < U(x1, x2, ..., xn) такого, что P(x1, x2,
..., xn, z) = «истина», значение функции f(x1, x2, ..., xn) = U
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(x1, x2, ..., xn).
Данное определение записывается следующим образом:
f(x1, x2, ..., xn) = μ z < U(x) (P(x1, x2, ..., xn, z)).
Ограничение z в ограниченном операторе минимизации
дает гарантию окончания вычислений, поскольку оно
оценивает сверху число вычислений предиката P.
Возможность оценить сверху количество вычислений
является
существенной
особенностью
примитивнорекурсивных функций.
5.3. Примитивно-рекурсивные
и частично-рекурсивные функции
Большинство вычислимых функций относится к классу
примитивно-рекурсивных функций.
Функция называется примитивно-рекурсивной, если
она может быть получена из простейших функций с
помощью конечного числа операторов суперпозиции и
примитивной рекурсии.
Если некоторые функции являются примитивнорекурсивными, то в результате применения к ним
операторов суперпозиции или примитивной рекурсии
можно получить новые примитивно-рекурсивные функции.
Существует три возможности доказательства того, что
функция является примитивно-рекурсивной:
а) показать, что заданная функция является простейшей;
б) показать, что заданная функция построена с
помощью оператора суперпозиции;
в) показать, что заданная функция построена с
помощью оператора примитивной рекурсии.
Тем не менее примитивно-рекурсивные функции не
охватывают все вычислимые функции, которые могут быть
определены конструктивно. При построении этих функций
могут
использоваться
другие
операции.
Функция
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
называется частично-рекурсивной, если она может быть
получена из простейших функций с помощью конечного
числа операторов суперпозиции, примитивной рекурсии и
минимизации. Указанные операции могут быть выполнены
в любой последовательности и любое конечное число раз.
Если такие функции оказываются всюду определенными,
то они называются общерекурсивными функциями.
Частично-рекурсивные
функции
вычислимы
путем
определенной процедуры механического характера.
Практически понятием частично-рекурсивных функций
пользуются
для
доказательства
алгоритмической
разрешимости или неразрешимости проблем.
Приведем тезис Черча, который связывает понятие
алгоритма и строгое математическое понятие частичнорекурсивной функции.
Тезис Черча: всякий алгоритм может быть
реализован частично-рекурсивной функцией.
Утверждение о несуществовании частично-рекурсивной
функции
эквивалентно
несуществованию
алгоритма
решения соответствующей задачи.
5.4. Типы рекурсивных алгоритмов
Эффективность разработки рекурсивного алгоритма
определяется наличием некоторых условий:
1) если исходные данные имеют рекурсивную
структуру, то процедуры анализа таких структур будут
более эффективны, если они сами рекурсивны;
2) если алгоритм обработки некоторого набора данных
построить, разбивая данные на части и обрабатывая в
отдельности каждую часть, то из частичных решений
можно получить общее;
3) если по условию задачи необходимо выбрать
оптимальный вариант из некоторого множества решений,
то искомое решение может быть найдено через конечное
число шагов.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поиск решения завершается после окончания данных
либо при нахождении искомого решения на текущем
наборе данных.
Примеры решения задач
Пример 6. Доказать примитивную рекурсивность
функции f(x, y) = x + y.
Решение.
Рассмотрим
способ
рекурсивного
определения данной функции:
f(x, 0) = x,
f(x, y+1) = x + y + 1 = f(x, y) +1.
Чтобы показать соответствие данной рекурсивной
схемы схеме примитивной рекурсии, воспользуемся
функциями выбора и следования:
f(x, 0) = x = I(x),
f(x, y+1) = f(x, y) + 1 = S(f(x, y)) = S(I 33 (x, y, f(x, y))).
Пример 7. Доказать примитивную рекурсивность
функции f(x, y) = x · y.
Решение.
Рассмотрим
способ
рекурсивного
определения данной функции:
f(x, 0) = 0,
f(x, y+1) = x · (y + 1) = x · y + x = f(x, y) + x, из которого
следует, что Z(x) = x · 0.
Обозначим x · y = p(x, y), тогда:
p(x, 0) = Z(x);
p(x, y+1) = p(x, y) +x = S(p(x, y), x) = S(I 13 (x, y, p(x, y)),
I 33 (x, y, p(x, y))).
Вопросы для самоконтроля
1. Какие функции считаются базисными?
2. В чем особенность действия оператора суперпозиции?
3.
В
чем
особенность действия оператора
примитивной рекурсии?
4. Что такое примитивно-рекурсивная функция?
5. Что такое примитивно-рекурсивный оператор?
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. Как действует оператор минимизации?
7. Сформулируйте определение частично-рекурсивной
функции?
8. Может ли примитивно-рекурсивная функция быть
частично-рекурсивной?
9. Проверьте выполняются ли основные требования к
алгоритмам в классе частично-рекурсивных функций.
10. Когда частично-рекурсивная функция называется
общерекурсивной?
11. Всякая ли функция, вычислимая некоторым
алгоритмом, частично-рекурсивна?
Упражнения
Доказать примитивную рекурсивность следующих функций.
1. Нахождение минимального значения из двух
заданных чисел f(x, y) = min(x, y).
2. Нахождение максимального значения из двух
заданных чисел f(x, y) = max(x, y).
3. Функция r(x, y) - остаток от деления y на x.
4. Функция q(x, y) - частное от деления y на x.
5. Доказать, что предикат «x делится на n» примитивнорекурсивен для любого n.
6. Доказать, что предикат «x делится на n и m»
примитивно-рекурсивен для любых n и m.
7. Доказать, что отношение x1 > x2 примитивнорекурсивно.
8. Доказать, что предикат f(x) = g(x) примитивнорекурсивен, если функции f(x) и g(x) примитивно-рекурсивны.
9. Дано множество слов одинаковой длины, причем
первые два слова выделены. Построить цепь от первого
выделенного слова ко второму так, чтобы все слова этой
цепи были только из заданного множества. Соседние слова
построенной цепи должны отличаться только одной буквой.
10. Дано множество слов. Построить из них кроссворд
заданной конфигурации (число слов может быть больше
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
требуемого количества для заполнения кроссворда).
ЗАКЛЮЧЕНИЕ
Всякий алгоритм можно рассматривать как некоторое
универсальное средство для решения целого класса
задач. Но существуют такие классы задач, для решения
которых нет общего универсального алгоритма. Проблемы
решения такого рода задач называются алгоритмически
неразрешимыми.
Однако
алгоритмическая
неразрешимость проблемы решения задач того или иного
класса не означает невозможность решения любой
частной задачи из этого класса. Переход от интуитивного
понятия алгоритма к формальному определению
алгоритма
позволяет
доказать
алгоритмическую
неразрешимость ряда проблем.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.
2.
3.
4.
5.
6.
7.
СПИСОК ЛИТЕРАТУРЫ
Бильгаева, Н. Ц. Теория алгоритмов, формальных
языков, грамматик и автоматов : учебное пособие
[Текст] / Н. Ц. Бильгаева. – Улан-Удэ : Изд-во
ВСГТУ, 2000. – 51 с.
Верещагин, Н. К. Математическая логика и теория
алгоритмов. Вычислимые функции [Текст] / Н. К.
Верещагин, А. Шень. – М. : МЦНМО, 2008. – 193 с.
Верещагин, Н. К. Начала теории множеств.
Математическая логика и теория алгоритмов [Текст]
/ Н. К. Верещагин, А. Шень. М. : МЦНМО, 2008. –
128 с.
Игошин, В. И. Задачи и упражнения по
математической логике и теории алгоритмов [Тест] /
В. И. Игошин. – М. : Академия, 2007. – 304 с.
Матрос, Д. Ш. Теория алгоритмов : учебник [Текст] /
Д. Ш. Матрос, Г. Б. Поднебесова. – М. : БИНОМ.
Лаборатория знаний, 2008. – 202 с.
Пономарев, В. Ф. Основы теории алгоритмов :
учебное пособие [Текст] / В. Ф. Пономарев. –
Калининград : Изд-во КГТУ, 2005. – 53 с.
Фалевич, Б. Я. Теория алгоритмов : учебное пособие
[Текст] / Б. Я. Фалевич. – М. : Машиностроение, 2004.
– 160 с.
8. Шелупанов, А. А. Математическая логика и
теория алгоритмов : учебное пособие для вузов
[Тест] / А. А. Шелупанов А. А., В. М. Зюзьков. –
М. : Академия, 2008. – 176 с.
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ПРИЛОЖЕНИЯ
ТЕСТЫ
ДЛЯ ОРГАНИЗАЦИИ КОНТРОЛЯ ЗНАНИЙ СТУДЕНТОВ
ТЕСТ № 1 «Основные понятия теории алгоритмов»
1. Множество {х | f(x) определено} – это:
a) множество значений функции f ;
b) область определения функции f;
c) ограничение функции f.
2. Если из х, у Î Dom(f) и х
функция называется:
¹ у следует f(x) ¹ f(y), то
a) инъективной;
b) сюръективной;
c) биективной.
3. Функция f из А в В называется сюръективной, если:
а) Dom(f) = A;
b) Ran(f) =B;
c) Dom(f) = Ran(f).
4. Поставить в соответствие. Функция f называется:
a) инъективной;
b) сюръективной;
1) если из х, у Î Dom(f) и х ¹ у следует f(x) ¹ f(y);
2) если Ran(f) ) =B;
3) Dom(g) =Ran(f) и g(f(x)=x).
5. Множество f -1 (Y) = {x | f(x)
Î У} называется:
a) прообразом Y относительно f;
b) ограничением функции f на множестве Y;
c) продолжением функции f.
6. Функция f из Nn в N, область определения которой
не обязательно совпадает с Nn, называется ...
a) n-местной функцией;
b) частичной функцией;
c) тотальной функцией.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Поставить в соответствие. Если для всех х, у, z
имеет место:
ÎА
a) иррефлексивность;
b) транзитивность,
то R называется:
1)
2)
3)
4)
отношением эквивалентности;
отношением порядка;
частичным порядком;
n-местным отношением.
8. Поставить в соответствие:
a) следование;
b) развилка;
c) повторение;
1) служит для выбора одной из двух альтернатив;
2)
управление
передается
от
одного
функционального блока к следующему;
3)
управление
передается
от
одного
функционального блока к другому и обратно;
4) используется для многократно повторяющегося
действия.
9. Какая структура изображена на схеме?
вход
s
P T
выход
F
a)
b)
c)
d)
цикл-до;
цикл-пока;
структура, эквивалентная структуре цикл-пока;
развилка.
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕСТ № 2 «Машина Тьюринга»
1. Машина Тьюринга – это:
a) алгоритм, позволяющий решать транспортные задачи;
b) устройство, представленное в виде бесконечной ленты, управляющего устройства и головки;
c) набор команд, определяющих ее состояние в
каждый конкретный момент.
2. Система правил q aj ® q' a' dk описывает:
i
i
i
a) конфигурацию;
b) полное состояние;
c) последовательность шагов.
3.
Натуральные
представляются:
числа
в
машине
Тьюринга
a) в унарном коде;
b) в двоичном коде;
c) в троичном коде.
4. Можно
Тьюринга?
ли
построить
универсальную
машину
a) да;
b) нет.
5. Можно ли построить универсальную машину
Тьюринга с двумя символами на ленте и двумя
состояниями?
а) да;
b) нет.
6. Смысл проблемы остановки (с точки зрения
программирования) заключается в следующем:
a) существует алгоритм воспроизведения
работы по заданному алгоритму;
b) не существует алгоритма, который бы по
номеру алгоритма определял результат;
c) не существует общего алгоритма для отладки
программ;
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
d) нет верного ответа.
7. Какой алгоритм реализован следующей машиной
Тьюринга (в унарной системе)?
Q1* ® qz*E
Q11 ® q2 l R
Q21 ® q21R
Q2* ® q31L
Q31 ® q31L
Q3 l ® q z l R
a) вычисление функции f(x) x + 1;
b) вычитание двух чисел;
c) сложение двух чисел;
d) вычисление функции f(x) x - 1.
8. Какая из машин Тьюринга вычисляет функцию f(x) =
х + 1 (в унарной системе)?
а) Q11 ® qz l R;
b) Q11 ® q11L, Q1 l ® qz1E;
c) Q11 ® q21L, Q2 l ® q11E.
9. Внутренняя память машины Тьюринга – это:
a) лента;
b) конечное множество состояний;
c) нет верного ответа.
10. Внешняя память машины Тьюринга – это:
a) лента;
b) конечное множество состояний;
c) нет верного ответа.
11. Машинное слово, обозначаемое a1qiа2, называется:
a) системой команд;
b) конфигурацией или полным состоянием;
c) нет верного ответа.
12. Поставить в соответствие:
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a) aj;
b) qi;
c) pk;
d) q1;
e) q0;
1) направление сдвига головки;
2) машинное слово;
3) состояние управляющего устройства;
4) символ из алфавита А;
5) конечное состояние управляющего устройства;
6) начальное состояние управляющего устройства;
7) текущая конфигурация.
13. Что получится в результате
следующей последовательности команд?
выполнения
Q11 ® q11R
Q1 l ® q11R
а) машина остановится, поставив вторую 1;
b) машина остановится, все стирая;
c) машина не остановится, заполняя ленту 1.
14. В текущей конфигурации a1 ak qi a j a2 выполнена
команда qi aj ® qi' aj' L. Какая конфигурация получится в
результате выполнения данной команды?
a) a1 ak a'j q' i a2;
b) a1 q'i ak a' i a2;
c) a1 ak q'j a'ja2.
15. Функция f называется вычислимой по Тьюрингу,
если:
a) для f существует правильная система команд;
b) для f существует машина Т, которая ее
вычисляет;
c) нет верного ответа.
16. Поставить в соответствие:
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a) слова в алфавите ленты;
b) конечное множество состояний и ленту;
c) считывание и запись символов, сдвиг на
ячейку влево или вправо, а также переход
управляющего
устройства
в
следующее
состояние;
1) детерминированность машины;
2) данные машины Тьюринга;
3) память машины Тьюринга;
4) элементарные шаги машины.
17. Что является исходными данными машины Т2 для
композиции машин Т2(Т1)?
a) система команд машины Т1;
b) система команд машины Т2;
c) результат работы машины Т1;
d) результат работы машины Т2.
18. Пусть функция f(a) задана описанием: «пока
истинно Р(а), вычислять g(a), иначе f(a) = g2(a)». Тогда f(а)
называется:
a) композицией;
b) развилкой;
c) повторением.
ТЕСТ № 3 «Нормальные алгоритмы Маркова»
1. Какая из трех основных алгоритмических моделей
занимается переработкой слов в произвольных алфавитах?
a) нормальные алгоритмы Маркова;
b) рекурсивные функции;
c) машины Тьюринга.
2.Функция вычислима машиной Тьюринга тогда и
только тогда, когда она частично-рекурсивна. Это
высказывание:
a) Тьюринга-Чёрча;
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
b) Тьюринга;
c) Чёрча.
3. Что получится в результате марковской
подстановке (пано, рама) в слово «панорама»?
a) рамарама;
b) панопано;
c) панорама;
d) рама.
4. Восстановить правильную последовательность
команд схеме алгоритма, определяющего, делится число
в унарной системе на 3 или не делится.
a) L ® ·1 ;
b) 111 ® L ;
c) 1 ® ·L;
d) 11 ® ·L.
5. Если А и В — два алфавита, причем A Í В, то:
a) алфавит В называется расширением алфавита A;
b) алфавит А называется расширением тем алфавита B;
c) алфавит В содержится в А;
d) нет верного ответа.
6. Поставить в соответствие:
a) (Р, Q);
b) Р Þ Q;
c) Р ® · Q;
1) заключительная подстановка;
2) формула подстановки;
3) схема нормального алгоритма;
4) упорядоченная пара слов.
7. В процессе работы алгоритма
следующая последовательность:
badca ® bdca ® bdc ® dc ® d ® L ® ·
Выбрать соответствующую схему.
16
получилась
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c)
b)
.
8. Нормальный алгоритм определяет схема:
a)
.
9. Что получится в результате применения данного к
слову 11?
a) 1111;
b) 111111;
c) 11111;
d) 11.
10. Что получится в результате подстановки ( L , ма)
в слово:
«мапа»?
a) Мамапа;
b) па;
c) мапама;
d) мапа.
11. Нормальный алгоритм определяет схема:
Что получится в результате применения данного алгоритма к слову abbbb?
a) bbbb;
b) aaaaa;
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c) abbbbb;
d) алгоритм неприменим к данному слову.
12. Операция над упорядоченной парой слов (Р, Q)
называется:
a) марковской подстановкой;
b) результатом применения марковской подстановки;
c) схемой нормального алгоритма.
13. Функция f, заданная на некотором множестве слов
алфавита А, называется нормально вычислимой, если:
a) найдется такое расширение В данного алфавита А (А
Í В) и такой нормальный алгоритм в В, что каждое слово Р
в алфавите А из области определения функции / этот
алгоритм перерабатывает в слово f(P);
b) найдется такой нормальный алгоритм в А, что
каждое слово Р в алфавите А из области определения
функции f этот алгоритм перерабатывает в слово f(Р);
c) существует схема нормального алгоритма,
вычисляющая эту функцию.
14. Верно ли, что функции f{x) = х + 1 и j
нормально вычислимы?
3(x)
a) да;
b) нет.
15. Какое из высказываний не является истинным?
a)
проблема
определения
общерекурсивности
алгоритмов разрешима;
b) универсальный алгоритм существует;
c) не существует общего алгоритма для отладки
программ;
d) частный случай алгоритмически неразрешимой
проблемы разрешим.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕСТ № 4 «Рекурсивные функции»
1. Среди требований к алгоритмам одно лишнее:
a) простота;
b) детерминированность;
c) дискретность;
d) результативность.
2.
Среди
перечисленных
средств
описания
примитивно-рекурсивных функций одно лишнее:
a) оператор минимизации;
b) оператор суперпозиции;
c) оператор примитивной рекурсии;
d) константа 0;
e) функция следования;
g) функция проекции.
3.
Частично-рекурсивная
общерекурсивной, если она:
функция
называется
a) всюду определена;
b) может быть получена с помощью константы 0,
функции следования и оператора проекции;
c) все ответы верные.
4. Чему равно значение функции проекции:
U 52(x1,x2,x3,x4,x5) ?
a) x2;
b) 2;
c) 5;
d) x5.
5. Примитивно-рекурсивная функция J(x) = х -1 определяется схемой:
a) f (0) = 0, f (1) = 0, f (х + 1) = f (х) + 1;
b) f (0) = 1, f (1) = 0, f (х + 1) =х;
c) f (0) = 0, f (х+1) = f (х)-1.
6.
Всякая
эффективно
вычислимая
функция
частично-рекурсивна. Это высказывание принадлежит:
a) Черчу;
b) Тьюрингу;
19
с) Раису.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Поставить в соответствие:
a) m ;
b) Snm;
c) Rn;
d) X1;
e) Unm.
1) оператор минимизации;
2) оператор суперпозиции;
3) оператор примитивной рекурсии;
4) функция следования;
5) функция проекции;
6) оператор тождества.
8. Верно ли, что оператор примитивной рекурсии Rn
определяет n-местную функцию f через (n+1)-местную
функцию g (n+2)-местную функцию n?
а) нет;
b) да.
9. Какие значения будут у оператора суперпозиции
для функции f(x1, х2) = h(gx(x1, х2, х3), gi(x1, х2, x3))?
a) S22;
b) R2; c) S32;
d) S32; e) S23.
10. Поставить в соответствие:
a) H1(x1, х2, х3) = f(x3, x2> х1);
b) h2(x) = f{x, x);
c) h3(x1 х2, х3) = f(x2, х3)
1) циклическая перестановка аргументов;
2) отождествление;
3) добавление фиктивных переменных;
4) перестановка аргументов.
11. Числа натурального ряда можно получить с
помощью:
a) константы 0 и функции следования;
b) функции следования и оператора проекции;
c) константы 0, функции следования и оператора проекции;
d) константы 0 и оператора минимизации.
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
12. Чему будет равно значение функции f{x) = 2х-1 в нуле?
a) 01;
b) ½;
c) 0".
у
13. Примитивно-рекурсивная функция fехр(х,у) = х определяется схемой:
a) fexp (х, 0) = 0', fехр(x,y +1) = f.(fexp(x,y),U12(x))
b) fexp(x,O)=O, fexp(x,y +1) = f.( x,y), U 11(x));
c) fexp (x, 0) = 0', fexp (х, у +1) = f.(fexp(x, у), 0');
d) fexp (x, 0) = 0', fexp (х, у +1) = f+( fexp(x,y),U11(x)).
14. Является ли функция Аккермана А{х) прими-тивнорекурсивной?
a) Да;
b) Нет.
15. Функции Ро, P1 связаны следующими соотношениями:
Р0(а, х) = а + х,
Рх(а, 1) = а,
Рг(а, х) = ах,
Р1(а, х+1) = Р0(а, Р1(а, х)).
Чему равно Р1(2, 3)?
a) 4;
b) 5;
c) 6.
16.
Определенность
в
n
m
вычислении
простейших
функций 0, х + 1, U и полная заданность в действиях
операторов суперпозиции, примитивной рекурсии и m оператора – это требование:
a) массовости;
b) детерминированности;
c) результативности.
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕСТ № 5 «Некоторые вопросы теории алгоритмов»
1. Назовите логическую среду, в которой строится
теория алгоритмов.
2. Понятие функции в теории алгоритмов вводится
двумя способами, отметьте их:
1) определяется множество простейших функций с
нужными свойствами – базис дальнейших построений;
2) искомый класс вычислимой функции определяется
как транзитивное замыкание множества базисных функций
относительно рассматриваемых операторов построения
новых функций;
3) вначале определяется понятие алгоритма А как
процесса определенного вида, ведущего от варьируемых
исходных данных m к результату l, т. е. l = A(m). Затем каждый
такой алгоритм А объявляется функцией, определенной на
множестве тех m, к которым он применим;
4) непосредственно
строится
класс
функций,
объявляемых вычислимыми, и понятие алгоритма
отождествляется с понятием вычислимой функции,
реализующей этот алгоритм при некоторой нумерации
рассматриваемых объектов.
3. Сформулируйте определение неформализованного
понятия «алгоритм».
4. Соотнесите характерные черты алгоритмов:
А. Общие.
В. Выделенные А. А. Марковым:
1) детерминированность; 4) элементарность шага;
2) универсальность;
5) массовость;
3) результативность;
6) дискретность.
5. Алгоритм, решающий массовую проблему – это:
1) частный метод, позволяющий решить любую задачу
этой проблемы;
2) общий метод, позволяющий решить только одну
задачу этой проблемы;
3) частный метод, позволяющий решить только одну
задачу этой проблемы;
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4) общий метод, позволяющий решить любую задачу
этой проблемы.
6. Продолжите тезис формализации:
«Любой содержательно описанный алгоритм…»
7. Перечислите формализации понятия алгоритм,
предложенные в терминах А. М. Тьюринга, Э. Поста,
А. Черча и С. К. Клини, А. А. Маркова, соответственно.
8. Пусть дано некоторое множество М, состоящее из
элементов a, b, c,… Является ли множество М
разрешимым, если:
1) существует алгоритм, по которому можно
упорядочить все элементы данного множества;
2) перечислимо само множество, но его дополнение
не перечислимо;
3) для любого слова х алфавита данного множества
можно определить, входит ли данное слово х в это
множество;
4) не перечислимо само множество, но его
дополнение перечислимо.
9. Какие из предоставленных утверждений являются
верными:
1) одна и та же буква может входить в слово только
один раз;
2) слово может входить в другое слово несколько раз;
3) операция конкатенации слов α и β выполняется
приписыванием к слову α справа слова β;
4) верных ответов нет.
10. Изобразите схематически взаимоотношение
массовых проблем В и С, где В – массовая проблема,
сведенная к массовой проблеме С, и С* - некоторое
подмножество задач массовой проблемы С.
11. Укажите вид, в котором хранятся исходные
данные, решаемые машиной Тьюринга задачи, все
промежуточные и конечные результаты:
1) алфавит М;
2) лента МТ;
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) одна ячейка ленты МТ;
4) одно слово α из алфавита М.
12.
Выберите из предложенных
формулировку тезиса Тьюринга:
утверждений
1) вычислимые по Тьюрингу функции могут быть
частично определенными;
2) любой вербальный алгоритм в алфавите М может
быть реализован некоторой МТ, работающей над
алфавитом М;
3) МТ является одной из возможных формализаций
содержательного представления о вербальных алгоритмах;
4) все ответы правильные.
13. Отметьте основные компоненты,
задают нормальный алгорифм N:
1) произвольный алфавит М, в котором
N, и слова этого алфавита;
2) произвольный алфавит М, в котором
N, и пустое слово;
3) произвольный алфавит М, в котором
N, и список подстановок;
4) произвольный алфавит М, в котором
N, пустое слово λ и список подстановок.
которые
работает НА
работает НА
работает НА
работает НА
14. Найдите ошибочное отличие алгорифмов Маркова
от алгоритмов Тьюринга:
1) алгоритмы Тьюринга являются вербальными,
алгорифмы Маркова – не вербальные;
2) МТ обладает свойством локальности, НА свойством
локальности не обладает;
3) теории НА и алгоритмов Тьюринга строятся на
основе разных планов и используют разную терминологию;
4) пустая буква не входит в алфавит М, в котором
работает алгорифм N.
15. Множество базисных функций, используемых при
построении класса примитивно-рекурсивных функций,
включает:
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) функцию построения по числу «нуль» как угодно
большого отрезка множества натуральных чисел;
2) функцию
«непосредственно
следующее
натуральное число»;
3) функции суперпозиции и примитивной рекурсии;
4) функции введения фиктивных переменных.
16. Класс частично-рекурсивных функций есть:
1) транзитивное замыкание множества базисных
функций относительно операторов суперпозиции функции,
примитивной рекурсии и μ-оператора;
2) всюду
определенная
примитивно-рекурсивная
функция;
3) транзитивное замыкание множества базисных
функций относительно операторов суперпозиции функции
и примитивной рекурсии;
4) правильного ответа нет.
17. Найдите форулировку-1 в терминах статьи Поста:
1) существует финитный 1-процесс, что будучи
применимым к натуральному n в качестве исходной
конфигурации ящиков, он задает n-ую конкретную
проблему;
2) финитный 1-процесс для общей проблемы есть
одно решение, если ответ для каждой конкретной
проблемы правильны;
3) если общая проблема 1-задана 1-разрешима, то,
соединяя наборы инструкций по заданию проблемы ее
решения, мы получаем ответ по номеру проблемы;
4) программа (набор инструкций в терминах Поста)
является одной и той же для всех конкретных проблем,
соотнесена с общей проблемой.
18. Укажите наиболее важное, на ваш взгляд, отличие
М.П. от МТ
19. Отметьте верное определение однозначной
Геделевой нумерации объектов множества Е, где Е –
множество конструктивных объектов:
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) нумерация объектов множества Е в случае, когда
некоторое множество натуральных чисел есть само
множество натуральных чисел;
2) отображение g некоторого множества натуральных
чисел на множество конструктивных объектов Е;
3) нумерация (кодирование) программ в теории
вычислений;
4) нумерация объектов множества Е, являющаяся и
сюръекцией, и инъекцией.
20.
Что
показывает
моделировании?
теорема
о
двоичном
1) в теории МТ нельзя ограничиться рассмотрением
только МТ, работающих в унарном алфавите;
2) в теории МТ нельзя ограничиться рассмотрением
только МТ, работающих в двоичном алфавите;
3) в теории МТ можно ограничиться рассмотрением
только МТ, работающих в унарном алфавите;
4) в теории МТ можно ограничиться рассмотрением
только МТ, работающих в двоичном алфавите.
21.
Конструктивными
объектами
(выберите только один ответ):
являются
1) конечные объекты;
2) объекты, имеющие конечное число частей с
некоторой, присущей только этим объектам, системой
координат, позволяющей различать их части;
3) записываемые в определенной системе счисления
натуральные числа и линейно упорядоченные конечные
последовательности натуральных чисел;
4) все ответы правильные.
22. В каком случае говорят о том, то осуществлена
арифметизация множества А и числа n из множества М?
1) при
установлении
конструктивного
взаимно
однозначного
соответствия
между
множеством
конструктивных объектов А и некоторым множеством М
натуральных чисел;
2) при установлении конструктивного однозначного
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
соответствия между множеством конструктивных объектов
А и некоторым множеством М натуральных чисел;
3) при установлении конструктивного неоднозначного
соответствия между множеством конструктивных объектов
А и некоторым множеством М натуральных чисел;
4) правильного ответа нет.
23.
Абстрактная
модель
устройства,
функционирующего в дискретное время, которая
перерабатывает последовательные входные и выходные
сигналы и превращает их в последовательность
выходных сигналов, называется:
1) М П;
2) М Т;
3) автомат;
4) все ответы верные.
Общие сведения
Множество будем обозначать заглавными латинскими
буквами А, В, С, … То, что х и у являются элементами
множества, записывается в виде х, уÎ М.
N - множество натуральных чисел, N+ - множество
положительных натуральных чисел.
Алфавит – конечное линейно упорядоченное
множество некоторых объектов.
М = { m 0, m 1, …, m i }, где m i– буква.
Слова будем записывать греческими буквами α… (α =
m1 m2 m3 m4).
Под длиной слова будем понимать количество букв в
этом слове.
Слова записываются на стандартном носителе,
разделенной на клетки ленты.
α
α
m1
m2
27
m3
m4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пустые буквы, которые не видны.
М* - потенциальное бесконечное множество слов
алфавита М.
М+ - М* / { α}, без пустого слова.
Область определения функции f(x) - это множество
вида{х/f(x) определенно}.
Обозначение: Domf(x) или Dom(f).
Множество значений функции f(x) – это множество
вида{f(x) / х принадлежит Dom(f) }. Обозначение:
Ram(f).
Ограничением функции f на множестве Х называется
функция с областью определения Х ∩Dom(f), значение
которой х принадлежит Х ∩Dom(f) совпадает с f(x).
Обозначение: f\ Х.
В теории алгоритмов преимущественно имеют дело с
функцией от натуральных чисел. Функция fиз Nn
называется n- местной.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Примерные вопросы к экзамену
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. Геделева нумерация МТ.
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
БЕЗУСОВА Татьяна Алексеевна
ТЕОРИЯ АЛГОРИТМОВ.
ОСНОВНЫЕ ПОДХОДЫ
К ФОРМАЛИЗАЦИИ АЛГОРИТМА
Учебное пособие для студентов 3-4 курсов,
обучающихся по специальности
050201 «Математика и информатика»,
050202 «Информатика и Математика»
.
Зав. РИО
Редактор
Корректор
Макет и компьютерная верстка
Дизайн обложки
Л. В. Малышева
Л. Г. Абизяева
Л. В. Кравченко
А. М. Вахрушевой
А. М. Вахрушевой
Сдано в набор 14.12.2010 г. Подписано в печать21.02.2011 г.
Бумага для копировальной техники. Формат 60х84/16.
Гарнитура «Arial». Печать цифровая.
Усл. печ. листов 4,2. Тираж 50 экз. Заказ № 257.
Отпечатано в редакционно-издательском отделе
ГОУ ВПО.
«Соликамский государственный педагогический институт»
618547, РОССИЯ, Пермский край
г. Соликамск, ул. Северная, 44.
30
Документ
Категория
Информатика и программирование
Просмотров
465
Размер файла
903 Кб
Теги
алгоритм, 1401, теория
1/--страниц
Пожаловаться на содержимое документа