1. Цели, уровень и предварительные знания

• Определить допустимые входные данные и требуемый выход алгоритма.
• Проследить поиск максимума с переменной, условием и циклом.
• Обосновать корректность и завершение, затем различить доказательство и тесты.

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

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

Уровень: начальный. Достаточно уметь сравнивать целые числа и читать упорядоченную последовательность значений, которую здесь называют списком. Отрицательные числа допустимы. Знание языка программирования не требуется: начните на бумаге. Переход к коду — применение метода, а не скрытое предварительное требование.

2. Определить задачу до выбора метода

Мы ищем наибольшее значение в конечном непустом списке целых чисел. Входные данные могут содержать повторения; сортировать их заранее не обязательно. Выход — значение, а не его позиция и не число его вхождений. Для [3, 7, 7, 2] ожидаемый результат — 7.

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

3. Построить однозначную процедуру

Храните кандидата с именем best. Присвойте ему первое значение, затем просматривайте остальные по порядку. Если рассматриваемое значение строго больше best, замените best этим значением. Иначе оставьте его без изменения. После последнего значения верните best.

Присваивание изменяет сохранённое значение: best ← x означает «сохранить текущее значение x в best». Это не уравнение, действующее всегда. Условие выбирает действие; цикл повторяет шаги для оставшихся значений. Порядок, инициализация и условие являются частью метода наряду с итоговым результатом.

best ← первое значение списка
для каждого значения x после первого:
    если x > best:
        best ← x
вернуть best

Это псевдокод: он описывает метод, не требуя синтаксиса конкретного языка. Его нельзя вставлять в интерпретатор Python без изменений.

Иллюстрация создана с помощью искусственного интеллекта. Она показывает роль памяти; точный числовой ход выполнения и его обоснование приведены в тексте и таблице.

4. Проследить решённый пример

Для [3, 7, 7, 2] инициализация даёт best = 3. Остаётся сравнить три значения.

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

5. Обосновать корректность и завершение

После каждого шага best равен максимуму уже просмотренной части. Такое сохраняющееся свойство называется инвариантом. В начале оно выполняется, поскольку просмотренная часть содержит только первое значение. Если следующее значение больше, замена кандидата сохраняет это свойство; иначе оно сохраняется и при оставлении кандидата без изменения. В конце просмотренная часть — весь список, поэтому постусловие выполнено.

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

6. Перевести метод в программу на Python

Ниже приведён перевод для непустого списка целых чисел. values[0] обозначает его первое значение; range(1, len(values)) перебирает следующие индексы. Отступы определяют границы цикла и условия.

def maximum(values):
    best = values[0]
    for i in range(1, len(values)):
        x = values[i]
        if x > best:
            best = x
    return best

Эта функция предполагает, что предусловие выполнено. Она не является полноценным интерфейсом проверки входных данных: пустой список вызывает ошибку при обращении к values[0]. Пропущенные значения, смешение типов и бесконечные списки выходят за рамки определённой задачи. Перед повторным использованием следует уточнить контракт и обработку отклоняемых входных данных. Код предназначен для понимания метода; на практике встроенная функция поиска максимума может быть предпочтительнее.

7. Упражнение с пояснениями

Проследить поиск максимума

Выполните процедуру вручную для [5, 1, 9, 3]. Составьте таблицу с рассматриваемым значением, best до и best после; укажите выход и число сравнений.

Критерий успеха : Трассировка инициализирует best первым значением, рассматривает каждое следующее значение один раз и объясняет решение при каждом сравнении.

Разбор, который следует читать после собственной попытки: начальное значение кандидата равно 5; после 1, 9 и 3 оно последовательно равно 5, 9 и 9. Три сравнения приводят к выходному значению 9. В каждой строке должны быть видны рассматриваемое значение, кандидат до и кандидат после; одного правильного выхода недостаточно, чтобы объяснить рассуждение.

8. Соразмерный проект

Специфицировать и проверить процедуру

Для [12, 8, 15, 15, 4] запишите предусловие и постусловие, проследите поиск максимума и обоснуйте завершение. Добавьте тесты [-4, -2, -9], [6] и [3, 3]. Объясните предусмотренную обработку пустого списка и опасность инициализации нулём.

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

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

9. Оценка переноса метода

Перенести метод на поиск минимума

Адаптируйте процедуру для поиска минимума конечного непустого списка целых чисел. Приведите псевдокод, проследите [6, -1, 4, -1] и объясните сохраняющееся свойство и завершение. Найдите контрпример к инициализации нулём, затем уточните, почему пустой список по-прежнему выходит за рамки контракта.

Критерий успеха : Метод работает во всей заявленной области, учитывает повторения и список из одного элемента, разделяет тест и доказательство и обосновывает инициализацию, сравнение и завершение, не повторяя заученное правило без объяснения.

Напишите обоснование, не пользуясь заметками, и объясните каждый выбор. Затем сравните свой метод с поиском максимума: какие шаги сохраняются и какое решение меняется?

10. Ограничения и частые ошибки

Инициализация best нулём кажется подходящей для некоторых списков положительных чисел, но не работает для [-4, -2, -9]: программа возвращает 0, которого нет даже во входных данных. Инициализация первым значением позволяет избежать этого скрытого предположения. Список из одного элемента и повторения — допустимые случаи, а не аномалии.

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

11. Итоги, активное воспроизведение и следующий шаг

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

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

Краткий эталонный ответ: метод отличается от его перевода; трассировка начинается с 2, переходит к 5, затем остаётся на 5, при двух сравнениях. Ноль ошибочно задаёт нижнюю границу для значений. Число элементов, которые ещё предстоит обработать, уменьшается на один до нуля.

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

12. Источники и редакционная методика

Этот оригинальный раздел сопоставляет две независимые учебные программы учреждений: французскую программу «Numérique et sciences informatiques», класс Première, BO от 22 января 2019 года, приложение, с. 8 «Langages et programmation» и с. 9 «Algorithmique», и английскую программу computing 2013 года, «Key stage 2» и «Key stage 3». Источники перечитаны 12 октября 2026 года. Сопоставление касается спецификации, последовательности, выбора, повторения, тестов и обоснования; оно не подтверждает полный охват этих программ.

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