## GLOSARIO

# A

Algoritmo. Conjunto de Instrucciones que especifican la secuencia de operaciones a realizar, en orden, para resolver un sistema específico o clase de problema.

Algoritmos aleatorizados. Se dice que un algoritmo está aleatorizado si su comportamiento es determinado no solo por su entrada, sino por valores producidos por un generador de números aleatorios random(a, b), que produce un entero en el rango [a..b] que tiene la misma probabilidad de aparecer que los otros enteros del rango.

Algoritmos ávidos. Seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución.

Algoritmo determinista. Es un algoritmo cuyo comportamiento está completamente determinado por su entrada.

Algoritmo de Monte Carlo. Con una alta probabilidad encuentra una solución correcta sea cual sea la entrada.

Algoritmo de las Vegas. Toma decisiones al azar para encontrar una solución antes que un algoritmo determinista.

Algoritmo de Sherwood. Existe una solución determinista que es mucho más rápida en media que en el peor caso.

Algoritmos numéricos. La solución obtenida es siempre aproximada pero s precisión esperada mejora aumentado el tiempo de ejecución.

Algoritmos probabilísticos. Algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaletorios.

Algoritmos recursivos. Es aquel que expresa la solución de un problema en términos de una llamada a sí mismo.

Análisis de algoritmos. Parte importante de la Teoría de complejidad computacional más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado.

# B

Bottom-up. Todos los subproblemas que puedan ser necesarios se resuelven de antemano y después son usados para resolver las soluciones a problemas mayores. Este enfoque es ligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

#

# C

Complejidad computacional. Es el tiempo de cálculo y el espacio de memoria requeridos para resolver un determinado problema.

Complejidad temporal. Es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición.

Complejidad espacial. Es la cantidad de memoria que necesita un algoritmo para resolver un problema.

Cota inferior asintótica. Es la complejidad temporal mínima requerida por cualquier algoritmo que pueda aplicarse para resolver un problema.

Cota superior asintótica. Es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito

# D

Divide y vencerás. Estrategia de diseño que divide el problema en subconjuntos disjuntos obteniendo la solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.

#

# E

Ecuación de recurrencia. Es una expresión finita que define implícitamente una sucesión, en la cual un elemento de la sucesión se determina por medio de otros elementos más sencillos, que incluyen casos iniciales o básicos.

#

# F

Fuerza bruta. Es una técnica que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de encontrar el candidato que satisface la solución al mismo.

#

# N

Notación asintótica. Permite representar la complejidad, y por ende la eficiencia, de un algoritmo, de tal manera que se puede proyectar el aumento de operaciones requeridas al aumentar el tamaño de la entrada.

NP. La clase de complejidad de los problemas que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing no-determinista.

NP-Completos. Pueden ser descritos como los problemas en NP que tienen menos posibilidades de estar en P.

#

# P

P. La clase de complejidad de los problemas que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista.

Principio de optimalidad. El principio de optimalidad de Bellman dicta que “dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima”.

Programación dinámica. Intenta resolver problemas disminuyendo su costo computacional aumentando el costo espacial.

#

# R

Recursividad. Consiste en funciones que se llaman a sí mismas, evitando el uso de ciclos y otros iteradores.

Reductibilidad. Es una forma de convertir un problema en otro problema de tal forma que la solución que se le da al segundo problema pueda ser usada para resolver el primero.

#

# T

Teoría de la complejidad computacional. Es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema.

Tiempo polinomial. Un algoritmo de tiempo polinomial es aquel cuya complejidad en el peor caso está acotada por arriba por un polinomio sobre el tamaño de su entrada.

Top-down. El problema se divide en subproblemas, y estos subproblemas se resuelven recordando las soluciones en caso de que sean necesarias nuevamente.Es una combinación de memorización y recursión.

##