Правила выполнения соединений

Uuml; программа.

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

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя хаpактеpизуют:

среда;

элементарные действия;

система команд;

отказы.

Среда (или обстановка) - это "место обитания" исполнителя.

Напpимеp, для исполнителя Робота среда - это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды.

Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.

Напpимеp, команда Робота "вверх" может быть выполнена, если выше Робота нет стены. Ее результат - смещение Робота на одну клетку вверх.

После вызова команды исполнитель совершает соответствующее элементарное действие.

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

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

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

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

Для решения поставленной задачи необходимо описать способ (метод) решения задачи в соответствии с определенными правилами, а именно:

ü задать исходные данные;

ü в требуемой последовательности разбить процесс решения задачи на этапы;

ü указать признак окончания решения задачи;

ü определить результат решения задачи.

Такая четко сформулированная последовательность правил, описывающая способ (метод), и является алгоритмом.

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

Способы описания алгоритмов:

ü словесное описание (словесно-формульное),

ü графическое (блок-схема),

ü псевдокод (структурно-стилизованный)

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

Словесное описание(записи на естественном языке);

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

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм может быть следующим:

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

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

Словесный способ не имеет широкого распространения по следующим причинам:

- такие описания строго не формализуемы;

- страдают многословностью записей;

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

Начало

1 …..

2….. шаги

3…..

.

. алгоритма

.

Конец

Начало и конец определяют физическое начало и конец алгоритма соответственно. Все шаги алгоритма нумеруются. Номера шагов определяют порядок их выполнения.

Для этой формы записи алгоритма выполняется естественный порядок выполнения действий (шагов алгоритма): слева направо и сверху вниз. Этот порядок соответствует процедуре чтения текста: слева направо в строке и по строкам сверху вниз.

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

Существуют два способа графического представления алгоритмов.

Первый - с использованием структурограмм Нэсси-Шнейдермана, широко используется в западной литературе по программированию.

Второй – с помощью блок-схем, геометрические фигуры которых имеют начертания в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения», используется преимущественно в нашей литературе.

Структурограммы Нэсси-Шнейдермана

Блоки структурограмм Нэсси-Шнейдермана представлены в табл.1.

Таблица 1

Графические обозначения символов и их функций

Решение

Проверка условия

Цикл

Повторяют процесс пока повторяется некоторое условие в конце цикла

Цикл

Повторяют процесс пока повторяется некоторое условие в начале цикла

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

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

Обозначение некоторых блоков в соответствии с
ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ ДАННЫХ И СИСТЕМ

Соотношения между геометрическими элементами символов устанавливаются стандартом.

Размер а10, 15,20 … мм.

Размер b = 1,5а. (b = 2а.)

Линии потока рекомендуется выполнять в два раза тоньше линий обводки блоков.

Прерывание

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

Процесс

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

Предопределенный процесс

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

Решение

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

Данные

Символ отображает данные, носитель данных не определен.

Ручной ввод

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

Дисплей

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

Модификация

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

Граница цикла

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

Комментарий

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

Соединитель

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

Пропуск

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

Внутри блоков записываются выполняемые действия.

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

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

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

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

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

Пример.

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

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

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

Пример.

3. Две или более входящие линии могут объединяться в одну исходящую линию. Если две или более линии объединяются в одну линию, место объединения должно быть смещено.

4. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.

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

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

Пример.