Лекция №3. Алгоритм и его свойства.

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

Понятие алгоритма – одно из фундаментальных понятий информатики. Слово «алгоритм» происходит от латинской формы написания имени математика IX века аль Хорезми, который сформулировал правила выполнения арифметических действий над многозначными числами. Научное определение понятию алгоритма дал Черч в 1930 г. Позже и другие математики вносили свои уточнения в определение.

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

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

Основные свойства алгоритмов.

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

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

2. Понятность: алгоритм составляется с ориентацией на определенного исполнителя. Составляя запись для исполнителя необходимо ориентироваться лишь на те команды, которые есть в его СКИ.

3. Определенность: (детерминированность): Будучи понятным, алгоритм не должен содержать предписаний, смысл котрых может восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результата.

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

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

2.Базовые алгоритмические структуры

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