Лекция: Алгоритм, его свойства и формы представления. Типовые структуры алгоритма.
АЛГОРИТМ (algorithm). Содержание и последовательность операций, точно определяющие решение задачи путем вычислительного процесса, преобразующего исходные данные в конечный результат. Характеристиками алгоритма являются: 1) однозначность результата при заданных исходных данных; 2) возможность расчленения процесса на конечное число отдельных операций, каждая из которых может быть выполнена человеком или вычислительной машиной; 3) способность получения результата для множества исходных данных, соответствующих множеству однотипных задач. Например, один из А. вычисления с помощью ЭВМ среднего арифметического трех чисел представляет собой следующую последовательность операций: ввод с клавиатуры в ЭВМ трех чисел; вычисление суммы введенных чисел; деление полученной суммы на 3; вывод результата на экран дисплея. В приведенном примере для записи А. был применен русский язык. Существуют специально созданные алгоритмические языки. Вычислительной машине А. задается в виде программы. Могут существовать несколько А. решения одной и той же задачи. Среди них следует выбирать наиболее эффективный, для вычислительной реализации которого требуется наименьшее количество операций, машинного времени, памяти и т. п. Изучение существования и способов построения (разработки) эффективных А. составляет основу теории алгоритмов
Алгоритм — точное описание способа решения задачи, устанавливающее состав операций и последовательность их выполнения.
Любой алгоритм должен обладать следующими свойствами:
— повторяемостью получаемого результата при многократных расчетах с одними и теми же исходными данными;
— результативностью — обязательным получением некоторого результата (числа, таблицы, текста, звука, изображения и т.д.) или сигнала о том, что данный алгоритм неприменим для решения поставленной задачи;
— массовостью — возможностью получения результата при различных исходных данных для некоторого класса сходных задач;
— дискретностью — возможностью разбиения алгоритма на отдельные элементарные действия.
Существуют следующие формы представления алгоритма:
- словесная (текстуальная);
- графическая;
- на языках программирования.
Словесная форма представления алгоритма имеет ряд недостатков. Для достаточно сложных алгоритмов описание становится слишком громоздким и ненаглядным. Эта форма представления обычно используется лишь на начальных стадиях разработки алгоритма.
Приведем пример словесной формы описания алгоритма.
Чтобы перейти улицу, нужно посмотреть налево, убедиться в отсутствии приближающегося транспорта, дойти до середины улицы, посмотреть направо, убедиться в отсутствии близко идущего транспорта, продолжить движение через улицу. При наличии движущихся транспортных средств нужно ждать, когда транспорт проедет.
Графическая форма представления алгоритмов является более компактной и наглядной. Алгоритм изображается в виде последовательности связанных между собой блоков, каждый из которых соответствует выполнению одного или нескольких операторов. Такое графическое представление называется блок-схемой алгоритма.
Условные графические обозначения символов, используемых для составления блок-схемы алгоритма, стандартизированы. Некоторые, часто используемые обозначения, приведены в таблице 1.
Отдельные блоки алгоритмов соединяются между собой линиями потоков информации, которые проводятся параллельно внешней рамке чертежа. Направления линий потока сверху-вниз и слева-направо принимаются за основные и, если линии потоков не имеют изломов, стрелками не обозначаются.