- •Министерство образования и науки украины
- •Рекурсивные функции
- •Теоретическая справка
- •Примитивно-рекурсивные функции
- •Задание на лабораторную работу
- •Контрольные вопросы
- •Машины тьюринга
- •Теоретическая справка Символьные конструкции
- •Определение машины Тьюринга (мт)
- •Задание на лабораторную работу
- •Контрольные вопросы
- •Композиция машин тьюринга
- •Теоретическая справка
- •1. Последовательная композиция машин Тьюринга
- •2. Параллельная композиция машин Тьюринга
- •3. Разветвление или условный переход в композиции машин Тьюринга
- •Задание на лабораторную работу
- •Контрольные вопросы
- •Нормальные алгоритмы маркова
- •Теоретическая справка
- •Функционирование нам
- •Задание на лабораторную работу
- •Контрольные вопросы
- •Перечень рекомендованной литературы
- •7.050102 “Программное обеспечение автоматизированных систем”,
- •7.080407 “Компьютерный эколого-экономический мониторинг ”
Министерство образования и науки украины
ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Методические указания и задания
к лабораторным работам по курсам
“ДИСКРЕТНЫЕ СТРУКТУРЫ“,
“ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ“
Донецк - 2009
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ
ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Методические указания и задания
к лабораторным работам
по курсам “Дискретные структуры”,
“ Теория алгоритмов и вычислительных процессов “
( для студентов специальностей
7.050102 “Программное обеспечение автоматизированных систем”,
7.080407 “Компьютерный эколого-экономический мониторинг ”)
Утверждено на заседании кафедры
прикладной математики и информатики
протокол № 14 от 29.06.09.
Донецк - 2009
УДК 681.3.07
Методические указания и задания к лабораторным работам по курсам “Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 7.050102 “Программное обеспечение автоматизированных систем”, 7.080407 “Компьютерный эколого-экономический мониторинг ”) / разраб.: Назарова И.А., Коломойцева И.А. – Донецк: ДонНТУ, 2009 – 35с.
Изложенные теоретические основы, методические рекомендации, контрольные вопросы и задания для выполнения лабораторных работ по следующим разделам курса теории алгоритмов и вычислительных процессов:
теория рекурсивных функций;
машины Тьюринга;
композиция машин Тьюринга;
нормальные алгоритмы Маркова.
Составители: Назарова И.А., доцент
Коломойцева И.А., ст. преп.
Рецензент: Теплинский С.В., к.т. н., доц.
Лабораторная работа №1
Рекурсивные функции
Цель работы: получить практические навыки в записи алгоритмов с использованием аппарата рекурсивных функций.
Теоретическая справка
Вычислимые функции – числовые функции, значения которых можно вычислять посредством единого для данной функции алгоритма.
Арифметические функции – функции, области определения и значений которых целые неотрицательные числа, то есть натуральный ряд + число ноль.
Частичные арифметические функции – арифметические функции с ограниченной областью определения, остальные – всюду определенными.
Примитивно-рекурсивные функции
В качестве простейших функций в теории рекурсивных функций приняты следующие:
1.– константа «ноль».
2.– « последователь ».
3.– функция тождества или выбора аргумента, проекция.
Оператор суперпозиции (подстановки) – подстановка в функцию от переменных функций от переменных, что дает новую функцию отпеременных.
Суперпозицией функций и называют функцию:
;
.
Оператор примитивной рекурсии , определяющий значение функции , записывается в виде следующей схемы:
Примитивно-рекурсивная функция – арифметическая функция, которая может быть получена из простейших с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.
Примитивно-рекурсивные функции являются всюду определенными.
Пример 1. Константа a получается путем суперпозиции функцийи:
Пример 2. Операция сложения может быть определена с помощью оператора примитивной рекурсии:
Таким образом, функция получена из простейшихипутем применения оператора примитивной рекурсии, что соответствует определению примитивно-рекурсивной функции.
Пример 3. Примитивная рекурсивность операции умножения доказывается с использованием сложения:
Пример 4. Примитивная рекурсивность операции возведения в степень доказывается следующим образом:
Пример 5. Операция вычитания не является примитивно-рекурсивной, т.к. она не всюду определена: результат операции a-b при не определен в области натуральных чисел. Однако примитивно-рекурсивной является так называемое арифметическое (усеченное) вычитание или разность.
Арифметическое вычитание:
Для доказательства примитивной рекурсивности вначале рассмотрим операцию: ;
т.е. операция – примитивно-рекурсивна.
Дополнительное свойство:
.
арифметическое вычитание – примитивно-рекурсивно.
Пример 6. Функция – аналог функциидля натуральных чисел.
Функция примитивно-рекурсивна:
–антисигнум, функция обратная .
.
Пример 7. Примитивная рекурсивность функций , и модульразности двух чисел доказывается с помощью арифметического вычитания:
Отношение называетсяпримитивно-рекурсивным, если примитивно-рекурсивна его характеристическая функция :
Пример 8. Отношение – примитивно-рекурсивно.
Действительно, .
Отношение примитивно-рекурсивно.
Действительно, .
Отношение примитивно-рекурсивно.
Действительно, .
Оператор минимизации (-оператор, оператор наименьшего корня) определяет новую арифметическую функцию отn переменных с помощью ранее построенной арифметической функции отn+1 переменных. Пусть существует некоторый механизм вычисления функции , причем значение функциинеопределенно, если этот механизм работает бесконечно, не выдавая никакого определенного значения.
Зафиксируем набор значений аргументов и рассмотрим уравнение относительноy: ; чтобы найти решение этого уравнения, натуральное, будем вычислять последовательность значений:
для ..
Наименьшее целое неотрицательное значение , удовлетворяющее этому уравнению:обозначим:
.
Говорят, что функция получена из функцииоперацией минимизации, если:
.
Оператор минимизации работает бесконечно в одном из следующих случаев:
1) значение не определено;
2) значение дляопределены, но не равны нулю, а значение– не определено;
3) значение определены для всех, но не равны нулю.
Оператор минимизации является удобным средством получения обратных функций: вычитание, деление, извлечение корня и так далее.
Пример 9. Определение операции «вычитание»:
.
Пример 10. Определение операции «деление»:
.
Пример 11. Определение операции « извлечение корня »:
.
Пример 21. Определение операции « логарифм »:
Пример 13. Процесс вычисления функции с помощью оператора минимизации приведен ниже:
Частично-рекурсивная функция – функция, которая может быть построена из простейших с помощью конечного числа применений оператора суперпозиции, примитивной рекурсии и минимизации.
Частично-рекурсивная функция является не всюду определенной, причем там, где она не определена, процесс ее вычисления продолжается бесконечно.
Общерекурсивная функция – всюду определенная частично-рекурсивная функция.
Связь между алгоритмами и рекурсивными функциями выражается тезисом Черча: какова бы ни была вычислимая неотрицательная целочисленная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей частично-рекурсивная функция.