Поддерживаемая фокусная точка HL. Первая оценка 2027 целевой показатель; официальный PDF возвращает 403; ранее приобретенный краткий план является финальной оценкой 2026. Оставшиеся руководство, оценка и практические требования сохраняют свои зарегистрированные удержания.
Предварительные требования: прочитайте указанные количества и единицы измерения, используйте арифметику и нижеприведённые условия модели. Каждый урок осваивает собственный метод перед независимым переносом.
Это оригинальные или явно вымышленные учебные примеры, а не фактические измерения или завершённые оценочные исследования учащихся.
5.2
Алгоритмы, трассировки и доказательства корректности
Что могло бы объяснить это наблюдение?
алгоритм может работать на одном примере и дать сбой на границе. Тестирование должно проектироваться по спецификации, а не только по «счастливому пути» (happy path).
Начните с гипотезы. Укажите величины или признаки, которые вы будете сравнивать, затем определите, какие доказательства могут различить два объяснения.
Постройте модель
Алгоритм — это конечная, однозначная процедура для выполнения задачи. Трассировка фиксирует изменения состояния. Инвариант цикла описывает свойство, сохраняемое каждой итерацией, и помогает обосновать корректность.
алгоритм: Конечная процедура, решающая поставленную задачу; граничный тест: Тест на пределе допустимого диапазона входных данных.
Выберите доказательства для проверки гипотезы
Укажите входные условия и ожидаемые выходные данные. Используйте граничные случаи, пустые коллекции (где разрешено), дубликаты и невалидные значения. Различайте неправильный алгоритм, неправильную реализацию и неполное требование.
Протрассируйте поиск по небольшому вымышленному отсортированному списку. Укажите конвенцию индексации. Для бинарного поиска обновляйте границы так, чтобы оставшийся интервал сужался, и отвергайте неотсортированный ввод, если сортировка не входит в задачу.
Работайте с известными величинами
Укажите известные значения и их единицы измерения. Выберите соотношение, предположения которого подходят к данному случаю, затем преобразуйте формулу перед подстановкой.
Известно: линейный поиск по списку из восьми элементов может потребовать восьми сравнений, когда искомый элемент находится в конце или отсутствует. Удвоение длины списка удваивает количество сравнений в худшем случае при этой модели. Бинарный поиск уменьшает интервал примерно вдвое на каждом шаге, но требует подходящей упорядоченной структуры.
Пример:
Линейный поиск просматривает все 14 элементов без нахождения совпадения. Сколько сравнений элементов происходит? Используйте ту же последовательность: известные величины → модель → соотношение → подстановка → единицы и интерпретация.
Проверьте вывод и его границы применимости
Успешная выборочная проверка не доказывает корректность для всех допустимых входных данных. Не импортируйте синтаксис псевдокода, специфичный для Cambridge, в курс IB без указания источника курса.
Вернитесь к первоначальному наблюдению. Объясните, что подтверждает результат, при каких условиях он верен и каким образом можно проверить конкурирующее объяснение.
Предупреждение:
Одна успешная выборочная проверка доказывает корректность алгоритма для каждого допустимого входного значения. Это утверждение неверно: Успешная выборочная проверка не доказывает корректность для всех допустимых входных данных. Не импортируйте синтаксис псевдокода, специфичный для Cambridge, в курс IB без указания источника курса.
Ключевые моменты:
Алгоритмы, трассировки и доказательства корректности: Опишите условия входных данных и ожидаемые результаты. Используйте граничные случаи, пустые коллекции (где это разрешено), дубликаты и недопустимые значения. Различайте ошибочный алгоритм от ошибки реализации или неполного требования.
Работоспособная трассировка и границы
def first_index(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(first_index([4, 7, 4], 4))
print(first_index([4, 7, 4], 9))
print(first_index([], 4))
Ожидаемый вывод:
0
-1
-1
Цикл сначала проверяет индекс 0, останавливается при совпадении и возвращает −1 только после полного перебора списка. Дубликаты поэтому возвращают первый индекс. Пустой список не выполняет тело цикла.
