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