Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекция 2
Тьюринга. Машина состояний и логическая структура алгоритма. Блок-схема алгоритма. Нормальный алгоритм. Программный монитор.
1. Алгоритмические проблемы.
Необходимость точного определения алгоритма возникла в 20 – 30х ХХ в. при решении чисто математической проблемы вычислимости и разрешимости множеств.
Вычислимость. Множество А(А М) вычислимо, если существует некоторая процедура П, порождающая все элементы а А и только их.
Пример 1. Задано множество действительных чисел – D и уравнение y = ax + b, определенное на четверках чисел D4 = M. Обозначим множество четверок, которое удовлетворяет уравнению, через А. Множество А вычислимо, т.к. существует процедура П(a, b, x) y, которая по любой тройке <> вычисляет . Эта процедура известна из 5–го класса средней школы. – обозначают конкретные числа.
Разрешимость. Множество А разрешимо на М (А М), если существует процедура (алгоритм), которая для любого m M определяет, принадлежит ли m к А (m A) или нет (m A).
Вообще говоря, проблема разрешимости сводится к вычислимости соответствующего предиката
Р(m)= .
Пример 2. Пусть А есть множество решений уравнения y = ax + b. Существует тривиальный алгоритм П проверки для каждой четверки <> D4 в виде подстановки этих чисел в уравнение и выполнения указанных в уравнении действий, который вычисляет предикат
П(y, a, x, b).
и таким образом решает проблему разрешимости для заданного уравнения.
Понятие алгоритма в обиход математики ввел немецкий математик Шрёдер (1912–14), назвав «достаточно простую» механическую процедуру по имени арабского математика Ал–Хорезми (IХ в.) алгоритмом.
Пример 3. Проблема Ферма.
Для уравнения xn + yn = zn, где x ,y, z, n N, можно ли предложить алгоритм П, порождающий все решения уравнения при заданном «»? П. Если такой алгоритм П(n) существует, то говорят, что он решает проблему вычислимости множества решений уравнения xn + yn = zn. Решение этой проблемы может быть двух типов: а) алгоритм не существует, б) алгоритм пока не известен(не открыт). Разрешимость множества решений уравнения xn + yn = zn решается просто, т.к. имеется тривиальный алгоритм для любой четверки , вычисляющий предикат
П.
Например,
– истина; но
– ложь.
Множество решений уравнения xn + yn = zn разрешимо, но не вычислимо (пока не известен алгоритм или он не существует).
Существует взаимосвязь между вычислимостью и разрешимостью.
Всегда 1) если А вычислимо в М, то А разрешимо в М;
2) если А разрешимо в М, то из этого не следует его
вычислимость.
Проблемы разрешимости и вычислимости множеств требуют точного определения понятия алгоритма. Точного понятия алгоритма нет и никогда не будет сделано по причине очень «туманного» содержательного объекта, который необходимо формально определить. В этом случае математики предложили некоторый точно определенный инструмент, при помощи которого можно конструировать любые интуитивно понятные порождающие (вычисляющие) и распознающие (разрешающие) процедуры.
Алгоритм, как точно определённый инструмент, для конструирования процедур должен обладать следующими свойствами.
2. Типы алгоритмов. История создания.
За 30–40 годы ХХ столетия интенсивного поиска универсального уточнения алгоритма было предложено примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа.
Основные АМ, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов были предложены в ХХ в.
Основное внимание уделяется механизму конструирования функций из базового набора элементарных функций, определенных на некотором фиксированном множестве.
Любая функция, вычислимая на интуитивном (содержательном) уровне, должна быть сконструирована из базовых .
Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.
Любые языки программирования, которые имеются на сегодняшний день, так и те, с которыми придется встречаться в будущем, должны быть формально описаны. Под формальным описанием всегда скрывается некоторая содержательная логика, которая иногда явно, а иногда неявно присутствует в определениях языка.
3. Структура алгоритма (составляющие алгоритма)
а) структурой (структурным описанием) б) процедурно (последовательностью базовых операций).
Языки программирования содержат оба способа задания функций.
В дальнейшем будут рассмотрены примеры всех трех типов алгоритмов: а) АМ – Машина Тьюринга и Нормальный алгоритм Маркова, б) функции вычислимых алгоритмом, использующие конструкции рекурсивных функций Клини, в) формальные порождающие грамматики Хомского и распознающие автоматы (конечные и магазинные автоматы).
4. Машина Тьюринга (МТ).
1) (запись обозначает: МТ определяется формально четверкой конечных множеств), где
2) Интерпретация МТ.
а) Процессор – в МТ называется управляющей головкой (УГ).
б) Структура данных (память процессора) бесконечная лента, разбитая на ячейки, в ячейку может быть записан только один символ , ячейка может быть пустой.
в) Процесс вычислений (см.рис.1) происходит по тактамв каждом ti УГ выбирает и выполняет правила в зависимости от собственного состояния и информации, записанной на ленте. Если УГ находится в состоянии и указатель головки стоит напротив ячейки, где записан символ аi (видит аi), то головка заменяет его на символ аj, переходит в состояние Sj, производит действие dj (Л – сдвигается на ячейку влево, П – сдвигается на ячейку вправо, Н – остается на месте, stop – МТ останавливается).
В начальном такте (t0) УГ находится всегда в состоянии S0, «смотрит» на некоторую ячейку ленты и «ждет» внешнего сигнала «пуск», чтобы начать работу.
г) Процесс остановки (остановка) МТ.
МТ – останавливается в двух случаях:
д) Процесс «вечной» работы МТ означает для порождающей МТ благополучную ситуацию, когда порождаемое слово может быть бесконечной цепочкой символов. Для распознающей МТ ситуация не предсказуема (либо МТ ещё не нашла значение предиката, либо имеется ошибка в программе).
е) Список правил для МТ не упорядочен. Поиск правила происходит по условиям (Si, ai), возникшим в ti такт.
Пример 4. Сложение двух чисел x и y в унарной системе, как пример порождающей МТ. – ограничители (спейсеры) слова, расположенного на ленте. Начальное состояние, ленты , где (в десятичной «1»), (в десятичной«2»). УГ сдвинута (установлена) на левый спейсер «(». Результат порождения .
– алфавит состояний, переход в то или иное состояние, определяет логику работы алгоритма.
Правила Условие П: Команда (программа)
если , то «» означает
«заменить на»
если , то
если , то
если , то
если , то
если , то
Логическую структуру алгоритма (ЛСА), содержащую все возможные последовательности команд удобно показывать на графе «переходов», (см.рис.2а).
Граф переходов МТ есть направленный бинарный граф , где S – вершины, которые соответствуют множеству состояний МТ; V – множество дуг, которые соответствуют переходам (правилам).из состояния Si в состояние Sj,; каждая дуга помечается состоянием памяти ai (символом ai, содержащимся в ячейке ленты, на которую указывает головка) и командой Пj, которую должна выполнить УГ в данном такте j. ( или при именовании тактов ).
Граф переходов GS замечателен тем, что он содержит все возможные «траектории» работы МТ, которые могут быть сколь угодно длинными (но конечными) и (это основное) определяет логику работы МТ, начиная с начального состояния S0, до момента останова. Граф GS в этом случае задаёт так называемую машину состояний.
ЛСА, также определяющая все возможные траектории (последовательности состояний и соответствующих команд) может быть определена и другой графовой конструкцией – блок–схемой алгоритма (БСА).
Рис. 1. Схема МТ Рис. 2. Логическая структура алгоритма
для сложения двух (ЛСА) в виде: а) машины состояния, унарных чисел б) блок-схемы алгоритма (БСА) для
МТ сложения двух унарных чисел
Рис. 3. МТ для задачи распознавания слов языка .
а) ЛСА в виде машины состояний, б) ЛСА в виде блок схемы
алгоритма с диагностикой неправильных слов в виде логических ловушек
Блок–схема алгоритма (БСА) представляет направленный бинарный граф где R – вершины двух типов П – соответствуют действиям, командам или программам и r – соответствуют процедурам, распознающим состояния памяти. Каждая дуга v V помечается либо состоянием памяти (условием перехода), либо символом «» безусловного перехода. В случае МТ, П – команды МТ, rR соответствуют состояниям. Для примера 4 логическая структура алгоритма в виде БСА показана на рис. 2б, где r1 соответствует S=, а r2 соответствует S+. Все возможные последовательности команд (траектории) эквивалентны машине состояний на рис. 2а.
Пример 5. МТ, распознающая слова языка L = anbn.
Содержательно: МТ должна вычислять некоторый предикат РL над любыми словами . .
Если , то МТ заканчивает работу благополучно (попадет в конечное состояние SK), если , то останавливается не имея возможности продолжать работу. Сложность распознающих алгоритмов в виде МТ как раз и заключается в идентификации состояний памяти (ленты), которые диагностируют неблагополучное завершение (). В этом случае МТ называется «машиной с диагностикой», а соответствующие состояния «логическими ловушками».
На рис. 3а показана ЛСА в виде машины состояний, на рис. 3б в виде БСА. ЛСА содержит полное описание МТ с алфавитом ленты , где – называется «собачка» или «бирка», которая заменяет «a» или «b».
а) Состояния б) Команды УГ графа ЛСА.
S0 – начальное состояние П1 = [aa; S0; П]
Sb – распознает «b» П2 = [b; Sb; Л]
Sа – распознает «а» П3 = [; Sb; Л]
S – проверка чистоты ленты П4 = [а; Sа; П]
SК – конечное состояние П5 = [b; S; Л]
в) Логические ловушки П6 = [)); Sb; Л]
(|a| – количество букв «а») П7 = [; Sа; П]
(или «а» не встречаются) П8 = [; S; Л]
– «b» не встречаются П10 = [((; SK, stop]
Распознавание слова (aabb) с благополучным завершением. Последовательность смены ситуаций на ленте и в УГ.
0) – {начальное состояние ленты и положения УГ}
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13) – проверка «чистоты» правого края
14)
– проверка «чистоты» левого края
18)
5. Нормальный алгоритм Маркова (НАМ)
НАМ работает с весьма специфической структурой данных, которая называется «строка Маркова» (СМ). СМ представляет собой слово , но в отличие от ленты МТ строка обладает свойством сжатия при замене символов алфавита на «пустой» символ и расширения при вставлении символов. Это свойство СМ позволяет значительно упростить распознающие алгоритмы, но также значительно усложнить их моделирование на процедурных языках.
Определение НАМ. , А – множество слов в алфавите А, есть строка Маркова в алфавите А, а Р – правила подстановок.
1) , где Т – терминальный алфавит для символов, над которыми работает алгоритм, V – вспомогательный алфавит для промежуточных символов, которые возникают в процессе работы НАМ.
2) Правила Р суть правила замены (подстановки) фрагмента СМ «x» на фрагмент «y». Применение интерпретируется следующим образом:
Пусть , где W, W, W, – строки Маркова, в результате применения правила «x» заменяется на «y» так, что , где и у есть СМ.
а) Если , то (строка Маркова расширяется);
б) Для правила строка Маркова сжимается ровно на х букв.
в) Для правила , где СМ сжимается на .
г) Существует «конечное» правило, отмеченное точкой «» – после его применения НАМ останавливается. Обычно (при правильном завершении НАМ) таким образом фиксируется результат в виде СМ из терминальных букв.
г) Логика исполнения каждого правила может быть описана условным выражением вида: если r = x, то х у, где r – условие применения правила; или в процедурной записи – if r then
П : х у, где П – последовательность действий по выполнению замены «х» на «у», некоторым гипотетическим процессором (программой).
3) Процесс выполнения НАМ (производится на единственном процессоре).
а) В каждом такте выполняется единственное правило.
б) Процесс выполнения описывается логической структурой (БСА) и для всех НАМ стандартен (см. рис. 4а). Последовательность выполнения правил может быть произвольной, но фиксированной во время исполнения НАМ.
в) Останов НАМ. После исполнения «конечного» правила () произошло благоприятное завершение, можно «считать» результат из СМ.
г) Аварийный останов НАМ (АО). В процессе выполнения НАМ не может применить ни одного правила. Для распознающего алгоритма аварийный останов АО сигнализирует о ложности предиката .
Пример 6. НАМ для распознавания слов
Правила Условия – Действия
–
–
–
ЛСА этого НАМ показана на рис. 4б. Ниже приводятся примеры работы НАМ при распознавании конкретных слов языка .
а) б) в) г)
(aabb) (abab) (aabbb) (aaabb)
(aSb) (Sab) (aSbb) (aaSb)
ab (SS) – АО (abb) (aab)
(S) (Sb) – АО (aS) – АО
( )
На примере хорошо видно, как сжимается строка Маркова (сравни с соответствующей МТ). Простота построения распознающих алгоритмов на структурах данных типа СМ сделало НАМ весьма популярным как для теории, так и для практики программирования.
Рис. 4. Логическая структура НАМ.
а) Стандартная логическая структура любого НАМ.
б) Логическая структура НАМ, распознающего слова языка
(без диагностики).
6. Некоторые рекомендации для практического
программирования
Теоретические конструкции МТ и НАМ, разработанные в 3050 г.г. ХХ века, дали толчок для развития практики программирования. Ниже приводятся некоторые принципы описания, организации и проектирования программ, «подсмотренные» в теоретических конструкциях.
МС = , где алфавит состояний; семантика состояния может относиться к некоторой обстановке, ситуации, возникающей в процессе функционирования аппаратуры, программного обеспечения и т.д.;
– условия, семантика условий конструктивна и связана с измерением состояния; обычно это состояние памяти или внешние события.
– действия, семантика действий связана с некоторыми процессорами, которыми могут быть люди (операторы), компьютеры, роботы и т.д.
– суть правила перехода из состояния в , семантика правила описывает отдельный (элементарный) акт действия МС в логическом выражении «если МС находится в состоянии , и в этой ситуации измеряются условия , то необходимо выполнить действия , чтобы перевести МС в состояние .
Граф переходов МС описывает логику работы алгоритма (программы, или аппаратуры, или их совместной работы), которую задумал проектировщик. Практика разработки больших программ показала, что невозможно обойтись без описания логики работы алгоритмов, которые в них заложены. В частности, язык универсального моделирования UML, основан на концепции машины состояний.
Правила Р могут иметь другой вид когда индексы i, j суть такты работы МС В этом случае интерпретация правила: если МС в такте t находится в состоянии S(t) и измеряет условие U(t), то в такте t + 1 переходит в состояние S(t+1) и выполняет действия П(t + 1).
На примере МТ и НАМ стало понятно, что реализация алгоритма в языках программирования должна инструментально поддерживать три основные конструкции:
Все эти конструкции выделены при описании МТ в разделе 5.
Из описания МТ и НАМ выясняется, что для реализации алгоритма необходимы три вещи –
а) конечный набор процедур ;
б) конечный набор условий (по состоянию памяти или строки Маркова)
;
в) правил исполнения – при каких условиях должны выполняться действия .
Это понимание привело к элементарной конструкции исполнителя, который был предложен Дейкстрой и назван «программный монитор» (ПМ). Принцип работы ПМ показан на рис. 5.
Алгоритм вычисляющий одну и ту же функцию может быть проще в зависимости от способа хранения данных, который принято называть структурой данных (СД). Например, структура данных – «лента МТ» просто моделируется на процедурных языках программирования, но алгоритмы (особенно распознающие)
весьма сложны, а структура данных «строка Маркова» наоборот
сложно моделируется, но алгоритмы, работающие с этой структурой достаточно просты.
Изображение ЛСА в виде чертежей графов оказалось очень удобным средством проектирования и анализа алгоритмов, в сравнении со «строчным» описанием, принятым в классической математике и языках программирования. Picture Logic воспринимается в современном программировании как способ «записывания» логики работы алгоритма специальными «рисуночными» формулами. В языке UML разработаны стандарты для Picture Logic.
6) Задачи для самостоятельного решения. Моделирования динамических структур данных типа «лента МТ» и «строка Маркова».
Обратить особое внимание на предварительную разработку ЛСА при проектировании текста программы.
А= – терминальный алфавит. Любое слово языка (LD) содержит одинаковое число открывающих «(» и «закрывающих» «)» скобок во вложенной структуре. Например, – правильное слово, , ; .
PAGE 28