Рекурсивный преобразователь

Cтраница 1

Рекурсивные преобразователи являются естественным обобщением дискретных преобразователей. Они описывают более общий класс алгоритмических систем, включая рекурсивные программы и сложные технические устройства. [1]

Описываются рекурсивные преобразователи информации, отно-сящиеся к автоматной модели алгоритма и охватывающие широкий класс сложных алгоритмических систем - рекурсивные программы, вычислительные устройства, различные иерархические управляющие системы. Излагаются виды рекурсивного взаимодействия5 проблемы разрешимости алгоритмов; недетерминизм в задании программ; преобразования рекурсии в более простые формы; рекурсивные алгоритмы в конкретных вычислительных средах; схемы программ и преобразователей. [2]

Так как рекурсивные преобразователи над памятью являются расширением класса стандартных схем, то все проблемы ( типа функциональной эквивалентности), неразрешимые для стандартных схем, неразрешимы и для рекурсивных преобразователей. С другой стороны, разрешимые случаи в классе стандартных схем могут оказаться неразрешимыми или неизвестными для рекурсивных преобразователей. Интересным примером является проблема функциональной эквивалентности для схем с одной переменной. С одной стороны, хорошо известно, что для схем Янова она разрешима ( см. следствие 7.9), но для унарных рекурсивных схем ( схем Де Баккера и Скотт) - это известная открытая проблема. Доказано, что эта проблема равносильна проблеме эквивалентности в классе детерминированных КС-языков. Отсюда, в частности, следует, что проблема эквивалентности в классе LA ( 1) - систем равносильна проблеме эквивалентности для недетерминированных языков. [3]

Содержательная математическая теория рекурсивных преобразователей может быть построена при помощи следующей схемы уточнений ( рис. 1.6): конкретизация класса базовых преобразователей 31, классификация правил а, характеризующих взаимодействие преобразователей из 31; выбор конкретных вычислительных сред. [4]

Траектория вычислений в случае рекурсивного по управлеч нию вызова преобразователем AI преобразователя Л у. [5]

Рассмотрим основные типы рекурсивных преобразователей. [6]

Излагаются способы представления рекурсивных преобразователей и их взаимосвязь: операционное задание через систему взаимодействующих базисных преобразователей; функциональное задание в виде систем уравнений; автоматное представление - в виде автоматов, дополненных магазином или стеком. [7]

Партитура параллельного взаимодействия. [8]

Интерес к изучению рекурсивных преобразователей обусловливается многими причинами. [9]

Как уже неоднократно подчеркивалось, рекурсивные преобразователи отражают основные свойства рекурсивной организации вычислений из базового набора вычислителей. В качестве базовых преобразователей целесообразно выбрать конечные преобразователи, так как системы обработки информации с конечным числом управляющих состояний являются основным, достаточно изученным классом преобразователей, применяемых как в программировании, так и в аппаратной реализации ЭВМ и других технических систем. [10]

Представим этот алгоритм в виде рекурсивного преобразователя, обрабатывающего структуру данных V с переходами, задаваемыми сдвигами / иг, где / - соответствует сдвигу По левой дуге, г - по правой. Преобразователь Мг имеет пять управляющих состояний - ( а0, alt а2, а3, я4), состояние а0 - начальное, аа - заключительное. [11]

Следует остановиться и на прагматическом аспекте рекурсивных преобразователей. [12]

Ханойская башня для трех дисков. [13]

Теперь нетрудно представить процесс в виде рекурсивного преобразователя. Вычислительной средой является пространство значений вектора ( v, m, х, у, z), к которому добавляются еще три невидимые компоненты Т ( х), Т ( у), Т ( г), обозначающие наполнение дисками башен на стержнях х, у и г соответственно. Компоненты Т ( х), Т ( у) ц Т ( г) меняются операторами перемещения дисков, имеющимися в задании алгоритма. С целью сокращения записи эти компоненты не указываются. Сигналом для преобразователя служит значение величины т - количество дисков на исходном стержне. Удобно отделить процесс ввода данных от процесса обработки. [14]

Шестая глава - посвящена общему определению рекурсивного преобразователя и его частным случаям. [15]

Страницы: 1 2