¿Problemas de ejemplo con soluciones polinómicas y exponenciales, y una huella pequeña?

Estoy planeando ejecutar un "experimento" cuando enseñe mi clase de algoritmos este otoño, con una computadora muy antigua y limitada (el factor limitante principal es probablemente la memoria, posiblemente tan bajo como 16 KB) y uno moderno / estándar. La idea es resolver un problema con un polinomio, que se ejecuta en la computadora lenta, y uno exponencial en la computadora rápida (y, por supuesto, que gane la lenta).

El problema es encontrar un problema adecuado, uno donde los tiempos de ejecución sean realmente diferentes para instancias de tamaño muy limitado (y, preferiblemente, donde las estructuras de datos son bastante simples; la computadora primitiva es ... primitiva). Originalmente pensé en los algoritmos de clasificación (p. Ej., Cuadrático vs. lineal), pero eso requeriría instancias demasiado grandes (a menos que fuera con bogosort, por ejemplo).

Por el momento, el único ejemplo (bastante aburrido) en el que he pensado es calcular los números de Fibonacci de manera inteligente y estúpida. Sería bueno tener algo un poco menos cansado / usado en exceso, y preferiblemente algo (semi) obviamente útil. ¿Alguna idea / sugerencia?

Una respuesta que generaliza un poco el comentario de Neel es mirar en el área de búsqueda y programación dinámica, que está llena de algoritmos maravillosos que funcionan muy bien si memorizas y terriblemente si no lo haces, incluso la aburrida función factorial en la que estabas pensando cae en esto. categoría.

Por supuesto, estará limitado por el límite de memoria en la computadora lenta, pero creo que eso significa que debe tener cuidado de ser lo suficientemente "malo" para la computadora rápida. Aquí hay algunas ideas específicas:

• Dado un gran gráfico no dirigido, encuentre una ruta entre dos puntos. La computadora rápida implementa una búsqueda aleatoria (¡justa, o podría no terminar!) A través del gráfico, mientras que la computadora lenta realiza tranquilamente una búsqueda de amplitud o profundidad. Probablemente necesite ejecutar esto en varias pruebas para asegurarse de que la diferencia de rendimiento sea notable.
• Obtenga un gráfico dirigido e intente encontrar la ruta más corta entre dos puntos: la computadora rápida enumera todas las rutas acíclicas (usando el algoritmo de detección de ciclo de tortuga y liebre en cada paso, bwahahahaha) primero, y la computadora lenta ejecuta pacientemente la fuente más corta más corta camino.
• El algoritmo de edición de distancia? Cualquier algoritmo de programación más ingenuo que dinámico probablemente se ahogará por completo aquí.

Una última idea es que podría probar algunos algoritmos en Prolog con y sin que ocurra una comprobación (innecesaria). Pero si les muestras a esos estudiantes lo maravilloso que es que Prolog sin un control semántico significativo ocurra, la comprobación es más rápida, lloraré. Además, esto suele ser lineal-vs-cuadrático, no polinomial-versus-exponencial.

Podrías hacer una coincidencia de expresiones regulares. Un ingenioso emparejador de retroceso puede ser fácilmente llevado a un comportamiento exponencial en las entradas que un emparejador más inteligente puede manejar en tiempo lineal.

Intente contar coincidencias perfectas en gráficos planos, un problema que debería ser fácil de explicar. En el caso plano, el algoritmo de Fisher-Kastelyen-Temperley lo resuelve en tiempo polinómico, mientras que para los gráficos generales el problema es # P-completo, es decir, probablemente no sea una forma más rápida que hacer un recuento de fuerza bruta. Simplemente ejecute FKT en la máquina lenta y la fuerza bruta contando con la rápida.

( Esta también es una pregunta relacionada).

Si está enseñando algoritmos, creo que debería hacer algo simple, que ilustra la idea. Creo que su idea de algoritmo de clasificación es muy buena y probablemente funcione si prueba algoritmos no recursivos en la computadora primitiva.

Actualmente estoy comparando algoritmos de clasificación y tengo Heap Sort ejecutándose con 17,000 elementos en una computadora con 32kb de ram.

Intentaría la inserción de clasificación vs Heap Sort.