Формальная модель исполнителя
Исполнитель алгоритма — это объект, который умеет выполнять только заранее определённые команды. Формальная модель исполнителя описывает его среду, систему команд, начальное состояние, допустимые действия и условия отказа; именно эти сведения позволяют строго проверить, будет ли алгоритм работать.
Из чего состоит формальная модель
Любого учебного исполнителя удобно описывать несколькими элементами. Такая запись отделяет то, что исполнитель умеет, от того, что требуется получить в конкретной есепке.
- Среда — объекты и пространство, в которых действует исполнитель: клетки поля, сосуды с водой, числа, переменные или другие элементы.
- Начальное состояние — положение объектов и значения величин до начала работы алгоритма.
- Система команд — полный список команд, доступных исполнителю.
- Правила выполнения — результат каждой команды и условия, при которых она разрешена.
- Отказ — остановка с ошибкой, если команда неприменима в текущем состоянии.
- Конечное состояние — результат после выполнения всех команд алгоритма.
Формальная модель — это описание множества состояний исполнителя, его системы команд и переходов между состояниями. Если состояние обозначить \(S\), а команду — \(C\), то выполнение команды можно записать как переход \(S \xrightarrow{C} S'\), где \(S'\) — новое состояние.
В школьных задачах исполнитель обычно детерминирован: для одного состояния и одной допустимой команды результат однозначен. Поэтому алгоритм можно рассматривать как последовательность команд, переводящую начальное состояние в требуемое конечное.
Здесь \(S_0\) — начальное состояние, \(C_1, C_2, \dots, C_n\) — команды алгоритма, а \(S_n\) — состояние после последней команды.
Среда и состояния исполнителя
Среда исполнителя — это не только видимая область на рисунке. Она включает все объекты, которые могут изменяться или влиять на выполнение команд. Например, для Робота средой является поле со стенами и клетками, для Водолея — сосуды с заданными вместимостями и количеством воды, а для алгоритма с переменными — набор числовых значений.
Состояние должно содержать всю информацию, необходимую для продолжения работы. Для Робота это как минимум координаты, направление и расположение стен; для Водолея — текущие объёмы воды в сосудах; для вычислительного исполнителя — значения переменных и, иногда, положение указателя команд.
Если два состояния полностью совпадают по всем параметрам, существенным для команд, то из них выполнение одного и того же продолжения алгоритма даст одинаковый результат. Нельзя игнорировать параметр, который влияет на применимость команды или её результат.
Важно различать состояние и результат тапсырма. Состояние описывает ситуацию в данный момент, а результат — состояние, удовлетворяющее условию задачи. Иногда одинаковый результат достигается разными последовательностями команд.
Система команд и ограничения
Система команд исполнителя — это не любой набор действий, которые можно придумать, а строго заданный перечень. Если в списке есть команды «налево» и «направо», нельзя заменить их командой «повернуться на 180 градусов», пока такая команда явно не разрешена. Сложное действие нужно представить последовательностью доступных простых команд.
У каждой команды есть область применимости. Например, команда движения может быть разрешена только при отсутствии стены перед исполнителем; команда наполнения сосуда — только пока сосуд не заполнен; операция деления — только при ненулевом делителе.
Отказ исполнителя — это ситуация, когда очередная команда не может быть выполнена по правилам среды. После отказа алгоритм не считается успешно выполненным, даже если до этого были получены нужные промежуточные значения.
Алгоритм для конкретного исполнителя должен удовлетворять двум требованиям: каждая его команда принадлежит системе команд, а в момент выполнения команды соблюдены все ограничения. Проверять нужно не только начальное и конечное состояние, но и каждый промежуточный шаг.
Нельзя считать команду допустимой только потому, что она записана в системе команд. Наличие команды в списке ещё не означает, что она разрешена в любом состоянии. Перед каждым шагом проверяйте границы, стены, вместимость, деление на ноль и другие ограничения.
При жазбалар алгоритма на школьном алгоритмическом тілінде команды и условия должны соответствовать возможностям исполнителя. Если для выбора действия нужна проверка, используется условие; повторяющиеся действия удобно оформлять как цикл.
Исполнитель находится у стены. В его системе команд есть команда «вперёд», но движение через стену запрещено. Что произойдёт при выполнении команды?
Как проверять алгоритм
Проверка алгоритма — это последовательное моделирование его работы. Для каждого шага полезно фиксировать номер команды, состояние до неё, команду, проверку применимости и состояние после неё.
| Шаг | Состояние до команды | Команда | Проверка | Состояние после |
|---|---|---|---|---|
| 0 | \(S_0\) | — | Начальное состояние | \(S_0\) |
| 1 | \(S_0\) | \(C_1\) | Команда допустима | \(S_1\) |
| 2 | \(S_1\) | \(C_2\) | Команда допустима? | \(S_2\) |
| … | \(S_{i-1}\) | \(C_i\) | Тексеру ограничение | \(S_i\) |
Если алгоритм содержит условие, сначала определяется истинность условия в текущем состоянии, а затем выбирается соответствующая ветвь. Если есть цикл, проверяется условие каждой итерации и фиксируется изменение состояния. Число повторений нельзя угадывать по внешнему виду записи: его находят по условию остановки и изменению величин.
Составьте таблицу состояний и отмечайте изменение только тех параметров, которые меняет текущая команда. Так легче обнаружить отказ, пропущенный шаг, неверное направление изменения переменной или преждевременную остановку цикла.
Разобранный пример: достижение числа
Исполнитель работает с переменной \(x\). Начальное значение \(x=2\). Доступны команды «увеличить \(x\) на 3» и «уменьшить \(x\) на 1». Требуется получить \(x=10\). Рассмотрим алгоритм: увеличить, увеличить, уменьшить, увеличить, увеличить.
Нужно проверить не только конечное значение, но и соответствие каждой команды системе команд. Все пять команд разрешены при любых значениях \(x\), поэтому отказ невозможен.
Алгоритм не решает тапсырманы: он заканчивается при \(x=13\), а не при \(x=10\). Ошибка обнаруживается только после полного моделирования. Например, после двух увеличений уже получено \(x=8\), поэтому достаточно ещё бір увеличения на 3 и бір уменьшения на 1: \(2\to5\to8\to11\to10\).
Показать правильное Шешім Шешім
Подходящая последовательность: увеличить, увеличить, увеличить, уменьшить. Она использует только разрешённые команды и приводит к требуемому состоянию.
Формальная жазба и завершение
Алгоритм считается корректным для данного начального состояния, если он выполняет только допустимые команды, не приводит к отказу, завершается и получает результат, указанный в условии. Эти требования связаны: алгоритм, который достигает цели, но делает это после отказа или никогда не заканчивается, корректным не является.
В задачах с числовыми исполнителями нужно учитывать переменные и их текущие значения. В задачах с Водолеем полезно отдельно изучить исполнителя Водолей и его команды: там состояние задаётся объёмами воды, а ограничения — вместимостью сосудов и доступными операциями.
Формальная модель отвечает на төрт главных вопроса: где действует исполнитель, что он умеет делать, когда команда разрешена и какое состояние должно получиться в конце.
Быстрая проверка
Главное
- Формальная модель задаёт среду, состояния, систему команд, правила применимости и отказ.
- Каждая команда переводит исполнителя из одного состояния в другое; алгоритм — последовательность таких переходов.
- Команда может быть известна исполнителю, но недопустима в конкретном состоянии.
- Корректность означает допустимость всех қадам, завершение и получение требуемого результата.
- Для проверки алгоритма моделируйте работу по шагам и фиксируйте промежуточные состояния.