Dạy học kĩ thuật lập trình cho sinh viên ngành Kĩ thuật điện tử - viễn thông theo hướng phát triển tư duy điện toán

Đại số tuyến tính cũng được sử dụng trong hầu hết các ngành khoa học và lĩnh vực kĩ thuật, vì nó cho phép mô hình hóa nhiều hiện tượng tự nhiên và tính toán hiệu quả với các mô hình như vậy. Với ứng dụng trong khoa học tự nhiên (vật lý, công nghệ...) và khoa học xã hội (kinh tế...), vì các mô hình phi tuyến tính hay gặp trong tự nhiên và xã hội thường có thể xấp xỉ bằng mô hình tuyến tính [33].

Sử dụng đại số tuyến tính có thể giải chính xác hoặc gần đúng rất nhiều bài toán, bao gồm cả các bài toán không tuyến tính. Lý do là ta luôn có thể sử dụng vi giải tích để biến các hàm không tuyến tính thành gần đúng tuyến tính ở gần những điểm quan tâm. Phương pháp này là một trong những phương pháp phổ biến nhất trong toán học ứng dụng vào khoa học và kĩ thuật.

Nhiều vấn đề kĩ thuật phức tạp trong cuộc sống, khoa học đều đưa về giải hệ này. Có thể nêu ra một số các ứng dụng của đại số tuyến tính như trong hóa học (việc cân bằng các phương trình phản ứng hóa học), ứng dụng trong tin học (lý thuyết mã hóa thông tin, mật mã, nén ảnh, lý thuyết đồ thị,…), ứng dụng trong di truyền học, ứng dụng trong, phân bố nhiệt độ, ứng dụng trong xã hội học,…

Một ví dụ minh họa trong quá trình mã hóa thông tin. Các thông điệp được truyền đi (như dữ liệu từ vệ tinh) thường là những thông tin đã bị gây nhiễu. Điều cần thiết là khả năng mã hóa một tin nhắn theo cách mà sau khi tiếng ồn đã gây nhiều nó, thông tin có thể được giải mã về dạng thông tin chính thống ban đầu. Trong ứng dụng của đại số tuyến tính, có thể xem xét cách thức giải mã một thông điệp sau khi nó bị bóp méo bởi một loại tiếng ồn. Đó là quá trình mã hóa thông tin. Một mã phát hiện lỗi trong một tin nhắn bị nhiễu gọi là phát hiện lỗi. Nếu có thể sửa lỗi thì được gọi là sửa lỗi. Trong tin học, có nhiều kĩ thuật mã hóa từ cơ bản đến nâng cao, cũng như thuật toán sửa lỗi sẽ quy về giải đại số tuyến tính [33].

Một ứng dụng đại số tuyến tính quan trọng nữa trong thế giới kĩ thuật số ngày nay đó là phát triển thuật toán song song thực hiện trên GPU (Graphic Processing Unit). Đó là xu hướng nghiên cứi mới bên cạnh các mô hình quen thuộc như MPI (Message Passing Interface), OpenMP,... Sự bùng nổ của Internet, sự bùng nổ của xu thế mọi thiết bị đều kết nối (Internet of thing - IOT), sự bùng nổ về nhu cầu thưởng các sẩn phầm âm thanh đồ họa độ phân giải cao và chất lượng cao, sự bùng nổ của các dịch vụ lưu trữ đám mây, dịch vụ trực tuyến, đã khiến cho khối lượng dữ liệu mà vi xử lý (CPU) phải tính toán ngày càng lớn và thực sự đã vượt quá nhanh so với sự phát triển tốc độ của CPU. Không những thế con người mặc dù muốn có nhiều thông tin hơn, thông tin phải tốt hơn lại còn muốn tốc độ xử lý phải nhanh hơn, điều này càng làm cho nhu cầu tính toán trong lĩnh vực khoa học, công nghệ đã và đang trở thành một thách thức lớn. Từ đó các giải pháp nhằm tăng tốc độ tính toán đã được ra đời. Hệ thống tính toán GPU là một giải pháp mới khắc phục tốt các hạn chế về chi phí rất lớn cho một hệ thống tính toán hiệu năng cao [43].

Với lợi ích của việc phát triển thuật toán song song hóa trên GPU nên việc cung cấp cho sinh viên các thuật toán của phương pháp số để xấp xỉ bài toán và đánh giá độ phức tạp của thuật toán khi thực hiện mô phỏng với dữ liệu lớn là rất cần thiết, đồng thời vận dụng việc phát triển tư duy điện toán cho SV trong quá trình phân tích và mô phỏng hệ thống bằng máy tính [73] [33].

Trong đại số tuyến tính để hướng dẫn SV vận dụng tư duy điện toán để thiết lập thuật toán từ kiến thức toán học được học trước đó, có thể viết minh họa một thuật toán Partial Pivoting của phương pháp khử Gauss [11] như sau:

Bước 1: Tại dòng thứ k, ta tìm phần tử có giá trị lớn nhất của vector cột thứ k:

Có thể bạn quan tâm!

Xem toàn bộ 235 trang tài liệu này.

|𝑎𝑝𝑘| = max

𝑗=𝑘,…,𝑛

|𝑎𝑗𝑘| (tức là giá trị lớn nhất nằm ở dòng thứ p).

Bước 2: Đổi hai dòng thứ k và thứ p của ma trận A’ cho nhau, ta được ma trận A”.

Bước 3: Thực hiện thuật toán Gauss1 cho ma trận A”:

𝑎(𝑘+1)

= 𝑎

(𝑘)

𝑎(𝑘)

𝑎

−𝑖𝑘 𝑎

(𝑘)

𝑘 = 1, 2, … , 𝑛 − 1;

𝑖𝑗

(𝑘+1)

𝑖𝑗

(𝑘)

𝑘𝑘

𝑎(𝑘)

𝑘𝑗

(𝑘)

𝑣ớ𝑖 |

𝑖 = 𝑘 + 1, … , 𝑛;

𝑗 = 𝑘, … , 𝑛

𝑏 = 𝑏

−𝑖𝑘𝑏

𝑎

𝑖 𝑖

{

(𝑘) 𝑘

𝑘𝑘

Đoạn chương trình mô phỏng thuật toán Partial Pivoting của phương pháp khử Gauss như sau:

import numpy as np

def Gauss2(A,b):

n = len(b)

for k in range(n-1):

# Tim dong p co abs(A(j,k)) lon nhat p = k

for j in range(k+1,n):

if abs(A[j,k]) > abs(A[p,k]): p = j

# Thuc hien doi dong p va k A[[k,p]] = A[[p,k]]

b[k],b[p] = b[p],b[k] for i in range(k+1,n): m = A[i,k]/A[k,k]

for j in range(k,n):

A[i,j] = A[i,j] - m * A[k,j] b[i] = b[i] - m * b[k]

return A, b

c3. Thuật toán nội suy và ứng dụng

Nội suy là phương pháp ước tính giá trị của các điểm dữ liệu chưa biết trong phạm vi của một tập hợp rời rạc chứa một số điểm dữ liệu đã biết. Trong khoa học kĩ thuật, người ta thường có một số điểm dữ liệu đã biết giá trị bằng cách lấy mẫu thực nghiệm. Những điểm này là giá trị đại diện của một hàm số của một biến số độc lập có một lượng giới hạn các giá trị. Thường chúng ta phải nội suy (hoặc ước tính) giá trị của hàm số này cho một giá trị trung gian của một biến độc lập. Điều này có thể thực hiện bằng phương pháp đường cong phù hợp hoặc phân tích hồi quy.

Bài toán nội suy [11] [44] là bài toán tìm giá trị gần đúng của y tại các điểm nằm giữa các giá trị x không có trong bảng trên. Nếu cần tìm các giá trị gần đúng của y tại các điểm x nằm ngoài khoảng [x0, xn] thì bài toán được gọi là bài toán ngoại suy. Một bộ n+1 cặp các giá trị đã biết của x và y: (x0,y0), (x1,y1), . . . , (xn,yn) được gọi là một mẫu quan sát, còn x0, x1, ... , xn được gọi là các điểm quan sát và y0, y1, ..., yn là các kết quả quan sát.

Một số đoạn chương trình mô phỏng các thuật toán nội suy đa thức như sau:

/*Tra ve gia tri da thuc noi suy tai x; anew[i] la cac he so da thuc noi suy Newton, xqs[i] la cac diem quan sat*/

double polinew(double x)

{ int i ; double mx, s; s=anew[0 ]; mx=1;

for(i=0 ; i<nqs ; i++)

{ mx*=(x-xqs[i]) ; s+= anew[i+1]*mx ;

}

return s ;

}

/*Tra ve gia tri da thuc noi suy tai x; alag[i] la cac he so cua da thuc noi suy Lagrange , xqs[i] la cac diem quan sat*/

double polilag(double x)

{ int i, j;

s=0 ;

double mx, s;

for( i=0 ; i<=nqs ; i++ )

{ mx=1;

for(j=0 ; j<=nqs ; j++)

if (j!=i) mx*=(x-xqs[j]) ; s+=alag[i]*mx;

}

return s;

}

/*Noi suy Newton voi khoang chia khong can deu */ void nsnewton(double *a)

{ int h, i, j, k ; double tmp ; kvecto sp ;

a[0]=yqs[0] ;

for(i=0 ; i<=nqs-1 ; i++)

//Tinh sai phan bac 1;

sp[i]=(yqs[i+1]-yqs[i])/(xqs[i+1]-xqs[i]) ; a[1]=sp[0] ;

for(k=2;k<=nqs;k++) //Tinh cac sai phan bac k va cac he so a[i]

{ for(i=0 ; i<=nqs-k ; i++)

sp[i]=(sp[i+1]-sp[i])/(xqs[i+k]-xqs[i]); a[k]=sp[0];

}

/*Noi suy Lagrange voi khoang chia khong can deu – Tinh cac he so*/ a[i] = 1/((x[i]-x[0])(x[i]-x[1])...(x[i]-x[i-1])(x[i]-x[i+1])...x[m])*/ void nslagrange(double *a)

{ int h, i, j, k ; double tmp ;

for(i=0;i<=nqs;i++)

{ tmp=1;

//Tinh cac he so a[i];

for(j=0; j<=nqs; j++)

if(j!=i) tmp=tmp*(xqs[i]-xqs[j]); a[i]=yqs[i]/tmp;

}

SV sẽ thường được học phương pháp giải bài toán nội suy bằng đa thức [44]. Các đa thức nội suy thường có bậc là n, trong đó n+1 là số điểm quan sát. Có thể tiến hành nội suy bằng đa thức bậc m nhỏ hơn n, nhưng như vậy thì ta cũng chỉ dùng đến mẫu quan sát dựa trên m+1 điểm là (x0,y0), (x1,y1), ..., (xm,ym) và như thế chỉ nội suy được giá trị của hàm tại các điểm x ∈ [x0,xm]. Điều này chứng tỏ ra không được phù hợp với thực tế cho lắm. Thật vậy, giả sử trong thực tế hàm f(x) là một đa thức bậc 3 nhưng vì ta không biết điều này nên phải dùng đa thức nội suy. Theo một cách tự nhiên, nếu có càng nhiều thông tin thì ta càng giải quyết bài toán tốt hơn. Nghĩa là nếu có càng nhiều điểm quan sát thì kết quả càng gần với thực tế hơn. Tuy nhiên, nếu dùng đa thức nội suy như kiểu vừa khảo sát thì không có được như điều mong đợi. Phép nội suy đa thức còn có một nhược điểm nữa là số lượng phép tính cần thực hiện phụ thuộc rất nhiều vào cỡ của mẫu quan sát. Trong kĩ thuật truyền thông chẳng hạn, việc chuyển đổi một tín hiệu số có hàng ngàn điểm quan sát sang dạng tương tự là vấn đề thường gặp. Thế nhưng chỉ cần nội suy đa thức cho 101 điểm quan sát ta đã phải dùng đến đa thức bậc 100, và việc dùng đa thức bậc 100 để tính toán cho các điểm còn lại là một việc tiêu tốn tài nguyên máy một cách quá lãng phí. Vì vậy có thể nói rằng phép nội suy đa thức chỉ có ý nghĩa lý thuyết mà thôi, trong thực tế hầu như người ta không dùng đến. Để tìm kiếm một cách nội suy gần với thực tế hơn, GV cho SV tư duy sử dụng kiến thức về dạng nội suy đường cong (spline) [44]. Chẳng hạn, để tìm kiếm nội suy thực tế hơn, SV muốn vẽ đồ thị hàm số nào đó, hãy bắt đầu bằng một thao tác đơn giản là vẽ các điểm rời rạc, và vẽ được càng nhiều điểm càng tốt. Sau đó, dùng bút nối các điểm đó với nhau, nhưng không nối bằng thước kẻ, mà nối bằng bút và sự quan sát bằng mắt sao cho các đoạn nối các điểm thành một đường mịn, không bị gãy khúc.

Đoạn chương trình mô phỏng thuật toán nội suy spline như sau:

import numpy as np

from matplotlib import pyplot as

plt

def myspline(x,y,bcond =

{"btype":1,"bleft":0,"bright":0}):

if bcond["btype"] == 1:

# Dieu kien bien type 2: s''(a) = f''(a), s''(b) = f''(b)

if "bleft" in bcond:

d2f0 = bcond["bleft"]

else:

d2f0 = 0

if "bright" in bcond:

d2fn = bcond["bright"]

else:

d2fn = 0

elif bcond["btype"] == 2:

# Dieu kien bien type 1: s'(a) = f'(a), s'(b) = f'(b)

if "bleft" in bcond:

df0 = bcond["bleft"]

else:

df0 = 0

if "bright" in bcond:

dfn = bcond["bright"]

else:

dfn = 0 n = len(x)

h = x[1:] - x[0:-1]

a0 = h/6

a1 = np.zeros(n)

a1[1:-1] = (h[0:-1]+h[1:])/3

if bcond["btype"] == 1: a1[0] = 1

a1[-1] = 1

a0[0] = 0

a0[-1] = 0

elif bcond["btype"] == 2: a1[0] = h[0]/3

a1[-1] = h[-1]/3

elif bcond["btype"] == 3: n = n-1

a1[0] = (h[0]+h[-1])/3 a1 = a1[:-1]

a0 = a0[:-1]

A0 = np.diag(a0,-1) A1 = np.diag(a1)

A2 = np.diag(a0,1)

A = A0 + A1 + A2

if bcond["btype"] == 3:

A[0,-1] = h[-1]/6

A[-1,0] = h[-1]/6 z = (y[1:]-y[0:-1])/h

d = z[1:]-z[0:-1]

if bcond["btype"] == 1:

d = np.insert(d,0,d2f0) d = np.append(d,d2fn)

elif bcond["btype"] == 2:

d = np.insert(d,0,z[0] - df0)

d = np.append(d,dfn-z[-1])

elif bcond["btype"] == 3:

d = np.insert(d,0,z[0]-z[-1]) m = np.linalg.solve(A,d)

if bcond["btype"] == 3: m = np.append(m,m[0])

# print(A,d)

return h,m

Đây là kiến thức cơ bản SV được học trong chương trình, nhằm giúp SV có thể dựng lại dữ liệu, khôi phục dữ liệu, giảm ước tính toán để xác định được quy luật, xác định được hàm số.