Author PhoenixH2000 2020-04-27

Lộ Trình Học Cấu Trúc Dữ Liệu Và Giải Thuật (Phần 2)

Ở bài trước, mình đã nói về việc chuẩn bị những gì và 4 vấn đề cần quan tâm đầu tiên về thuật toán. Trong bài viết này mình sẽ nói tiếp các vấn đề cần quan tâm khác và các nguồn tài liệu, trang web mình hay dùng trong quá trình học nhé.

Các vấn đề cần quan tâm còn lại

5. Cấu trúc dữ liệu stack, queue, dequeue

6. Quy hoạch động

7. Đồ thị

5. Cấu trúc dữ liệu stack, queue, dequeue

a. Stack (ngăn xếp)

Stack là CTDL cho phép thực hiện hai thao tác:

Thêm 1 phần tử vào cuối ngăn xếp
Xóa 1 phần tử ở cuối ngăn xếp

Cả 2 thao tác trên đều có độ phức tạp $O (1)$ . Chú ý ta chỉ có thể xóa phần tử ở cuối ngăn xếp (hay phần tử mới được thêm vào gần nhất) . Vì vậy, Stack còn được gọi là LIFO (Last In First Out).

Trong C++ STL, có sẵn kiểu dữ liệu stack, tuy nhiên chúng ta có thể cài tay như sau:

const int N = 1e6;

int top = 0;
int stack[N];

// Thêm 1 phần tử x ở cuối ngăn xếp
stack[++top] = x;

// Xóa 1 phần tử ở cuối ngăn xếp
if (top) {
	--top;
}

b. Queue (hàng đợi)

Queue là CTDL cho phép thực hiện các thao tác:

Thêm 1 phần tử vào cuối hàng đợi.
Xóa 1 phần tử khỏi đầu hàng đợi.

Cả 2 thao tác đều có độ phức tạp $O (1)$ . Chú ý ta chỉ có thể xóa phần tử ở đầu hàng đợi, nói cách khác là phần tử mà đã được thêm vào lâu nhất. Vì vậy, Queuecòn được gọi là FIFO (First In First Out).

Queue có cài đặt đơn giản và được sử dụng trong BFS.

Trong C++ STL, có sẵn kiểu dữ liệu queue, tuy nhiên ta có thể cài tay như sau:

const int N = 1e6;

int l = 0, r = -1;
int queue[N];

// Thêm 1 phần tử x vào cuối queue
stack[++r] = x;

// Xóa 1 phần tử ở đầu queue
if (l <= r) {
	++l;
}

c. Dequeue (hàng đợi hai đầu)

Về cơ bản thì dequeue là sự kết hợp của cả stack và queue, nó có thể hỗ trợ các thao tác thêm và xóa phần tử ở hai đầu của CTDL này.

d. Tổng quan

Ba CTDL được giới thiệu ở trên được ứng dụng khá nhiều vào các bài đồ thị và nhiều thuật toán hay khác. Bên cạnh các CTDL trên, trong C++ còn giới thiệu nhiều CTDL với hàm có sẵn như set, map, priority_queue,... Việc hiểu chúng cũng tương đối đơn giản nhưng việc ứng dụng vào các bài toán thì không dễ. Do đó việc học lý thuyết luôn cần phải đi đôi với làm bài tập, có như thế thì mới có thể nắm vững được thuật toán và các CTDL này.

Các bạn cũng có thể thử cài tay và submit các CTDL trên tại đây: https://www.spoj.com/PTIT/problems/basic/

6. Quy hoạch động

Như các bạn đã biết đến phương pháp đệ quy ở phần trước, phương pháp đệ quy tính toán các bài toán bằng cách giải quyết các bài toán nhỏ hơn thông qua lời gọi hàm đến chính nó. Tuy nhiên phương pháp đệ quy thường sử dụng bộ nhớ lớn và thời gian tính toán khổng lồ. Và quy hoạch động là một kỹ thuật nhằm cải thiện hai nhược điểm lớn trên của đệ quy là sử dụng bộ nhớ lớn và thời gian tính toán rất lớn.

Quy hoạch động là một phương pháp khó, vì mỗi bài toán tối ưu đều có một đặc thù riêng, nên cách giải quyết hoàn toàn khác nhau đòi hỏi người lập trình phải nắm vững bản chất của quy hoạch động. Quy hoạch động được dùng khi có một công thức hoặc một (một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã được tìm ra từ trước, và kết quả các bài toán sẽ được lưu lại để những lần tính toán tiếp theo nếu cần đến những kết quả đó thì không cần tốn thêm thời gian thực hiện lại những bài toán này nữa. Nói cách khác, quy hoạch động bắt đầu từ việc giải các bài toán nhỏ, để từ đó từng bước giải quyết bài toán lớn hơn , và cuối cùng là bài toán lớn nhất (bài toán ban đầu).

Trong quy hoạch động thì thường có hai cách nghĩ để giải bài, đó là bottom-up(dưới lên) và top-down(trên xuống):

Top-down: Bài toán được chia thành các bài toán con, các bài toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng, và các bài toán con này tiếp tục gọi đến bài toán con của chúng đến khi đủ dữ kiện để lấy ra kết quả tính toán. Đây là kỹ thuật đệ quy và lưu trữ được kết hợp với nhau, quy hoạch động giải quyết vấn đề. Ví dụ chính là đoạn code fibo của bài trước.
```
int f[100];
int fibo(int n) {
	f[0] = 1;
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		f[i] = f[i-1] + f[i-1];
	}
	return f[n];
}
```
Bottom-up: Tất cả các bài toán con có thể cần đến đều được giải trước (từ bài toán cơ sở trở đi) , sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. Cách tiếp cận này tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước không được trực quan như Top-down. Ví dụ cho phần này cũng chính là đoạn code fibo của bài trước luôn.
```
int f[100];
int fibo(int n) {
	if (n == 0 || n == 1) return f[n] = 1;
	if (f[n]) return f[n];
	return f[n] = fibo(n-1) + fibo(n-2);
}
```

Để nghĩ ra công thức của các bài toán quy hoạch động, không còn cách nào khác ngoài việc làm thật nhiều bài tập để hiểu tư tưởng của quy hoạch động. Khi giải quyết bài toán quy hoạch động, điều quan trọng là tìm ra được công thức truy hồi của bài toán đó, sau đó là lựa chọn một CTDL phù hợp để cài đặt.

Để luyện tập về quy hoạch động, các bạn có thể bắt đầu từ đây: http://vnoi.info/problems/list/?tag=52&page=1&sort_by=score

7. Đồ thị

Để tìm hiểu về đồ thị, thì theo mình thứ tự sẽ là:

Lý thuyết cơ bản về đồ thị (định nghĩa, phân loại đồ thị, đỉnh, cạnh, cạnh liên thuộc, bậc, đường đi, chu trình, đồ thị liên thông, ...)
Cách biểu diễn và lưu trữ đồ thị (có rất nhiều cách biểu diễn đồ thị nhưng 2 cách thường dùng nhất là danh sách kề và ma trận kề)
Các phương pháp duyệt đồ thị (DFS, BFS,...) và ứng dụng cho các bài toán về liên thông.
Các thuật toán tìm đường đi ngắn nhất (Dijkstra, Bellman Ford, Floyd)
Các thuật toán tìm cây khung nhỏ nhất (Kruskal sử dụng Disjoint Sets, Prim)
...

Theo mình liệt kê trên là các thuật toán cơ bản trong đồ thị, chắc chắn sẽ còn nhiều thuật toán hơn nhưng theo mình nếu chỉ luyện tập cơ bản thì như vậy là đủ.

Vậy tìm bài tập ở đâu?

Khi mới bắt đầu học, mình thường làm các bài tập ở trang SPOJ PTIT vì nó có khá nhiều bài cơ bản, các bạn chỉ cần bấm vào các mục ở danh sách bên trái, mỗi bài có tỉ lệ người làm được cao hơn là các bài được nhiều người giải được trong contest cũ đã public lại lên trang này. Ngoài ra có một trang khá hay là NTUcoder, ở đây các bạn vừa có thể luyện code, vừa có thể đọc code để học hỏi thuật toán.

Trong hai trang trên thì có những bài vừa sức và những bài cũng khá khó, nếu các bạn mới bắt đầu và muốn tìm hiểu và luyện tập các bài tập vừa sức, đa dạng hơn để chuẩn bị cho interview thì có thể làm các bài ở codelearn.io nhé. Ở trang này thì để giải bài, các bạn không cần phải viết cả một chương trình mà chỉ cần viết một hàm trả về kết quả của bài toán. Một số bài có lối tư duy khá mở, không nhất thiết thuộc về một thuật toán cụ thể nào, rất phù hợp để luyện tập phỏng vấn và nâng cao kỹ năng của mình. Hệ thống đang hỗ trợ 2 ngôn ngữ Tiếng Anh - Tiếng Việt, các bạn có thể tham gia khóa thuật toán căn bản ngay tại trang web này.

Khi cứng hơn một chút thì mình chuyển qua trang VNOI, vì trang này là trang luyện thi ACM và VOI nên các bài có độ khó tương đối cao và thú vị.

Ngoài ra, thì bạn có thể vào codeforces và hackerrank để luyện tập cho đa dạng. Codeforces có các contest định kỳ với bảng rank, ngoài ra cũng có thể làm lại các contest cũ và đọc được code giống trang NTUcoder. Hackerrank thì được làm bài theo phong cách ăn test case chứ không cần giải full bài như codeforces, cũng khá hay.

Kết

Hy vọng là qua 2 bài viết về CTDL&GT này của mình, các bạn đã phần nào có cái nhìn tổng quan hơn về môn học này và có cho mình thêm những kiến thức bổ ích. Trong một chương trình, phần cốt lõi của nó chính là thuật toán, "không thuật toán, không một chương trình nào hết". Do đó việc phân tích và thiết kế thuật toán là một khâu hết sức quan trọng trong quá trình làm nên một sản phẩm, vì vậy hãy bắt đầu ngay khi bạn mới làm quen với lập trình nhé.

Tham khảo: