Obras

1.− Dadas las matrices A,B,C,D, encontrar los costos asociados al orden asociativo del producto. Las dimensiones de las matrices son: A[10x30], B[30x50], C[50x1], D[1x100] (AxB)xC)xD = 16500 (AxB)x(CxD) = 70000 (Ax(BxC)xD = 2800 Ax((BxC)xD) = 34500 Ax(Bx(CxD) = 185000 2.− Para multiplicar n matrices M1,M2,M3...Mn. ¿ De cuantas formas distintas se puede realizar este producto? ¿ Encuentre ysolucione la ecuación de recurrencia que tiene el problema? El producto de n matrices se puede realizar de p maneras posibles: Siendo M = M1xM2XM3x...xMn−1 P = [ 2(n − 2) ]! / ( (n − 2)! (n − 1)! ) Esto implica para el caso de 4 matrices que n−1=4 ! n=5 P = [ 2(5 − 3) ]! / ( (5 − 2)! (5 − 1)! ) ! P = 5 La ecuación de recurrencia de este problema, gira en lo que es el factorial de la formula propuesta.T(n) = 2T(n − 2) / T(n − 2) x T(n − 1) Se sabe que existe una única forma de multiplicar 2 matrices ! T(2) = 1. 3.− Aplicar la técnica divide para vencer, al problema de multiplicar n matrices, con costo optimo. Si S es un conjunto de matrices, el problema de multiplicar con costo optimo reside solamente en decidir que matrices se han de multiplicar primero. Si tomamos en cuenta que al multiplicar2 matrices, solo existe una sola opción a seguir, por lo que un algoritmo no puede decidir como multiplicar 2 matrices, en cambio al tener 3 matrices, existen 2 formas de llevar a cabo la operación. Ahora si se pretende que el algoritmo decida como multiplicar 4 matrices eso, ya lleva tomar en cuenta 5 formas distintas de realizar dicha multiplicación. Multiplicación( S, Conjunto de matrices )1

{Si #S = 0 Ent (`Error') Si #S = 1 Ent Retornar(S) Si #S > 1 Ent {Si #S es par Ent {Dividir a S en dos conjutos de igual tamaño (S1,S2) Multiplicación(S1) Multiplicación(S2) S ! S1xS2 Retornar(S) } Si #S es impar Ent {Sn ! elemento central de S S1 ! Las matrices anteriores a Sn S2 ! Las matrices posteriores a Sn Multiplicación(S1) Multiplicación(S2) Si S1xSn es costo menor //Implica conocerel costo de SnxS2 Ent S1!S1xSn //Esta comparación se hace Sino S2!SnxS2 // en base a las dimensiones S ! S1xS2 // de las matrices (pxqxr) Retornar(S)

2

} } } Para el caso de multiplicar 3 matrices, el algoritmo funciona bien, pero si se quieren multiplicar 4 matrices, el algoritmo realiza las siguientes llamadas: S ={ A[10x30] B[30x50] C[50x1] D[1x100] } Multiplicar(S) #S es par S1 = { A,B} S2 = { C,D } Multiplicar(S1 = { A,B }) #S es par S1 = { A } S2 = { B } Multiplicar(S1 = { A }) #S = 1 Retornar(S = { A }) Multiplicar(S2 = { B }) #S = 1 Retornar(S = { B }) S = AB Retornar(S1 = { AB }) Multiplicar(S2 = { C,D }) #S es par S1 = { C } S2 = { D } Multiplicar(S1 = { C }) 3

#S = 1 Retornar(S = { C }) Multiplicar(S2 = { D }) #S = 1 Retornar(S = { D }) S = CD Retornar(S2 = { CD }) S= (AB)(CD) Retornar( S = (ABCD) Si nos damos cuenta, el algoritmo multiplico en (AB) primero y luego (BC) y por último los resultados de dicha multiplicación, obteniendo un costo de 70000 multiplicaciones y no el costo mínimo de 2800 operaciones. Esto es debido a la concepción del algoritmo, ya que la decisión de multiplicar con costo mínimo se toma solo en el caso que n sea impar. Si se realizaun pequeño cambio en el algoritmo, de tal manera que en el caso que #S sea par, se elija un a " #S, de tal manera que se formen dos grupos de conjunto, #S1 = a y #S2 = #S − a. El problema que se enfrenta ahora es derechamente la elección de a, ¿cómo elijo a para que la multiplicación tenga costo mínimo?

Si intentamos analizar las dimensiones de las matrices e inferir que a se puede elegir paramultiplicar con costo mínimo, nos podremos encontrar que para el caso de las cuatro matrices se tiene que, al multiplicar BC primero obtenemos un costo mínimo.

4

Para que el algoritmo hubiese realizado una multiplicación con el mínimo costo, era necesario que este dividiera a S en los conjuntos: S1 = { A,B,C }, S2 = { D }, teniendo un costo de 2800 mínimo. En base a esto, la elección de a...