Исполнителем алгоритма является субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий

Алгоритм – понятная и точная последовательность команд исполнителю выполнить преобразование исходных (входных) данных в желаемый результат (выходные данные) за конечное число шагов.

Центральным объектом в этой системе является ИСПОЛНИТЕЛЬ алгоритмов. Исполнитель – это тот объект (или субъект), для управления которым составляется алгоритм. С точки зрения управления, основной характеристикой исполнителя является система его команд (СКИ), т.е. конечное множество команд, которые понимает и может выполнить исполнитель. При построении СКИ решаются две проблемы: проблема элементарности команд и проблема полноты системы команд. Система команд исполнителя называется полной, если она содержит весь минимально-необходимый набор команд, позволяющий построить любой алгоритм в том классе задач, на который ориентирован исполнитель.

Взаимосвязь основных понятий из определения алгоритма:

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

Свойства алгоритмов:

Дискретность – алгоритм определяется последовательностью шагов (этапов или действий), причем выполнение очередного шага возможно только после выполнения предыдущих и основывается на их результатах.

Детерминированность (определенность) или точность – однозначность действий исполнителя на каждом шаге обработки данных.

Элементарность – простота и строгая определенность правила получения данных на каждом шаге из предыдущих результатов.

Результативность (конечность) – конечное число шагов для получения результата.

Массовость – пригодность алгоритма для решения определенного класса задач из некоторого множества.

Работу алгоритма можно представить математической моделью преобразования по правилам Q исходных данных, выраженных посредством алфавита А в окончательные результаты за К шагов (действий):

Рк = fQ (P),

Где Р – слово исходных данных, составленное на основание алфавита А, Q – алгоритм преобразования исходных данных, Рк – к-ый шаг алгоритма.

Данная модель подходит как для класса задач, связанных с вычислениями значений функции, так и для класса задач, связанных с распознаванием принадлежности объекта заданному множеству.

Функция называется вычислимой (разрешимой), если существует алгоритм, определяющий ее значения.

Множество называется разрешимым, если имеется алгоритм, который для любого объекта позволяет определить принадлежность его к данному множеству.

Существует круг задач, решение которых алгоритмически невозможно. Например, «проблема остановки» - когда по исходным данным Р и правилам преобразования Q (описание алгоритма) невозможно установить, завершится ли выполнение алгоритма результативной остановкой. Или проблема распознавания эквивалентности алгоритмов – нельзя создать алгоритм, оценивающий два других алгоритма на предмет получения ими всегда одинаковых результатов.

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

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

Временная сложность алгоритма – это функция, которая для всех конкретных однотипных задач с объемом входных данных n (длина входного слова) ставит в соответствие максимальное время, затрачиваемое алгоритмом на ее решение. Если данная функция имеет полиномиальный характер (f(n) = n или n**2 или n**3), то данный алгоритм полиномиальный. Если же характер функции (f(n) = 2**n или а** n), то такой алгоритм носит название экспоненциального.

Считается, что задача является трудноразрешимой, если для нее невозможно создать полиномиальный алгоритм.

С практической точки зрения к алгоритму предъявляются требования удобства программирования и эффективности решения задачи.

На практике при разработке и описании алгоритма решения задачи определяющими оказываются возможности исполнителя.

Исполнительалгоритма считается заданным, если для него установлены параметры:

v система команд - совокупность элементарных действий алгоритма, которые способен выполнить исполнитель;

v формы представления входной и выходной информации;

v система допустимых внутренних состояний;

v язык представления алгоритма.

Блок обработки данных ветвление (развилка)

(Р – проверяемое

логическое условие)

Начало и конец алгоритма

Ввод – вывод данных

Соединительная линия Объединение

Подпрограмма (использование ранее созданных алгоритмов)

Комментарий,

пояснения,

Циклическая конструкция содержание

подпрограмм.

Если исполнителем является человек, то для правильного и однозначного понимания им содержания и последовательности действий достаточно представить описание алгоритма на естественном языке, в виде формулы, псевдокода (частично формализованный язык, позволяющий записывать алгоритмы в форме, весьма близкой к алголоподобным языкам программирования) или в виде графической блок-схемы

В графической форме записи или блок-схеме для представления отдельных блоков алгоритма используется обусловленный набор геометрических фигур.

Графическая форма предназначена для исполнителя – человека и это ее недостаток. Однако на этапе разработки программ для технического устройства представление алгоритма в виде блок-схем оказывается очень удобным для разработчика.

По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либо формальном языке.

Прежде чем приступить к составлению блок-схемы, необходимо:

Регламентировать состав входа и выхода, т.е. определить имена входных данных, промежуточных и выходных результатов.

Дать наименование основной программе и вспомогательным алгоритмам.

Исполнитель алгоритма – техническое устройство

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

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

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

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

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

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

Для создания формального языка необходимо разработать синтаксис (грамматику) и семантику.

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

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

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

Конечные цепочки символов данного алфавита называются предложениями формального языка, а само множество цепочек – языком, описываемым данной грамматикой.

Дата добавления: 2014-01-06