Шесть свойств алгоритма, проверка граничных случаев и исправление инструкций. По § 1 учебного пособия Котова: практические задания, скрытый разбор, презентация и план на 45 минут.
Конспект урока
Представь, что роботу поручили: «Выбери подходящий предмет и красиво поставь его рядом». Что значит «подходящий»? Рядом с чем? Как проверить красоту? Человек попробует догадаться. Исполнителю алгоритма нужны точные правила.
Твоя цель: проверить инструкцию по шести свойствам алгоритма, показать ошибку на конкретном примере и предложить исправление. Основа урока — § 1 «Алгоритм и его свойства» учебного пособия «Информатика. 10 класс» В. М. Котова и соавторов, 2020, с. 8–10. Понадобятся тетрадь и ручка; программировать сегодня не требуется.
Алгоритм задаёт понятные исполнителю, точно определённые действия, которые приводят к решению задачи за конечное число шагов для любого допустимого входа. Перед проверкой запиши три вещи: что дано, что нужно получить, какие команды умеет выполнять исполнитель.
Наш сквозной пример: даны два целых числа a и b. Нужно сообщить большее из них; если числа равны — сообщить это число. Исполнитель умеет сравнивать целые числа и выводить число.
a и b.a > b, вывести a; иначе вывести b.При a = 7, b = 4 получим 7; при a = 4, b = 7 — тоже 7, но выбрана другая ветвь. При a = 5, b = 5 условие ложно, выводится b, то есть 5. Равенство не осталось без правила.
Выполнение разбивается на отдельные действия. В рассматриваемой последовательности следующий шаг начинается после предыдущего. Указание «подготовь посылку» может оказаться слишком крупным для исполнителя: ему нужны команды «положи предмет в коробку», «закрой коробку». Насколько подробно разбивать действие, зависит от системы команд исполнителя. Иллюстрация показывает только идею этапов, а не полную инструкцию упаковки.
В примере с числами отдельно выполняются получение данных, проверка условия, вывод и завершение. Нумерация строк сама по себе не делает инструкцию алгоритмом.
В модели алгоритма из этого параграфа одни и те же исходные данные и правила задают одни и те же промежуточные результаты и ответ. «Возьми любой оранжевый предмет» оставляет выбор исполнителю, если таких предметов несколько. Нужно задать однозначный способ выбора.
Ветвление не нарушает детерминированность: условие a > b однозначно определяет, какую ветвь выполнить. Разные входы могут вести по разным ветвям. Для одинаковых входов выбор повторится.
Команды должны иметь для выбранного исполнителя ясный смысл и быть выполнимыми. Если робот умеет только «шаг вперёд» и «поворот направо», команда «нарисуй окружность» ему недоступна. Она может быть понятна другому исполнителю — например, человеку с циркулем.
Понятность и определённость тесно связаны, но вопросы различаются: умеет ли исполнитель выполнить команду и однозначно ли правила задают выполнение. У одной плохой инструкции могут нарушаться сразу несколько свойств.
После выполнения нужен ответ именно на поставленный вопрос. Если требуется выбрать большее число, команда «выведи сумму» даст число и завершится, но задачу не решит. Например, для 7 и 4 сумма 11 не является большим из двух исходных чисел.
Иногда корректный ответ — «решения нет». Например, уравнение x + 1 = x не имеет решений в целых числах. Это обоснованный ответ на задачу, а не сбой программы. Просто остановиться без ответа недостаточно.
Для каждого допустимого входа выполнение должно завершаться за конечное число шагов. Команды «увеличь число на 1; повтори» без выхода из повторения этому требованию не отвечают. Иллюстрация — метафора: свойства реального игрушечного поезда не доказывают свойства алгоритма.
Цикл может быть конечным. Если n — целое неотрицательное число, команда «пока n больше 0, уменьшай n на 1» дойдёт до нуля. Число уменьшений равно исходному n. У алгоритма не обязательно одинаковое число шагов для разных входов.
Алгоритм рассчитан на некоторый класс задач. Область применения задаёт допустимые исходные данные. Наш пример выбирает большее для любой пары целых чисел, включая отрицательные и равные.
Массовость не означает «подходит вообще для всего». Для команды «уменьшай n на 1 до нуля» область n = 0, 1, 2, ... существенна: начиная с −1, при уменьшении к нулю не придёшь. Работу с недопустимым входом можно предусмотреть отдельно.
Следование — действия идут последовательно. Ветвление — по условию выбирается действие. Цикл — действия повторяются. Эти три базовые конструкции позволяют строить алгоритмы. Одну идею можно записать словами или блок-схемой; запись на языке программирования обсудим в следующем уроке.
В § 1 приведено решето Эратосфена — способ находить простые числа, отбрасывая составные. Для чисел от 2 до 20 вычеркнем кратные 2, кроме 2; затем кратные 3, кроме 3. Останутся 2, 3, 5, 7, 11, 13, 17, 19. Здесь следующего простого 5 уже достаточно для остановки проверки: 5² > 20. Любое составное число не больше 20 имеет простой делитель не больше корня из 20. Этот пример — дополнительный; запоминать новый алгоритм наизусть сегодня не нужно.
Проверять алгоритм можно рассуждением и специально подобранными тестами. Один успешный тест не доказывает правильность для всех входов. Для выбора большего проверим оба порядка чисел, равенство и отрицательные числа. Один найденный контрпример уже опровергает утверждение «работает для всех допустимых входов».
Сначала выполни задания в тетради. Для каждого диагноза запиши проблемную команду → пример сбоя → исправление. Разбор ниже скрыт до нажатия кнопки.
Даны два целых числа. Нужно вывести большее, а при равенстве — это число. Предложена инструкция:
a > b, вывести a.b > a, вывести b.Проверь пары (8, 3), (3, 8) и (5, 5). Какой вход обнаруживает ошибку? Какое свойство нарушено для задачи в указанной области? Исправь инструкцию, сохранив все допустимые входы. До обсуждения запиши личный ответ: контрпример, свойство, исправление. После сверки сохрани первую попытку, а правки добавь отдельно: так будет видно, что именно ты понял и изменил.
Допустимы целые n ≥ 0. Нужно вывести исходное n, затем все целые числа по убыванию до 0 включительно. Инструкция: «Выведи n. Уменьши n на 1. Если n не равно 0, повтори сначала. Иначе заверши».
Запиши первые шаги для n = 2 и n = 0. Найди две разные проблемы и запиши исправленную инструкцию. Подсказка: проверь, когда выводится ноль и когда нужно проверять условие выхода.
Для каждой ситуации назови свойство, которое лучше всего объясняет указанную проблему. Обоснуй одним предложением; другие обоснованные нарушения тоже можно отметить.
(7, 4); для остальных входов ответа нет.Дано целое число t. Нужно вывести одно из сообщений: «отрицательное», «ноль» или «положительное». Исполнитель умеет сравнивать целые числа с нулём и выводить эти сообщения.
Запиши алгоритм словами, затем выполни его для −3, 0, 4. Партнёр проверяет: в каждом случае выведено ровно одно верное сообщение, нет команды «догадайся», выполнение останавливается. При самостоятельной работе выполни эту проверку сам.
Закрой разбор. Запиши два коротких ответа: почему завершение не гарантирует результативность и какие три вида входов нужно проверить в алгоритме определения знака числа. Объяснение с собственным примером важнее воспроизведения определения.
Дома прочитай § 1 и составь точную инструкцию для знакомого исполнителя. Укажи допустимые входы, результат и два теста, один из них — граничный. Найди фразу, которую исполнитель мог бы понять по-разному, и исправь её. Не используй примеры с действиями, которые нельзя проверить.
Котов В. М., Лапо А. И., Быкадоров Ю. А., Войтехович Е. Н. «Информатика. 10 класс». Народная асвета, 2020, § 1. Термины и границы темы сверены с учебником и программой информатики X–XI классов. Задания и иллюстрации созданы для этого урока. Изображения — учебные метафоры; точные условия задач заданы текстом.
Скачать и открыть
Показано 2 из 2
Презентация · для учителей
20 слайдов по § 1 учебного пособия Котова: шесть свойств алгоритма, допустимые входы, контрпримеры, исправление инструкций и самостоятельная практика. 18 основных слайдов и два дополнительных.
Методичка · для учителей
Самостоятельный план на 45 минут по § 1: реплики учителя, точные условия задач, трассировки и ключи, критерии, помощь, выходной билет и вариант без проектора. Шесть страниц.
Комментарии
Войдите, чтобы оставлять комментарии.
Пока нет комментариев. Будьте первым!