Hozirgi kunda biror bir sohada ishni boshlash va uni boshqarishni kompyutersiz tasavvur qilish qiyin. XXI asr savodxon kishisi bo’lishi uchun kompyuter savodxon bo’lish, axborot texnologiyalarini puxta egallamoq lozim

14 - MAVZU: MATRISALARNI KO’PAYTIRISH UCHUN SHTRASSEN ALGORITMI


Reja


1. Masala quyilishi.
2. Matrisalarni ko’paytirish uchun lemma.
3. Matrisalarni ko’paytirish uchun teorema.
4. Algoritmni baholash.

Matrisalarni ko’paytirishda assimptotik hisoblash murakkabligini tahlil qilamiz. Oddiy O(n³) murakkabligiga ega algoritmni assimptotik yahshilash jarayonini o’rganamiz va 2 ta matrisalarni ko’paytirishda O(n^2,81) vaqt yetarli ekanligini ko’rsatamiz.

Ikkita o’lchamli A va B matrisalar berilgan bo’lsin. Bu yerda n - 2 ning darajasidagi son deb qabul qilinadi. A va B matrisalarni 4 ta o’lchamli matrisalarga bo’lish mumkinligi haqidagi lemmani qo’llab, A va B larni ko’paytmasini quyidagicha tasvirlaymiz.



Bu yerda
A₁₁ – yuqori chap kvadrat,
A₁₂ – yuqori o’ng kvadrat,
A₂₁ – pastki chap kvadrat,
A₂₂ – pastki o’ng kvadrat.
Shtrassen 2 ta o’lchamli matrisalarni ko’paytirish uchun sun’iy usulni ishlab chiqqan. Bu usulda 7 ta ko’paytirish amalga oshiriladi. Usulni rekursiv qo’llab, 2 ta matrisani vaqtda ko’paytiriladi. .
Lemma. 2 ta o’lchamli matrisalarni ko’paytirishda 18 ta qo’shish va ayirish va 7 ta ko’paytirish amallari bajarilsa yetarli.
Isbot. C=a*b ko’paytmasini hisoblashdan oldin quyidagi ko’paytirishlarni amalga oshiramiz.

Keyin c(i,j) larni quyidagi formulalar bo’yicha hhisoblaymiz:


c11=m1+m2-m4+m6; c12=m4+m5; c21=m6+m7; c22=m2-m3+m5-m7;

Amallar soni oddiy hisoblanadi.

Teorema. Ikkita o’lchamli matrisalarni sonli arifmetik amallarni bajarib ko’paytirish mumkin.
Isbot. Birinchi, n – 2-ning darajasidagi son bo’lgan hholatni ko’ramiz. Ikki o’lchamli matrisalarni ko’paytirish uchun kerak bo’lgan arifmetik operatsiyalar sonini T(n) deb belgilaymiz.Unda lemma bo’yicha uchun.
n o’lchamli masala qandaydir chiziqli vaqtda ikkita -o’lchamli masalalarga bo’linishi murakkablikdagi algoritmni beradi. Shuni hisobga olib ekanligini ko’rsatamiz.
Endi n – 2-ning darajasidagi son bo’lmagan holatni ko’ramiz. Bu holda har bir matrisani shunday matrisaga qo’yamiz-ki, uning tartibi n dan katta bo’lgan 2-ning darajasidagi eng kichik son bo’lsin. Berilgan matrisamizning tartibi bu holda 2 baravarga ham oshmaydi, bu esa hamma lar uchun chin ekanligini ko’rsatadi.
Takrorlash ucun savollar


1. Matrisalarni ko’paytirish oddiy usulda qanday amalgam oshiriladi?
2. Matrisalarni ko’paytirish uchun lemmani aytib bering.
3. Matrisalarni ko’paytirish uchun teoremani aytib bering.
4. Xoara algoritm bahosini tavsiflab bering.