Como enganar a heurística da inspeção de plotagem?

23

Por aqui , Dave Clarke propôs que, para comparar o crescimento assintótico, você deve traçar as funções em questão. Como cientista da computação, teoricamente inclinado, chamo esse vodoo de que um enredo nunca é prova. Pensando bem, tenho que concordar que essa é uma abordagem muito útil que às vezes é subutilizada; um enredo é uma maneira eficiente de obter as primeiras idéias e, às vezes, é tudo o que você precisa.

Ao ensinar o TCS, sempre há o aluno que pergunta: "Para que preciso de uma prova formal, se posso fazer o X que sempre funciona?" Cabe ao (s) professor (s) apontar e ilustrar a falácia. Há um brilhante conjunto de exemplos de padrões aparentes que acabam falhando no math.SE, mas esses são cenários bastante matemáticos.

Então, como você engana a heurística da inspeção de plotagem? Existem alguns casos em que é difícil diferenciar as diferenças, por exemplo,

exemplo exemplo exemplo
^{[ fonte ]}

Faça um palpite e verifique a fonte quanto às funções reais. Mas essas não são tão espetaculares quanto eu esperaria, principalmente porque é fácil identificar as relações reais apenas com as funções, mesmo para iniciantes.

Existem exemplos de crescimento assintótico (relativo) em que a verdade não é óbvia a partir da função definição e inspeção de plotagem para razoavelmente grande $n$ dá uma idéia completamente errada? Funções matemáticas e conjuntos de dados reais (por exemplo, tempo de execução de um algoritmo específico) são bem-vindos; abstenha-se de funções definidas por partes.

asymptotics didactics Rafael
fonte

2

Na verdade, eu a propus como uma dica para entender o problema.

Dave Clarke

@ DaveClarke: eu sei; Eu usei sua formulação inicial apenas como um provocador abridor. Nenhuma ofensa pretendida.

Raphael

23

$(\log n)^a$ $n^b$ $O(\sqrt{n} \log n)$ $O(n^{0.6})$

enredo
^{[ fonte ]}

$[0,1]$ $n^{0.6}$ $n^{0.7}$ $n^{1/2}\log^{3/4}n$ $n^{2/3}$

Peter Shor
fonte

15

Aqui está outro exemplo (reconhecidamente bastante construído), mas ainda acho notável. Pretende-se mostrar que as parcelas podem ser muito enganadoras para julgar o crescimento assintótico.

$f$ $g$

Você consegue adivinhar qual das funções cresce (assintoticamente) mais rapidamente?

plot de fe eg até 2000 plot de fe até 10.000 plot de fe até 200.000

$f\sim g$

f (x) = x^{2}

$f(x) = x^2$

g (x) = \iint \sin (\log (x)) + 1 d x d x = x^{2} (1 - \frac{3}{5} \cos (\log (x)) + \frac{1}{5} \sin (\log (x))) .

$g(x) = \iint \sin(\log(x))+1 \;dx\,dx = x^2\Bigl(1 - \tfrac{3}{5} \cos(\log(x)) + \tfrac{1}{5} \sin(\log(x)) \Bigr)\;.$

Então é essencialmente , ou seja, o mesmo que , mas sua segunda derivada não é uniformemente , mas oscila entre e com o período de crescimento exponencial. Essa oscilação não é visível em gráficos comuns. $g$ $x^2$ $f$ $2$ $0$ $4$

Para este exemplo, podemos demask as oscilações considerando um log-log-enredo:

log-log-plot de feg até 200.000

Obviamente, isso não ajuda, em geral; por exemplo, podemos ter um período duplamente exponencial ...

Sebastian
fonte

12

Um bom exemplo é o algoritmo DFA mínimo profundamente mágico de Brzozowski. Dado um autômato finito , podemos calcular um autômato finito determinístico mínimo a partir dele: $N = (Q, S \subseteq Q, F \subseteq Q, R \subseteq Q \times \Sigma \times Q)$

M i n i m i z e : N F A \to D F A = D e t e r m i n i z e \circ R e v e r s e \circ D e t e r m i n i z e \circ R e v e r s e

$\mathrm{Minimize} : \mathrm{NFA \to DFA} = \mathrm{Determinize\circ Reverse \circ Determinize \circ Reverse}$

Obviamente, esse é um algoritmo de tempo exponencial no pior dos casos, pois ele pode pegar um autômato não determinístico e fornecer um determinista (ou, mais obviamente, chama a construção do subconjunto duas vezes).

No entanto, se você der ao DFA o algoritmo de Brzozowski como entrada, em muitos tipos comuns de entrada, ele pode competir com e frequentemente superar os algoritmos especializados de minimização de DFA (que normalmente são ou se você é hard-core e implementa o algoritmo de Hopcraft). $O(n^2)$ $O(n \log(n))$

Isso toca a parte "plot" da "heurística de inspeção de plotagem" - temos que escolher quais pontos serão amostrados ao desenhar a plotagem, e você pode enganar uma plotagem ingênua se não escolher seus pontos com cuidado. Isso também vale para outros exemplos, como o Quicksort e o algoritmo Simplex, mas para a pedagogia prefiro esse algoritmo aos dois.

A diferença do Quicksort é "apenas" quadrática versus log-linear, que é menos espetacular do que uma diferença polinomial / exponencial. O algoritmo simplex tem uma diferença igualmente espetacular, mas sua análise é consideravelmente mais complicada do que o algoritmo de Brzozowski.

(Além disso, acho que o algoritmo de minimização de DFA de Brzozowski é muito menos conhecido do que merece, mas é claro que é uma questão de gosto.)

Neel Krishnaswami
fonte

Desculpe, mas não vejo a conexão com a interpretação de gráficos de funções.

Raphael

3

Suponho que você faria algo como desempenho da plotagem versus tamanho da instância para uma amostra de instâncias - e o algoritmo de Brzozowski "pareceria" polinomial, a menos que você escolhesse instâncias para torná-lo um tempo exponencial.

Neel Krishnaswami

1

Entendo. Isso certamente é um problema ao comparar algoritmos e plotar tempos de execução médios, ou seja, uma questão de plotar os dados corretos . Quando fiz a pergunta, estava pensando apenas em interpretar o enredo corretamente , o que é outra fera inteiramente. Você pode adicionar essa perspectiva à resposta?

Raphael

Você teria o mesmo problema para todos os algoritmos com comportamento diferente de média e pior caso; Quicksort e Simplex vêm à mente.

Raphael

8

A técnica matemática de ajuste de curvas pode ser usada para fornecer um número infinito de respostas para sua pergunta. Dada uma curva e um intervalo, é possível encontrar facilmente um polinômio que se ajusta à curva com qualquer grau de precisão. Este exemplo da wikipedia mostra como uma onda sin pode ser ajustada com bastante precisão com um polinômio de quarta ordem (a curva azul).

insira a descrição da imagem aqui

Eu poderia usar polinômios de ordem superior e enganar a heurística de inspeção de plotagem ainda melhor do que este gráfico.

Dave Clarke
fonte

2

Isso é verdade. Ele também tem um sabor artificial, no entanto. Claro que posso gerar contra-exemplos para os alunos dessa maneira, mas não vejo os mais céticos convencidos por isso. Existem ocorrências "naturais" desse fenômeno (ou seja, funções polinomiais de alto grau que podem ser confundidas com outras funções) em que a má interpretação é "fatal"?

Raphael

Eu sei que não é a resposta que você está procurando.

31412 Dave Clarke

Como enganar a heurística da inspeção de plotagem?

Respostas: