Алгоритмизация. Понятие алгоритма и алгоритмической системы. Свойства алгоритма. Проектирование алгоритмов. Блок-схема алгоритма. Основн

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

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

7.1.5.2 Псевдокод

 

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

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

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

7.1.5.3 Блок-схема

 

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

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

Правила выполнения схем определяются следующими документами:

ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения.

ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические.

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

Основные элементы схем алгоритма:

 

Наименование	Обозначение	Функция
Блок начало-конец  (пуск-остановка)		Элемент отображает вход из внешней среды или выход  из нее (наиболее частое применение −  начало и конец программы). Внутри фигуры записывается соответствующее  действие.
Блок вычислений (вычислительный блок)		Выполнение одной или  нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно  сами операции, например, операцию присваивания: a = 10*b + c.
Логический блок (блок условия)		Отображает решение  или функцию переключательного  типа с одним входом и двумя  или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути.
Предопределенный процесс		Символ отображает выполнение процесса, состоящего из одной или  нескольких операций, который определен  в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в  него данные. Например, в программировании − вызов процедуры или функции.
Данные  (ввод-вывод)		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов  обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Граница цикла		Символ состоит из двух частей − соответственно, начало и конец цикла − операции, выполняемые  внутри цикла, размещаются между  ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости от типа организации цикла. Часто для изображения на блок-схеме цикла вместо данного символа используют символ решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла).
Соединитель		Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения ее в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при этом уникальное) обозначение.
Комментарий		Используется для более  подробного описания шага, процесса или  группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.

7.1.5.4 Программа

 

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

Программа – описание структуры алгоритма на языке алгоритмического программирования.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.6 Основные типы алгоритмов

 

 

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

7.1.6.1 Линейная алгоритмическая конструкция

 

Линейной называют алгоритмическую  конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма  выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие — не конец алгоритма.                                

7.1.6.2 Разветвляющаяся алгоритмическая конструкция

 

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

При полной форме ветвления  действия выполняются в обоих случаях: и при истинности и при ложности условия. Ей соответствует следующее выражение: если <условие>, то <действие 1>, иначе <действие 2>. При неполной форме ветвления действие выполняется в единственном случае, то есть, когда выполняется условие. Ей соответствует выражение: если <условие>, то <действие 1>.

7.1.6.3 Алгоритмическая конструкция «Цикл»

 

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

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

7.1.6.3.1 Арифметический цикл

 

В арифметическом цикле  число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (K) значений параметра и шагом (h) его изменения. То есть, на первом шаге цикла значение параметра равно N, на втором – N+h, на третьем – N+2h и так далее. На последнем шаге цикла значение параметра не больше K, но такое, что дальнейшее его изменение приведёт к значению, большему, чем K.

7.1.6.3.2 Цикл с предусловием

 

В данной циклической  структуре сначала проверяется  значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается. Количество шагов цикла заранее не определено и зависит от входных данных задачи.  

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

7.1.6.3.3 Цикл с постусловием

 

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

7.1.6.4 Рекурсивный алгоритм

 

Рекурсивным называется алгоритм, организованный таким образом, что в процессе выполнения команд на каком-либо шаге он прямо или косвенно обращается сам к себе.

7.1.6.5 Вспомогательный алгоритм

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.7 Проектирование алгоритмов

 

 

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

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

7.1.7.1 Нисходящее проектирование

 

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

На практике «чистую» нисходящую разработку осуществить практически невозможно, так как выбор более конкретизированных элементов на каждой стадии должен производиться на основе представления и понимания возможностей языка реализации. Однако даже в данном случае на более поздней стадии часто обнаруживается, что некоторый выбор, сделанный ранее, был неверным. Это приводит к необходимости разработки новых и корректировки уже имеющихся модулей.