Simulaciones, eficiencia algorítmica y problemas indecidibles
Imagina que un equipo de ingenieros quiere saber si un puente aguantará un huracán en la costa del Golfo. No pueden construirlo, esperar la tormenta y ver qué pasa. Entonces lo simulan en una computadora. Pero también hay problemas que ni la computadora más rápida resuelve a tiempo, e incluso algunos que ningún programa podrá resolver jamás. En esta página verás cómo se usan los números aleatorios, qué es una simulación, cómo medir si un algoritmo es "razonable" y qué significa que un problema sea indecidible.
Valores aleatorios con RANDOM
Muchos programas necesitan azar: un videojuego que reparte cartas, una app que elige una canción al azar o una simulación de lanzar un dado. En el pseudocódigo de AP se usa RANDOM(a, b).
El número de valores posibles es $b - a + 1$. Por ejemplo, RANDOM(1, 6) puede dar 1, 2, 3, 4, 5 o 6: seis valores, como un dado. Se suma 1 porque se cuentan los dos extremos.
Si un programa usa azar, la salida puede cambiar en cada ejecución. Un algoritmo cuyo resultado depende del azar se llama probabilístico. Uno que siempre da la misma salida con la misma entrada es determinista.
a) ¿Cuáles son los valores posibles de RANDOM(1, 6)? b) ¿Cuántos valores distintos puede devolver RANDOM(5, 15)? c) ¿Qué llamada podría simular el lanzamiento de una…
- a) ¿Cuáles son los valores posibles de
RANDOM(1, 6)?
- b) ¿Cuántos valores distintos puede devolver
RANDOM(5, 15)?
- c) ¿Qué llamada podría simular el lanzamiento de una moneda?
Simulaciones
Una simulación es un programa que usa un modelo simplificado de algo del mundo real para estudiar su comportamiento. Los modelos dejan fuera detalles; por eso son manejables, pero también por eso pueden fallar.
Ventajas de simular:
-
Es más barato y seguro (probar un puente, un avión o un tratamiento sin riesgos).
-
Se pueden probar situaciones que serían imposibles o peligrosas en la vida real, como un huracán de categoría 5.
-
Se puede repetir muchas veces y rápido.
Límites:
-
El modelo deja fuera factores reales, así que los resultados son aproximados.
-
Si los supuestos o los datos tienen sesgos, la simulación también.
-
No sustituye por completo a las pruebas en el mundo real.
Los ingenieros usan simulaciones para probar cómo responde un puente a vientos fuertes antes de construirlo. Da un beneficio y una limitación de usar simulaciones en…
Los ingenieros usan simulaciones para probar cómo responde un puente a vientos fuertes antes de construirlo. Da un beneficio y una limitación de usar simulaciones en lugar de experimentos en el mundo real.
Liam simula a una jugadora de baloncesto que encesta el 70% de sus tiros libres. a) ¿Cuál es la probabilidad de que cada tiro simulado sea encestado? Explica. b) ¿Qué…
Liam simula a una jugadora de baloncesto que encesta el 70% de sus tiros libres.
makes ← 0
REPEAT 10 TIMES
{
IF (RANDOM(1, 10) ≤ 7)
{
makes ← makes + 1
}
}
DISPLAY(makes)
- a) ¿Cuál es la probabilidad de que cada tiro simulado sea encestado? Explica.
- b) ¿Qué rango de valores se puede mostrar?
- c) ¿La salida será la misma en cada ejecución? ¿Por qué ejecutar la simulación muchas veces y promediar da una mejor estimación?
Eficiencia: tiempo razonable y no razonable
Dos algoritmos pueden resolver el mismo problema y uno ser mucho más rápido. Para medir la eficiencia contamos los pasos que da el algoritmo según el tamaño $n$ de la entrada (por ejemplo, cuántos elementos tiene la lista). Contar pasos sirve porque no depende de qué tan rápida sea cada computadora.
Mira cómo crecen los pasos:
| $n$ | $n$ | $n^2$ | $2^n$ |
|---|---|---|---|
| 10 | 10 | 100 | 1,024 |
| 20 | 20 | 400 | 1,048,576 |
| 30 | 30 | 900 | 1,073,741,824 |
Al subir $n$ de 10 a 30, $n^2$ pasa de 100 a 900, pero $2^n$ se dispara a más de mil millones. Los algoritmos exponenciales son prácticos solo para entradas muy pequeñas.
Un algoritmo se ejecuta en tiempo razonable si el número de pasos crece como un polinomio del tamaño de la entrada $n$, como $n$ o $n^2$. Se ejecuta en tiempo no…
Un algoritmo se ejecuta en tiempo razonable si el número de pasos crece como un polinomio del tamaño de la entrada $n$, como $n$ o $n^2$. Se ejecuta en tiempo no razonable si el número de pasos crece de forma exponencial o más rápido. Clasifica cada caso como razonable o no razonable:
- a) $n$ pasos
- b) $n^2$ pasos
- c) $2^n$ pasos
- d) $n!$ pasos
Compara el número de pasos de dos algoritmos: | $n$ | $n^2$ | $2^n$ | |---|---|---| | 10 | 100 | 1,024 | | 20 | 400 | 1,048,576 | | 30 | 900 | 1,073,741,824 | a) ¿Cuál…
Compara el número de pasos de dos algoritmos:
| $n$ | $n^2$ | $2^n$ |
|---|---|---|
| 10 | 100 | 1,024 |
| 20 | 400 | 1,048,576 |
| 30 | 900 | 1,073,741,824 |
- a) ¿Cuál algoritmo es razonable y cuál no razonable? Explica con la tabla.
- b) Una computadora realiza 1,000 millones de pasos por segundo. ¿Aproximadamente cuánto tarda el algoritmo de $2^{30}$ pasos?
- c) Para $n = 60$, el algoritmo exponencial necesita aproximadamente $1.15 \times 10^{18}$ pasos. ¿Cuántos años son, aproximadamente, a la misma velocidad? Usa $1\text{ año} \approx 3.15 \times 10^7$ segundos.
Dos algoritmos averiguan si una lista de $n$ valores tiene un duplicado. El algoritmo A compara todos los pares, con aproximadamente $\dfrac{n(n-1)}{2}$ pasos. El…
Dos algoritmos averiguan si una lista de $n$ valores tiene un duplicado.
-
El algoritmo A compara todos los pares, con aproximadamente $\dfrac{n(n-1)}{2}$ pasos.
-
El algoritmo B ordena primero la lista y luego revisa los vecinos, con aproximadamente $10n$ pasos.
- a) Calcula el número de pasos de cada algoritmo cuando $n = 10$ y cuando $n = 1{,}000$.
- b) ¿Para qué valor de $n$ los dos algoritmos usan el mismo número de pasos? ¿Cuál es más rápido para valores mayores de $n$?
- c) ¿Ambos algoritmos son razonables? Explica. Luego explica por qué el algoritmo con menos pasos para entradas pequeñas no siempre es la mejor opción.
Heurísticas
¿Qué se hace cuando el único algoritmo exacto conocido es no razonable? Un caso famoso es el del repartidor: debe visitar $n$ ciudades y volver a casa por la ruta más corta. La fuerza bruta revisa todos los órdenes posibles. Fijando la ciudad de partida hay $(n-1)!$ rutas.
-
$n = 5$: $4! = 24$ rutas.
-
$n = 10$: $9! = 362{,}880$ rutas.
-
$n = 15$: $14! = 87{,}178{,}291{,}200$ rutas.
Con una computadora que revisa 1,000,000 de rutas por segundo, $n = 10$ tarda cerca de 0.36 segundos, pero $n = 15$ tarda unos $87{,}178$ segundos, es decir, unas 24.2 horas. Y con $n = 25$ ya serían miles de millones de años.
Una heurística es un método que da una solución buena en tiempo razonable, aunque no garantiza que sea la mejor. Por ejemplo, la del vecino más cercano: desde la ciudad actual, ir siempre a la ciudad no visitada más cercana. Es rápida, pero la ruta puede ser más larga que la óptima.
Un repartidor debe visitar $n$ ciudades y regresar a casa. La fuerza bruta revisa todos los órdenes posibles. Si se parte de una ciudad fija, hay $(n-1)!$ rutas. a)…
Un repartidor debe visitar $n$ ciudades y regresar a casa. La fuerza bruta revisa todos los órdenes posibles. Si se parte de una ciudad fija, hay $(n-1)!$ rutas.
- a) Calcula el número de rutas para $n = 5$ y $n = 10$. Luego usa $14! = 87{,}178{,}291{,}200$ para $n = 15$.
- b) Una computadora revisa 1,000,000 de rutas por segundo. ¿Cuánto tarda para $n = 10$ y para $n = 15$? Da la segunda respuesta en horas, redondeada a un decimal.
- c) ¿El algoritmo de fuerza bruta es razonable o no razonable? Describe una heurística que dé una buena ruta, aunque no necesariamente la mejor, y explica la concesión (trade-off).
Problemas indecidibles
Un problema es decidible si existe un algoritmo que siempre da la respuesta correcta (sí o no) para cualquier entrada. Un problema es indecidible si no puede existir ningún algoritmo que lo resuelva siempre para todas las entradas. Esto no es falta de ingenio: está demostrado que es imposible.
El ejemplo clásico es el problema de la detención (halting problem): dado un programa y su entrada, ¿se detendrá algún día o se ejecutará para siempre? Alan Turing demostró que ningún algoritmo puede responder esto correctamente para todos los programas.
La idea de la demostración: si existiera un detector perfecto, podríamos escribir un programa que lo consulte sobre sí mismo y haga lo contrario de lo que el detector diga. Eso genera una contradicción, así que el detector no puede existir.
Esto no significa que nunca se pueda saber si un programa se detiene. Para muchos programas concretos sí se puede. Lo imposible es una herramienta que acierte con todos.
En la práctica, los desarrolladores usan pruebas con casos de prueba, límites de tiempo (timeouts) que detienen un programa que tarda demasiado, y revisión del código para detectar bucles infinitos.
Una empresa de software afirma haber creado una herramienta que puede analizar cualquier programa y decir con certeza si en algún momento se detendrá o se ejecutará para…
Una empresa de software afirma haber creado una herramienta que puede analizar cualquier programa y decir con certeza si en algún momento se detendrá o se ejecutará para siempre.
- a) Explica la diferencia entre un problema decidible y uno indecidible.
- b) El problema descrito se conoce como el problema de la detención (halting problem). ¿Es posible lo que afirma la empresa? Explica.
- c) Describe una cosa práctica que los desarrolladores sí pueden hacer para detectar programas que se quedan atascados.
Vuelve al principio: los ingenieros simulan el puente porque es más seguro y barato, pero su modelo simplifica la realidad. Y aunque la simulación sea correcta, algunos cálculos son tan grandes que necesitan heurísticas, y otros no tienen algoritmo posible.
Resumen
-
RANDOM(a, b)devuelve un entero entreayb, ambos incluidos: hay $b - a + 1$ valores posibles. -
Una simulación usa un modelo simplificado: es barata y segura, pero aproximada y puede tener sesgos.
-
Un algoritmo es razonable si sus pasos crecen como un polinomio ($n$, $n^2$) y no razonable si crecen exponencialmente o más rápido ($2^n$, $n!$).
-
Una heurística da una buena solución rápido, sin garantizar la mejor.
-
Un problema indecidible, como el de la detención, no puede resolverse con ningún algoritmo para todas las entradas.