Fecha de publicación: 04-feb-2014 20:43:25

EL PROYECTO: este consiste en crear un programa siguiendo los algoritmos Mult_Mat y minProd, en dev-c++ en el cual permita multiplicar dos matrices. este debera ser entregado en horas de la mañana hasta las 12m el dia martes 11 de febrero de 2012. Sin prorroga el proyecto tendra un maximo de dos integrantes y se debera entregar el codigo escrito a mano o impreso del programa y el codigo fuente compilado con su ejecutable.

Optimización del Producto de Matrices

El siguiente texto fue trasladado desde Wikipedia, bajo el título "Optimización del Producto de Matrices"

Objetivo

Minimizar el coste de realizar la multiplicación de n matrices.

Descripción

El producto de un número n de matrices es optimizable en cuanto al número de multiplicaciones escalares requeridas. A la hora de multiplicar una serie de matrices se puede elegir en que orden queremos realizar las multiplicaciones entre estas. Se pueden realizar en un orden cualquiera dada la propiedad asociativa de la multiplicación.

Ejemplo: Para cuatro matrices dadas A, B, C y D. Las posibilidades de realizar el calculo son las siguientes: 1. ((A*B)*C)*D 2. (A*(B*C))*D 3. A*((B*C)*D) 4. A*(B*(C*D)) 5. (A*B)*(C*D)

Decidamos el orden que decidamos el resultado siempre es el mismo. La diferencia esta en el número de multiplicaciones que implica elegir un orden u otro. Al multiplicar dos matrices M₁ de tamaño nxm y M₂ de tamaño mxk el número de multiplicaciones escalares es n*m*k. La cantidad total de multiplicaciones será, la suma de todas las multiplicaciones que hacen falta para multiplicar cada submatriz obtenida como resultado con la siguiente en el orden escogido. Y como vamos a ver en este sencillo ejemplo esta cantidad puede variar con el orden utilizado.

Ejemplo: Para el ejemplo anterior con tamaños para las matrices A (13x5), B(5x89), C(89x3) y D(3x34). La cantidad de multiplicaciones para cada orden es el siguiente: 1. ((A*B)*C)*D --> 13*5*89 + 13*89*3 + 13*3*34 = 10582 2. (A*(B*C))*D --> 5*89*3 + 13*5*3 + 13*3*34 = 2856 3. A*((B*C)*D) --> 5*89*3 + 5*3*34 + 13*5*34 = 3055 4. A*(B*(C*D)) --> 89*3*34 + 5*89*34 + 13*5*34 = 26418 5. (A*B)*(C*D) --> 13*5*89 + 89*3*34 + 13*89*34 = 54201

Eligiendo un orden adecuado como podemos ver, optimizamos el coste de realizar las multiplicaciones escalares necesarias para llegar al resultado. Para encontrar el modo de ordenar las multiplicaciones vamos a utilizar un algoritmo de Programación Dinámica.

Esquema

Como vamos a emplear Programación Dinámica, buscamos que todas las subsoluciones sean óptimas, porque se debe de cumplir el principio de optimalidad de Bellman. Esto quiere decir que si la solución es buscar la forma de realizar la multiplicación de n matrices, una posible subsolución será multiplicar desde la matriz i hasta la j. El número mínimo de multiplicaciones necesarias para hallar la subsolución óptima de i a j será M_ij. Si tenemos que ir calculando todas las subsoluciones hasta encontrar la M_1n que es la que andamos buscando, necesitaremos una tabla de nxn donde iremos almacenando los resultados.

Para hallar cada subsolución aplicamos la siguiente función que minimiza el coste total en número de multiplicaciones:

M_ij = { min( M_ik + M_(k+1)j + t_i-1 * t_k * t_j ) | para todo k siendo i<=k<=j }

Algoritmo de PD

fun Mult_Mat_PD(dimMatriz[0..n]: ent) dev sol:ent //Donde n es la dimension de la matriz solución, var es decir, el número de matrices a solucionar matrizSol[1..n,1..n]: ent; //Matriz solución fvar para i=1 hasta n hacer matrizSol[i][i]=0; //Inicializa la diagonal principal a 0 fpara para diagonal=1 hasta n-1 hacer para i=0 hasta n-diagonal hacer matrizSol[i,i+diagonal]=minProd(dimMatriz,matrizSol,i,i+diagonal); //En cada casilla de cada diagonal escribe el su correspondiente mínimo de multiplicaciones necesaria fpara fpara dev matrizSol[0,n]); ffun

fun minProd(dimMatriz[1..n]: ent,matrizSol[1..n,1..n]: ent,i,j: ent) dev minP:ent var aux: ent; fvar minP=+infinito; para k=i hasta j-1 hacer aux=matrizSol[i,k]+matrizSol[k+1,j]+(dimMatriz[i-1]*dimMatriz[k]*dimMatriz[j]); si (aux<minP) entonces minP=aux; //Actualiza si el número de multiplicaciones es menor fsi fpara dev minP; ffun

EL PROYECTO: este consiste en crear un programa siguiendo los algoritmos Mult_Mat y minProd, en dev-c++ en el cual permita multiplicar dos matrices. este debera ser entregado en horas de la mañana hasta las 12m sin prorroga el proyecto tendra un maximo de dos integrantes y se debera entregar el codigo escrito a mano o impreso del programa y el codigo fuente compilado con su ejecutable.