Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Qué es un algoritmo?

1. AUna secuencia finita de pasos bien definidos que resuelve un problema
2. BUn lenguaje de programación diseñado para escribir fórmulas matemáticas
3. CUna estructura de datos que almacena números
4. DCualquier programa informático con interfaz gráfica

Un problema suele llamarse tratable si:

1. APuede resolverse en tiempo polinómico
2. BNo tiene solución
3. CSolo puede resolverse probando todas las posibilidades
4. DPuede resolverse en tiempo constante

¿Qué algoritmo de ordenación intercambia repetidamente elementos adyacentes que están en el orden incorrecto?

1. AOrdenamiento por montículos (heap sort)
2. BQuicksort
3. COrdenamiento de burbuja (bubble sort)
4. DOrdenamiento por mezcla (merge sort)

¿Es correcto decir que un algoritmo O(n²) también es O(n³)?

1. ASí, pero solo si n es menor que 100
2. BNo, porque n³ es menor que n² para n grande
3. CNo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función
4. DSí, porque O grande es una cota superior y n² no crece más deprisa que n³

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 4 monedas; el óptimo es 3
2. BEl voraz usa 3 monedas; el óptimo es 2
3. CEl voraz usa 3 monedas; el óptimo es 3
4. DEl voraz usa 2 monedas; el óptimo es 2

¿Por qué muchas rutinas de ordenación de las bibliotecas cambian al ordenamiento por inserción para subarrays muy pequeños?

1. AEl ordenamiento por inserción es O(n log n) en el peor caso
2. BLos algoritmos recursivos no pueden tratar arrays de menos de 10 elementos
3. CEl ordenamiento por inserción tiene poca sobrecarga y es rápido con entradas pequeñas o casi ordenadas
4. DEl ordenamiento por inserción usa menos memoria que cualquier otro algoritmo de ordenamiento con entradas grandes

¿Qué definición de la clase P es correcta?

1. AProblemas cuyas soluciones pueden comprobarse, pero nunca hallarse, en tiempo polinómico
2. BProblemas que necesitan tiempo exponencial en cualquier ordenador
3. CProblemas de decisión resolubles por un algoritmo determinista en tiempo polinómico
4. DProblemas que pueden resolverse en paralelo

El ordenamiento por inserción se ejecuta en O(n) con una entrada ordenada. ¿Contradice esto la cota inferior Ω(n log n) de la ordenación por comparaciones?

1. ANo, la cota inferior se aplica al peor caso entre todas las entradas, no a cada entrada
2. BNo, porque el ordenamiento por inserción no es una ordenación por comparaciones
3. CSí, pero solo para arrays de menos de 100 elementos
4. DSí, así que la cota inferior es errónea