Cấu trúc dữ liệu và giải thuật

1. Cấu trúc dữ liệu và giải thuật (Chương 1):

• Mối quan hệ: Giải thuật và cấu trúc dữ liệu có mối quan hệ mật thiết, như “hình với bóng”. Việc lựa chọn cấu trúc dữ liệu phù hợp sẽ ảnh hưởng trực tiếp đến hiệu quả của giải thuật xử lý.
• Các vấn đề liên quan:
  • Dữ liệu nguyên tử và cấu trúc dữ liệu: Dữ liệu bao gồm các phần tử cơ sở (nguyên tử) và cách chúng liên kết tạo nên các cấu trúc khác nhau. Việc chọn cấu trúc dữ liệu thích hợp là rất quan trọng cho việc xây dựng giải thuật hiệu quả.
  • Phép toán trên cấu trúc dữ liệu: Các cấu trúc dữ liệu mới, đặc biệt trong các bài toán phi số, đi kèm với các phép toán mới (tạo lập, hủy bỏ, truy cập, bổ sung, loại bỏ). Hiệu quả của phép toán phụ thuộc vào cấu trúc được chọn.
  • Cấu trúc lưu trữ: Là cách biểu diễn cấu trúc dữ liệu trong bộ nhớ (lưu trữ trong hoặc ngoài). Cần phân biệt cấu trúc dữ liệu và cấu trúc lưu trữ vì có thể có nhiều cấu trúc lưu trữ cho cùng một cấu trúc dữ liệu, hoặc ngược lại.
  • Cấu trúc dữ liệu tiền định: Các ngôn ngữ lập trình thường có các cấu trúc dữ liệu tiền định (ví dụ: mảng trong PASCAL) nhưng không phải lúc nào cũng đáp ứng mọi yêu cầu. Người lập trình cần linh hoạt vận dụng hoặc tự định nghĩa cấu trúc.
• Ngôn ngữ diễn đạt giải thuật: Sách sử dụng “ngôn ngữ tựa PASCAL” để diễn đạt giải thuật, nhằm tránh sự gò bó về cú pháp của các ngôn ngữ cấp cao và thể hiện đầy đủ ý tưởng về cấu trúc dữ liệu.

2. Thiết kế và phân tích giải thuật (Chương 2):

• Thiết kế giải thuật:
  • Mô-đun hóa và chiến thuật “chia để trị”: Phân chia bài toán lớn thành các bài toán nhỏ hơn (mô-đun con) để đơn giản hóa việc giải quyết.
  • Thiết kế “từ đỉnh xuống” (top-down design): Bắt đầu từ cái nhìn tổng quát về vấn đề, sau đó đi sâu vào các phần cụ thể.
  • Phương pháp tinh chỉnh từng bước (stepwise refinement): Phát triển giải thuật từ ngôn ngữ tự nhiên, qua giả ngôn ngữ (pseudo code), đến ngôn ngữ lập trình, dần dần chi tiết hóa các bước xử lý và cấu trúc dữ liệu. Minh họa bằng ví dụ sắp xếp dãy số và in các đường chéo của ma trận.
• Phân tích giải thuật:
  • Đặt vấn đề: Phân tích tính đúng đắn, tính đơn giản của giải thuật. Quan trọng hơn là đánh giá hiệu quả về thời gian và bộ nhớ, đặc biệt với các chương trình được sử dụng nhiều lần và xử lý khối lượng dữ liệu lớn.
  • Phân tích thời gian thực hiện giải thuật:
    • Độ phức tạp về thời gian (ký hiệu O lớn): Đánh giá thời gian thực hiện giải thuật độc lập với máy tính và các yếu tố liên quan đến máy. Thể hiện bằng các hàm như log₂n, n, nlog₂n, n², n³, 2ⁿ, n!, nⁿ. Các hàm loại đa thức thường được chấp nhận, các hàm loại mũ thì rất chậm.
    • Xác định độ phức tạp: Sử dụng quy tắc tổng (O(max(f(n), g(n)))) và quy tắc nhân (O(f(n)g(n))). Phân tích bằng cách đếm số lần thực hiện các “phép toán tích cực” (active operation).
    • Độ phức tạp về thời gian trung bình: Thời gian thực hiện giải thuật có thể phụ thuộc vào tình trạng dữ liệu vào. Cần xét trường hợp thuận lợi nhất, xấu nhất và trung bình. Việc xác định trung bình thường khó và đôi khi người ta đánh giá qua giá trị xấu nhất.

3. Giải thuật đệ quy (Chương 3):

• Khái niệm về đệ quy: Một đối tượng là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc được định nghĩa dưới dạng của chính nó.
• Giải thuật đệ quy và thủ tục đệ quy: Lời giải của bài toán T được thực hiện bằng lời giải của một bài toán T’ có dạng giống T nhưng “nhỏ hơn”.
  • Đặc điểm:
    1. Chứa lời gọi đến chính nó.
    2. Kích thước bài toán thu nhỏ hơn sau mỗi lần gọi.
    3. Có trường hợp suy biến (degenerate case) được giải quyết theo cách khác, kết thúc quá trình đệ quy.
  • Đệ quy có thể trực tiếp hoặc gián tiếp.
• Thiết kế giải thuật đệ quy: Thuận lợi khi bài toán hoặc dữ liệu được định nghĩa dưới dạng đệ quy. Cần trả lời các câu hỏi: định nghĩa bài toán nhỏ hơn như thế nào, kích thước bài toán giảm ra sao, và trường hợp suy biến là gì.
  • Ví dụ:
    • Hàm n!: Định nghĩa n! = n * (n-1)! với trường hợp suy biến 0! = 1.
    • Dãy số Fibonacci: Định nghĩa F(n) = F(n-2) + F(n-1) với trường hợp suy biến F(1)=1, F(2)=1.
    • Bài toán “Tháp Hà Nội”: Chuyển n đĩa được giải quyết bằng cách chuyển (n-1) đĩa, sau đó chuyển đĩa thứ n, rồi lại chuyển (n-1) đĩa. Trường hợp suy biến là chuyển 1 đĩa.
    • Bài toán 8 quân hậu và giải thuật quay lui (backtracking): Tìm vị trí cho từng quân hậu sao cho không quân nào ăn được nhau. Nếu một lựa chọn không an toàn, quay lui về bước trước để thử các lựa chọn khác. Bài toán con là giải quyết vị trí cho các quân hậu còn lại.
• Hiệu lực của đệ quy: Là một công cụ mạnh mẽ, đôi khi dễ nghĩ ra lời giải hơn giải thuật lặp. Đệ quy còn cho phép xác định một tập vô hạn các đối tượng bằng một phát biểu hữu hạn.
• Đệ quy và quy nạp toán học: Có mối quan hệ chặt chẽ. Quy nạp toán học được dùng để chứng minh tính đúng đắn của giải thuật đệ quy, ví dụ như chứng minh tính đúng đắn của hàm FACTORIAL và đánh giá số lần di chuyển đĩa trong bài toán Tháp Hà Nội.