- •7. Алгоритмы управления исполнителями.
- •7.1. Исполнитель Робот
- •7.2. Программное управление исполнителем
- •7.3. Общий вид алгоритма
- •7.4. Комментарии в алгоритмическом языке
- •7.5. Исполнение алгоритма
- •7.6. Ошибки в алгоритмах
- •7.7. Запись нескольких команд в одной строке
- •8.1. Понятие о вспомогательном алгоритме
- •Основные и вспомогательные алгоритмы
- •8.3. Пример использования вспомогательных алгоритмов
- •8. Вспомогательные алгоритмы
- •8.4. Метод последовательного уточнения
- •8.5. Заголовки вспомогательных алгоритмов
- •8.6. Разделение труда между компьютером и исполнителями
- •9 Цикл n раз
- •9.1. Пример алгоритма с циклом n раз
- •9.2. Общий вид цикла n раз
- •9.3. Короткие алгоритмы могут описывать длинные последовательности действий
- •9 А15 .4. Внутри цикла можно вызывать вспомогательные алгоритмы
- •9.5. Внутри цикла могут быть другие циклы
- •10. Цикл пока
- •10.1. Команды-вопросы Робота
- •10.2. Цикл пока
- •10.3. Диалог Компьютер — Робот при выполнении цикла пока
- •10.4. Общий вид цикла пока
- •10.5. Цикл n раз и цикл пока
- •10.6. Условия в цикле пока
- •10.7. Свойства цикла пока
- •1. Тело цикла может не выполниться ни разу
- •2. Выполнение цикла может не завершиться
- •3. Условие цикла не проверяется в процессе выполнения тела цикла
- •4. Перед каждым выполнением тела цикла условие обязательно выполняется.
- •5. Сразу после окончания цикла условие не выполняется
- •10.8. Составление алгоритмов с циклом пока
- •10.9. Примеры построения алгоритмов
- •1. Закрашивание ряда
- •2. Закрашивание коридора произвольной длины
- •3. Выход в левый верхний угол в лабиринте
- •11. Команды ветвления и контроля
- •11.1. Пример алгоритма с командой если
- •11.2. Общий вид команды если
- •11.3. Команды контроля
- •11.4. Пример алгоритма с командой утв
- •11.5. Выбор из многих вариантов
- •11.6 Общий вид команды выбор
- •12 Анализ и тестирование алгоритмов
- •12.1. Результаты труда программиста
- •12.2. Что такое правильный алгоритм
- •12.3. Пример рассуждения, подтверждающего правильность алгоритма
- •12.4. Тестирование алгоритмов
12 Анализ и тестирование алгоритмов
12.1. Результаты труда программиста
Составляя алгоритмы, мы с вами фактически были программистами. Подобную работу, только для других, намного более сложных задач, выполняют профессиональные программисты.
А что является итогом труда программиста? Предположим, в результате действия программы Робот выполнил какую-то полезную работу. Можно ли считать, что ее сделал программист? Нет, ее выполнил Робот. Может быть, программист управлял Роботом? Нет, этим занимался компьютер. Получается, что, хотя без программиста работа была бы невозможна, непосредственного участия в ней он вроде бы не принимает.
Результат работы программиста — это текст написанной им программы (алгоритма).
12.2. Что такое правильный алгоритм
Если нам точно известно, в какой начальной ситуации будет выполняться тот или иной алгоритм, то составить его нетрудно. Достаточно просто записать последовательность необходимых команд и оформить ее в соответствии с правилами языка. В полученном алгоритме не будет команд-вопросов — они не нужны, ведь ситуация полностью известна, следовательно, не будет в нем ни циклов пока, ни ветвлений. Такие алгоритмы называют линейными.
Проверить правильность линейного алгоритма очень легко — достаточно выполнить одну за другой все входящие в него команды, чтобы убедиться в достижении необходимого результата или же найти ошибку.
Однако значительно чаще бывает так, что задано только общее описание начальных условий, а точная ситуация неизвестна. С такими задачами мы встречались в §10—11. Правильно составленный алгоритм должен работать в любой ситуации, соответствующей условию.
Как проверить такой алгоритм? Конечно, для конкретной ситуации его можно исполнить и убедиться, что он работает (или не работает, тогда нужно искать ошибку). Но разных ситуаций может быть очень много, перебрать их все просто невозможно. Даже в простейшей задаче о движении Робота до стены (§10) количество ситуаций теоретически бесконечно — ведь расстояние до стены может быть любым.
Такая ситуация возникает не только с алгоритмами. Невозможно, например, перебрать все существующие треугольники, но доказав, что сумма углов треугольника всегда равна 180°, мы будем использовать это свойство для любого треугольника без дополнительной проверки. Такой прием очень распространен в математике: если какое-то свойство удается доказать, то потом его используют без дополнительных проверок.
Точно так же можно поступать и с алгоритмами. Если доказать, что алгоритм правильный, то нет необходимости проверять его отдельно для каждой ситуации.
А что такое правильный алгоритм? Интуитивно мы понимаем это, но для доказательства нужны четкие формулировки.
Правильность алгоритма означает, что для любой допустимой (соответствующей условию дано) начальной ситуации:
при выполнении алгоритма не может возникнуть отказ;
при выполнении алгоритма не может возникнуть зацикливание;
после завершения алгоритма будет достигнут правильный (соответствующий условию надо) результат.
Существуют специальные методы доказательства правильности алгоритмов, которые позволяют строго доказывать справедливость данных утверждений для конкретных алгоритмов. К сожалению, эти методы достаточно сложны и требуют серьезных математических знаний, выходящих за рамки школьного курса, поэтому мы вместо строгих доказательств будем проводить рассуждения, подтверждающие правильность алгоритмов.