Алгоритм. Формальное исполнение алгоритмов.

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

Решение задачи предполагает выполнение определенной последовательности действий над объектами (элементами).

Определение. Действие — есть процесс построения на основе конечной системы объектов (исходных величин, данных), заданной в начальный момент времени, конечной системы объектов (результирующих величин, данных) в следующий момент времени. Действие характеризуется: наличием исполнителя (субъекта, устройства и т.д.), определенных объектов, инициирующих его выполнение, и конечным временем выполнения действия.

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

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

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

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

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

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

Примечание.

В настоящее время в мире есть сотни алгоритмических языков программирования.

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

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

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

Все алгоритмы обладают рядом свойств. Приведем основные свойства алгоритмов [21]⁾:

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

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

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

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

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

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

Способы записи алгоритма.

Существуют три основных способа записи или представления алгоритма:Словесное описание, Описание на алгоритмическом языке, Структурная схема (графическая схема) [22]⁾ .

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

Пример: Составить словесное описание алгоритма решения уравнения x+2= 3x–4.

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

Алгоритм 1.
Шаг1. Начало.
Шаг2. Перенести слагаемое 3x в левую часть уравнения. Х–3Х+2=–4
Шаг3. Перенести слагаемое 2 в правую часть Х–3Х = -2–4
Шаг4. Привести подобные слагаемые в левой части -2Х = -2–4
Шаг5. Привести подобные слагаемые в правой части -2Х = -6
Шаг6. Разделить обе части уравнения на -2. Х = 3
Шаг7. Записать результат. Ответ: х = 3
Шаг8. Конец.

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

Алгоритма 1а.
Шаг1. Начало.
Шаг2. Перенести все слагаемые в левую часть уравнения с обратным знаком и привести подобные члены 2Х+6 = 0
Шаг3. Решить линейное уравнение. Х = 3
Шаг4. Записать результат. Ответ: х = 3
Шаг5. Конец.

§ Описание алгоритма на алгоритмическом языке.

Определение.Алгоритмический язык — это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения.

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

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

Приведем пример построения алгоритма на школьном алгоритмическом языке КуМир.

Пример: Правописание приставок на «з» и «с»

Алгоритм 2.

алг

нач

если корень слова начинается со звонкой согласной

I то на конце приставки написать «з»

I иначе на конце приставки написать «с»

все

кон

§ Структурное схема алгоритма (графическая схема алгоритма).

Алгоритм наиболее удобно изображать графически с помощью блок-схем или граф-схем.

Определение.Блок-схемы — это набор элементов, называемых блоками, соединенных между собой линиями или стрелками. Линии называются линиями потока. Они отражают последовательность выполнения действий, определяемых каждым блоком.

Примечание.

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

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

1. Блок начала программы, «Пуск» («Начало»), представляет собой овал с выходящей из него линией потока. В овале может быть приведена вспомогательная или поясняющая информация, например. Блок оконча-ния програм-мы, «Останов» (рис.6.1).

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

3. Блоки ввода и вывода информации, «Ввод-вывод», изображаются параллелограммом с входящей и исходящей стрелками. Это относится к любым носителям информации (рис. 6.3). В блоке указываются вводимые или выводимые данные.

4. Логический блок, «Решение», изображаемый в виде ромба с одной входящей и двумя или несколькими выходящими стрелками (рис.6.4). Внутри ромба помещается текст логического вопроса, допускающего или двоичный ответ (да/нет), или несколько вариантов выбора. В любом случае над линиями потока пишутся условия прохождения по этой ветви.

Рис.6.4 Пример блоков Решение.

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

Рис.6.5. Пример блоков Модификация

6. Если модуль или подпрограмма составлены и описаны отдельно, то используется блок «Предопределенный процесс» (рис.6.6). В нем указывается название подпрограммы или программного модуля.

Рис.6.6. Пример блоков Предопределенный процесс.

7. Для пояснения отдельных блоков, их групп и линий потока используются «комментарии» (рис.6.7). Они записываются справа от блоков и соединяются с ними пунктирной линией. В комментариях может находиться любая поясняющая информация.

Рис.6.7. Пример комментария.

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

Рис.6.8. Пример соединителей.

Использование этих блоков позволяет наглядно представить алгоритм вычислений. Всего же ГОСТ 19002-80 и ГОСТ 19003-80 устанавливает для изображения схем алгоритмов и программ 42 символа. Из них 30 – обязательных, а 12 – рекомендуемых.

Пример: Приведем в качестве примера запись алгоритма решения линейного уравнения x+2= = 3x–4в виде блок-схемы (Алгоритм 3 на рис.6.9).