PDF de programación - Análisis y Diseño de Algoritmos - Introducción

Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
Introducción
Introducción

Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos

Concepto de algoritmo
 Concepto de algoritmo
 Resolución de problemas
Resolución de problemas
Clasificación de problemas
 Clasificación de problemas
Algorítmica
 Algorítmica
 Análisis de la eficiencia de los algoritmos
 Análisis de la eficiencia de los algoritmos
Análisis de la eficiencia de los algoritmos
Análisis de la eficiencia de los algoritmos
 Técnicas de diseño de algoritmos
Técnicas de diseño de algoritmos

11

Concepto de algoritmo
Concepto de algoritmo

Definición de algoritmo
Definición de algoritmo

Secuencia ordenada de pasos exentos de ambigüedad
Secuencia ordenada de pasos exentos de ambigüedad
tal que, al llevarse a cabo con fidelidad, dará como
tal que, al llevarse a cabo con fidelidad, dará como
resultado que se realice la tarea para la que se ha
resultado que se realice la tarea para la que se ha
resultado que se realice la tarea para la que se ha
resultado que se realice la tarea para la que se ha
diseñado en un tiempo finito.
diseñado en un tiempo finito.

Un algoritmo nos permite obtener
Un algoritmo nos permite obtener

la solución del problema para el que esté diseñado.
la solución del problema para el que esté diseñado.

Concepto de algoritmo
Concepto de algoritmo

Propiedades de un algoritmo
Propiedades de un algoritmo

Finitud::
 Finitud
La ejecución de un algoritmo ha de terminar después
La ejecución de un algoritmo ha de terminar después
de un número finito de etapas.
de un número finito de etapas.
de un número finito de etapas.
de un número finito de etapas.

Precisión::
 Precisión
Cada etapa ha de estar especificado rigurosamente.
Cada etapa ha de estar especificado rigurosamente.
La ejecución de un algoritmo no ha de dejar espacio
La ejecución de un algoritmo no ha de dejar espacio
para la interpretación, la intuición o la creatividad.
para la interpretación, la intuición o la creatividad.

22

33

Concepto de algoritmo
Concepto de algoritmo

Características de un algoritmo
Características de un algoritmo

Entradas::
 Entradas
Un algoritmo tiene cero o más entradas
Un algoritmo tiene cero o más entradas
(cantidades que se le dan inicialmente antes de que comience su ejecución).
(cantidades que se le dan inicialmente antes de que comience su ejecución).

Salidas::
 Salidas
Un algoritmo tiene una o más salidas
Un algoritmo tiene una o más salidas
(cantidades que tienen una relación específica con las entradas).
(cantidades que tienen una relación específica con las entradas).

Resolución de problemas
Resolución de problemas

Resolución de problemas con ordenador:
Resolución de problemas con ordenador:

 Diseñar un algoritmo para el problema.
Diseñar un algoritmo para el problema.

 Expresar el algoritmo como un programa.
 Expresar el algoritmo como un programa.
Expresar el algoritmo como un programa.
Expresar el algoritmo como un programa.

 Ejecutar el programa.
Ejecutar el programa.

44

55

Resolución de problemas
Resolución de problemas

Clasificación de problemas
Clasificación de problemas

Años 30
 Años 30
Problemas computables y no computables.
Problemas computables y no computables.

 Años 50
 Años 50
Años 50
Años 50
Complejidad de los problemas computables
Complejidad de los problemas computables
(búsqueda de algoritmos más eficaces).
(búsqueda de algoritmos más eficaces).

 Años 70
Años 70
Clasificación de los problemas computables: P y NP.
Clasificación de los problemas computables: P y NP.

66

77

Clasificación de problemas
Clasificación de problemas

Clases P y NP
Clases P y NP

 Clase P
Clase P
Problemas resolubles en tiempo polinómico
Problemas resolubles en tiempo
polinómico
con una máquina de
con una máquina de Turing
con una máquina de
con una máquina de Turing
Turing determinística
Turing determinística
determinística
determinística
(esto es, el tiempo de ejecución del algoritmo en un
(esto es, el tiempo de ejecución del algoritmo en un
ordenador viene descrito por una fórmula
ordenador viene descrito por una fórmula polinómica

polinómica).).

 Clase NP

Clase NP [Non
[Non--Deterministic
Polynomial--time]
time]
polinómico
Problemas resolubles en tiempo
Problemas resolubles en tiempo polinómico
determinística..
Turing no no determinística
con una máquina de
con una máquina de Turing

Deterministic Polynomial

Clasificación de problemas
Clasificación de problemas

Clase P ⊆⊆⊆⊆⊆⊆⊆⊆ Clase NP
Clase P
Clase NP

88

99

Clasificación de problemas
Clasificación de problemas

Reducción de problemas y complejidad
Reducción de problemas y complejidad

 Si reducimos un problema (A) a otro (B), podemos
Si reducimos un problema (A) a otro (B), podemos
obtener una solución con un algoritmo para el
obtener una solución con un algoritmo para el
problema B y transformar esa solución para convertirla
problema B y transformar esa solución para convertirla
problema B y transformar esa solución para convertirla
problema B y transformar esa solución para convertirla
en una solución para el problema A.
en una solución para el problema A.

 ¿P=NP?

polinómico. .

Si encontráramos un algoritmo polinómico
polinómico

¿P=NP? Si encontráramos un algoritmo
para un problema NP
para un problema NP--completo, sabríamos que todos
completo, sabríamos que todos
los problemas de la clase NP se pueden resolver en
los problemas de la clase NP se pueden resolver en
tiempo
tiempo polinómico

Algorítmica
Algorítmica

La algorítmica, como disciplina de estudio de los
La algorítmica, como disciplina de estudio de los
algoritmos, ha de considerar:
algoritmos, ha de considerar:

 El diseño de algoritmos.
El diseño de algoritmos.
 El diseño de algoritmos.
El diseño de algoritmos.

 La validación de algoritmos.
La validación de algoritmos.

 El análisis de algoritmos.
El análisis de algoritmos.

1010

1111

Algorítmica
Algorítmica

Diseño de algoritmos
Diseño de algoritmos

 Creación de algoritmos (parte creativa).
Creación de algoritmos (parte creativa).

El diseño de algoritmos no se puede dominar si no se
 El diseño de algoritmos no se puede dominar si no se
 El diseño de algoritmos no se puede dominar si no se
El diseño de algoritmos no se puede dominar si no se
conocen las técnicas de diseño de algoritmos
conocen las técnicas de diseño de algoritmos
(métodos y heurísticas que han demostrado ser útiles
(métodos y heurísticas que han demostrado ser útiles
en la práctica).
en la práctica).

Algorítmica
Algorítmica

Validación de algoritmos
Validación de algoritmos

Demostración de que las respuestas dadas por el
 Demostración de que las respuestas dadas por el
algoritmo son correctas para todas las posibles
algoritmo son correctas para todas las posibles
entradas.
entradas.
entradas.
entradas.

 Único método válido: Demostración formal.
Único método válido: Demostración formal.

1212

1313

Algorítmica
Algorítmica

Análisis de algoritmos
Análisis de algoritmos

 Determinación de los recursos (espacio, tiempo) que
Determinación de los recursos (espacio, tiempo) que
consumen los algoritmos en la resolución de
consumen los algoritmos en la resolución de
problemas.
problemas.
problemas.
problemas.

El análisis de algoritmos permite comparar algoritmos
 El análisis de algoritmos permite comparar algoritmos
alternativos con criterios cuantitativos (y elegir el
alternativos con criterios cuantitativos (y elegir el
algoritmo más adecuado para resolver un problema).
algoritmo más adecuado para resolver un problema).

1414

Análisis de la eficiencia
Análisis de la eficiencia

 Problema

Problema: :
Determinar las características del algoritmo que sirvan
Determinar las características del algoritmo que sirvan
para evaluar su rendimiento.
para evaluar su rendimiento.

p.ej.
p.ej.

Tiempo requerido para la ejecución del
Tiempo requerido para la ejecución del
algoritmo en términos del número de veces
algoritmo en términos del número de veces
algoritmo en términos del número de veces
algoritmo en términos del número de veces
que se ejecuta cada etapa del algoritmo.
que se ejecuta cada etapa del algoritmo.

 Alternativas

Alternativas (complementarias):
(complementarias):
 Enfoque empírico
Enfoque empírico
 Enfoque teórico
Enfoque teórico
 Enfoque híbrido
Enfoque híbrido

1515

Técnicas de diseño
Técnicas de diseño

Ejemplo: Problema del viajante de comercio (TSP)
Ejemplo:
Problema del viajante de comercio (TSP)

532 ciudades

532! soluciones posibles

Solución óptima: 27.686 millas

Técnicas de diseño
Técnicas de diseño

Ejemplo: Problema del viajante de comercio (TSP)
Ejemplo:
Problema del viajante de comercio (TSP)

Si tenemos N ciudades e intentamos solucionar el
Si tenemos N ciudades e intentamos solucionar el
problema por fuerza bruta (comprobando todas las
problema por fuerza bruta (comprobando todas las
soluciones posibles), tendremos que comprobar N!
soluciones posibles), tendremos que comprobar N!
soluciones posibles), tendremos que comprobar N!
soluciones posibles), tendremos que comprobar N!
posibles soluciones.
posibles soluciones.

Se necesitan técnicas que nos permitan
Se necesitan técnicas que nos permitan

diseñar algoritmos eficientes.
diseñar algoritmos eficientes.

1616

1717

Técnicas de diseño
Técnicas de diseño

Ejemplo: Problema del viajante de comercio (TSP)
Ejemplo:
Problema del viajante de comercio (TSP)

17 ciudades

Solución óptima = 226.64

Soluciones posibles = 17! = 355 687 428 096 000

Técnicas de diseño
Técnicas de diseño

Solución aproximada con un algoritmo iterativo:
Solución aproximada con un algoritmo iterativo:

Iteración 0:
Iteración 0:
Mejor solución = 403.7
Mejor solución = 403.7

Iteración 25:
Iteración 25:
Mejor solución = 303.86
Mejor solución = 303.86

17 ciudades

Solución óptima = 226.64

Soluciones posibles = 17! = 355 687 428 096 000

1818

1919