AAED Examen Final (Teoría) UCA Puerto Real

¿Qué diferencia fundamental hay entre problema, algoritmo y programa?. El problema define qué se quiere resolver; el algoritmo cómo resolverlo de forma abstracta; el programa cómo implementarlo en una máquina real. El problema describe el lenguaje; el algoritmo la máquina; el programa el resultado final. El algoritmo define el problema; el programa es una versión informal del algoritmo. Problema y algoritmo son equivalentes; el programa solo añade sintaxis.

¿Cómo se define formalmente un problema en este contexto?. Como una función que transforma entradas en salidas. Como un conjunto de instrucciones ejecutables en una máquina. Como una secuencia finita de pasos ordenados. Como un programa independiente del lenguaje.

¿Qué caracteriza a un algoritmo frente a un programa?. Es abstracto, independiente de lenguaje y máquina, y consiste en una secuencia finita de instrucciones. Está escrito en un lenguaje concreto y se ejecuta directamente. Depende de la arquitectura hardware utilizada. Solo puede expresarse mediante código fuente compilable.

¿Por qué un programa depende necesariamente de un algoritmo correcto y eficiente?. Porque un programa hereda la corrección y eficiencia del algoritmo que implementa. Porque el compilador optimiza automáticamente cualquier programa. Porque la eficiencia depende solo del lenguaje de programación. Porque la máquina garantiza resultados correctos si el programa termina.

¿Para qué se utiliza el Lenguaje de Especificación de Algoritmos (LEA)?. Para describir algoritmos de forma concisa, abstracta y con semántica bien definida. Para programar algoritmos directamente en código ejecutable. Para medir el tiempo real de ejecución de un programa. Para optimizar algoritmos a bajo nivel.

¿Qué tipos de construcciones básicas permite LEA?. Asignación (normal y paralela), condición e iteración. Clases, objetos y herencia. Funciones recursivas y estructuras dinámicas. Entrada/salida y manejo de memoria.

¿Por qué LEA es preferible a lenguajes informales para describir algoritmos?. Porque evita ambigüedades y define claramente el significado de cada instrucción. Porque es más cercano a los lenguajes de programación reales. Porque permite ejecutar directamente los algoritmos. Porque reduce el número de instrucciones necesarias.

¿Qué preguntas responde la corrección algorítmica?. Si el algoritmo termina y si, cuando termina, produce el resultado correcto. Cuánto tiempo tarda en ejecutarse en una máquina concreta. Qué lenguaje es más eficiente para implementarlo. Cuánta memoria ocupa el programa final.

¿Qué diferencia hay entre parada y corrección parcial?. La parada asegura que el algoritmo termina; la corrección parcial que el resultado es correcto si termina. La parada garantiza resultados correctos; la corrección parcial garantiza eficiencia. Ambas significan exactamente lo mismo. La corrección parcial analiza el tiempo y la parada el espacio.

¿Qué recursos se analizan principalmente en la eficiencia algorítmica?. Tiempo y espacio, a nivel abstracto. Tiempo real de ejecución y consumo eléctrico. Número de líneas de código y lenguaje usado. Velocidad del procesador y memoria física.

¿Por qué el análisis se hace sobre algoritmos y no solo sobre programas?. Porque el comportamiento esencial no depende del lenguaje ni de la máquina concreta. Porque los programas no pueden analizarse formalmente. Porque los algoritmos siempre son más rápidos que los programas. Porque el hardware elimina las diferencias de eficiencia.

¿Qué ilustra el ejemplo de la multiplicación rusa?. La diferencia entre algoritmo abstracto y su implementación concreta en un programa. Una optimización específica de bajo nivel. Un caso donde programa y algoritmo coinciden exactamente. Una técnica dependiente del lenguaje de programación.

¿Por qué distintos programas pueden implementar el mismo algoritmo?. Porque el algoritmo es independiente del lenguaje y de la sintaxis concreta. Porque todos los lenguajes tienen la misma sintaxis. Porque el compilador unifica todos los programas. Porque los programas no afectan al resultado.

¿Qué afirma el principio de invarianza?. Que dos programas del mismo algoritmo sólo difieren en tiempo por un factor constante. Que todos los algoritmos tienen el mismo tiempo de ejecución. Que cambiar el lenguaje cambia el orden de eficiencia. Que el hardware no influye en absoluto.

¿Cuándo deja de cumplirse el principio de invarianza?. Si se cambia el algoritmo o se altera radicalmente la arquitectura de la máquina. Cuando se optimiza el código fuente. Cuando se usa otro compilador. Cuando el tamaño de entrada es pequeño.

¿Qué implicación tiene este principio para la optimización de programas?. Que las mejoras de bajo nivel no cambian el orden de eficiencia del algoritmo. Que optimizar el código siempre mejora el orden asintótico. Que la optimización elimina la necesidad de analizar algoritmos. Que solo importa el lenguaje usado.

¿Qué significa que dos algoritmos tengan el mismo orden?. Que sus tiempos de ejecución difieren solo por constantes multiplicativas. Que ejecutan exactamente el mismo número de instrucciones. Que producen los mismos resultados. Que usan el mismo lenguaje de programación.

¿Por qué esta definición se considera informal o imprecisa?. Porque requiere una formalización mediante tiempo algorítmico y orden asintótico. Porque no se puede medir el tiempo de ejecución. Porque depende del hardware concreto. Porque los algoritmos no pueden compararse.

¿Por qué se introduce el concepto de orden asintótico en el análisis de algoritmos?. Para comparar eficiencias ignorando constantes y detalles de implementación. Para medir el tiempo real de ejecución en una máquina concreta. Para optimizar programas a bajo nivel. Para contar exactamente el número de instrucciones ejecutadas.

¿Qué papel juega el principio de invarianza en el uso de órdenes asintóticos?. Justifica que solo importa el crecimiento del algoritmo, no la máquina ni el programa. Garantiza que todos los algoritmos tienen el mismo tiempo de ejecución. Permite ignorar completamente el tamaño de la entrada. Afirma que el lenguaje de programación no influye en la eficiencia real.

¿Cómo se relaciona la eficiencia de un algoritmo con el tamaño de la entrada?. Mediante funciones que asignan a cada tamaño un consumo de recursos. Mediante el tiempo real medido en segundos. Mediante el número de líneas de código. Mediante la velocidad del procesador utilizado.

¿Qué expresa intuitivamente que un algoritmo sea O(f(n))?. Que su tiempo crece, como máximo, proporcionalmente a f(n). Que su tiempo crece exactamente como f(n). Que su tiempo nunca supera un valor constante. Que su tiempo depende del peor programa posible.

¿Qué significa que la definición de O sea asintótica?. Que solo importa el comportamiento para n suficientemente grande. Que se aplica solo a valores pequeños de n. Que tiene en cuenta constantes y detalles de implementación. Que describe el tiempo exacto de ejecución.

¿Por qué las constantes y los valores pequeños de n no son relevantes en O?. Porque quedan absorbidos por los multiplicadores y el umbral n₀. Porque no pueden medirse con precisión. Porque siempre son despreciables en cualquier caso. Porque solo se analizan entradas unitarias.

¿Qué relación existe entre pertenencia f ∈ O(g) y contención de conjuntos?. f ∈ O(g) equivale a O(f) ⊆ O(g). f ∈ O(g) implica que f = g. O(g) ⊆ O(f) siempre que f ∈ O(g). No existe relación formal entre ambas.

¿Qué tipo de relación induce O entre funciones de coste?. Un preorden reflexivo y transitivo, pero no total. Una relación de equivalencia. Un orden total estricto. Una relación antisimétrica y total.

¿Por qué multiplicar por una constante no cambia el orden asintótico?. Porque las constantes quedan absorbidas en la definición de O. Porque las constantes siempre valen 1. Porque el tiempo real no depende de constantes. Porque el compilador elimina las constantes.

¿Por qué O(f + g) se simplifica como O(max{f, g})?. Porque el término dominante controla el crecimiento. Porque siempre se pueden sumar las funciones. Porque f y g crecen al mismo ritmo. Porque max{f, g} es siempre mayor que f + g.

¿Cómo se puede comparar el orden de dos funciones usando límites?. Analizando el límite del cociente f(n)/g(n). Comparando sus valores para n = 1. Midiendo el tiempo de ejecución real. Sumando ambas funciones.

¿Qué idea transmite la jerarquía de complejidad entre funciones?. Que algunos crecimientos son inherentemente mucho más rápidos que otros. Que todas las funciones pueden optimizarse al mismo nivel. Que la eficiencia depende solo del hardware. Que las funciones polinómicas y exponenciales son equivalentes.

¿Por qué los algoritmos exponenciales son impracticables para n grandes?. Porque su tiempo crece demasiado rápido incluso con pequeñas entradas. Porque no pueden implementarse en lenguajes reales. Porque consumen siempre memoria infinita. Porque solo funcionan para n pequeño por definición.

¿Qué nos enseñan las tablas sobre duplicar tiempo o tamaño de entrada?. Que el impacto depende críticamente del orden asintótico del algoritmo. Que duplicar la entrada siempre duplica el tiempo. Que el tiempo real es impredecible. Que el hardware elimina las diferencias.

¿Qué expresa intuitivamente que un algoritmo sea Ω(f(n))?. Que su tiempo crece al menos proporcionalmente a f(n). Que su tiempo crece como máximo f(n). Que su tiempo es exactamente f(n). Que su tiempo no depende de n.

¿Qué relación de dualidad existe entre O y Ω?. f ∈ O(g) si y solo si g ∈ Ω(f). O y Ω son equivalentes siempre. Ω es un subconjunto de O. No existe relación formal entre ambas.

¿Qué significa que un algoritmo sea Θ(f(n))?. Que su tiempo está acotado superior e inferiormente por f(n). Que su tiempo es menor que f(n). Que su tiempo es mayor que f(n). Que su tiempo depende del lenguaje usado.

¿Cómo se relacionan Θ, O y Ω entre sí?. Θ(f) = O(f) ∩ Ω(f). Θ(f) = O(f) ∪ Ω(f). O(f) = Θ(f) ∪ Ω(f). Ω(f) = O(f) − Θ(f).

¿Qué tipo de relación induce Θ entre funciones?. Una relación de equivalencia: mismo orden de crecimiento. Un orden total. Un preorden parcial. Una relación antisimétrica.

¿Qué significa operar órdenes asintóticos (suma o producto)?. Combinar funciones representativas de cada orden de forma consistente. Sumar tiempos reales de ejecución. Mezclar algoritmos distintos. Calcular el tiempo exacto del programa.

¿Por qué O(f) + O(g) = O(f + g) y O(f) · O(g) = O(f·g)?. Porque las operaciones se trasladan al crecimiento dominante. Porque siempre se suman y multiplican constantes. Porque O elimina cualquier término no lineal. Porque f y g siempre son comparables.