Конспект: алгоритм и исполнитель

Понятия

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

Исполнитель - тот, кто выполняет алгоритм. Система команд - что он умеет без объяснений.

Интерпретатор выполняет текст программы строка за строкой; компилятор переводит программу в другой язык, обычно в команды процессора, и выполняется уже перевод.

Состояние - значения всех переменных в данный момент и место, откуда выполнение продолжится. Шаг переводит одно состояние в другое.

Трассировка - таблица «шаг - значения после него», которую ведут руками по тексту программы.

Что унести

Определённость меряется относительно исполнителя: «до готовности» - команда для повара и не команда для новичка. Массовость - свойство универсального способа, а не условие: «напечатай 42» входа не имеет и остаётся алгоритмом.

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

Доказательство остановки опирается на предположения («оба числа положительны»). Граница допустимых входов - ноль, пустой список, равные элементы - и есть место, где предположение ломается.

Трассировка: строка таблицы - выполненный шаг, в клетке - значение ПОСЛЕ шага, у условия - True или False. Ошибку ищут в первой строке, где таблица разошлась с ожиданием.

Присваивание перезаписывает: после a = b старого a нет нигде. Обмен - через временную переменную.

Ловушки джокера

Проверил остановку на тестах. Тесты обходят плохой вход: Евклид вычитанием висит на паре с нулём и работает на всех положительных.

Остановилась - значит решила. «Ответ - меньшее из двух чисел» останавливается на любой паре, а на (84, 36) отвечает 36, на которое 84 не делится.

Инструкция, понятная только тому, кто и так умеет. Рецепт для опытного повара - не алгоритм для исполнителя без опыта.

Вёл таблицу в голове и пропустил «очевидный» круг. Дефект второго по величине жил ровно там.

Заполнил клетки замыслом, а не текстом. Таблица повторила замысел и ничего не нашла.

Обмен двумя присваиваниями. a = b; b = a даёт два одинаковых значения.

Значение переменной цикла после цикла. Его показывает последняя проверка условия, которая вернула False: после while i < 10 с удвоением i равно 16.

Проверь себя

Чем «перебирай числа, пока не найдёшь общий делитель» хуже, чем вычитание меньшего из большего?

Почему алгоритм вычитанием останавливается на положительных парах и где это рассуждение ломается?

Где в программе поиска второго по величине таблица впервые расходится с ожиданием на [3, 8, 5, 8]?

Что напечатает a = 4; b = 9; a = b; b = a; print(a, b) и почему?