Học Algorithms, Ngày 01

Hôm nay học "Week 0 : Welcome to Algorithms" và "Week 1 : Union-find" [dynamic connectivity]

Mới bắt đầu, chính yếu là giới thiệu xem hoa một chút chưa có kiến thức gì nặng nề cả.

Ghi chú lại vài điểm mà tôi cho là quan trọng :

• Algorithm : method for solving a problem
• Data structure : method to store information

Data structure thì luôn gắn kèm với một vấn đề nào đó cần giải quyết, và luôn đi cùng với algorithm. Hình dung algorithm và data structure như thể tay với chân vậy đó. Cùng phối hợp, làm việc với nhau để solve problems. Mà giải được câu đố nào đó thì quá tuyệt rồi đúng không?

Tại sao lại học thuật toán ?

• Their impact is broad and far-reaching.
• Old roots, new opportunities.
• To solve problems that could not otherwise be addressed.
• For intellectual stimulation.
• To become a proficient programmer.
• They may unlock the secrets of life and of the universe.

Các bước để xây dựng một thuật toán hữu dụng ?

• Model the problem.
• Find an algorithm to solve it.
• Fast enough? Fits in memory?
• If not, figure out why.
• Find a way to address the problem.
• Iterate until satisfied.

Một ví dụ được dùng để phát triển một algorithm cho vấn đề dynamic connectivity.

Bài toán là cho N phần tử, với "union command" để kết nối 2 phần tử, với "find query" để kiểm tra xem 2 phần tử có kết nối với nhau không. Bài toán là cần tìm một thuật toán hữu dụng để kiểm tra xem 2 phần tử bất kỳ có kết nối với nhau hay không ?

Rồi, bắt đầu các bước để xây dựng thuật toán.

Việc đầu tiền là : modeling the objects
Việc tiếp là : modeling the connection
Tiếp là : implementing the operations (find query, union command)
Nữa là : thiết kế một data structure hữu hiệu cho thuật toán Union-find

Túm lại là có cái Union-find data type (API) như phía dưới :

public class UF
UF(int N) --> initialize union-find data structure with N objects (0 to N – 1)
void union(int p, int q) -->add connection between p and q
boolean connected(int p, int q) --> are p and q in the same component?
int find(int p) --> component identifier for p (0 to N – 1)
int count() --> number of components

Ngày mai sẽ học tiếp "Week 1" [quick find] & [quick union].