Universidad Central de Venezuela Facultad de Ciencias Escuela de Computación

ND 2001– 05

Análisis de Algoritmos y Complejidad Eugenio Scalise, Rhadamés Carmona e-mail: [email protected], [email protected]

Caracas, Septiembre 2001

ND 2001–05

Análisis de Algoritmos y Complejidad Eugenio Scalise 1 Rhadamés Carmona 2 Septiembre 2001

RESUMEN El presente trabajo presenta una recopilación de notas y apuntes de docencia correspondientes al tema “Análisis de Algoritmos y Complejidad” que puede ser utilizado en diversos cursos de la Licenciatura en Computación e inclusive como material introductorio para algunos cursos de post-grado. Se presentan los conceptos y herramientas básicas para el cálculo de complejidad tanto en tiempo como en espacio, para algoritmos escritos en lenguajes imperativos (incluyendo algoritmos recursivos). Estas herramientas están acompañadas de ejemplos didácticos que ilustran su utilización. Se presenta también una reseña sobre las técnicas clásicas para la resolución de problemas y sus correspondientes estudios de complejidad en tiempo. Finalmente, se presenta una breve introducción a la teoría de problemas NPcompletos. Cabe destacar que estas notas de docencia están acompañadas de un conjunto de referencias bibliográficas que complementan significativamente los conceptos aquí introducidos. Palabras Clave: análisis de algoritmos, complejidad, complejidad en tiempo, complejidad en espacio, complejidad de algoritmos recursivos, problemas NP, problemas NP-completos.

1

Laboratorio MeFIS - Centro ISYS e-mail: [email protected]

2

Laboratorio de Computación Gráfica e-mail: [email protected]

CONTENIDO 1

Introducción........................................................................................ 2

2

Herramientas para el Análisis de Complejidad .................................. 3 2.1 Tasas de crecimiento ............................................................................................ 3 2.2 Análisis de Complejidad de Tiempo ................................................................... 4 − Regla de la suma............................................................................................... 5 − Regla del producto............................................................................................ 5 − Análisis de complejidad en tiempo de las instrucciones de un lenguaje.......... 6 2.3 Análisis de Complejidad en Espacio................................................................... 8 − Requerimientos estáticos de espacio ................................................................ 8 − Requerimientos dinámicos de espacio............................................................ 10 2.4 Ejemplo................................................................................................................ 10 2.5 Análisis de Complejidad en programas recursivos ......................................... 12 − Cota Superior de T(n)..................................................................................... 13 − Forma Cerrada de T(n) ................................................................................... 14 − Solución General para una clase de recurrencias........................................... 14

3

Técnicas clásicas para la resolución de problemas ........................... 15 3.1 Divide y Conquista ............................................................................................. 15 3.2 Balanceo .............................................................................................................. 16

4

Modelos de Computación.................................................................. 17 4.1 RAM (Random Access Machine)...................................................................... 17 4.2 RASP (Random Access Stored Program Machine) ........................................ 17 4.3 Turing Machine (Máquina de Turing)............................................................. 17

5

Clasificación de los problemas según su complejidad....................... 18

Referencias .............................................................................................. 19

1 Introducción Un algoritmo es "una secuencia finita de instrucciones, cada una de las cuales tiene un significado preciso y puede ejecutarse con una cantidad finita de esfuerzo en un tiempo finito" [AHU 83]. Un programa es un algoritmo expresado en un lenguaje de programación específico. Los criterios para evaluar programas son diversos: eficiencia, portabilidad, eficacia, robustez, etc. El análisis de complejidad está relacionado con la eficiencia del programa. La eficiencia mide el uso de los recursos del computador por un algoritmo. Por su parte, el análisis de complejidad mide el tiempo de cálculo para ejecutar las operaciones (complejidad en tiempo) y el espacio de memoria para contener y manipular el programa más los datos (complejidad en espacio). Así, el objetivo del análisis de complejidad es cuantificar las medidas físicas: "tiempo de ejecución y espacio de memoria" y comparar distintos algoritmos que resuelven un mismo problema. El tiempo de ejecución de un programa depende de factores como [AHU 83]: − los datos de entrada del programa − la calidad del código objeto generado por el compilador − la naturaleza y rapidez de las instrucciones de máquina utilizadas − la complejidad en tiempo del algoritmo base del programa El tiempo de ejecución debe definirse como una función que depende de la entrada; en particular, de su tamaño. El tiempo requerido por un algoritmo expresado como una función del tamaño de la entrada del problema se denomina complejidad en tiempo del algoritmo y se denota T(n). El “comportamiento límite” de la complejidad a medida que crece el tamaño del problema se denomina complejidad en tiempo asintótica. De manera análoga se pueden establecer definiciones para la complejidad en espacio y la complejidad en espacio asintótica. En muchos casos, la complejidad de tiempo de un algoritmo es igual para todas las instancias de tamaño n del problema. En otros casos, la complejidad de un algoritmo de tamaño n es distinta dependiendo de las instancias de tamaño n del problema que resuelve. Esto nos lleva a estudiar la complejidad del peor caso, mejor caso, y caso promedio. Para un tamaño dado (n), la complejidad del algoritmo en el peor caso resulta de tomar el máximo tiempo (complejidad máxima) en que se ejecuta el algoritmo, entre todas las instancias del problema (que resuelve el algoritmo) de tamaño n; la complejidad en el caso promedio es la esperanza matemática del tiempo de ejecución del algoritmo para entradas de tamaño n, y la complejidad mejor caso es el menor tiempo en que se ejecuta el algoritmo para entradas de tamaño n. Por defecto se toma la complejidad del peor caso como medida de complejidad T(n) del algoritmo. Aún cuando son los programas que consumen recursos computacionales (memoria, tiempo, etc.) sobre una máquina concreta, se realiza el análisis sobre el algoritmo de base, considerando que se ejecuta en una máquina hipotética.

2

2 Herramientas para el análisis de complejidad Esta sección presenta un conjunto de herramientas utilizadas para el cálculo de complejidad de algoritmos en tiempo y espacio. Para mayor detalles se recomienda [AHU 74] y [AHU 83]. 2.1 Tasas de crecimiento Definición 1: Sean f y g dos funciones, f,g: Ν→ℜ+-{0}. Se dice que f = Ο(g) (f es de orden g) si y sólo si existe c∈ℜ+ y n0 ∈Ν tal que ∀n>n0 se cumpla f(n) ≤ c.g(n). (Ν no incluye el 0). La relación Ο denota una dominancia de funciones, en donde la función f está acotada superiormente por un múltiplo de la función g (f es dominada por c.g(n)). Así, la expresión f=Ο(g) refleja que el orden de crecimiento asintótico de la función f es inferior o igual al de la función g. Ejemplo : f(n) = 3n3 +2n2 y g(n) = n3 . Aunque f(0) está definida, podemos restringir su dominio a f(n) con n>0. Así, que f,g:Ν→ℜ+-{0}, y además ∃c∈ℜ+ (c = 5) y n0 ∈Ν (n0 = 0) tal que ∀n>n0 se cumple f(n) ≤ c.g(n). Así, 3n3 +2n2 = Ο(n3 ). A continuación se enumeran alguna propiedades de la relación O: − Si c∈ℜ+, y f: Ν→ℜ+-{0}, entonces, c.f=Ο(f) − Si c∈ℜ+, y f: Ν→ℜ+-{0}, entonces Ο(c.f)≡Ο(f) − Si f1=Ο(g1) ∧ f2=Ο(g2) entonces f1+f2=Ο(g1+g2) − Si f1=Ο(g1) ∧ f2=Ο(g2) entonces f1.f2=Ο(g1.g2) − Si f1=Ο(g) ∧ f2=Ο(g) entonces f1+f2=Ο(g) Definición 2: Sean f y g dos funciones, f,g: Ν→ℜ+-{0}. Se dice que f y g tienen igual orden de crecimiento (f=Θ(g)) si y sólo si existe c,d ∈ℜ+ y n0 ∈Ν tal que ∀n>n0 se cumpla d.g(n)≤f(n)≤c.g(n). Se puede demostrar también que Θ es una relación de orden (total) por ser reflexiva, simétrica y transitiva: f = Θ(f), f = Θ(g) ⇒ g = Θ(f), f = Θ(g) ∧ g = Θ(h) ⇒ f = Θ(h). Además, Θ satisface las siguientes propiedades: − Sean f y g dos funciones, f,g: Ν→ℜ+-{0}. f=Θ(g)⇔f=Ο(g) ∧ g=Ο(f) − Si c∈ℜ+, y f: Ν→ℜ+-{0}, entonces, c.f=Θ(f) − Si c∈ℜ+, y f: Ν→ℜ+-{0}, entonces Θ(c.f)≡Θ(f) − Si f1=Θ(g1) ∧ f2=Θ(g2) entonces f1+f2=Θ(Max{g1,g2}) − Si f1=Θ(g1) ∧ f2=Θ(g2) entonces f1.f2=Θ(g1.g2) − Si f1=Θ(g) ∧ f2=Θ(g) entonces f1+f2=Θ(g) − (f+g)k = Θ(f k +gk ) 3

En la siguiente figura [Bro 89], se presenta un ejemplo de dos funciones f y g con la misma tasa de crecimiento.

Fig. 1.- Dos funciones f y g con la misma tasa de crecimiento 2.2 Análisis de Complejidad de Tiempo El tiempo de ejecución depende de diversos factores. Se tomará como más relevante el relacionado con la entrada de datos del programa, asociando a un problema un entero llamado tamaño del problema, el cual es una medida de la cantidad de datos de entrada. De manera general, la complejidad T(n) de un algoritmo es de Ο(f(n)) si T,f: Ν→ℜ+-{0}, y ∃c∈ℜ+ y n0 ∈Ν tal que ∀n>n0 se cumpla T(n )≤ c.f(n). (ver Definición 1). Generalmente, nos interesa la tasa de crecimiento f(n) del tiempo requerido para resolver instancias más grandes del problema, basándonos en el concepto de dominancia de funciones. La tasa de crecimiento obtenida para hallar el orden de complejidad en tiempo de un algoritmo, permite entre otras cosas: •

Determinar el comportamiento del algoritmo en función del tamaño del problema, y reflejar un tamaño razonable del mismo

•

Determinar cuánto tiempo de cómputo aumenta al incrementar el tamaño del problema en una unidad (f(n+1)-f(n))

•

Facilita la comparación de algoritmos y permite determinar entre varios algoritmos, cuál será el más eficiente en teoría (el que tiene menor tasa de crecimiento).

Las tasas de crecimiento suelen ser logarítmicas, polinomiales, y exponenciales. A continuación tenemos una comparación entre las tasas de crecimiento más comunes: log2n A[j].NumCarnet entonces aux := A[j-1]; A[j-1] := A[j]; A[j] := aux; fsi fpara fpara facción

Para hacer el cálculo de complejidad del algoritmo de burbuja es necesario calcular en primer lugar la complejidad en tiempo del ciclo interno. En cuanto al condicional que se encuentra dentro del ciclo interno, la prueba de la condición requiere un tiempo constante 10

c1 . Las acciones internas del condicional (3 asignaciones) son de orden constante (que se pueden asumir iguales, por ejemplo c2 ). Luego, por la regla 4 (regla del condicional) se tiene Tcond(n) = O(max{c1 , c2 }) = c. La complejidad del ciclo interno viene dada por: n

TCicloInterno(n) =

∑ Tj(n) + 2.c.( n − i) =

j =i +1

n

∑ c + 2.c.( n − i) = c.(n-i)+2.c.(n-i) = 3.c.(n-i)

j =i +1

El ciclo externo se ejecuta n-1 veces; luego, su complejidad viene dada por: TCicloExterno(n) =

n −1

n −1

i =1

i =1

∑ TCicloInterno (n) + 2.c.(n − 1) = 3.c ∑ (n − i) + 2.c.( n − 1)

n −1  n−1  n.( n − 1)  = 3.c  ∑ n − ∑ i  + 2.c.( n − 1) = 3.c  n.( n − 1) − + 2.c.( n − 1) 2  i =1    i=1

=

[

3 3 1 1 .c.n.( n − 1) + 2.c.(n − 1) = .c.n 2 − c.n − 2.c = 3.c.n 2 − c.n − 4.c 2 2 2 2

]

Luego, la complejidad en tiempo T(n) del algoritmo de la burbuja es: T(n) = TCicloExterno (n) que es O(n2 ); finalmente, T(n)= O(n2 ). Entonces, para ejecutar el algoritmo de ordenamiento mostrado arriba, es necesario un tiempo proporcional al cuadrado del número de elementos a clasificar. La complejidad de un algoritmo también se puede contabilizar en base al número de operaciones fundamentales que realiza (en este ejemplo, las comparaciones), ya que las otras operaciones generarán un factor multiplicativo o aditivo en la función T(n), el cual es despreciable al calcular el orden de complejidad. Así que para calcular el orden del algoritmo de burbuja basta con hallar el número de comparaciones C(n) y determinar el orden a partir de éste. Según esto, en la iteración i del ciclo interno se realizan: Ci(n) = n-i comparaciones. El ciclo externo se ejecuta n-1 veces; por lo tanto, el número de comparaciones C(n) viene dado por: n −1

C(n) =

∑ (n − i) = i =1

n(n − 1) n 2 − n = 2 2

que es O(n2 ); luego, T(n)= O(n2 ). Para calcular la complejidad en espacio del algoritmo, de manera ordenada, se determina la complejidad en espacio para cada tipo de objeto en el algoritmo, y luego se calcula la suma del número de palabras que requiere cada variable involucrada en el algoritmo. − El tipo Cadena es un arreglo de 40 caracteres, por lo que Cm(Cadena)=40+3=43 palabras de memoria. − El Tipo Reg require Cm(Reg)=1+43+1=45 palabras de memoria. − El Tipo Empleados requiere Cm(Empleados)=n.Cm(Reg)+3=43.n+3 palabras de memoria.

11

El algoritmo involucra: − Tres enteros: i,j,n, cada uno ocupa Cm(Entero)=1 palabra de memoria. − Una variable de tipo Reg: aux, que ocupa Cm(Reg)=45 − Un arreglo A de tipo Empleados que ocupa Cm(Empleados) palabras de memoria Así, la complejidad en espacio requerido viene dado por: 3.Cm(Entero)+1.Cm(Reg)+1.Cm(Empleados)=3+45+43.n+3=43.n+51 palabras lo cual es Ο(n). 2.5 Análisis de Complejidad en programas recursivos Para calcular la complejidad sobre programas recursivos se utilizan las herramientas citadas en la Sección 2.3 y adicionalmente se utilizan ecuaciones de recurrencia para expresar la función de complejidad en tiempo T(n). Esta sección presentará el análisis de complejidad en tiempo mediante un ejemplo intuitivo, se recomienda revisar [AHU 74], [AHU 83] y [GPK 94] para más detalle. A continuación, se presenta el algoritmo correspondiente a la función MergeSort utilizado como ejemplo a lo largo de esta sección: función MergeSort(n: entero; L: Lista) -> Lista var L1, L2: Lista; comienzo si (n=1) entonces Retornar Lista; sino L1 := Lista de los primeros n/2 elementos de L L2 := Lista de los últimos n/2 elementos de L retorna (Mezcla(MergeSort(n/2,L1),MergeSort(n/2,L2))); fsi ffunción

Esta función ordena una lista de elementos realizando particiones sucesivas hasta obtener listas de un elemento y aplicando el algoritmo tradicional de mezcla entre sub-listas ordenadas. Por ejemplo, para la lista (5, 2, 4, 6) la función MergeSort divide la lista hasta obtener sub-listas unitarias y en los retornos realiza las siguientes mezclas (cada nivel del gráfico corresponde a un nivel de la recursion):

5

2

4

6

mezcla

mezcla

2 5

4 6 mezcla

2 4 5 6 La función de complejidad T(n) para el algoritmo mergeSort viene dada por una definición recursiva. En particular, se distingue el tratamiento de listas unitarias y el tratamiento de listas de tamaño mayor o igual que dos.

12

Para el caso de listas unitarias (condición n=1 en la función mergeSort) se tiene una complejidad constante que denominaremos c1 . Para listas de tamaño superior a uno (parte else de la función mergeSort) el problema es dividido en dos sub-problemas de tamaño n/2 con un costo adicional para: − construir dos listas de tamaño n/2, con costo c3 .n − mezclar dos listas de tamaño n/2, con costo c4 .n Luego, tomando c2 = c3 + c4 , se tiene:

c1  T(n) =  2.T ( n 2) + c 2 .n

si si

n =1 n >1

donde se asume que n es potencia de 2 (n = 2k, k ≥ 0). Para determinar el orden de complejidad de la función mergeSort es necesario resolver la ecuación de recurrencia asociada a T(n). A manera de ejemplo, se presentarán tres enfoques para determinar el orden de un algoritmo cuya función T(n) es una ecuación de recurrencia: − Proponer una cota superior f(n) para T(n); o sea, demostrar que T(n) ≤ f(n) para un f dado − Hallar una forma cerrada 3 para T(n) − Emplear soluciones conocidas para recurrencias En lo que resta de esta sección se ilustrarán estos tres enfoques para resolver la función de complejidad en tiempo T(n) asociada a la función mergeSort. Cota Superior de T(n) Este enfoque persigue buscar una cota superior para T(n) proponiendo funciones f(n) candidatas y comprobando que efectivamente acotan superiormente a T(n). Para continuar con el ejemplo de la función mergeSort, suponga que para algún a se cumple que: f(n) = a.n.log2 (n) + b. Si tomamos n = 1, debe cumplirse b ≥ c1 [r1 ], para que se cumpla T(n) ≤ f(n). Para realizar una prueba por inducción, se supone que: T(k) ≤ a.k.log2 (k) + b, para todo k < n [1] Para iniciar la demostración, se supone que n ≥ 2, luego: T(n) ≤ 2.T ( n 2) + c 2 .n Aplicando [1], tenemos (suponiendo k = n/2): T(n) ≤ 2.[a. n 2 . log 2 ( n 2) + b ] + c 2 .n ≤ a.n.[log 2 ( n) − log 2 ( 2)] + 2.b + c 2 .n

3

una forma cerrada es una función (no recursiva) en términos de n y algunas constantes 13

≤ a.n. log 2 ( n) − a.n + 2.b + c 2 .n ≤ a.n. log 2 ( n) + b (siempre y cuando a ≥ c2 + b [r2 ]) Luego, si se seleccionan a y b de manera que cumplan con las restricciones [r1 ] y [r2 ] citadas anteriormente, por ejemplo: b = c1 y a = c1 + c2 , se cumple que para todo n: T(n) ≤ (c1 + c2 ).n.log2 (n) + c1 Luego, T(n) = O(n.log2 (n)). Cabe destacar que esta no es la tasa exacta de T(n), pero se comprueba que T(n) no es peor que c.n.log2 (n). Forma Cerrada de T(n) Utilizando la hipótesis de que n = 2k, se puede hallar una fórmula no recurrente (cerrada) para T(n). Para esto, se desarrolla T(n) realizando las sustituciones para: n, n/2, n/4, ... , 1: T(n) = 2.T(n/2) + c2 .n = 2.[2.T(n/4) + c2 .n/2] + c2 .n = 4.T(n/4) + 2.c2 .n = 4.[2.T(n/8) + c2 .n/4] + 2.c2 .n = 8.T(n/8) + 3.c2 .n = ... (sust. i-ésima)

= 2i.T(n/2i) + i.c2 .n

Si n = 2k , la expansión termina cuando i = k. Luego: T(n) = 2k .T(n/2k ) + k.c2 .n = 2k .T(1) + k.c2 .n = 2k .c1 + k.c2 .n Sustituyendo k = log2 (n), se tiene: T(n) = 2 log2 ( n) .c1 + n. log 2 ( n).c 2 = n log2 ( 2) .c1 + n. log 2 ( n).c 2 = n.c1 + n. log 2 (n ).c 2 Luego, T(n) = O( n. log 2 (n) ). Solución General para una clase de recurrencias La función mergeSort es un ejemplo típico de solución de un problema mediante la división en sub-problemas. Para este tipo de problemas, existe un teorema [AHU 74] que se cita a continuación. Teorema: Sean a, b y c constantes no negativas. La solución de la recurrencia: si n = 1 si n > 1

b  T(n) =  a.T ( n c ) + b.n

donde: a es el número de sub-problemas y c es el tamaño de cada uno. Si n es potencia de c se cumple que:

 O( n)  T(n) = O( n log n )  O( n logc a ) 

si a < c si si

a=c a>c

14

Por razones de espacio, no se cita la demostración del teorema; para mayor detalles de esta demostración se recomienda [AHU 83]. Este tipo de soluciones generales pueden utilizarse para hallar el orden de complejidad de funciones T(n). En particular, para la función de complejidad de mergeSort :

c1  T(n) =  2.T ( n 2) + c 2 .n

si si

n =1 n >1

se puede asumir (por simplicidad) que c1 = c2 y en consecuencia se tiene: b = c1 = c2 , a = c = 2. Aplicando el teorema presentado se puede afirmar que T(n) = O(n.log n).

3 Técnicas clásicas para la resolución de problemas En esta sección se discuten algunas técnicas de programación que son utilizadas con frecuencia para definir algoritmos eficientes. Entre estas técnicas se pueden citar: la técnica de divide y conquista (divide and conquer), balanceo, programación dinámica, backtracking y búsqueda local. En este trabajo sólo se discuten la técnica de “divide y conquista” y “balanceo”. 3.1 Divide y Conquista Un enfoque común para resolver un problema consiste en particionar un problema en partes mas pequeñas y combinar la solución de las partes como la solución general al problema. Cuando se aplica este enfoque de manera recursiva ofrece soluciones eficientes en las cuales los sub-problemas constituyen versiones reducidas del problema original. A manera de ejemplo [AHU 74], considere el problema de encontrar tanto el máximo como el mínimo de un conjunto de n elementos enteros. Por simplicidad, se asume que n es una potencia de 2. Una manera obvia de encontrar el máximo y el mínimo podría ser: función max_min(C: Conjunto_Enteros) → tupla_enteros; var max, min: entero max := cualquier elemento de C; min := max; para todos los x elementos restantes en C hacer si x > max entonces max:=x; fsi si x < min entonces min:=x; fsi fpara max_min := (max, min); ffuncion

Asumiendo n≥2, se puede calcular tanto el máximo como el mínimo de un conjunto efectuando 2(n-1) = 2n-2 comparaciones. Luego, T(n) = 2n-2 comparaciones. Utilizando un enfoque divide y conquista se puede dividir el conjunto C de entrada en dos conjuntos C1 y C2 de n/2 elementos; en cuyo caso, el algoritmo puede buscar tanto el

15

máximo como el mínimo de cada sub-conjunto, mediante aplicaciones recursivas. El algoritmo basado en esta estrategia viene dado por: función max_min(C: Conjunto_Enteros) → tupla_enteros; var max1, max2, min1, min2: entero; si || C || = 2 entonces // sea C el conjunto {a,b} return (max(a,b), min(a,b)); sino divide C en dos sub-conjuntos C1 y C2, cada uno con la mitad de los elementos (max1, min1) := max_min(C1); (max2, min2) := max_min(C2); return (max(max1,max2), min(min1,min2)); fsi ffuncion

Sea T(n) el número total de comparaciones requeridas por max_min para encontrar el máximo y el mínimo del conjunto C. Es obvio que T(2) = 1. Si n>2, T(n) es el número total de comparaciones utilizadas en las dos llamadas de max_min sobre conjuntos de tamaño n/2, más las dos comparaciones utilizadas para determinar el máximo y el mínimo de los sub-conjuntos. Luego: 1 n=2  T ( n) =  2T ( n / 2) + 2, n > 2 La ecuación de recurrencia T(n) puede ser resuelta de manera general. La función 3 T(n) = n − 2 2

es la solución de la ecuación de recurrencia presentada anteriormente. Por lo tanto, se demuestra que la segunda solución es más eficiente que la primera. 3.2 Balanceo En general, las estrategias de particionar un problema utilizan sub-problemas de igual tamaño, pero esto no es una condición necesaria. Por ejemplo, la clasificación u ordenamiento por insersión puede considerarse como la división de un problema en dos sub-problemas, uno de tamaño 1 y otro de tamaño n-1, con un costo máximo de n pasos para combinarlos. Esto se puede expresar la mediante la ecuación de recurrencia: T(n) = T(1) + T(n-1) + n que es de orden O(n2 ). Si se utiliza la clasificación por intercalación (mergesort), que divide el problema en dos sub-problemas de tamaño n/2 y combina las permutaciones obtenidas, se tiene una función de complejidad representada por: 0 n =1  T ( n) =  2T ( n / 2) + n − 1, n > 1 que es de orden O(n.log n). Como principio general, dividir un problema en sub-problemas iguales o casi iguales es un factor crucial para la obtención de un buen rendimiento. 16

4 Modelos de Computación En esta sección se definen diversos modelos teóricos de computación utilizados para evaluar la complejidad de algoritmos. Estos modelos permiten hacer un estudio formal de la complejidad de un programa (asociado a un algoritmo) en términos de modelos de computación concretos, cercanos a los modelos de cómputo reales. Esto permite hacer estudios comparativos independientes de la plataforma de hardware. 4.1 RAM (Random Access Machine) Una máquina de acceso aleatorio (RAM – Random Access Machine) modela un computador con un acumulador, cuyas instrucciones no pueden modificar el programa fuente. Una RAM esta formada por una cinta de sólo lectura, una cinta de sólo escritura, un programa y una memoria. Tanto la cinta de entrada como la cinta de salida almacenan valores enteros. La cinta de salida está inicialmente en blanco. Cada vez que se lee/escribe de una cinta, la cabeza de lectura/escritura correspondiente se desplaza un elemento hacia la derecha. La memoria está formada por una secuencia de registros r0 ,...,rm; capaces de almacenar un entero. Todos los cálculos son realizados en el registro r0 , el cual es denominado “acumulador”. Un programa de la RAM está formado por una secuencia de instrucciones (aritméticas, I/O, indirecciones, saltos, etc.); cada instrucción esta conformada por un código de operación y una dirección. Para realizar los cálculos de complejidad de un programa en una RAM se calcula el tiempo necesario para ejecutar cada instrucción y la cantidad de registros utilizados. En general, existen dos criterios para evaluar la complejidad: el criterio uniforme (en el cual se asume que todas las operaciones tardan el mismo tiempo en ejecutarse) y el criterio logarítmico (en el cual se establece un costo a cada tipo de operación). 4.2 RASP (Random Access Stored Program Machine) Este modelo es similar a la RAM, con la diferencia de que el programa es almacenado en memoria y en consecuencia, puede modificarse a si mismo. El programa es entonces almacenado en los registros de memoria de la RASP, tomando en cuenta que cada instrucción de la RASP ocupa dos registros (uno para el tipo de operación y otro para la dirección). Está demostrado que un programa que se ejecuta con una complejidad T(n) en una RAM, puede ser ejecutado en una RASP con una complejidad k.T(n). 4.3 Turing Machine (Máquina de Turing) Una máquina de turing multicintas (TM – Turing Machine) está compuesta por un número k de cintas de capacidad infinita. Cada cinta almacena un conjunto de símbolos propios de la máquina y posee una cabeza lectora/escritora. La operación de una máquina de turing viene dada por un programa denominado control finito. De acuerdo al estado actual del control finito y de los símbolos de las cintas, la máquina de Turing puede realizar cualquiera de las siguientes operaciones:

17

− Cambiar el estado del control finito. − Escribir nuevos símbolos sobre los actuales en cualquiera de las celdas de las diversas cintas. − Mover cualquiera de las cabezas de las cintas a la izquierda o a la derecha. Una máquina de turing puede ser vista formalmente como una 7-tupla: (Q, T, I, δ, b, q0 , qf), donde: Q es el conjunto de estados, T es el conjunto de símbolos de las cintas, I es el conjunto de símbolos de entrada, b es el símbolo blanco o nulo, q0 es el estado inicial, qf es el estado final y δ es la función de transición de estados. Una máquina de turing constituye un modelo formal para reconocedores de lenguajes. Para esto es necesario colocar en la primera cinta la cadena a ser reconocida; luego, la cadena es reconocida si y sólo si, partiendo del estado inicial, la máquina realiza una secuencia de pasos tales que alcanza un estado de aceptación. El modelo definido por una máquina de turing es utilizado para determinar cotas inferiores para las funciones de complejidad tanto en espacio como en tiempo de la solución de un problema determinado. Este modelo general es conocido también como Máquina de Turing Determinísitica (MTD). Adicionalmente, se puede definir una Máquina de Turing No Determinística (MTND) como aquella en la cual la función de transición δ tiene más de un resultado para pares estado-símbolo. Desde otro punto de vista, puede afirmarse que un programa en una MTND difiere de un programa de una MTD en que el primero se ejecuta en dos etapas: etapa de pronóstico (que consiste en obtener una secuencia de pronóstico o cadena inicial para ejecutar el programa de la MT) y una etapa de chequeo (que opera bajo las mismas reglas que una MTD).

5 Clasificación de los problemas según su complejidad Si se estudia la complejidad desde el punto de vista de reconocimiento de lenguajes, se utilizan como modelos base las máquinas de turing. Según esto, pueden clasificarse los lenguajes en diversas clases: − La clase P: es la clase de lenguajes que pueden ser reconocidos por una máquina de turing en tiempo polinómico. − La clase NP: es la clase de lenguajes que pueden ser reconocidos por una máquina de turing no determinística en tiempo polinómico. Estas definiciones están basadas en la teoría de lenguajes y en general, es conveniente destacar que para hacer un estudio de un algoritmo bajo la teoría de problemas P/NP es necesario reescribir el problema como un problema de reconocimiento de lenguajes (específicamente como un problema de decisión). Esto permite que problemas de diversas disciplinas sean tratados como problemas de reconocimiento de lenguajes, aplicando así un razonamiento teórico general. Dentro de la clase de problemas catalogados como NP se diferencia el conjunto NPcompleto. Se dice que un lenguaje L0 es NP-completo si está en NP y todo lenguaje L en

18

NP puede ser transformado en tiempo polinomial en L0 . Cabe destacar que tanto L como L0 representan problemas, expresados como lenguajes. Las relaciones entre las clases de problemas se muestran en la siguiente gráfica: NP

NP-completo

P

Para probar que un problema π es un problema NP-completo se debe: − Expresar π como un lenguaje L; en particular como un problema de decisión. − Mostrar que L ∈ NP, esto es, mostrar que L puede ser reconocido por una máquina de turing no determinísitica. − Seleccionar un problema NP-completo conocido L’ − Definir una transformación f: L’ → L. − Probar que f es polinomial La teoría de problemas NP-completos permite utilizar una base formal para saber si un problema es intratable o no. En general, los problemas clasificados dentro de la clase P se consideran tratables o factibles computables, mientras que los problemas clasificados dentro de la clase NP se consideran infactibles o intratables. Para mayor detalle de este tema, se recomienda [GJ 79].

Referencias [AHU 74]

AHO A., HOPCROFT J., ULLMAN J. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Company. 1974.

[AHU 83]

AHO A., HOPCROFT J., ULLMAN J. Data Structures and Algorithms. Addison-Wesley Publishing Company. 1983.

[Bro 89]

BROOKSHEAR J. G., Theory of Computation. Formal Languages, Automata and Complexity. The Benjamin/Cummings Publishing Company, Inc., Reedwood City, California, USA. 1989.

[GJ 79]

GAREY M., JOHNSON D. Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman & Co. 1979.

[GPK 94]

GRAHAM R., PATASHNIK O., KNUTH D.E. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Publishing Company. 2nd. Edition. March 1994.

[Mat 97]

MATTEO A. Apuntes del curso "Estructuras de Datos y Análisis de Algoritmos" . Postgrado en Ciencias de la Computación. 1997. 19