Programación Avanzada - Complejidad de Algoritmos PDF

UNIDAD I COMPLEJIDAD DE ALGORITMOS PROGRAMACIÓN AVANZADA  Módulo I Complejidad de algoritmos Fuente:http://blog.en1mes.com/wp-content/uploads/Screen-Shot-2014-09-29-at-4.59.jpg  ¿Qué es la complejidad de un algoritmo?...

UNIDAD I COMPLEJIDAD DE ALGORITMOS PROGRAMACIÓN AVANZADA  Módulo I Complejidad de algoritmos Fuente:http://blog.en1mes.com/wp-content/uploads/Screen-Shot-2014-09-29-at-4.59.jpg  ¿Qué es la complejidad de un algoritmo? 2 Fuente:http://veille-techno.blogs.ec-nantes.fr/wp-content/uploads/2012/10/code-space.jpg Cuando solucionamos un problema mediante la construcción de un algoritmo, usualmente podemos resolver el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas. Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, incluso pensando anticipadamente en problemas que impliquen un gran volumen de datos. La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere de destrezas matemáticas y la aplicación de una serie de técnicas bastante particulares. Sin embargo, el concepto en sí, no es difícil de entender. Entender la complejidad de un algoritmo es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo o incluso a elegir entre distintos algoritmos que realizan lo mismo. Prof. Viviane Oliveira Con un abordaje didáctico, de manera sencilla, vamos a exponer qué es la complejidad de un algoritmo y distinguir qué impacto tiene el que un algoritmo tenga una u otra complejidad. Una de las definiciones de algoritmo es una secuencia de instrucciones o pasos cuyo objetivo es la resolución de un problema. El término clave aquí es el de problema. Saber si un algoritmo es mejor que otro puede estudiarse desde dos 3 puntos de vista: un algoritmo es mejor cuanto menos tarde en resolver un problema, o bien es tanto mejor cuanta menos memoria necesite. Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en ejecutarse. Ambos representan los costes que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado de entre varios que solucionan un mismo problema. Nos referiremos a la eficiencia temporal. A la idea del tiempo que consume un algoritmo para resolver un problema le llamamos complejidad temporal y a la idea de la memoria que necesita el algoritmo le llamamos complejidad espacial. Para cada problema determinaremos una medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utilizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es más importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un fichero se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste. El análisis de la eficiencia temporal de los algoritmos consta de dos fases: análisis a priori y análisis a posteriori. El análisis a posteriori ofrece una medida real, consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto. El análisis a priori proporciona una medida teórica, que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados. Esta medida ofrece estimaciones del comportamiento de los algoritmos de forma independiente del ordenador en donde serán implementados y sin necesidad de ejecutarlos. La unidad de tiempo a la que debe hacer referencia esta medida de eficiencia Prof. Viviane Oliveira temporal no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no existe un ordenador estándar al que puedan hacer referencia todas las medidas. Esta medida de eficiencia temporal se define como una función del tamaño o talla de la entrada. Se denomina tamaño de la entrada el número de componentes sobre los que se va a ejecutar el algoritmo. La complejidad de un algoritmo es un "valor", por así decirlo, que nos da una idea de cuánto va a tardar un algoritmo en resolver el problema para el que fue diseñado. 4 El tamaño de un problema La idea que subyace tras el concepto de complejidad temporal de un algoritmo es, básicamente, medir cuánto tarda en resolver el problema. Para resolver cualquier problema, son necesarios unos datos de entrada sobre los que trabaja el algoritmo y que describen una ocurrencia concreta del problema que queremos resolver. El algoritmo, finalmente obtiene una o varias soluciones al problema (si es que el problema tiene soluciones). Sin embargo, debemos tener en cuenta algunas consideraciones. Por ejemplo, piensa en un típico algoritmo para ordenar los elementos de un vector. El algoritmo consta de una serie de instrucciones que se repiten una y otra vez (bucles), y probablemente, de una serie de selecciones (comparaciones) que hacen que se ejecute uno u otro camino dentro del algoritmo. Se hace necesaria una pregunta: ¿Tardará lo mismo un algoritmo de ordenación en ordenar un vector con 100 valores que uno con 100000 valores?.... Obviamente no. Pues aquí es donde tenemos que empezar a hablar del tamaño o talla del problema. Un algoritmo de ordenación debería ser capaz de ordenar un vector con cualquier número de elementos. Sin embargo, el tamaño del vector incide directamente en el tiempo que tarda el algoritmo en resolverse. Pues cualquier problema tiene un tamaño, que es un valor o un conjunto de valores que se pueden obtener de los datos de entrada y que si varían, normalmente tienen una repercusión en el tiempo que tardará el algoritmo en finalizar (aunque en algunos casos no). Por ejemplo, del problema de ordenar un vector, la talla del problema nos la da el número de elementos del vector. En un algoritmo que halle el término n-ésimo de la sucesión de Fibonacci?, la Prof. Viviane Oliveira talla nos la da el propio término número n que queremos hallar. Cada problema tiene uno o varios valores que determinan su talla. La complejidad se calcula en función de una talla genérica, y no concreta. Por ejemplo, la complejidad de un algoritmo de ordenación se calcula pensando en un array de longitud n, y no 5, 150 o 100.000. La complejidad no es un número: es una función Otra consideración a tener en cuenta a la hora de tratar con la complejidad es 5 que si estamos contando el tiempo que tarda un algoritmo en resolver un problema ¿En qué computador lo ejecutamos? Parece obvio que el mismo algoritmo ejecutado en un ordenador el doble de rápido que otro tardará la mitad en encontrar la solución. ¿Cuál debería ser entonces la unidad de medida de la complejidad? Ninguna unidad de tiempo nos vale: ni segundos ni milisegundos, porque el resultado variaría de un computador a otro. El mismo algoritmo tardará más o menos en solucionar un problema de una talla u otra. Es decir, no puede tardarse lo mismo en ordenar un vector de 100 valores que uno de 100.000. Si no tenemos en cuenta en qué computador se ejecutará el algoritmo: en lugar de medir tiempos, vamos a contar las instrucciones que debe realizar el algoritmo. Supondremos que cada instrucción se ejecuta en un tiempo constante. Haremos esa simplificación porque lo que queremos saber es cómo crece el número de instrucciones necesarias para resolver el problema con respecto a la talla del problema. Eso es realmente la complejidad. Por ejemplo, observa éste algoritmo escrito en un pseudocódigo. Ejemplo1 número de línea INICIO 1 variables: a, j, k, n entero 2 DESDE J = 1 hasta n 3 a=a+j 4 FIN DESDE 5 DESDE K = n hasta 1 6 a=a-1 7 a=a*2 8 Prof. Viviane Oliveira  FIN DESDE 9 IMPRIMIR a 10 FIN 11 En este algoritmo hay un par de bucles para que se ejecuten uno después del otro. Observemos el primer bucle. Se ejecuta n veces, y en su interior hay una instrucción (la de la línea 4). Eso quiere decir que la línea 4 se ejecuta n veces. 6 Después se ejecuta el segundo bucle, que contiene en su interior dos instrucciones (las de las líneas 7 y 8). Como ese segundo bucle se ejecuta también n veces y tiene dos instrucciones, se realizan 2n instrucciones. Finalmente hay una instrucción en la línea 10 que se ejecuta una sola vez. El número de instrucciones que se ejecutan en total son n+2n+1... es decir, 3n+1 Podemos decir que la complejidad de ese algoritmo es 3n+1, porque ese es el número de instrucciones que hay que realizar para solucionar el problema cuando la talla del problema es n. La idea que subyace es que podemos saber cómo se comporta el algoritmo conforme la talla del problema va creciendo. En este caso, si representamos 3n+1 con respecto a n nos daremos cuenta de que esta función es una recta. Para este algoritmo podemos suponer que cuando lo traslademos a un lenguaje de programación concreto sobre un ordenador concreto, si para un n=100 tarda 7 unidades de tiempo en solucionarlo, con unas pocas operaciones podemos deducir cuántas unidades de tiempo tarda para un n=1000. Por supuesto, no es un valor exacto, pero lo que nos importa es saber de qué manera aumenta el tiempo con respecto a la talla del problema. Veamos otros ejemplos. Ejemplo2 número de línea INICIO 1 variables: a entero 2 a=n*3 3 a=a+2 4 IMPRIMIR a 5 FIN 6 Prof. Viviane Oliveira Ejemplo3 número de línea INICIO 1 variables i, j, k, n entero 2 DESDE i=1 hasta n 3 DESDE j=n hasta 1 4 k=k+j 5 k=k+i 6 7 FIN DESDE 7 FIN DESDE 8 IMPRIMIR k 9 FIN 10 La función ejemplo2 realiza siempre 3 instrucciones (las líneas 3, 4 y 5), independientemente de lo que se le pase como parámetro. Así pues, este algoritmo siempre tarda lo mismo para cualquier valor de n. El número de instrucciones se mantiene constante, a diferencia del ejemplo anterior, que crecía linealmente con respecto a n. La función ejemplo3 tiene dos bucles para anidados. Cada bucle se ejecuta n veces, y en el interior del segundo hay 2 instrucciones. Ej. bucle interior hace que las dos instrucciones se repitan n veces, y el bucle exterior hace que todo eso se repita n veces más. Después hay una última instrucción (la de la línea 9). Así pues, se hacen 2×n×n+1 instrucciones... es decir, 2n2+1. Si representamos 2n2+1 con respecto a n en un gráfico nos podemos dar cuenta de que es una parábola... es decir, el tiempo crece muchísimo más rápido conforme crece n que en los ejemplos anteriores. En este caso, el tiempo crece cuadráticamente. Igual que ocurría en los ejemplos anteriores, si en una determinada máquina para n=100 se tardan 7 unidades de tiempo, con unas pocas operaciones podemos intuir cuánto va a tardar para un n=1000 o para cualquier otro valor. Prof. Viviane Oliveira Lo importante de la idea expuesta hasta ahora es que los distintos algoritmos se comportan de forma distinta. Su tiempo de ejecución varía de manera muy distinta conforme aumenta la talla del problema. Este gráfico clarifica ese punto. El eje horizontal representa a la talla del problema (n), y el eje vertical al número de instrucciones necesarias de nuestros tres ejemplos. La línea verde corresponde al primer ejemplo. Su número de instrucciones, y por tanto su tiempo de ejecución crece linealmente conforme n se hace más 8 grande. La línea azul corresponde al segundo. El número de instrucciones necesarias se mantiene constante, por muy grande que sea n. La línea granate corresponde al tercer ejemplo. El número de instrucciones crece proporcionalmente al cuadrado de n conforme crece n. Independientemente de los valores numéricos, resulta evidente que cada gráfica crece de manera distinta. A medida que n se vaya haciendo grande, las tres gráficas se distanciarán cada vez más. Eso es lo que nos importa realmente de un algoritmo: saber cómo crece el número de instrucciones a realizar conforme lo apliquemos cada vez a problemas más grandes, más que el tiempo medido en segundos. Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en ejecutarse. Ambos representan los costes que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado de entre varios que solucionan un mismo problema. Nos referiremos exclusivamente a la eficiencia temporal. El análisis de la eficiencia temporal de los algoritmos consta de dos fases: análisis a priori y análisis a posteriori. Prof. Viviane Oliveira El análisis a posteriori ofrece una medida real, consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto. El análisis a priori proporciona una medida teórica, que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados. Esta medida ofrece estimaciones del comportamiento de los algoritmos de forma independiente del ordenador en donde serán implementados y sin necesidad de ejecutarlos. La unidad de tiempo a la que debe hacer referencia esta medida de eficiencia temporal no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no existe un ordenador estándar al que puedan hacer referencia 9 todas las medidas. Esta medida de eficiencia temporal se define como una función del tamaño o talla de la entrada. Se denomina tamaño de la entrada el número de componentes sobre los que se va a ejecutar el algoritmo. La resolución práctica de un problema exige:  un algoritmo o método de resolución y  un programa o codificación del algoritmo en un computador real. Para cada problema determinaremos una medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N. El concepto exacto que mide N depende de la naturaleza del problema. Así, para un vector se suele utilizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es más importante considerar el número de arcos, dependiendo del tipo de problema a resolver); en un archivo se suele usar el número de registros, etc. Es imposible dar una regla general, pues cada problema tiene su propia lógica de costo. Tiempo de Ejecución Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, cronometrando el tiempo, por ejemplo). Reglas Prácticas Aunque no existe una receta que siempre funcione para calcular la complejidad de un algoritmo, si es posible tratar sistemáticamente una gran cantidad de ellos, basándonos en que suelen estar bien estructurados y siguen pautas uniformes. Los algoritmos bien estructurados combinan las sentencias de alguna de las formas siguientes: Prof. Viviane Oliveira  1. sentencias sencillas 2. secuencia (;) 3. decisión (if) 4. bucles 5. llamadas a procedimientos Sentencias sencillas Nos referimos a las sentencias de asignación, entrada/salida, etc. siempre y cuando no trabajen sobre variables estructuradas cuyo tamaño esté 10 relacionado con el tamaño N del problema. La inmensa mayoría de las sentencias de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1). Secuencia (;) La complejidad de una serie de elementos de un programa es del orden de la suma de las complejidades individuales, aplicándose las operaciones arriba expuestas. Decisión (if) La condición suele ser de O(1), complejidad a sumar con la peor posible, bien en la rama THEN, o bien en la rama ELSE. En decisiones múltiples (ELSE IF, SWITCH CASE), se tomara la peor de las ramas. Bucles En los bucles con contador explícito, podemos distinguir dos casos, que el tamaño N forme parte de los límites o que no. Si el bucle se realiza un número fijo de veces, independiente de N, entonces la repetición sólo introduce una constante multiplicativa que puede absorberse. Ej.- for (int i= 0; i < K; i++) { algo_de_O(1) } => K*O(1) = O(1) Si el tamaño N aparece como límite de iteraciones... Ej.- for (int i= 0; i < N; i++) { algo_de_O(1) } => N * O(1) = O(n) Ej.- for (int i= 0; i < N; i++) { for (int j= 0; j < N; j++) { algo_de_O(1) } } tendremos N * N * O(1) = O(n2) Prof. Viviane Oliveira Ej.- for (int i= 0; i < N; i++) { for (int j= 0; j < i; j++) { algo_de_O(1) } } el bucle exterior se realiza N veces, mientras que el interior se realiza 1, 2, 3,... N veces respectivamente. En total, 1 + 2 + 3 +... + N = N*(1+N)/2 -> O(n2) A veces aparecen bucles multiplicativos, donde la evolución de la variable de control no es lineal (como en los casos anteriores) Ej.- c= 1; 11 while (c < N) { algo_de_O(1) c= 2*c; } El valor incial de "c" es 1, siendo "2k" al cabo de "k" iteraciones. El número de iteraciones es tal que 2k >= N => k= techo(log2 (N)) [techo( ), el entero inmediato superior] y, por tanto, la complejidad del bucle es O(log n). Ej.- c= N; while (c > 1) { algo_de_O(1) c= c / 2; } Un razonamiento análogo nos lleva a realizar log2(N) iteraciones y, por tanto un orden O(log n) de complejidad. Ej.- for (int i= 0; i < N; i++) { c= i; while (c > 0) { algo_de_O(1) c= c/2; } } tenemos un bucle interno de orden O(log n) que se ejecuta N veces, luego el conjunto es de orden O(n log n) Llamadas a procedimientos La complejidad de llamar a un procedimiento viene dada por la complejidad del contenido del procedimiento en sí. El costo de llamar no es sino una constante que podemos obviar inmediatamente dentro de nuestros análisis asintóticos. El cálculo de la complejidad asociada a un procedimiento puede complicarse notablemente si se trata de procedimientos recursivos. Prof. Viviane Oliveira Resumiendo Un algoritmo es una abstracción de un programa y un programa es una implantación de un algoritmo. El objetivo del análisis de tiempo es predecir cuánto tiempo toma un programa con una entrada específica para ser ejecutado sin tener que ejecutarlo. Problemas que se presentan:  el tiempo de ejecución depende del computador,  el tiempo de ejecución depende del sistema operativo y 12  el tiempo de ejecución depende del compilador. Se desea tener una medida de la duración del tiempo de ejecución de un algoritmo en función del tamaño de la entrada. A través de llamados al sistema operativo se puede conocer el valor del reloj de tiempo real. Invocando al reloj, antes y después de realizar el algoritmo se tendrá una medida de la duración del tiempo de ejecución. Sin embargo esta medida es muy dependiente del hardware (memoria, reloj, procesador), del sistema operativo (multitarea, multiusuario) y puede variar significativamente dependiendo del computador, del compilador, y de la carga del sistema. Al disponer de sistemas con multiprocesadores o que la ejecución sea distribuida también afecta medir el tiempo con cronómetro. Por la razón anterior como una medida del tiempo de ejecución, se considera contar las instrucciones del lenguaje de alto nivel que son necesarias realizar. El tamaño de la entrada debe ser precisado con más detalle. Podría ser el número de bits que miden la información que el algoritmo procesa, pero en forma tradicional se considera el número de elementos o componentes básicas que son sometidos al proceso. Por ejemplo si tenemos un arreglo de n componentes, y el algoritmo tiene por objetivo, sumar los valores de las componentes, o bien ordenar las componentes, se suele decir que n es el tamaño de la entrada. Independientemente si el arreglo es de enteros, o de estructuras. El tiempo de ejecución depende además de la entrada específica; demora más tiempo el ordenamiento de 1.000.000 que de 10 elementos. Si la entrada específica tiene la misma cantidad de elementos se pueden distinguir problemas simples y problemas no tan simples. La cantidad de elementos de entrada n se denomina el tamaño del problema. Prof. Viviane Oliveira Para calcular el tiempo que se ocupa para ejecutar un programa se asocia con el tamaño a través de la formula t = f(n), donde f es generalmente denominado la complejidad de tiempo. El número n representa una medida para determinar la dimensión del problema a resolver. Por ejemplo, si se quiere ordenar una lista de elementos la medida para determinar la dimensión de este problema es la cantidad n de elementos que contiene la lista. Por ejemplo, la comparación de dos algoritmos de búsqueda lleva a los siguientes valores: 13  Algoritmo 1 - Búsqueda secuencial  Algoritmo 2 - Búsqueda binaria. Para el primer algoritmo se puede establecer que en el peor caso el tiempo para buscar un elemento es t = c * n. El tiempo depende de: c es una constante que representa las características del computador y otros factores que son independientes del algoritmo y n que es el tamaño de la lista. Este tipo de formula no se utiliza en esta forma en la comparación de algoritmos porque es difícil (imposible) determinar el valor exacto de c. Se usa una fórmula que se denomina notación “O” mayúscula, lo que significa el orden de complejidad: t = O[f(n)]. Esto significa que el tiempo de ejecución es del orden O[f(n)]. El objetivo del análisis de tiempo de algoritmos es encontrar los algoritmos con el menor orden de complejidad posible que resuelven el mismo problema. El algoritmo 1 de la búsqueda secuencial tiene claramente el orden de complejidad O(n). Para el algoritmo 2 de la búsqueda binaria se obtiene lo siguiente: Después de cada comparación, el tamaño de la lista a ordenar se disminuye a la mitad, tomando los siguientes tamaños: 1, ½, ¼, 1/8, 1/16, etc. En el peor caso esta búsqueda termina si se llega a la lista vacía. PROBLEMAS SEGÚN SU COMPLEJIDAD En calculabilidad se ha demostrado que hay problemas para los que no existe algoritmo que los resuelva. El estudio de los problemas decidibles, en el límite de la indecibilidad, es de lo que trata la complejidad. Prof. Viviane Oliveira Los problemas decidibles se clasifican según los recursos (espacio y/o tiempo) que consumen para ser resueltos usando siempre su mejor solución algorítmica conocida para la peor entrada posible. Problemas intratables: Son problemas decidibles que necesitan tantísimo tiempo para resolverse que no son factibles ni prácticos (según qué casos). Ejemplo de utilidad: claves de seguridad. Problema intratable: No existe un algoritmo de tiempo polinómico que resuelve el problema. Problemas tratables: Son problemas decidibles que usan un tiempo razonable 14 para resolverse. Problema tratable: Sí existe un algoritmo de tiempo polinómico que resuelve el problema. La frontera entre estos dos tipos de problemas decidibles es la misma que entre las funciones polinómicas y las funciones exponenciales. La frontera será tanto mayor cuanto mayor sea el valor de la entrada. Los problemas intratables suponen que tienen, al menos, un algoritmo de tiempo exponencial que hace no factible su uso práctico. Al estar tratando con algoritmos con la “peor entrada” de todas las posibles puede ocurrir que para alguna entrada “no tan mala” el problema pueda resolverse o que el tiempo necesario para resolverse no sea, necesariamente, exponencial. Esto permite un uso práctico puntual (optimización). No obstante, no suele ser habitual que esto suceda.  La intratabilidad de un problema es independiente de la codificación y del modelo de cálculo.  Los diferentes modelos abstractos de cálculo pueden simularse entre sí con una pérdida polinómica de eficiencia como máximo.  Todos los modelos de cálculo son equivalentes respecto a la complejidad temporal. Esto permite estudiar los problemas sin tener que preocuparnos de la “máquina” que estemos usando. Un problema se denomina Tratable si existe un algoritmo de complejidad polinomial para resolverlo. En caso contrario se denomina Intratable. Esta clasificación es importante porque, cuando el tamaño del problema aumenta, los algoritmos de complejidad polinomial dejan de ser utilizables de manera gradual. El caso límite de los problemas Intratables son los problemas Indecibles, son problemas para los cuales no existen algoritmos que los resuelvan. Prof. Viviane Oliveira Algoritmos Determinísticos: Tiene la propiedad de que el resultado de cada operación, se define en forma única. En Ciencias de la computación, un algoritmo no determinístico es un algoritmo que con la misma entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de la ejecución de un algoritmo no determinístico. Opción no determinista: es el conjunto de transiciones posibles para la misma situación inicial y las evoluciones diferentes asociadas de la función de transición. 15 Si para cada situación diferente hay una sola regla de transición posible la máquina es determinista. Las máquinas indeterministas aceptan una entrada si existe, al menos, una secuencia de opciones no deterministas que hace que la respuesta al problema sea “SI”. Con las máquinas indeterministas nos ahorramos explicitar todas las combinaciones posibles. Con las máquinas deterministas tenemos que especificar todas y cada una de las combinaciones posibles. Instrucción de opción no determinista: es una nueva instrucción del modelo de cálculo abstracto lenguaje de programación no determinista. Esta instrucción está asociada a un número fijo de alternativas y para cada una de ellas el algoritmo sigue un camino distinto y, al final, decide aceptar o no la entrada. Notación Asintótica La notación asintótica nos permite realizar simplificaciones sustanciales aun cuando estemos interesados en medir algo más tangible que el tiempo de ejecución, tal como es el número de veces que se ejecuta una instrucción dentro del programa. Se denomina notación asintótica porque trata acerca del comportamiento de funciones en el límite, esto quiere decir, para valores suficientemente grandes de su parámetro. Esto hace que los valores pequeños de las entradas no sean interesantes. Dicho de otra manera, estamos interesados en las tasas de crecimientos en lugar de los valores concretos. Prof. Viviane Oliveira  Consideraciones Generales  Si un programa se va a ejecutar muy pocas veces, los costes de codificación y depuración son los que más importan, relegando la complejidad a un papel secundario.  Si a un programa se le prevé un uso por un período de tiempo largo, hay que pensar que le tocará mantenerlo a otra persona y, por tanto, conviene tener en cuenta su legibilidad, incluso a costa de la complejidad de los algoritmos empleados.  Si podemos garantizar que un programa sólo va a trabajar sobre datos 16 pequeños (valores bajos de N), el orden de complejidad del algoritmo que usemos suele ser irrelevante, pudiendo llegar a ser incluso contraproducente. Por ejemplo, si disponemos de dos algoritmos para el mismo problema, con tiempos de ejecución respectivos: algoritmo tiempo complejidad f 100 n O(n) g n2 O(n2) Asintóticamente, "f" es mejor algoritmo que "g"; pero esto es cierto a partir de N > 100. Si nuestro problema no va a tratar jamás problemas de tamaño mayor que 100, es mejor solución usar el algoritmo "g". El ejemplo anterior muestra que las constantes que aparecen en las fórmulas para T(n), y que desaparecen al calcular las funciones de complejidad, pueden ser decisivas desde el punto de vista de ingeniería. Veamos otro ejemplo. algoritmo tiempo complejidad f n O(n) g 100 n O(n) Aun siendo dos algoritmos con idéntico comportamiento asintótico, es obvio que el algoritmo "f" es siempre 100 veces más rápido que el "g", y por lo tanto, candidato primero a ser utilizado.  Usualmente un programa de baja complejidad en cuanto a tiempo de ejecución, suele conllevar un alto consumo de memoria; y viceversa. A Prof. Viviane Oliveira  veces hay que sopesar ambos factores, quedándonos en algún punto de compromiso.  En problemas de cálculo numérico hay que tener en cuenta más factores que su complejidad pura, o incluso que su tiempo de ejecución: queda por considerar la precisión del cálculo, el máximo error introducido en cálculos intermedios, la estabilidad del algoritmo, etc.  O(1): Complejidad constante  O(log(n)): Complejidad logarítmica, suele aparecer en algoritmos con 17 iteración o recursión no estructurada (búsqueda binaria)  O(n) Complejidad lineal, es en generalmente una complejidad buena y bastante usual. Suele aparecer, en la evaluación de ciclos simples cuando la complejidad de las operaciones interiores es constante o en algoritmos de recursión estructurada.  O(n log(n)): Aparece en los algoritmos con recursión no estructurada (por ejemplo Quick Sort) y se considera una complejidad buena.  O(n2): Complejidad cuadrática, aparece en ciclos o recursiones doblemente anidadas  O(n3): Complejidad cúbicas, aparece en ciclos o recursiones triples, para un valor de n empieza a crecer en exceso.  O(nk): Complejidad polinómica, n > 3, si k crece la complejidad del programa es bastante mala.  O(2n): Complejidad exponencial, debe evitarse a medida de lo posible, puede aparecer en rutinas recursivas, que contengan dos o más llamadas internas. En problemas donde aparece esa complejidad suele hablarse de “explosión combinatoria“ Terminología comúnmente usada: O(1) Complejidad Constante O(n) Complejidad lineal O(n2) Complejidad cuadrática O(n3) Complejidad cúbica O(nm) Complejidad polinomial Prof. Viviane Oliveira O(mn) Complejidad exponencial O(log n) Complejidad logarítmica O(n!) Complejidad factorial Problemas P y NP Volvemos a mencionar algunos conceptos anteriormente citados y 18 abordaremos de forma sencilla los problemas NP (algoritmo no determinístico), que componen un universo tan directo y al mismo tiempo difícil, y sus soluciones. Por otro lado, comentaremos que son los problemas P (algoritmo determinístico polinomial). La Complejidad Computacional es una rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable, comúnmente se estudia el tiempo y el espacio, teniendo en cuenta la noción del problema. La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. Existen diferencias entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no se conoce ningún algoritmo polinómico, es decir no es polinómico. Tiempo polinomial En computación cuando el tiempo de ejecución de un algoritmo es menor que un cierto valor calculado, obviamente usando una formula polinomial como por ejemplo logarítmica, lineales, cuadráticas o cubicas, se dice que dicho problema se puede resolver en un tiempo polinómico. Prof. Viviane Oliveira  Clasificación de los Problemas Los problemas matemáticos los podemos dividir en dos grupos:  Problemas indecidibles: Aquellos que no se pueden resolver mediante un algoritmo.  Problemas decidibles: Aquellos que cuentan al menos con un algoritmo para su cómputo. Sin embargo, un problema decidible puede no ser solucionado por un 19 computador, porque el algoritmo requiere un número elevado de operaciones para resolverlo. Esto permite separar los problemas decidibles en dos. Problemas Tratables Son los problemas que cuentan con al menos una solución polinomial. Ejemplo: Todos los algoritmos a los que se la ha podido establecer su tiempo de ejecución. Problemas Intratables La cuestión de la inclusión estricta entre las clases de complejidad P y NP es uno de los problemas abiertos más importantes de las matemáticas.1 Veamos un ejemplo sencillo. Probablemente casi todos nos hemos olvidado de cómo calcular manualmente una raíz cuadrada. Pero es casi seguro que todos sepamos elevar un determinado número al cuadrado. Llegamos a la 1 El Instituto Clay de Matemáticas (Cambridge, Massachusetts) premia con un millón de dólares a quién sea capaz de lograr la resolución de esta conjetura. http://www.claymath.org/millennium/ Prof. Viviane Oliveira conclusión que resolver una raíz cuadrada (que existe un método muy laborioso) es más complicado o lento que la operación inversa. Si un problema nos pide que comprobemos si un número determinado n es la raíz cuadrada de x podríamos resolverlo de dos formas:  Calculando la raíz de x y comparando con n (proceso lento y engorroso)  O bien, elevando al cuadrado a n y comparando con x (simple multiplicación n* n) 20 La conclusión que sacamos de éste sencillo ejemplo es que en algunos problemas comprobar la solución es más eficiente que calcularla. La complejidad de la función “elevar al cuadrado” es más simple que calcular la raíz cuadrada. ¿Y qué tiene que ver todo esto con P=NP? Pues, P es la clase de complejidad que contiene problemas de decisión que se pueden resolver en un tiempo polinómico. P contiene a la mayoría de problemas naturales, algoritmos de programación lineal, funciones simples, etc. Por ejemplo la suma de dos números naturales se resuelven en tiempo polinómico (para ser más exactos es de orden 2n). Entre los problemas que se pueden resolver en tiempo polinómico nos encontramos con diversas variedades como los logarítmicos (log(n)), los lineales (n), los cuadráticos (n2), los cúbicos (n3),... Volviendo al ejemplo principal llegamos a la conclusión que la función de elevar al cuadrado está contenida en la clase P. La clase de complejidad NP contiene problemas que no pueden resolverse en un tiempo polinómico. Cuando se dice que un algoritmo no puede obtener una solución a un problema en tiempo polinómico siempre se intenta buscar otro procedimiento que lo consiga mejorar. Frente a los problemas contenidos en P tienen métodos de resolución menos eficaces. Podemos ver que la operación de calcular la raíz cuadrada se encuentra contenida en esta clase. Si nos resulta sencillo encontrar una solución para un determinado problema, sabemos comprobar si la solución es cierta (simplemente comparar), por lo que P es un subconjunto de la clase NP. La gran cuestión es si ocurre lo mismo a la inversa, es decir, si tenemos un problema que sabemos comprobar Prof. Viviane Oliveira fácilmente si un resultado es una solución, ¿sabemos calcular una solución sencillamente? ¿Todo problema se puede resolver en tiempo polinómico? Las clases P y N P  Son clases de problemas de decisión. La “N” de “NP” viene de la generación no determinística y la “P” de la verificación polinomial.  Un problema de decisión pertenece a la clase P si existe un algoritmo 21 determinístico polinomial, en el largo de la entrada, que lo resuelve.  Un algoritmo determinístico es esencialmente una máquina de Turing.  Un problema pertenece a la clase NP si es que es posible generar una solución. Algunos ejemplos de problemas de decisión en la clase P:  Dado un grafo (V, E), ¿es d la distancia mínima entre el nodo v1 y el nodo v2?.  Dada una lista de números L, ¿es la lista L 0 una ordenación ascendente de L? El proceso de generación y verificación puede ser aclarado con el siguiente esquema: Los problemas P y NP se relacionan con los problemas de decisión que requieren una respuesta de SI o No. Los problemas P pueden resolverse en Complejidad Polinómica por una Prof. Viviane Oliveira maquina determinista que se subdivide en Conjunto P y Conjunto Co-P, en la primera la respuesta es positiva y en la segunda la respuesta es negativa, ambas pueden ser verificadas rápidamente. Sus aplicaciones son el Algoritmo Dijkstra, el cual encuentra un camino corto desde un origen. Y también se utilizan en el Ciclo Euleriano que recorre cada vértice solo una vez en un grafo. Los problemas NP pueden resolverse en 22  Complejidad no polinómica por una maquina no determinística y se aplican en Camino Hamiltoniano, es decir, que pasa por cada vértice de un grafo una vez.  Tiempo polinómico por medio de una información extra (certificado) por ejemplo, verificar si un número es factorizable y dar un factor de él mismo. Problemas NP Un problema es de tipo P si existe un algoritmo polinomial que lo resuelve, dicho de forma intuitiva "si es fácil de resolver". Por ejemplo, cuando salimos de viaje, por ejemplo a Encarnación, normalmente queremos saber cuáles son los caminos que podemos tomar para ir del hotel a varios puntos de la ciudad. Este problema se resuelve fácilmente con el algoritmo de Dijkstra en O(n²) operaciones, por lo tanto es de tipo P. Un problema es de tipo NP si existe un algoritmo polinomial que es capaz de verificar una solución propuesta. Dicho intuitivamente, NP son los problemas Prof. Viviane Oliveira que son "fáciles de comprobar". Todo problema P es también NP, pero parece ser que no es al revés. Continuando con el ejemplo anterior, en el mapa tenemos marcado n lugares diferentes de la ciudad de Encarnación y queremos saber si existe un camino que pase por todos esos lugares exactamente una vez (sin repetición). Este problema es muy fácil de comprobar, si alguien propone una solución, rápidamente podemos comprobar en tan solo O(n) operaciones que el camino 23 que la persona propuso efectivamente pasa una sola vez por los n sitios. A pesar de que es fácil de comprobar, nadie sabe cómo resolverlo fácilmente. Todos los algoritmos que se han descubierto para este problema no son esencialmente mejores que una búsqueda por fuerza bruta (pero nadie ha comprobado que no exista un algoritmo polinomial para resolverlo). Este problema se conoce como el problema de Camino Hamiltoniano. Ejemplo puntual El premio por resolver alguno de estos problemas es de un millón de dólares. La descripción del Instituto Clay sobre el problema P versus NP es aproximadamente la siguiente: "Supongamos que estás organizando el alojamiento para un grupo de cuatrocientos estudiantes universitarios. El espacio es limitado y sólo cien de los estudiantes recibirán lugares en los dormitorios. Para complicar las cosas, el Decano te ha proporcionado una lista de parejas de estudiantes que presentan incompatibilidad entre sí, y pidió que ningún par de la lista aparezca en la distribución final." Este es un ejemplo de lo que los científicos en computación llaman un problema NP, porque es fácil comprobar si una determinada lista de cien estudiantes propuestos es satisfactoria (es decir, ningún par tomado de lista aparece en la lista de incompatibilidades entregadas por el decano). Sin embargo la tarea de generar una lista desde el principio parece ser tan difícil, como completamente impracticable. Prof. Viviane Oliveira De hecho, el número total de maneras de elegir un centenar de estudiantes procedentes de los cuatrocientos solicitantes ¡es mayor que el número de átomos en el universo conocido! Así que ninguna civilización futura podría esperar construir un supercomputador capaz de resolver el problema por fuerza bruta, es decir, revisando cada posible combinación de 100 estudiantes. Sin embargo, esta aparente dificultad sólo podría reflejar la falta de ingenio del programador. Uno de los problemas pendientes en ciencias de la 24 computación es determinar si existen problemas cuya respuesta puede ser rápidamente verificada, pero que requieren un tiempo imposiblemente largo para resolver, por cualquier procedimiento directo. La importancia del problema P y NP Básicamente el problema es "para ciertos problemas, lo mejor que podemos hacer es una búsqueda bruta", o, "para ciertos problemas el algoritmo más obvio es el mejor". NP como sabemos quiere decir "tiempo polinomial no-determinístico", y P "tiempo polinomial determinístico". Entonces los problemas o lenguajes con algoritmos que corren en tiempo polinomial están en P, y los problemas con algoritmo en tiempo polinomial no- determinístico en NP. Una caracterización más fácil de entender de problemas en NP es la siguiente: Sea A un algoritmo que tiene dos entradas, x que representa una instancia de un problema L y c que representa una solución al problema. Entonces L está en NP si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A y existe un c tal que A(x,c)=1, y que c sea una respuesta válida al problema. Generalmente a c se le llama solución, certificado, testigo o simplemente prueba, una prueba de que x tiene solución. La misma caracterización se puede hacer para P, pero esta vez el algoritmo no tiene una prueba c. Entonces decimos que L está en P si y solo si existe un algoritmo determinístico que corre en tiempo polinomial A tal que A(x)=1. Prof. Viviane Oliveira La gran diferencia está en el certificado. Los algoritmos para lenguajes en P determinan una solución, mientras que los algoritmos para lenguajes en NP verifican una solución. Una buena analogía es: si resolvemos un problema matemático por nosotros mismos (está en P), o estamos verificando la solución de otra persona (en NP). Entonces, la diferencia radica en que estamos comparando un proceso de 25 determinar una solución a un problema, contra un proceso de verificación de una solución ya dada para un problema. P vs NP en términos computacionales se refiere a cotas inferiores de problemas NP-completos. La conjetura es que para estos problemas no existe un mejor algoritmo que el de fuerza bruta, P≠NP. La mayoría de los científicos creen que esto es cierto, y de ahí surgen muchas alternativas para resolver problemas NP-completos como Búsqueda Local, Algoritmos Genéticos, etc. Y la eficiencia de estos métodos está en que pueden verificar soluciones en tiempo polinomial. En el aspecto filosófico, P vs NP hace la siguiente pregunta: ¿Puede la creatividad ser automatizada? Si escribimos un libro en el cual hemos trabajado 1 año, y lo enviamos a un periódico local para que un crítico primeramente lo lea, y luego lo destruya, digamos en un tiempo de 2 semanas, ¿Qué es más difícil, escribir nuevamente el libro o realizar la crítica al libro? Intuitivamente el proceso creativo es más complejo y requiere más tiempo, pero hasta que no tengamos una prueba que indique sin duda alguna, no lo sabremos. P vs NP no solo se refiere a problemas que solo interesan a las ciencias de la computación. Se refiere también a problemas fundamentales de otras ciencias. Podría decirse que es una de las preguntas más fundamentales de las matemáticas. Saber si podemos encontrar pruebas eficientemente nos da conocimiento de cómo resolver otros problemas muy difíciles. Prof. Viviane Oliveira  26 MAPA CONCEPTUAL DISEÑOS EFICIENTES Prof. Viviane Oliveira MAPA CONCEPTUAL TIEMPO DE EJECUCIÓN 27 Prof. Viviane Oliveira