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




Скачать 321.54 Kb.
НазваниеМетодические указания и задания к лабораторным работам по курсам “
страница1/5
Дата публикации03.10.2013
Размер321.54 Kb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
  1   2   3   4   5




МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ




Методические указания и задания

к лабораторным работам по курсам




ДИСКРЕТНЫЕ СТРУКТУРЫ“,

ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ


Донецк - 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   4   5

Добавить документ в свой блог или на сайт

Похожие:

Методические указания и задания к лабораторным работам по курсам “ iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по выбору рациональных структур...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсам “ iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по учебным дисциплинам...
«Электродинамика и распространение радиоволн», «Техническая электродинамика» (для студентов направлений подготовки 050901 «Радиотехника»,...

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и задания к контрольной работе Ростов-на-Дону
Арженовский С. В. Анализ временных рядов и прогнозирование: Методические указания и задания к контрольной работе/Рост гос экон ун-т....

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница