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

План лекции:

1. Понятие и свойства алгоритма.

2. Способы описания алгоритма.

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

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

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

Для иллюстрации этих свойств алгоритма можно рассмотреть вычисление значения функции sin (x) методом разложения ее в ряд по степеням. Очевидно, что при расчете по подобной формуле окончательного ответа не будет, поскольку в условии задачи ничего не говорится о количестве членов ряда, которые необходимо учитывать при вычислениях. Без подобных указаний вычислительный процесс может продолжаться бесконечно. Чтобы этого не произошло, следует ввести некоторые ограничения, обеспечивающие свойствоконечности алгоритма, в частности задать некоторое допустимое число шагов выполнения алгоритма. Например, суммирование продолжать до тех пор, пока значение очередного, учитываемого в сумме члена ряда не станет меньше некоторого ε, равного 10⁴. В этом случае за некоторое конечное число шагов будет получен результат, и алгоритм вычисления функции приобретет свойство результативности.

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

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

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

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

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

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

Логический блочный символ «решение» (рисунок 1 е–и (блоки 6, 7, 8, 9 соответственно)) используют для обозначения выбора направления выполнения алгоритма в зависимости от некоторых условий. В блоке указывают условие, вопрос или решение, определяющие дальнейшее направление выполнения алгоритма. Условия могут быть простыми (рисунок 1е (блок 6)) и составными (рисунок 1з (блок 8)). В них должны быть учтены абсолютно все возможные варианты следования процесса при решении задачи.

Из блока проверки условия может выходить два, три и более (блок 9) информационных потока, что отличает его от других блочных символов, имеющих не более одного выхода. Выходящие из блока линии должны снабжаться пояснениями о направлениях исполнения алгоритма при выполнении или невыполнении приведенного условия (например, «да», «нет», «<0», «=0», «>0», «=1»,«+» «–» или др.).

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

I = А_НАЧ, А_КОН, ∆А,

где I – переменная цикла,

А_НАЧ и А_КОН – начальное и конечное значения переменной цикла,

∆А – шаг ее изменения (переменная цикла изменяется от А_НАЧ до А_КОН с шагом ∆А).

Если шаг равен 1, то ∆А можно не указывать. Кроме входящей линии, блок модификации имеет одну выходящую (на рисунке 1л обозначенную «Вых»), а также линии, отмечающие передачу вычислительного процесса на обработку для циклических вычислений «Цикл» и возврат в начало для изменения переменной цикла «Изм. пер».

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

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

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

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

Рисунок 1 – Наиболее употребляемые в схемах алгоритмов блок-символы

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

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

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

· не допускается передача управления в никуда. «Источник» передачи управления и «получатель» должны быть четко обозначены.

Лекция 2