lekcii5 (Лекции), страница 14

диигралсмерах, выходными языками которых обычно являются С, :+, 1ГГМ1, 3ачаЯсг1р1 или Я! . Кроме того, необходимо заметить, .что доказательство взаимной эквивалентности программ и диаграмм '!'ыоринга существенно проще, чем, например, строгое сопоставление Паскаля и Си. Лекция 8 2.3 Нормальные алгоритмы Маркова В 1947-1954 гг. академик А. А. Х!арков (мл.) предложил алгоритмическую систему, в которой, как и в машине Тьюринга, преобразуются текстовые сообщения, но на основе других принципов ~3, 25~. Элементарными тактами обработки алгоритмов Маркова являются за; мены подслов исходного сообщения на некоторые другие слова.

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

Э го может быть обеспечено, например, установлением приоритета применения правил. Такие приоритеты могут быть заданы линейным порядком их записи ~20~. В алгоритмической системе Маркова нст понятия ленты и подразумевается непосредственный доступ к различным частям преобразуемого слова. Марковская стратегия применения правил заключается в следуклцем: 1.

сели применимо несколько правил, то берется правило. которое встречается в описа,нии алгоритма первым; 2, если правило применимо в нескольких местах обрабатываемого слова, то выбирается самое левое из этих мест. Поскольку нет никакой свободы в выборе очередного шага обработки, алгоритмы Маркова являются детерминистическими. Поскольку результат алгоритма Маркова этой стра.- тегией определяется однозначно, то он также является детермина1нтатым. Итак, нормальный алгоритм Маркова (НАМ) представляет собой упорядочешпяй набор правил-продукций пар слов (цепочек знаков, в том числе пустых цепочек длины О), соединенных между собой символами — ~ или ~-~.

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

Если же какую-то продукцию не удалось применить, проверяется следующая за ней, и так далее. Процесс выполнения нормального алгоритма заканчивается в одном из двух случаев: либо все формулы оказались неприменимыми, т. е. в обрабатываемом слове нет вхождений левой части ни одной формулы подстановки; либо только что применилась так называемая терминальная (завершающая) продукция, в которой правую и левую часть разделяет символ ~ . Терминальных продукций в одном НАМ может быть несколько. В любом из этих случаев нормальный алгоритм применим к данному входному слову.

Если же в процессе выполнения нормалыюго алгоритма бесконечно долго применяются нетерминальные правила, то алгоритм неприменим к данному входному слову. Существует два простых достаточных признака применимости НАМ ко всем входным словам ~3~: 1. левые части всех продукций непустые, а в правых частях пет букв, входящих в левые части; 2.

в каждом правиле правая часть короче левой. Рассмотрим примеры НАМ. Алгоритм кодирования по Цезарю: т. е, нам необходимо сопоставлять каждой очередной букве а., исходного слова, «следующую» кодированную букву а, з б„„а 26р В отличие от машины Тьюринга, передвигаюгцей головку вдоль ленты. нормальный алгоритм Маркова не имеет такого же непосредственного доступа к очередной букве обрабатываемого сообщения.

Однако текущая позиция в обрабатываемом по Маркову слове может быть смоделирована с помощью маркерного или курсорного символа, исследованного учениками Маркова, Нагорным и В. С. ~1ернявским ~106~. Маркер является дополнительной несобственной буквой рабочего алфавита, помечающей интересующее нас место в обрабатываемом слове. Заметим., что метасимволы в НАМ игранет ту же роль, что и промежуточные состояния в МТ. ФА — ~ ВФ (1) ~ — ~ Е4 (2) Ю- Е» ~Х вЂ” ~ А~ ~У вЂ” ~ В~ ~Š— ~ С1 (23) (26) (25) (26) (27) (28) Первые 27 правил нагпего а;шоритма не применимы ни к каким правильным исходным данным, поскольку они нс могут содержать несобственного знака ~.

Следовательно, сработает 28-ое правило, которое поставит ~ вместо первого пустого слова, т. е. в начало псрекодирусмой последовательности. После чего, согласно правилам исполнения НЛМ, для поиска следующей применимой продукции они будут перебираться сначала. Теперь одно из первых 27 правил может быть применено. Причем 27-ое правило сработает для пустого слова, к которому алгоритм тоже применим, а одно из правил (1)-(26) пригиенится к первой букве слова, перекодируя ее и перебрасывая звездочку к следующей букве.

Далее эта операция перекодирования с продвижением курсора повторяется до тех пор, пока не исчерпан)тся оуквы входного слова. Это произойдст, когда маркер окажется за последней буквой и ни одно из 26 первых правил не будет применимо. Проследим за работой марковского алгоритма, кодирующего имя императора, давшее название коду: Правило В резузп.тате работы алгоритма маркер движется вправо до конца слова, пока пс будет удален терминирукицим правилом (27). оо Слово САЕЯАК ~САЕЯАК ГэАЕЯАН РРФЕЯАК ГЭНФЯАК РЭНЧ~АК РЭНЧРФК ЕпНЧ1Б4' РВНЧ1Б (8) (1) (б) (18) (1) (12) (27) Для некоторых задач требуется два и более маркеров.

Например, копирование слова требует пометки исходной и целевой позиций обрабатываемого слова. оДЬ вЂ” ~ 136о аД вЂ” ~ ВЬ~За Ь вЂ” ~ с ( Я ) — ~ При копировании слова возникает проблема постановки копии очередной буквы на правильную позицию (как мы знаем, НАМ не в состоянии обратиться к конкретной позиции). Для этого в описанном выше изощренном алгоритме используется буква а, чтобы пометить текущую букву оригинала. Согласно правилу (2), буква копируется, маркер а перемещается за нее, а букву и ее копию разделяет маркер 6.

Если копируемое слово содержит более одной буквы, то маркер Ь используется для перемещения копии буквы на подходящее место. Если перед маркером 6 расположены две буквы слова подряд, т. е. без маркеров, то эти буквы меняются местами, а курсор занимает позицию между ними. Таким образом, всякая копия буквы снабжается префиксом в виде маркера 6. При этом сначала вводимая, а потом удаляемая буква с совсем не лишняя. Без нее алгоритм будет работать неверно. Нижеприведенный пример поможет понять работу этого алгоритма: Правило За.иечаяие.

Буквы о и Д в алгоритме копирования слова используются в качестве метасимволов. Они не входят в алфавит алгоритма, а лишь обозначают буквы субалфавита 10, 11, сокращая запись алгоритма. Рассмотрим еще один класс НАМ вЂ” присоединяющие алгоритмы ~25~. Дописывание 0 к двоичному слову ~0 — ~ 0~ 4 1 — ~ 1~ — 0 Выделение первого слова в последовательности типа 1004'0110 ~0— Ф1 — э Ф Выделение последнего слова в последовательности ОФ вЂ” ~ ж 1~ — ~ ~ 56 Слово 101 п1 01 И1а01 И1060а1 160610а1 160610161п 160611601а ИОЬИ101а 101101 Ж (2) (2) (1) (2) (1) (1) 1З) (1) (2) 16) (4) (5) (6) Высокий уровень НАМ в сравнении с МТ особенно ярко проявляется в рекурсивных правилах вычисления выражений.

Приведем соответствующий алгоритм для вычисления частного класса булевских константных выражений, заданных па множестве символов ~Ъ', -, багие, Га1ве, (, )): — Ка1ве — багие Ыие Га1ве Нормальные алгоритмы Маркова весьма оригинально применяются для арифметических вычислений: вместо числовых расчетов обрабатываются текстовые изображения чисел. Во-первых, для марковской алгоритмизации работы с целыми числами полезны натуральная и кардинальная системы счисления, в которых, напомним, число 3 изображается как «~ Й» и «~ ~(~» соответственно. Тогда сложение операндов, разделегшых», реализуется в одно действие (для кардинальной системы нужно удалить лишнюю палочку из суммы): Некоторая сложность вычитания обусловлена его алгебраичностькк Этот алгоритм вычисляет модуль разности. Е< ли же использование в качестве разности меныпего и большего чисел модуля их разности неприемлемо, то можно выдать нулевой результат.

Этот распространенный случай, видимо, происходит от мапппппях команд сравнения двух чисел. Если левый операнд 57 - багие -Ха1ве (1,где) (1а1не) Га1веЪ' ЪТа1ве багие «' багие (1) (2) Ж (1) (5) (б) (7) (8) оказь!вается бо'!Ьпю правого, то результа.т операции явх!яется положительеюй разнос'!'ыо этих чисел, иначе нуль. Таким образом, эта операция является булевской, поскольку нуль означает «ложь», а не нуль «истина».

11адо отметить, что именно так трактуются логические выражения в ассемблере и Си. Приведем этот алгоритм: После успешного обычного вычитания стирается остаток, если он оказался справа от разделителя операндов в случае, когда вычитаемое больше уменьшаемого и результат полагается равным О. Терминирующее правило стирает сам разделитель. Мультипликативныс операции чуть сложнее, если нс считать операций типа вычисления остатка от деления на 5 в на гуральной системе счисления: В ЭВМ операции деления и взятия остатка, как правило, неразделимы.

С помощью НАМ можно реализовать такую комбинированную операцию (подразумевается, что второй операнд - - снова пять палочек «)()(!»1: Частное от деления на 5: Инкремент двоичного числа (уже в позиционной системс счисления!); >1 » 1> >Π— 0> 58 <о 1 1 > 1< о< < Поразрядная импликация лвои иного числа: Проверка числа, на нечетностгя е11 е10 е01 е00 е1 еО е1 еО Более сложный алгоритм (20! умножение двух чисел, заключенных в угловые скобки и разделенных звездочкой (заметьте, что здесь нет терминальных продукций!): ! >ч« с(! с)ш с(> <>э< е! >Ж<Д ! ше( шее > <е е сО с1 с Оа 1а О(0) 0(1) 1(0) 1(1) О~ (0) 0~(1) 1ч' (О) 1~'(1) [о]о [0] 1 [1] 0 [1] 1 [О] Ь [1] Ь Ос 1с а (0)Ь (1) Ъ (0) 0 (1) 0 (0) 1 (1) 1 *[1] *[1] *[О] *[1] О [О] 1 [О] 0 [1] 1 [1] аО а1 .