Лекции 3—5. Формализация понятия алгоритма (1107980), страница 2
Текст из файла (страница 2)
Среди состоянийМТ выделяются «начальное состояние» q0 и «состояние останова» qs. В начале работыМТ на ленту записываются начальные данные – слова над входным алфавитом A. Лента МТ с записанными на ней данными (например, словом 0010111001011100000) итекущим положением УГ может быть изображена следующим образом (Λ представляетпустую ячейку ленты, остальные символы представляют самих себя, ОЯ обозначенарамочкой вокруг обозреваемого символа под рамочкой указано текущее состояние УГ):...ΛΛΛΛΛΛΛΛΛΛΛΛΛΛ0010111001011100000ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ...qНа каждом такте работы МТ УГ считывает символ из ОЯ, и в зависимости от этогосимвола и состояния УГ может записать в ОЯ новый символ, перейти в новое состояние, и передвинуться на следующую слева или справа ячейку ленты, либо остаться наместе.7.3.
Пример МТ. Проверка правильности скобочных выражений, т.е. последовательностейоткрывающих и закрывающих скобок.Правильным называется скобочное выражение, удовлетворяющее следующим двумусловиям: (1) число открывающих скобок равно числу закрывающих, (2) каждаяоткрывающая скобка предшествует парной ей закрывающей скобке. Например,(( ))( ) – правильное скобочное выражение, а )( или (( ) – неправильные скобочные выражения.Если скобочное выражение правильное, МТ должна записать на ленту результат 1 иостановиться, если нет, – записать 0 и остановиться.
Таким образом, после работы МТна ленте должен быть записан только результат: 0 или 1, и УГ должна быть установлена на ячейке, в которой записан результат.Рабочий алфавит: S = {(, ), 0, 1} ∪ {Λ, X} (Λ и X – маркеры).Алфавит состояний Q = {q0, q1, q2, q3, qs}:q0 – начальное состояние МТ: поиск ближайшей справа закрывающей скобки “)”,замена ее на маркер Х и переход в состояние q1. Если, дойдя до конца слова,закрывающей скобки не нашлось – переход в состояние q2 и движение влево;qs – состояние останова;q1 – поиск парной открывающей скобки при движении влево, замена её на Х ипереход в q0;q2 – достигнут конец выражения и при этом не найдено закрывающей скобки:движение влево, стирая все маркеры X; при достижении левого конца выражения (Λ) – запись результата 1; при обнаружении открывающей скобки –переход в состояние q3, так как выражение неправильное.q3 – выражение неправильное: движение влево, стираем символы ( и Х, запись результата 0 в первую пустую ячейку и переход в состояние qs.Описание данной МТ с помощью «пятерок» вида :состояние, символ → состояние, символ, направлениенаправление: L – влево, R – вправо, H – на месте5(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годq0, ( → q0, (, R;q1, ( → q0, X, R;q2, ( → q3, Λ, H;q3, ( → q3, Λ, L;q0, ) → q1, X, L;q1, ) → q1, ), L;q2, ) невозможна;q3, ) невозможна;q0, X → q0, X, R;q1, X → q1, X, L;q2, X → q1, Λ, L;q3, X → q3, Λ, L;q0, Λ → q2, Λ, L;q1,Λ → q3, Λ, R;q2, Λ → qs, Λ, H;q3, Λ → qs, 0, H;Описание МТ («Пятерки») можно наглядно представить с помощью таблицы:qi ↓ \ sj →q0q1q2q3(q0, (, Rq0, X, Rq3, Λ, Нq3, Λ, L)q1, X, Lq1, ), L——Xq0, X, Rq1, X, Lq2, Λ, Lq3, Λ, LΛq2, Λ, Lq3, Λ, Rqs, 1, Нqs, 0, Н7.4.
Можно показать, что любую МТ можно перестроить таким образом, что она будет, вычислять ту же функцию, что и исходная, но при этом удовлетворять следующим двумусловиям (соглашениям или ограничениям):(1) в начальном состоянии (q0) УГ установлена на ячейке, в которой записанпервый символ исходного слова,(2) в состоянии останова (qs) УГ установлена на ячейке, в которой записан первый символ слова-результата функции F, вычисляемой этой МТ.Такая МТ называется нормальной МТ.
Переход к нормальным МТ существенно упрощает проблему построения композиции МТ и открывает возможность представлениясложных МТ как композиции более простых МТ.7.5. Диаграммы Тьюринга (ДТ).7.6. Композиция МТ.7.7. Понятие Универсальной МТ.7.8. Проблема останова. Понятие об алгоритмической неразрешимости проблем.8. Нормальные алгоритмы Маркова8.1.
Определение нормального алгоритма Маркова (НАМ)8.1.1. Подстановки. Рассмотрим два непересекающихся алфавита: алфавит основныхсимволов V и алфавит маркеров V'. Мы будем рассматривать множества слов V*и (V∪V')*. Подстановка σ → σ′ задает замену в рассматриваемом слове (τ) подслова σ ∈ (V∪V′)*, указанного в левой части подстановки на слово σ′ ∈ (V∪V')*,указанное в правой части подстановки. В результате исходное словоτ = ασβ ∈ (V∪V^)* превращается в слово τ′ = ασ′β ∈ (V∪ V')*.Заметим, что 1) подслова α и β могут быть пустыми (ε); 2) из всех возможныхпредставлений исходного слова τ в виде τ = ασβ выбрается такое представление,в котором длина подслова α (|α|) минимальна, и для него осуществляется замена.Если обрабатываемое слово (τ) не содержит подслова σ, то подстановка считается неприменимой. Символ-стрелка → ∉ (V∪V') называется метасимволом. В некоторых подстановках вместо метасимвола «→» (стрелка) используется метасимвол стрелка с точкой «→.», означающий, что соответствующая подстановка является терминальной (завершающей).
Иногда для обозначения терминальнойподстановки в качестве метасимвола употребляют терминальную стрелку «|→»,ее смысл такой же, как и стрелки с точкой «→.» .6(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год8.1.2. Нормальный алгоритм Маркова задается конечной последовательностьюподстановок {p1, p2, … pn}. При этом:(1) если применимо несколько подстановок, применяется подстановка, котораявстречается в описании алгоритма раньше других;(2) при подстановке всегда рассматривается самое левое вхождение (длина α минимальна). Например, вхождением пустого слова (σ = ) в заданное слово (τ)считается пустой символ перед заданным словом (τ = ασβ, где α = , β = τ).(3) после применения терминальной подстановки алгоритм завершается;(4) если ни одна из подстановок неприменима, алгоритм завершается.(5) если алгоритм завершает работу8.1.3.
Пример. Шифр Юлия Цезаря. V = {a, b, c, …, z}, V' = {*}. j-ая буква латинскогоалфавита шифруется j+h (mod 26)-ой буквой того же алфавита. Например, дляh = 3 подстановки НАМ имеют вид (маркер * помечает текущую шифруемуюбукву, цифра в скобках – номер правила подстановки):(1)*A → D*, (2)*B → E*, (3)*C → F*, …, (23)*W → Z*, (24)*X → A*, (25)*Y → B*,(26)*Z → C*, (27)* →. , (28) → *Применим построенный НАМ к слову CAESAR:CAESAR (28)→ *CAESAR (3)→ F*AESAR (1)→ FD*ESAR (5)→ FDH*SAR (13)→FDHV*AR (1)→ FDHVD*R (12)→ FDHVDU* (27)→ FDHVDU8.1.4.
Пример. Копирование двоичных чисел: V = {0, 1}, V' = {*, #}8.2. Процедура интерпретации НАМНАМ – это упорядоченная конечная последовательность правил подстановок {p1, p2, …pn}, которые применяются к строке σ0 ∈ V* (исходная строка) или к строкам σi ∈(V∪V')*, i > 0 в соответствии со следующей процедурой:(1) Положить i = 0.(2) Положить j = 1.(3) Если правило pj применимо к σi , то перейти к (5).(4) Положить j = j + 1. Если j ≤ n, то перейти к (3). В противном случае – останов.(5) Применить pj к σi и найти σi+1. Положить i = i + 1. Если pj – нетерминальное правило, то перейти к 2. В противном случае – останов.Говорят, что НАМ применим к слову σ0, если в результате применения его к слову σ0произойдет останов.
Множество слов в алфавите А, к которым применим заданныйНАМ, называется областью применимости этого алгоритма.Если же, начиная работу над словом σ0, НАМ зацикливается, то он неприменим к слову σ0.8.3. Пример. Сложение чисел в единичной системе счисления. V = {+, 1}, V' = {}. Правилаподстановок:8.3.1. Первый вариант: {1+ → +1; +1 → 1; 1→. 1} («выгоняем» плюсы на левый крайслова (правило 1) и «стираем» (правило 2), в заключение применяем правило 3 иполучаем результат).Пример применения алгоритма:7(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годσ0 = «1111+11+111» = «1111+11+111» ⇒ «111+111+111» ⇒ «11+1111+111» ⇒«1+11111+111» ⇒ «+111111+111» ⇒ «111111+111» ⇒ «111111111» ⇒ «111111111»8.3.2.
Второй вариант: {+ → ε; 1→. 1} (стираем все плюсы).8.4 Эквивалентность алгоритмов.В приведенном примере для решения одной и той же задачи были составлены дваНАМ. Но таких алгоритмов можно было бы привести не два, а три, четыре, … - целыйкласс алгоритмов. Фактически, решая проблему составления алгоритма для решенияконкретной задачи, мы приводим в качестве результата – один из класса эквивалентныхалгоритмов, решающих поставленную задачу.Два алгоритма P и Q в алфавите А ( P : A* → A* , Q : A* → A* ) называются эквивалентными, если области применимости этих алгоритмов совпадают, и для любого слова σ0из области применимости эти алгоритмы получают одинаковый результат, т.е. P(σ0)=Q(σ0).8.5. Тезис Маркова. Любой алгоритм преобразования слов в алфавите V может быть представлен нормальным алгоритмом Маркова над алфавитом V.8.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
