Методические указания и задания к лабораторным работам по курсам “

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Методические указания и задания к лабораторным работам по курсам “ДИСКРЕТНЫЕ СТРУКТУРЫ“, “ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ“ Донецк - 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. Процесс вычисления функции с помощью оператора минимизации приведен ниже: Частично-рекурсивная функция – функция, которая может быть построена из простейших с помощью конечного числа применений оператора суперпозиции, примитивной рекурсии и минимизации. Частично-рекурсивная функция является не всюду определенной, причем там, где она не определена, процесс ее вычисления продолжается бесконечно. ^ Общерекурсивная функция – всюду определенная частично-рекурсивная функция. Связь между алгоритмами и рекурсивными функциями выражается тезисом Черча: какова бы ни была вычислимая неотрицательная целочисленная функция от неотрицательных целочисленных аргументов, существует тождественно равная ей частично-рекурсивная функция. Задание на лабораторную работу 1. Разработать алгоритм вычисления в виде рекурсивной функции. 2. Проверить модель алгоритма на множестве тестовых примеров. 3. Определить к какому классу рекурсивных функций принадлежит : примитивно-рекурсивна, частично-рекурсивна или общерекурсивна. Варианты заданий Сумма всех четных делителей числа . Количество всех нечетных делителей числа . Количество нулей в двоичной записи . Сумма цифр в двоичной записи . Количество взаимно-простых с чисел, Максимальная цифра в 8-ричной записи числа . Минимальная цифра в 8-ричной записи числа . Количество четных цифр в 8-ричной записи числа . Количество нечетных цифр в 8-ричной записи числа . Сумма простых делителей числа . Количество простых делителей числа . Количество простых чисел, Количество чисел, являющихся полными квадратами, Сумма чисел, являющихся степенью двойки, Максимальная цифра в 16-ричной записи числа . Минимальная цифра в 16-ричной записи числа . Ближайшее к простое число. Произведение делителей числа . Произведение простых делителей числа . Произведение взаимно-простых с чисел, Наименьшее общее кратное двух чисел, , Наибольший общий делитель двух чисел, Функция, отличная от нуля в конечном числе точек. Номер наибольшего простого делителя числа Функция, вычисляющая целую часть квадратного корня от аргумента, . Контрольные вопросы Что такое вычислимая, арифметическая, частичная или всюду определенная функция? Определить операторы суперпозиции и примитивной рекурсии. Перечислить простейшие функции теории рекурсивных функций. Что такое примитивно-рекурсивные функции? Показать примитивную рекурсивность известных арифметических функций. Показать примитивную рекурсивность арифметизованных логических функции. Примитивная рекурсивность отношений и предикатов. Определить оператор минимизации, в каких случаях он работает бесконечно? Что такое частично-рекурсивная функция и общерекурсивная? Сформулировать тезис Черча. Определите соотношение между примитивно, частично и общерекурсивными функциями. Лабораторная работа № 2 ^ МАШИНЫ ТЬЮРИНГА Цель работы: получить практические навыки в записи алгоритмов с использованием машин Тьюринга. Теоретическая справка Символьные конструкции Алфавитом будем называть любое конечное множество попарно различных знаков, называемых буквами (символами) этого алфавита. Алфавит будем обозначать заглавными буквами, например: Символом  будем обозначать пустой символ. Словом в данном алфавите называется любая конечная (в том числе и пустая) последовательность букв этого алфавита. Слова будем обозначать малыми греческими буквами. Например:  = алгоритм – слово в алфавите А;  = 1010100 – слово в алфавите В; – слово в алфавите С. Пустое слово будем обозначать . Длина слова  (обозначается ) – это количество букв в слове. Определим некоторые отношения и операции над словами. ^ Равенство слов в алфавите А определяется индуктивно: а) пустые слова равны б) если слово  равно слову , то  b =b , где b – буква в алфавите А. Если слово  является частью слова , то говорят, что имеет место вхождение слова  в слово  (слово  называется подсловом слова ). Это можно записать следующим образом: , где – слова в алфавите А. Слово  называется началом слова , если ; концом слова , если . Слово длины n, составленное из буквы а, повторенной n раз, будем обозначать , например xyxxxyyyy = . Операция (и результат) приписывания слов  и  друг к другу называется конкатенацией (обозначается ||). Например, если . Определение машины Тьюринга (МТ) Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей: бесконечной в обе стороны ленты, разбитой на ячейки, в каждой из ячеек может быть записан только один символ из алфавита , а также пустой символ ; рабочей головки или управляющего устройства (УУ), которое в каждый момент времени может находиться в одном из состояний множества . В каждом из состояний головка размещается напротив ячейки и может считывать (обозревать) или записывать в нее букву из алфавита А. Машина Тьюринга Функционирование МТ состоит из последовательности элементарных шагов (тактов). На каждом шаге выполняются следующие действия: управляющее устройство считывает (обозревает) символ ; в зависимости от своего состояния и обозреваемого символа УУ вырабатывает символ и записывает его в обозреваемую ячейку (возможно ); головка перемещается на одну ячейку вправо (R), влево (L) или остается на месте (E); головка переходит в другое внутреннее состояние (возможно ). Состояние называется начальным, – заключительным. При переходе в заключительное состояние машина останавливается. Полное состояние МТ называется конфигурацией. Это распределение букв по ячейкам ленты, состояние рабочей головки и обозреваемая ячейка. Конфигурация в такте t записывается в виде: , где – подслово слева от обозреваемой ячейки, – буква в обозреваемой ячейке, – подслово справа. Начальная конфигурация и конечная называются стандартными. Для описания работы МТ существует 3 способа: 1) система команд вида 2) функциональная таблица; 3) граф (диаграмма) переходов. С помощью МТ можно описывать выполнение арифметических операций над числами. При этом числа представляются на ленте, как слова в алфавите, состоящем из цифр какой-нибудь системы счисления, и разделяющихся специальным знаком, не входящем данный алфавит, например, . Наиболее употребительной является унарная система, состоящая из одного символа  – . Число ^ Х в унарной системе счисления на ленте записывается словом , ( сокращенно ) в алфавите А={ }. Пример 1. Операция сложения двух чисел в унарном коде. Начальная конфигурация: . Конечная конфигурация: , т.е. сложение фактически сводится к приписыванию числа b к числу a . Для этого первый символ стирается, а * заменяется на . Система команд при и . Комментарий к системе команд 1. – 增寮陝猥 渟躁謫î 茁蚓鏑à . 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 艇增迹, 幢 逡淳侁奄 舜調脣. 2. – стирание 茁蚓鏑à , первый аргумент равняется 0. 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ в состоянии (первый аргумент равняется 0), 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 艇增迹, 幢 逡淳侁奄 舜調脣. 3. – сдвиг вправо. 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑, 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å è 翟蹟釣循諺渾 茁蚓鏑 張 了靭, 幢 逡淳侁奄 舜調脣. 4. – стирание символа . 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , è 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 , 幢 逡淳侁奄 瞬億î (惟張ö 渟躁謫î 燮身靭粧à). 5. – сдвиг влево. 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å è 翟蹟釣循諺渾 茁蚓鏑 張 了靭, 幢 逡淳侁奄 瞬億î. 6. – 퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 張 了靭奄, 幢 逡淳侁奄 舜調脣 (惟張ö 贍莘鳥嫉à, 幢 調楫鏑跡孼î â 壯妬音 調灑特é 吾裝 ). Описание МТ в виде функциональной таблицы: |* - - - Описание МТ в виде диаграммы переходов Вычисление на МТ словарной функции будем понимать следующим образом. Пусть в начальной конфигурации на ленте записано слово . Если значение определено, то конечного числа шагов (тактов) машина должна перейти в заключительную конфигурацию, в которой на ленте записано слово . В противном случае МТ должна работать бесконечно. Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда =y , или работает бесконечно, когда не определена.

Похожие:

	Методические указания к лабораторным наборам предназначены для студентов,... Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...		Методические указания к лабораторным работам по курсу «Информатика» Методические указания предназначены для выполнения лабораторных работ по написанию программ на языке C. Работы проводятся с использованием...
	Методические указания к лабораторным работам по дисциплине «Теория электрической связи» Методические указания предназначены для студентов дневной формы обучения по специальности «Телекоммуникационные системы и сети»		Методические указания и задания к лабораторным работам по курсу "основы... Методические указания к курсу "Основы автоматизации проектирования сложных объектов и систем" (для студентов специальности 22. 04)...
	Методические указания и контрольные задания к выполнению контрольных... В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...		Практикум по компьютерному моделирования ядерных процессов с использованием... Практикум по компьютерному моделирования ядерных процессов с использованием библиотеки geant4
	Методические указания и контрольные задания по дисциплине «Экономика организации» Методические указания составлены в соответствии с примерной программой по дисциплине		Методические указания по выполнению курсового проекта с использованием... Изложены общие указания по курсовому проектированию, приведены задания на проекты, даны методические указания по отдельным этапам...
	Методические указания по анализу финансового 12 состояния организации 12 Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...		Методические указания и контрольные задания для студентов заочной... Методические указания составлены в соответствии с Учебно-методическим комплексом дисциплины на основе требований Государственного...