Ejercicios: Simulaciones, eficiencia algorítmica y problemas indecidibles

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.

1. a) ¿Cuáles son los valores posibles de RANDOM(1, 6)?

1. b) ¿Cuántos valores distintos puede devolver RANDOM(5, 15)?

1. c) ¿Qué llamada podría simular el lanzamiento de una moneda?

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:

1. a) $n$ pasos

1. b) $n^2$ pasos

1. c) $2^n$ pasos

1. d) $n!$ pasos

Compara el número de pasos de dos algoritmos:

1. a) ¿Cuál algoritmo es razonable y cuál no razonable? Explica con la tabla.

1. b) Una computadora realiza 1,000 millones de pasos por segundo. ¿Aproximadamente cuánto tarda el algoritmo de $2^{30}$ pasos?

1. 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.

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)

1. a) ¿Cuál es la probabilidad de que cada tiro simulado sea encestado? Explica.

1. b) ¿Qué rango de valores se puede mostrar?

1. 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?

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.

1. a) Explica la diferencia entre un problema decidible y uno indecidible.

1. b) El problema descrito se conoce como el problema de la detención (halting problem). ¿Es posible lo que afirma la empresa? Explica.

1. c) Describe una cosa práctica que los desarrolladores sí pueden hacer para detectar programas que se quedan atascados.

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.

1. a) Calcula el número de rutas para $n = 5$ y $n = 10$. Luego usa $14! = 87{,}178{,}291{,}200$ para $n = 15$.

1. 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.

1. 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).

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.

1. a) Calcula el número de pasos de cada algoritmo cuando $n = 10$ y cuando $n = 1{,}000$.

1. 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$?

1. 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.