Reja Algoritmlar va ularning to’liq tuzulishining bosqichlari

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.
Adabiyotlar ro’yhati

1. 
   Жуманов И.И., Кобилов С.С. СУБД и информационные системы. Уч. пособие. Самарканд, 1977 г.
   
2. 
   В.А.Успенский, А.Л.Семенов. Теория алгоритмов: основные открытия и приложения. – М: Наука, 1987, 287 с.
   
3. 
   Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. Сер: Классические учебники. М.: МЦНМО, 2001.- 960 с.
   
4. 
   Гуломов С.С. ва бошқалар. Ахборот тизимлари ва технологиялари. Тошкент, 2000 й.
   
5. 
   Д.Кнут. Искусство программирования для ЭВМ. Основные алгоритмы.-М: Мир, 2000 г.