Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения



Скачать 120.56 Kb.
Дата30.12.2012
Размер120.56 Kb.
ТипЛекция
Лекция 2

Машина состояний. Блок-схема алгоритма (БСА). Матричная структура алгоритма (МСА). Строка Тьюринга. Строка Маркова. Строка Ляпунова. Логическая структура алгоритма (ЛСА). Структурное программирование.
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения.

Точного определения алгоритма нет. В 19301950 г. в работах Тьюринга, Поста, Клини, Гёделя сложились три типа уточнения понятия алгоритма: 1) алгоритм-машина (машинный алгоритм); 2) алгоритм-функция (система функций вычислимых алгоритмом, информационная структура алгоритма); 3) алгоритм-исчисление. В настоящее время все три типа алгоритмов используются для решения различных задач и поддерживаются специальными программными средствами в языках программирования.

Принципы, положенные в основу функционирования машинных алгоритмов.

  1. Однопроцессорность и поэтому последовательная работа процессора только над одним потоком команд.

  2. Управление процессора происходит под действием внешних либо внутренних событий.

  3. Алгоритм понимается как последовательность переходов из состояния в состояние под действием команд или последовательностей команд.

  4. Управляющие внутренние события воспринимаются как изменения в памяти процессора.

1. Машина состояний (State Machine) – SM.

SM =  S, E, П, P 

а) S = s0, s1, …, sk – алфавит состояний, s0 – начальное состояние, sk – конечное состояние.

б) E = e1, e2, …, en – алфавит событий (events), событие идентифицируется (происходит, совершается) при изменении состояния машины под воздействием команд.

в) П = П1, П2, …, Пе – набор элементарных действий, изменяющих состояние машины.

г) P=р1, р2, …, рm – набор правил (команд машины); где вид правила (команда SM) – р = {S(t), e(t), П(t)  S(t + 1)}.

Интерпретация правил SM: если SM находится в момент времени t в состоянии S(t), идентифицируется событие e(t), тогда инициируется действие П(t), которое переводит SM в новое состояние S(t+1); момент времени «t» называется тактом работы SM.
В большинстве SM употребляется другой вид правил: р = S(t), e(t),  S(t + 1), П(t + 1) – с интерпретацией: событие e(t) вызывает переход в S(t + 1) и действие П(t + 1) в этот же момент.

Последовательность действий SM, приводящих SM из состояния S0 в конечное состояние Sk, называется алгоритмом (программой) работы SM.

Исходная информация (данные), промежуточная и результирующая (когда SM попадает в конечное состояние Sk и останавливается) записывается в память SM.

Для абстрактных SM (например, машины Тьюринга) память имеет вид ленты или строки (например, нормального алгоритма Маркова) с определенными свойствами.

2. Машина Тьюринга (МТ).

МТ = S, E, П, P определяется как некоторая SM.

а) S – алфавит состояний.

б) E  А={a1, a2, …, an} – алфавит внешних символов, которые записываются в память (на ленту). Идентификацию символа в момент t в МТ производит специализированный процессор, который называется «управляющей головкой» (УГ). Внешние символы являются событиями, которые управляют процессором УГ.

в) П = {L, R, stop} – алфавит действий УГ.

г) Для МТ определяется набор команд вида

, либо .

Лента МТ представляет своеобразную структуру данных (СД), которая может моделироваться двунаправленным линейным списком, вообще говоря, растущим в обе стороны.



Обозначения в линейном списке:

L – ссылка на предыдущий элемент списка;

R – ссылка на последующий элемент списка;

Z – запись (для МТ это ячейка ленты, куда записывается

единственный символ);

 – спейсер, ограничивающий запись слова.

Строка с такой СД носит название «строка Тьюринга» – (СТ).

Пример SM в виде машины Тьюринга, порождающей слова языка L = anbn; A = {a, b, , } – алфавит символов ленты МТ. Структура данных – СТ;  – пустой символ; начальное состояние СТ – все ячейки пустые;  – спейсер может быть в любой ячейке. SM определяется следующими конструкциями.

а) S = {SL, SR, Sstop} – алфавит состояний; SL – начальное состояние; состояние движения УГ влево, Sstop – конечное состояние, SR – состояние движения УГ вправо.

б) Правила: Р1 = {(SL, , а, R)  SR}, правило читается так, если SM в состоянии SL, считывает из элемента списка символ «», то записывает символ «а», по правой ссылке R вызывается следующий элемент списка и SМ переходит в SR.

Р2 = {(SR, , b, L)  SL}; P3 = {(SR, a, a, R)  SR}

P4 = {(SR, b, b, R)  SR}; P5 = {(SL, *, *, stop)  SR}

P6 = {(SL, b, b, L)  SL}; P7 = (SL, a, a, L) SL}.

Правила работы SM могут быть записаны в виде матриц S  S (матрица состояние/состояние) S  A (матрица состояние/собы-тие). Такая запись называется матричной структурой алгоритма (МСА). Для рассматриваемого примера:
в) Матрица переходов S S (состояние/состояние).




SL

SR

Sstop

SL

a,(a,L)

b,(b,L)

(a,R)



*,(*,stop)

SR

(b,L)



a,(a,R)

b,(b,R)




г) Матрица – S  A (состояние/событие).




a

b





SL

(a,L)SL

(b,L)SL

(a,R)SR

*,(*,stop)Sstop

SR

(a,R)SR

(b,R)SR

(b,L)SL




Каждое действие в правилах можно назвать элементарной программой. Набор элементарных программ П = {П1 = (a,R); П2 = (b,R); П3 = (b,L); П4 = (a,L); Пk = (*, stop)} из которых строятся сценарии работы (поведения) МТ в зависимости от начальной информации на входной ленте.

Программа работы SM может быть задана графом. Для примера на рис.1 приведен граф переходов. Вершины – состояния. Дуги помечены выражением: «если в элементе списка находится символ «х», то замени его на символ «у» и перейди к следующему элементу по ссылке L или R, в соответствии с правилом».



Рис.1 Граф переходов SM, порождающей .

Пример работы SМ со строкой Тьюринга при порождении слова а2b2L.

0)  1) а 2) аb
3) ab 4) aab 5) aab
6) aab 7) aabb 8) aabb
9) aabb 10)aabb 11) Stop SM
3. Блок-схема алгоритма (БСА – машина). БСА является еще одной конструкцией алгоритмической машины, к БСА достаточно просто перейти от SM, если задан ее граф переходов.

БСА суть направленный граф с множествами вершин двух типов.

1) П – программные вершины,2) R – вершины-распознаватели. Дуги RП, RR помечаются «+» или «–», дуги ПП, ПR не помечаются. Интерпретация графа: П – программный блок, R – содержит проверку истинности или ложности условия. Проверку выполняет программа, вычисляющая соответствующий предикат.

Интерпретация работы БСА – машины.

  1. Машина начинает работу с П0 (начальный программный блок) и заканчивает (останавливается) после работы над блоком Пk.

  2. Переход после окончания работы над блоком Пi к блоку ПJ безусловно (по стрелке) либо через распознаватель R по стрелке «+», если условие (предикат) распознавателя выполнено, или по стрелке «–», если условие (предикат) не выполнено. Выполнение/невыполнение условия суть события, на которые БСА реагирует включением того или иного блока.



4 Блок-схема алгоритма машины, порождающей слова языка

БСА построена по SM, приведенной в пункте 2, 1, 2, 3, a1, a2, b1, b2 – обозначение распознавателей пустого символа и символов a, b.

 – останов БСА-машины при неправильной ситуации на ленте.

5
Строка Ляпунова (СЛ)
представляет граф в виде слова, построенный по определенным правилами, который служит логическим «скелетом» программы. СЛ является логической моделью записи программы на любом процедурном языке для однопроцессорной алгоритмической машины.

На рисунке представлена строка Ляпунова для алгоритма порождения со структурой данных СТ.

Строка Ляпунова суть последовательность символов П, условий распознавателя, стрелок и специального символа . Она строится по следующим правилам:

    1. «+» стрелка не показывается, за ней всегда идет программный блок или символ  (безусловный переход);

    2. «–» стрелка показывает переход на соответствующий программный блок;

    3. после символа  стрелка показывает безусловный переход на соответствующий программный блок.

6. Эквивалентные преобразования СЛ. Символы СЛ могут быть переставлены в любой последовательности, при этом сохраняется логическая структура графа БСА.

Д
алее приведена «запутанная» строка Ляпунова (местами поменялись П2 и П3).

7. Строка Маркова (СМ). Сложность алгоритма зависит от структур данных. Строка Маркова (СМ) получила свое название по имени Маркова, автора нормального алгоритма Маркова, где она была впервые использована. СМ обладает рядом свойств, которые позволяют строить очень простые порождающие и распознающие алгоритмы. Но реализация структуры данных типа СМ даже в языках программирования высокого уровня достаточно сложна. Реализация СМ должна удовлетворять некоторым условиям.

Свойства СМ, которые делают ее «резиновой» (растягивающейся/сжимающейся) при перестановках (заменах) фрагментов слов:

а) Растяжение СМ.

Правило подстановки  такое, что  (длина слова  меньше длины слова ). При выполнении подстановки строка растягивается.

Например, x = aaSbbслово, (SaSb) – правило.

Применение правила дает слово x = aaaSbbb.

б) Сжатие СМ.

Правило подстановки  такое, что  > .

Например, x = aaSbb – слово, (aSbS) – правило; применение правила дает слово x = aSb.

Пример SM, порождающей слова языка L=anbn, использующей структуру данных «строка Маркова» (СМ). Обратите внимание, как упрощается алгоритм по сравнению с аналогичным, но работающим со «строкой Тьюринга» (п. 2).



Рис.2. Граф SM и ЛСА для задачи порождения слов языка L=anbn на строке Маркова.
а) Машина состояний (SM).

Алфавит языка: – вспомогательный символ.

Алфавит состояний .

Алфавит внешних событий: – продолжать порождение, – закончить порождение.

Правила: ; .

б) Логическая структура алгоритма ЛСА.

П0 – начальный блок, на ленту СМ занесен символ «».

П1 – подстановка (  аb), Пk – подстановка (  аb).

Значение распознавателя ek = «+» – закончить порождение,

ek = «–» – продолжать порождение.

Граф алгоритма на СМ очевидно проще, чем граф алгоритма на СГ (см. рис. 1).

8 Логическая структура алгоритма. (ЛСА)

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

ЛСА может быть задана графом либо матрицей переходов соответствующей SM. Существует несколько видов SM: SM общего вида; последовательностная SM; SM в виде БСА.

а) SM общего вида или просто SM=, где U – вычисляемые условия, выполнение условия (наступления события) определяются истинностью/ложью соответствующим предиката, П – множество элементарных программных блоков, S – состояния, абстрактные объекты (объекты не подлежащие программированию), которые служат для организации различных последовательностей вычисления по правилам Р вида , где На рис. 3 а, б показана ЛСА для задачи порождения L = anbn.

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

с правилами вида

Существует двустороннее эквивалентное преобразование , эквивалентное в смысле алгоритма решения одной и той же задачи. На рис.3 в показана ЛСА в виде ПSM решающая задачу порождения L = anbn.

Можно видеть, что ПSM имеет пять состояний (соответствующая SM имеет три состояния). Эквивалентность обеспечивается эквивалентностью программных блоков.

ЛСА в виде ПSM обладает заметным удобством, которое превращает ПSM в программную строку. Для этой цели рассматриваются строки общего вида , они содержат более чем два перехода, которые совершаются по ключам (см. рис.3 г, д). Также как для строки Ляпунова, существуют эквивалентные SW, которые получаются перестановкой операторов и введением соответствующих безусловных переходов ().



Рис. 3. Порождение слов :

а) SM общего вида;

б) матрица переходов SM общего вида;
в
Программные бло- Эквивалентные

ки последователь- соотношения

ностной SM SM и ПSM

ПRaзапись «а»; П1ПRa ПRR

ПRbзапись «b»; П2ПRb ПRR

ПLaзапись «а»; П3ПLb ПRL

ПLbзапись «b»; П4ПLa ПLL

ПRR – сдвиг указателя

вправо

ПLLсдвиг указателя

влево
)



е0 – событие, соответствующее

тождественно истинному условию.

г)



д)



Рис. 3. Порождение слов :

в) последовательная SM (ПSM)

г) SW-строка (с переходами по ключам К1 и К2) программы;

д) SW-строка с перестановкой программных блоков ПRR и ПLL.

9 Структурное (структурированное) программирование.

В начале 70–х годов Дейкстра предложил принцип последовательного уточнения логической структуры алгоритмов. Внутреннее содержание каждого программного блока в БСА уточняется одним из четырёх способов, показанных на рисунке.


begin begin begin begin

begin begin begin begin

A1 if R then A1 while R do A1 repeat A1

end else A2; end until R

begin end end end

A2 end end end

еnd

end

Рис.4 Структуризация по Дейкстре.


Свойства структуризации по Дейкстре.

  1. «один вход –один выход». Каждый программный блок имеет единственную точку входа (а) по управлению и единственную точку выхода (b). Например, выходы b1 и b2 (при структуризации типа «альтернатива») объединяются в один выход из блока А. В цикле с постусловием входная точка a1 объединяет два входа;

  2. запрет «GO TO» Запрещается употребление оператора «go to» при уточнении логики работы программных блоков.

Структурное программирование иногда называют программированием без «GO TO». На самом деле, оператор безусловного перехода необходим только для отображения графа ЛСА в строку Ляпунова для указания следующего программного блока. Структурированная по Дейкстре программа обладает свойством локализации логических переходов только в теле соответствующего программного блока, что даёт возможность эффективного поиска ошибок при построении автоматических отладчиков.




Похожие:

Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconРабочая программа По дисциплине «Разработка программного обеспечения» По специальности
Основная задача курса – сформировать фундаментальные знания у студентов о принципах построения, реализации и функционирования программного...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconВопрос: Организация приобрела неисключительное право на использование программного обеспечения на неопределенный срок. Может ли организация единовременно учесть расходы на приобретение указанного права в целях исчисления налога на прибыль?
«Об учете расходов на приобретение неисключительного права на использование программного обеспечения»
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconВнедрение пакета свободного программного обеспечения
Учитывая важность и неизбежность процесса информатизации системы образования Курской области, рассмотрим один из важнейших вопросов...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconАвтоматизация проектирования и технология использования сапр программного обеспечения Автоматизация проектирования
Проектирование — это один из наиболее сложных видов интеллектуальной работы, выполняемой человеком
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconИнтегрированная среда разработки программного обеспечения Visual Basic, Borland Delphi
Интегрированная) среда разработки программного обеспечения (англ. Ide, Integrated development environment) — система программных...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconКурсовой проект (курсовую работу) по дисциплине Операционные среды
Наименование темы Технологии проектирования программного обеспечения для ос windows
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconТехнология программирования
Вопрос №1 Методы проектирования программного обеспечения (программных продуктов) 1
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconПрограммное обеспечение и лицензия на него
Для определения юридических рисков использования нелицензионного программного обеспечения необходимо прежде всего дать определение...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconТрадиционные процессы разработки по. Стадии разработки по. Водопадный и спиральный процессы, rup. Стадии разработки программного обеспечения
В компьютерной терминологии, показатель Стадии разработки программного обеспечения используется программистами для описания степени...
Лекция содержит фундаментальные понятия машинных алгоритмов и их использование для проектирования программного обеспечения iconИстория развития программного обеспечения
Сотворение компьютерного мира. Вы будете одними из творцов виртуального мира. Вы наверняка знаете много имен тех людей которые приложили...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org