estructuradedatosfimeuanl

Complejidad Computacional

La Teoría de la Complejidad Computacional es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo a su dificultad inherente, y en la relación entre dichas clases de complejidad.

Un problema se cataloga como "inherentemente difícil" si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de cómputo matemáticos para el estudio de estos problemas y la cuantificación de la cantidad de recursos necesarios para resolverlos, como tiempo y memoria.

Uno de los fines de la teoría de la complejidad computacional es determinar los límites prácticos de qué es lo que se puede hacer en una computadora y qué no. Otros campos relacionados con la teoría de la complejidad computacional son el análisis de algoritmos y la teoría de la computabilidad. Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.

La teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

Definición De Algoritmo

Un algoritmo es un procedimiento computacional bien definido, el cual considera un valor o conjunto de valores como valores de entrada y a través de una secuencia de instrucciones organizadas produce un valor o conjunto de valores de salida, en un tiempo determinado con la finalidad de dar solución a un problema específico.

Las características principales de un algoritmo son:

Ø Preciso y Definido. Cada paso debe ser definido en forma precisa e indicar el orden de realización.

Ø Datos de entrada (input). El algoritmo recibe datos iniciales antes de su ejecución.

Ø Datos de salida (output). El algoritmo tiene una o más salidas, es decir, datos que tienen una relación específica respecto a los datos de entrada.

Ø Generalidad. Independientemente de las veces que se siga un algoritmo, se debe obtener el mismo resultado.

Ø Finito. Un algoritmo debe terminar siempre después de un número finito de pasos.

Al analizar un algoritmo se considera el tiempo de corrida y consiste en el número de operaciones elementales que ejecuta en cada paso. Dicho análisis se concentra generalmente en encontrar el peor caso de tiempo de corrida, es decir, el mayor tiempo que tardaría el algoritmo en obtener los valores de salida.

Características

El análisis se basa en dos aspectos:

v Tiempo. Mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema.

v Espacio. Mediante una aproximación a la cantidad de memoria utilizada para resolver un problema.

El análisis se puede realizar de dos formas distintas:

v Empírica (experimental)

v Teóricamente.

Tipo

Ventajas

Desventajas

Experimental

-“Sencilla”

-Resultados “reales”

Hace falta tener dos implementaciones

igual de cuidadas,

hacen falta datos reales, más costosa, dependiente de la maquina

Teórica

-Flexible

-“Barata”

-Independiente de la maquina

Resultados no “exactos”.

Clases de complejidad

Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional.

Definiendo clases de complejidad

Las clases de complejidad más sencillas se definen teniendo en cuenta factores como:

· El tipo de problema computacional: Los problemas más comúnmente utilizados son los problemas de decisión, pero las clases de complejidad se pueden definir para otros tipos de problemas.

· El modelo de cómputo: El modelo de cómputo más común es la Máquina de Turing determinista, pero muchas clases de complejidad se basan en Máquinas de Turing no deterministas, Máquinas de Turing cuánticas, etc.

· El recurso (o recursos) que está(n) siendo acotado(s) y la(s) cota(s): Estas dos propiedades usualmente se utilizan juntas, por ejemplo, "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.

Máquinas de Turing deterministas y la clase P

La clase P contiene a aquellos problemas que son solubles en tiempo polinómico por una máquina de Turing determinista.

Para la definición anterior se ha fijado el modelo de cómputo: la Máquina de Turing determinista. Existen distintas variantes de la Máquina de Turing y es conocido que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumo un tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la clase análoga a P para dichos modelos no es mayor que la clase P para el modelo de cómputo de la máquina de Turing.

La clase P juega un papel importante en la teoría de la complejidad computacional debido a que:

1. P es invariante para todos los modelos de cómputo que son polinómicamente equivalentes a la Máquina de Turing determinista.

2. A grandes rasgos, P corresponde a la clase de problemas que, de manera realista, son solubles en una computadora.

Computación no determinista y la clase NP

Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinómico. Sin embargo, para algunos problemas esto no ha podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debido a que son "inherentemente difíciles".

La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se les llama problemas NP.

El término NP proviene de no determinista en tiempo polinómico y se deriva de una caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista (recordar la equivalencia entre algoritmo y Máquina de Turing).

El algoritmo mencionado está compuesto por 2 etapas separadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.

Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.

Clases de complejidad importantes

Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo. Algunas de estas clases de problemas de decisión son:

Clase de complejidad	Modelo de cómputo	Restricción de recurso
DTIME(f(n))	Máquina de Turing determinista	Tiempo f(n)
P	Máquina de Turing determinista	Tiempo poly(n)
EXPTIME	Máquina de Turing determinista	Tiempo 2^poly(n)
NTIME(f(n))	Máquina de Turing no determinista	Tiempo f(n)
NP	Máquina de Turing no determinista	Tiempo poly(n)
NEXPTIME	Máquina de Turing no determinista	Tiempo 2^poly(n)
DSPACE(f(n))	Máquina de Turing determinista	Espacio f(n)
L	Máquina de Turing determinista	Espacio O(log n)
PSPACE	Máquina de Turing determinista	Espacio poly(n)
EXPSPACE	Máquina de Turing determinista	Espacio 2^poly(n)
NSPACE(f(n))	Máquina de Turing no determinista	Espacio f(n)
NL	Máquina de Turing no determinista	Espacio O(log n)
NPSPACE	Máquina de Turing no determinista	Espacio poly(n)
NEXPSPACE	Máquina de Turing no determinista	Espacio 2^poly(n)

La pregunta P=NP

La relación entre las clases P y NP es fundamental para la teoría de la NP-completitud. Intuitivamente, creemos que P es un subconjunto de NP. Y, efectivamente, cada problema de decisión resuelto por un algoritmo de tiempo polinomial determinista, también puede ser resuelto por un algoritmo de tiempo polinomial no determinista. Simplemente se necesita observar que cualquier algoritmo determinista puede ser utilizado en la etapa de verificación de un algoritmo no determinista. Si B es un problema de P, y A es un algoritmo de tiempo polinomial para B, entonces se puede construir un algoritmo de tiempo polinomial no determinista para B, simplemente utilizando A en la etapa de verificación e ignorando la etapa de adivinación. Por tanto, si B pertenece a P, entonces B también pertenece a NP.

La pregunta P=NP es una de las más importantes en el campo de las ciencias de la computación, debido a las grandes repercusiones que habría, en caso de encontrarse una solución. Si P=NP, cualquier problema polinómicamente verificable sería polinómicamente decidible. La mayoría de los investigadores cree que estas clases no son iguales, porque se ha realizado bastantes esfuerzos, sin éxito, para encontrar algoritmos de tiempo polinomial para varios problemas en NP. Los investigadores también han tratado de probar que las clases son distintas, pero eso conllevaría a mostrar que no existe un algoritmo «eficiente» para reemplazar a la búsqueda por fuerza bruta.

NP-Completitud

· Reducción polinomial

Una reducción es una transformación de un problema en otro problema. Intuitivamente, un problema Q puede ser reducido a otro problema Q', si cualquier instancia del problema Q puede ser "fácilmente" expresada como una instancia del problema Q', y cuya solución proporcione una solución para la instancia de Q.

Existen muchos tipos de reducciones: basadas en el método de reducción, como las reducciones de Cook, las reducciones de Karp y las reducciones de Levin, y las basadas en la cota de la complejidad, como la reducción en tiempo polinomial o la reducción de espacio logarítmica. Una de las reducciones más utilizadas es la reducción en tiempo polinomial, lo cual significa que el proceso de reducción toma un tiempo polinomial.

· Problemas NP-completos

Las reducciones en tiempo polinomial nos dotan de elementos para probar, de una manera formal, que un problema es al menos tan difícil que otro, con una diferencia de un factor polinomial. Estas son esenciales para definir a los problemas NP-completos, además de ayudar a comprender los mismos.

La clase de los problemas NP-completos contiene a los problemas más difíciles en NP, en el sentido de que son los que estén más lejos de estar en P. Debido a que el problema P=NP no ha sido resuelto, el hecho de reducir un problema B, a otro problema A, indicaría que no se conoce solución en tiempo polinomial para A. Esto es debido a que una solución en tiempo polinomial para A, tendría como consecuencia la existencia de una solución polinomial para B. De manera similar, debido a que todos los problemas NP pueden ser reducidos a este conjunto, encontrar un problema NP-completo que pueda ser resuelto en un tiempo polinomial significaría que P=NP.

· Importancia de la NP-Completitud

Quizás la razón de mayor peso por la cual los científicos de la computación creen que P es distinto de NP, es la existencia de la clase de problemas "NP-completos". Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP. A pesar de años de estudio, ningún algoritmo de tiempo polinomial se ha descubierto para ningún problema NP-completo.

Desde el punto de vista teórico, un investigador intentando mostrar que la clase P es distinta de la clase NP, pudiera enfocarse en un problema NP-completo. Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también. Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo.

Desde el punto de vista práctico, el fenómeno de la NP-completitud puede prevenir la pérdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado. Aún cuando no se posean los elementos matemáticos para demostrar que cierto problema no se puede resolver en tiempo polinomial, creemos que P no es igual a NP, así que demostrar que el problema es NP-completo, es una fuerte evidencia de su no "polinomialidad".

Aplicaciones

Se enfoca en algoritmos eficientes en optimización discreta, combinatoria y continua y on-line, en teoría de grafos, aplicaciones internet y análisis de ficheros de texto (stringología) y también para la evaluación de consultas particulares de bases de datos muy grandes en genómica, recuperación de imágenes búsquedas en la web y geometría elemental. Complejidad en computación científica (cotas superiores e inferiores de complejidad en el contexto numérico, seminumérico y simbólico).

Campos: Teoría general de grafos, optimización lineal y no-lineal, local y global, algoritmos on- line, Knowledge Management, microeconomía y algorítmica de publicidad on-line, complejidad de Kolmogorov y azar, algoritmos para problemas de palabras (stringology) con aplicaciones en genómica, álgebra lineal numérica, sampling, teoría de números efectiva, criptografía, constraint data bases, geometría algebraica, semialgebraica y diofántica efectiva (Computer Algebra), teoría algebraica de la complejidad.

Grupos de Investigación/Temas:

· Algoritmos sobre palabras/secuencias y aplicaciones

Dedicados a problemas sobre palabras (secuencias, strings), especialmente en temas de aleatoriedad y combinatoria, con un enfoque que integra la teoría y la práctica. Diseñamos e implementamos algoritmos y estructuras de datos para volúmenes muy grandes de datos, donde la complejidad de representación, complejidad tiempo y complejidad memoria son cruciales. También trabajamos en la visualización, ideando e implementando interfaces para mostrar los resultados computacionales.

Uno de los proyectos actuales, en colaboración con especialistas en genómica comparativa, trata sobre secuencias de ADN. Dimos una aproximación computable y eficientemente calculable de la función de complejidad de Kolmogorov, garantizando buenas propiedades matemáticas, como la subaditividad. Usamos nuestra función para aproximar la cantidad de información de distintos genomas que los biólogos interpretan desde la perspectiva genómica y evolutiva. Este proyecto incluye temas de algorítmica, complejidad, cómputo de alta performance y diálogo interdisciplinario.

· Algoritmos y Herramientas computacionales para los motores búsqueda y la publicidad online

La venta de publicidad asociada a los resultados de las búsquedas o a los contenidos de una página se ha convertido en la mayor fuente de ingresos de las principales empresas del sector, y su importancia relativa continúa creciendo. Las decisiones acerca de cuántos y cuáles avisos elegir, en qué orden mostrarlos, cómo y cuánto cobrarlos, abren un amplio campo de investigación que vincula distintas disciplinas, en la búsqueda de mecanismos que permitan satisfacer los intereses de los distintos actores involucrados (editores, anunciantes y usuarios), con propiedades de eficiencia y practicidad adecuadas a las características de la aplicación (masividad, velocidad de respuesta requerida, etc.). Se busca analizar tanto teórica como experimentalmente los mecanismos actualmente en uso y otros nuevos, con el objeto de proveer nuevas herramientas a los participantes de esta importante y novedosa actividad económica. Otra línea de investigación de este grupo consiste en el diseño de algoritmos y estructuras de datos más eficientes para la recuperación de información, en particular la construcción de índices distribuidos.

· Criptografía

El tema central de investigación es el desarrollo de algoritmos polinomiales de factorización de enteros, esencial para la seguridad del método estándar de criptografía de clave pública (RSA).

· Investigación en Grafos y Optimización: Teoría y Aplicaciones

Dentro del área de Teoría de Grafos, las principales líneas de investigación son: Coloreo de grafos; Caracterizaciones estructurales de clases de grafos; Complejidad computacional. Dentro de lo que es Optimización Combinatoria, las principales áreas abordadas son: Combinatoria poliedral; Problemas de scheduling deportivo; Aplicaciones a problemas reales (ruteo de vehículos, logística); Aplicaciones en teoría de juegos. Con respecto a los proyectos aplicados, entre los últimos se encuentran la segmentación de viviendas para el Censo Nacional 2010, la planificación de la recolección de residuos en contenedores en la zona sur de la Ciudad de Buenos Aires, el diseño del fixture de la liga de primera división de vóley masculino, el diseño de un modelo matemático para administrar la licitación de Internet para las escuelas públicas de la Ciudad de Buenos Aires y la implementación de modelos de simulación para el Sistema de Administración de Aportes de Productores en el ámbito de la Ciudad de Buenos Aires.

· Teoría de Grafos

Realiza investigaciones en el área de combinatoria, teoría de algoritmos y estructuras de datos complejas. Se estudian propiedades de diferentes clases de grafos, se caracterizan estas clases y se estudia el problema de reconocimiento de las mismas. Por otro lado, desarrollo de nuevos algoritmos que resuelven problemas ya resueltos en la literatura, intentando mejorar la "eficiencia" de las soluciones conocidas.

Ejemplos

Problemas de Decisión

Los problemas de decisión son aquéllos en que se nos pide averigüemos si una determinada expresión tiene una cierta propiedad o si varias expresiones están en una determinada relación. Así, por ejemplo, el problema de averiguar si un determinado número natural es primo o no, es un problema de decisión. También son problemas de decisión el problema de averiguar si una determinada fórmula de la lógica sentencial es una tautología o si una determinada fórmula e la lógica de primer orden es válida o no, o si una determinada fila de signos del alfabeto de nuestra lengua constituye una oración castellana gramaticalmente correcta o no, etc.

Un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son “si” o “no”.

Desde esta perspectiva, la clase P corresponde a la clase de los Problemas de Decisión que pueden resolverse con Máquinas de Turing en tiempo polinomial. Tanto es así, que con frecuencia consideramos a P más que una clase de lenguajes Decidibles, como una clase de Problemas de Decisión.

Características

Un problema de decisión presenta las siguientes características principales:

· Existen al menos dos posibles formas de actuar, que llamaremos alternativas o acciones, excluyentes entre sí, de manera que la actuación según una de ellas imposibilita cualquiera de las restantes.

· Mediante un proceso de decisión se elige una alternativa, que es la que se lleva a cabo.

· La elección de una alternativa ha de realizarse de modo que cumpla un fin determinado.

Dentro de los problemas de decisión, intervienen ciertos factores, como los son:

· Predicción de las consecuencias de cada actuación. Esta predicción deberá basarse en la experiencia y se obtiene por inducción sobre un conjunto de datos. La recopilación de este conjunto de datos y su utilización entran dentro del campo de la Estadística.

· Valoración de las consecuencias de acuerdo con una escala de bondad o deseabilidad. Esta escala de valor dará lugar a un sistema de preferencias.

· Elección de la alternativa mediante un criterio de decisión adecuado. Este punto lleva a su vez asociado el problema de elección del criterio más adecuado para nuestra decisión, cuestión que no siempre es fácil de resolver de un modo totalmente satisfactorio

Ejemplos

Algunos ejemplos de problemas de decisión expresados como lenguajes:

· Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b.

· Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b.

· Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más corto entre esos dos vértices.

· Las frases que describen una máquina de Turing y una cinta de entrada para esta máquina tal que la máquina se detiene en un tiempo finito al procesar esa entrada.

Los problemas de decisión son interesantes dado que todos los problemas formales (que incluyen tanto lógicos como matemáticos) pueden ser redactados para que tomen la forma de un problema de decisión. Las soluciones al problema de decisión y al problema original se diferencian a lo sumo por un factor lineal.

En un problema de decisión cada instancia tiene asociada exactamente una solución "sí" o "no". Los problemas de decisión quedan completamente determinados por el conjunto de instancias que tienen asociada la solución "sí". Por ejemplo, el problema de decidir si una gráfica tiene o no un ciclo Hamiltoniano queda completamente determinado su conjunto de soluciones "sí":

Con esta representación el problema equivale a preguntar si una instancia pertenece o no al conjunto HAM. En general, los problemas de decisión siempre equivalen a decidir la proposición i € Y donde Y es el conjunto de instancias con solución "sí". Una solución algorítmica para un problema de decisión es un algoritmo que calcula la función característica de Y o equivalente:

Problema de optimización

En un problema de optimización no solo se busca una solución, sino que se busca "la mejor" de todas. Cada problema de optimización puede concebirse como un problema de búsqueda y una función, comúnmente conocida como función objetivo, que determina la calidad de las soluciones.

El problema de optimización (que a su vez es de búsqueda) consiste en encontrar la solución que maximice o minimice el valor.

En el caso más simple, un problema de optimización consiste en maximizar o minimizar una función real eligiendo sistemáticamente valores de entrada (tomados de un conjunto permitido) y computando el valor de la función.

La teoría de optimización clásica o programación matemática está constituida por un conjunto de resultados y métodos analíticos y numéricos enfocados a encontrar e identificar al mejor candidato de entre una colección de alternativas, sin tener que enumerar y evaluar explícitamente todas esas alternativas. Un problema de optimización es, en general, un problema de decisión.

Características de un problema de optimización

Es problema que tiene una instancia (restricciones) que trata de llegar a una solución óptima.

A cada problema de optimización corresponde uno o más problemas de decisión.

Se puede expresar como problema de decisión.

Los modelos de optimización son usados en casi todas las áreas de toma de decisiones, como en ingeniería de diseño y selección de carteras financieras de inversión. Y podemos encontrar ejemplos focalizados y estructurados para la formulación de problemas de optimización, diseño de la estrategia óptima , verificación y análisis post-solución.

Ejemplos:

• La combinación de ingredientes más barata/durable/ecológica para una pintura de exteriores.

• el problema del viajante para determinar si una gráfica tiene o no un ciclo hamiltoniano, sino que además pregunta cuál es el ciclo hamiltoniano más corto.

• La asignación de rutas de camiones de entrega de mercancía de centros de distribución a tiendas de autoservicio.

Conclusiones

La importancia de la complejidad computacional es de suma importancia para la solución de problemas ya que esta estudia a fondo los problemas que pueden ser considerados de alta dificultad y que requieren ser analizados paso a paso detenidamente mediante procesos que se requieren suma concentración para su análisis. Como se observó que es importante ya que se aplican en áreas como los grafos y uso de secuencias de caracteres. La complejidad es de mucha ayuda para la solución de problemas.

En base a la Complejidad Computacional, es que podemos tomar la decisión correcta para resolver un problema de tipo computacional, utilizando las mejores y más convenientes herramientas para la resolución del mismo.

En torno a la complejidad computacional, nace uno problema llamado problema de optimización en donde buscas la mejor de todas las soluciones a un problema, donde debes de tomar una decisión donde tu criterio será la clave para escoger dicha solución.

DESCARGA LA PRESENTACIÓN EN POWER POINT