Информатика и компьютерные науки (стр. 3 из 14)

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

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

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

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

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

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

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

Пример (алгоритмы Маркова). Пусть задана система текстовых замен R на множестве символов {v, ~, true, false, (, )} для редукции булевских термов, которые построены только из символов данного множества, к нормальной форме. Эта система состоит из следующих правил:

(1) ~ ~ ® е

(2) ~ true ® false

(3) ~.false ® true

(4) (true) ® true

(5) (false) ® false

(6) false v ® e

(7) v false ® e

(8) true v true ® true

Алгоритм, определенный данной системой, работает по марковской стратегии корректно для замкнутых булевских термов (т. е. замкнутые булевские термы переводятся в семантически эквивалентные однозначные нормальные формы, состоящие из true и false). Это справедливо лаже для замкнутых термов с неполностью расставленными скобками. Однако в этом случае возможны такие применения, которые не являются эквивалентными преобразованиями. Для терма

-.true v true по марковской стратегии получаются вычисления

-.true v true ® (правило (2) )

false v true ® (правило (6) )

true

В общей недетерминистической стратегии дополнительно получают (в смысле постановки задачи корректное) вычисление

- true v true ® (правило (8) )

- true ® (правило (2))

false

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

2.1.4. Отображения, индуцируемые алгоритмами текстовых замен

Путем сопоставления выходного слова каждому входному слову при конечном вычислении детерминистические алгоритмы вычисляют частичные функции. Функции являются частичными, так как иногда при некоторых исходных данных алгоритмы не завершаются и потому результат вычислений не определен. Это имеет место также и для АТЗ. Явного использования частичных функций можно избежать путем введения особого символа -^ ("дно"), который символизирует отсутствующий "результат" незавершающегося ("расходящегося") вычисления.

Каждый детерминированный алгоритм R в форме СТЗ на последовательностях символов V* определяет отображение:

fR: V* ® V* U ^ вследствие следующих правил. Пусть справедливо:

(1) fR (t) = г, если слово г есть результат вычислений по R для входного слова t;

(2) fR (t) = ^, если вычисление по R для входного слова t не заканчивается.

Тогда мы говорим: алгоритм R вычисляет функцию fp .

Обратим внимание, что для слов t, для которых выполнение СТЗ не завершается, отображение fR дает результат ^. Символ ^, таким образом, обозначает (псевдо)результат незавершающегося вычисления. С помощью введения этого символа обходят явную работу с частичными отображениями.

Если слова t Î V* понимать как представления определенных информации из множества А, т. е. существует функция интерпретации такая, что (А, V*, I) образует информационную систему, и если функция fR , индуцируемая алгоритмом R, согласована с интерпретацией, то R индуцирует также функцию между информациями, т. е. R индуцирует отображение интерпретаций.

Пример (умножение чисел, представленных количеством штрихов). Пусть интерпретация числа штрихов определяется отображением

I:{<, |,>}* ® N

с 1(<|...|>) = п для слова <|...|> с п штрихами. Тогда алгоритм умножения так представленных чисел со входом

<|...|> * <|...|> —» <|...|>

n m n*m

I¯ I¯ I¯

mult (n, m) = n*m

индуцирует отображение пары чисел на их произведение» т. е. отображение умножения.

Детерминистические АТЗ порождают частичные отображения на словах и тем самым, поскольку слова служат для представления информации и отображение согласовано с интерпретацией, частичные отображения между соответствующими информациями. Недетерминированные алгоритмы определяют отношения. С системой замен R на V мы связываем отношение (граф, который вычисляется через алгоритм)

GR Í V*x(V* U ^), определяемое следующим образом:

GR = { (t, r) Î V* х V* : г - выходное слово вычисления по R с входным словом t}

U {(t, ^) Î V* х {^} : существует бесконечное вычисление по R для входного слова t}.

Обратим внимание, что в отношении gr для каждого входа t существует выход r Î V*U{^}.

Пример (недетерминистический алгоритм с неоднозначным результатом). Пусть вход имеет форму Ð<|||...|>. Пусть задана система замен R с правилами:

Ð< ® <Ð

Ð| ® |Ð|

Ð| ® ||

Ð> ® |>

Так заданный алгоритм R по любому натуральному числу n (представленному в виде числа штрихов) порождает натуральное число m, большее, чем n, либо не завершается. На рис. 2.2 приведена схема дерева всевозможных вычислений для входа V<| ||>.

Рис. 2.2. Дерево вычислений

Получается следующее отношение (при интерпретации последовательности штрихов как натурального числа):

GR = { (n, m): n Î N^((m Î N ^ n<m) v m=^

Детерминистические алгоритмы вычисляют функции. Это ставит вопрос о том, могут ли все математические функции вычисляться с помощью алгоритмов. Один из фундаментальных результатов современной математической логики принадлежат логику Курту Геделю и отвечает на вопрос о вычислимых функциях, представимых через алгоритмы. Упрощая ф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

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