Алгоритмы в виде текстовых замен в общем случае являются недетерминистическимн и недетерминированными. Для входного слова t суще­ствуют, как правило, многие разные вычисления с различными результа­тами. При этом для одной и той же задачи могут существовать как завер­шающиеся, так и незавершающиеся вычисления.

2.1.3. Детерминистические алгоритмы текстовых замен

Часто предпочитают рассматривать детерминистические АТЗ, т. е. алгоритмы, которые для каждого входного слова однозначно задают вычисления и тем самым в случае их завершения порождают вполне определенный результат. Это может быть обеспечено, например, установлением приоритетов применения правил. Такие приоритеты могут быть заданы просто порядком описаний правил.

Примером детерминистических алгоритмов являются так называемые алгоритмы Маркова (по имени русского математика А. А. Маркова). В алгоритмах Маркова правила замен линейно упорядочены (этот порядок определяется последовательностью описания правил). Тогда применение правил устанавливается следующим образом.

Определение (марковская стратегия применения). Если применимо несколько правил, то фактически применяется то из этих правил, которое в описании алгоритма встречается первым. Если правило применимо в нескольких местах обрабатываемого слова, то выбирается самое левое из этих мест.

Таким образом, марковские алгоритмы всегда являются детерминиро­ванными и детерминистическими. В частности, справедливо следующее:

- каждое вычисление по марковской стратегии является также общим вычислением в СТЗ;

- для каждого входного слова существует точно одно конечное или же бесконечное марковское вычисление; алгоритмы Маркова являются детерминистическими (а отсюда результат, если он существует, однозначно определен).

Пример (алгоритмы Маркова). Пусть задана система текстовых замен R на множестве символов {v,

Детерминистические алгоритмы вычисляют функции. Это ставит вопрос о том, могут ли все математические функции вычисляться с помощью алгоритмов. Один из фундаментальных результатов современной математической логики принадлежат логику Курту Геделю и отвечает на вопрос о вычислимых функциях, представимых через алгоритмы. Упрощая фopмулировку, результат Геделя говорит, что не всякая функция допускает ее вычисление с помощью алгоритма. Те функции, для вычисления которых может быть задан алгоритм, называют вычислимыми.

Имеется много различных формализации понятия "алгоритм" Некоторыми примерами этого являются:

- текстовые и термовые замены (редукция);

- рекурсивные функции;

-(тьюринговые) машины (а также регистровые машины).

Однако все эти формализации ведут к тому же самому понятию "вычис­лимые функции". Каждая вычислимая функция может быть вычислена с помощью АТЗ.

2.2. Вычислительные структуры

Алгоритмы работают над элементами данных, которые могут быть объе­динены в так называемый носитель (множества данных). Для формулиро­вания алгоритмов, наряду с используемыми элементами данных, весьма существенны имеющиеся в распоряжении эффективные функции над этими элементами. Фигурирующие в алгоритмах носители и операции могут трактоваться вместе как вычислительные структуры. Вычислительная структура охватывает тем самым семейство носителей (данные) и семейство отображений между этими носителями. Вычислительные структуры обнаруживаются в самых различных проявлениях. К примеру, карманный калькулятор, так же как и мощная ЭВМ, могут математичес­ки восприниматься и описываться как вычислительные структуры.

2,2.1, Семейства функций и множеств как вычислительные структуры

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

Определение (вычислительная структура). Пусть S и F - множества обо­значений; вычислительная структура А состоит из семейства {sА: s  S} носителей sА и семейства {fА: f  F} отображений fА между этими носителями. Мы пишем:

А=({sА: s  S}, {fА: f  F}).

Элементы s  S есть обозначения для носителей и называются типами. Элементы f  F есть обозначения для отображений и называются символами функции или знаками операций. Для каждого f  F существует 1 одно n  N такое, что имеет место: fА есть n-местная функция, и существуют типы s1…. sn+1  S такие, что



Может также быть и n = 0, т. e. допускаются и "нульместные" отображе­ния. Это такие отображения, которые (с пустым списком аргументов) получают в точности один элемент из области значений.

Для устранения частичных отображений снова используется специаль­ный элемент  ("дно") для представления неопределенного значения функции. Пусть М - множество, не содержащее . Множество M1 определяется как

M'=M U {}.

Элемент  представляет "неопределенный" результат функции, например в случае незавершающегося алгоритма.

Отображение f:M1 x...x Mn  Mn+1

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

Пример

(1) Вычислительная структура BOOL булевских значений Множество S типов вычислительной структуры BOOL задано так:

S = {Ьоо1}. Множество F символов функций структуры BOOL задано так:

F = {true, false, -, v, ^}. Множество носителей В1 сопоставлено типу Ьоо1, т. e. имеет место

boo|BOOL=B'= {L, О, }.

Символы из F обозначают следующие функции:

trueBOOL: . B',

faiseBOOL: B',

-bool : B'  B' (бесскобочный префикс),

^ ВооL: B' х В'  В' (инфикс),

v BOOL: B' х В'  В' (инфикс).

Причем для a, b  В имеет место

trueBOOL = L,

falseBOOL =o,

- bool b = not(b),

a vBOOL b = or(a, b),

а ^BOOL b = and(a, b).

Функции являются строгими и потому их значения для случая, когда один из аргументов есть , также установлены.

2.2.2. Сигнатуры

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

Определение (сигнатура). Сигнатура - это пара (S, F) множеств S и F, причем

S обозначает множество типов, т. е. имен для носителей;

F обозначает множество символов (имен) функций;

для каждого символа функции f  F пусть задана ее функциональное fct f  S+.

В дальнейшем для улучшения читаемости при задании функциональности для f мы будем писать

fct f=(S1,..., Sn)Sn+l, .

чтобы выразить, что fА в вычислительной структуре А с соответствующей сигнатурой  используется для обозначения отображения



Пример (сигнатуры). Сигнатура вычислительной структуры BOOL булевс­ких значении и натуральных чисел из вышеприведенного примера дает пример сигнатуры.

smat = (bool,),

fbool = {true, false, -i, v, ^},

fct true = bool,

fct false = bool,

fct = (bool) bool (бесскобочный префикс),

fct v = (bool, bool) bool (инфикс),

fct ^ = (bool, bool) bool (инфикс),



Рис.2.3. Диаграмма сигнатуры

Сигнатуры допускают наглядное графическое представление в виде диаграммы сигнатуры. Такая диаграмма для каждого типа содержит узел и для каждого n-местного символа операции - ребро с n входными узлами и одним выходным узлом. Для вычислительной структуры bool мы получаем диаграмму сигнатуры, показанную на рис. 2.3.

Задания одной только сигнатуры, конечно, недостаточно для того, чтобы однозначно охарактеризовать вычислительную структуру. Имеется много различных вычислительных структур с одной и той же сигнатурой.

Вычислительные структуры указывают на структурные свойств информационных систем. В частности, имеет место:

({sА : s  S}, S, T)

образует снова информационную систему с Т: S  {sА : s  S, причем T[s] = sА

Также ({fА: f  F}, F, I) с I: F {fА: f  F}, причем I[f] = fА являет информационной системой.

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

2.2.3. Основные термы

При заданной сигнатуре существует множество основных термов, кото­рые могут быть образованы с помощью символов функций сигнатуры. Пусть  = (S, F) есть сигнатура. Множество основных термов типа s с s  S определяется следующим образом:

(i) каждый нульместиый символ функции f  F с fct f = s образует основной терм типа s;

(ii) каждая последовательность символов f(t1, ..., tn) с f  F и fct f= (S1, ..., Sn) s есть основной терм типа s, если для всех i, 1 <= i <= n, ti есть основной терм типа si.

Множество всех основных термов сигнатуры  обозначим через W, a множество основных термов типа s - через Ws. Если не существует нульместных символов функций, то множество W пусто.

Если имеется вычислительная структура А с сигнатурой , то основные термы в А допускают интерпретацию. Переход от основного терма (представления) типа s к соответствующему элементу а из множества А называют интерпретацией t в А. Интерпретация IA поэтому означает отображение

IA: W  {а  sA; s  S}.

Для каждого основного терма t запись IA[t] обозначает интерпретацию I в А. Пишут также tA вместо IA[t]. Интерпретация получается заменой в основном терме символов функций на соответствующие функции:

IA[f(t1,...,tn)]=fA (IA[t1] ,.., IA[tn]).

В классической математике часто заданная интерпретация опускается и вместо tA просто записывается t; разницей между основным термом и его интерпретацией там сознательно пренебрегают.

Для каждой вычислительной структуры А сигнатуры  основные термы типа s  S могут использоваться как представления элементов из множества sA, которые связаны с типом s в А. Если для каждого элемента а (<>) носителей из А имеется представление терма, т. е. для каждого s и каждого а  sA (<>) существует основной терм типа s с tA = а, то А называется термопроизводимой, это равносильно требованию, что в соот­ветствующей информационной системе отображение интерпретаций является сюръективным.

Интерпретация ("значение") основного терма допускает соответствен­но вычисление терма. Один из простых способов организации такого вычисления представляют собой схемы.

2.2.4. Вычисления основных термов: схемы

Основные термы имеют характерную внутреннюю структуру. Основной терм образуется из символов функций и последовательности (иногда пустой) основных термов ("подтермов"), являющихся термами-аргументами.

Схема (или формуляр) для основного терма - это графическое представление вычислений при интерпретации этого терма; схема состоит из прямоугольников, в которые заносится интерпретация основных термов, и из подсхем для вычислений подтермов. Вычисление интерпретации основного терма допускает удобное его проведение по схеме. Поскольку интерпретация основного терма производится через значения интерпретаций его подтермов, эта интерпретация подтермов упорядочивается с помощью схемы, структура которой аналогична структуре самого основного терма.

Примеры (схемы).

(1) Основному терму ((1 + 2) * 3) - 4 с интерпретацией в N соответствует схема, показанная на рис. 2.4.



Рис. 2.4. Вычислительная схема

(2) Основному тepмy (true ^ false) v (false v ((false ^ true)) с интерпретацией в BOOL соответствует схема, приведенная на рис. 2.5.

true

false

false

false

true



Рис. 2.5. Вычислительная схема

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

2.2,5. Термы с (свободными) идентификаторами

Идентификатор ("обозначатель", "переменная", "неизвестное") - это держатель места ("имя") для терма (или элемента), который (позднее) может быть подставлен на это место. Идентификаторы могут пониматься как имена термов или элементов, которые будут конкретизированы только позднее.

Пусть  = (S, F) - сигнатура, и Х = {Xs: s  S} - семейство множеств идентификаторов. Пусть множества Xs идентификаторов попарно не пересекаются и отличны от символов функций в F. W(X) обозначает алгебру термов, распространенную на X, т. е. WI с I = (S, F u {х  Xs: s  S}) и fct x = s для х  Хs, где Xs обозначает множество идентификаторов (держателей мест, обозначений) типа s.

Примеры (термы с идентификаторами).

Уравнения с "неизвестными" в математике - это уравнения между термами с идентификаторами, например ax2 + bx + с = 0.

(2) Часто термы снабжаются свободными идентификаторами, чтобы определять функции. Функция f может быть определена через:

f: N  N с f(x) = 2х+ 1

Термы со свободными идентификаторами называются также полиномами. Вместо идентификаторов в термы могут подставляться другие термы. Соответствующее отображение называется подстановкой в термы с (сво­бодными) идентификаторами.

Пусть t - терм с идентификаторами, х - идентификатор типа s и г -терм типа s; через t [г/х] обозначается терм, который получается, когда идентификатор х заменяется на г. Этот процесс называется подстановкой.

Подстановки описываются формально, аналогично построению термов, с помощью следующих уравнении:

x [t/x] = t,

у [t/x] = у, если х и у - различные идентификаторы,

f(tl,...,tn)[t/x]=f(t1[t/x],...,tn[t/x]), где f  F с fct f= (S1, .... Sn) Sn+1 и термы ti имеют типы si;.

Через t [t1|/X], ..., tn/Xn] обозначается терм, который возникает из терма t при одновременной подстановке ti вместо (попарно различных) иденти­фикаторов Xi.

Пусть t - терм с (свободными) идентификаторами. Терм г назовем экземпляром t, если г получается из t путем замены (подстановки) в нем определенных (свободных) идентификаторов.

2.2.6. Интерпретация термов с (свободными) идентификаторами

Пусть А - вычислительная структура с сигнатурой  = (S, F), а Х - семей­ство множеств идентификаторов. Отображение

b: {х  Xs: s  S}  {а  sA : s  S},

которое каждому идентификатору х в X типа s ставит в соответствие элемент а  sA структуры данных sA типа s, называется конкретизацией Х (в А).

Для каждой конкретизации b определяется интерпретация IAb терма t со свободными идентификаторами из Х с помощью следующих равенств:

IAb[x]=b(x), IAb [f(t1,…,tn)]=fA(IAb [t1],…, IAb [tn]),

лтя n = 0 получается IAb [f] = fA .

2.2.7. Термы с (свободными) идентификаторами как схемы

Термы со свободными идентификаторами могут играть роль схем, в кото­рых не все значения определены.

Пример (из геометрии). Площадь S кольца s с внутренним радиусом г и внешним радиусом R получается по формуле

S = (R2 - r').

Терму в правой части формулы соответствует схема, приведенная на рис. 2.7.


1   2   3   4   5   6   7

скачати