Студопедия — Частично-рекурсивные функции
Студопедия Главная Случайная страница Обратная связь

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

Частично-рекурсивные функции






 

3.1. Теоретические сведения о рекурсивных функциях

 

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

Частично-рекурсивными функциями называются функции, которые можно выразить через элементарные применением конечное число раз операторов суперпозиции, примитивной рекурсии и минимизации.

Элементарные функции:

  1. Ноль – функция без аргументов, всегда возвращает ноль –
  2. Инкремент – функция повышения значения переменной на единицу, возвращает x+1 –
  3. Проекция – возвращает i-тую проекцию вектора переменных (то есть i-тую переменную) -

 

 

Операторы:

  1. Суперпозиция – оператор, позволяющий передавать функции в качестве параметра значение, возвращённое другой функцией.
    Пример:
  2. Примитивная рекурсия – оператор, позволяющий вычислять значение на основе . При применении оператора примитивной рекурсии к функции задаются две функции и такие, что:

  3. Оператор минимизации – оператор, осуществляющий последовательный перебор всех возможных значений переменной пока её значение не будет удовлетворять некоторому условию. Формально – для заданной находит . Если , то оператор минимизации зацикливается и функция не выполняется. На практике используется оператор минимизации вида

3.2. Дерево структурного анализа

 

 

3.3. Доказательство ЧРФ

 

Пусть . Тогда:

 

Докажем действия. Введём функции для каждой операции

 

 

 

 

 

 

Докажем константы:

 

 

Применим оператор минимизации:

 

 








Дата добавления: 2015-09-04; просмотров: 508. Нарушение авторских прав; Мы поможем в написании вашей работы!



Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

Примеры задач для самостоятельного решения. 1.Спрос и предложение на обеды в студенческой столовой описываются уравнениями: QD = 2400 – 100P; QS = 1000 + 250P   1.Спрос и предложение на обеды в студенческой столовой описываются уравнениями: QD = 2400 – 100P; QS = 1000 + 250P...

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

Педагогическая структура процесса социализации Характеризуя социализацию как педагогический процессе, следует рассмотреть ее основные компоненты: цель, содержание, средства, функции субъекта и объекта...

РЕВМАТИЧЕСКИЕ БОЛЕЗНИ Ревматические болезни(или диффузные болезни соединительно ткани(ДБСТ))— это группа заболеваний, характеризующихся первичным системным поражением соединительной ткани в связи с нарушением иммунного гомеостаза...

Решение Постоянные издержки (FC) не зависят от изменения объёма производства, существуют постоянно...

ТРАНСПОРТНАЯ ИММОБИЛИЗАЦИЯ   Под транспортной иммобилизацией понимают мероприятия, направленные на обеспечение покоя в поврежденном участке тела и близлежащих к нему суставах на период перевозки пострадавшего в лечебное учреждение...

Studopedia.info - Студопедия - 2014-2024 год . (0.007 сек.) русская версия | украинская версия