Как обмануть эвристику «попробуй несколько тестов»: алгоритмы, которые кажутся правильными, но на самом деле неверны

106

Чтобы попытаться проверить, является ли алгоритм для какой-либо проблемы правильным, обычная отправная точка состоит в том, чтобы попытаться запустить алгоритм вручную на нескольких простых тестовых примерах - попробуйте на нескольких примерах проблемных примеров, включая несколько простых «угловых случаев ». Это отличная эвристика: это отличный способ быстро отсеять множество неверных попыток алгоритма и понять, почему алгоритм не работает.

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

Так как же обмануть эвристику "попробуй кучу тестов"? Я ищу несколько хороших примеров, чтобы показать, что этой эвристики недостаточно. Другими словами, я ищу один или несколько примеров алгоритма, который выглядит поверхностно, как будто он может быть правильным, и который выводит правильный ответ на все мелкие входные данные, которые могут возникнуть у любого, но где алгоритм на самом деле не работает Может быть, алгоритм просто работает правильно на всех маленьких входах и терпит неудачу только для больших входов, или терпит неудачу только для входов с необычным шаблоном.

В частности, я ищу:

  1. Алгоритм Недостаток должен быть на алгоритмическом уровне. Я не ищу ошибки реализации. (Например, как минимум, пример должен быть независимым от языка, а недостаток должен касаться алгоритмических проблем, а не разработки программного обеспечения или реализации.)

  2. Алгоритм, который кто-то может правдоподобно придумать. Псевдокод должен выглядеть как минимум правдоподобно правильным (например, код, который запутан или явно сомнителен, не является хорошим примером). Бонусные баллы, если это алгоритм, который на самом деле придумал какой-то студент, пытаясь решить домашнюю работу или экзаменационную задачу.

  3. Алгоритм, который прошел бы разумную ручную стратегию тестирования с высокой вероятностью. Тот, кто пробует несколько небольших тестовых примеров вручную, вряд ли обнаружит недостаток. Например, «симуляция QuickCheck вручную на дюжине небольших тестовых случаев» вряд ли покажет, что алгоритм неверен.

  4. Желательно, детерминированный алгоритм. Я видел, что многие студенты думают, что «пробовать некоторые тестовые примеры вручную» - это разумный способ проверить правильность детерминированного алгоритма, но я подозреваю, что большинство студентов не будут считать, что использование нескольких тестовых примеров является хорошим способом проверки вероятностных алгоритмы. Для вероятностных алгоритмов часто нет способа определить, верен ли какой-либо конкретный результат; и вы не можете провернуть достаточное количество примеров, чтобы провести какой-либо полезный статистический тест на выходное распределение. Поэтому я бы предпочел сосредоточиться на детерминистических алгоритмах, поскольку они более понятны сердцу заблуждений учащихся.

Я хотел бы рассказать о важности доказательства правильности вашего алгоритма, и я надеюсь использовать несколько подобных примеров, чтобы помочь мотивировать доказательства правильности. Я предпочел бы примеры, которые являются относительно простыми и доступными для студентов; примеры, которые требуют тяжелой техники или тонны математического / алгоритмического фона, менее полезны. Кроме того, я не хочу, чтобы алгоритмы были «неестественными»; в то время как может быть легко создать какой-то странный искусственный алгоритм, чтобы обмануть эвристику, если он выглядит крайне неестественным или имеет очевидный черный ход, созданный просто для того, чтобы обмануть эту эвристику, он, вероятно, не будет убедительным для студентов. Есть хорошие примеры?

DW
источник
2
Мне нравится ваш вопрос, он также связан с очень интересным вопросом, который я видел на днях по математике и касался опровержения гипотез с большими константами. Вы можете найти его здесь
ZeroUltimax
1
Еще немного копания, и я нашел эти два геометрических алгоритма.
ZeroUltimax
@ZeroUltimax Вы правы, центральный пункт любых трех неколинейных точек не гарантированно находится внутри. Быстрое решение состоит в том, чтобы поставить точку на линии между крайним левым и крайним правым. Есть ли проблема еще где?
InformedA
Суть этого вопроса мне кажется странной, так как мне трудно разобраться, но я думаю, что все сводится к тому, что описанный процесс разработки алгоритма является принципиально нарушенным. Даже для студентов, которые не «останавливаются там», это обречено. 1> написать алгоритм, 2> придумать / запустить тестовые случаи, 3a> остановить или 3b> доказать, что они верны. Первый шаг в значительной степени был бы идентифицировать входные классы для проблемной области. Угловые случаи и сам алгоритм вытекают из них. (продолжение)
Мистер Миндор
1
Как вы формально отличаете ошибку реализации от некорректного алгоритма? Меня интересовал ваш вопрос, но в то же время меня беспокоил тот факт, что описываемая вами ситуация представляется скорее правилом, чем исключением. Многие люди проверяют то, что они реализуют, но обычно у них все еще есть ошибки. Второй пример ответа с наибольшим количеством голосов - именно такая ошибка.
Бабу

Ответы:

70

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

Пример: номиналы монет, и число n , выражают n как сумму d i : s с как можно меньшим количеством монет.d1,,dknndi

Наивный подход состоит в том, чтобы сначала использовать как можно большую монету и жадно получить такую ​​сумму.

Например, монеты со значениями , 5 и 1 будут давать правильные ответы с жадностью для всех чисел от 1 до 14, кроме числа 10 = 6 + 1 + 1 + 1 + 1 = 5 + 5 .65111410=6+1+1+1+1=5+5

Пер Александерссон
источник
10
Это действительно хороший пример, в частности тот, который студенты обычно ошибаются. Вам нужно не только выбрать конкретные наборы монет, но и конкретные значения, чтобы увидеть сбой алгоритма.
Рафаэль
2
Кроме того, позвольте мне сказать, что в этом примере учащиеся также часто имеют неправильные доказательства (с некоторыми наивными аргументами, которые не проходят при ближайшем рассмотрении), поэтому здесь можно выучить более одного урока.
Рафаэль
2
Британская система монет в старом стиле (до десятичности в 1971 году) имела реальный пример этого. Жадный алгоритм для отсчета четырех шиллингов будет использовать полкроны (2½ шиллинга), монету в один шиллинг и шесть пенсов (½ шиллинга). Но оптимальное решение использует два флорина (по 2 шиллинга каждый).
Марк Доминус
1
Действительно, во многих случаях жадные алгоритмы кажутся разумными, но не работают - другой пример - максимальное двустороннее соответствие. С другой стороны, есть также примеры, когда кажется, что жадный алгоритм не должен работать, но он работает: максимальное связующее дерево.
jkff
62

Я сразу вспомнил пример Р. Бэкхауса (это могло быть в одной из его книг). По-видимому, он назначил задание по программированию, где студенты должны были написать программу на Паскале, чтобы проверить равенство двух строк. Одна из программ, предложенных студентом, была следующей:

issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

Теперь мы можем протестировать программу со следующими входами:

"университет" "университет" Верно; Хорошо

«курс» «курс» Верно; Хорошо

"" "" Верно; Хорошо

"университет" "курс" Неверно; Хорошо

«лекция» «курс» Ложь; Хорошо

«точность» «точность» Неверно, ОК

Все это кажется очень многообещающим: возможно, программа действительно работает. Но более тщательное тестирование, скажем, «чистый» и «истинный» выявляет ошибочный вывод. Фактически, программа говорит «True», если строки имеют одинаковую длину и одинаковый последний символ!

Тем не менее, тестирование было довольно тщательным: у нас были строки разной длины, строки одинаковой длины, но разного содержимого и даже одинаковые строки. Кроме того, студент даже проверил и выполнил каждое отделение. Вы не можете утверждать, что тестирование здесь было небрежным - учитывая, что программа действительно очень проста, может быть трудно найти мотивацию и энергию для ее тщательного тестирования.


Еще один милый пример - бинарный поиск. В TAOCP Кнут говорит, что «хотя основная идея бинарного поиска сравнительно проста, детали могут быть на удивление хитрыми». По-видимому, ошибка в реализации Java для бинарного поиска оставалась незамеченной в течение десятилетия. Это была ошибка целочисленного переполнения, которая проявлялась только при достаточно большом входном сигнале. Сложные подробности реализации бинарного поиска также освещены Бентли в книге « Программирование жемчужин» .

Итог: может быть на удивление трудно убедиться, что алгоритм двоичного поиска верен, просто протестировав его.

Юхо
источник
9
Конечно, недостаток вполне очевиден из источника (если вы сами написали подобное ранее).
Рафаэль
3
Даже если простой недостаток в примере программы исправлен, строки создают немало интересных проблем! Перестановка строк - это классика, «основной» способ сделать это - просто поменять местами байты. Тогда кодирование вступает в игру. Затем суррогаты (обычно дважды). Проблема, конечно, в том, что нет простого способа формально доказать, что ваш метод верен.
Ордос
6
Может быть, я полностью неверно истолковал вопрос, но это, кажется, недостаток в реализации, а не недостаток в самом алгоритме .
Мистер Миндор
8
@ Mr.Mindor: как узнать, записал ли программист правильный алгоритм, а затем неправильно его реализовал, или записал неверный алгоритм, а затем верно его реализовал (стесняюсь сказать «правильно»!)
Стив Джессоп,
1
@wabbit Это спорно. То, что очевидно для вас, может не быть очевидным для первокурсника.
Юхо
30

Лучший пример, с которым я когда-либо сталкивался, - это тестирование простоты:

ввод: натуральное число p, p! = 2
Вывод: это главное или нет?
алгоритм: вычислить 2 ** (p-1) mod p. Если результат = 1, то p простое, иначе p нет.

Это работает (почти) для каждого числа, за исключением очень небольшого числа контрпримеров, и на самом деле нужен компьютер, чтобы найти контрпример в реалистичный период времени. Первый контрпример составляет 341, и плотность контрпримеров фактически уменьшается с увеличением p, хотя это примерно логарифмически.

Вместо того, чтобы просто использовать 2 в качестве основы степени, можно улучшить алгоритм, также используя дополнительные, увеличивая маленькие простые числа в качестве основы в случае, если предыдущее простое число вернуло 1. И все же, есть контрпример к этой схеме, а именно числа Кармайкла, довольно редко, хотя

Франки
источник
Тест на примитивность по Ферму является вероятностным, поэтому ваше пост-состояние неверно.
Femaref
5
Конечно, это вероятностный тест, но ответ хорошо показывает (в более общем плане), как вероятностные алгоритмы, ошибочно принятые за точные, могут быть источником ошибки. больше о числах Кармайкла
vzn
2
Это хороший пример с ограничением: для практического использования знакомого мне тестирования на простоту, а именно для генерации асимметричного криптографического ключа, мы используем вероятностные алгоритмы! Числа слишком велики для точных тестов (если бы их не было, они бы не подходили для криптографии, потому что ключи могли быть найдены с помощью грубой силы в реальном времени).
Жиль
1
ограничение, на которое вы ссылаетесь, является практическим, а не теоретическим, и основные тесты в криптосистемах, например, RSA , подвержены редким / крайне маловероятным сбоям именно по этим причинам, что еще раз подчеркивает важность примера. то есть на практике иногда это ограничение считается неизбежным. Есть алгоритмы времени P для тестирования простоты, например, AKS, но они занимают слишком много времени для «меньших» чисел, используемых на практике.
vzn
Если вы тестируете не только с 2 p, но с p для 50 различных случайных значений 2 ≤ a <p, то большинство людей узнает, что это вероятностный, но с ошибками настолько маловероятными, что более вероятно, что сбой в вашем компьютере приведет к неправильный ответ. При 2 p, 3 p, 5 p и 7 p сбои уже очень редки.
gnasher729
21

Вот тот, который был брошен на меня представителями Google на съезде, на котором я был. Он был написан на C, но работает на других языках, которые используют ссылки. Извините за то, что написал код на [cs.se], но это только для иллюстрации.

swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

Этот алгоритм будет работать для любых значений, заданных для x и y, даже если они имеют одинаковое значение. Однако он не будет работать, если он называется swap (x, x). В этой ситуации x заканчивается как 0. Теперь это может вас не устраивать, поскольку вы можете каким-то образом доказать, что эта операция математически корректна, но все же забыть об этом крайнем случае.

ZeroUltimax
источник
1
Этот трюк использовался в закулисном конкурсе C для создания ошибочной реализации RC4 . Читая эту статью еще раз, я только заметил, что этот хак, вероятно, был представлен @DW
CodesInChaos
7
Этот недостаток действительно неуловим - но, тем не менее, этот недостаток зависит от языка, так что в действительности это не недостаток в алгоритме; это недостаток в реализации. Можно придумать другие примеры странных языковых особенностей, которые позволяют легко скрыть тонкие недостатки, но это не совсем то, что я искал (я искал что-то на уровне абстракции алгоритмов). В любом случае, этот недостаток не идеальная демонстрация ценности доказательства; если вы уже не думаете о псевдонимах, вы можете не заметить ту же проблему, когда выписываете свое «доказательство» правильности.
DW
Вот почему я удивлен, что так высоко проголосовали.
ZeroUltimax
2
@DW Это вопрос того, в какой модели вы определяете алгоритм. Если вы переходите на уровень, где ссылки на память явные (а не общая модель, которая предполагает отсутствие совместного использования), это недостаток алгоритма. Недостаток в действительности не зависит от языка, он обнаруживается на любом языке, который поддерживает совместное использование ссылок на память.
Жиль
16

Существует целый класс алгоритмов, которые по своей природе сложно протестировать: генераторы псевдослучайных чисел . Вы не можете проверить один выход, но должны исследовать (много) ряды выходов с помощью статистики. В зависимости от того, что и как вы тестируете, вы можете пропустить неслучайные характеристики.

Один известный случай, когда все пошло не так, как надо - это RANDU . Он прошел проверку, доступную в то время - которая не учитывала поведение кортежей последующих выходных данных. Уже тройки показывают много структуры:

По сути, тесты не охватывали все варианты использования: хотя одномерное использование RANDU было (вероятно, в основном) нормальным, оно не поддерживало его использование для выборки трехмерных точек (таким образом).

Правильная псевдослучайная выборка - сложное дело. К счастью, в наши дни существуют мощные тестовые наборы, например dieharder, которые специализируются на выдаче всей известной нам статистики в предлагаемом генераторе. Это достаточно?

Если честно, я понятия не имею, что вы можете реально доказать для PRNG.

Рафаэль
источник
2
хороший пример, однако на самом деле вообще нет способа доказать, что у любого PRNG нет недостатка, есть только бесконечная иерархия слабых и сильных тестов. фактическое доказательство того, что он «случайный» в любом строгом смысле, предположительно неразрешимо (хотя это и не доказано).
vzn
1
Это хорошая идея чего-то, что сложно проверить, но ГСЧ также сложно доказать. PRNG не столько подвержен ошибкам реализации, сколько плохо задан. Такие тесты, как diehard, хороши для некоторых целей, но для crypto вы можете сдать diehard и все равно смеяться из комнаты. Не существует «проверенной безопасности» CSPRNG, лучшее, на что вы можете надеяться, это доказать, что если ваш CSPRNG сломан, то так же, как и AES.
Жиль
@ Жиль Я не пытался углубиться в криптографию, только в статистическую случайность (я думаю, что эти два имеют в значительной степени ортогональные требования). Должен ли я сделать это ясно в ответе?
Рафаэль
1
Крипто-случайность подразумевает статистическую случайность. Ни то, ни другое не имеет математически формального определения, хотя, насколько мне известно, кроме идеального (и противоречащего концепции PRNG, реализованной на детерминированной машине Тьюринга) понятия теоретико-информационной случайности. Имеет ли статистическая случайность формальное определение, выходящее за пределы «должны быть независимы от распределений, с которыми мы будем проверять»?
Жиль
1
@vzn: что значит быть случайной последовательностью чисел, можно определить многими возможными способами, но простой из них - «большая сложность Комолгорова». В этом случае легко показать, что определение случайности неразрешимо.
Коди
9

2D локальный максимум

n×nA

(i,j)A[i,j]

A[i,j+1],A[i,j1],A[i1,j],A[i+1,j]A

0134323125014013

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

O(n2)

AXXA(i,j)X(i,j)(i,j)

AXAX(i,j)A

AA

(i,j)AA(i,j)

n2×n2A(i,j)

T(n)n×nT(n)=T(n/2)+O(n)T(n)=O(n)

Таким образом, мы доказали следующую теорему:

O(n)n×n

Или мы?

Нил Янг
источник
T(n)=O(nlogn)T(n)=T(n/2)+O(n)
2
Это прекрасный пример! Я люблю это. Спасибо. (Я, наконец, понял недостаток в этом алгоритме. Из временных отметок вы можете получить нижнюю границу того, сколько времени мне понадобилось. Я слишком смущен, чтобы раскрывать фактическое время. :-)
DW
1
O(n)
8

Это примеры первичности, потому что они распространены.

(1) Первичность в SymPy. Выпуск 1789 . На известном веб-сайте был поставлен неверный тест, который не удался до 10 ^ 14. Хотя исправление было правильным, оно просто исправляло дыры, а не переосмысливало проблему.

(2) Первичность в Perl 6. Perl6 добавил is-prime, который использует ряд тестов MR с фиксированными основаниями. Существуют известные контрпримеры, но они довольно велики, поскольку количество тестов по умолчанию огромно (в основном скрывая реальную проблему, снижая производительность). Это будет решено в ближайшее время.

(3) Первичность в FLINT. n_isprime () возвращает true для композитов , поскольку исправлено. В основном та же проблема, что и SymPy. Используя базу данных Feitsma / Galway псевдопраймов SPRP-2 до 2 ^ 64, мы можем теперь проверить их.

(4) Математика Perl :: Первичность. is_aks_prime сломан . Эта последовательность, похоже, похожа на множество реализаций AKS - много кода, который либо работал случайно (например, потерян на шаге 1 и в итоге делал все это при пробном разделении), либо не работал для больших примеров. К сожалению, AKS настолько медленный, что его сложно проверить.

(5) Пари до 2.2 is_prime. Математика :: Пари билет . Он использовал 10 случайных баз для тестов MR (с фиксированным начальным числом при запуске, а не с фиксированным начальным значением GMP при каждом вызове). Он скажет вам, что 9 простое число примерно 1 из каждых 1M звонков. Если вы выберете правильное число, вы можете заставить его ошибаться относительно часто, но числа становятся более разреженными, поэтому на практике это не так уж много. С тех пор они изменили алгоритм и API.

Это не так, но это классика вероятностных тестов: сколько раундов вы даете, скажем, mpz_probab_prime_p? Если мы дадим ему 5 раундов, то это, похоже, будет работать хорошо - числа должны пройти тест Ферма с базой 210, а затем 5 предварительно выбранных тестов Миллера-Рабина. Вы не найдете контрпример до 3892757297131 (с GMP 5.0.1 или 6.0.0a), поэтому вам придется много тестировать, чтобы найти его. Но есть тысячи контрпримеров под 2 ^ 64. Таким образом, вы продолжаете поднимать число. Как далеко? Есть ли противник? Насколько важен правильный ответ? Вы путаете случайные базы с фиксированными? Знаете ли вы, какие входные размеры вам дадут?

1016

Это довольно сложно проверить правильно. Моя стратегия включает в себя очевидные модульные тесты, плюс крайние случаи, а также примеры сбоев, замеченных ранее или в других пакетах, тестирование по сравнению с известными базами данных, где это возможно (например, если вы делаете один тест MR с базовым уровнем 2, то вы уменьшаете невозможность вычисления). задача проверки 2 ^ 64 чисел (около 32 миллионов чисел) и, наконец, множество рандомизированных тестов, использующих другой пакет в качестве стандарта. Последний пункт работает для таких функций, как первичность, где есть довольно простой ввод и известный вывод, но довольно много задач, как это. Я использовал это, чтобы найти дефекты как в моем собственном коде разработки, так и случайные проблемы в пакетах сравнения. Но учитывая бесконечное пространство ввода, мы не можем проверить все.

Что касается доказательства правильности, вот еще один пример первичности. Методы BLS75 и ECPP имеют концепцию сертификата первичности. По сути, после того, как они работают в поисках значений, которые подходят для их доказательств, они могут выводить их в известном формате. Затем можно написать верификатор или попросить кого-нибудь написать его. Они выполняются очень быстро по сравнению с созданием, и теперь либо (1) оба фрагмента кода неверны (следовательно, почему вы бы предпочли других программистов для верификаторов), либо (2) неверна математика, лежащая в основе идеи доказательства. # 2 всегда возможен, но они, как правило, публикуются и проверяются несколькими людьми (и в некоторых случаях вам достаточно легко пройти через себя).

Для сравнения, такие методы, как AKS, APR-CL, пробное деление или детерминистический тест Рабина, не дают ничего, кроме «простого» или «составного». В последнем случае у нас может быть фактор, следовательно, мы можем проверить, но в первом случае у нас не осталось ничего, кроме этого одного бита вывода. Программа работала правильно? Не знаю.

Важно протестировать программное обеспечение не только на нескольких игрушечных примерах, а также на нескольких примерах на каждом шаге алгоритма и сказать: «Учитывая этот вход, имеет ли смысл, что я нахожусь здесь с этим состоянием?»

DanaJ
источник
1
Многие из них выглядят как (1) ошибки реализации (лежащий в основе алгоритм верен, но он не был реализован правильно), что интересно, но не в этом вопросе, или (2) осознанный, осознанный выбор, чтобы выбрать что-то, что быстрый и в основном работает, но может с ошибкой работать с очень малой вероятностью (для кода, который тестирует с одной случайной базой или несколькими фиксированными / случайными базами, я надеюсь, что тот, кто выберет это, знает, что делает компромисс производительности).
DW
Вы правы в первом пункте - правильный алгоритм + ошибка - не главное, хотя обсуждение и другие примеры также объединяют их. Поле полно догадок, которые работают для небольших чисел, но неверны. Для пункта (2) это верно для некоторых, но мои примеры № 1 и № 3 не были этим случаем - считалось, что алгоритм был верным (эти 5 базисов дают доказанные результаты для чисел до 10 ^ 16), затем позже обнаружил, что это не так.
DanaJ
Разве это не фундаментальная проблема с тестами на псевдопримарность?
asmeurer
asmeurer, да в моем # 2 и последующем обсуждении их. Но № 1 и № 3 были оба случая использования Миллера-Рабина с известными основаниями, чтобы дать детерминированные правильные результаты ниже порога. Таким образом, в этом случае «алгоритм» (использующий термин «свободно» для соответствия ОП) был неверным. # 4 не является вероятным простым тестом, но, как указал DW, алгоритм работает нормально, сложная реализация. Я включил его, потому что это приводит к сходной ситуации: необходимо тестирование, и как далеко вы выходите за рамки простых примеров, прежде чем сказать, что оно работает?
DanaJ
Некоторые из ваших постов, кажется, соответствуют этому вопросу, а некоторые нет (комментарий cf @ DW). Пожалуйста, удалите примеры (и другой контент), который не отвечает на вопрос.
Рафаэль
7

Алгоритм перетасовки Фишера-Йейтса-Кнута является (практическим) примером, который прокомментировал один из авторов этого сайта .

Алгоритм генерирует случайную перестановку заданного массива в виде:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

ij0ji

«Наивный» алгоритм может быть:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

Где в цикле заменяемый элемент выбирается из всех доступных элементов. Однако это приводит к смещенной выборке перестановок (некоторые перепредставлены и т. Д.)

На самом деле можно придумать перетасовку Фишера-Йейтса-Кнута, используя простой (или наивный) счетный анализ .

nn!=n×n1×n2..nn1

Основная проблема с проверкой правильности алгоритма тасования ( смещения или нет ) состоит в том, что из-за статистики требуется большое количество выборок. В статье codinghorror, на которую я ссылаюсь выше, объясняется именно это (и с реальными тестами).

Никос М.
источник
1
Смотрите здесь пример доказательства корректности для алгоритма тасования.
Рафаэль
5

Лучший пример (читай: что мне больше всего неприятно ), который я когда-либо видел, имеет отношение к гипотезе Коллатца, Я участвовал в соревновании по программированию (с призом в 500 долларов на линии за первое место), в котором одной из проблем было найти минимальное количество шагов, необходимых для того, чтобы два числа достигли одного и того же числа. Решение, конечно, состоит в том, чтобы поочередно шагать каждый, пока они оба не достигнут чего-то, что было замечено ранее. Нам дали диапазон чисел (я думаю, что это было между 1 и 1000000) и сказали, что гипотеза Коллатца была проверена до 2 ^ 64, так что все числа, которые нам дали, в конечном итоге сходятся на 1. Я использовал 32-битный целые числа, чтобы сделать шаги с однако. Оказывается, что существует одно неясное число от 1 до 1000000 (что-то 170 тысяч), которое в свое время приведет к переполнению 32-разрядного целого числа. На самом деле эти цифры чрезвычайно редки ниже 2 ^ 31. Мы проверили нашу систему на ОГРОМНЫЕ числа, намного превышающие 1000000, чтобы «убедиться», что переполнения не произошло. Получается, что гораздо меньшее число, которое мы просто не тестировали, вызывало переполнение. Поскольку я использовал «int» вместо «long», я получил только приз в 300 долларов, а не приз в 500 долларов.

Джейк
источник
5

Проблема рюкзака 0/1 - это проблема, которую почти все студенты считают разрешимой с помощью жадного алгоритма. Это случается чаще, если вы ранее показывали некоторые жадные решения в качестве версии проблемы рюкзака, где работает жадный алгоритм .

Для этих задач в классе я должен показать доказательство для рюкзака 0/1 ( динамическое программирование ) для устранения любых сомнений и для жадной версии задачи. На самом деле, оба доказательства не тривиальны, и студенты, вероятно, считают их очень полезными. Кроме того, есть комментарий по этому поводу в CLRS 3ed , глава 16, стр. 425-427 .

Проблема: вор грабит магазин и может нести максимальный вес W в свой рюкзак. Есть n предметов, и каждый из них весит wi и стоит vi долларов. Какие вещи должен взять вор? максимизировать свою выгоду ?

Проблема ранца 0/1 : установка такая же, но предметы не могут быть разбиты на более мелкие части , поэтому вор может решить либо взять предмет, либо оставить его (двоичный выбор), но не может взять часть предмета ,

И вы можете получить от студентов некоторые идеи или алгоритмы, которые следуют той же идее, что и проблема жадных версий, а именно:

  • Возьмите общую вместимость пакета и поместите как можно больше самого ценного объекта, и повторяйте этот метод, пока вы не можете положить больше объекта, потому что мешок заполнен или нет объекта с меньшим или равным весом для помещения в мешок.
  • Другой неправильный способ мышления: ставьте более легкие предметы и ставьте следующие ниже наименьшей цены.
  • ...

Это полезно для вас? на самом деле, мы знаем, что проблема с монетами - это проблема с рюкзаком. Но в лесу проблем с рюкзаком есть и другие примеры, например, как насчет рюкзака 2D (это действительно полезно, когда вы хотите резать древесину для изготовления мебели , я видел это в местном городе из моего города), очень часто думают, что жадные работы здесь тоже, но нет.

jonaprieto
источник
Жадность уже была рассмотрена в принятом ответе , но проблема рюкзака, в частности, хорошо подходит для того, чтобы установить ловушки.
Рафаэль
3

Распространенной ошибкой является неправильная реализация алгоритмов тасования. Смотрите обсуждение в Википедии .

n!nn(n1)n

Пер Александерссон
источник
1
Это хороший баг, но не хорошая иллюстрация дурачения эвристики тестовых случаев, поскольку тестирование на самом деле не относится к алгоритмам тасования (оно рандомизировано, так как бы вы его протестировали? Что бы означало провал тестового примера, и Как бы вы обнаружили это, глядя на вывод?)
DW
Вы проверяете это статистически конечно. Равномерная случайность далека от «что-либо может произойти на выходе». Не будете ли вы с подозрением относиться к тому, что программа, имитирующая игру в кости, даст вам 100 3 подряд?
За Александерссон
Опять же, я говорю о студенческой эвристике «попробуй несколько тестов вручную». Я видел, что многие студенты думают, что это разумный способ проверить правильность детерминированного алгоритма, но я подозреваю, что они не будут предполагать, что это хороший способ проверить правильность алгоритма тасования (поскольку алгоритм тасования рандомизирован, есть нет никакого способа определить, является ли какой-то конкретный вывод правильным, в любом случае, вы не можете вручную набрать достаточное количество примеров, чтобы выполнить какой-либо полезный статистический тест). Так что я не ожидаю, что алгоритмы тасования сильно помогут разобраться в распространенном заблуждении.
DW
1
@PerAlexandersson: Даже если вы генерируете только один случайный случай, он не может быть действительно случайным при использовании MT с n> 2080. Теперь отклонение от ожидаемого будет очень небольшим, так что вам, вероятно, будет все равно ... но это применимо, даже если вы генерируете намного меньше, чем период (как указано выше asmeurer).
Чарльз
2
Этот ответ, похоже, устарел из- за более сложного ответа Никоса М. ?
Рафаэль
2

Питоны PEP450, которые ввели статистические функции в стандартную библиотеку, могут представлять интерес. В качестве оправдания наличия функции, которая вычисляет дисперсию в стандартной библиотеке python, автор Стивен Д'Апрано пишет:

def variance(data):
        # Use the Computational Formula for Variance.
        n = len(data)
        ss = sum(x**2 for x in data) - (sum(data)**2)/n
        return ss/(n-1)

Вышеупомянутое представляется правильным для случайного теста:

>>> data = [1, 2, 4, 5, 8]
>>> variance(data)
  7.5

Но добавление константы к каждой точке данных не должно изменять дисперсию:

>>> data = [x+1e12 for x in data]
>>> variance(data)
  0.0

И дисперсия никогда не должна быть отрицательной:

>>> variance(data*100)
  -1239429440.1282566

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

Кристиан
источник
1
n1
2
@Raphael: Хотя, честно говоря, выбранный алгоритм, как известно, является плохим выбором для данных с плавающей запятой.
2
Речь идет не просто о реализации операции, о числах и о том, как теряется точность. Если вам нужна максимальная точность, вам нужно определенным образом упорядочить свои операции. Это было одной из проблем, о которых говорил мой числовой курс в университете.
Кристиан
В дополнение к точному комментарию Рафаэля, недостатком этого примера является то, что я не думаю, что доказательство правильности поможет избежать этого недостатка. Если вы не знаете тонкостей арифметики с плавающей точкой, вы можете подумать, что доказали это правильно (доказав, что формула верна). Так что это не идеальный пример для обучения студентов, почему важно доказать правильность их алгоритмов. Если бы студенты увидели этот пример, я подозреваю, что вместо этого они извлекут урок «вычисления с плавающей запятой / числовые вычисления сложны».
DW
1

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

nn2+n+410<dd divides n2+n+41d<n2+n+41

Предлагаемое решение :

int f(int n) {
   return 1;
}

n=0,1,2,,39n=40

Этот подход «попробуйте несколько небольших случаев и выведите алгоритм из результата» часто встречается (хотя и не так сильно, как здесь) в соревнованиях по программированию, где нужно придумать алгоритм, который (а) можно быстро реализовать и (б) ) имеет быстрое время выполнения.

Рик Декер
источник
5
Я не думаю, что это очень хороший пример, потому что мало кто попытается найти делители многочлена, возвращая 1.
Брайан С.
1
nn3n
Это может иметь значение в том смысле, что возвращение постоянного значения для делителей (или другого вычисления) может быть результатом неправильного алгоритмического подхода к проблеме (например, статистической проблемы или отсутствия обработки краевых случаев алгоритма). Однако ответ нуждается в перефразировке
Никос М.
@NikosM. Хех. Я чувствую, что я бью здесь мертвую лошадь, но второй абзац вопроса говорит, что «если их алгоритм работает правильно на нескольких примерах, включая все угловые случаи, которые они могут попробовать, то они заключают, что алгоритм должен быть правильным. Всегда есть студент, который спрашивает: «Почему мне нужно доказать, что мой алгоритм корректен, если я могу просто попробовать его на нескольких тестовых примерах?» В этом случае, для первых 40 значений (гораздо больше, чем студент вероятно, попытается), возвращая 1 - это правильно. Мне кажется, что это именно то, что искал ОП
Рик Декер
Хорошо, да, но это, как говорится, тривиально (может быть, как правило, правильно), но не в духе вопроса. Все еще нужно перефразировать
Никос М.