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

1. Общее понятие алгоритма

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

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

В соответствии с данной теорией понятие алгоритма может рас­сматриваться (и применяться) на трех уровнях: интуитивно-содер­жательном, формальных уточнений и так называемом прикладном уровне.

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

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

Алгоритмы делятся на вычислительные и невычислительные.

Например, правила решения уравнения, построение графика функций, вычисление / = (ах+ву) • d –это вычислительные ал­горитмы. Расписание лекций, режим дня, процессуальный поря­док ведения допроса – это невычислительные алгоритмы.

Алгоритм состоит из команд.

Команда – это отдельное указание исполнителю выполнить некоторое законченное действие.

Команды алгоритма выполняются одна за другой. Последова­тельное выполнение команд алгоритма приводит к решению зада­чи.

Основные свойства алгоритма – это детерминированность (определенность), дис­кретность, массовость, результативность и инвариантность по от­ношению к вычислителю.

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

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

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

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

4. Результативность означает, что при точном выполнении всех команд алгоритма процесс заканчивается получением опре­деленного результата за конечное число шагов. Если задача реше­ния не имеет, – это тоже результат.

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