Алгоритмы. История. Типы алгоритмов. Машина icon

Алгоритмы. История. Типы алгоритмов. Машина


1 чел. помогло.
Смотрите также:
Введение Предмет "Программирование"...
«Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов...
Основные типы алгоритмов, Вспомогательные алгоритмы...
Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов...
От счёта на пальцах до пк...
Лабораторная работа №1 «Алгоритмы»...
Алгоритмы и исполнители....
Задача на использование логических операций и построение логических схем...
Генетические алгоритмы. Мутация (обобщенный доклад)...
Методические указания к выполнению контрольных работ по дисциплине "Основы программирования"...
Курс лекций по дисциплине “Компьютерные науки”, кафедра Нелинейного анализа и оптимизации...
Алгоритмы и машины Тьюринга Основы алгоритмов...



Загрузка...
скачать
Лекция 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) если А разрешимо в М, то из этого не следует его

вычислимость.

Проблемы разрешимости и вычислимости множеств требуют точного определения понятия алгоритма. Точного понятия алгоритма нет и никогда не будет сделано по причине очень «туманного» содержательного объекта, который необходимо формально определить. В этом случае математики предложили некоторый точно определенный инструмент, при помощи которого можно конструировать любые интуитивно понятные порождающие (вычисляющие) и распознающие (разрешающие) процедуры.

Алгоритм, как точно определённый инструмент, для конструирования процедур должен обладать следующими свойствами.

  1. Конструктивность. Любые А и М (интуитивно понятные и содержательные множества) должны быть конструктивно описаны в виде структур данных. Любые интуитивно понятные функции (предикаты) должны быть конструктивно (формально) описаны в терминах определения инструмента.

  2. Детерминированность. Вообще говоря следует из 1), т.к. интуитивно алгоритм предполагает реализацию функций и только их.

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

^ 2. Типы алгоритмов. История создания.

За 30–40 годы ХХ столетия интенсивного поиска универсального уточнения алгоритма было предложено примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа.

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

Основные АМ, которые повлияли на создание реальных вычислительных машин, реальных языков программирования и концепции организации вычислительных процессов были предложены в ХХ в.

  • Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г.

  • Машина Поста (МР) предложена Постом в 1937 г.

  • Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.

  1. Функции вычислимые алгоритмом. В этом случае сам алгоритм не определяется формально, а существует как бы в виде «всем понятной механической процедуры».

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

Любая функция, вычислимая на интуитивном (содержательном) уровне, должна быть сконструирована из базовых .

  • ^ Рекурсивные функции на множестве натуральных чисел были предложены Клини в 1938 г.

Конструктивные механизмы рекурсивных функций очень просты, их применение в процессе построения «функции от функции» позволяет явно выстраивать структуру функции в отличие от АМ, где функция определяется процедурно, через последовательность действий.

  1. Исчисления. Представляют собой формальные системы, в которых определены понятия правильно построенных формул (ППФ) и конечного набора правил преобразования ППФ. Алгоритм понимается как цепочка применения последовательности правил к начальной ППФ для получения вывода конечной ППФ. В аксиоматических формальных системах конечные ППФ всегда выводятся из ППФ, которые называются аксиомами.

  • ^ Исчисление функций, вычисляемых на множестве натуральных чисел предложено Эрбраном и Гёделем в 1938 г.

  • -исчисление А.Чёрча также может быть отнесено к этому типу алгоритмов, предложено в 1937 г.

  • ^ Формальные грамматики, порождающие языки, предложены Хомским в 1953 – 1956 г.

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


^ 3. Структура алгоритма (составляющие алгоритма)

  1. Процессорная структура. (Исполнитель алгоритма). Во всех теоретических конструкциях алгоритмов и большинстве алгоритмических языках это единственный процессор.

  2. ^ Структуры данных. Структура данных это способ организация записи, хранения и извлечение данных. Данные – это элементы множеств, которые нужно порождать или распознавать. Содержательные данные могут быть определены весьма экзотическим образом и требуют иногда большого искусства в отображении их на организацию данных, которые разрешены в тех или иных конструкциях алгоритмов и языков программирования.

  3. ^ Информационная структура алгоритма (ИСА). Структура функций есть описание конструирования функции от функций из базовых. Заметим, что функция может быть определена двумя способами:

а) структурой (структурным описанием) б) процедурно (последовательностью базовых операций).

Языки программирования содержат оба способа задания функций.

  1. ^ Логическая структура алгоритма (ЛСА) или программы (ЛСП). ЛСА суть описание организации вычислительного процесса, который управляется состоянием памяти.

В дальнейшем будут рассмотрены примеры всех трех типов алгоритмов: а) АМ – Машина Тьюринга и Нормальный алгоритм Маркова, б) функции вычислимых алгоритмом, использующие конструкции рекурсивных функций Клини, в) формальные порождающие грамматики Хомского и распознающие автоматы (конечные и магазинные автоматы).

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

1) (запись обозначает: МТ определяется формально четверкой конечных множеств), где

  • – алфавит рабочих символов

  • – алфавит состояний

  • – алфавит действий

  • – набор правил вида – , где (иногда называют программой МТ).

2) Интерпретация МТ.

а) Процессор – в МТ называется управляющей головкой (УГ).

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

в) ^ Процесс вычислений (см.рис.1) происходит по тактамв каждом ti УГ выбирает и выполняет правила в зависимости от собственного состояния и информации, записанной на ленте. Если УГ находится в состоянии и указатель головки стоит напротив ячейки, где записан символ аi (видит аi), то головка заменяет его на символ аj, переходит в состояние Sj, производит действие dj (Л – сдвигается на ячейку влево, П – сдвигается на ячейку вправо, Н – остается на месте, stop – МТ останавливается).

В начальном такте (t0) УГ находится всегда в состоянии S0, «смотрит» на некоторую ячейку ленты и «ждет» внешнего сигнала «пуск», чтобы начать работу.

г) ^ Процесс остановки (остановка) МТ.

МТ – останавливается в двух случаях:

  • удачное завершение (фиксация результата), выполняется команда (ak, Sk, stop) переводит УГ в конечное состояние и происходит остановка машины;

  • неудачное завершение, УГ не может найти правило с условием (ai, Si), ошибка в программе (наборе правил), ошибка в данных. В распознающих МТ неудачные завершение фиксирует «ложность» соответствующего предиката.

д) ^ Процесс «вечной» работы МТ означает для порождающей МТ благополучную ситуацию, когда порождаемое слово может быть бесконечной цепочкой символов. Для распознающей МТ ситуация не предсказуема (либо МТ ещё не нашла значение предиката, либо имеется ошибка в программе).

е) ^ Список правил для МТ не упорядочен. Поиск правила происходит по условиям (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. Некоторые рекомендации для практического

программирования

Теоретические конструкции МТ и НАМ, разработанные в 3050 г.г. ХХ века, дали толчок для развития практики программирования. Ниже приводятся некоторые принципы описания, организации и проектирования программ, «подсмотренные» в теоретических конструкциях.

  1. ^ Проектирование программ. Машины состояний. Графы переходов для описания логики работы МТ и НАМ привели к абстрактному понятию «машина состояний» (МС).

МС = , где алфавит состояний; семантика состояния может относиться к некоторой обстановке, ситуации, возникающей в процессе функционирования аппаратуры, программного обеспечения и т.д.;

– условия, семантика условий конструктивна и связана с измерением состояния; обычно это состояние памяти или внешние события.

– действия, семантика действий связана с некоторыми процессорами, которыми могут быть люди (операторы), компьютеры, роботы и т.д.

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

Граф переходов МС описывает логику работы алгоритма (программы, или аппаратуры, или их совместной работы), которую задумал проектировщик. Практика разработки больших программ показала, что невозможно обойтись без описания логики работы алгоритмов, которые в них заложены. В частности, язык универсального моделирования UML, основан на концепции машины состояний.

Правила ^ Р могут иметь другой вид когда индексы i, j суть такты работы МС В этом случае интерпретация правила: если МС в такте t находится в состоянии S(t) и измеряет условие U(t), то в такте t + 1 переходит в состояние S(t+1) и выполняет действия П(t + 1).

  1. Организация программ в языках программирования.

На примере МТ и НАМ стало понятно, что реализация алгоритма в языках программирования должна инструментально поддерживать три основные конструкции:

  • структуру данных (способ запоминания данных);

  • структуру функций (список процедур, реализующих функцию вычислимую алгоритмом);

  • логическую структуру алгоритма (описание возможных траекторий исполнения программы).

Все эти конструкции выделены при описании МТ в разделе 5.

  1. Организация вычислений. Программный монитор Дейкстры.

Из описания МТ и НАМ выясняется, что для реализации алгоритма необходимы три вещи –

а) конечный набор процедур ;

б) конечный набор условий (по состоянию памяти или строки Маркова)

;

в) правил исполнения – при каких условиях должны выполняться действия .

Это понимание привело к элементарной конструкции исполнителя, который был предложен Дейкстрой и назван «программный монитор» (ПМ). Принцип работы ПМ показан на рис. 5.

  1. ^ Структуры данных (СД).

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

весьма сложны, а структура данных «строка Маркова» наоборот




^

Рис. 5. Принцип работы программного монитора



Рис. 6. Меандр Фиббоначи




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

  1. ^ Picture Logic (картиночная логика)

Изображение ЛСА в виде чертежей графов оказалось очень удобным средством проектирования и анализа алгоритмов, в сравнении со «строчным» описанием, принятым в классической математике и языках программирования. Picture Logic воспринимается в современном программировании как способ «записывания» логики работы алгоритма специальными «рисуночными» формулами. В языке UML разработаны стандарты для Picture Logic.

^ 6) Задачи для самостоятельного решения. Моделирования динамических структур данных типа «лента МТ» и «строка Маркова».

Обратить особое внимание на предварительную разработку ЛСА при проектировании текста программы.

      1. Построить программную реализацию МТ, порождающую слова языка Дика (LD)

А= – терминальный алфавит. Любое слово языка (LD) содержит одинаковое число открывающих «(» и «закрывающих» «)» скобок во вложенной структуре. Например, – правильное слово, , ; .

  1. Построить программную реализацию МТ, распознающую слова LD с диагностикой типов неправильных слов

  2. Построить программную реализацию машины состояний, порождающей LD.

  3. Построить программную реализацию НАМ, распознающего LD. Спроектировать и смоделировать структуру данных «строка Маркова».

  4. Задана МТ, работающая с 2 – мерной плоскостью, разбитой на клетки и управляющей головкой (УГ), которая может производить четыре вида движения (право, лево, верх, низ). Такая МТ называется клеточным автоматом (КЛА). Построить программную реализацию КЛА, порождающего и распознающего на клеточном поле фигуру «Меандр Фибоначчи». Пример фигуры показан на рис.6. Параметры размеров клеточного поля не должны изменяться путём редактирования текста программы.







Скачать 214.59 Kb.
оставить комментарий
Дата30.09.2011
Размер214.59 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  2
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх