1/56 Lógica Proposicional Ing. Samuel Oporto Díaz (Msc) INTELIGENCIA ARTIFICIAL.
Mg. Samuel Oporto Díaz Complejidad Computacional SISTEMAS INTELIGENTES.
-
Upload
ynez-solar -
Category
Documents
-
view
22 -
download
3
Transcript of Mg. Samuel Oporto Díaz Complejidad Computacional SISTEMAS INTELIGENTES.
Mg. Samuel Oporto Díaz
Complejidad Computacional
SISTEMAS INTELIGENTES
22/60/60
Mapa Conceptual del Curso
33/60/60
COMPLEJIDAD ALGORITMICA
44/60/60
Algoritmo• Un algoritmo es un procedimiento
computacional bien definido, que toma un conjunto de valores de entrada y produce valores de salida.
• También podemos ver a un algoritmo como una herramienta para resolver un problema computacional específico.
55/60/60
Complejidad• La complejidad de un
algoritmo es una medida de la cantidad de recursos que consume.
• Recurso:– Tiempo– Espacio
• Memoria• Disco
66/60/60
Utilidad del Análisis Cuando desarrollamos un algoritmo nos interesados en:
– Tener un idea qué tan bien puede esperarse que trabaje – Cómo se compararía con el desempeño de otros
algoritmos en el mismo problema.
• El análisis de un algoritmo nos puede ayudar a comprenderlo mejor, y nos puede sugerir mejoras.
• Entre más complicado sea un algoritmo, más complicado es su análisis.
77/60/60
Ejemplo 1
Calcular la complejidad de un algoritmo para encontrar el mayor valor en un arreglo de tamaño N.
public class buscador {
public static int busca_max(int L[]) { int Max = L[0];
for (int i = 1; i < L.length; i++) { if (L[i] > Max) { Max = L[i]; } } return Max; }
public static void main(String[] args) { int L[] = { 3, 6, 1, 8, 4, 2, 8, 4, 9, 23, 5, 3 }; int Max; Max = busca_max(L); System.out.println(Max); }}
88/60/60
Ejemplo 1• En el mejor de los casos
• En el caso promedio
• En el peor de los casos
99/60/60
Complejidad• ¿Qué medimos?:
– Tiempo de ejecución
• ¿De qué depende?: – Tamaño de la entrada – Otros factores (HW y SW)
• Velocidad de la máquina • Calidad del compilador • Calidad del programa
• ¿ Cómo medirlo?: – Experimentalmente – Estimándolo matemáticamente
1010/60/60
Medición Experimental• Midiendo el tiempo de ejecución en función del tamaño de
la entrada – No podemos probar con todas las entradas – Es necesario implementar el algoritmo – Depende del software y el hardware
• Busquemos otra medida – Más abstracta – Más fácil de obtener
1111/60/60
Estimación Matemática• Asociamos a cada algoritmo una función f(n) • Emplearemos el caso peor para caracterizar el tiempo de
ejecución • Es más fácil de calcular • Interesa la velocidad de crecimiento del tiempo de
ejecución en función del tamaño de la entrada • Comportamiento asintótico • Asociamos a cada operación primitiva un tiempo de
ejecución constante: – Asignación - Llamada a método
– Operación aritmética - Indexación en array
– Seguir una referencia - Volver de un método
– Etc.
1212/60/60
Ejemplo 2
Calcular la complejidad de un algoritmo para ecalcular el factorial de un número N.
public static int iterative(int n) { int fact = 1; for (int i = 1; i <= n; i++) fact *= i; return fact;}
1313/60/60
Ejemplo 3Calcular la complejidad de un algoritmo para calcular la serie de fibonacci
public class fibonacci { public static long fibonacci_multiple(long N) { if (N <= 1) return 1; else return fibonacci_multiple(N - 1) + fibonacci_multiple(N - 2); }
} public static void main(String[] args) { long F1; F1 = fibonacci_multiple(10); System.out.println(F1);}}
1414/60/60
Ejemplo 3
1515/60/60
Ejemplo 3• f(n)= 1+f(n-1)+ f(n-2) n ≥ 2∀• Puede observarse que f(n) es una función creciente a partir
de n ≥ 2 y entonces, para esos valores, se satisface:• f(n)= 1+f(n-1)+ f(n-2) > 2 f(n-2)
• y aplicando esta misma propiedad a f(n-2) y sucesivos f(n-i) deberíamos tener que:
• f(n) >2·2·f(n-4) > 2·2·2·f(n-6)>...> 2 i f(n-2i) > 2 [n/2]
• por inducción n, f(n) > 2 [n/2] para todo n ≥ 2.
1616/60/60
Tiempo de cálculo• Asumiendo que cada término se puede calcular en 1 nano
segundo (10-9 segundos)
1717/60/60
Ejemplo 4
Calcular la complejidad de un algoritmo para calcular la serie de fibonacci
public class fibonacci { public static long fibonacci_iterativo(long N) { if (N <= 1) { return 1; } else { int n0 = 1, n1 = 1, n2 = 0; for (int i = 1; i < N; i++) { n2 = n1 + n0; n0 = n1; n1 = n2; } return n2; } } public static void main(String[] args) { long F2; F2 = fibonacci_iterativo(10); System.out.println(F2); }}
1818/60/60
NOTACION O()
1919/60/60
Complejidad asintótica• Cuando se hace el análisis teórico de algoritmos es común
calcular su complejidad en un sentido asintótico, es decir, para una tamaño de entrada suficientemente grande.
• En el caso de la búsqueda binaria, el algoritmo se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico".
• Las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia.
• La eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.
2020/60/60
Complejidad Asintótica
2121/60/60
Complejidad Asintótica• Para un n suficientemente grande, el valor de la función
está completamente determinado por su término dominante.
• El valor del coeficiente del término dominante no se conserva al cambiar de máquina.
• Los valores pequeños de N generalmente no son importantes.
2222/60/60
Ejemplos
2323/60/60
Tamaño máximo de un problema
• Suponernos que cada operación puede realizarse en 1 μ s.
2424/60/60
LogaritmosNotación:
log n = log 2 n
ln n = log e n
Propiedades:
a = b log b a,
log c (ab) = log ca + log c b
log b a n = n log b a
log b a = log c a / log c b,
log b (1/a) = - log b a,
log b a = 1 / log a b,
a log b n = n log b a
2525/60/60
Notación O()• 7n-3 es O(n)
– c=7, n0=1 – 7n-3 ≤ 7n
• 20n3 + 10N log(n) +5 es O(n3)
• 3log(n) + Iog(log(n)) es O(log(n))
• 2100 es O(1)
• 5/n es O(1/n)
• log n O(n), > 0
• nk O(c n),c > 1
2626/60/60
Ejercicio 5• Ordenar las siguientes funciones con respecto de su orden
de crecimiento.– log n – 4 log n – 2 n
– 22 – 1/n– (3/2) n
2727/60/60
Ejercicio 6• Ordenar las siguientes funciones con respecto de su orden
de crecimiento.
2 (log n)/2 log( log n) n n3
en n ! n log(log n) n log n
(3/2) n 2 log n n2 n 2 n
2 n 2 2 4 log n (n+1) !
n 1/log n (log n) ½ log n 2 2n +1
2828/60/60
Orden de magnitud de un algoritmo• Tiempos más comunes de los algoritmos:• O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)
2929/60/60
CLASES DE PROBLEMAS
3030/60/60
Clases P y NP • Un problema pertenece a la clase P si puede ser resuelto en
tiempo polinomial en una computadora determinística.
• Ejemplos: Quicksort, búsqueda binaria, multiplicación matricial.
• Problema NP: puede ser resuelto en tiempo polinomial pero usando una computadora no determinística
3131/60/60
P vs NP• La clase P contiene problemas que pueden resolverse
rápidamente.
• La clase NP contiene problemas cuya solución puede verificarse rápidamente.
• En 1971 se planteó la pregunta: ¿Es P = NP? Desde entonces, sigue siendo una pregunta abierta para los teóricos.
• Se cree que P != NP
3232/60/60
Problemas NP Completos
• Todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con respecto al tamaño de la entrada.
• Todos los algoritmos requeridos para resolverlos requieren tiempo exponencial en el peor caso.
• Es decir, son sumamente difíciles de resolver.
• Ejemplos: el problema del agente viajero, O(n22n)
3333/60/60
Problemas NP-completo• En teoría de la complejidad computacional, la clase de
complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo.
• Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P.
• La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico.
3434/60/60
Ejemplo• Suma de subconjuntos:
• Dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos sumen cero?
• Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos los 2n-1 subconjuntos posibles hasta encontrar uno que cumpla con la condición.
3535/60/60
Soluciones aproximadas• Se desconoce si hay mejores algoritmos, por la cual, para
resolver un problema NP-completo de tamaño arbitrario se utiliza uno de los siguientes enfoques:
• Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen buenos algoritmos de aproximación.
• Probabilístico: Un algoritmo probabilístico obtiene en promedio una buena solución al problema planteado, para una distribución de los datos de entrada dada.
• Casos particulares: Cuando se reconocen casos particulares del problema para los cuales existen soluciones rápidas.
• Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta.
• Algoritmo genético: Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta.
3636/60/60
Soluciones aproximadas• Un problema de decisión C es NP-completo si
– es un problema NP y – todo problema de NP se puede transformar polinomialmente en él.
• Una transformación polinomial de L en C es un algoritmo determinista que transforma instancias de l L en ∈instancias de c C, tales que la respuesta a c es positiva ∈si y solo si la respuesta a l lo es.
• Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP.
3737/60/60
Problemas NP-completo• Esta definición fue propuesta por Cook en 1971.
• Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo.
• Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo.
3838/60/60
TRATABILIDAD DE LOS PROBLEMAS
3939/60/60
Clases de problemas• Muchos problemas se resuelven con algoritmos
polinómicos (O(nk)): problemas tratables
• Hay problemas que no se pueden resolver: problema de la parada.
• Hay problemas que no se pueden resolver en tiempo polinónico ((nk)): problemas intratables
4040/60/60
Problema de la parada• No existe ningún algoritmo que diga si un programa va a
parar en tiempo finito con una entrada dada:– Supongamos que hay una función H(P,I) que lo
resuelve.– Construimos D(P):
If H(P,P) then loop forever
else stop– ¿Qué debe hacer D(D)?
4141/60/60
Problemas NP-completos• Hay una clase de problemas que no se sabe si son
tratables: problemas NP-completos
• Nadie ha encontrado algoritmos polinómicos para ninguno de ellos.
• Algunos muy parecidos a problemas tratables:– Ciclos eulerianos y hamiltonianos.– Satisfabilidad de 2-FNC y 3-FNC
4242/60/60
Clases P, NP y NPC• La clase P contiene todos los problemas tratables.
• La clase NP contiene todos los problemas que se pueden “verificar” en tiempo polinómico. Claramente PNP.
• La clase NPC contiene todos los problemas NP-completos
4343/60/60
Definición NPC• Un problema es NP-Completo si:
– Pertenece a NP.– Es tan “duro” como cualquier otro problema en NP (es NP-duro).
• Un problema es NP-completo si es que existe un algoritmo polimómico para él, implica que existe uno para todos los problemas en NP.
4444/60/60
¿P=NP?• Observa que si hubiera un algoritmo polinómico para
cualquier problema en NPC entonces P=NP.
• La hipótesis más aceptada es que P≠NP.
• Si queremos enfrentar un problema NPC es nejor buscar alternativas (simplificaciones, aproximaciones, etc.).
4545/60/60
PREGUNTAS