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

105

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?

DW
fonte
2
Adoro a sua pergunta, também está relacionada a uma pergunta muito interessante que eu vi na matemática outro dia relacionada à refutação de conjecturas com constantes grandes. Você pode encontrá-lo aqui
ZeroUltimax
1
Um pouco mais de escavação e encontrei esses dois algoritmos geométricos.
precisa saber é o seguinte
@ZeroUltimax Você está certo, o ponto central de quaisquer 3 pontos não colineares não é garantido. O remédio rápido é colocar um ponto na linha entre a extrema esquerda e a extrema direita. Existe outro problema onde?
InformedA
A premissa dessa pergunta me parece estranha de uma maneira que estou tendo dificuldade em entender, mas acho que tudo se resume ao processo de design do algoritmo descrito como fundamental. Mesmo para os alunos que não param por aí, está condenado. 1> algoritmo de gravação, 2> pensa / executa casos de teste, 3a> stop ou 3b> se mostra correto. O primeiro passo praticamente tem ser identificar as classes de entrada para o domínio do problema. Os casos de canto e o próprio algoritmo surgem desses. (cont)
Mr.Mindor
1
Como você distingue formalmente um bug de implementação de um algoritmo defeituoso? Fiquei interessado em sua pergunta, mas ao mesmo tempo fiquei incomodado com o fato de que a situação que você descreve parece ser mais a regra do que a exceção. Muitas pessoas testam o que implementam, mas geralmente ainda têm bugs. O segundo exemplo da resposta mais votada é precisamente esse erro.
babou 5/09/14

Respostas:

70

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 id1,,dknndi

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 + 565111410=6+1+1+1+1=5+5

Per Alexandersson
fonte
10
Este é realmente um bom exemplo, especialmente o de que os alunos costumam errar. Você não precisa apenas escolher conjuntos de moedas específicos, mas também valores específicos para ver o algoritmo falhar.
Raphael
2
Além disso, deixe-me dizer que os alunos também terão provas erradas neste exemplo (ostentando alguns argumentos ingênuos que falham em um exame mais detalhado), para que mais de uma lição possa ser aprendida aqui.
Raphael
2
O sistema de moedas britânico à moda antiga (antes da decimalização de 1971) tinha um exemplo real disso. Um algoritmo ganancioso para contar quatro xelins usaria uma meia coroa (2 ½ xelins), uma moeda de um xelim e seis centavos (½ xelim). Mas a solução ideal usa dois florins (2 xelins cada).
Mark Dominus
1
De fato, em muitos casos, algoritmos gananciosos parecem razoáveis, mas não funcionam - outro exemplo é a correspondência bipartida máxima. Por outro lado, também existem exemplos em que parece que um algoritmo ganancioso não deve funcionar, mas funciona: árvore de abrangência máxima.
jkff 19/04
62

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

"curso" "curso" True; Está bem

"" "" True; Está bem

"universidade" "curso" False; Está bem

"palestra" "curso" False; Está bem

"precisão" "exatidão" False, OK

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.

Juho
fonte
9
Obviamente, a falha é bastante aparente na fonte (se você já escreveu uma coisa semelhante antes).
Raphael
3
Mesmo que a falha simples no programa de exemplo seja corrigida, as strings causam alguns problemas interessantes! A reversão de string é um clássico - a maneira "básica" de fazer isso é simplesmente revertendo os bytes. Então a codificação entra em jogo. Em seguida, substitutos (geralmente duas vezes). O problema é, obviamente, que não há maneira fácil de provar formalmente que seu método está correto.
Ordous 29/08/14
6
Talvez eu esteja interpretando mal a pergunta completamente, mas isso parece ser uma falha na implementação e não uma falha no próprio algoritmo .
precisa saber é o seguinte
8
@ Mr.Mindor: como você pode saber se o programador anotou um algoritmo correto e o implementou incorretamente ou anotou um algoritmo incorreto e o implementou fielmente (hesito em dizer "corretamente"!)
Steve Jessop,
1
@wabbit Isso é discutível. O que é óbvio para você pode não ser óbvio para um aluno do primeiro ano.
Juho
30

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

Franki
fonte
O teste de primalidade de Fermat é um teste probabilístico, portanto, sua pós-condição não está correta.
Femaref 29/08/14
5
ofc é um teste probabilístico, mas a resposta mostra bem (de maneira mais geral) como algoritmos probabilísticos confundidos com os exatos podem ser uma fonte de erro. mais sobre os números de Carmichael
vzn
2
Esse é um bom exemplo, com uma limitação: para o uso prático dos testes de primalidade com os quais estou familiarizado, ou seja, geração de chaves criptográficas assimétricas, usamos algoritmos probabilísticos! Os números são grandes demais para testes exatos (se não fossem, não seriam adequados para criptografia porque as chaves poderiam ser encontradas pela força bruta em tempo realista).
Gilles
1
a limitação a que você se refere é prático, não teórico, e os testes principais em sistemas de criptografia, por exemplo, o RSA estão sujeitos a falhas raras / altamente improváveis por exatamente essas razões, novamente sublinhando a importância do exemplo. isto é, na prática, algumas vezes essa limitação é aceita como inevitável. existem algoritmos de tempo P para teste de primalidade, por exemplo, AKS, mas eles demoram muito para números "menores" usados ​​na prática.
vzn
Se você testar não apenas com 2 p, mas com p para 50 valores aleatórios diferentes 2 ≤ a <p, a maioria das pessoas saberá que é probabilístico, mas com falhas tão improváveis ​​que é mais provável que um mau funcionamento no computador produza a resposta errada. Com 2p, 3p, 5p e 7p, as falhas já são muito raras.
gnasher729
21

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.

ZeroUltimax
fonte
1
Esse truque foi usado no concurso C secreto para produzir uma implementação defeituosa do RC4 . Lendo esse artigo novamente, notei que esse hack provavelmente foi enviado por @DW
CodesInChaos
7
Essa falha é realmente sutil - mas a falha é específica da linguagem, portanto, não é realmente uma falha no algoritmo; é uma falha na implementação. Poder-se-ia encontrar outros exemplos de esquisitices de linguagem que facilitam a ocultação de falhas sutis, mas não era exatamente isso que eu procurava (procurava algo no nível de abstração de algoritmos). De qualquer forma, essa falha não é uma demonstração ideal do valor da prova; a menos que você já esteja pensando em alias, poderá acabar ignorando o mesmo problema ao escrever sua "prova" de correção.
DW
É por isso que estou surpresa que isso tenha sido votado tão alto.
precisa saber é o seguinte
2
@DW É uma questão de saber em que modelo você define o algoritmo. Se você descer para um nível em que as referências de memória sejam explícitas (em vez do modelo comum que pressupõe a ausência de compartilhamento), essa é uma falha do algoritmo. A falha não é realmente específica do idioma, aparece em qualquer idioma que suporte o compartilhamento de referências de memória.
Gilles
16

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.

Rafael
fonte
2
bom exemplo, no entanto, na verdade, em geral, não há como provar que o PRNG não tem falhas, existe apenas uma hierarquia infinita de testes mais fracos versus mais fortes. na verdade, provar que alguém é "aleatório", em qualquer sentido estrito, é presumivelmente indecidível (ainda não vi isso provado).
vzn
1
É uma boa idéia de algo difícil de testar, mas também é difícil provar a RNG. O PRNG não é tão propenso a erros de implementação quanto a ser mal especificado. Testes como obstinado são bons para alguns usos, mas para criptografia, você pode passar pelo obstinado e ainda assim ser ridicularizado. Não existe um CSPRNG "seguro comprovado", o melhor que você pode esperar é provar que, se o seu CSPRNG estiver quebrado, o AES também estará.
Gilles
@ Gilles Eu não estava tentando entrar em criptografia, apenas aleatoriedade estatística (acho que os dois têm requisitos ortogonais). Devo deixar isso claro na resposta?
Raphael
1
A aleatoriedade criptográfica implica aleatoriedade estatística. Também não existe uma definição matematicamente formal, até onde eu saiba, além da noção ideal (e contraditória com o conceito de PRNG implementado em uma máquina determinística de Turing) de aleatoriedade teórica da informação. A aleatoriedade estatística tem uma definição formal além de "deve ser independente das distribuições contra as quais testamos"?
Gilles
1
@vzn: o que significa ser uma sequência aleatória de números pode ser definida de várias maneiras possíveis, mas uma simples é a "grande complexidade de Komolgorov". Nesse caso, é fácil mostrar que determinar a aleatoriedade é indecidível.
Cody
9

Máximo local 2D

entrada: bidimensional matrizn×nA

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,j1],A[i1,j],A[i+1,j]A

0134323125014013

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(n2)

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.AXXA(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 . AXAX(i,j)A

Lema. Quadrant contém um máximo local de .AA

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)AA(i,j)

O algoritmo chama a si próprio recursivamente na sub-matriz para encontrar um máximo local lá e depois retorna a célula.n2×n2A(i,j)

O tempo de execução para uma matriz satisfaz , então . T(n)n×nT(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×n

Ou nós?

Neal Young
fonte
Eu ainda estou absorvendo isso. Uma pergunta rápida até que eu faça: Você quis dizer que o tempo de execução é ? (Como essa é a solução para a recorrência .)T ( n ) = T ( n / 2 ) + O ( n )T(n)=O(nlogn)T(n)=T(n/2)+O(n)
DW
2
Este é um belo exemplo! Eu amo isso. Obrigado. .. (Eu finalmente descobri a falha neste algoritmo Dos timestamps você pode obter um limite inferior de quanto tempo ele me levou Estou muito envergonhado de revelar o tempo real :-).
DW
1
Uma parte boa é que esse algoritmo está quase correto: se escolhermos uma 'janela' em vez de uma 'cruz', podemos recuar adequadamente e obter um algoritmo . Veja também cursos.csail.mit.edu/6.006/spring11/lectures/lec02.pdf . O(n)
Lagarto discreto
8

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.1016

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?"

DanaJ
fonte
1
Muitos deles se parecem com (1) erros de implementação (o algoritmo subjacente está correto, mas não foi implementado corretamente), o que é interessante, mas não é o objetivo desta questão, ou (2) uma escolha consciente e deliberada para selecionar algo que é rápido e funciona principalmente, mas pode falhar com uma probabilidade muito pequena (para o código que está testando com uma base aleatória ou com algumas bases fixas / aleatórias, espero que quem quer que faça isso saiba que está fazendo uma troca de desempenho).
DW
Você está certo no primeiro ponto - algoritmo correto + bug não é o ponto, embora a discussão e outros exemplos também os estejam conflitando. O campo está repleto de conjecturas que funcionam para pequenos números, mas estão incorretas. Para o ponto (2), isso é verdade para alguns, mas meus exemplos # 1 e # 3 não foram o caso - acreditava-se que o algoritmo estava correto (essas 5 bases fornecem resultados comprovados para números abaixo de 10 ^ 16) e depois descobriu que não era.
DanaJ
Esta não é uma questão fundamental nos testes de pseudo-primalidade?
asmeurer
asmeurer, sim no meu nº 2 e na discussão posterior deles. Mas os nºs 1 e 3 foram casos de uso de Miller-Rabin com bases conhecidas para fornecer resultados corretos determinísticos abaixo de um limite. Portanto, neste caso, o "algoritmo" (usando o termo livremente para corresponder ao OP) estava incorreto. O número 4 não é um teste provável, mas como DW apontou, o algoritmo funciona bem, é apenas a implementação que é difícil. Incluí-o porque leva a uma situação semelhante: o teste é necessário e até onde você vai além de exemplos simples antes de dizer que funciona?
DanaJ
Algumas das postagens parecem se encaixar na pergunta, enquanto outras não (cf. comentário de @ DW). Remova os exemplos (e outros conteúdos) que não respondem à pergunta.
Raphael
7

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 iij0ji

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 - 1nn!=n×n1×n2..nn1

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).

Nikos M.
fonte
1
Veja aqui um exemplo de prova de correção para um algoritmo de reprodução aleatória.
Raphael
5

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.

Jake
fonte
5

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.

jonaprieto
fonte
O ganancioso já estava coberto na resposta aceita , mas o problema da mochila em particular é adequado para definir algumas armadilhas.
Raphael
3

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 ) nn!nn(n1)n

Per Alexandersson
fonte
1
É um bom bug, mas não é uma boa ilustração para enganar a heurística dos casos de teste, pois o teste não se aplica a algoritmos aleatórios (é aleatório, então como você o testaria? O que significaria falhar em um caso de teste e como você detectar que de olhar para a saída)?
DW
Você testa isso estatisticamente, é claro. A aleatoriedade uniforme está longe de "qualquer coisa pode acontecer na saída". Você não ficaria desconfiado se um programa que emulasse um dado lhe desse 100 3 seguidos?
Por Alexandersson
Mais uma vez, estou falando sobre a heurística do aluno de "experimentar alguns casos de teste manualmente". Já vi muitos estudantes pensarem que essa é uma maneira razoável de verificar se um algoritmo determinístico está correto, mas suspeito que eles não assumiriam que é uma boa maneira de testar se um algoritmo de embaralhamento está correto (já que um algoritmo de embaralhamento é aleatório, existe não há como saber se alguma saída específica está correta; em qualquer caso, você não pode acionar manualmente exemplos suficientes para fazer qualquer teste estatístico útil). Portanto, não espero que algoritmos de embaralhamento ajudem muito a esclarecer o equívoco comum.
DW
1
@PerAlexandersson: Mesmo que você gere apenas um shuffle, não pode ser verdadeiramente aleatório usando MT com n> 2080. Agora, o desvio do esperado será muito pequeno, então você provavelmente não se importará ... mas isso se aplica mesmo se você gera muito menos do que o período (como indicado acima).
Charles
2
Essa resposta parece ter sido tornada obsoleta pela mais elaborada de Nikos M. ?
Raphael
2

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.

cristão
fonte
1
n1
2
@ Rafael: Embora seja justo, o algoritmo escolhido é conhecido por ser uma má escolha para dados de ponto flutuante.
2
Não se trata simplesmente da implementação da operaçã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. Esse foi um dos assuntos sobre o qual meu curso numérico na universidade era.
Christian
Além do comentário preciso de Raphael, uma desvantagem deste exemplo é que eu não acho que uma prova de correção ajudaria a evitar essa falha. Se você não está ciente das sutilezas da aritmética de ponto flutuante, pode pensar que provou isso corretamente (provando que a fórmula é válida). Portanto, não é um exemplo ideal para ensinar aos alunos por que é importante provar que seus algoritmos estão corretos. Se os alunos vissem esse exemplo, minha suspeita é que eles desenhariam a lição "coisas de ponto flutuante / computação numérica são complicadas".
DW
1

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.

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

Solução proposta :

int f(int n) {
   return 1;
}

n=0,1,2,,39n=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.

Rick Decker
fonte
5
Eu não acho que este é um exemplo muito bom, porque poucas pessoas tentariam encontrar os divisores de um polinômio, retornando 1.
Brian S
1
nn3n
Isso pode ser relevante, no sentido de que o retorno de um valor constante para divisores (ou outra caclulação) pode ser o resultado de uma abordagem algorítmica incorreta de um problema (por exemplo, um problema estatístico ou de não lidar com casos extremos do algoritmo). No entanto, a resposta precisa reformular
Nikos M.
@NikosM. Heh. Sinto que estou batendo em um cavalo morto aqui, mas o segundo parágrafo da pergunta diz que "se o algoritmo deles funcionar corretamente em alguns exemplos, incluindo todos os casos de canto que eles podem pensar em tentar, então eles concluem que o algoritmo deve Sempre há um aluno que pergunta: "Por que preciso provar que meu algoritmo está correto, se posso experimentá-lo em alguns casos de teste?" Nesse caso, para os primeiros 40 valores (muito mais do que um aluno é . propensos a tentar), retornando 1 está correta parece-me ser isso que o OP estava procurando.
Rick Decker
Ok, sim, mas isso como formulado é trivial (talvez normalmente correto), mas não no espírito da pergunta. Ainda precisa de reformulação
Nikos M.