Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Березенцева Т.Н.






Негосударственное образовательное учреждение высшего профессионального образования

«РОССИЙСКИЙ НОВЫЙ УНИВЕРСИТЕТ»

Воскресенский филиал

Кафедра прикладной информатики и естественнонаучных дисциплин

 

 

Контрольная работа

По теории алгоритмов

 

IV-вариант

 

 

Выполнил:

студента 2 курса на базе среднего профессионального (профильного) образования заочной формы обучения группы ИП11 Макарова Юрий Игоревич

 

Проверил:

старший преподаватель

Березенцева Т.Н.

 

Воскресенск

2013 г.


1. Определить, какая функция получается при суперпозиции функции g(x)=x+1 с самой собой.

h(x)= g(g(х))=x+2

Ответ: Суперпозиция функции g(х) с самой собой получим функцию h(х) = х + 2.

2. Определить, какая функция возникает примитивной рекурсией из функций g= x и h=xz.

f(0)=g(0)=0;

f(1)=h(0, g(0))=00=0;

f(2)=h(1, f(1))=10=1;

f(3)=h(2, f(2))=21=2;

f(4)=h(3, f(3))=32=9;

f(x)=(x-1)(x-2)

Ответ: Примитивная рекурсией из функций g= x и h=xz есть функция f(x)=(x-1)(x-2)

3. Покажите, что функция f(x, y)= 2x+3y является примитивно рекурсивной.

Доказательство.

Функция f(x; y) удовлетворяет соотношениям:

f(x; y + 1) =2 x + 3(y + 1) = 2x + 3y + 3 = s(s(s(2x + 3y))) = s(s(s(f(x; y)))):

Следовательно, функция f(x; y) возникает из примитивно рекурсивных функций

и операцией примитивной рекурсии и поэтому функция f(x; y) = 2x + 3y является примитивно рекурсивной.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.