Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuál de estos tiempos de ejecución es polinómico?

1. AO(n!)
2. BO(n³)
3. CO(2ⁿ)
4. DO(nⁿ)

¿Qué describe el tiempo de ejecución en el peor caso de un algoritmo?

1. AEl tiempo esperado que tarda con una entrada aleatoria de tamaño n
2. BEl tiempo que tarda con la entrada más pequeña
3. CEl tiempo que tarda en un ordenador lento
4. DEl tiempo máximo que tarda entre todas las entradas de tamaño n

¿Cuánto vale log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Con monedas de 1, 3 y 4 y una cantidad de 6, ¿cuántas monedas usa el método voraz de «la moneda más grande primero», comparado con el óptimo?

1. AEl voraz usa 3 monedas; el óptimo es 2
2. BEl voraz usa 2 monedas; el óptimo es 2
3. CEl voraz usa 4 monedas; el óptimo es 3
4. DEl voraz usa 3 monedas; el óptimo es 3

¿Por qué la programación dinámica no aporta ninguna mejora real a merge sort?

1. ALa programación dinámica solo funciona con problemas de grafos, no con arreglos
2. BSus subproblemas no se solapan, así que no hay nada que reutilizar
3. CMerge sort no tiene estructura recursiva
4. DMerge sort ya es O(n)

¿Qué algoritmo de ordenación es estable?

1. AMerge sort
2. BOrdenamiento por selección (versión habitual)
3. CHeap sort
4. DQuicksort (versión in situ habitual)

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

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

El algoritmo de programación dinámica de Held-Karp resuelve exactamente el problema del viajante. ¿Cuál es su tiempo de ejecución para n ciudades?

1. AO(n!)
2. BO(n³)
3. CO(n² 2ⁿ)
4. DO(2^n²)