Инвариант

Инвариант — условие которые выполняется до и после каждого шага цикла. Инварианты могут использоваться для доказательства корректности алгоритмов.

Пример инварианта для каждой итерации линейного поиска:

$$(0\le i<N)\wedge (A_k:0\le k<i:a_k\ne x)$$

Ссылки

• Алгоритмы и структуры данных. Новая версия для Оберона. Никлаус Вирт. ДМК Пресс. 2010. Глава 1. Фундаментальные структуры данных. 1.8. Поиск

Ссылки на эту заметку

Эта заметка на GitHub

Обсудить на форуме