Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использованияа.pdf

Символ «Пуск – останов» используется для обозначения начала, конца, прерывания процесса обработки данных или выполнения программы.

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

1.4.2.1 Графические способы описания алгоритмов работы информационных систем (промышленных систем)

К графическим способам описания алгоритмов работы информационных систем (промышленных систем) относятся также:

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

-Структурные схемы (рис. 2.a) и сигнальные графы (рис. 2.б). Применяются для изображения структуры и описания функционирования преимущественно непрерывных систем. Переход от одной формы описания к другой очень прост. Передаточные функции (передачи) F отдельных функциональных блоков записываются в структурной схеме внутри соответствующих прямоугольников, а в направленном графе – на его ветвях (ребрах). Переменным (сигналам) x в структурной схеме соответствуют линии, соединяющие блоки, а в графе – его узлы (вершины). Автоматные графы (рис. 3). Применяются для описания дискретных состояний системы и возможных переходов между ними. Узлы изображают различные возможные состояния q, а ветви со стрелками – переходы. Рядом с каждой ветвью записывается условие B, которое вызывает переход между соответствующими состояниями. Сети Петри (рис. 4). Сети Петри являются направленными графами с двумя видами узлов, а именно с узлами для изображения состояний q (кружки) и узлами для изображения переходов (вертикальные штрихи) между состояниями. Переход осуществляется, если состояния, находящиеся перед символом перехода, помечены и наступает событие, вызывающее переход. Например, имеет место переход от q к q, q и q, если имеется q и выполнено условие В1.

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

-Графы последовательного выполнения программы. Пригодны для записи задач управления и для описания поведения релейных систем управления. Изображают зависящую от каких-либо условий последовательность состояний системы q. Положение (0 или 1) конкретных функциональных элементов (Q1, Q2, Y1, Y2, Y3), соответствующие некоторым характерным состояниям системы, указываются в отдельной таблице. В приведенном примере (рис. 5): как только S1 = 1, система совершает переход из состояния q в q; если S2 = 1, то осуществляет переход в состояние q, для S2 = 0 – в состояние q и т.д.

- Схемы работы (рис.  6).  Очень удобно использовать для описания линейно протекающих процессов и работы соответствующих систем управления. Изображается зависящая от появления определенных событий последовательность отдельных шагов или состояний процесса (q, q, q, …). Пример: сигнал ″Пуск″ и сигнал ″закрыть заслонку″ начинают первый шаг процесса (например, наполнение мешалки). Как только поступают информационные сигналы 1, 2, 3 (двигатель А включен, вентиль 1 открыть, время ожидания истекло), следует шаг процесса 2 и т.д.

1.4.3. Псевдокоды

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

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

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

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

Как и любой язык, АЯ строится на основе алфавита, включающего в себя набор символов, разрешенных к использованию при написании алгоритмов.

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

Для дополнения символов алфавита в АЯ вводятся так называемые ключевые (служебные) слова, которые позволяют сделать запись алгоритма более понятной и выразительной. Они используются для формирования типовых синтаксических конструкций. Наборы ключевых слов алгоритмического языка типа АЯ приведен в табл. 2.

Синтаксические конструкции языка подразделяются на два типа (см. рис. 7): описания данных (величин) и операторов (команд).

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

1.4.4. Программный способ представления

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

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

Математическое обеспечение – средства, которые могут быть предоставлены пользователю для решения его задачи с помощью ПК. Оно включает в себя алгоритмическое обеспечение – методы и алгоритмы, модели решения задач, лингвистическое обеспечение – языки программирования, программное обеспечение – систему автоматизации программирования и информационное обеспечение – структуры данных и базы данных.

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

По этому критерию можно выделить следующие уровни языков программирования: машинные; машинно-ориентированные (языки ассемблера);
машинно-независимые (языки высокого уровня).

Машинные и машинно-ориентированные языки – это языки низкого уровня, требующие указания мелких деталей процесса обработки данных.

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

Языки высокого уровня делятся на:

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

- логические (Prolog, Lisp и др.), которые ориентированы не на разработку алгоритма решения задачи, а на систематическое и формализованное
описание задачи с тем, чтобы решение следовало из составленного описания;

- объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над ними. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути, описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

Подведем итоги по данной главе. Алгоритм – это точная, понятная последовательность действий. Он имеет 5 основных свойств таких, как определенность, массовость, результативность, понятность и дискретность; и 2 характеристики: временная и объемная. Алгоритм имеет 4 способа описания: словесный, графический, псевдокоды и программный.

Глава 2 Структуры алгоритмов

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

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

• Ввод исходных данный в память ЭВМ;
• Вычисление искомых величин по формулам;
• Вывод результатов из памяти ЭВМ на информационный носитель.

Стандартная блок-схема линейного алгоритма приводится на рис. 8 (вы­числение суммы двух чисел — А и В).

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

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

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

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

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

Структура ветвление существует в четырех основных вариантах [1] (см. табл. 3): если – то; если – то – иначе; выбор; выбор – иначе.

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

Различия в исполнении этих конструкций вытекают из свойств ветвления.

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

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

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