ds.algorithms – ¿Problemas de ejemplo con soluciones polinomiales y exponenciales, y tamaño reducido?

Pregunta:

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

El problema es encontrar un problema adecuado, uno donde los tiempos de ejecución serán 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 ordenar algoritmos (p. Ej., Cuadrático frente a lineal), pero eso requeriría instancias demasiado grandes (a menos que optara por bogosort, por ejemplo).

Por el momento, el único ejemplo (bastante aburrido) en el que he pensado es calcular los números de Fibonacci de la 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?

Respuesta:

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 este categoría.

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

  • Dado un gráfico grande sin dirección, encuentre un camino entre dos puntos. La computadora rápida implementa una búsqueda aleatoria (regular, ¡o podría no terminar!) A través del gráfico, mientras que la computadora lenta realiza tranquilamente una búsqueda en 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 (utilizando el algoritmo de detección del ciclo de la tortuga y la liebre en cada paso, bwahahahaha) primero, y la computadora lenta ejecuta pacientemente la fuente única más corta sendero.
  • ¿El algoritmo de distancia de edición? 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 una verificación de ocurre (innecesaria). Pero si les muestra a esos estudiantes lo maravilloso que es que Prolog sin un control de ocurrencias semánticamente significativo sea más rápido, lloraré. Además, esto suele ser lineal frente a cuadrático, no polinómico frente a exponencial.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım