Algoritmos

Que es un Algoritmo?

Complejidad de los Algoritmos

Webster: cualquier método especial para resolver cierta
clase de problemas.
Horowitz: método preciso utilizable en una computadora
para lasolución de un problema.

CONJUNTO FINITO DE PASOS UTILIZADO POR UNA
COMPUTADORA PARA RESOLVER UN PROBLEMA

Preguntas
¿Para todos los problemas, existe al menos un algoritmo?
Si existen variosalgoritmos para un problema, ¿Cómo
hacer una selección en términos de eficiencia?

Características de los Algoritmos
•Cada paso requiere una o más operaciones
• Operaciones definida (Noambiguas):
> 5/0, 6 + 7 ó tal vez 8: No se permiten
• Cada paso puede realizarse en una cantidad finita de tiempo.
•Un algoritmo produce una o más salidas y requiere cero o más
entradas (externas).
• Unalgoritmo siempre termina en un número finito de pasos

Características

Áreas de Estudio de los Algoritmos

Sin ambigüedad.
Efectividad: tiempo finito de cómputo.
Computabilidad. Alg que seamás listo que los
humanos
Complejidad.
Claridad: programación estructurada.

Análisis de Algoritmos

¿Cómo construir Algoritmos? -->Enfoques
Divide y vencerás, Programación dinámica,
Exacta,estocástica, de vecindades,…
¿Cómo expresar algoritmos? -->Enfoques
Programación estructurada, de objetos, de
agentes, funcional, lógica,..
¿Cómo validar algoritmos? -->Caminatas,
verificaciónformal,…-->¿Cómo probar un programa?
¿Cómo analizar algoritmos? -->Complejidad
computacional, amigabilidad, robustez,..

Tareas en el Análisis de Algoritmos
Determinar qué operaciones se emplean ysu costo
relativo.

Estudia la complejidad espacial y
temporal de los algoritmos

Determinar conjuntos de datos para exhibir todos los
patrones posibles de comportamiento.

Y las otraspropiedades relevantes!!!

Análisis a priori: se determina una función (de ciertos
parámetros) que acote el tiempo de cómputo del
algoritmo.
Análisis a posteriori: estadísticas reales sobre tiempo y...