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




НазваниеМетодические указания и задания к лабораторным работам по курсам “
страница1/3
Дата публикации23.06.2013
Размер0.57 Mb.
ТипМетодические указания
lit-yaz.ru > Информатика > Методические указания
  1   2   3


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

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

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




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

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




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

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


  1. Донецк - 2009


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

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

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


  • ^

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


к лабораторным работам

по курсам “Дискретные структуры”,

“ Теория алгоритмов и вычислительных процессов “

( для студентов специальностей

7.050102 “Программное обеспечение автоматизированных систем”,

7.080407 “Компьютерный эколого-экономический мониторинг ”)


Утверждено на заседании кафедры

прикладной математики и информатики

протокол № 14 от 29.06.09.


  1. ^

    Донецк - 2009

  2. УДК 681.3.07




Методические указания и задания к лабораторным работам по курсам “Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 7.050102 “Программное обеспечение автоматизированных систем”, 7.080407 “Компьютерный эколого-экономический мониторинг ”) / разраб.: Назарова И.А., Коломойцева И.А. – Донецк: ДонНТУ, 2009 – 35с.
Изложенные теоретические основы, методические рекомендации, контрольные вопросы и задания для выполнения лабораторных работ по следующим разделам курса теории алгоритмов и вычислительных процессов:

  1. теория рекурсивных функций;

  2. машины Тьюринга;

  3. композиция машин Тьюринга;

  4. нормальные алгоритмы Маркова.

Составители: Назарова И.А., доцент

Коломойцева И.А., ст. преп.
Рецензент: Теплинский С.В., к.т. н., доц.
Лабораторная работа №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. Определить к какому классу рекурсивных функций принадлежит : примитивно-рекурсивна, частично-рекурсивна или общерекурсивна.
Варианты заданий

  1. Сумма всех четных делителей числа .

  2. Количество всех нечетных делителей числа .

  3. Количество нулей в двоичной записи .

  4. Сумма цифр в двоичной записи .

  5. Количество взаимно-простых с чисел,

  6. Максимальная цифра в 8-ричной записи числа .

  7. Минимальная цифра в 8-ричной записи числа .

  8. Количество четных цифр в 8-ричной записи числа .

  9. Количество нечетных цифр в 8-ричной записи числа .

  10. Сумма простых делителей числа .

  11. Количество простых делителей числа .

  12. Количество простых чисел,

  13. Количество чисел, являющихся полными квадратами,

  14. Сумма чисел, являющихся степенью двойки,

  15. Максимальная цифра в 16-ричной записи числа .

  16. Минимальная цифра в 16-ричной записи числа .

  17. Ближайшее к простое число.

  18. Произведение делителей числа .

  19. Произведение простых делителей числа .

  20. Произведение взаимно-простых с чисел,

  21. Наименьшее общее кратное двух чисел, ,

  22. Наибольший общий делитель двух чисел,

  23. Функция, отличная от нуля в конечном числе точек.

  24. Номер наибольшего простого делителя числа

  25. Функция, вычисляющая целую часть квадратного корня от аргумента, .


Контрольные вопросы


  1. Что такое вычислимая, арифметическая, частичная или всюду определенная функция?

  2. Определить операторы суперпозиции и примитивной рекурсии.

  3. Перечислить простейшие функции теории рекурсивных функций.

  4. Что такое примитивно-рекурсивные функции?

  5. Показать примитивную рекурсивность известных арифметических функций.

  6. Показать примитивную рекурсивность арифметизованных логических функции. Примитивная рекурсивность отношений и предикатов.

  7. Определить оператор минимизации, в каких случаях он работает бесконечно?

  8. Что такое частично-рекурсивная функция и общерекурсивная?

  9. Сформулировать тезис Черча.

  10. Определите соотношение между примитивно, частично и общерекурсивными функциями.

Лабораторная работа № 2
^ МАШИНЫ ТЬЮРИНГА
Цель работы: получить практические навыки в записи алгоритмов с использованием машин Тьюринга.
Теоретическая справка

Символьные конструкции

Алфавитом будем называть любое конечное множество попарно различных знаков, называемых буквами (символами) этого алфавита. Алфавит будем обозначать заглавными буквами, например:



Символом будем обозначать пустой символ.

Словом в данном алфавите называется любая конечная (в том числе и пустая) последовательность букв этого алфавита. Слова будем обозначать малыми греческими буквами.

Например: = алгоритм – слово в алфавите А; = 1010100 – слово в алфавите В; – слово в алфавите С.

Пустое слово будем обозначать .

Длина слова (обозначается ) – это количество букв в слове.

Определим некоторые отношения и операции над словами.

^ Равенство слов в алфавите А определяется индуктивно:

а) пустые слова равны

б) если слово  равно слову , то  b =b , где b буква в алфавите А.

Если слово является частью слова , то говорят, что имеет место вхождение слова в слово (слово называется подсловом слова ). Это можно записать следующим образом: , где – слова в алфавите А.

Слово называется началом слова , если ; концом слова , если . Слово длины n, составленное из буквы а, повторенной n раз, будем обозначать , например xyxxxyyyy = .

Операция (и результат) приписывания слов и друг к другу называется конкатенацией (обозначается ||). Например, если .
Определение машины Тьюринга (МТ)

Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей:

  1. бесконечной в обе стороны ленты, разбитой на ячейки, в каждой из ячеек может быть записан только один символ из алфавита , а также пустой символ ;

  2. рабочей головки или управляющего устройства (УУ), которое в каждый момент времени может находиться в одном из состояний множества . В каждом из состояний головка размещается напротив ячейки и может считывать (обозревать) или записывать в нее букву из алфавита А.



Машина Тьюринга
Функционирование МТ состоит из последовательности элементарных шагов (тактов). На каждом шаге выполняются следующие действия:

  1. управляющее устройство считывает (обозревает) символ ;

  2. в зависимости от своего состояния и обозреваемого символа

УУ вырабатывает символ и записывает его в обозреваемую ячейку (возможно );

  1. головка перемещается на одну ячейку вправо (R), влево (L) или остается на месте (E);

  2. головка переходит в другое внутреннее состояние (возможно ).

Состояние называется начальным, – заключительным. При переходе в заключительное состояние машина останавливается.

Полное состояние МТ называется конфигурацией. Это распределение букв по ячейкам ленты, состояние рабочей головки и обозреваемая ячейка. Конфигурация в такте t записывается в виде: , где – подслово слева от обозреваемой ячейки, – буква в обозреваемой ячейке, – подслово справа. Начальная конфигурация и конечная называются стандартными.

Для описания работы МТ существует 3 способа:

1) система команд вида

2) функциональная таблица;

3) граф (диаграмма) переходов.

С помощью МТ можно описывать выполнение арифметических операций над числами. При этом числа представляются на ленте, как слова в алфавите, состоящем из цифр какой-нибудь системы счисления, и разделяющихся специальным знаком, не входящем данный алфавит, например, .

Наиболее употребительной является унарная система, состоящая из одного символа  – . Число ^ Х в унарной системе счисления на ленте записывается словом , ( сокращенно ) в алфавите А={ }.

Пример 1. Операция сложения двух чисел в унарном коде.

Начальная конфигурация: . Конечная конфигурация: , т.е. сложение фактически сводится к приписыванию числа b к числу a . Для этого первый символ стирается, а * заменяется на .

Система команд при и .



Комментарий к системе команд

1. – 增寮陝猥 渟躁謫î 茁蚓鏑à .

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 艇增迹, 幢 逡淳侁奄 舜調脣.

2. – стирание 茁蚓鏑à , первый аргумент равняется 0.

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ в состоянии (первый аргумент равняется 0), 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 艇增迹, 幢 逡淳侁奄 舜調脣.

3. – сдвиг вправо.

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑, 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å è 翟蹟釣循諺渾 茁蚓鏑 張 了靭, 幢 逡淳侁奄 舜調脣.

4. – стирание символа .

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , è 翟蹟釣循諺渾 茁蚓鏑 裔靭奄 壯 , 幢 逡淳侁奄 瞬億î (惟張ö 渟躁謫î 燮身靭粧à).

5. – сдвиг влево.

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å è 翟蹟釣循諺渾 茁蚓鏑 張 了靭, 幢 逡淳侁奄 瞬億î.

6.

퇸泣 â 翟蹟釣循諺迹 ÿ特隅å 裔炡焌í 茁蚓鏑 и МТ находится в состоянии , 桎宸à 櫛增杖å 了靭奄 壯 , 翟蹟釣循諺渾 茁蚓鏑 張 了靭奄, 幢 逡淳侁奄 舜調脣 (惟張ö 贍莘鳥嫉à, 幢 調楫鏑跡孼î â 壯妬音 調灑特é 吾裝 ).
Описание МТ в виде функциональной таблицы:

|* - - -

Описание МТ в виде диаграммы переходов

Вычисление на МТ словарной функции будем понимать следующим образом. Пусть в начальной конфигурации на ленте записано слово . Если значение определено, то конечного числа шагов (тактов) машина должна перейти в заключительную конфигурацию, в которой на ленте записано слово . В противном случае МТ должна работать бесконечно.

Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда =y , или работает бесконечно, когда не определена.
  1   2   3

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

Похожие:

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

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания к лабораторным работам по курсу «Информатика»
Методические указания предназначены для выполнения лабораторных работ по написанию программ на языке C. Работы проводятся с использованием...

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

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и задания к лабораторным работам по курсу "основы...
Методические указания к курсу "Основы автоматизации проектирования сложных объектов и систем" (для студентов специальности 22. 04)...

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

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

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и контрольные задания по дисциплине «Экономика организации»
Методические указания составлены в соответствии с примерной программой по дисциплине

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

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

Методические указания и задания к лабораторным работам по курсам “ iconМетодические указания и контрольные задания для студентов заочной...
Методические указания составлены в соответствии с Учебно-методическим комплексом дисциплины на основе требований Государственного...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница