Tabulation And Memozitation [ Dynamic Programming ] [ Set 1 ]

LÝ THUYẾT CƠ SỞ

Có hai cách thức để lưu các value của một problem mà những value này có thể được tái sử dụng.
Ở đây, chúng ta tập trung vào hai mô hình của việc giải quyết problem thông qua dynamic programming. Đó là:
1. Tabulation: Sự sắp xếp thành bảng, cột. Từ dưới lên gọi là bottom up.
2. Memoization: Sự ghi nhớ hay lưu trữ. Từ trên xuống gọi là top down

Trước khi đi đến những định nghĩa của hai mục trên, ta xem xét 2 phát biểu sau:
Version 1: Tôi sẽ học lý thuyết của Quy hoạch động từ blog buingoctai.blogspot.com và sau đó practice vài problem trên đây, dĩ nhiên tôi sẽ trở thành chuyên gia về lập trình quy hoạch động.
Version 2:  Để trở thành một chuyên gia về lập trình quy hoạch động, tôi cần luyện tập giải quyết nhiều problem về quy hoạch động, do đó đầu tiên, tôi cần học lý thuyết về quy hoạch động từ trang buingoctai.blogspot.com.

Cả hai version trên đều giống nhau về mặt nội  dung, chỉ khác nhau về cách truyền đạt lời nhắn trên và đó chính xác là cách làm việc của bottom up và top down.
Version 1 có thể được xem như bottom up và Version 2 được xem như top down.

TABULATION METHOD- BOTTOM UP DYNAMIC PROGRAMMING

Đúng như cái tên của nó, bắt đầu từ đấy và tích lũy câu trả lời đến top.
cùng thảo luận vào những mục của sự chuyển đổi trạng thái.
Ta xem trạng thái cơ sở được gắn liền với dp[0] và trạng thái đích là dp[n]. vì vậy ta cần tìm value của trạng thái đích dp[n]
Cách tiếp cận theo kiểu bottom up là chúng ta bắt đầu sự chuyển đổi từ trạng thái cơ bản bottom và đi đến trạng thái top mong muốn.

 Vậy tại sao ta gọi đó là tabulation method ?
Để hiểu được nó, ta cần viết 1 vài dòng code tinh thừa số của một số sử dụng cách tiếp cận bottom up. Các thủ tục thông thường để solve một DP problem là đầu tiên ta cần định nghĩa một trạng thái.
trong trường hợp này ta định nghĩa 1 trạng thái như 1 dp[x] mà ở đó dp[x] là để tìm thừa số của x.
Rất dễ hiểu rằng dp[x+1]=dp[x]*(x+1). ví dụ tìm giai thừa của 4 thì rõ ràng ta thấy giai thừa của 4= giai thừa của 3  nhân cho 4
implement trong c:

Ở cách tiếp cận theo phương pháp tabulation trên, ta bắt đầu sự chuyển tiếp từ đáy với trạng thái cơ bản là dp[0] và tới trạng thái đích là dp[9]. ở đây chúng ta nhận thấy rằng bảng dp được thêm vào một cách tuần tự và chúng ta truy cập và tính trực tiếp từ bảng đó . Và do đó ta gọi phương pháp này là tabulation ( lập bảng)

MEMOZATION METHOD- TOP DOWN DYNAMIC PROGRAMMING

Phương pháp memozation rất giống với phương pháp chia để trị, tức là ta chi nhỏ bài toán thành các bài toán con, sau đó đi tìm lời giải các bài toán con, để tổng hợp thành lời giải cho bài toán ban đầu. Nhưng khác phương pháp chia để trị ở chỗ là phương pháp này nó giúp ta ghi nhớ lời giải các bài toán con để có thể tái sử dụng chúng cho các problem khác nên nó cũng được gọi là phương pháp ghi nhớ.

Ta thấy rằng lời giải của các bài toán con được lưu vào mảng dp[]

TÓM LẠI: Ý tưởng của quy hoạch động khá đơn giản " mỗi khi tính toán một problem nào đó, ta lưu kết quả của nó để trong tương lai, nếu sau này có gặp vấn đề đó sau này thì không phải tính lại nữa. Nếu một problem có thể chia nhỏ thành các sub- problem và các sub-problem này chồng chéo lên nhau, tức kết của sub-problem này dùng để giải các sub-problem kia thì đây là lúc cần dùng quy hoạch động "

Tham khảo: https://www.geeksforgeeks.org/

Đọc tiếp »

LINEAR ALGEBRA ( ĐẠI SỐ TUYẾN TÍNH )

1. CHUYỂN VỊ VÀ CHUYỂN VỊ LIÊN HỢP
   Lý thuyết cơ sở

• Chuyển vị

Cho A ∈ R^m*n, ta nói B ∈ R^m*n là chuyển vị của A nếu như bij=aji với mọi 1<= i <=n
và 1<= j <= m. Chuyển vị của một ma trận nhận được từ ma trận cũ thông qua phép phản xạ gương qua đường chéo chính của ma trận ban đầu. Ký hiệu: T
Nếu  A ∈ R^m*n,  A^T=A thì ma trận A được gọi là ma trận đối xứng.

Ví dụ:

• Chuyển vị liên hợp

Định nghĩa giống với chuyển vị thông thường, tuy nhiên các thành phần của vector hay ma trận là số phức. Việc lấy chuyển vị đi kèm với lấy liên hợp phức. Ký hiệu : H

Nếu A ∈ R^m*n,  A^H=A thì ma trận A được gọi là hermitan.

Ví dụ:

Implement by Python code

Problem: Tìm ma trận chuyển vị của ma trận a và vector b.

Solution: Sử dụng các lớp và hàm mà module numpy cung cấp

Cách implement 1: Ta sử dụng class array của module numpy, tạo ra hai đối tượng a và b.

sau đó ta tìm ma trận chuyển vị của hai ma trận trên bằng cách dùng hàm transpose của module numpy hỗ trợ.

Cách implement 2: Khi tìm ma trận chuyển vị, ta dùng hàm toán tử T của class array.

Kết quả giống nhau cho hai cách implement trên !

Các thuật ngữ tiếng anh dùng cho tra cứu:
Toán tử chuyển vị: Transpose operator
Ma trận đối xứng: Symmetric matrix
chuyển vị liên hợp: Conjugate transpose

Tham khảo tài liệu:
-Machine learning cơ bản- Vũ Hữu Tiệp

Edit bye me_BNT.

Mong nhận được đóng góp ý kiến từ độc giả.

Xin chân thành cảm ơn !

Đọc tiếp »

Median in a stream of intergers ( Part 1) [ Statistical Algorithms ]

Problem: Cho một dãy số interger được đọc từ 1 data stream. Tìm median của dãy online data.

Sau khi số đầu tiên của stream là 5 là median là 5

…….số thứ 2…………….. là 15, dãy số 5 , 15 là median là 10

…….số thứ 3 …. Là 1,dãy số 5,15,1 và median là 5

…….số thứ 4….là 3, dãy số là 5,15,1,3 và median là 4



Lưu ý: Cần sắp xếp trước khi tìm median. Output là median của dãy số interger đọc từ stream.
Một thuật toán như thế gọi là online algorithm.
" Any algorithm that can guarantee output of i-elements after processing i-th element, is said to be online algorithm "( Các định nghĩa luôn được giữ nguyên bảng bằng tiếng anh).

Có 3 solutions cho problem trên, chúng ta bắt đầu với giải pháp đầu tiên:

Method 1: Tư tưởng thuật toán insertion sort
Tóm tắt nội dung thuật toán insertion sort: Thuật toán này giả định ta có 1 nhóm phần tử đầu tiên đã được sắp xếp, ta lần lượt chèn các phần tử còn lại vào nhóm phần tử trên.

Ban đầu, nhóm phần tử đó chỉ là phần tử đầu tiên của dãy. Lập lần 1, ta chèn phần tử thứ 2 vào nhóm trên sao cho phù hợp, ta có số lượng của nhóm phần tử đầu tiên là 2, lập lần 3, ta số lượng nhóm phần tử đầu tiên là 3, cứ như thế lập n-1 lần ( với n là số lượng phần tử của dãy số ban đầu)  thì ta có được danh sách đã được sắp.

Quay trở lại problem trên, nếu ta có thể sắp xếp data ngay khi nó xuất hiện, chúng ta có thể dễ dàng xác định được median. Insertion sort là 1 online algorithm mà sắp xếp data ngay khi nó xuất hiện.

Ta thấy rằng sau khi sắp xếp element thứ i, i elements của mảng thì được sắp xếp. Insertion sort không phụ thuộc vào data tương lai. Điều này làm nó được gọi là online algorithm.

Tuy nhiên, insertion sort mất O(n^2) để sắp xếp n elements. Có lẽ chúng ta có thể dùng binary search trên insertion sort để vị trí của element kế tiếp trong time O(nlogn).

Tuy vậy, chúng ta không thể làm vậy để duy chuyển data trong time O(nlogn).
Nó mất polynomial time trong trường hợp insertion sort.


Implement: Full python code

Time complexity: O(n^2)

Mong nhận được đóng góp từ bạn đọc.

Xin chân thành cảm ơn !

Edit bye me_BNT

Đọc tiếp »