Tổng quan về thuật toán và cấu trúc dữ liệu

Trước khi đi chi tiết vào các nội dung chi tiết tiếp theo của khóa học, ta xem xét ví dụ sau:

Question :

• Giả sử ta có một danh sách các cặp thông tin: (họ và tên, số điện thoại) dưới dạng: (t1,s1),(t2,s2),...,(tn,sn).
• Yêu cầu đặt ra là hãy viết một chương trình cho phép in ra "số điện thoại" khi nhập "họ và tên" của một người bất kỳ.

Để giải bài toán này, chúng ta có thể sử dụng nhiều cách thức như sau:

• Một cách đơn giản và trực quan nhất mà chúng ta có thể nghĩ đến đó là duyệt lần lượt danh sách đã cho theo tên t1,t2,...tn cho tới khi tìm thấy tên đã chỉ định, thì sẽ tiến hành đối chiếu để lấy ra số điện thoại tương ứng của người này. Tuy nhiên, để duyệt qua toàn bộ một danh sách rất lớn sẽ tốn khá nhiều thời gian. Hãy thử tưởng tượng đây là chức năng của một chương trình tìm kiếm số của tổng đài điện thoại thì nó sẽ cực kỳ chậm, nhất là khi phải nhận đến hàng triệu truy vấn vào cùng một thời điểm thì rõ ràng điều này sẽ làm tắc nghẽn dịch vụ.
• Một cách nhanh hơn, nếu trước đó danh mục điện thoại đã được sắp xếp theo thứ tự từ điển (dictionary order) đối với họ và tên, thì chúng ta có thể áp dụng một giải thuật tìm kiếm khác tốt hơn, như ta vẫn thường làm khi tra từ điển. Khi bạn tra từ điển, rõ ràng bạn sẽ không lật từng trang phải không? Bạn sẽ làm gì? Như tôi, tôi sẽ thường làm như thế này: Lật đến vị trí nào đó của từ điển, nghĩ xem từ mình cần tìm là trước hoặc sau trang này, sau đó sẽ lật tiếp ngẫu nhiên đến phía mà tôi nghĩ nó sẽ ở, rồi tiếp tục các bước như vừa làm cho tới khi tìm được từ mong muốn. Rõ ràng, dù chưa hiểu thuật toán là gì, bạn cũng có thể dễ dàng thấy cách này về mặt trực quan đã tốt hơn cách phía trước rất nhiều phải không?
• Hoặc, cải tiến hơn nữa, trong từ điển còn có thêm một bảng mục lục để chỉ dẫn theo chữ cái đầu tiên của "Họ và tên", thì chắc rằng khi tìm số điện thoại của "Nguyễn Văn Long" ta sẽ dễ dàng bỏ qua được các tên khác mà chữ đầu không phải là chữ Ng. Nhanh hơn rất nhiều nữa phải không?

Note!!

Trong ví dụ trên: Danh sách điện thoại là một dạng dữ liệu nó sẽ được tổ chức theo nhiều cách khác nhau cho từng trường hợp:

• danh sách thông thường;
• danh sách sắp xếp theo thú tự từ điển;
• danh sách được sắp xếp và chỉ mục có mục lục.

Đây là các "cấu trúc dữ liệu". Còn các cách thức thực hiện việc tra cứu theo từng dạng "cấu trúc dữ liệu" được gọi là "thuật toán" hay "giải thuật".

Thuật toán và cấu trúc dữ liệu

Từ ví dụ trên ta có thể thấy giữa cấu trúc dữ liệu và giải thuật có mối quan hệ mật thiết. Có thể coi chúng như hình với bóng. Không thể nói tới cái này mà không nhắc tới cái kia. Niklaus Wirth đã đưa ra một công thức thể hiện khá rõ vai trò và mối liên hệ giữa cấu trúc dữ liệu và thuật toán:

Note!!

CHƯƠNG TRÌNH = THUẬT TOÁN + CẤU TRÚC DỮ LIỆU

Programs = Algorithms + Data structures

Một thuật toán giải bài toán bao giờ cũng thao tác trên một cách tổ chức dữ liệu (cấu trúc dữ liệu) cụ thể và các thao tác phải được cấu trúc dữ liệu đó hỗ trợ.

Tip&Trick

Sau này R. Kowalski còn phân tích chi tiết hơn công thức trên bằng cách đưa ra công thức: "Algorithms = Logic + Control", với ý nghĩa thuật toán gồm hai thành phần: thành phần logic xác định tri thức được dùng trong việc giải bài toán và thành phần điều khiển xác định các chiến lược giải toán theo tri thức được sử dụng. Thành phần logic xác định ý nghĩa của thuật toán, còn thành phần điều khiển liên quan đến tính hiệu quả của thuật toán. Tính hiệu quả có thể được cải thiện bằng cách cải thiện phần điều khiển mà không thay đổi logic của thuật toán.

Khi tổ chức dữ liệu cho bài toán thay đổi thì thuật toán cũng phải thay đổi theo để phù hợp với cách tổ chức dữ liệu mới. Chẳng hạn như ví dụ trên, một danh sách bất kỳ sẽ phải xử lý khác một danh sách có thứ tự và một danh sách có thứ tự lại khác một danh sách đã được đánh chỉ số. Trong quá trình xây dựng, hoàn thiện thuật toán cũng sẽ gợi mở cho chúng ta cách tổ chức dữ liệu phù hợp với thuật toán và tiết kiệm tài nguyên của hệ thống. Quá trình giải một bài toán trên máy tính là một quá trình hoàn thiện dần cách tổ chức dữ liệu và thuật toán để tăng hiệu quả cho nó.

Có thể, đôi lúc, khi nói tới việc giải quyết bài toán trên máy tính, chúng ta chỉ chú ý đến giải thuật hay thuật toán (algorithms). Nhưng, xét cho cùng, giải thuật chỉ phản ánh các phép xử lý, còn đối tượng để xử lý trên máy tính điện tử, chính là dữ liệu (data) chúng biểu diễn các thông tin cần thiết cho bài toán: các dữ kiện đưa vào, các kết quả trung gian... Không thể nói tới giải thuật mà không nghĩ tới: giải thuật đó được tác động trên dữ liệu nào, còn khi xét tới dữ liệu thì cũng phải hiểu: dữ liệu ấy cần được tác động giải thuật gì để đưa tới kết quả mong muốn. Bản thân các phần tử của dữ liệu thường có mối quan hệ với nhau, ngoài ra nếu lại biết "tổ chức" theo các cấu trúc thích hợp thì việc thực hiện các phép xử lý trên các dữ liệu sẽ càng thuận lợi hơn, đạt hiệu quả cao hơn. Với một cấu trúc dữ liệu đã chọn ta sẽ có giải thuật xử lý tương ứng. Cấu trúc dữ liệu thay đổi, giải thuật cũng thay đổi theo.

Note

Tóm lại, để giải quyết các bài toán trong lập trình chúng ta cần sử dụng các thuật toán để tác động lên các cấu trúc dữ liệu phù hợp. Thuật toán và cấu trúc dữ liệu là hai thành phần không thể tách rời để xây dựng chương trình. Đây là trọng tâm của khoá học này!

Trong bài tiếp theo, chúng ta sẽ đi chi tiết về hai khái niệm cấu trúc dữ liệu và thuật toán, cũng như các vấn đề đối với hai đối tượng này.