Análisis y Diseño de Algoritmos
Introducción
Análisis y Diseño de Algoritmos
Concepto de algoritmo
Resolución de problemas
Clasificación de problemas
Algorítmica
Análisis de la eficiencia de losalgoritmos
Técnicas de diseño de algoritmos
1
Concepto de algoritmo
Definición de algoritmo
Secuencia ordenada de pasos exentos de ambigüedad
tal que, al llevarse a cabo con fidelidad, dará comoresultado que se realice la tarea para la que se ha
diseñado en un tiempo finito.
Un algoritmo nos permite obtener
la solución del problema para el que esté diseñado.
2
Concepto de algoritmo
Propiedadesde un algoritmo
Finitud:
Finitud:
La ejecución de un algoritmo ha de terminar después
de un número finito de etapas.
Precisión:
Precisión:
Cada etapa ha de estar especificado rigurosamente.
Laejecución de un algoritmo no ha de dejar espacio
para la interpretación, la intuición o la creatividad.
3
Concepto de algoritmo
Características de un algoritmo
Entradas:
Entradas:
Un algoritmo tiene cero omás entradas
(cantidades que se le dan inicialmente antes de que comience su ejecución).
Salidas:
Salidas:
Un algoritmo tiene una o más salidas
(cantidades que tienen una relación específica con lasentradas).
4
Resolución de problemas
Resolución de problemas con ordenador:
Diseñar un algoritmo para el problema.
Expresar el algoritmo como un programa.
Ejecutar el programa.
5
Resolución deproblemas
6
Clasificación de problemas
Años 30
Problemas computables y no computables.
Años 50
Complejidad de los problemas computables
(búsqueda de algoritmos más eficaces).
Años 70
Clasificación delos problemas computables: P y NP.
7
Clasificación de problemas
Clases P y NP
Clase P
Problemas resolubles en tiempo polinómico
con una máquina de Turing determinística
(esto es, el tiempo deejecución del algoritmo en un
ordenador viene descrito por una fórmula polinómica).
polinómica).
Clase NP [Non
[Non–Deterministic PolynomialPolynomial-time]
Problemas resolubles en tiempo polinómico…
