Тема 1. Основы алгоритмизации. Алгоритм и его свойства.

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

Это понятие относится к исходным математическим понятиям, которые не могут быть определены через другие, более простые понятия. Такое или подобное определение называют интуитивным, т.е. понятным из опыта.

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

Каждый алгоритм должен задаваться:

• множеством исходных допустимых данных;

• начальным состоянием;

• множеством допустимых промежуточных состояний;

• правилами перехода из одного состояния в другое;

• множеством конечных результатов;

• конечным состоянием.

В зависимости от конкретного задания этих параметров определяются классы алгоритмов. Например: линейные, циклические, сортировки и другие алгоритмы.

Математическое определение алгоритма есть уточнение понятия алгоритма в интуитивном смысле и представляется в виде машины Тьюринга, машины Поста, нормального алгоритма Маркова.

Слово «алгоритм» происходит от латинской формы написания имени арабского математика аль-Хорезми (полное имя - Абу Абдуллах Мухаммад ибн Муса аль-Хорезми (783-850 гг.), жил и работал в Багдаде), который разработал правила четырех арифметических действий над числами в десятичной системе счисления.

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

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

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

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

3. Массовость предполагает, что алгоритм применим к целому классу однотипных задач, а при решении конкретной задачи из этого класса исходные данные могут меняться в определенных пределах.

4. Конечность следует понимать в том смысле, что каждый алгоритм должен приводить к конечному результату за конечное число шагов. Алгоритм не допускает зацикливаний.

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

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

7. Понятность. Каждый алгоритм создается в расчете на определенного исполнителя. В качестве исполнителя алгоритма могут быть автоматы, роботы, ЭВМ, человек. Для того чтобы исполнитель мог выполнить алгоритм, он должен понимать каждое его предписание. Совокупность предписаний, которые понятны исполнителю и которые он может выполнить, называют системой команд исполнителя. Для правильного построения алгоритма необходимо знать систему команд исполнителя.

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