Средства представления алгоритмов

АЛГОРИТМЫ

Основные понятия

Понятие «алгоритм» появилось в девятом веке и связано с именем

математика Аль-Хорезми, который сформулировал правила выполнения

четырех арифметических действий над многозначными числами.

В настоящее время понятие алгоритма – одно из фундаментальных

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

предметом изучения такой отрасли математики как теория алгоритмов, с

другой стороны, в информатике существует неформальное определение

алгоритма, и алгоритмизация выступает в качестве общего

метода информатики.

Алгоритм– это точно определенная последовательность действий

для некоторого исполнителя, выполняемых по строго определенным

правилам и приводящих через некоторое количество шагов

к решению задачи.

Исполнитель алгоритмовопределяет элементарные действия, из

которых формируется алгоритм. Отдельные действия, составляющие

алгоритм, называются операциями. При этом под операцией понимается

как какое-то единичное действие, например, сложение, так и группа

взаимосвязанных действий.

Основными особенностями любого алгоритма являются решение

задачи в обобщенном виде и возможность выполнять действия по

решению задачи для конкретных значений (не только человеку, но и

различным техническим устройствам (исполнителям)). Основным

исполнителем несложных алгоритмов является человек. Достаточно

вспомнить последовательность действий для решения систем линейных

уравнений, вычисления корней уравнений.

При решении сложных задач исполнителем является программное

обеспечение ЭВМ, и составление алгоритма решения задачи является

необходимым этапом, детализирующим метод решения для

дальнейшей реализации.

Свойства алгоритма:

определенность – выполнив очередное действие, исполнитель

должен точно знать, что ему делать дальше;

дискретность – прежде, чем выполнить определенное действие,

надо выполнить предыдущее;

массовость – по одному и тому же алгоритму решаются

однотипные задачи и неоднократно;

понятность – алгоритм строится человеком для конкретного

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

модификацию при необходимости;

результативность – алгоритм всегда должен приводить

к результату.

Мы видим, что в процессе формального решения задачи ее решение

сначала описывается на языке математики в виде системы формул, а затем

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

ранее определенные математические формулы и условия их выполнения.

Таким образом, алгоритм рассматривается как средство описания

процесса решения задачи, как связующее, промежуточное звено в цепочке

«метод решения – реализующая программа».

Средства представления алгоритмов

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

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

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

Алгоритм, реализующий решение задачи, можно задать различными

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

текстовых, табличных.

Графические средствапредставления алгоритмов имеют ряд

преимуществ благодаря визуальности и явному отображению процесса

решения задачи. Алгоритмы, представленные на языке графических

объектов, получили название визуальные алгоритмы.

Текстовое описаниеалгоритма является достаточно компактным и

может быть реализовано на абстрактном или реальном языках

программирования в виде программы для ЭВМ. Таблицы значений

представляют алгоритм неявно, как некоторое преобразование конкретных

исходных данных в выходные.

Табличный способописания алгоритмов может быть с успехом

применен для проверки правильности функционирования разработанного

алгоритма на конкретных тестовых наборах входных данных, которые

вместе с результатами выполнения алгоритма фиксируются в «таблицах

трассировки».

Таким образом, все три способа представления алгоритмов можно

считать взаимодополняющими друг друга. На этапе проектирования

алгоритмов наилучшим способом является графическое представление, на

этапе проверки алгоритма – табличное описание, на этапе применения –

текстовая запись в виде программы.

Визуальные алгоритмы

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

графические блоки, представленные на рис. 2.

Рассмотрим общие правила при проектировании визуальных

алгоритмов:

 в начале алгоритма должны быть блоки ввода значений

входных данных;

 после ввода значений входных данных могут следовать

блоки обработки и блоки условия;

 в конце алгоритма должны располагаться блоки вывода

значений выходных данных;

 в алгоритме должен быть только один блок начала и один

блок окончания;

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

ненаправленными линиями.

Этап проектирования алгоритма следует за этапом выбора

формальной модели и методов решения задачи, на котором определены

входные и выходные данные, а также зависимости между ними.

При построении алгоритмов для сложной задачи используют

системный подход с использованием последовательной декомпозиции

решаемой задачи на ряд подзадач до тех пор, пока не будут определены

задачи, для которых алгоритмическое решение известно или оно может

быть оперативно найдено.

Одним из системных методов разработки алгоритмов является метод

структурной алгоритмизации. Этот метод основан на визуальном

представлении алгоритма в виде последовательности управляющих

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

обработки информации структуры: композицию, альтернативу и итерацию.

С помощью этих структур можно описать решение большого класса задач

обработки информации.

Композиция (следование)– это линейная управляющая

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

для описания единственного процесса обработки информации.

Альтернатива– это нелинейная управляющая конструкция, не

содержащая итерацию. Она предназначена для описания процессов

решения различных задач обработки информации, выбор которых зависит

от значений входных данных.

Итерация– это циклическая управляющая конструкция, которая

содержит композицию и ветвление. Она предназначена для организации

повторяющихся процессов обработки последовательности

значений данных.

Линейные алгоритмы не содержат блока условия. Они

предназначены для представления линейных процессов. Такие алгоритмы

применяют для описания обобщенного решения задачи в виде

последовательности модулей.

Пример линейного алгоритма приведен на рис. 3.

В соответствии с наличием в алгоритмах управляющих структур

композиции, альтернативы и итерации алгоритмы классифицируют на

линейные, разветвленные и циклические алгоритмы.