Bloque de Colores

Problema de Algoritmia Básico: Simulación del Caso Promedio

Icono de Post February 29 2012 :: Algoritmia, Estadística, Probabilidad, Python ::

Finalmente para analizar el caso promedio, decidí realizar una serie de simulaciones en Python, aproveche de paso, para presentar este programa como trabajo práctico final en la materia “Lenguajes de Scripting” de la facultad. El código del programa de la simulación puede encontrarse aquí, para correrlo compilar algo.c, ejecutar limpiar.sh y luego version-1-0.py. Las muestras se guardan en formato CSV en la carpeta “resultados/muestras” y los reportes en “resultados/reportes”.

Algunas notas sobre la simulación

Me interesaba analizar específicamente el comportamiento de la porción del algoritmo en la que se itera a travéz de la lista pasados que es la porción variable del mismo. Para hacer esto, cree una variable global total y en cada iteración por la lista pasados en la función esta_en_lista() se la incrementa en uno. El programa escribe luego en STDOUT el valor de esta variable al finalizar. Ver algo.c.

En el script de Python se genera una lhttps://github.com/emluque/Post_Stuff/blob/master/Problema_Algoritmia_Basico/Simulacion/version-1-0.pyista randomizada se levanta un proceso al que se le pasa esta lista como argumento y luego se lee el STDOUT del proceso para obtener el costo. Esto se hace en el archivo: muestras.py y la porción de código que hace esto es:


  def generar_lista(self):
    lista = []
    for i in range(self.n):
      lista.append(random.randint(1, self.k))
    return ",".join( [str(x) for x in lista])

  def generar_resultado(self, lista ):
    process = subprocess.Popen(["algoritmo/algo", lista] , shell=False, stdin=subprocess.PIPE, stdout=subprocess.PIPE)
    res = ""
    for char in process.stdout.read():
      res += char
    
    process.wait()
    #Esta linea que sigue es medio al dope
    if (process.returncode != None):
      if(process.returncode < 0):
        print("----")
        print(process.returncode)
        print("----")
        raise NameError("Tio, No andubo el proceso.") 
    else:   
      process.kill()

    return int(res)

  def generar_resultados(self):
    for i in range(self.cant):
      strr = self.generar_lista();
      a = self.generar_resultado( strr )
      self.resultados.append(a)

Resultados

Un conjunto de resultados pregenerados (una corrida completa del programa puede tardar varias horas) puede verse aquí.

Reportes de Tipo 1

Lo primero que podemos ver en los reportes de tipo 1 es como a mayor tamaño de muestra, la función va tendiendo a un tipo de gráfica especifica. Que no es exactamente igual para diferentes tamaños de alfabeto y cadena, pero se acerca a un Campana de Gauss aunque un poco deformada en la región derecha y con una media corrida un poco hacia la izquierda del rango de valores posibles.

Por ejemplo, este es el gráfico obtenido para tamaño de cadena 10, tamaño de alfabeto 10 con 100000 muestras:

Y este es para 200,200,100000:

Reportes de Tipo 2

Los reportes de tipo 2, permiten ver el comportamiento de la gráfica manteniendo fijo el tamaño de cadena y de muestra.

Que nos muestra el reporte de tipo 2?

Bueno lo que vemos es que manteniendo el tamaño de cadena fijo, al ir aumentando el tamaño de alfabeto, los valores estadísticos (promedio, mediana, modo) van siendo cada vez mayores, lo mismo sucede con la gráfica. Podemos pensar que la posibilidad de ocurrencia de un elemento mayor a los elementos precedentes aumenta a mayor tamaño de alfabeto, lo cual mueve los valores hacia la derecha. Ver el comportamiento de los valores en el reporte para tamaño de cadena 200.

Por otro lado si el tamaño de alfabeto es significativamente mayor al tamaño de cadena, este comportamiento va disminuyendo. Lo cual indica que luego de un determinado valor en función al tamaño de la cadena, la posibilidad de que ocurra un elemento mayor a los elementos anteriores va estabilizándose. Ver reporte para tamaño de cadena 10.

Reportes de Tipo 3

Los reportes de tipo 3, nos muestran que la gráfica de la función se encuentra corrida hacia la izquierda en relación al rango de valores posibles, y que a mayor valor de n y k más hacia la izquierda se mueve en proporción al rango. Esto parecería coincidir con nuestras intuiciones de los posts anteriores, y parecería confirmarse gráficamente los factores de atenuamiento que habíamos considerado en estey este posts.

Gráfico de la función con alfabeto n=50, k=50 y muestra de tamaño 500:

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Simulación del Caso Promedio

Problema de Algoritmia Básico: Algunas observaciones sobre el peor caso

Icono de Post February 29 2012 :: Algoritmia ::

Este post continua con una pequeña observación sobre lo visto en el post Problema de Algoritmia Básico, Análisis de Complejidad.

Voy a continuar en este post trabajando sobre la solución básica, analizando el comportamiento de la función esta_en_lista() ante diferentes inputs.

Listas ordenadas con un alfabeto finito

Supongamos que el alfabeto que tienen las listas posibles tiene un tamaño finito, o lo que es lo mismo que el numero de ints posibles es finito, y ademas que las listas son ordenadas y de mayor tamaño al tamaño del alfabeto.

Por ejemplo, tomemos un alfabeto de tamaño 3:

[1,2,3,1,2,3,1,2,3,….]

Sabemos por el análisis del post referido que mientras se va construyendo la lista pasados, se necesita iterar por cada elemento menor hasta incluirlo en la lista. Sabemos así mismo que una vez construida la lista pasados por cada elemento repetido se necesita pasar por todos lo elementos anteriores antes de encontrar al elemento. Por esto, sabemos que el costo asociado a cada elemento es:

T(n%3 == 0) = 2a + w
T(n%3 == 1) = 1a + w
T(n%3 == 2) = 0a + w

Donde a es el costo de iterar por cada elemento de la lista y w es una constante que representa el resto de las operaciones (constantes) de la función, n es la posición del elemento en la lista y Usamos la notación n%3 == x para representar aquellos valores de n en el que el modulo 3 es igual a x

Para el resto del post vamos a olvidarnos de w y preocuparnos solamente por a ya que es aqui donde se producen las operaciones que son variables de la función (por el costo de iterar por la lista).

Es evidente que en una sucesión de listas ordenadas de tamaño 3, la cantidad de veces que se cumplirá la llamada a cada uno de los valores de la recurrencia es 1/3 * n. O sea, en el total de la lista se cumple que 1/3 de los valores son 1, un tercio son 2 y un tercio son 3.

Nos queda entonces el costo total de las llamadas a la función por iterar por cada uno de los elementos como:

Total = 1/3 * n * T(n%3==0) + 1/3 * n * T(n%3 == 1) + 1/3 * n * T(n%3 == 2)

Esta formula puede ampliarse para cualquier tamaño de alfabeto:

Total = 1/k * n * T(n%k == 0) + 1/k * n * T(n%k == k-1) + 1/k * n * T(n%k == k-2) + … + 1/k * n * T(n%k == 1)

Donde k es el tamaño de alfabeto. Ademas sabemos (de acuerdo al análisis del post anterior) que:

T(n%k == 0) = (k-1)a
T(n%k == 1) = (k-2)a
T(n%k == 2) = (k-3)a
...
T(n%k == k-2) = 1a
T(n%k == k-1) = 0a

Por lo que esta formula puede plantearse entonces como:

Total = 1/k * n * (k-1)a + 1/k * n * (k-2)a + 1/k * n * (k-3)a + … + 1/k * n * 1a

O lo que es lo mismo:






i
=
1

k



1
k

n

(
i

1
)

a

Repensando el peor caso

En el peor caso se cumple que la lista esta ordenada y el tamaño del alfabeto es igual al tamaño de la lista, por consiguiente la formula:






i
=
1

k



1
k

n

(
i

1
)

a

Se reduce a:






i
=
1

n



1
n

n

(
i

1
)

a

=






i
=
1

n



(
i

1
)

a

=





(
n

1
)

n

2


Que es la equivalencia que vimos anteriormente.

Que pasa si no es una lista ordenada?

Supongamos que la lista no es ordenada y supongamos un alfabeto de tamaño k. En este caso hasta que no se sucedan los k valores del alfabeto, el costo asociado a cada entero no se corresponde directamente con la tabla planteada anteriormente. Por ejemplo si se presenta un 3 como primer elemento, no se van a cumplir 2 iteraciones sino 0, ya que la lista pasados esta vacia. Esto sucederia hasta que aparezcan en la lista todos los elementos del alfabeto.

Podemos plantear (ingenuamente) para este caso una funcion de aproximacion que seria la siguiente:

Total = 1/k * n * (k-1)a + 1/k * n * (k-2)a + 1/k * n * (k-3)a + … + 1/k * n * 1a – j

Donde j representara la disminucion producida en relacion a la formula anterior hasta que se suceden todos los valores de la lista.

Es evidente que, manteniendo fijo el tamaño de alfabeto, y con un tamaño de lista lo significativamente mayor al tamaño de alfabeto, j se vuelve en el caso tipico despreciable en el costo total de la funcion.

Sin embargo analizar el caso promedio sigue siendo muy complicado. Hica varios intentos y me quedaba una formula enorme, por consiguiente decidi hacer una simulacion matematica para evaluarlo y es el tema del ultimo y final post de esta serie.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Introduction to Algorithms, 2nd Edition; Cormen, Leierson, Rivest, Stein; MIT Press; 2009

Problema de Algoritmia Básico: Mejoras a la Solución Básica

Icono de Post February 28 2012 :: Algoritmia, c, Estructuras de datos ::

Este post continua con el problema planteado en este post. Habiendo ya analizado la complejidad de la solución básica , el siguiente paso es tratar de mejorarla proponiendo diferentes estructuras de datos para la función esta_en_lista().

Usar un array

La solución mas inmediata es cambiar la lista pasados por un array. Esta version se puede ver en solucion-array.c.

La gran diferencia entre ambas versiones es la función esta_en_lista(), que ahora nos queda:


int esta_en_lista(int value, char pasados[ MAXINT ]) {	

	if( pasados[value] == 1) return 1;
	pasados[value] = 1;
	return -1;

}

Código en solucion-array.c

Porque es una mejora?

El acceso a un array es siempre O(1). Por consiguiente el costo total del algoritmo seria O(n) * O(1), que es equivalente a O(n).

Cuales son las desventajas?

La desventaja principal es que lo que ganamos en la mejora de la complejidad de la función, lo perdemos en la complejidad espacial. Basicamente porque ahora necesitamos alocar e inicializar memoria para un array del tamaño del mayor int posible en la lista.

La otra desventaja es que es necesario inicializar el array a 0. Lo cual hace que el algoritmo de por si tenga una cota minima de O( MAXINT ), en el caso (esperable) de que la lista sea de tamaño mayor que el MAXINT posible este no es un problema ya que la porción del algoritmo que es O(n) es mayor que el MAXINT, pero si estuvieramos trabajando con un input de listas chicas, la solución anterior podria ser preferible.

En definitiva, esta solución es mas efectiva cuando el mayor int posible es pequeño y la lista es muy larga.

Usar un Binary Search Tree

Esta versión se puede ver en solucion-binary-search-tree.c. El código nos queda:


int esta_en_lista(int value, BSTree *pasados) {	
  BSTree cursor = *pasados;

  //El nodo esta vacio
  if( cursor == NULL) {
    BSTree temp = (BSTree) malloc(sizeof(struct BST_Node));
    temp->value = value;
    temp->right = NULL;
    temp->left = NULL;
    *pasados = temp;
    return -1;
  }

  //El nodo tiene el mismo valor
  if( cursor->value == value ) return 1;

  if( cursor->value < value) {
      //Fijarse en el nodo derecho
      return esta_en_lista(value, &(cursor->right));
   } else {
      //Fijarse en el nodo izquierdo
      return esta_en_lista(value, &(cursor->left));
   }
}

La ventaja inmediata de un Binary Search Tree es que la inserción y la busqueda tienen para un input promedio, complejidad O(log(n)). Esto nos mejoraría el algoritmo, llevandolo a O(n log(n)).

Sigue existiendo, sin embargo, el problema de que en el peor caso posible de una lista ordenada ascendentemente: [1,2,3,4,..]; el binary search tree se comporta exactamente igual que una lista. Esto se puede arreglar usando un Balanced Binary Search Tree, aunque es una estructura de datos un poco compleja para acordarse de su implementación y codificarla en una entrevista.

Soluciones esotéricas

Usar un bit array

Si se quiere tener una performance similar a la de un array pero con un uso menor de memoria, se puede usar un Bit Array, aunque tampoco escala bien a nivel espacio.

Usar un hashtable de binary trees

Esta es la ultima opción que codifique y se puede encontrar en solucion-hashtable-de-binary-search-trees.c. Analizar las ventajas y desventajas de esta solución se las dejo al lector.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Introduction to Algorithms, 2nd Edition; Cormen, Leierson, Rivest, Stein; MIT Press; 2009

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Mejoras a la Solución Básica

Problema de Algoritmia Básico: Complejidad Algorítmica

Icono de Post February 28 2012 :: Algoritmia, c ::

Bueno, este post continua con el problema del post anterior, lo que voy a hacer en este post es analizar la Complejidad del algoritmo.

Codigo con anotaciones

Para el análisis voy a hacer algunas anotaciones sobre el código, básicamente con comentarios sobre el mismo para dividirlo en diferentes partes. El código que se va a usar en el post es el siguiente:



int esta_en_lista(int value, List *pasados) {

/* B0 */
	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
/* /B0 */
/* B01	*/
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
/* /B01 */
	}

/* B1 */
	while(rList != NULL) {
/* /B1 */

/* B11 */
		if(rList->value == value) return 1;
/* /B11 */
/* B12 */
		if(rList->value > value) {
/* /B12 */
/* B121 */
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
/* /B121 */
		}
/* B13 */
		prev = rList;
		rList = rList->next;
/* /B13 */
	}
/* B3 */
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
/* B3 */
}

List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
/* A0 */
	if( (*lista) == NULL) {
/* /A0 */
/* A01 */
		return lista;
/* /A01 */
	} else {
	//PASO INDUCTIVO
/* A1 */
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
/* /A1 */
/* A10 */
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
/* /A10 */
		} else {
/* A11 */
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
/* /A11 */
		}
	}
}


Se ve que estan separadas en el codigo las secciones que se ejecutan independientemente. Una aclaración, jamas en la practica se hace una análisis de complejidad con el nivel de detalle que tiene este post y dudo fuertemente que fuera lo que buscaba el entrevistador (la parte intuitiva de cada caso, alcanzaria), pero ya que estoy haciendo un post y considerando que hay pocos ejemplos en castellano, lo vamos a hacer relativamente riguroso y pedagógico.

Mejores Casos

Lista vacia

Este caso es trivial, pero de todas maneras es importante marcarlo. Se llama a la función sacar_duplicados() con lista igual a NULL, se llega al caso base y se retorna NULL. No hay mucho que analizar.

Lista con todos el mismo elemento

Ej: [1,1,1,1,1,1,1,1,1 …] .

Vamos a pensarlo intuitivamente:

Básicamente lo que pasa en este caso es que en el primer llamado a sacar_duplicados(), pasados esta vacio por consiguiente en la llamada a esta_en_lista() se agrega el elemento a pasados y se devuelve -1.

Ahora, lo interesante es que en todas las sucesivas llamadas, cada vez que se llame a esta_en_lista() esta función va a iterar por pasados, encontrarlo en el primer intento y devolver 1.

Es evidente que salvo para el primer elemento de la lista, para todos los demas el código va a tardar exactamente lo mismo (O sea que las llamadas a esta funcion son O(1) ). Como la función sacar_duplicados() pasa recursivamente por cada uno de los n elementos de la lista, la complejidad en este caso para todo el algoritmo es O(n).

Pensemoslo más detalladamente. En la primer llamada se ejecutan: A0, A1, A11, B0, B01 y la llamada recursiva al siguiente elemento. En cada una de las siguientes llamadas se ejecuta: A0 + A1 + A10 + B0 + B1 + B11 y la llamada recursiva al próximo elemento. En la ultima llamada, la que se hace cuando ya se recorrio toda la lista y se pasa el ultimo nodo que es NULL se ejecutan: A0 + A01 .

Podemos establecer una relación de recurrencia para analizar el algoritmo pensando en cuantas veces se ejecuta cada una de las partes. Llamemos T(n+1) a la ultima llamada, T(n) a la ultima llamado con un elemento, T(n-1) a la anterior, hasta llegar a T(1) la primer llamada. Nos queda entonces, la siguiente ecuación:

T(n+1) = A0 + A01 + T(n)
T(n) = A0 + A1 + A10 + B0 + B1 + B11 + T(n-1)
T(n-1) = A0 + A1 + A10 + B0 + B1 + B11 + T(n-2)
...
T(2) = A0 + A1 + A10 + B0 + B1 + B11 + T(1)
T(1) =  A0 + A1 + A11 + B0 + B01

La relación de recurrencia es la que va de T(n) a T(2) ya que esta es la parte recurrente, por otro lado, se podría haber planteado todo el problema solo pensando en esto, ya que es aquí donde se hace la parte del procesamiento que crece al crecer el tamaño de la lista y como tal es la que afecta la complejidad del algoritmo.

Es evidente que de 2 a n hay n-1 llamados, entonces la relacion de recurrencia nos queda resuelta como: (n-1)(A0 + A1 + A10 + B0 + B1 + B11) . El total de toda la ecuación ( sumando T(1) y T(n+1) y llamandola f(n) ) es: f(n) = (n-1)(A0 + A1 + A10 + B0 + B1 + B11) + ( A0 + A01) + (A0 + A1 + A11 + B0 + B01) o f(n) = (n+1)(A0)+(n)(A1+B0)+(n-1)(A10+B1+B11)+A01+A11+B01 .

Es evidente que esta función crece linealmente, o sea que en este caso es O(n).

Lista ordenada descendentemente

Ej: [n, n-1, n-2, n-3, …] .

Este caso es exactamente igual al anterior con la diferencia en que en cada llamado a esta_en_lista() se encuentra que el elemento nuevo es menor a todos los elementos anteriores de pasados en la primera iteración del while y se lo agrega a la misma. De nuevo, las llamadas a esta función son O(1) y el total es O(n)

Peor Caso

Lista ordenada ascendentemente

Ej: [1,2,3,4,5,6 …]

Bueno, este caso es bastante mas interesante. Intuitivamente, en este caso en cada llamado a esta_en_lista(), el while itera por cada uno de los elementos anteriores que son menores que el nuevo elemento, hasta que se termina el while y se agrega el nuevo elemento. Claramente en cada nueva llamada a la función el numero de iteraciones crece en 1. Intuitivamente podemos pensaer que como el numero de elementos de pasados es función del tamaño de la lista, esta parte es O(n) y como en sacar_duplicados() se itera por cada uno de los elementos de la lista el algoritmo total es O(n^2).

Analizemoslo más en profundidad y hagamos la recurrencia, los casos para el T(1) y T(n+1) son iguales. Luego para cada llamado en un elemento en posicion j de la lista se ejecuta (en orden): A0 + A1 + B0 + (j-1)(B1 + B11 + B12 + B13) + B3 + A10 ( que incluye la llamada recursiva al proximo elemento). La parte a ver y que es la que cambia radicalmente en relación con los casos anteriores es (j-1)(B1 + B11 + B12 + B13), que es la porcion del codigo donde se itera por cada elemento de pasados que preexiste al elemento actual. Esta parte ya no es constante para cada llamada a esta_en_lista(), efectivamente esta parte crece (linealmente) con cada nuevo llamado y luego de un suficiente numero de llamados es donde se concentrara la mayor parte de las operaciones de la función y de todo el algoritmo. Es fácil ver que para un j lo suficientemente grande, el resto de las operaciones se vuelve despreciable en relación al tiempo que se pasa en esta parte. Por ejemplo supongamos que j=1000, nos queda: A0 + A1 + B0 + (999)(B1 + B11 + B12 + B13) + B3 + A10 .

Hagamos la relación de recurrencia:

T(n+1) = A0 + A01 + T(n)
T(n) = A0 + A1 + A10 + B0 + B3 + (n-1)(B1 + B11 + B12 + B13) + T(n-1)
T(n-1) = A0 + A1 + A10 + B0 + B3 + (n-2)(B1 + B11 + B12 + B13) + T(n-2)
...
T(2) = A0 + A1 + A10 + B0 + B3 + (1)(B1 + B11 + B12 + B13) + T(1)
T(1) =  A0 + A1 + A11 + B0 + B01

Centremonos en la parte recurrente, llamemos k a (B1 + B11 + B12 + B13), l a (A0 + A1 + A10 + B0 + B3) y z a T(1) nos queda:

T(n) = l + (n-1)k + T(n-1)
T(n-1) = l + (n-2)k + T(n-2)
...
T(2) = l + (1)k + z 

Para poder pensar la recurrencia vamos a ir asignando los valores en cada paso y tratar de ver si existe algún patrón, intentemoslo:

T(2) = l + k + z
Total = l + k + z

T(3) = l + 2k + T(2)
Total = 2l + (1 + 2)k + z


T(4) = l + 3k + T(3)
Total = 3l + (1 + 2 + 3)k + z

T(5) = l + 4k + T(3)
Total = 4l + (1 + 2 + 3 + 4)k + z

...

T(n) = (n-1)l + (1 + 2 + 3 + 4 + ... + n-1)k + z

La parte del k es simplememnte una sumatoria hasta (n-1), existe una formula bastante básica para la misma que se puede encontrar acá y existe una anecdota muy simpática sobre Gauss sobre la misma. Aplicando equivalencias de sumatoria nos queda para toda esa parte (n * (n-1))/2 = (n^2 – n)/2 = (n²)/2 – n/2.

Veamos entonces como nos queda la recurrencia total (llamando w a T(n+1)): f(n) = (n-1)l + ((n^2)/2)k – (n/2)k + z + w . Esta función es cuadratica y el algoritmo total nos queda O(n^2).

Caso Medio

Pensar sobre el caso medio es todavia mas interesante, porque antes que nada tendriamos que definir exactamente que significa el caso medio y este seria el momento en el que le preguntariamos al entrevistador sobre más precisiones para poder entender el problema. Las preguntas básicas serian:

  • El numero de int posibles es finito?
  • Cuan ordenada esta la lista?
  • Cual es la probabilidad de que que se repitan elementos?
  • Es una distribución uniforme?

Intuitivamente, cuando pense el problema originalmente, mi idea era considerando:

1. si la lista no es ordenada se puede dar que en la primera aparicion de un elemento este sea mayor a x elementos que vengan despues que fueran menores en este elemento no se tendria que iterar por todos los anteriores sino solamente por una porción de estos. Ej:

[5,1,6,3,4,2,7]

Iteraciones para cada elemento y como queda pasados:
5 : 0
[5]

1 : 0
[1,5]

6 : 2
[1,5,6]

3 : 1
[1,3,5,6]

4 : 2
[1,3,4,5,6]

2 : 1
[1,2,3,4,5,6]

7 : 6
[1,2,3,4,5,6,7]

Se ven claramente dos cosas, el numero de iteraciones no coincide directamente ni con la posición n del elemento en lista, ni con su orden dentro de pasados; lo otro es que cuando un elemento es mayor a todos los elementos anteriores, si o si, se debe iterar por todos los elementos n-1 de pasados y ahí si, el numero de iteraciones coincide con la posición n del elemento en lista (menos 1).

2. Cuando un elemento se repita, independientemente del factor de ordenamiento de la lista, solo debe iterar hasta encontrarse a si mismo dentro de la lista.

Considerando estas 2 cosas habia pensado ingenuamente en considerar arbitrariamente una constante k, llamemosla factor de atenuación por ordenamiento y otra constante l llamemosla factor de atenuación por duplicados; que combinadas darian una constante c que se podria considerar como afectando la funcion anterior quedando el algoritmo dentro de alguna funcion del tipo f(n): c * n^2; 0 < c < 1 o sea terminando en O(n^2). Especificamente porque quedaria en una funcion cuadratica, porque todos los casos en que un elemento sea mayor a todos los anteriores, si o si, la función esta_en_lista() es lineal.

El problema es que cuando me puse a pensar un poco mas sobre el problema para escribir el post, me surgieron algunas preguntas y honestamente es un problema mucho más complicado de lo que pensaba. Voy a escribir un cuarto post con algunas de las conclusiones a las que llegue, incluyendo la muy sorprendente de que si el número de ints posibles es finito y el tamaño de la lista es mayor a este numero, la función puede ser expresada como una función lineal.

Pero bueno, siendo estrictos una función lineal esta acotada por una función cuadratica y por consiguiente sigue siendo O(n^2).

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Problema de Algoritmia Básico: Primera Solución

Icono de Post February 28 2012 :: Algoritmia, c, Estructuras de datos, Lógica ::

Este es una serie de posts sobre un ejemplo básico de analisis de algoritmos. Va a constar de 3 partes: Descripción del problema y solución básica, Análisis de complejidad de la solución básica y Posibles mejoras. El codigo de estos posts se puede encontrar aquí .

Hace unos días estuve hablando con un ex-compañero de la facultad sobre una entrevista de trabajo que había tenido en una empresa muy grande de estados unidos. Me comento muy rapidamente y sin muchos detalles sobre el problema que le habían presentado y me resultó interesante como un buen ejercicio de Algoritmia básica.

Descripción del problema

El problema consiste en dado una lista de numeros enteros, remover los duplicados de la lista. Asumí al hacer el codigo, que interesa mantener la estructura de la lista ( O sea dado una lista: [5,3,4,5,3,2]; encontrar la misma lista pero con los duplicados removidos: [5,3,4,2] ).

Obviamente el problema no es solamente solucionar este problema, sino razonar sobre la corrección y eficiencia de la solución encontrada y ademas codificarlo en algun lenguaje ( especificamente C ).

Algunos pasos previos

Antes de comenzar a trabajar en el problema, me parecio conveniente hacer algunas funciones para poder testear y probar el codigo.

Struct de la lista

La estructura de datos que se va a utilizar en el ejercicio


typedef struct Node *List;
struct Node {
  int value;
  struct Node *next;
};

Función para mostrar la lista

Una función para mostrar la lista por pantalla.


void mostrar_lista(List lista) {
	//Este primer paso es para el pretty print de la lista
	if(lista != NULL) {
		printf("%d", lista->value);
		lista = lista->next;
	}
	while(lista != NULL) {
		printf("-%d", lista->value);
		lista = lista->next;
	}
}

Función para cargar una lista de prueba

Una función que dado un string con una lista de enteros separados por comas, lo parsea a un linked list.

Esta es una versión mejorada sobre la que hice originalmente, esta versión es forgiving con aquellos caracteres que pueden haber sido mal tipeados por el usuario o por input malintencionado, tomando solo los caracteres que representan dígitos ( el string: “1,a2,3b,d4d,xxxx,5,,,,6,a8b0,10” se tranforma en la lista: [1,2,3,4,5,6,80,10] ). La versión original era un poco más simple y no anticipaba malas entradas.


List crear_lista(List lista, char str[2000]) {
	int i=0;
	List rList = lista;

	//Es forgiving, solo lee los digitos y descarta lo demas.
	while( str[i] != '' ) {
		while( str[i] != '' && (str[i] < '0' || str[i] > '9') ) i++;
		if(str[i] == '') break;

		int pre = 0;
	    
		//Calcular el int
		while( str[i] != ',' && str[i] != '' ) {
			if(!(str[i] < '0' || str[i] > '9')) { 
				pre = pre * 10;
				pre = pre + (str[i] - '0');
			} 
			i++; 
		}
	    
		//Crear el nodo nuevo    
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = pre;
		temp->next = NULL;

		//Primera iteracion
		if(lista==NULL) {
			//Agregar nodo a lista
			lista = temp;
			//Lista de retorno
			rList = lista;
		} else {
			//Agregar nodo, mover cursor.
			lista->next = temp;
			lista = lista->next;
		} 
		i++;
	}
	return rList;
}

Ejemplo de uso:


	char str[2000] = "";
	scanf("%s", str);
	lista = crear_lista(lista, str);
	printf("La lista es: n");
	mostrar_lista(lista);

Solución básica

La solución básica consiste de 2 funciones. Una función int esta_en_lista(int value, List *pasados) que dado un entero value y una lista pasados verifica si el valor existe en la lista. Si ya existe devuelve 1, si no, devuelve -1 (podría haber usado constantes TRUE y FALSE como macros y el codigo seria mas bonito) y agrega este valor a la lista pasados en orden ascendente. La lista pasados se pasa por referencia ( efectivamente es un puntero a puntero ) dado que como side effect de la función se modifica esta lista, agregandosele ordenadamente cualquier valor que no pre-existe. O sea, en sucesivas llamadas a la funcion se va creando una lista ordenada de valores. La otra función List * sacar_duplicados(List *lista, List *pasados), recibe 2 punteros a listas, la lista de enteros de la que queremos sacar duplicados y una lista donde se guardan los valores que ya existen en la lista. Esta es la función que devuelve la primer lista con los valores removidos. Esta pensado para ser llamada con pasados siendo una lista vacia.


//Version basica a ser mejorada
//Se pasa un puntero al puntero de lista para hacer los side effects
int esta_en_lista(int value, List *pasados) {

	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
	}

	while(rList != NULL) {
		if(rList->value == value) return 1;
		if(rList->value > value) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
		}
		prev = rList;
		rList = rList->next;
	}
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
}



//ESTA ES LA FUNCION QUE IMPORTA EN UN PRIMER PASO
//EN UN SEGUNDO PASO LO QUE IMPORTA ES MEJORAR LA FUNCION ANTERIOR
List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} else {
	//PASO INDUCTIVO
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}
	}
}

Se puede testear el programa compilando y corriendo solucion-basica.c .

Razonando sobre la corrección del algoritmo

Primera Parte

Lo primero que habria que considerar es si la función esta_en_lista() es correcta. No voy a hacer un análisis muy formal, pero supongamos los posibles casos:

  • pasados es una lista vacia: Se ejecuta el primer if: if(rList == NULL) , se crea un nodo nuevo que se agrega a pasados y se devuelve -1.
  • pasados no es una lista vacia y el valor existe en la lista:, se ejecuta el primer if y devuelve falso, se ejecuta la sentencia: while(rList != NULL) , se itera por todos los nodos hasta que se encuentra el nodo en el que pre-existe el valor, se llega a la condición: if(rList->value == value) y se devuelve 1.
  • pasados no es una lista vacia, el valor no existe en la lista y es menor a cualquier valor de la lista: se llega al while, en la primera iteración se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev fue inicializado a NULL y es la primera iteración, se asigna este nuevo nodo a pasados y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y esta entre medio de 2 valores de la lista: se llega al while, se itera por los nodos hasta que se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev esta apuntando al nodo pàdre del actual, se asigna este nuevo nodo como hijo de prev y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y es mayor a cualquier valor de la lista: se llega al while, se itera por los nodos hasta que se recorre toda la lista y se sale del while, se crea el nuevo nodo, se le agrega null como nodo hijo y se evalua la condición, se asigna este nuevo nodo como hijo de prev (que en este momento es el ultimo nodo de la lista) y se devuelve -1.

Razonar sobre la corrección del valor que devuelve (1 o -1) es trivial. Asi como razonar que no agrega un valor que ya existe.

Lo que es importante ver es que si se llama a la función con una lista ordenada y un valor que no existe en la misma, por los 3 ultimos casos (y el primero siendo estrictos, ya que una lista vacia es una lista ordenada), a esta lista se le agrega el valor en orden.

Segunda parte

Asumiendo que la función anterior es correcta y que la función esta_en_lista() devuelve un valor correcto y asi mismo que en sucesivas llamadas a la lista pasados se guardan en esta todos los elementos anteriores, podemos razonar sobre la función sacar_duplicados() que es la que nos importa.

La función es recursiva, por lo que para pensar sobre su corrección alcanza con hacer induccion para demostrar que la función retorna la misma lista sin duplicados. Voy a hacer un esquema del razonamiento que nos llevaria a una demostracion.

Paso base

El paso base es que la lista esta vacia. En ese caso se retorna una lista vacia, como una lista vacia es una lista sin duplicados, no hay nada más que demostrar. El codigo que soporta este caso es:


	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} 

Paso Inductivo

Ahora tenemos que demostrar que si llamamos a la funcion con una lista con n elementos sin duplicados entonces llamando a la función con la lista con n+1 elementos tambien se retorna una lista sin duplicados.

Para razonar sobre esto alcanza pensar que en el caso en que se llama a la función con (n+1) elementos, se llega a la siguiente porción de codigo:


		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}

Analizemos los dos casos:

  • Si el valor (n+1) ya existe en la lista, se devuelve la lista hasta n. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y se devuelve esta, la lista que se devuelve en la llamado con n+1 elementos es así mismo una lista sin duplicados.
  • Si el valor (n+1) no existe en la lista, se devuelve la lista hasta n mas el elemento n+1. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y por asunción de caso el elemento nuevo no existe en la lista hasta n, la lista que se devuelve en la llamado con n+1 elementos es una lista sin duplicados.

Por exhaustación de casos, se comprueba que se cumple el paso inductivo.

Algunas observaciones sobre el algoritmo

El proximo paso y va ser el siguiente post es analizar la complejidad del algoritmo y despues buscar formas de mejorarlo. Como observaciones basicas se puede ver que llamando a la función sacar_duplicados() con una lista con n elementos, se itera (recursivamente) por cada uno de los n elementos de la lista, por otro lado la lista pasados va creciendo con cada llamado a esta_en_lista() que tiene un elemento nuevo y en todo caso de que este elemento sea mayor a cualquiera de los j elementos anteriores de pasados, esta_en_lista() itera por cada uno de los j elementos de pasados. Es pensando en estos temas que vamos a encarar el siguiente post.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994

Autor: Emiliano Martínez Luque.

Comments Off on Problema de Algoritmia Básico: Primera Solución

Iterando por una matriz cuadrada recursivamente

Icono de Post June 5 2009 :: Algoritmia, Estructuras de datos, Java, Lógica ::

En otro ejercicio de la facultad se me pedía sumar todos los valores individuales de una matriz cuadrada a través de un algoritmo recursivo. Mi resolución en Java fue la siguiente:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
			if(n > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
			} else {	
				return arr2[m][n];
			}
		} else { //n > m
			if(m > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
			} else {
				return arr2[m][n];
			}
		}
	}

Me interesa este ejercicio para pensar de otra forma sobre corrección de programas. La pregunta es si el algoritmo es correcto y después de pensarlo un poco llegue a la conclusión de que lo era. Por lo pronto para hacer una demostración formal debería usar inducción estructural pero este post trata más bien sobre trabajo previo a una demostración, lo que en How to Prove it llaman scratchwork. O sea el razonamiento a través del cual se llega a una demostración.

Primero que nada hagamos un poco de debugging con un caso simple de una matriz de 3x3. Para esto agregamos lo siguiente al código anterior:


	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		System.out.println(n + " " + m);
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
....
....

Y testeamos la función llamándola con:


public class TP4 {

	public static void main (String[] args) {
		int[][] arr2;
		arr2 = new int[3][3];
		arr2[0][0] = 1;
		arr2[0][1] = 2;
		arr2[0][2] = 2;
		arr2[1][0] = 4;
		arr2[1][1] = 2;
		arr2[1][2] = 3;
		arr2[2][0] = 4;
		arr2[2][1] = 7;
		arr2[2][2] = 8;
		System.out.println("Ej9:");
		System.out.println( TP4.sumaMatriz(arr2,2 ,2));
	}
}

Lo que muestra por consola es:


Ej9:

2 2
2 1
2 0
1 1
1 0
0 0
0 1
1 2
0 2

33

Podemos ver que todos los elementos de la matriz fueron accedidos y que el resultado es el correcto. Ahora imaginémonos el árbol de las llamadas de función.

Vemos que los elementos de la diagonal principal hacen 3 llamados más, al próximo elemento de la diagonal principal, y a los dos elementos con m o n decrementados en uno. Mientras que los elementos que no están en la diagonal principal hacen un solo llamado.

Razonamiento (Informal) sobre la corrección del Algoritmo

Consideremos una matriz cuadrada de grado m, tal que m sea mayor que 5 (esto es por claridad para hacer este ejercicio) y concentrémonos en los últimos 5x5 casilleros del limite inferior derecho, que es donde comienza el algoritmo.

Primer paso toma el elemento en m x m:

A partir de esto se realiza la llamada recursiva:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

De la que se desprenden los siguientes 3 pasos.

El caso b:


return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b

De nuevo el caso a:


if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

Y finalmente el caso c:


				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c

Hemos llegado a llenar una matriz de 3x3, pero esto no nos demuestra nada, ahora lo interesante es saber que pasa cuando continua el algoritmo en los pasos siguientes y aquí es donde esta el truco.

Lo interesante es que las 3 posibles llamadas recursivas garantizan la siguiente:

  • Por el caso a, desde una llamada de la función desde un casillero en la diagonal principal, no se llamara a la función en ningún casillero que este en la misma linea o columna de los elemento de donde han sido llamados por un casillero en la diagonal principal anterior.También por el caso a, la iteración a través de elementos de la diagonal principal eventualmente cubrirá todos los elementos de la diagonal principal de la matriz.

  • Por el caso b, desde una llamada de la función desde un casillero en una columna que no sea en la diagonal principal, siempre continuara por esa misma columna hasta completarla.

  • Por el caso c, desde una llamada de la función desde un casillero en la fila que no sea en la diagonal principal, siempre continuara por esa misma fila hasta completarla.

A partir de esto podemos inferir que el algoritmo pasa por todos los elementos de cualquier matriz cuadrada.

Importante

Quiero recalcar que esto es un razonamiento, a partir del cual por inducción estructural podría construirse una demostración, pero en términos de lógica formal no es una demostración. Igual, no deja de ser un razonamiento valido, lo cierto es que en la programación como practica es importante poder pensar si lo que se esta haciendo es correcto y si los programas que uno hace cumplen con las necesidades que uno tiene, pero también es cierto que sería completamente Overkill el tener que hacer una demostración formal de cada programa que uno hace. Lo importante es tener herramientas para poder razonar y pensar sobre como se programa.

Autor: Emiliano Martínez Luque.

Comments Off on Iterando por una matriz cuadrada recursivamente

Implementación del Algoritmo de Euclides

Icono de Post June 4 2009 :: Algoritmia, Haskell, Java ::

En un ejercicio de la facultad me pidieron hacer un función recursiva que encuentre el Maximo común divisor entre dos números por medio de restas. Ahora, esto que parece un simple ejercicio en realidad se engancha con un montón de temas interesantes de la historia de la matemática. Bueno, lo primero que se me ocurrió fue factorizar los dos números y después buscar los factores comunes, obviamente esta idea no es lo que se dice fácil ( quizás hasta imposible ) de hacer recursivamente. Se me ocurrió investigar un poco y encontré el Algoritmo de Euclides. La implementación básica en Haskell es:

algEuclid :: Int -> Int -> Int
algEuclid a b	| c < 0 	= algEuclid b a
		| c == 0	= b
		| c >= b 	= algEuclid c b
		| c < b		= algEuclid b c
		where c = a - b

La versión en Haskell es super clara, pero se me pedía implementarla en Java y quedo así:

public class Ej {

	public static void main (String[] args) {
		//Ej8. Maximo Comun Divisor de 2 numeros
		System.out.println("Ej8:");
		System.out.println( TP4.algEuclid(64, 48));
	}


	public static int algEuclid( int a, int b) {
		int c = a - b;
		if ( c < 0) {
			return algEuclid(b, a);
		} else if (c == 0) {
			return b;
		} else if ( c >= b ) {
			return algEuclid(c, b);
		} //(c < b)
			return algEuclid(b, c);
	}
	
}

Lo interesante es que Euclides hace su demostración en términos puramente geométricos y en términos geométricos existen magnitudes a las que no es posible aplicarles esta formula. En particular raíz cuadrada de 2, es decir que no son conmensurables. Esto tuvo profundas implicancias en el desarrollo de la matemática, porque durante siglos al existir relaciones que no podían ser expresadas puramente en números (tal y como pretendían los pitagóricos) los griegos decidieron priorizar la geometría sobre otras formas de razonamiento matemático. Fue necesario un salto de paradigma, en el sentido de Kuhn, a saber la aceptación de los números irracionales como objetos matemáticos por derecho propio para poder continuar avanzando en diversas áreas de la matemática.

En definitiva, si la historia de las matemáticas demuestra algo, es que si hay algo que no podemos entender actualmente o que parece que nos lleva a un callejón sin salida, en algún momento quizás con un enfoque nuevo probablemente podremos integrarlo a un sistema explicativo de orden superior.

Referencias

Journey through Genius: The Great Theorems of Mathematics; William Dunham; Penguin Books; 1990

Autor: Emiliano Martínez Luque.

Comments Off on Implementación del Algoritmo de Euclides

Razonando sobre corrección de Programas en Haskell

Icono de Post May 18 2009 :: Algoritmia, Combinatoria, Haskell, Lógica ::

Una de las cosas más interesantes de Haskell es lo facil que resulta razonar sobre corrección de programas. Veamos un ejemplo simple; construiremos una función que tome 3 elementos ordenables y los devuelva como una triada ordenada (Ejercicio 2.40 de Razonando con Haskell):


ordena3:: Ord a => a -> a -> a -> (a, a, a )
ordena3 a b c 	| a <= b && b <= c = (a, b, c) 		-- Caso 1
	 	| a <= b = ordena3 a c b		-- Caso 2
		| b <= c = ordena3 b a c		-- Caso 3
		| otherwise = (c, b, a)			-- Caso 4

Las posibles permutaciones de un conjunto de 3 elementos distintos son obviamente 3! = 2 * 3 = 6. Sean 3 elementos ordenables distintos, a los que llamamos 1, 2, 3 tales que 1 < 2 < 3, veamos como trata el programa estas 6 permutaciones distintas:

ordena3 1 2 3 Caso 1 -> (1 ,2 ,3)
ordena3 1 3 2 Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 1 3 Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 2 3 1 Caso 2 -> ordena3 2 ,1 ,3; Caso 3 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 1 2 Caso 3 -> ordena3 1 ,3 ,2; Caso 2 -> ordena3 1 ,2 ,3; Caso 1 -> (1 ,2 ,3)
ordena3 3 2 1 Caso 4 -> (1 ,2 ,3)

Las condiciones exhaustuan todos los caso y el algoritmo termina siempre. ( No se consideran los casos en que existen elementos duplicados en la explicación ya que es trivial ver que por el uso de <= en las condiciones están contemplados en la definición de la función. )

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Autor: Emiliano Martínez Luque.

Comments Off on Razonando sobre corrección de Programas en Haskell