Лекция по составлению алгоритмов и спецификаций для простейших случаев Любой алгоритм - это упорядоченная последовательность действий, направленная на перевод системы из одного состояния в другое. Соответственно, начальное состояние называется предусловием - чтобы алгоритм правильно работал, нужно, чтобы он запустился только тогда, когда система находится в начальном состоянии, иначе нельзя гарантировать, что выполнение всех действий приведёт к ожидаемому результату, или, что эти действия не приведут к аварии. Конечное состояние называется постусловием - алгоритм обязан гарантированно приводить к конечному состоянию, нередко окончание работы алгоритма (особенно с циклами и/или рекурсией) определяется именно по факту выполнения постусловия (т.е. достижения ожидаемого результата). Пред- и постусловие разрабатываются
до алгоритма и потом помогают программисту составлять сам алгоритм. Когда алгоритм разбивается на части - на последовательные шаги или этапы, пред- и постусловие разрабатываются для каждого шага, при этом постусловие предыдущего не должно конфликтовать с предусловием последующего шага.
Как этим пользоваться? Рассмотрим на элементарном примере. Допустим, система - это дверь. Соответственно, она может находиться в двух состояниях: открыта или закрыта. И над ней можно выполнять три действия: открыть или закрыть, а также узнать текущее состояние. Поскольку алгоритм должен переводить систему из одного состояния в другое, для двери возможно составить 2 алгоритма, каждый из которых состоит лишь из 1 действия.
Предусловие А: дверь открыта.
Алгоритм А: закрыть дверь.
Постусловие А: дверь закрыта.
Предусловие Б: дверь закрыта.
Алгоритм Б: открыть дверь.
Постусловие Б: дверь открыта.
Отсюда видно влияние пред- и постусловий на возможность применения алгоритмов. Совершенно очевидно, что открытую дверь нельзя открыть ещё раз, перед этим не закрыв, и нельзя закрыть уже закрытую дверь. Т.е. к предусловию А алгоритм Б просто не подходит - возникнет логическая ошибка при исполнении.
Но алгоритмы могут быть и более сложными, например:
Алгоритм В: закрыть дверь, открыть дверь.
Алгоритм Г: закрыть дверь, открыть дверь, закрыть дверь.
Алгоритм В подходит для предусловия А, но после его исполнения не будет справедливым постусловие А - поэтому такой алгоритм отвергается. Наконец, алгоритм Г подходит и для предусловия А, и для постусловия А - это корректный алгоритм для решения задачи, его можно применять. Но здравый смысл говорит, что алгоритм А предпочтительнее, потому что проще.
Если ослабляется (т.е. уменьшается количество ограничений) предусловие или усиливается (т.е. увеличивается количество ограничений) постусловие - алгоритм должен становиться сложнее, если наоборот - алгоритм можно упростить.
Например, если предусловие "дверь открыта", то более слабое предусловие "дверь открыта или закрыта" или, другими словами, "дверь находится в любом состоянии". Усиление происходит в обратном направлении: от безразличия мы должны перейти к определённости.
Посмотрим, как это влияет на алгоритмы:
Предусловие: дверь открыта или закрыта.
Алгоритм: закрыть дверь.
Постусловие: дверь закрыта.
В этом примере алгоритм подходит для постусловия, но слишком прост для предусловия - в некоторых случаях мы будем пытаться закрыть уже закрытую дверь, поэтому его нужно усложнить:
Предусловие: дверь открыта или закрыта
Алгоритм: ЕСЛИ дверь открыта ТО закрыть дверь КОНЕЦ ЕСЛИ
Постусловие: дверь закрыта
Пока что у нас дверь открывалась и закрывалась бессмысленно - не обсуждался вопрос, зачем её открывать или закрывать. Чтобы на такой вопрос получить ответ, систему с дверью нужно поместить в контекст другой системы. Например, система "дверь к врачу". К врачу потому, что такая дверь не бывает постоянно открыта, чтобы не мешать проходу, как это бывает, например, в магазинах, дверь у врача специально предназначена для возможности сохранения врачебной тайны.
В этом новом контексте уже имеет смысл ситуация:
Предусловие: дверь закрыта.
Алгоритм: открыть дверь, закрыть дверь.
Постусловие: дверь закрыта.
Такой алгоритм служит для впускания или выпускания посетителя, и не является ненужным усложнением. Но, как я выше говорил, любой алгоритм должен менять состояние системы. А этого в данной ситуации не видно.
Нужно добавить в систему посетителя. Посетитель умеет входить и выходить и может быть в двух состояниях: снаружи и внутри. К нему можно применить аналогичные рассуждения, что и к двери - подробно расписывать не буду, думаю, это очевидно. Возникает вопрос, как увязать посетителя и дверь между собой.
Попробуем сопоставить состояния:
ЗВ: дверь закрыта и посетитель внутри - возможно;
ЗС: дверь закрыта и посетитель снаружи - возможно;
ОВ: дверь открыта и посетитель внутри - возможно;
ОС: дверь открыта и посетитель снаружи - возможно.
Лишних состояний нет. Если бы мы к двери добавили замок с состояниями отперт и заперт, то очевидно, что состояние, когда дверь открыта и замок заперт хотя и возможно, но бессмысленно, смысл имеет только запертый замок у закрытой двери.
Раз нет лишних состояний, нужно подумать, какие допустимы комбинации действий. Для этого нужно исследовать, как могут меняться состояния, и какие действия при этом выполняются.
Например, если предусловие - ЗВ, а постусловие - ЗС, то возможны алгоритмы:
ЗВ-ЗС-1: посетитель выходит;
ЗВ-ЗС-2: открыть дверь, посетитель выходит, закрыть дверь;
ЗВ-ЗС-3: посетитель выходит, открыть дверь, закрыть дверь;
ЗВ-ЗС-4: открыть дверь, закрыть дверь, посетитель выходит;
и другие более длинные комбинации. Тут здравый смысл говорит, что из всех вариантов подходит только ЗВ-ЗС-2, так как посетитель может войти или выйти лишь через открытую дверь. Но здравый смысл хорошо работает только в очевидных случаях вроде этого, а более сложные и неочевидные случаи могут потребовать больших раздумий, какой из вариантов лучше выбрать - чтобы это решить, нужно очень хорошо понимать, что происходит.
Или, например, если предусловие - ЗВ, а постусловие - ОВ, то возможны алгоритмы:
ЗВ-ОВ-1: открыть дверь;
ЗВ-ОВ-2: посетитель выходит, открыть дверь, посетитель входит;
ЗВ-ОВ-3: открыть дверь, посетитель выходит, посетитель входит;
ЗВ-ОВ-4: посетитель выходит, посетитель входит, открыть дверь;
и другие более длинные комбинации. Здесь уже допустимы как ЗВ-ОВ-1, так и ЗВ-ОВ-3.
Что ещё интересно: посетитель может выполнять своё действие только при состоянии открытой двери. Значит можно сформулировать правило: прежде, чем посетитель выполняет свои действия, дверь нужно открыть. По контексту, поскольку дверь ведёт к врачу, мы договорились, что в конце концов она должна закрываться - это будет в самом конце любого алгоритма.
Посредством формулировки таких утверждений о порядке действий начинают проступать особенности всего множества осмысленных алгоритмов по данной теме. Но чтобы не делать утомительного перечисления всех этих алгоритмов, можно свести их к формуле - для этого понадобятся переменные.
Обозначим Z состояние двери, а Y состояние посетителя. Через ~Z и ~Y обозначим противоположные состояния. Например, если Z - дверь открыта, то ~Z - дверь закрыта, если же Z - дверь закрыта, то ~Z - дверь открыта. Соответственно, формула алгоритмов:
Предусловие: Z
Какой-то алгоритм.
Постусловие: ~Z
подходит как для описания открытия, так и для описания закрытия двери. Или, как говорят, формула инвариантна относительно содержания действия, а её абстрактный смысл - измнение состояния системы на противоположное.
В нашем случае имеется:
Предусловие: Z и Y.
Шаги алгоритма.
Постусловие: дверь закрыта и ~Y.
Шаги алгоритма должны приводить к изменению состояния, описываемого исходным предусловием, чтобы получить окончательное постусловие.
Один шаг
Предусловие: Z
Постусловие: дверь закрыта
Если Y не упоминается, то для этого шага значение переменной не имеет значения.
Другой шаг
Предусловие: дверь открыта и Y
Постусловие: дверь открыта и ~Y.
Теперь попробуем сложить:
Предусловие: Z и Y
Шаг 1, предусловие: Z
Шаг 1, постусловие: дверь закрыта
Шаг 2, предусловие: дверь открыта и Y
Шаг 2, постусловие: дверь открыта и ~Y
Постусловие: дверь закрыта и ~Y
Как говорилось, в алгоритме каждое постусловие и следующее за ним предусловие не должны друг другу противоречить. Также не должны противоречить внешнее и первое вложенное предусловия, внешнее и последнее вложенное постусловия. Здесь это не соблюдается: постусловие шага 1 противоречит предусловию шага 2, постусловие шага 2 противоречит общему постусловию - значит нужно попробовать переставлять шаги, чтобы максимально уменьшить противоречия.
Предусловие: Z и Y
Шаг 1, предусловие: дверь открыта и Y
Шаг 1, постусловие: дверь открыта и ~Y
Шаг 2, предусловие: Z
Шаг 2, постусловие: дверь закрыта
Постусловие: дверь закрыта и ~Y
Положение улучшилось: все прежние противоречия устранились. Но появилось новое противоречие между общим предусловием и предусловием шага 1. Перестановка шагов ухудшит положение, значит остаётся лишь одно средство - добавить ещё один шаг, который снимает противоречие.
Предусловие: Z и Y
Шаг 1, предусловие: Z
Шаг 1, постусловие: дверь открыта
Шаг 2, предусловие: дверь открыта и Y
Шаг 2, постусловие: дверь открыта и ~Y
Шаг 3, предусловие: Z
Шаг 3, постусловие: дверь закрыта
Постусловие: дверь закрыта и ~Y
Теперь не осталось противоречий, и можно писать алгоритм. Но можно ещё обратить внимание, что постусловие шага 2 в части Z сильнее, чем предусловие шага 3. Если в конце шага 2 дверь гарантированно открыта, то в начале шага 3 она не может быть открытой или закрытой - она точно открыта. Поэтому мы смело можем усилить предусловие шага 3 и, как в самом начале говорилось, это приведёт к упрощению алгоритма на шаге 3.
Предусловие: Z и Y
Шаг 1, предусловие: Z
Шаг 1, постусловие: дверь открыта
Шаг 2, предусловие: дверь открыта и Y
Шаг 2, постусловие: дверь открыта и ~Y
Шаг 3, предусловие: дверь открыта
Шаг 3, постусловие: дверь закрыта
Постусловие: дверь закрыта и ~Y
Осталось только подставить нужные алгоритмы, которые, записанные в порядке следования, дадут нам общий алгоритм:
Шаг 1, алгоритм: ЕСЛИ дверь закрыта ТО открыть дверь КОНЕЦ ЕСЛИ
Шаг 2, алгоритм: посетитель входит (или посетитель выходит)
Шаг 3, алгоритм: закрыть дверь
Теперь алгоритм можно закодировать на языке C++. Условимся, что состояния описываются переменными (z и y) логического типа (bool), и константа true соответствует открытой двери и посетителю внутри. Договоримся описать алгоритм в отдельной функции, которой будем передавать ссылки на переменные (т.е. если функция будет менять значения переменных, это будет сказываться на других частях программы). Результата у функции нет (тип void). Назовём функцию "пройти" (go).
Вот это всё вышеперечисленно: пред- и постусловия, шаги алгоритма на русском языке, выбор способа кодирования - решения о том, как сказанное на русском языке, будет выражено в коде - вот это всё называется спецификацией. По ней можно совершенно точно написать требуемый участок кода:
void go(bool &y, bool &z)
{
// Шаг 1
if(!z)
{
z = true;
}
// Шаг 2
y = !y;
// Шаг 3
z = false;
}
Естественно, хоть сколь-нибудь опытный программист в подавляющем большинстве случаев всё это не расписывает, и такие соображения и доводы приходят к нему автоматически. Начинающим же именно нужно попробовать так подробно порассуждать, пока у них не выработается соответствующий навык мышления.