Лекция 2. Алгоритмы

Лекция 2. Алгоритмы 

1.     Понятие алгоритма, его свойства и формы представления

2. Описание ГОСТ 19.701 – 90

3. Примеры простейших алгоритмов

1.    Понятие алгоритма, его свойства и формы представления

Понятие алгоритма является одним из важнейших понятий, на которых базируется применение компьютеров для решения различных задач. Термин АЛГОРИТМ является собирательным названием множества определений от строго математического до таких, как:

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

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

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

Свойства (характеристики) алгоритмов:

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

2. Детерминированность - набор указаний должен быть точен, понятен и не допускать неоднозначных толкований. Это обеспечивает однозначность результата при заданных исходных данных. Детерминированность называют также определенностью.

3. Результативность - процесс должен приводить к результату за конечное число этапов. На компьютере нельзя получить результат, стремясь достичь бесконечности.

4. Массовость - последовательность действий должна быть пригодной для решения всех задач данного типа и на оговоренном множестве исходных данных должна сохранять первые три свойства алгоритмов.

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

Формы представления алгоритмов:

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

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

Начало;

п.0   Определить X и A;

п.1   Если  X>0, то перейти к п.2., иначе перейти к п.4;

п.2   Y:=X+A;

п.3   Перейти к п.5;

п.4   Y:=X-A;

п.5   Выдать значение Y как результат;

Конец.

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

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

элементов алгоритма отображается графическим символом. Схемы алгоритмов изображаются в соответствии с ГОСТами. Основные положения ГОСТ 19.701 – 90 приведены в следующем разделе. На рис. 1.1 приведен пример схемы алгоритма.

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

4. Программа на алгоритмическом языке. Язык программирования является изобразительным средством, служащим для упрощения и удешевления реализации алгоритма на ЭВМ. Это достаточно наглядная форма, являющаяся специфическим развитием формульно-словесной записи. В качестве примера ниже приведена программа определения значения Y по заданным условиям.

PROGRAM OPRED_Y;

  VAR A, X, Y: REAL;

BEGIN

  READ (A, X)                         { ввод данных       }

  IF X>0 THEN Y:=X+A         { расчет Y         по первой ветви  }

               ELSE Y:=X-A;          {                        по второй ветви   }

   WRITE (Y)                            { вывод результата   }

END.

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

2. Описание ГОСТ 19.701 – 90

Наряду с Единой системой конструкторской документации (ЕСКД) существует  Единая система программной документации (ЕСПД), требования которой должны выполняться в официальных документах. ЕСПД объединяет стандарты на языки программирования, алгоритмы конкретных процессов обработки данных и т.п.. Одним из стандартов ЕСПД является ГОСТ 19.701 – 90  (ИСО 5807 – 85) Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

2.1 Общие положения

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

1)    данных; они отображают путь данных при решении задач и определяют этапы обработки и различные применяемые носители данных;

2)    программ; отображают последовательность операций в программе;

3)    работы системы; отображают управление операциями и поток данных в системе;

4)    взаимодействия программ; отображают путь активаций программ и взаимодействий с соответствующими данными;

5)    ресурсов системы; отображают конфигурацию блоков данных и обрабатывающих блоков, которая требуется для решения задачи или набора задач.

В стандарте используются следующие понятия:

1)    основной символ – символ, используемый в тех случаях, когда точный тип (вид) процесса или носителя данных неизвестен или отсутствует необходимость в описании фактического носителя данных;

2)    специальный символ – символ, используемый в тех случаях, когда известен точный тип процесса или носителя данных или когда необходимо описать фактический носитель данных;

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

2.2 Описание и применение символов

Наиболее часто употребляемые символы приведены в табл. 1. Там же указана применимость символов для изображения тех или схем.

Символы в схеме должны быть расположены равномерно. Следует придерживаться разумной длины линий и минимального числа длинных линий. Не должны меняться углы и другие параметры, влияющие на соответствующую форму символов. Символы должны быть, по возможности, одного размера. В предшествующих ГОСТах определялось отношение высоты символа к его длине как 2/3 или  1/2, а также кратность размеров 5 мм.  Эти рекомендации полезны при ручном выполнении схем в тетрадях.

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

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

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

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

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

                                                                                                                      Таблица 1.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.