4 Laboratoriya ishi #Vinograd va Shtrassen usullari. Matritsani ko'paytirish

4 Laboratoriya ishi #Vinograd va Shtrassen usullari.

Matritsani ko'paytirish

Matritsa - ikki o'lchovga teng bo'lgan matematik ob'ekt bir qator. Raqamlar matritsada qatorlar va ustunlar shaklida joylashtirilgan. Bir xil o'lchamdagi ikkita matritsa elementar ravishda qo'shilishi yoki bir-biridan olinishi mumkin. Agar birinchi matritsadagi ustunlar soni ikkinchisidagi qatorlar soniga to'g'ri keladigan bo'lsa, bu ikki matritsani ko'paytirish mumkin. Mahsulot birinchi matritsada bo'lgani kabi, ustunlar qatorida va ikkinchisidagi kabi ustunlarga ega bo'ladi. 3 x 4 matritsani 4 x 7 matritsaga ko'paytirganda, biz 3 x 7 matritsani olamiz. Matritsaning ko'payishi komutativ emas: ikkala AB va BA bir xil o'lchamdagi ikkita kvadrat matritsani hisoblash mumkin, ammo natijalar, umuman olganda, bir-biridan farq qiladi. (E'tibor bering, raqamlarning ko'payishi kommutativdir va A va B ikkita sonlarning AB va B A mahsulotlari tengdir.)

Ikki matritsaning hosilasini hisoblash uchun birinchi satrning har bir qatori davriy ravishda, ikkinchisining har bir ustuniga ko'paytiriladi. Keyin bunday ishlarning yig'indisi hisoblab chiqiladi va natijaning tegishli katagiga yoziladi. Ikkita matritsani ko'paytirish misoli keltirilgan. Matritsaning ko'payishi uchun 24 ko'paytirish va 16 qo'shimchalar kerak. Umuman olganda, a x b kattalikdagi matritsani ko'paytirishning standart algoritmi b x c kattalikdagi matritsa abc ko'payishlarni va a (b-1) qo'shimchalarni bajaradi.

G matritsani ko'paytirish algoritmi standart ko'rinishi. b x s o'lchamdagi H matritsaga x 6 o'lchamda. Natija qayd etiladi

a x s o'lchamdagi R matritsasiga...

public class MatrixMultiplection {

public static void main(String[] args) {

int[][] mA =

{{33,34,12},

{33,19,10},

{12,14,17},

{84,24,51},

{43,71,21}};

int[][] mB =

{{10,11,34,55},

{33,45,17,81},

{45,63,12,16}};

int m = mA.length;

int n = mB[0].length;

int o = mB.length;

int[][] res = new int[m][n];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

for (int k = 0; k < o; k++) {

res[i][j] += mA[i][k] * mB[k][j];

}

}

}

for (int i = 0; i < res.length; i++) {

for (int j = 0; j < res[0].length; j++) {

System.out.format("%6d ", res[i][j]);

}

System.out.println();

}

}

}

Bir qarashda, bu ikkita matritsani ko'paytirish uchun zarur bo'lgan minimal ish hajmi. Biroq, tadqiqotchilar minimallikni isbotlay olmadilar va natijada matritsalarni yanada samaraliroq ko'paytiradigan boshqa algoritmlarni topdilar.