PinkShark Gaming

Hola y bienvenido al foro oficial de PinkShark Gaming (http://www.youtube.com/PinkSharkGaming).
Disfruta de todas las ventajas del foro!!
Conectate, o registrate si no lo estas.
Si tienes alguna duda una vez registrado, envía un Mp a moderadores o administrador

Pásalo bien y si necesitas alguna ayuda aquí nos tienes!
HOLA Invitado!! esto es el scroll de noticias, aquí puedes ver noticias del foro.
Esperamos que el foro sea de su agrado, nosotros hacemos lo posible por ello.
Disfruta de ZonaZero.
(PON EL RATON ENCIMA  PARA PARAR EL SCROLL)
EL FORO ESTÁ SIENDO REFORMADO
En breve dispondrás de nuevas categorías y temas, los antiguos estaban desactualizados
y ya no están disponibles. También el diseño está sufriendo cambios hasta que se asiente
una apariencia permanente.

    Las Matrices (2º Bachillerato; Ciencias y Tecnología)

    Comparte

    Kiff M. Rose
    Admin. King
    Admin. King

    Masculino Google Chrome
    Edad : 24
    Hobby : Música, Videojuegos, PC
    Música PreferidaGlam&Sleaze Metal.
    Mensajes : 3385
    Miembro desde : 08/11/2007
    Reputación Reputación : 25

    Pedido/sugerencia Las Matrices (2º Bachillerato; Ciencias y Tecnología)

    Mensaje por Kiff M. Rose el Mar 03 Nov 2009, 08:01

    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 y solucione 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 multiplicar 2 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 ) {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 conocer el 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) } } } 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 }) #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 realiza un 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 para multiplicar 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.


    __________________________________

    Bienvenido al foro Invitado, es obligatoria la lectura de las > Normas <

    Kiff M. Rose
    Admin. King
    Admin. King

    Masculino Google Chrome
    Edad : 24
    Hobby : Música, Videojuegos, PC
    Música PreferidaGlam&Sleaze Metal.
    Mensajes : 3385
    Miembro desde : 08/11/2007
    Reputación Reputación : 25

    Pedido/sugerencia Re: Las Matrices (2º Bachillerato; Ciencias y Tecnología)

    Mensaje por Kiff M. Rose el Mar 03 Nov 2009, 08:02

    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 radica en : #S1 = a impar #S2 = #S - a impar De no ser posible la condición, se debe elegir a impar. Lo que indudablemente es poca información ya que en base a estas
    ecuaciones se podrían haber elegido los conjuntos de la siguiente
    manera: S1 = { A }, S2 = { B,C,D }, teniendo un costo de 34500. Si generamos un conjunto S de 5 matrices, con dimensiones al azar, podremos observar lo siguiente: S ={ A[57x34] B[34x83] C[83x11] D[11x85] E[85x45] } S ={ A[21x66] B[66x72] C[72x79] D[79x49] E[49x54] } S ={ A[54x36] B[36x12] C[12x76] D[76x81] E[81x41] } S ={ A[62x86] B[86x70] C[70x36] D[36x45] E[45x23] } Analizando visualmente estos gráficos, es obvio que la distribución del
    mínimo costo sigue un orden aleatorio, que habría que estimar,
    transformándose el problema en la estimación de un modelo estadístico,
    que permita determinar un valor a, de división del conjunto s, para que
    la multiplicación de matrices resulte con costo mínimo la gran mayoría
    de las veces (más de un 15% de las veces). Para nuestro caso
    de 4 matrices S = { A,B,C,D }, podemos realizar alguna comparación
    rápida (costo irrelevante), de tal manera que esta nos pueda entregar
    una pista sobre la división de el conjunto S, para así aplicar el
    algoritmo anterior. No olvidar que S ={ A[10x30] B[30x50] C[50x1] D[1x100] } De esta manera se puede inferir que el menor costo esta asociado hacia
    el lado izquierdo del conjunto S, de esta manera se puede elegir una a
    = 3, que involucra a los vértices A,B,C. S1 = { A,B,C } S2 = { D } El algoritmo planteado anteriormente, multiplica con costo mínimo a un conjunto de 3 matrices. Si tenemos un conjunto de 5 matrices, cuales quiera, de tal manera que,
    basándose en los principios de programación dinámica, se puedan elegir
    las tres mejores matrices a multiplicar. Si S ={ A[57x34] B[34x83] C[83x11] D[11x85] E[85x45] }, si llevamos a cabo el calculo propuesto anteriormente obtendríamos que: ABC = 57x34x83x11 = 1769394 BCD = 34x83x11x85 = 2638570 CDE = 83x11x85x45 = 3492225 Por lo que las mejores 3 matrices a multiplicar primero son ABC, si
    aplicamos el algoritmo de multiplicación propuesto, se obtiene que el
    orden de multiplicación es: Ax(BxC) = 52360, ABC[57x11] Si restablecemos nuestra lista, se obtiene que: Esto implica que queda una única opción de aplicación del algoritmo de multiplicación, comportándose de la siguiente manera: ABCx(DxE) = 70290, ABCDE[57x45] Por lo que el costo total otorgado por este método es de 122650 Si hallamos el costo mínimo de la multiplicación de estas 5 matrices, esta resulta ser: (Ax(BxC))x(DxE) = 122650 De tal manera, de que la combinación entre los mejores triángulos y el
    algoritmo de multiplicación de 3 matrices resulta entregar el costo
    mínimo. Multiplicación( S, Conjunto de matrices ) {Si #S = 0 Ent (`Error') Si #S = 1 Ent Retornar(S) Si #S = 2 Ent { Dividir a S en dos conjuntos iguales de un elemento cada uno S1,S2 S ! S1xS2 Retornar(S) } Si #S = 3 Ent {Sn ! elemento central de S S1 ! La matriz anterior a Sn S2 ! La matriz posterior a Sn Si S1xSn es costo menor Ent S1 ! S1xSn Sino S2 ! SnxS2 S ! S1xS2 Retornar(S) } Si #S > 3 Ent { Elegir las mejores 3 matrices y dividir el conjunto de la siguiente manera Si las mejores 3 matrices están al inicio Ent {S1 ! Tres mejores matrices S2 ! El resto de matrices. Multiplicación(S1) S ! S1 + S2. } Si las mejores matrices están al final Ent {S2 ! Tres mejores matrices S1 ! El Resto de matrices. Multiplicación(S2) S ! S1 + S2 } Si las mejores matrices están en el centro Ent {Sn ! Tres mejores matrices S1 ! Las matrices anteriores S2 ! Las matrices posteriores Multiplicación(Sn) S ! S1 + Sn +S2 } Multiplicación(S) Retornar(S) } } Este Algoritmo permite multiplicar n matrices con un costo mínimo.





    A
    B
    C
    D
    B
    10x30x50x1
    A
    30x50x1x100
    E
    D
    C
    D
    ABC
    E


    __________________________________

    Bienvenido al foro Invitado, es obligatoria la lectura de las > Normas <

      Fecha y hora actual: Miér 07 Dic 2016, 15:03