Конспект: инженерия алгоритмов и проверка результата

Понятия

Стресс-тест - быстрое решение и перебор-эталон на тысячах маленьких входов; остановка на первом расхождении.

Гипотеза малой области - у логических ошибок почти всегда есть маленький свидетель.

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

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

Инвариант - условие на состояние структуры после каждой операции. Метаморфное отношение - связь ответов на два родственных входа; проверяется без знания правильного ответа.

Что унести

СТРЕСС-ТЕСТ
эталон: перебор по определению; генератор: длина 0-5, значения 1..3-10
пара с суммой s, ошибка i <= j:
  значения до 10⁹ - 2000 попыток чисто; до 10 - 4-я; до 3 - 3-я
полный перебор: длины 0-3, значения 1-3, s 2-6 = 200 входов,
  45 расхождений, самое маленькое - [1], s = 2
«не нашли» в малой области = «нет» только в этой области

УМЕНЬШЕНИЕ
куски: половина -> четверть -> по одному; потом числа к нулю
признак «разошлись»: 30 отрезков -> [] за 3 проверки (другая ошибка)
признак «непустой и недосчитывает»: -> [[1, 2], [0, 3]] за 56
вложенный отрезок: kon = s[1] вместо max(kon, s[1])
QuickCheck, Hypothesis: найти -> уменьшить -> показать

СЕРТИФИКАТЫ (Сандерс, 2.6.4)
сортировка: соседи по порядку + счётчики значений, O(n)
двудольность: раскраска / нечётный цикл
ацикличность: топологический порядок / цикл
кратчайшие пути: dist[v] <= dist[u] + w для всех рёбер (не завышено)
  + тугое ребро от родителя у каждой вершины (не занижено), O(V + E)
поток - разрез; паросочетание - покрытие (Кёниг); ЛП - двойственное

СВОЙСТВА
инвариант кучи: сломан на 11-й операции, ответ неверен с 14-й
метаморфные для пути: веса ×2 -> ответ ×2; новое ребро не удлиняет;
  переименование вершин не меняет
жадный «к ближайшему»: ×2 - 0 нарушений из 83; ребро - 7 из 83
поиск: нерелевантный документ не меняет топ

РАЗМЕН МОНЕТ
наименьший контрпример к жадности, если есть, < суммы двух крупнейших
  (Козен, Закс, 1994); две монеты с 1 - жадность всегда верна
1,3,4 -> 6; 1,7,10 -> 14; 1,15,25 -> 30; 1,98,99 -> 196
стресс на суммах до 10 пропускает 5 наборов из 6 с ошибкой

Ловушки джокера

Широкий диапазон в генераторе. Тысячи чистых попыток и ложное спокойствие.

Большой контрпример без уменьшения. Час отладки там, где хватило бы двух отрезков.

Признак «что-то не так». Уменьшение соскальзывает к пустому входу и чинят не ту ошибку.

Проверка тем же способом. Вторая Дейкстра из той же библиотеки ошибается так же.

Половина постусловия. Только «упорядочен» - и потеря повторов проходит.

Одно слабое отношение. Масштабирование прошло 83 из 83 - а ошибка в выборе направления осталась.

Молчание стресс-теста за доказательство. Без границы области «не нашли» не значит «нет».

Понятия

Что унести

Ловушки джокера

Комментарии

Оставить комментарий