¿Cómo engañar a la trama heurística de inspección?

23

Por aquí , Dave Clarke propuso que para comparar el crecimiento asintótico, debe trazar las funciones disponibles. Como científico de la computación teóricamente inclinado, llamo (ed) a este vudú ya que una trama nunca es una prueba. Pensándolo bien, tengo que estar de acuerdo en que este es un enfoque muy útil que incluso a veces se subutiliza; una trama es una forma eficiente de obtener primeras ideas, y a veces eso es todo lo que necesita.

Cuando se enseña TCS, siempre hay un estudiante que pregunta: "¿Para qué necesito una prueba formal si puedo hacer X que siempre funciona?" Depende de su maestro (s) señalar e ilustrar la falacia. Hay un conjunto brillante de ejemplos de patrones aparentes que eventualmente fallan en matemáticas. SE, pero esos son escenarios bastante matemáticos.

Entonces, ¿cómo engañas a la heurística de la inspección de la trama? Hay algunos casos en que las diferencias son difíciles de distinguir, p. Ej.

ejemplo ejemplo ejemplo
^{[ fuente ]}

Adivine y luego verifique la fuente de las funciones reales. Pero esos no son tan espectaculares como esperaría, en particular porque las relaciones reales son fáciles de detectar solo desde las funciones, incluso para un principiante.

¿Hay ejemplos de crecimiento asintótico (relativo) donde la verdad no es obvia a partir de la definición de la función y la inspección de la parcela para razonablemente grande $n$ le da una idea completamente equivocada? Las funciones matemáticas y los conjuntos de datos reales (por ejemplo, tiempo de ejecución de un algoritmo específico) son bienvenidos; sin embargo, absténgase de las funciones definidas por partes.

asymptotics didactics Rafael
fuente

2

En realidad, lo propuse como un consejo para entender el problema.

Dave Clarke

@DaveClarke: lo sé; Utilicé tu formulación inicial simplemente como un abridor provocativo. Sin intención de ofender.

Raphael

23

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

trama
^{[ fuente ]}

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

Peter Shor
fuente

15

Aquí hay otro ejemplo (ciertamente construido), pero todavía encuentro uno notable. Se pretende mostrar que las parcelas pueden ser muy engañosas para juzgar el crecimiento asintótico.

$f$ $g$

¿Puedes adivinar cuál de las funciones crece (asintóticamente) más rápido?

trama de f y g hasta 2000 parcela de f y g hasta 10.000 parcela de f y g hasta 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)\;.$

Entonces, es esencialmente , es decir, lo mismo que , pero su segunda derivada no es uniformemente , sino que oscila entre y con un período de crecimiento exponencial. Esta oscilación no es visible en las parcelas ordinarias. $g$ $x^2$ $f$ $2$ $0$ $4$

Para este ejemplo, podemos demask las oscilaciones considerando un log-log-plot:

log-log-plot de f y g hasta 200,000

Por supuesto, esto no ayuda, en general; por ejemplo, podríamos tener un período doblemente exponencial ...

Sebastian
fuente

12

Un buen ejemplo es el algoritmo DFA mínimo profundamente mágico de Brzozowski. Dado un autómata finito , podemos calcular un autómata finito determinista mínimo a partir de él: $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, este es un algoritmo de tiempo exponencial en el peor de los casos, ya que puede tomar un autómata no determinista y darle uno determinista (o incluso más obviamente, llama a la construcción del subconjunto dos veces).

Sin embargo, si le da al algoritmo de Brzozowski un DFA como entrada, en muchos tipos comunes de entrada puede competir y, a menudo, superar a los algoritmos especializados de minimización de DFA (que generalmente son u si tiene un núcleo duro e implementa el algoritmo de Hopcraft). $O(n^2)$ $O(n \log(n))$

Esto toca la parte de "trama" de la "heurística de inspección de trama" --- tenemos que elegir qué puntos muestrear al dibujar la trama, y puede engañar a una trama ingenua si no elige sus puntos con cuidado. Esto también es cierto para otros ejemplos, como Quicksort y el algoritmo Simplex, pero para la pedagogía prefiero este algoritmo a esos dos.

La diferencia de Quicksort es "solo" cuadrática versus log-lineal, que es menos espectacular que una diferencia polinómica / exponencial. El algoritmo simplex tiene una diferencia espectacularmente similar, pero su análisis es considerablemente más complicado que el algoritmo de Brzozowski.

(Además, creo que el algoritmo de minimización de DFA de Brzozowski es mucho menos conocido de lo que merece, pero, por supuesto, es cuestión de gustos).

Neel Krishnaswami
fuente

Lo siento, pero no veo la conexión para interpretar gráficos de funciones.

Raphael

3

Supongo que haría algo como el rendimiento de la trama versus el tamaño de la instancia para una muestra de instancias, y el algoritmo de Brzozowski "luciría" polinomial a menos que elija instancias para hacerlo exponencial.

Neel Krishnaswami

1

Veo. Eso es ciertamente un problema al comparar algoritmos y trazar tiempos de ejecución promedio, es decir, un problema de trazar los datos correctos . Cuando planteé la pregunta, solo estaba pensando en interpretar la trama correctamente , que es otra bestia por completo. ¿Puedes agregar esta perspectiva a la respuesta?

Raphael

Tendría el mismo problema para todos los algoritmos que tienen un comportamiento promedio diferente y el peor de los casos; Quicksort y Simplex vienen a la mente.

Raphael

8

La técnica matemática de ajuste de curvas se puede utilizar para proporcionar un número infinito de respuestas a su pregunta. Dada una curva y un rango, uno puede encontrar fácilmente un polinomio que se ajuste a la curva con cualquier grado de precisión. Este ejemplo de Wikipedia muestra cómo una onda sinusoidal puede ajustarse con bastante precisión con un polinomio de cuarto orden (la curva azul).

ingrese la descripción de la imagen aquí

Podría utilizar polinomios de orden superior y engañar a la heurística de inspección de la trama incluso mejor que este gráfico.

Dave Clarke
fuente

2

Es verdad. Sin embargo, también tiene un sabor artificial. Claro que puedo generar contraejemplos para los estudiantes de esta manera, pero no veo que los más escépticos estén convencidos de ello. ¿Hay ocurrencias "naturales" de este fenómeno (es decir, funciones polinómicas de mayor grado que pueden confundirse con otras funciones) donde la mala interpretación es "fatal"?

Raphael

Sé que no es la respuesta que estás buscando.

Dave Clarke

¿Cómo engañar a la trama heurística de inspección?

Respuestas: