0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
1 | |
Доказательство примитивно рекурсивных функций24.05.2018, 16:58. Показов 1449. Ответов 11
Метки нет (Все метки)
0
|
24.05.2018, 16:58 | |
Ответы с готовыми решениями:
11
Нахождение производных булевых функций и доказательство полноты системы функций Оператор CASE в теории примитивно-рекурсивных функций Использование рекурсивных функций Применение рекурсивных функций |
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,647
|
|
24.05.2018, 22:11 | 2 |
Докажите, что x^y и x+y примитивно рекурсивны. Ваши функции являются композициями этих.
0
|
0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
24.05.2018, 22:53 [ТС] | 3 |
3D Homer, то есть так будет правильно?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,647
|
|
24.05.2018, 22:55 | 4 |
— это , а не .
0
|
0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
24.05.2018, 22:58 [ТС] | 5 |
3D Homer, можете тогда помочь с решением?
Пожалуйста, очень нужно.
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,647
|
|
24.05.2018, 23:09 | 6 |
Воспользуйтесь советом в сообщении 2. Я бы определил f(x, y) с помощью композиции примитивно рекурсивный функций, а не схемы примитивной рекурсии.
0
|
0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
24.05.2018, 23:11 [ТС] | 7 |
3D Homer, а вторая правильно сделана?
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,647
|
|
24.05.2018, 23:26 | 8 |
f(x, y+1)=(x+y+1)(x+y+1) ≠ (x+y)(x+y) + 1. Это известно школьникам средних классов.
Еще раз повторяю. Чтобы построить высотный дом, вам нужен кран. Но это не значит, что последний этап строительства, например, установку сантехники, необходимо выполнять с помощью крана. Представьте f в виде композицию п.р. функций, а не с помощью схемы примитивной рекурсии.
0
|
0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
24.05.2018, 23:33 [ТС] | 9 |
3D Homer, пожалуйста, можете скинуть хотя бы пример доказательства любой подобной функции. Я пока что не совсем понимаю как доказывать, представляя функцию в виде композиции. Дело в том, что разбирали на совсем легких примерах и про композиции речи не шло. Уже несколько источников прочитала, все берется очень поверхностно и не понятно. Нет конкретных примеров.
0
|
4945 / 3564 / 1149
Регистрация: 01.09.2014
Сообщений: 9,647
|
|
25.05.2018, 00:43 | 10 |
Можете посмотреть примеры в следующих книгах.
Игошин В.И. Теория алгоритмов. М.: Инфра-М, 2016. Раздел 3.2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2004. Часть III, §1. Это задачник с ответами. Композиция называется также суперпозицией или подстановкой. Это один из способов порождения п.р. функций. То есть если у вас есть несколько п.р.ф., вы можете подставлять одни в другие, и результат будет п.р.ф.
0
|
0 / 0 / 0
Регистрация: 22.04.2018
Сообщений: 26
|
|
26.05.2018, 14:12 [ТС] | 12 |
3D Homer, спасибо, немного понятней стало
0
|
26.05.2018, 14:12 | |
26.05.2018, 14:12 | |
Помогаю со студенческими работами здесь
12
В чем преимущество рекурсивных функций? Алгоритм решения рекурсивных функций Задачи на использование рекурсивных функций Применение рекурсивных функций: вычислить факториал Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |