Divide and conquer - khái niệm "vạn năng"

Tôi thấy bài viết này hay hữu ích, dịch lại để nhớ phòng khi cần áp dụng :)) 

Ý tưởng chính là mọi vấn đề dù phức tạp đến đâu đều có thể giải quyết bằng phương pháp chia để trị, vấn đề phức tạp sẽ được chia thành càng vấn đề càng nhỏ càng tốt. Nhỏ tới mức đơn giản để giải quyết. Một ví dụ tôi có thể nghĩ ra là chiếc máy tính của bạn làm được rất nhiều việc phức tạp như lướt web coi phim, làm văn bản, nhận diện giọng nói mặt người ... nhưng các việc máy tính làm ở phía dưới chỉ là các phép toán cộng, trừ, lấy dư ... của CPU với các bit 0,1 mà thôi

----

Divide and conquer (chia để trị) là tên của một nhóm các thuật toán giải quyết các vấn đề bằng cách đệ quy (đệ quy là một khái niệm lập trình mà một chương trình sử dụng một phiên bản nhỏ hơn của nó). Ví dụ như Quicksort, một thuật toán gọn gàng dùng để sắp xếp các phần tử của một danh sách, có sử dụng đệ quy.

Nhưng đó không phải là định nghĩa duy nhất của nó. Trong lịch sử nó bắt nguồn từ 'divide and rule', một khái niệm để chỉ những người dân bản địa chiến đấu với nhau làm cho kẻ thù chung cai trị tất cả bọn họ. Hợp lại chúng ta thắng, chia rẽ chúng ta thất bại ...

Lý do mà tôi cho rằng divide and conquer là một trong những chiến lược đầy sức mạnh trong lập trình, đó là nó có thể được áp dụng ở mức cao : khi viết các chương trình phức tạp. Nếu bạn gặp một vấn đề quá khó để giải quyết trong một bước, bạn có thể sử dụng devide and conquer từng bước cho tới khi vấn đề của bạn trở nên dễ dàng. Sau đó bạn trở lại với vấn đề ở một cấp phía trên và tái sử dụng nó cho tới khi tất cả các vấn đề phụ được giải quyết và điều này đồng nghĩa với việc bạn đã giải quyết được vấn đề phức tạp ban đầu rồi đó.

Thậm chí khái niệm này còn được áp dụng để giải quyết tất cả các vấn đề ngoài lĩnh vực lập trình. Tôi chỉ cho bạn một ví dụ nhé : bạn cần sửa sang lại ngôi nhà? Quá khó để nắm được hết trong chốc lát, và tôi chắc rằng nếu không có kế hoạch cụ thể bạn sẽ bế tắc, thậm chí tuyệt vọng tới mức đốt luôn ngôi nhà của bạn lúc nào không hay. Không cần phải thế đâu, hãy chia nhỏ vấn đề ra và mọi thứ sẽ dễ dàng hơn :

• cơ sở hạ tầng
• hệ thống điện
• đường dẫn khí ga
• đường ống nước
• hệ thống s
• các căn phòng
• phòng bếp
• sửa trần
• chuẩn bị tường
• sàn gạch
• bàn ăn
• hộp tủ
• phòng tắm
• làm trần
• đặt kính
• vặn ốc vít
• làm mượt
• sơn
• sưả tường
• lát tường
• lắp đặt vòi tắm
• lắp cửa kính
• phòng khách
• phòng áp mái
• tầng hầm

Tôi vừa mới liệt kê chi tiết vài hạng mục nhỏ, bạn không cần phải dừng lại ở bất kỳ cấp độ cụ thể nào, mà có thể chia càng nhỏ hạng mục tới mức bạn muốn. Đây là một bí quyết rất hữu ích, nó cho phép một người có thể giải quyết mọi vấn đề nếu cho anh ta đủ thời gian. Nó cũng áp dụng cho việc sữa chữa xe hơi, hệ thống điện, ...vân vân. Tôi chưa thấy một công việc nào mà 'divide and conquer' không làm cho nó đơn giản hơn và nó luôn làm tôi ngạc nhiên khi mọi người không biết về nó hay không biết làm thế nào để sử dụng nó trong thực tế. Và nếu bạn chia nhỏ công việc trước khi bắt tay vào làm thì hẳn nhiên nó đã trở thành một kế hoạch, mà nó sẽ càng dễ dàng hơn nếu bạn nhận ra trước được việc nào có thể sai hoặc thứ tự các việc cần làm trước, việc cần làm sau. Chẳng hạn như ở ví dụ trên, rõ ràng là bạn nên cần phải làm sàn của ngôi nhà trước khi làm các phụ kiện phòng bếp, nó giúp bạn tiết kiệm công sức và tiền của.

Rõ ràng là có vài trường hợp mà chiến lược này không dùng được. Nếu bạn có ước mong trèo lên đỉnh Everest một mình thì bạn sẽ khó mà hoàn thành được cho dù bạn đã chia nhỏ nó thành 2 quãng đường nhỏ hơn bằng toàn bộ hành trình. Bởi vì việc leo tới đỉnh Everest bản thân nó đã vượt ra khỏi giới hạn của một cá nhân con người. Nhưng gần như tất cả vấn đề bạn gặp hàng ngày, quy tắc này đảm bảo rằng bạn thường là có thể chia nhỏ chúng ra các vấn đề nhỏ hơn.

Vậy thì lần tới khi gặp phải vấn đề gì mà bạn không thể làm, trong lĩnh vực lập trình hay các vấn đề trong cuộc sống : Divide and conquer! Chia vấn đề thành hai phần nhỏ hơn bằng nhau nếu có thể, sau đó cố gắng giải quyết chúng và nếu chúng vẫn còn quá phức tạp thì hay lặp lại quá trình trên cho tới khi có ít nhất một vài phần của vấn đề lớn trở nên khả thi. Thậm chí đôi khi phải bỏ đi một phần nhỏ của vấn đề để làm cho công việc còn lại dễ giải quyết hơn.

Source : http://jacquesmattheij.com/divide-and-conquer

Học Algorithms, Ngày 03

Hôm nay học Week 1 Analysis of Algorithms [introduction] & [observations]. Phần này nói về việc phân tích các thuật toán.

Ghi lại một vài ý mà tôi cho là quan trọng.

1.[introduction]

Lý do tại sao cần phải phân tích thuật toán :

• Predict performance.
• Compare algorithms.
• Provide guarantees.
• Primary practical reason : avoid performance bugs.

Phân tích thuật toán như thế nào? Một trong các cách là dùng scientific method, nghĩa là dùng phương pháp khoa học. Gồm các bước chính sau :

• Observe some feature of the natural world.
• Hypothesize a model that is consistent with the observations.
• Predict events using hypothesis.
• Verify the predictions by making futher observations.
• Validate by repeating until the hypothesis and observations agree.

2.[observations]

Sử dụng phương pháp quan sát để mô hình hóa việc tính toán thời gian chạy với kích cỡ dữ liệu đầu vào.

Hầu hết được tính theo công thức : T(N) = aN^b

Từ các kết quả chạy chương trình thực tế, tính toán a và b. Dự đoán b bằng cách gấp đôi số liệu dữ liệu đầu vào, phương pháp "doubling hypothesis". So sánh tỷ lệ kết quả các lần chạy, tính log cơ số 2, -> tính được b.

Hypothesis. Running time is about a N^b with b = lg ratio

Sau đó tính a bằng cách thay vào công thức T(N) và kết quả từ việc chạy chương trình thực tế.

Sau đó so sánh lại kết quả thực tế và kết quả dự đoán cho tới khi 2 kết quả này gần nhau nhất có thể.

Một vài lưu ý nhỏ về việc ảnh hưởng của các tham số:

System independent effects.
・Algorithm.
・Input data.

System dependent effects.
・Hardware: CPU, memory, cache, …
・Software: compiler, interpreter, garbage collector, …
・System: operating system, network, other apps, …

Hôm sau học Week 1 Analysis of Algorithms [mathematical models]

Học Algorithms, Ngày 02

Hôm nay học "Week 1" [quick-find] & [quick-union]. Đã thấy khó hơn nhưng vẫn hiểu được không nhiều thì ít hơ hơ.

Ghi lại vài chú ý chính.

1. [quick-find]

Data structure.
・Integer array id[] of length N.
・Interpretation: p and q are connected if and only if they have the same id.

Operations.
・Find : check if p and q have the same id.
・Union : to merge components containing p and q, change all entries whose id equals id[p] to id[q].

quick-find is too slow. 

union is too expensive. It takes N*N array accesses to process a sequence of N union commands on N objects.

2. [quick-union]

Data structure. 

・Integer array id[] of length N. 

・Interpretation: id[i] is parent of i. 

・Root of i is id[id[id[...id[i]...]]].

Operations.

・Find : check if p and q have the same root. 

・Union : to merge components containing p and q, set the id of p's root to the id of q's root.

quick-union is also too slow.

find too expensive (could be N array accesses).

Túm lại là 2 thuật toán quick-find và quick-union có thể giải quyết được vấn đề [dynamic connectivity], một cái thì "tìm nhanh" , cái còn lại thì "hợp nhanh". Tuy nhiên 2 thuật toán này không hiệu quả về mặt hiệu năng, quá chậm khi số phần tử N lớn. Hai cái này gọi là "quandratic algorithms" nghĩa là thời gian tính toán tăng theo cấp số bình phương của kích cỡ.

Hôm sau sẽ học Week 1 [quick-union improvements] & [union-find applications].

Tự thiết kế nhà của mình

Mỗi ngày 1 ý tưởng

Có ý tưởng muốn tìm hiểu cách xây dựng một ngôi nhà. Từ đó có thể tự thiết kế ngôi nhà của mình.

Ngôi nhà mà tôi thich sẽ như thế này, bên ngoài sẽ nhiều cây cối (cây ăn trái như xoài, hồng xiêm, ổi càng tốt), bên trong thì đầy đủ tiện nghi với lò sưởi, điều hòa, chăn gối loại xịn và êm, rồi có bóng đèn nhiều màu sắc. Tivi truyền hình cáp, internet tốc độ cao.
Hơ hơ như thế có mơ mộng quá không nhỉ.

Sẽ tham khảo thêm nếu có đủ thời gian, và tất nhiên là $$ nữa.

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].

Học Algorithms, Part I trên Coursera

Từ hôm nay sẽ quay lại chuyện học hành, cho tử tể. Tôi thấy việc học từ trước đến giờ của mình thực sự "bát nháo", không biết dùng từ nào khác.

Cần làm một cuộc cải cách bằng việc tự học là chính. Dù khó khăn nhưng cũng phải mỉm cười đi tiếp, cũng xem như là một thử thách cho cuộc đời vốn nhàm chán.

Bắt đầu với khóa học Thuật toán, phần 1, https://www.coursera.org/course/algs4partI trên trang web học trực tuyến miễn phí nổi tiếng toàn thế giới Coursera với nhiều khóa học đến từ các trường học danh giá nhất trên tinh cầu Standford, Princenton ...

Tôi hay bỏ giữa chừng các khóa học, một phần do thiếu ý chí, phần do kiến thức chắp vá lổm chỗm nên khó theo đuổi được trọn vẹn. Lần này sẽ cố gắng học xong khóa này và viết blog tổng kết hàng ngày để theo dõi quá trình học của mình.

Hy vọng 2 hoặc 3 tháng nữa có bài tổng kết tốt đẹp cho bài blog bắt đầu ngày hôm nay này.