§ 47. Еще раз о понятии «алгоритм»

Определения и обозначения

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

Исполнитель алгоритма — объект или человек, способный выполнять команды алгоритма из заранее определённого набора. Исполнителем может быть человек, робот или компьютер, если он умеет выполнять нужные действия. Понятие исполнителя нужно, чтобы оценить, выполнимы ли команды, а не только понятны ли они автору.

Система команд исполнителя — полный набор команд, которые понимает и может выполнить конкретный исполнитель. Например, компьютер может сравнивать числа и выполнять присваивание, но не понимает бытовую команду «посмотри внимательнее» без дополнительных инструкций. Зная систему команд, можно проверить, подходит ли ей описание решения.

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

Как это устроено

Алгоритм рассматривают как последовательность отдельных шагов, потому что исполнитель должен понимать, что делать в каждый момент. Общее описание вроде «разберись с данными и найди ответ» сообщает цель, но не объясняет способа её достичь. Разбиение на шаги делает действия проверяемыми: можно установить, выполнена ли команда и какой шаг следует дальше. Поэтому даже сложное решение представляют как цепочку простых операций и переходов.

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

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

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

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

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

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

Разбор задач

1. Инструкция «найдите самое большое число»

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

1. Определим входные данные: набор чисел, среди которых требуется найти наибольшее. В условии набор не задан, поэтому исполнитель не знает, с чем работать.
2. Проверим последовательность действий: команда «найдите» не задаёт, как сравнивать числа и сохранять текущий максимум. Одно лишь умение сравнивать не устраняет этот пробел.
3. Уточним описание: например, сравнивать числа по очереди, каждый раз сохранять большее и в конце вывести сохранённое значение. Это уже задаёт шаги и позволяет получить ответ для непустого набора.

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

2. НОД по алгоритму Евклида

Условие. Составим алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел a и b. Алгоритм Евклида использует факт: НОД(a, b) = НОД(b, a mod b), если b ≠ 0; a mod b — остаток от деления a на b. Нужно задать повторяющийся шаг и объяснить остановку.

1. Пока b ≠ 0, вычислить r = a mod b. Это команда, которую исполнитель должен уметь выполнять для натуральных чисел.
2. Заменить a на b, а b на r. После замены пара чисел сохраняет тот же НОД, поэтому повторение не меняет искомый ответ.
3. Проверить условие снова и повторять действия, пока остаток не станет нулём. Остатки при делении натуральных чисел убывают, поэтому в конце концов получится нулевой остаток.
4. Когда b = 0, вывести a. По свойству НОД пара (a, 0) имеет НОД, равный a.

Ответ. Алгоритм завершится за конечное число шагов: положительные остатки уменьшаются и не могут убывать бесконечно. Например, для 48 и 18 остатки равны 12, 6, 0, поэтому НОД равен 6. Алгоритм применим к парам натуральных чисел при условии, что хотя бы одно из них положительно.

3. Сравнение двух описаний решения

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

1. Выделить исходные данные и требуемый результат в каждом описании. Если вход или цель неясны, исполнитель не сможет установить, когда задача решена.
2. Проверить каждую команду по системе команд исполнителя. Команда, которой он не понимает или не умеет выполнять, делает описание непригодным для него.
3. Убедиться, что шаги и условия перехода точны, а выполнение заканчивается результатом за конечное число шагов. Затем проверить, работает ли способ для всех допустимых данных, а не только для приведённого примера.

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

Типичные ошибки

Первая ошибка — считать алгоритмом любое полезное описание действий. Обычно так происходит, когда цель принимают за способ: фраза «найди максимум» звучит понятно, но не задаёт шаги. Проверь себя: сможет ли исполнитель действовать без догадок, зная только текст и исходные данные?

Вторая ошибка — забыть об исполнителе и использовать команду, которой нет в его системе. Это случается, когда автор описывает действия так, как сам привык их понимать. Сверь каждую команду с возможностями исполнителя; если операции нет, её нужно заменить доступной последовательностью действий.

Третья ошибка — путать конечность записи алгоритма с малым числом шагов. Из-за краткого описания цикла может показаться, что его повторения автоматически допустимы. Цикл разрешён, если для допустимых данных выполняется условие остановки; проверь, что оно обязательно достигается, а не просто присутствует в записи.

Четвёртая ошибка — считать решением алгоритм, проверенный только на одном примере. Один удачный результат ещё не доказывает, что способ работает для остальных данных. Подумай, как алгоритм действует на разных допустимых входах и граничных случаях; массовый способ применим ко всему заданному классу задач.

Связь с другими темами

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

Что запомнить

• Алгоритм задаёт точную последовательность действий.
• Алгоритм предназначен для конкретного исполнителя.
• Каждая команда алгоритма должна быть понятна исполнителю.
• Алгоритм состоит из отдельных шагов.
• Алгоритм должен приводить к результату за конечное число шагов.
• Массовый алгоритм применим к множеству допустимых исходных данных.
• Один алгоритм можно записывать разными способами.