Скачать 320.61 Kb.
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Методические указания и заданияк лабораторным работам по курсам“ДИСКРЕТНЫЕ СТРУКТУРЫ“, “ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ“ Донецк - 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. Определить к какому классу рекурсивных функций принадлежит : примитивно-рекурсивна, частично-рекурсивна или общерекурсивна. Варианты заданий
|
Методические указания к лабораторным работам по дисциплине «Компьютерные Технологии» Основы расчётов в системе mathcad: Методические указания к лабораторным работам – Набережные Челны: инэка, 2007, с |
Методические указания к лабораторным работам по дисциплине «Охрана труда» Методические указания к лабораторным работам по дисциплине «Охрана труда» для студентов всех специальностей. / Сост. В. И. Коробко.... |
||
Методические указания и задания к лабораторным работам по курсу «Протоколы компьютерных сетей» Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по курсу «Протоколы компьютерных... |
Методические указания и контрольные задания для студентов специальности... Методические указания содержат тематический план, программу курса, задания и методические указания к выполнению контрольных работ,... |
||
Методические указания и контрольные задания к выполнению контрольных... Методические указания содержат программу курса, контрольные вопросы по темам курса, контрольные задания и методические рекомендации... |
Методические указания и контрольные задания для студентов специальности... ... |
||
Методические указания и задания к самостоятельной работе студентов... Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по курсу «Протоколы компьютерных... |
Методические указания по выполнению контрольных работ по «Математике»... Математика: Методические указания по выполнению контрольных работ Бузулук: бгти, 2013 |
||
Методические указания и задания для выполнения контрольных работ... Методические указания составлены в соответствии с требованиями Федерального государственного образовательного стандарта по специальности... |
Методические рекомендации по выбору варианта контрольной работы Экономика организации (предприятия) : контрольные задания и методические указания к выполнению контрольных работ №1 и №2 для студентов... |
Поиск на сайте Главная страница Литература Доклады Рефераты Курсовая работа Лекции |