elementos de complejidad algorimica.docx
TRANSCRIPT
ISAE UNIVERSIDAD
FACULTAD DE CIENCIAS TECNOLÓGICAS
FUNDAMENTO DE MATEMATICAS
DISCRETA PARA COMPUTADORA
ELEMENTOS DE COMPLEJIDAD ALGORIMICA
JAIME REYES GONZALES
8-478-725
Grupo LE #9-10
Profesora
Omaira E. Chérigo S
10 de diciembre de 2014
INDICE
IntroducciónFunción de Complejidad en el tiempoRelación de DominaciónClases P y NPConclusiones Infografía
INTRODUCCION
Hoy en día, a pesar de que las computadoras han evolucionado rápidamente y que actualmente son capaces de procesar gran cantidad de operaciones por segundo, todavía existen problemas cuya solución puede tardar años en obtenerse.Es difícil realizar un análisis simple de un algoritmo que determine la cantidad exacta de tiempo que éste requiere para ser ejecutado porque depende en gran parte del algoritmo y de la computadora en que se ejecute.Al hablar del uso eficiente de los recursos, éste puede medirse en función de dos indicadores: el espacio (cantidad de memoria que utiliza) y tiempo (que tarda en ejecutarse). Si para resolver un problema P, un algoritmo A, requiere de poca memoria del equipo de cómputo y/o ejecuta un pequeño número de instrucciones comparado con el resto de los algoritmos conocidos que resuelven el P, entonces se puede afirmar que A es más eficiente que los restantes cuando se resuelve P.
FUNCIÓN DE COMPLEJIDAD EN EL TIEMPO.
En computación, cuando el tiempo de ejecución de un algoritmo
(mediante el cual se obtiene una solución al problema) es menor que
un cierto valor calculado a partir del número de variables implicadas
(generalmente variables de entrada) usando una fórmula polinómica,
se dice que dicho problema se puede resolver en un tiempo polinómico.
Por ejemplo,
si determinar el camino óptimo que debe recorrer un cartero que pasa
por casas necesita menos de segundos, entonces el
problema es resoluble en un "tiempo polinómico".
De esa manera, tiempos de , o son
polinómicos; pero no lo es.
Dentro de los tiempos polinómicos, podemos distinguir los logarítmicos
, los lineales , los cuadráticos , los cúbicos ,
etc.
La complejidad temporal se expresa normalmente utilizando la
notación “notación O” o de la “O grande”, con la cual se dispone de un
medio para expresar la cota asintótica de una función en el peor de los
casos. El término asintótico es referente al tamaño de la entrada del
problema, en este caso para un valor de n grande. El peor de los
casos indica cuando el algoritmo computacional lleva a cabo el total de
las instrucciones que el algoritmo puede ejecutar. Es una expresión
aproximada de la relación entre el tamaño de un problema y la
cantidad de instrucciones necesarias en el algoritmo para obtener un
resultado.
Ejemplos de esto son:
Los ejemplos mostrados no son tan
sencillos de evaluar como parecen, es
solo una muestra de un análisis detallado
que debe realizarse a una serie de
instrucciones que se aplican en un
algoritmo computacional para resolver
un problema.
El tiempo de ejecución de una secuencia consecutiva de instrucciones
se calcula los tiempos de ejecución de cada una de las instrucciones.
• El tiempo de ejecución de la sentencia
“CASE C OF v1:S1|v2:S2|...|vn:Sn
END;” es T = T(C) + max{T(S1),T(S2),...,T(Sn)}.
Obsérvese que T(C) incluye el tiempo de comparación con
v1, v2 ,..., vn.
• El tiempo de ejecución de la sentencia
“IF C THEN S1 ELSE S2 END;” es
T = T(C) + max{T(S1),T(S2)}.
Función
temporal
f(n)
Complejidad
asintótica
3.5n2 O(n2)
2 n3 O(n3)
n4 O(n4)
2n2+3n-1 O(n2)
• El tiempo de ejecución de un bucle de sentencias
“WHILE C DO S END;” es T = T(C) + (nº iteraciones)*(T(S) + T(C))}
. Obsérvese que tanto T(C) como T(S)
Pueden variar en cada iteración, y por tanto habrá que tenerlo en
cuenta para su cálculo.
• Para calcular el tiempo de ejecución del resto de sentencias
iterativas (FOR, REPEAT, LOOP) basta expresarlas como un bucle
WHILE. A modo de ejemplo,
el tiempo de ejecución del bucle:
FOR i:=1 TO n DOS END;
Puede ser calculado a partir del bucle equivalente:
i:=1;WHILE i<=n DOS; INC(i) END;
• El tiempo de ejecución de una llamada a un procedimiento o
función
F(P1, P2,..., Pn) es 1 (por la llamada), más el tiempo de evaluación de
los parámetros P1, P2,..., Pn, más el tiempo que tarde en ejecutarse
F, esto es,T = 1 + T(P1) + T(P2) + ... + T(Pn) + T(F).
No contabilizamos la copia de los argumentos a la pila de ejecución,
salvo que se trate de estructuras complejas (registros o vectores) que
se pasan por valor. En este caso contabilizaremos
Tantas OE como valores simples contenga la estructura. El paso de
parámetros por referencia, por tratarse simplemente de punteros, no
contabiliza tampoco.
• El tiempo de ejecución de las llamadas a procedimientos recursivos
va a dar lugar a ecuaciones en recurrencia, que veremos
posteriormente.
• También es necesario tener en cuenta, cuando el compilador las
incorpore, las optimizaciones del código y la forma de evaluación.
RELACIÓN DE DOMINACIÓN
Haciendo uso del concepto de aplicación inyectiva, definimos una
clase relacional binaria sobre el universo de los conjuntos, la de
dominación, sobre la que se fundamentar en una sección posterior,
la comparación entre los cardinales.
Sean A y B dos conjuntos. Decimos que B domina a A, o que A esta
dominado por B, si hay un monomorfismo de A en B. Si tal es el caso
lo denotamos por A ≤ B.
EJERCICIO.
Demuéstrese que no existe el conjunto { (A, B) | A ≤ B }.
Respecto de la relación de dominación puede ocurrir, a priori, para dos
conjuntos Arbitrarios A y B, la siguiente toracotomía
1. ) A ≤ B y B ≤ A.
2. ) A ≤ B pero B _ A.
3. ) A _ B pero B ≤ A.
4. ) A _ B y B _ A.
Posteriormente, demostraremos que en el primer caso obtenemos que
A y B sean isomorfos, que sean indistinguibles en la teoría de
conjuntos, que es el Teorema de Cantor-
Bernstein;
Y que el último caso no puede darse, ya que,
como consecuencia del axioma de elección,
siempre se cumple que, para cualesquiera
conjuntos A y B,
A ≤ B o B ≤ A.
Proposición
La proposición que sigue establece que la relación binaria, ≤ , de
dominación sobre el universo de los conjuntos, tiene las propiedades
de una relación de pre orden, i.e.,es reflexiva y transitiva.
Sean A, B y C tres conjuntos. Entonces:
1. A ≤ A.
2. Si A ≤ B y B ≤ C, entonces A ≤ C.
Demostración. Esta Proposición se deduce inmediatamente de la
Proposición.
Ejercicio
Demuéstrese que la clase relacional ≤ ∩ ≤ − 1 tiene las
propiedades de una relación de equivalencia, i.e., es reflexiva
simétrica y transitiva.
Teorema
El teorema de Cantor que sigue, establece que cada conjunto está
dominado por
Otro conjunto, concretamente, por el conjunto de sus partes.
Para cada conjunto A, hay un monomorfismo natural
de A en Sub(A), i.e., hay un {・} A : A __ /Sub(A)
tal que, para cada aplicación
f : A /B, el diagrama:
Conmuta. Así pues, con la terminología anterior, cada conjunto A esta
dominado por Sub(A).
Demostración. Sea A un conjunto. Entonces la aplicación {・} A: A
__ /Sub(A), Definida como:
{
Es un monomorfismo.
Por otra parte, si f : A B y a ∈ A, entonces
{・} B (f(a)) = {f(a)} y f[{・}A(a)] = {f(a)},
Luego {・} B ◦ f = f[・] ◦ {・}
A. Por consiguiente el diagrama conmutación
Obsérvese que la definición de las aplicaciones {・} A y {・} B es la
misma, i.e., es
Independiente del conjunto que se considere, dicho de otro modo la
familia de aplicaciones
({・} A) A ∈V es una transformación natural entre dos factores
convenientes.
Más adelante demostraremos que Sub(A) no está dominado por A
CLASES P Y NP
La clase PP es conocido por contener muchos problemas naturales, incluyendo las versiones de decisión de programa lineal, cálculo del máximo común divisor, y encontrar una correspondencia máxima.Problemas notables en PAlgunos problemas naturales son completos para P, incluyendo la conectividad (o la accesibilidad) en grafos no dirigidos.Una generalización de P es NP, que es la clase de lenguajes decidibles en tiempo polinómico sobre una máquina de Turing no determinista. De forma trivial, tenemos que P es un subconjunto de NP. Aunque no está demostrado, la mayor parte de los expertos creen que esto es un subconjunto estricto.Aquí, EXPTIME es la clase de problemas resolubles en tiempo exponencial. De todas las clases.
Los problemas más difíciles en P son los problemas P-completosOtra generalización de P es el Tiempo polinómico No uniforme (P/Poly)[1]. Si un problema está en P/poly, entonces puede solucionarse en un tiempo polinomial determinado el cual, dado una cadena, este solo depende de la longitud de la entrada. A diferencia de NP, no se comprueban las cadenas defectuosas que entran en la máquina de Turing, puesto que no es un verificador.P/poly es una clase grande que contiene casi todos los algoritmos prácticos, incluyendo todo el BPP. Si esta contiene a NP, la jerarquía polinomial se colapsa con el segundo nivel. Por otra parte, esta también contiene algunos algoritmos poco prácticos, incluyendo algunos problemas no decidibles.
PropiedadesLos algoritmos de tiempo polinómico son cerrados respecto a la composición. Intuitivamente, esto quiere decir que si uno escribe una función con un determinado tiempo polinómico y consideramos que las llamadas a esa misma función son constantes y, de tiempo polinómico, entonces el algoritmo completo es de tiempo polinómico. Esto es uno de los motivos principales por los que P se considera una máquina independiente; algunos rasgos de esta máquina, como el acceso aleatorio, es que puede calcular en tiempo polinómico el tiempo polinómico del algoritmo principal reduciéndolo a una máquina más básica.Las pruebas existenciales de algoritmos de tiempo polinómicoSe conoce que algunos problemas son resolubles en tiempo polinómico, pero no se conoce ningún algoritmo concreto para solucionarlos. Por ejemplo, el teorema Robertson-Seymour garantiza que hay una lista finita de los menores permitidos que compone (por ejemplo) el conjunto de los grafos que pueden ser integrados sobre un toroide; además, Robertson y Seymour demostraron que hay una complejidad O (n3) en el algoritmo para determinar si un grafo tiene un grafo incluido. Esto nos da una prueba no constructiva de que hay un algoritmo de tiempo polinómico para determinar si dado un grafo puede ser integrado sobre un toroide, a pesar de no conocerse ningún algoritmo concreto para este problema.EjemplosCamino Mínimo: encontrar el camino mínimo desde un vértice origen al resto de los vértices.Ciclo Euleriano: Encontrar un ciclo que pase por cada arco de un grafo una única vez.
La Clase NP
La clase NP está compuesta por los problemas que tienen un certificado sucinto (también llamado testigo polinómico) para todas las instancias cuya respuesta es un SÍ. La única forma de que tengan un tiempo polinomial es realizando una etapa aleatoria, incluyendo el azar de alguna manera para elegir una posible solución, y entonces en etapas posteriores comprueba si esa solución es correcta.En otras palabras, dada una solución para una cierta instancia, es posible comprobar que es válida en TIME (n^k). En el caso de SAT (Problema de satisfacibilidad booleana), dado una asignación de valores de verdad, se puede comprobar fácilmente si la fórmula es cierta o no. Una nMT puede "adivinar" la solución en O (n) y verificarla en tiempo polinómico.
Completitud de NPPara analizar la pregunta P = NP, resulta muy útil el concepto de completitud NP . De manera informal, los problemas de completitud NP son los problemas más "difíciles" en NP en el sentido de que ellos son los que son más probable no se encuentren en P. Problemas NP - difíciles son aquellos para los cuales cualquier problema en NP puede ser reducido en tiempo polinómico. Los problemas de completitud NP son aquellos problemas NP-difícil que se encuentran en NP. Por ejemplo, la versión de problema de decisión del problema del vendedor viajero es completamente NP. Así ningún caso de ningún problema en NP puede ser transformado mecánicamente en una parte del problema del vendedor viajero, en tiempo polinómico. Por lo tanto, si el problema del vendedor viajero estuviera contenido en P, entonces P = NP. El problema del vendedor viajero es uno de muchos problemas NP-completos. Si cualquier problema NP-completo se encuentra contenido en P, entonces se verificaría que P = NP. Desafortunadamente, se ha demostrado que muchos problemas importantes son NP-completos y no se conoce la existencia de ningún
La definición anterior de NP permite considerar de manera natural una clase de problemas complementarios. La co-NP está compuesta por los problemas que tienen un contraejemplo sucinto para todas las instancias cuya respuesta es NO.
ProblemaDenominamos Clique al siguiente problema:Dado un grafo G y un entero k, ¿es posible encontrar un subgrafo de G completo de tamaño k?• Claramente Clique pertenece a NP.• Ahora deberemos hacer una reducción de SAT a NP.• Supongamos que tenemos una fórmula en CNF:C1 v C2 v . . . v Ck con n variables proposicionales.Formaremos un grafo G con un nodo por cada literal que aparece en cada cláusula. Cada nodo está etiquetado con el literal que le dio origen. Agregaremos un arco entre un nodo etiquetado con l y un nodo etiquetado con l0 si y solo si:– l y l0 están en cláusulas distintas.– l no es el literal complementario de l.Supongamos la siguiente fórmula: (x1 v x2 v ¬x3) ^ (¬x1 v ¬x3) ^ (x3 v x2). El grafo resultante queda como:
Ahora deberemos demostrar que G tiene un subgrafo completo de tamaño k si es satisfactible. Como todos los miembros del subgrafo pertenecen a cláusulas distintas, cualquier valuación que hace verdadero a todo literal en el subgrafo hace verdadera a la fórmula (recordemos que dos literales complementarios no pueden estar en un subgrafo completo). Si la fórmula es satisfecha, debe existir una valuación que haga verdaderos a al menos un literal en cada cláusula.
Sean l1 pertenece a C1, l2 pertenece a C2, . . . , lk pertenece Ck estos literales. Notemos que no es posible que existan dos literales complementarios li y lj. Necesariamente, entonces, podemos construir arcos entre cada par de nodos en donde aparecen dichos literales siguiendo las reglas de construcción del grafo.
EjemplosCamino Máximo: Dados dos vértices de un grafo encontrar el camino (simple) máximo.Ciclo Hamiltoniano: Ciclo simple que contiene cada vértice del grafo.
NP-Completo[editar]Para abordar la pregunta de si P=NP, el concepto de la completitud de
NP es muy útil. Informalmente, los problemas de NP-completos son los
problemas más difíciles de NP, en el sentido de que son los más
probables de no encontrarse en P. Los problemas de NP-completos
son esos problemas NP-duros que están contenidos en NP, donde los
problemas NP-duros son estos que cualquier problema en NP puede
ser reducido a complejidad polinomial. Por ejemplo, la decisión del
Problema del viajante de comercio es NP-completo, así que cualquier
caso de cualquier problema en NP puede ser transformado
mecánicamente en un caso del Problema del viajante de comercio, de
complejidad polinomial. El Problema del viajante de comercio es de los
muchos problemas NP-completos existentes. Si cualquier problema
NP-completo estuviera en P, entonces indicaría que P=NP.
Desafortunadamente, se sabe que muchos problemas importantes son
NP-completos y a fecha de 2008, no se conoce ningún algoritmo
rápido para ninguno de ellos. Basándonos solo en esta idea, no es
obvio que exista un problema NP-completo. Un problema NP-completo
trivial e ideado, se puede formular como: Dada una descripción de una
máquina de Turing M que se detiene en tiempo polinómico, ¿existe
una entrada de tamaño polinómico que M acepte? Es NP porque,
dada una entrada, es simple comprobar si M acepta o no la entrada
simulando M, es NP-duros porque el verificador para cualquier caso
particular de un problema en NP puede ser codificado como una
maquina M de tiempo polinomial que toma la solución para ser
verificada como entrada. Entonces la pregunta de si el caso es o no un
caso, está determinado por la existencia de una entrada valida. El
primer problema natural que se demostró ser NP-completo fue el
Problema booleano de satisfacibilidad. Este resultado es conocido
como el teorema de Cook-Levin; su prueba de que la satisfacibilidad
es NP-completo contiene los detalles técnicos sobre máquinas de
Turing y como se relacionan con la definición de NP. Sin embargo,
después se demostró que el problema era NP-completo, la prueba por
reducción, proporcionó una manera más simple de demostrar que
muchos otros problemas están en esta clase. Así, una clase extensa
de problemas aparentemente sin relación es reducible a otra, y son en
este sentido el mismo problema.
Conclusiones
La matemática discreta Para computadoras antes de realizar un programa conviene elegir un buen algoritmo, donde por bueno entendemos que utilice pocos recursos, siendo usualmente los más importantes el tiempo que lleve ejecutarse y la cantidad de espacio en memoria que requiera. Las matemáticas discretas son un área de las matemáticas encargadas del estudio de los conjuntos discretos: finitos o infinitos numerables
INFOGRAFIA
http://micursodeestructuradedatos.blogspot.com/2008/08/analisis-de-algoritmos.htmlhttp://neofronteras.com/?p=3220
http://www.disfrutalasmatematicas.com/conjuntos/np-completo.HTMLhttp://www.dm.uba.ar/materias/optimizacion/2006/1/fbonomo_clase_npc.PDFhttp://danieliha.blogspot.com/2011/07/clases-de-complejidad-computacional-p-y.html
http://centrodeartigo.com/articulos-utiles/article_112504.html
http://robotica.uv.es/pub/Libro/PDFs/CAPI7.pdf