Определение и свойства алгоритма

Основные темы параграфа:

■ происхождение понятия «алгоритм»;

■ исполнитель алгоритма;

■ алгоритмический язык;

■ свойства алгоритма;

■ определение алгоритма;

■ формальное исполнение алгоритма;

■ что такое программа.

Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Поэтому в нем очень важно как следует разобраться.

Происхождение понятия «алгоритм»

Само слово «алгоритм» происходит от имени выдающегося математика средневекового Востока Мухаммеда ибн Мусы аль-Хорезми (787-850 гг.). Им были предложены приемы выполнения арифметических вычислений с многозначными числами (вам они хорошо знакомы из школьной математики). Позже в Европе эти приемы назвали алгоритмами, от Algorithms — латинского написания имени аль-Хорезми. В наше время алгоритм понимается шире, не ограничивается только арифметическими вычислениями.

Исполнитель алгоритма

Из предыдущего параграфа вы узнали, что алгоритм — это последовательность команд управления каким-либо объектом. Мы назвали такой объект объектом управления или исполнителем алгоритма. Им может быть как техническое устройство, так и живое существо.

Рассмотрим исполнителя-человека. Для него можно сформулировать множество алгоритмов, например алгоритмы арифметических вычислений. С таким же успехом можно назвать алгоритмами множество различных инструкций, предписывающих последовательность действий человека для выполнения какой-либо работы. Например, кулинарный рецепт — это алгоритм работы повара с целью приготовления блюда; инструкция по сборке машинки из деталей детского конструктора — алгоритм для ребенка; инструкция по использованию кухонного комбайна — алгоритм для домохозяйки.

Вы, наверное, никогда не задумывались над тем, какое количество алгоритмов вам известно. Жизненный опыт человека растет с увеличением числа освоенных им алгоритмов. Например, чтобы ребенок научился покупать в магазине хлеб, ему нужно сначала рассказать (а лучше показать), как это делается. Освоив «алгоритм покупки хлеба», он в дальнейшем будет успешно выполнять эту работу.

Поиск выигрышной тактики, а следовательно, и алгоритма несложной игры — интересная и полезная задача. Рассмотрим одну из таких игр, которая называется игрой Баше.

Играют двое. Перед ними 21 предмет, допустим, камни (также может быть 11, 16, 26 и т. д.). Игроки берут камни по очереди. За один ход можно взять 1, 2, 3, 4 камня. Проигрывает тот, кто забирает последний камень.

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

алг Игра Баше

Нач

1. Предоставить ход сопернику.

2. Взять столько камней, чтобы в сумме с предыдущим ходом соперника получилось 5.

3. Если остался один камень, то объявить о своем выигрыше, иначе вернуться к выполнению команды 1.

Кон

Игрок, строго следующий этому алгоритму, будет всегда выигрывать, даже если он не понимает, почему так происходит.

Алгоритмический язык

В приведенном примере записи алгоритма используется символика учебного Алгоритмического языка (АЯ).

Из примера видно, что при записи алгоритма на АЯ вначале пишется заголовок, начинающийся со служебного слова алг (сокращенное слово «алгоритм»). Затем указывается название алгоритма, которое составитель алгоритма придумывает сам. Следующая часть называется телом алгоритма. Она начинается со служебного слова нач (начало) и заканчивается словом кон (конец). Тело алгоритма представляет собой последовательность команд для исполнителя.

Здесь и в дальнейшем служебные слова в алгоритмах на АЯ будут записываться жирным шрифтом. В языках программирования (как и в АЯ) служебными называются слова, которые всегда употребляются в одном и том же смысле.

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

Это свойство алгоритма называется дискретностью.

Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того чтобы алгоритм был выполним, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы подробная инструкция ему ни давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Такой перечень называется системой команд исполнителя алгоритмов (СКИ).

Это свойство алгоритма называется понятностью.

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

Это свойство алгоритма называется точностью.

Это свойство алгоритма называется конечностью.

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

Дано: катеты прямоугольного треугольника a = 3 см; b = 4 см.

Найти: гипотенузу c.

Алгоритм решения этой задачи можно представить в таком виде:

алг Гипотенуза

Нач

1. Возвести а в квадрат.

2. Возвести b в квадрат.

3. Сложить результаты действий 1 и 2.

4. Вычислить квадратный корень результата действия 3 и принять его за значение с.

Кон

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

Еще пример: для поиска номера телефона нужного вам человека исходными данными являются: фамилия, инициалы человека и телефонная книга (точнее, информация, заключенная в телефонную книгу). Однако этого может оказаться недостаточно. Например, вы ищете номер телефона Смирнова А. И. и обнаруживаете, что в книге пять строк с фамилией «Смирнов А. И». Ваши исходные данные оказались неполными для точного решения задачи (вместо одного номера телефона вы получили пять). Оказалось, что нужно знать еще домашний адрес.

Набор: «фамилия — инициалы — телефонный справочник — адрес» является полным набором данных в этой ситуации.

Если исходные данные неполные, то задачу либо совсем нельзя решить (ничего нельзя узнать про гипотенузу по одному катету), либо получается неоднозначное решение (пять номеров телефонов).

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

Определение алгоритма

Обобщая все сказанное, сформулируем определение алгоритма.