Архив категории ‘Понятие рекурсии’

Реализация механизма рекурсии

    На этом шаге мы рассмотрим реализацию механизма рекурсии.     Исполнение рекурсивной процедуры (функции) оказывается для компьютера не совсем простой задачей. Для того чтобы поддержать все возможности, заложенные в схеме рекурсии, компьютер должен выполнить ряд действий, скрытых от программиста. Необходимость этих действий диктуется тем, что имеется определенный разрыв между алгоритмическим языком высокого уровня, освобождающим программиста […]

Связь между рекурсией и итерацией

    На этом шаге мы рассмотрим связь между рекурсией и итерацией.         Рассмотрим подробнее связь между рекурсией и итерацией на примере ряда задач. Первый пример демонстрирует случай явного преимущества итерационного решения над рекурсивным - вычисление чисел Фибоначчи. Рекурсивный вариант. function Fr (n: integer): integer; begin if n = 1 or n = 2 then […]

Рекурсия и итерация

    На этом шаге мы рассмотрим итерацию.     Рекурсия и итерация в некотором смысле противоположны. Рекурсия решает задачу от сложного к простому, итерация - от простого к сложному. Текст рекурсивного алгоритма выражает сложный объект через более простой (более простые) такого же типа. Текст итеративного алгоритма описывает процесс строительства, начиная с мелких деталей.     Рекурсивный алгоритм […]

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

    На этом шаге мы рассмотрим частично рекурсивные функции.     Пусть задана функция f(x1, ..., xn, y).     Определение. Говорят, что φ(x1, ..., xn) получена из f(x1, ..., xn, y) с применением операции ограниченной минимизации, если имеет место следующее равенство: (44) и обозначают φ(x1, ..., xn) = μγ(f(x1, ..., xn, y) = 0). (45) Лемма […]

Операция ограниченной минимизации

    На этом шаге мы рассмотрим операцию ограниченной минимизации.     Пусть задан всюду определенный предикат p(x1, ..., xn, y).     Определение. Говорят, что функция φ(x1, ..., xn, z) получена из предиката p(x1, ..., xn, y) в результате операции ограниченной минимизации, т.е. φ(x1, ..., xn, z) = μγy<=zp(x1, ..., xn, y), если выполняются следующие равенства: (33) […]

Кусочное задание функции

    На этом шаге мы рассмотрим кусочное задание функции.     Пусть задана совокупность функций {f1, ..., fk, fk+1} и совокупность предикатов {p1, ..., pk}, где fi = fi(x1,..., xn), i=1, 2, ..., k, k+1 и pj = pj(x1,..., xn), j=1, 2, ..., k, причем области истинности предикатов попарно не пересекаются.     Введем следующие обозначения: x […]

Операция навешивания ограниченного квантора над предикатами

    На этом шаге мы рассмотрим операцию навешивания ограниченного квантора над предикатами.         Пусть задан двуместный предикат p(x,y), где в общем случае x = (x1, ..., xn).     Определение. Говорят, что предикат R(x,z) получен из предиката p(x,y) с применением операции навешивания ограниченного квантора существования, т.е. R(x,z) = (∃y)y<=zp(x,y), если выполняется следующее равенство: R(x,z) = […]

Примитивно рекурсивный предикат

    На этом шаге мы рассмотрим примитивно рекурсивный предикат.     Как нам известно, предикатом называют логическую функцию определенную на заданном множестве объектов. Будем рассматривать в качестве области определения предиката конечный набор, состоящий из натуральных чисел. Таким образом, рассматриваемые предикаты представляют логические функции вида:     В качестве примера предикатов можно привести следующие логические функции: ; ; […]

Операции навешивания кванторов

    На этом шаге мы рассмотрим операции навешивания кванторов.     В логике предикатов кроме операций отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности, рассматриваются и операция навешивания квантора всеобщности и квантора существования.     Пусть на множестве М ≠ ∅ задан одноместный предикат p(x).     Определение. Будем говорить, что выражение вида ∀x p(x) на множестве M представляет собой […]

Понятие предиката и логической функции. Логические операции с предикатами

    На этом шаге мы рассмотрим понятие предиката и логической функции. Логические операции с предикатами.     Предикат - логическая функция, определенная на некотором множестве M, то есть такая n-местная функция p, которая каждому упорядоченному набору (x1, ..., x1) из множества M сопоставляет некоторое высказывание, обозначаемое p(x1, ..., x1). В этом случае p называется n-местным предикатом […]