Tema1 Flashcards
(31 cards)
¿Qué significa que un problema sea de clase NP?
Significa que no se conoce un algoritmo que lo resuelva en tiempo polinómico, pero se puede verificar una solución en tiempo polinómico.
Explica la diferencia entre un algoritmo exacto y uno aproximado.
Un algoritmo exacto encuentra la solución óptima, mientras que uno aproximado da una buena solución cercana al óptimo sin garantizarlo.
¿Cuál de las siguientes es una característica de los algoritmos heurísticos?
a) Garantizan la solución óptima
b) No siempre conocemos su grado de aproximación
c) Siempre son rápidos
b) No siempre conocemos su grado de aproximación
¿Qué se considera una operación elemental (OE) en el análisis de algoritmos?
Son operaciones básicas como sumas, restas, asignaciones, saltos, y comparaciones que consumen una unidad constante de tiempo.
Describe qué es un algoritmo de orden constante O(1).
Es un algoritmo cuyo tiempo de ejecución no depende del tamaño de los datos de entrada, ejecutándose siempre con el mismo número de operaciones.
Explica qué son los algoritmos heurísticos y cuándo se utilizan.
Son algoritmos que ofrecen soluciones aproximadas para problemas complejos donde no se puede determinar si son óptimas globales. Se usan cuando no hay soluciones prácticas conocidas.
Explica el proceso de desarrollo de un algoritmo.
Incluye modelar el problema, diseñar el algoritmo con técnicas adecuadas, analizar su eficiencia y, si es necesario, revisarlo para optimizar resultados.
¿Qué indica la notación O(f) en complejidad?
Representa el orden de complejidad de un algoritmo, indicando cómo escala su tiempo de ejecución en función del tamaño de entrada.
Detalla cómo se evalúa el tiempo de ejecución de un algoritmo.
Se analiza mediante operaciones elementales (OE) que incluye sumas, multiplicaciones, asignaciones, y más, asegurando independencia del procesador.
Explica la diferencia entre los casos más favorable, promedio y más desfavorable en análisis de complejidad.
Se refieren al tiempo de ejecución mínimo, promedio y máximo respectivamente, considerando todas las posibles entradas de datos.
Describe el propósito de la optimización multiobjetivo.
Busca encontrar soluciones aceptables para varios objetivos simultáneamente, como minimizar tiempo y costo, ofreciendo un conjunto de soluciones óptimas.
Explica la diferencia entre algoritmos deterministas y probabilistas.
Los deterministas producen siempre el mismo resultado para una misma entrada, mientras que los probabilistas pueden generar resultados diferentes debido a la aleatoriedad.
¿Cómo se mide la eficiencia de un algoritmo?
Se mide por el tiempo y el espacio que necesita para ejecutarse, en función del tamaño de entrada.
Describe el concepto de complejidad computacional.
Es el estudio del rendimiento de algoritmos considerando tiempo y espacio, categorizando problemas según sus requisitos de recursos.
¿Qué es el óptimo de Pareto?
Es un conjunto de soluciones donde no se puede mejorar un objetivo sin perjudicar a otros.
¿Cuál de las siguientes opciones describe un algoritmo?
a) Proceso desordenado
b) Conjunto de reglas finitas y ordenadas
c) Resultado de cálculos matemáticos
b) Conjunto de reglas finitas y ordenadas
¿Cuál es la característica principal de los algoritmos probabilistas?
a) Siempre producen la misma solución
b) Incorporan aleatoriedad
c) No son prácticos
b) Incorporan aleatoriedad
¿Qué tipo de análisis mide el tiempo de ejecución después de la ejecución?
a) Teórico
b) Real
c) Promedio
b) Real
¿Qué tipo de complejidad tiene el peor rendimiento?
a) Constante
b) Exponencial
c) Logarítmica
b) Exponencial
Un algoritmo determinista ________ produce la misma solución para los mismos valores de entrada.
siempre.
El propósito de los algoritmos es encontrar ________ computacionales para resolver problemas.
soluciones.
Los algoritmos ________ no dependen del tamaño de los datos de entrada.
de orden constante.
La clase de problemas llamada ________ incluye problemas que pueden verificarse en tiempo polinómico pero no necesariamente resolverse.
NP.
¿Es cierto que un algoritmo siempre tiene pasos establecidos?
Sí, siempre tienen pasos claramente establecidos.
