Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es un algoritmo de fuerza bruta?

1. AUno que siempre usa recursión
2. BUno que adivina una respuesta al azar
3. CUno que prueba todas las soluciones candidatas posibles
4. DUno que se ejecuta en muchos procesadores

¿Qué significa f(n) = Θ(g(n))?

1. Af crece estrictamente más deprisa que g
2. Bf crece estrictamente más despacio que g
3. Cf es siempre menor que g para todo n, así que g la acota por arriba pero nunca por abajo
4. Df crece al mismo ritmo que g, acotada por arriba y por abajo por múltiplos constantes de g

¿Cuánto vale log₂ 1024?

1. A512
2. B32
3. C10
4. D12

¿Aproximadamente cuántas comparaciones necesita la búsqueda binaria en el peor caso en un array ordenado de 1,000,000 de elementos?

1. AUnas 100
2. BUnas 500,000
3. CUnas 20
4. DUnas 1,000

¿Qué mide el análisis amortizado?

1. AEl coste esperado con entradas aleatorias
2. BEl coste de la única operación más cara de toda la secuencia
3. CEl coste de un algoritmo con la mejor entrada
4. DEl coste medio por operación a lo largo de una secuencia de operaciones del peor caso

¿Cuál es la complejidad temporal de: para i = 1 hasta n: (j = 1; mientras j < n: j = j × 2)?

1. AO(n²)
2. BO(n log n)
3. CO(n)
4. DO(log n)

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}), aproximadamente n^2,81

¿Cuál es la diferencia entre un problema indecidible y uno intratable?

1. AAmbos significan que el problema no tiene ningún algoritmo
2. BLos problemas intratables no pueden resolverse con ningún algoritmo, mientras que los indecidibles solo necesitan tiempo exponencial
3. CLos problemas indecidibles están en NP, mientras que los intratables están en P
4. DUn problema indecidible no tiene ningún algoritmo que sirva para todas las entradas; uno intratable sí lo tiene, pero es demasiado lento