1.1. Алгоритм и его формальное исполнение

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

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

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

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

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

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

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

В начале имеются исходные данные, например значения переменных или положение объекта. Каждая команда использует текущее состояние и создаёт новое, поэтому между началом и ответом появляются промежуточные результаты. Цепочка «исходные данные — команда — новое состояние» показывает, как алгоритм постепенно приводит исполнителя к результату.

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

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

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

Свойства алгоритма и их проявление при формальном исполнении

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

Разбор задач

Задача 1. Последовательные команды

Нужно формально выполнить алгоритм для x = 7: прибавить к x число 5, затем умножить результат на 2 и вывести x. Здесь нельзя сразу записать ответ, не показав изменения переменной. После каждой команды фиксируем новое значение x.

1. Исходное состояние: x = 7.
2. После команды «прибавить 5»: x = 7 + 5 = 12.
3. После команды «умножить на 2»: x = 12 · 2 = 24.
4. Команда вывода сообщает значение x, то есть 24.

Ответ: x = 24. Порядок важен: если сначала умножить 7 на 2, а потом прибавить 5, получится 19, то есть уже другой результат.

Задача 2. Проверка условия команды

Исполнитель получает число 6 и выполняет по порядку команды «увеличь число на 1» и «если число чётное, раздели его на 2». После первой команды число меняется, поэтому условие второй команды нужно проверять уже для нового значения. Нельзя делить исходное число 6, потому что это нарушило бы порядок действий.

1. Исходное число равно 6.
2. Увеличиваем его на 1: получаем 7.
3. Проверяем условие второй команды: 7 нечётное, поэтому деление на 2 не выполняется.

Ответ: результат равен 7. Условная команда не требует действия, если её условие ложно; формальный исполнитель просто переходит дальше.

Задача 3. Алгоритм Евклида

Для чисел 48 и 18 нужно повторять вычитание меньшего из большего, пока числа не станут равными. Чтобы не потерять ход решения, записываем пару чисел после каждого шага. Когда появляется равная пара, цикл заканчивается, и это число выводится.

1. 48 и 18: вычитаем 18 из 48, получаем 30 и 18.
2. 30 и 18: получаем 12 и 18.
3. 18 и 12: получаем 6 и 12.
4. 12 и 6: получаем 6 и 6.
5. Числа равны, поэтому повторение прекращается.

Ответ: 6. Таблица состояний показывает не только итог, но и причину окончания алгоритма: условие «числа не равны» стало ложным.

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

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

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

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

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

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

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

Формальное исполнение пригодится при изучении блок-схем, языков программирования и трассировки программ. Трассировка — это запись изменений переменных во время работы программы. Она помогает находить ошибки в алгоритмах и коде.

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

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

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