Cẩm nang thuật toán – Tập 1 – Các thuật toán thông dụng

Nội dung chính của sách:

• Mục tiêu: Tổng hợp có hệ thống các phương pháp cơ bản, từ nhiều lĩnh vực ứng dụng riêng biệt, nhằm cung cấp các giải thuật tốt nhất đã được kiểm chứng và công bố để giải các bài toán cụ thể bằng máy tính.
• Đối tượng: Sinh viên ngành Tin học, những người đã quen với máy tính và có kỹ năng lập trình (ít nhất là Pascal chuẩn), các thầy cô và học sinh các trường Trung học chuyên Tin, cũng như cán bộ nghiên cứu ngành khác hoặc những người có nhu cầu phát triển phần mềm hệ thống hay ứng dụng.
• Cấu trúc: Gồm 45 chương, chia thành 8 phần. Tập 1 (tập này) gồm 23 chương thuộc bốn phần đầu của nguyên bản, tập trung vào “Các thuật toán thông dụng”. Tập 2 sẽ xuất bản sau, gồm 22 chương thuộc bốn phần cuối, tập trung vào “Các thuật toán chuyên dụng”.
• Ngôn ngữ lập trình: Sử dụng Pascal để trình bày và cài đặt hầu hết các thuật toán, nhưng các chương trình có thể dễ dàng chuyển đổi sang các ngôn ngữ lập trình hiện đại khác do chỉ sử dụng một tập con tương đối nhỏ của ngôn ngữ.
• Các phần chính được giới thiệu trong Tập 1:
  • Cơ sở: Các công cụ và phương pháp cơ bản, giới thiệu về Pascal, các cấu trúc dữ liệu cơ bản (mảng, xâu liên kết, ngăn xếp, hàng đợi, cây), đệ quy, và cách tiếp cận phân tích, cài đặt thuật toán.
  • Sắp xếp: Các phương pháp sắp xếp tệp theo thứ tự, bao gồm hàng đợi ưu tiên, phép chọn và phép trộn.
  • Tìm kiếm: Các phương pháp tìm kiếm cơ bản và nâng cao sử dụng cây và phép biến đổi khóa số (cây tìm kiếm nhị phân, cây cân bằng, phép băm, cây tìm kiếm số, trie), và các phương pháp cho tệp lớn.
  • Xử lý chuỗi: Các phương pháp phân tích câu, kỹ thuật nén tập tin và mật mã.
  • Hình học: Các phương pháp giải quyết bài toán liên quan đến điểm và đường (bao lồi, giao giữa các đối tượng hình học, bài toán điểm gần nhất, tìm kiếm nhiều chiều).
  • Đồ thị: Các thuật toán giải quyết bài toán khó và quan trọng trên đồ thị (liên thông cơ bản, đường đi ngắn nhất, cây liên thông tối thiểu, mạng, so khớp).
  • Toán học: Các phương pháp cơ bản từ số học và giải tích số (số nguyên, đa thức, ma trận, tạo số ngẫu nhiên, giải phương trình đồng thời, xấp xỉ dữ liệu, lấy tích phân).
  • Các chủ đề cao cấp: Liên hệ các chất liệu trong sách với các lĩnh vực nghiên cứu cao cấp khác (phần cứng chuyên dụng, quy hoạch động, quy hoạch tuyến tính, tìm kiếm vét cạn, vấn đề NP-đầy đủ).
• Các cấu trúc dữ liệu cơ bản được thảo luận chi tiết:
  • Mảng (array): Cấu trúc cơ bản nhất, gồm các mẫu dữ liệu cố định được chứa liên tục và truy xuất bằng chỉ mục.
  • Xâu liên kết (linked list): Ưu điểm là có thể co giãn kích thước, linh hoạt trong việc tổ chức lại phần tử. Được định nghĩa bằng các nút chứa dữ liệu và liên kết đến nút kế tiếp. Có các thao tác cơ bản như chèn, xóa.
  • Ngăn xếp đẩy xuống (pushdown stack): Cấu trúc truy xuất hạn chế với hai thao tác cơ bản: cất (push) một phần tử lên ngăn xếp (chèn ở đầu) và lấy (pop) một phần tử (loại bỏ khỏi đầu). Tuân theo quy luật LIFO (Last In, First Out).
  • Hàng đợi (queue): Cấu trúc truy xuất hạn chế với hai thao tác cơ bản: chèn (insert) một phần tử vào đầu và lấy đi (remove) một phần tử ở cuối. Tuân theo quy luật FIFO (First In, First Out).
  • Cây (tree): Cấu trúc liên kết hai chiều, bao gồm các đỉnh (nút) và các cạnh. Có nhiều loại cây như cây nhị phân, cây nhị phân đầy đủ. Các khái niệm liên quan: gốc, cha, con, nút lá/tận cùng, nút không tận cùng, tầng, chiều cao, độ dài đường đi.

Cuốn sách nhấn mạnh tầm quan trọng của thuật toán và cấu trúc dữ liệu trong tin học, cung cấp các ví dụ cài đặt bằng Pascal và khuyến khích người đọc thực hành để hiểu sâu hơn. Nó cũng bàn về việc quản lý bộ nhớ và khái niệm kiểu dữ liệu trừu tượng.