Mục lục bài viết

CHUYÊN ĐỀ ỨNG DỤNG CỦA PHÉP NHÂN MA TRẬN TRONG GIẢI CÁC BÀI TOÁN TIN HỌC

PHẦN I: MỞ ĐẦU

Trong Tin học, khi lập trình một bài toán thì vấn đề đặt ra cho mỗi người lập trình không phải chỉ là cho ra đáp số đúng, mà vấn đề quan trọng hơn là phải đưa ra đáp số đúng trong thời gian ngắn nhất. Thông thường, để đạt được độ phức tạp thuật toán như mong muốn, cách làm thường là tìm ra một thuật toán ban đầu làm cơ sở, rồi từ đó dùng các kỹ năng để giảm độ phức tạp của thuật toán. Đối với nhiều bài toán có công thức truy hồi nhưng với kích thước dữ liệu rất lớn, chẳng hạn 1018 ta không thể làm thuật toán quy hoạch động thông thường mà cần phải kết hợp thêm một kĩ thuật nữa. Một kĩ thuật khá thông dụng, hay được sử dụng trong các kì thi học sinh giỏi quốc gia, quốc tế là nhân ma trận.

Hiện nay, kĩ thuật nhân ma trận vận dụng nhiều trong những kì thi học viên giỏi môn tin học, nhưng tài liệu viết một cách cụ thể, mạng lưới hệ thống về kĩ thuật này thì chưa có. Điều này làm cho việc điều tra và nghiên cứu, giảng dạy và học kĩ thuật này khá khó khăn vất vả. Với kinh nghiệm tay nghề tu dưỡng học viên giỏi tỉnh, vương quốc tôi thấy những bài toán quy hoạch động thường thì thì học viên hoàn toàn có thể làm được, nhưng những bài toán quy hoạch động có tài liệu rất lớn thì học viên thường ít khi được 100 % số điểm, đó là một điều rất đáng tiếc. Vì vậy tôi đã quyết định hành động chọn và viết chuyên đề : “ Ứng dụng của phép nhân ma trận trong giải những bài toán Tin học ” .
Trong chuyên đề tôi sẽ trình diễn những kỹ năng và kiến thức về ma trận, phép nhân ma trận và ứng dụng kĩ thuật nhân ma trận trong những bài toán Tin học. Hi vọng đây là một tài liệu thiết thực so với những đồng nghiệp và những em học viên .

Xem thêm Hướng dẫn cách tải VssID để tra cứu BHXH, Bảo hiểm y tế ngay tại nhà

PHẦN II: NỘI DUNG

I. MA TRẬN (Matrix), NHÂN MA TRẬN (Matrix multiplication)

1. Khái niệm ma trận

1.1. Khái niệm ma trận

Trong toán học, ma trận là một mảng chữ nhật gồm các số, ký hiệu, hoặc biểu thức, sắp xếp theo hàng và cột mà mỗi ma trận tuân theo những quy tắc định trước. Các ô trong ma trận được gọi là các phần tử. Ví dụ dưới đây là một ma trận có 3 hàng và 2 cột:

Bạn đang đọc: Gác sách | Chuyên đề: Ứng dụng của phép nhân ma trận trong giải các bài toán Tin học

Khi định nghĩa một ma trận ta cần chỉ rõ số hàng m và số cột n của nó. Lúc này, mn được gọi là cấp của ma trận .
Các thành phần trong ma trận được định danh bằng 2 địa chỉ hàng i và cột j tương ứng. Ví dụ thành phần hàng thứ i, cột thứ j sẽ được kí hiệu là : Aij. Véc tơ hoàn toàn có thể coi là trường hợp đặt biệt của ma trận với số hàng hoặc số cột là 1 .

Ma trận vuông: Ma trận vuông là ma trận có số hàng bằng với số cột. Ví dụ một ma trận vuông cấp 3 (số hàng và số cột là 3) có dạng như sau:

$\begin{bmatrix} 2& 4& 6\\ 2& 3& 1\\ 0& 4& 9 \end{bmatrix}$

1.2. Khai báo ma trận trong ngôn ngữ lập trình C++

Sử dụng khai báo ma trận kiểu cấu trúc, giả sử khai báo cấu trúc ma trận có mảng dữ liệu val kích thước gồm 4 dòng, 4 cột; khởi tạo giá trị ban đầu cho các phần tử của ma trận đều bằng 0:

struct matrix   {
    long long  val[4][4];  //khai bao mang hai chieu chua du lieu cua ma tran
    matrix() //Ham khoi tao cho ma tran
    {
        memset(val,0,sizeof(val));    
    }   
};

2. Phép nhân ma trận

2.1. Các khái niệm về phép nhân ma trận

Cho 2 ma trận : ma trận A size M ∗ N và ma trận B kích cỡ N ∗ P ( quan tâm số cột của ma trận A phải bằng số hàng của ma trận B thì mới hoàn toàn có thể thực thi phép nhân ) .
Kết quả phép nhân ma trận A và B là ma trận C size M ∗ P, với mỗi thành phần của ma trận C được tính theo công thức :

Xem thêm TÍNH CHẤT HÓA HỌC, ĐIỀU CHẾ VÀ ỨNG DỤNG CỦA ANCOL

$Cik = \sum_{j=1}^{n} Aij * Bjk$ với i = 1..m, k = 1..p

Hay viết :

$Cik = \begin{bmatrix} ai1 & ai2& ...& ain \end{bmatrix} \begin{bmatrix} b1k\\ b2k\\ .\\ .\\ bnk \end{bmatrix}$ tức là phần tử ở dòng thứ i, cột thứ k của C là tích vô hướng của vectơ dòng thứ i của A với vectơ cột thứ k của B.

Ví dụ: Cho hai ma trận:

$A = \begin{bmatrix} -1 & 2 & 3\\ 2& 0& -4 \end{bmatrix}$ và $B =\begin{bmatrix} 1 & 2 & 1 & -1\\ 0 & 3 &2 & 0\\ -1 & 4 & 2 & 5 \end{bmatrix}$

Xem thêm: Tải Game & Ứng Dụng MOD APK Phổ Biến 2021 – ModRadar

Phần tử C23 của ma trận tích A * B là tích vô hướng của vectơ dòng thứ hai của ma trận A và vectơ cột thứ 3 của ma trận B, ta có :

$C23 = \begin{bmatrix} 2 & 0 & -4 \end{bmatrix} * \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix}$

Ma trận tích A * B có dạng :

$A*B = \begin{bmatrix} -1 & 2 & 3\\ 2& 0& -4 \end{bmatrix} * \begin{bmatrix} 1 & 2 & 1 & -1\\ 0 & 3 &2 & 0\\ -1 & 4 & 2 & 5 \end{bmatrix} = \begin{bmatrix} -4 & 16 & 9 & -22\\ 6 & -12 & -6 & -22 \end{bmatrix}$

Chú ý: Với ma trận vuông A cấp p (gồm p dòng, p cột) ta có thể thực hiện phép lũy thừa với số mũ k nguyên dương bất kì, kí hiệu là: Ak ; kết quả cũng là một ma trận vuông cấp p.

Ak = A * A * A * … * A ( k lần ma trận A )

2.2. Tính chất của phép nhân ma trận

Phép nhân ma trận không có tính chất giao hoán: có thể A*B nhưng B không thể nhân được với A, nếu nhân được thì kết quả A*B≠B*A.
Tính chất kết hợp: (A*B)*C=A*(B*C)
Tính chất phân phối: A*(B+D)=A*B+A*D, (B + C)D = BD + CD.

2.3. Cài đặt phép nhân ma trận trong ngôn ngữ lập trình C++

* Phép nhân 2 ma trận:

Cho hai ma trận : ma trận A kích cỡ m * n và ma trận B kích cỡ n * p. Phép nhân hai ma trận A * B được viết trong ngôn từ lập trình C + + như sau :

matrix a, b;
long long m,n,p;
matrix nhan(matrix a, matrix b)
{
    matrix c; //ma tran ket qua c=a*b
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= p; j++)
        {
            c.val[i][j] = 0;
            for (int k = 1; k <= n; k++)
                c.val[i][j] = c.val[i][j] + a.val[i][k] * b.val[k][j];
        }
    return c;
}

Nhận xét: Độ phức tạp O(m*n*p).

Xem thêm Tạo và chạy ứng dụng Android đầu tiên với Eclipse

Chú ý: Đối với phép nhân các ma trận vuông kích thước N∗N, có thuật toán nhân ma trận Strassen với độ phức tạp O(Nlog7) theo tư tưởng chia nhỏ ma trận (tương tự cách nhân nhanh 2 số lớn). Tuy nhiên cài đặt rất phức tạp và trên thực tế với giá trị N thường gặp, cách này không chạy nhanh hơn nhân ma trận thông thường O(N3).

Tính lũy thừa của ma trận: Ak

Cho ma trận vuông A size n * n. Khi đó ta có phép tính ma trận A lũy thừa k ( kí hiệu : Ak ), với k là số nguyên dương bất kể. Cài đặt phép toán này ta hoàn toàn có thể sử dụng 2 cách như sau :

Cách 1: Cài đặt bằng đệ quy

matrix mu(matrix a, long long k)
{
    matrix x;
    if ( k == 1) return a;
    x = mu (a, k/2);
    x = nhan (x, x);
    if (k % 2) x = nhan (x, a);
    return x;
}

Cách 2:Cài đặt bằng vòng lặp

Xem thêm: [Video] Cách tải lại ứng dụng đã xóa trên iPhone đơn giản, nhanh chóng - https://bem2.vn

matrix mu(matrix a, long long k)
{
    matrix x;//x là ma trận đơn vị
    for (;k; k/=2; a=nhan(a,a))
        if (k&1) x=nhan(x,a); //nếu k lẻ
    return x;
}

Hoặc :

matrix mu(matrix a, long long k)
{
    matrix x;//x là ma trận đơn vị
    while (k>0)
    { 
       if (k&1) x=nhan(x,a); //nếu k lẻ
           k/=2;
       a=nhan(a,a);
    }
    return x;
}

Nhận xét: Thuật toán tính Ak có độ phức tạp O(n3logk), với n là kích thước của ma trận vuông A.

II. BÀI TẬP ỨNG DỤNG.

Toàn bộ chuyên đề những bạn hoàn toàn có thể tải về ở đây

Source: https://bem2.vn
Category: Ứng dụng hay

Rate this post

Gác sách | Chuyên đề: Ứng dụng của phép nhân ma trận trong giải các bài toán Tin học