Matematicas Discretas - Actividad en clase - 03 Abril 2025

¿Cuál de las siguientes es una proposición lógica?

• ¡Cierra la puerta!
• ¿Qué hora es?
• La Tierra gira alrededor del Sol.
• ¡Qué sorpresa!

¿Qué es la tratabilidad de un problema en computación?

• La posibilidad de resolver un problema en tiempo razonable con un algoritmo
• La facilidad de representar un problema gráficamente
• La capacidad de resolver un problema sin errores
• La dificultad de traducir un algoritmo a código

¿Qué se entiende por la complejidad temporal de un algoritmo?

• El número de líneas de código
• El tiempo que tarda en compilar
• La cantidad de memoria que usa
• La cantidad de tiempo que consume al ejecutarse en función del tamaño de la entrada

¿Cuál de las siguientes clases de complejidad representa un algoritmo con crecimiento constante?

• O(n)
• O(1)
• O(n²)
• O(2ⁿ)

¿Qué representa O(n) en la notación Big-O?

• Tiempo constante
• Tiempo cuadrático
• Tiempo lineal
• Tiempo exponencial

¿Cuál es la complejidad temporal de un algoritmo que compara todos los pares posibles en una lista?

• O(1)
• O(n)
• O(log n)
• O(n²)

¿Qué implica que un problema sea P (polinomialmente tratable)?

• Que solo puede resolverse con algoritmos recursivos
• Que tiene una solución aproximada
• Que existe un algoritmo que lo resuelve en tiempo polinómico
• Que su solución no puede verificarse

¿Cuál es la complejidad de un algoritmo que ejecuta una instrucción única, sin importar el tamaño de la entrada?

• O(n)
• O(1)
• O(n²)
• O(log n)

Si un algoritmo tiene complejidad O(n²), ¿cómo crecerá su tiempo de ejecución si se duplica el tamaño de la entrada?

• Se cuadruplicará
• Se duplicará
• Se mantendrá igual
• Se reducirá a la mitad

¿Qué ocurre con el tiempo de ejecución de un algoritmo de complejidad O(n!) al aumentar ligeramente el tamaño de entrada?

• Aumenta de forma extrema
• No cambia
• Aumenta de forma moderada
• Disminuye debido al factorial