Bloque de Colores

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