Алгоритм и его свойства

Алгоритм и его свойства

Разберём § 1 учебника «Информатика. 10 класс» В. М. Котова и соавторов, с. 8–10. Сначала познакомимся с понятием алгоритма и решетом Эратосфена, затем рассмотрим свойства, примеры и способы проверки алгоритмов.

1. Что называют алгоритмом

Понятие алгоритма пришло в информатику из математики. Название связано с именем математика IX века Мухаммеда ибн Мусы аль-Хорезми, описавшего правила арифметических действий.

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

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

В § 1 это описание раскрывает смысл понятия, но не считается строгим математическим определением: оно само использует понятия, которым ещё нужно дать точное определение. Поэтому дальше учебник уточняет понятие алгоритма через его свойства.

2. Пример 1.1. Решето Эратосфена

Задача из учебника: получить все простые числа, не превышающие заданное натуральное число N. Простое число больше 1 и имеет ровно два натуральных делителя: 1 и само себя. Например, 2 и 3 — простые, а 4 делится ещё и на 2.

Разберём ту же границу, что показана на рисунке учебника: N = 50. Число 1 в список не входит.

1. Если N = 1, выдай пустой список и закончи. Иначе запиши числа от 2 до N.
2. Сохрани число 2. Вычеркни его кратные, большие самого числа: 4, 6, 8 и далее.
3. Найди следующее незачёркнутое число, большее предыдущего. Если такого числа нет или оно больше √N, перейди к шагу 5. Иначе сохрани его и вычеркни его кратные, большие его самого. Например, для 3 это 6, 9, 12 и далее. Уже зачёркнутые числа пропускай.
4. Повторяй шаг 3 с очередными незачёркнутыми числами. Проверка границы выполняется до вычёркивания их кратных.
5. Все оставшиеся незачёркнутыми числа и будут простыми числами от 2 до N.

При N = 50 получаем √50 ≈ 7,07. Поэтому вычёркиваем кратные 2, 3, 5 и 7, сохраняя сами эти числа. Следующее незачёркнутое число — 11, оно больше √50.

Результат: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

Почему достаточно √N? У составного числа есть делитель, отличный от 1 и не превышающий квадратного корня из этого числа. Если бы оба множителя были больше корня, их произведение оказалось бы больше самого числа. Поэтому все составные числа до N уже будут вычеркнуты.

Попробуй сам (А1). Выполни эти действия для N = 20. Запиши, кратные каких простых чисел достаточно вычеркнуть, и перечисли оставшиеся числа. Ответ пока не открывай.

3. Шесть свойств алгоритма

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

Дискретность

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

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

В решете сначала выписываем числа, затем обрабатываем кратные 2, потом кратные 3. После каждого шага можно увидеть, какие числа остались.

Детерминированность (определённость)

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

Если два ученика точно выполнят решето для N = 50, на каждом соответствующем этапе они получат одинаковый список. Если кто-то случайно зачеркнёт 7, это ошибка выполнения, а не недостаток самого алгоритма.

Понятность

Смысл каждой команды должен быть однозначно понятен исполнителю. Описание должно быть полным и точным, чтобы исполнителю не приходилось самостоятельно принимать недостающие решения.

Команда «вычеркни кратные 3, большие 3» понятна тому, кто умеет находить кратные. Для исполнителя без такой возможности команду нужно выразить через доступные ему действия.

Результативность

Точное выполнение должно дать ответ на вопрос задачи. Нужно заранее определить, что считать результатом, в том числе для случая, когда искомого объекта нет. Ответ «решения нет» тоже может быть предусмотренным результатом.

Решето должно оставить именно простые числа до N. Если после остановки в списке осталось составное число 49, задача решена неверно. Дополнительный случай: при N = 1 простых чисел в заданном диапазоне нет; результат — пустой список.

Конечность

Выполнение должно завершаться за конечное число шагов и выдавать результат. Это свойство тесно связано с результативностью.

В решете список ограничен числом N, а условие остановки задаётся через √N. Бесконечная команда «повторяй снова» без возможности завершения нарушила бы конечность.

Массовость

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

Для решета меняется натуральное N: например, 20, 30 или 50. Правила те же. Отрицательное N не входит в выбранную область применения. При N = 1 список пуст; это допустимый особый случай.

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

4. Примеры 1.2 и 1.3. Где возникают трудности

Можно ли считать кулинарный рецепт алгоритмом

В примере 1.2 учебник рассматривает обычные рецепты. Одинаковые указания могут дать разный результат из-за условий приготовления и качества продуктов. Если эти условия не заданы как исходные данные, описание не обеспечивает детерминированность.

Кроме того, указания вроде «посоли по вкусу» требуют личного решения, а диапазон «добавь 2–3 ложки сахара» не определяет точное действие. Для формального исполнителя это проблема понятности. Здесь оценивается конкретная запись рецепта: точный технологический процесс с заданными условиями можно описывать алгоритмически.

А2. Какое свойство обсуждается в каждом случае: а) результат зависит от неуказанных условий приготовления; б) исполнителю предлагают самому решить, сколько означает «по вкусу»? Объясни, что нужно уточнить.

Человек решил задачу. Значит ли это, что алгоритм уже записан

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

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

5. Формы записи и базовые конструкции

Один алгоритм можно представить в разных формах. § 1 называет текстовое описание, блок-схему, машину Тьюринга и другие представления. При смене формы записи нужно сохранять смысл действий. Машина Тьюринга здесь — формальная математическая модель, а не обычный компьютер; устройство этой модели в данном уроке не изучаем.

Для построения алгоритмов используются три базовые алгоритмические конструкции:

Не смешивай: блок-схема — форма записи, а цикл — способ организации действий внутри алгоритма.

6. Теория алгоритмов и проверка правильности

Одну задачу иногда можно решить разными алгоритмами. Теория алгоритмов рассматривает их свойства и позволяет сравнивать способы решения, в том числе выбирать более эффективный. Эффективность связана с затратами на решение; её анализ — одна из задач этой теории. Подробные оценки эффективности будут изучаться позже.

Пример 1.4 называет два способа проверки правильности: математическое доказательство и специально подобранные тесты.

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

Б1. Подбери тесты — авторское задание к примеру 1.4

Нужно выдать большее из двух чисел a и b, а если они равны — их общее значение. Предложена запись:

1. Получить a и b.
2. Если a > b, выдать a и закончить.
3. Если b > a, выдать b и закончить.
4. Закончить.

Проверь пары (8, 3), (3, 8), (5, 5). Для каждой запиши ожидаемый ответ и фактическое поведение. Найди пропущенный случай, дополни запись и проверь её на (−2, −2). Объясни, почему одна только остановка ещё не гарантирует решения задачи.

7. Вопросы по итогам § 1

Ответь своими словами без подсказок:

1. Что такое алгоритм? Включи в объяснение команды, исполнителя, допустимые данные и конечное число шагов.
2. Какие шесть свойств характеризуют алгоритм? Приведи пояснение хотя бы к одному свойству.
3. Какие базовые алгоритмические конструкции используют при составлении алгоритмов?

Домашняя работа: прочитай § 1, с. 8–10, ответь на эти три вопроса. Для закрепления выполни решето при N = 30 и объясни, после какого простого числа можно завершить вычёркивание.

Самопроверка после выполнения

Показать ответ после выполнения

Историческая справка из полей § 1

В 1930-е годы началась разработка математических моделей для строгого определения алгоритма. В учебнике названы машина Тьюринга, машина Поста и нормальный алгоритм Маркова, а также отмечена эквивалентность этих подходов к формализации понятия. Упомянуты Алан Тьюринг и Эмиль Пост, предложившие свои модели в 1936 году. В этом уроке достаточно понимать назначение моделей; устройство и доказательство их эквивалентности остаются за его пределами.

Дополнительный пример после параграфа

Пример с периметром можно использовать для ещё одной проверки свойств. Для положительных длин a и b в сантиметрах получи a и b, вычисли s = a + b, затем P = 2 · s и выдай P в сантиметрах. При a = 5 и b = 3 получаем s = 8 и P = 16 см. При a = 4 и b = 2 получаем s = 6 и P = 12 см. Этот пример дополняет разбор учебника.

Источник: Котов В. М. и соавторы. Информатика. 10 класс. 2020, § 1, с. 8–10. Объяснения и задания изложены и оформлены MediaSchool.

План для учителя (PDF)