@article{SITITO, author = {Rustem Aidagulov и Sergei Glavatsky}, title = { Градуированные вычисления}, journal = {Современные информационные технологии и ИТ-образование}, volume = {15}, number = {2}, year = {2019}, keywords = {}, abstract = {Вычисления с большим количеством данных (или данных большой размерности) обычно сводят к наборам вычислений с достаточно малыми их объемами. Одним из способов такого сведения является фильтрация, когда разбиение всего объема данных на мелкие составляющие сводится к рассмотрению ветвлений на графе (дереве). Метод фильтрации вычислений, кратко формулируемый как метод «разделяй и властвуй», часто позиционируется как наиболее эффективный метод сокращения количества операций в сложных вычислениях. Мы рассмотрим здесь более эффективный метод, метод градуированных вычислений, суть которого ранее не была опубликована. Основное содержание нашего метода заключается в разбиении множества элементов вычисления по их значениям. Это позволяет избежать множества повторов в промежуточных вычислениях. Градуировка линейного пространства предполагает разбиение его на подпространства так же, как при представлении его в виде тензорного произведения компонент малых размерностей. Значениями в этом случае являются линейные функционалы, которые вычисляются как многочлены, сопоставляющие определенные значения базисным элементам компонентов тензорного произведения. В задачах сортировки выигрыш скорее не так существенен, а в задачах умножения выигрыш метода градуированных вычислений проявляется явно. Даже в случае произведения больших чисел, представление многочлена от одной переменной как многочлена от нескольких переменных, соответствующее тензорному произведению пространств малых размерностей (малых степеней в компонентах), приводит к более эффективным алгоритмам, нежели алгоритм Карацубы, соответствующий вычислению с фильтрацией. Наш алгоритм позволяет выполнить вычисления за Nlog (N) операций при количестве данных  N . Метод фильтрации приводит, вообще говоря, к Nα  операций с экспонентой (умножения) α > 1.}, pages = {274--282}, doi = {10.25559/SITITO.15.201902.274-282}, url = {http://sitito.cs.msu.ru/index.php/SITITO/article/view/513} }