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

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

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

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

(для студентов, обучающихся по направлениям

“Программная инженерия”, “Компьютерные науки”)

Рассмотрено на заседании кафедры

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

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

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

учебно-издательского совета ДонНТУ

протокол № 5 от 21.12.09

Донецк - 2009

УДК 004.021

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

Изложенные теоретические основы, методические рекомендации, контрольные вопросы и задания для выполнения лабораторных работ по следующим разделам курса теории алгоритмов и вычислительных процессов:

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

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

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

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

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

Коломойцева И.А., ст. преп.

Рецензент: Губенко Н.Е., к.т. н., доцент

Лабораторная работа №1

РЕКУРСИВНЫЕ ФУНКЦИИ

Цель работы: получить практические навыки в записи алгоритмов с использованием аппарата рекурсивных функций.

Теоретическая справка

Вычислимые функции – числовые функции, значения которых можно вычислять посредством единого для данной функции алгоритма.

Арифметические функции – функции, области определения и значений которых целые неотрицательные числа, то есть натуральный ряд + число ноль.

Частичные арифметические функции – арифметические функции с ограниченной областью определения, остальные – всюду определенными.