Como enganar a heurística “experimente alguns casos de teste”: algoritmos que parecem corretos, mas na verdade estão incorretos

Para tentar testar se um algoritmo para algum problema está correto, o ponto de partida usual é tentar executar o algoritmo manualmente em vários casos de teste simples - tente em alguns exemplos de instâncias de problemas, incluindo alguns casos de canto "simples" " Essa é uma ótima heurística: é uma ótima maneira de eliminar rapidamente muitas tentativas incorretas de um algoritmo e entender melhor por que o algoritmo não funciona.

No entanto, ao aprender algoritmos, alguns alunos ficam tentados a parar por aí: se seu algoritmo funciona corretamente em alguns exemplos, incluindo todos os casos de canto que eles podem pensar em tentar, então concluem que o algoritmo deve estar correto. Sempre há um aluno que pergunta: "Por que preciso provar meu algoritmo correto, se posso experimentá-lo em alguns casos de teste?"

Então, como você engana a heurística "experimente vários casos de teste"? Estou procurando alguns bons exemplos para mostrar que essa heurística não é suficiente. Em outras palavras, estou procurando um ou mais exemplos de um algoritmo que superficialmente pareça estar correto, e que dê a resposta certa em todas as pequenas entradas que qualquer pessoa provavelmente encontrará, mas onde o algoritmo realmente não funciona Talvez o algoritmo funcione corretamente em todas as entradas pequenas e falhe apenas para entradas grandes ou apenas para entradas com um padrão incomum.

Especificamente, estou procurando:

1. Um algoritmo A falha deve estar no nível algorítmico. Não estou procurando por erros de implementação. (Por exemplo, no mínimo, o exemplo deve ser independente da linguagem e a falha deve estar relacionada a preocupações algorítmicas, em vez de questões de engenharia ou implementação de software.)

2. Um algoritmo que alguém pode apresentar de maneira plausível. O pseudocódigo deve parecer pelo menos plausivelmente correto (por exemplo, código ofuscado ou obviamente dúbio não é um bom exemplo). Pontos de bônus se for um algoritmo que algum aluno realmente apresentou ao tentar resolver um problema de lição de casa ou de exame.

3. Um algoritmo que passaria em uma estratégia razoável de teste manual com alta probabilidade. É improvável que alguém que tente manualmente alguns pequenos casos de teste descubra a falha. Por exemplo, "simular o QuickCheck manualmente em uma dúzia de pequenos casos de teste" não deve revelar que o algoritmo está incorreto.

4. De preferência, um algoritmo determinístico. Já vi muitos estudantes pensarem que "experimentar alguns casos de teste manualmente" é uma maneira razoável de verificar se um algoritmo determinístico está correto, mas suspeito que muitos estudantes não considerariam que tentar alguns casos de teste é uma boa maneira de verificar probabilística. algoritmos. Para algoritmos probabilísticos, geralmente não há como saber se alguma saída específica está correta; e você não pode manobrar com exemplos suficientes para fazer qualquer teste estatístico útil na distribuição de saída. Portanto, eu preferiria me concentrar em algoritmos determinísticos, pois eles chegam mais claramente ao coração dos conceitos errados dos alunos.

Gostaria de ensinar a importância de provar seu algoritmo correto, e espero usar alguns exemplos como esse para ajudar a motivar provas de correção. Eu preferiria exemplos que sejam relativamente simples e acessíveis aos estudantes de graduação; exemplos que exigem maquinaria pesada ou uma tonelada de conhecimentos matemáticos / algorítmicos são menos úteis. Além disso, não quero algoritmos "não naturais"; embora possa ser fácil construir algum algoritmo artificial estranho para enganar a heurística, se parecer altamente artificial ou se houver um backdoor óbvio construído apenas para enganar essa heurística, provavelmente não será convincente para os alunos. Algum bom exemplo?

Acho que um erro comum é usar algoritmos gananciosos, que nem sempre são a abordagem correta, mas podem funcionar na maioria dos casos de teste.

Exemplo: denominações de moedas, e um número , expressam como uma soma de : s com o mínimo de moedas possível. n n d $d_1,\dots,d_k$$n$$n$$d_i$

Uma abordagem ingênua é usar primeiro a maior moeda possível e produzir avidamente essa soma.

Por exemplo, as moedas com os valores , e fornecerão respostas corretas com ganância para todos os números entre e exceto para o número .5 1 1 14 10 = 6 + 1 + 1 + 1 + 1 = 5 + $6$$5$$1$$1$$14$$10 = 6+1+1+1+1 = 5+5$

Lembrei-me imediatamente de um exemplo de R. Backhouse (isso poderia estar em um de seus livros). Aparentemente, ele havia designado uma tarefa de programação em que os alunos tinham que escrever um programa em Pascal para testar a igualdade de duas seqüências. Um dos programas apresentados por um aluno foi o seguinte:

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

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

write(issame);

Agora podemos testar o programa com as seguintes entradas:

"universidade" "universidade" True; Está bem$\Rightarrow$

"curso" "curso" True; Está bem$\Rightarrow$

"" "" True; Está bem$\Rightarrow$

"universidade" "curso" False; Está bem$\Rightarrow$

"palestra" "curso" False; Está bem$\Rightarrow$

"precisão" "exatidão" False, OK$\Rightarrow$

Tudo isso parece muito promissor: talvez o programa realmente funcione. Mas um teste mais cuidadoso com dizer "puro" e "verdadeiro" revela resultados defeituosos. De fato, o programa diz "Verdadeiro" se as seqüências tiverem o mesmo comprimento e o mesmo último caractere!

No entanto, o teste foi bastante completo: tínhamos seqüências de caracteres de comprimento diferente, seqüências de comprimento igual, mas com conteúdo diferente e até seqüências de caracteres iguais. Além disso, o aluno havia testado e executado cada ramo. Você realmente não pode argumentar que o teste foi descuidado aqui - dado que o programa é realmente muito simples, pode ser difícil encontrar motivação e energia para testá-lo completamente o suficiente.

Outro exemplo bonito é a pesquisa binária. No TAOCP, Knuth diz que "embora a idéia básica da pesquisa binária seja comparativamente direta, os detalhes podem ser surpreendentemente complicados". Aparentemente, um bug na implementação de pesquisa binária do Java passou despercebido por uma década. Foi um erro de excesso de número inteiro, e só se manifestou com entrada grande o suficiente. Detalhes complicados das implementações de pesquisa binária também são abordados por Bentley no livro Programming Pearls .

Conclusão: pode ser surpreendentemente difícil garantir que um algoritmo de pesquisa binária esteja correto apenas testando-o.

O melhor exemplo que me deparei é o teste de primalidade:

input: número natural p, p! = 2
saída: pa prime ou não?
algoritmo: calcular 2 ** (p-1) mod p. Se resultado = 1, então p é primo, caso contrário, p não é.

Isso funciona para (quase) todos os números, exceto por alguns poucos exemplos de contadores, e na verdade é necessário que uma máquina encontre um contra-exemplo em um período realista de tempo. O primeiro contra-exemplo é 341, e a densidade dos contra-exemplos realmente diminui com o aumento de p, embora quase logaritmicamente.

Em vez de usar apenas 2 como base da potência, pode-se melhorar o algoritmo usando também primos pequenos adicionais adicionais, como base, caso o primo anterior retorne 1. E, ainda assim, há contraexemplo para esse esquema, ou seja, os números de Carmichael, muito raro embora

Aqui está um que foi jogado para mim pelos representantes do Google em uma convenção em que fui. Foi codificado em C, mas funciona em outros idiomas que usam referências. Desculpe por ter que codificar em [cs.se], mas é o único a ilustrá-lo.

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

Este algoritmo funcionará para quaisquer valores dados para x e y, mesmo que tenham o mesmo valor. No entanto, não funcionará se for chamado como swap (x, x). Nessa situação, x termina como 0. Agora, isso pode não satisfazê-lo, pois você pode provar que esta operação está matematicamente correta, mas ainda assim esquece esse caso extremo.

Existe toda uma classe de algoritmos que é inerentemente difícil de testar: geradores de números pseudo-aleatórios . Você não pode testar uma única saída, mas precisa investigar (muitas) séries de saídas com meios estatísticos. Dependendo do que e como você testar, você poderá perder características não aleatórias.

Um caso famoso em que as coisas deram terrivelmente errado é RANDU . Ele passou no exame disponível na época - que não considerou o comportamento das tuplas das saídas subsequentes. Já os triplos mostram muita estrutura:

Basicamente, os testes não cobriram todos os casos de uso: embora o uso unidimensional do RANDU fosse (provavelmente a maioria) bom, ele não suportava o uso para amostrar pontos tridimensionais (dessa maneira).

A amostragem pseudo-aleatória adequada é um negócio complicado. Felizmente, existem suítes de testes poderosas nos dias de hoje, por exemplo, um dieharder especializado em lançar todas as estatísticas que conhecemos em um gerador proposto. É o suficiente?

^{Para ser justo, não tenho ideia do que você pode provar para os PRNGs.}

Máximo local 2D

entrada: bidimensional matriz$n \times n$$A$

saída: um máximo local - um par modo que não tenha célula vizinha na matriz que contenha um valor estritamente maior. $(i,j)$$A[i,j]$

(As células vizinhas são aquelas entre que estão presentes na matriz.) Então, por exemplo, se é$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$$A$

então cada célula em negrito é um máximo local. Toda matriz não vazia possui pelo menos um máximo local.

Algoritmo. Existe um algoritmo de tempo : basta verificar cada célula. Aqui está uma idéia para um algoritmo recursivo mais rápido.$O(n^2)$

Dado , defina a cruz para consistir nas células da coluna do meio e nas células da linha do meio. Primeiro verifique cada célula para ver se a célula é um máximo local em . Nesse caso, retorne uma célula. Caso contrário, seja uma célula em com o valor máximo. Como não é um máximo local, ele deve ter uma célula vizinha com maior valor.$A$$X$$X$$A$$(i, j)$$X$$(i, j)$$(i', j')$

Particione (a matriz , menos as células em ) em quatro quadrantes - os quadrantes superior esquerdo, superior direito, inferior esquerdo e inferior direito - da maneira natural. A célula vizinha com maior valor deve estar em um desses quadrantes. Chame esse quadrante de . $A \setminus X$$A$$X$$(i', j')$$A'$

Lema. Quadrant contém um máximo local de .$A'$$A$

Prova. Considere começar na célula . Se não for um máximo local, vá para um vizinho com um valor maior. Isso pode ser repetido até chegar a uma célula que seja um máximo local. Essa célula final deve estar em , porque é delimitada por todos os lados por células cujos valores são menores que o valor da célula . Isso prova o lema. $(i', j')$$A'$$A'$$(i', j')$$\diamond$

O algoritmo chama a si próprio recursivamente na sub-matriz para encontrar um máximo local lá e depois retorna a célula.$\frac{n}{2}\times\frac{n}{2}$$A'$$(i, j)$

O tempo de execução para uma matriz satisfaz , então . $T(n)$$n\times n$$T(n) = T(n/2) + O(n)$$T(n) = O(n)$

Assim, provamos o seguinte teorema:

Teorema. Existe um algoritmo de tempo para encontrar um máximo local em uma matriz .$O(n)$$n\times n$

Ou nós?

Estes são exemplos de primalidade, porque são comuns.

(1) Primalidade no SymPy. Edição 1789 . Houve um teste incorreto em um site conhecido que só falhou após 10 ^ 14. Enquanto a correção estava correta, era apenas corrigir os buracos em vez de repensar o problema.

(2) Primality em Perl 6. O Perl6 adicionou o is-prime, que usa vários testes de RM com bases fixas. Existem contra-exemplos conhecidos, mas são bastante grandes, já que o número padrão de testes é enorme (basicamente ocultando o problema real por degradação do desempenho). Isso será tratado em breve.

(3) Primalidade em FLINT. n_isprime () retornando true para composites , desde que corrigido. Basicamente, o mesmo problema que o SymPy. Usando o banco de dados Feitsma / Galway de pseudoprimes SPRP-2 para 2 ^ 64, podemos agora testá-los.

(4) Matemática de Perl: primazia. is_aks_prime quebrado . Essa sequência parece semelhante a muitas implementações do AKS - muitos códigos que funcionaram por acidente (por exemplo, se perderam na etapa 1 e acabaram fazendo a coisa toda por divisão de teste) ou não funcionaram para exemplos maiores. Infelizmente, o AKS é tão lento que é difícil testar.

(5) O pari anterior ao 2.2 é_prime. Bilhete Math :: Pari . Utilizou 10 bases aleatórias para testes de RM (com semente fixa na inicialização, em vez de semente fixa do GMP a cada chamada). Ele informará que 9 é o principal cerca de 1 em cada 1 milhão de chamadas. Se você escolher o número certo, poderá falhar com relativa frequência, mas os números se tornarão mais esparsos, de modo que não aparecerá muito na prática. Desde então, eles mudaram o algoritmo e a API.

Isso não está errado, mas é um clássico dos testes probabilísticos: quantas rodadas você dá, digamos, mpz_probab_prime_p? Se dermos 5 rodadas, com certeza parece que funciona bem - os números precisam passar no teste Fermat de base 210 e depois em 5 testes Miller-Rabin de bases pré-selecionadas. Você não encontrará um contra-exemplo até 3892757297131 (com GMP 5.0.1 ou 6.0.0a); portanto, você precisará fazer muitos testes para encontrá-lo. Mas existem milhares de contra-exemplos abaixo de 2 ^ 64. Então você continua aumentando o número. Quão longe? Existe um adversário? Quão importante é uma resposta correta? Você está confundindo bases aleatórias com bases fixas? Você sabe quais tamanhos de entrada serão fornecidos?

Há um ponto relacionado: o que é um grande número? Para os estudantes, parece que muitos pensam que 10.000 é um número enorme . Para muitos programadores, é um número grande. Para os programadores que trabalham com criptografia, estes são pequenos e grandes, digamos, 4096 bits. Para os programadores que trabalham com a teoria dos números computacionais, todos são pequenos e grandes podem ter entre 10 e 100 mil dígitos decimais. Para alguns matemáticos, tudo isso pode ser considerado "não grande", considerando que há muito mais números positivos maiores que esses exemplos do que pequenos. Isso é algo em que muitas pessoas não pensam, mas faz a diferença ao pensar em correção e desempenho.$10^{16}$

Estes são bastante difíceis de testar corretamente. Minha estratégia inclui testes de unidade óbvios, além de casos extremos, mais exemplos de falhas vistas antes ou em outros pacotes, bancos de dados versus bancos de dados conhecidos sempre que possível (por exemplo, se você faz um único teste de RM de base 2, reduziu a inviabilidade computacionalmente inviável) tarefa de testar 2 ^ 64 números para testar cerca de 32 milhões) e, finalmente, muitos testes randomizados usando outro pacote como padrão. O último ponto funciona para funções como primalidade, onde há uma entrada bastante simples e uma saída conhecida, mas algumas tarefas são assim. Eu usei isso para encontrar defeitos tanto no meu próprio código de desenvolvimento quanto em problemas ocasionais nos pacotes de comparação. Mas, dado o espaço infinito de entrada, não podemos testar tudo.

Quanto à comprovação da correção, aqui está outro exemplo de primalidade. Os métodos BLS75 e ECPP têm o conceito de certificado de primalidade. Basicamente, depois que eles fazem buscas para encontrar valores que funcionem para suas provas, eles podem produzi-los em um formato conhecido. Pode-se então escrever um verificador ou pedir que alguém o escreva. Eles são executados muito rapidamente em comparação com a criação e agora (1) os dois pedaços de código estão incorretos (por isso, você prefere outros programadores para os verificadores) ou (2) a matemática por trás da ideia de prova está errada. O número 2 é sempre possível, mas estes geralmente foram publicados e revisados ​​por várias pessoas (e, em alguns casos, são fáceis o suficiente para você se orientar).

Em comparação, métodos como AKS, APR-CL, divisão de teste ou o teste determinístico de Rabin, todos produzem outra saída que não seja "primordial" ou "composta". No último caso, podemos ter um fator, portanto, podemos verificar, mas no primeiro caso, ficamos com nada além desse bit de saída. O programa funcionou corretamente? Não sei.

É importante testar o software em mais do que apenas alguns exemplos de brinquedos, além de passar por alguns exemplos em cada etapa do algoritmo e dizer "dada essa entrada, faz sentido que eu esteja aqui com esse estado?"

O algoritmo de embaralhamento de Fisher-Yates-Knuth é um exemplo (prático) e sobre o qual um dos autores deste site comentou .

O algoritmo gera uma permutação aleatória de um determinado array como:

 // 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]

Vê-se que no circuito os elementos são trocados entre e , . Isso produz uma amostragem imparcial das permutações (nenhuma permutação é super-representada e outras sub-representada).j 0 ≤ j ≤ $i$$j$$0 \le j \le i$

Um algoritmo "ingênuo" pode ser:

 // 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]

Onde no loop o elemento a ser trocado é escolhido entre todos os elementos disponíveis. No entanto, isso produz amostragem tendenciosa das permutações (algumas são super-representadas etc.)

Na verdade, pode-se apresentar o embaralhamento de Fisher-Yates-Knuth usando uma análise simples (ou ingênua) de contagem .

O número de permutações de elementos é , o que significa que o primeiro elemento pode ser colocado em qualquer uma das posições, o segundo elemento nas posições restantes e assim por diante. por que ele produz permutações não-tendenciosas (aleatórias) (ao contrário do algoritmo "ingênuo")n ! = n × n - 1 × n - 2 . . n n - $n$$n! = n \times n-1 \times n-2 ..$$n$$n-1$

O principal problema para verificar se o algoritmo de reprodução aleatória está correto ou não ( tendencioso ou não ) é que, devido às estatísticas, é necessário um grande número de amostras. O artigo de codinghorror que eu ligo acima explica exatamente isso (e com testes reais).

O melhor exemplo (leia-se: o que mais me machuca) que eu já vi tem a ver com conjecturas de collatz. Eu estava em uma competição de programação (com um prêmio de 500 dólares em jogo pelo primeiro lugar) em que um dos problemas era encontrar o número mínimo de etapas necessárias para dois números alcançarem o mesmo número. A solução, é claro, é alternar cada uma delas até que ambas alcancem algo que já foi visto antes. Foi-nos dado um intervalo de números (acho que era entre 1 e 1000000) e disseram-nos que a conjectura de collatz tinha sido verificada até 2 ^ 64, para que todos os números que nos foram dados eventualmente convergissem para 1. Eu usei 32 bits números inteiros para executar as etapas no entanto. Acontece que existe um número obscuro entre 1 e 1000000 (170 mil algo) que fará com que um número inteiro de 32 bits seja excedido no devido tempo. De fato, esses números são extremamente raros abaixo de 2 ^ 31. Testamos nosso sistema em busca de números ENORMES muito maiores que 1000000 para "garantir" que o estouro não estava ocorrendo. Acontece que um número muito menor que simplesmente não testamos causou estouro. Como usei "int" em vez de "long", recebi apenas um prêmio de 300 dólares, em vez de um prêmio de $ 500.

O problema da mochila 0/1 é aquele que quase todos os alunos pensam ser solucionável por um algoritmo ganancioso. Isso acontece com mais frequência se você mostrar anteriormente algumas soluções gananciosas como a versão do problema do Knapsack, onde um algoritmo ganancioso funciona .

Para esses problemas, em sala de aula , devo mostrar a prova do Knapsack 0/1 ( programação dinâmica ) para remover qualquer dúvida e também para a versão do problema ganancioso. Na verdade, ambas as provas não são triviais e os alunos provavelmente as acham muito úteis. Além disso, há um comentário sobre isso no CLRS 3ed , capítulo 16, página 425-427 .

Problema: ladrão roubando uma loja e pode carregar um peso máximo de W na mochila. Existem n itens e o i-ésimo item pesam wi e vale vi dólares. Quais itens o ladrão deve levar? maximizar seu ganho ?

Problema na mochila 0/1 : A configuração é a mesma, mas os itens não podem ser divididos em pedaços menores , portanto, o ladrão pode decidir pegar um item ou deixá-lo (opção binária), mas não pode levar uma fração de um item .

E você pode obter dos alunos algumas idéias ou algoritmos que seguem a mesma idéia que o problema da versão gananciosa, que é:

• Pegue a capacidade total da bolsa e coloque o máximo possível de objetos, e itere esse método até que você não possa colocar mais objetos porque a bolsa está cheia ou não há objetos com peso igual ou menor para colocar dentro da bolsa.
• Outra maneira errada é pensar: coloque itens mais leves e coloque-os do preço mais alto ao mais baixo.
• ...

Isso é útil para você? na verdade, sabemos que o problema da moeda é uma versão do problema da mochila. Mas, existem mais exemplos na floresta dos problemas da mochila, por exemplo, o que diz respeito à mochila 2D (isso é realmente útil quando você deseja cortar madeira para fazer móveis , vi em um local da minha cidade), é muito comum pensar que o ganancioso trabalha aqui também, mas não.

Um erro comum é implementar algoritmos de embaralhamento incorretos. Veja a discussão na wikipedia .

O problema é que o viés geralmente não é fácil de detectar, e é preciso provar que realmente existem"escolhas" feitas pelo algoritmo, e não ou que são comuns para implementações erradas.n n ( n - 1 ) $n!$$n^n$$(n-1)^n$

Os Pythons PEP450 que introduziram funções estatísticas na biblioteca padrão podem ser interessantes. Como parte da justificativa para ter uma função que calcula a variação na biblioteca padrão de python, o autor Steven D'Aprano escreve:

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)

O exposto acima parece estar correto com um teste casual:

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

Mas adicionar uma constante a cada ponto de dados não deve alterar a variação:

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

E a variação nunca deve ser negativa:

>>> variance(data*100)
  -1239429440.1282566

A questão é sobre números e como a precisão é perdida. Se você deseja a máxima precisão, deve ordenar suas operações de uma certa maneira. Uma implementação ingênua leva a resultados incorretos porque a imprecisão é muito grande. Esse foi um dos assuntos sobre o qual meu curso numérico na universidade era.

Embora provavelmente não seja exatamente isso que você procura, é certamente fácil entender e testar alguns casos pequenos sem qualquer outro pensamento que levem a um algoritmo incorreto.

$n$$n^2+n+41$$0<d$$d\text{ divides } n^2+n+41$$d < n^2+n+41$

Solução proposta :

int f(int n) {
   return 1;
}

$n= 0, 1, 2, \dotsc, 39$$n=40$

Essa abordagem "tente alguns casos pequenos e deduza um algoritmo a partir do resultado" surge com frequência (embora não tão extremamente quanto aqui) em competições de programação em que a pressão é de um algoritmo que (a) seja rápido de implementar e (b) ) tem um tempo de execução rápido.