МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / ЗВІТ з лабораторної роботи № 7 з дисципліни: “Алгоритми та методи обчислень” на тему: “ Множення матриць за алгоритмом Винограда ” Мета роботи: навчитися будувати складні алгоритми. Теоретичні відомості: Алгоритм Винограда призначений для швидкого множення матриць. Він був розроблений Фолькером Виноградом в 1969 році і є узагальненням методу множення Карацуби на матриці. Цей алгоритм дозволяє швидше за стандартний спосіб множити матриці. На практиці це відчутно на великих матрицях, але існує ще більш швидкий алгоритм Копперсміта-Винограда[en] для множення дуже великих матриць. На відміну від традиційного алгоритму множення матриць (за формулою /), який виконується за час /, алгоритм Штрассена множить матриці за час /, що дає виграш на великих щільних матрицях починаючи, приблизно, з матриць розміру 64 × 64. Існує модифікація алгоритму Штрассена, для якого вимагається 7 множень та 15 додавань (замість18для звичайного алгоритму Штрассена). Матриці A,B і C діляться на блокові підматриці. Обчислюються проміжні матриціS1 —S8,P1 —P7,T1 —T2 / / / / / / / / / / / / / / / / / Елементи матриці C обчислюються за формулами / / / / Завдання: Реалізувати множення матриць за алгоритмом Винограда. Код програми #include <iostream> #include <ctime> using namespace std; int main() { setlocale(0, "UKR"); srand(time(NULL)); const int a = 2, b = 5, c = 3; int d = b / 2; int G[a][b]; int H[b][c]; int R[a][c]; int rowFactor[a]; int columnFactor[c]; //заповнення матриць for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { G[i][j] = rand() % 10; } } for (int i = 0; i < b; ++i) { for (int j = 0; j < c; ++j) { H[i][j] = rand() % 10; } } // вивід матриць cout << "I матриця:\n"; for (int i = 0; i < a; ++i) { for (int j = 0; j < b; ++j) { cout << G[i][j] << " "; } cout << endl; } cout << "\nII матриця:\n"; for (int i = 0; i < b; ++i) { for (int j = 0; j < c; ++j) { cout << H[i][j] << " "; } cout << endl; } // обчислення rowFactors для G for (int i = 0; i < a; ++i) { rowFactor[i] = G[i][0] * G[i][1]; for (int j = 1; j < d; ++j) { rowFactor[i] = rowFactor[i] + G[i][2 * j - 1] * G[i][2 * j]; } } cout << "\nФактори рядка для G:\n"; for (int i = 0; i < a; ++i) { cout << rowFactor[i] << " "; } cout << endl; // вобчислення columnFactors для H for (int i = 0; i < c; ++i) { columnFactor[i] = H[0][i] * H[1][i]; for (int j = 1; j < d; ++j) { columnFactor[i] = columnFactor[i] + H[2 * j - 1][i] * H[2 * j][i]; } } cout << "\nФактори колонки для H:\n"; for (int i = 0; i < c; ++i) { cout << columnFactor[i] << " "; } cout << endl; // обрахунок матриці R for (int i = 0; i < a; ++i) { for (int j = 0; j < c; ++j) { R[i][j] = -rowFactor[i] - columnFactor[j]; for (int k = 1; k < d; ++k) { R[i][j] = R[i][j] + (G[i][2 * k - 1] + H[2 * k][j]) * (G[i][2 * k] + H[2 * k - 1][j]); } } } cout << "\nРезультат множення:\n"; for (int i = 0; i < a; ++i) { for (int j = 0; j < c; ++j) { cout << R[i][j] << "\t"; } cout << endl; } system("pause"); return 0; } / Рис.1 Результат виконання програми Висновок: На даній лабораторній роботі я навчилася реалізовувати множення матриць методом Винограда.