Nhập môn thuật toán

GIỚI THIỆU SÁCH NHẬP MÔN THUẬT TOÁN

Cuốn sách này được viết hướng đến người đọc là giáo viên và học sinh từ cấp THCS lớp 8 trở lên theo nội dung lõi của định hướng khoa học máy tính trong nhà trường: Thuật toán. Đây có lẽ là cuốn sách đầu tiên được viết theo hướng này với kiến thức nhập môn lý thuyết thuật toán dành cho lứa tuổi học sinh. Sau đây là tóm tắt nội dung sách.

Nội dung cuốn sách bao gồm các chương kiến thức sau:

Chương 1. Thuật toán là gì.

Chương 2. Tìm kiếm và sắp xếp. Thuật toán trâu bò.

Chương 3. Đệ quy.

Chương 4. Chia để trị.

Chương 5. Tham lam.

Chương 6. Quy hoạch động.

Chương 7. Một số cấu trúc dữ liệu cơ bản. Cấu trúc cây. Cây nhị phân tìm kiếm.

Chương 8. Một vài thuật toán đơn giản trên đồ thị.

Chương 9. Kỹ thuật duyệt vét cạn quay lui.

Chương 1, Thuật toán là gì, sẽ trình bày các khái niệm cơ bản và đơn giản nhất liên quan đến khái niệm thuật toán: định nghĩa, đặc tính, các tính chất cơ bản của thuật toán. Nội dung chính của chương này là phần trình bày quy trình thiết kế và mô tả thuật toán thông qua pseudocode, cách chứng minh và đánh giá độ phức tạp thuật toán. Tất cả những kiến thức này đều là rất mới với đối tượng là học sinh và giáo viên các nhà trường phổ thông tại Việt Nam. Cũng trong chương này sẽ trình bày sơ lược về định hướng phân môn khoa học máy tính trong Chương trình GDPT 2018 mới, phân biệt các khái niệm cơ bản như tư duy máy tính, tư duy thuật toán và tư duy STEM.

Chương 2, Tìm kiếm và sắp xếp. Thuật toán tự nhiên, "trâu bò", trình bày thiết kế một số thuật toán đơn giản, tự nhiên như các bài toán tìm kiếm, sắp xếp dãy. Với mỗi thuật toán đều có phân tích chi tiết độ phức tạp thời gian và không gian của thuật toán. Trong chương này cũng trình bày một thuật toán "nâng cao" là tìm kiếm nhị phân trên một dãy tuyến tính các phần tử đã sắp xếp và tính thời gian chạy chính xác của thuật toán này. Phần cuối chương giới thiệu một lớp các thuật toán "tự nhiên" hay còn gọi là các thuật toán "trâu bò" như một công cụ chung để giải bất kỳ bài toán nào.

Chương 3, Đệ quy, sẽ giới thiệu kỹ thuật lập trình đệ quy, một kỹ thuật quan trọng trong lập trình và thiết kế thuật toán. Để minh họa cho kỹ thuật đệ quy trong chương này sẽ trình bày một số bài toán mẫu như bài toán tháp Hà Nội, bài toán sinh hoán vị, Kỹ thuật đệ quy sẽ được sử dụng trong suốt phần còn lại của cuốn sách để mô tả các thuật toán điển hình.

Chương 4, Chia để trị, sẽ trình bày một phương pháp, hay kỹ thuật quan trọng nhất hay dùng cho thiết kế thuật toán. Có thể nói chia để trị là phương pháp trung tâm của hầu hết các thuật toán cổ điển, quen thuộc được mô tả trong các sách kinh điển về thuật toán. Trong chương này sẽ trình bày 2 thuật toán chia để trị cơ bản là thuật toán sắp xếp trộn và thuật toán sắp xếp nhanh. Các thuật toán này khá đơn giản, dễ hiểu và có thể được trình bày như những ví dụ ban đầu của việc thiết kế thuật toán bằng kỹ thuật chia để trị.

Chương 5, Tham lam, sẽ giới thiệu kỹ thuật, hay chiến lược tham lam, một kỹ thuật đặc thù, đơn giản để giải một lớp các bài toán tối ưu. Không phải bài toán nào sử dụng tham lam cũng cho lời giải tối ưu, tuy nhiên cách tiếp cận tham lam, nhìn chung, có thể coi là một cách tiếp cận gần đúng khá tốt để giải nhiều bài toán tối ưu khác. Trong chương này sẽ sử dụng chiến lược tham lam giải một số bài toán điển hình như bài toán đổi tiền, bài toán xếp ba lô, bài toán xếp lịch,

Chương 6, Quy hoạch động, giới thiệu phương pháp quy hoạch động là một phương pháp, kỹ thuật vô cùng nổi tiếng được áp dụng rất nhiều trong các bài toán tối ưu. Khác với tham lam, quy hoạch động là một phương pháp hoàn hảo có thể dùng để tìm ra lời giải tối ưu cho rất nhiều dạng bài toán khác nhau. Trong chương này, phương pháp quy hoạch động sẽ được dùng để giải một số bài toán nổi tiếng như bài toán đổi tiền, bài toán xếp ba lô, bài toán người gác rừng, bài toán tìm dãy con đơn điệu tăng cực đại,

Chương 7, Một số cấu trúc dữ liệu cơ bản. Cấu trúc cây. Cây nhị phân tìm kiếm, là một chương đệm mô tả một số cấu trúc dữ liệu cơ bản nhất sẽ được học trong chương trình môn Tin học mới. Đó là các cấu trúc dữ liệu đơn giản sau:

- Cấu trúc mảng tuyến tính (một hoặc 2 chiều).

- Cấu trúc ngăn xếp (stack) và hàng đợi (queue).

- Cấu trúc danh sách liên kết (linked list).

- Cấu trúc đống (heap) và hàng đợi ưu tiên (priority queue).

- Cấu trúc cây, cây nhị phân và cây nhị phân tìm kiếm.

Chú ý: Kiến thức phần này có thể là hơi khó với học sinh cấp THCS, do vậy học sinh thấy khó có thể bỏ qua ở lần đọc đầu tiên.

Chương 8, Một vài thuật toán đơn giản trên đồ thị, sẽ mô tả cấu trúc dữ liệu đồ thị và một số thuật toán đơn giản nhất trên đồ thị. Trong chương này sẽ không đi sâu vào các bài toán nổi tiếng liên quan đến đồ thị mà chỉ là một nhập môn ngắn về mô hình đồ thị và một số bài toán, thuật toán đơn giản nhất trên đồ thị. Phần đầu của chương sẽ giới thiệu mô hình toán học của lý thuyết đồ thị và mô hình dữ liệu chính mô tả các đồ thị đơn vô hướng hoặc có hướng. Phần tiếp theo sẽ mô tả các thuật toán duyệt đồ thị cơ bản bao gồm duyệt theo chiều sâu (DFS) và duyệt theo chiều rộng (BFS). Trong sách sẽ đề xuất một mô hình duyệt tổng quát gọi là duyệt theo cái túi (TFS) là một tổng quát hóa của DFS và BFS. Phần cuối của chương sẽ sử dụng BFS để giải bài toán tìm đường đi ngắn nhất trên đồ thị. Phần kết thúc của chương sẽ trình bày thuật toán Dijkstra cho bài toán tìm đường đi ngắn nhất trên đồ thị có trọng số không âm.

Chương 9, Kỹ thuật duyệt vét cạn quay lui, sẽ giới thiệu nhanh một kỹ thuật đặc biệt dùng để giải một lớp các bài toán khó mà chưa tìm ra các thuật toán tốt hoặc không thể có thuật toán tốt. Đó là thuật toán, hay kỹ thuật vét cạn quay lui (backtracking). Kỹ thuật này là một công cụ tốt để giải một lớp các bài toán khó như bài toán tìm đường đi trong mê cung, bài toán xếp hậu, bài toán mã tuần, bài toán người gác rừng,

Cuối mỗi chương của sách đều có bài tập kèm theo. Trong sách có hơn 300 bài tập từ dễ đến khó phân bổ đều theo tất cả các chương. Phần cuối sách sẽ có 2 phụ lục, một phụ lục về phân tích thời gian khấu hao và một phụ lục liệt kê danh sách các thuật toán đã mô tả trong sách.

Cuối cùng là phần Chỉ số và danh sách các tài liệu tham khảo với hơn 100 đầu mục.

Cuốn sách này có thể được dùng trong các trường hợp sau:

- Sách tham khảo dành cho giáo viên tin học các trường THCS và THPT dùng để nâng cao kiến thức, giúp giáo viên dạy tốt hơn môn Tin học trong nhà trường phổ thông.

- Sách dành cho các em học sinh giỏi cấp THCS và THPT muốn tự học và khám phá những kiến thức mới mẻ của phân môn khoa học máy tính trong chương trình Tin học mới.

- Sách có thể dùng cho các lớp chuyên tin, luyện thi học sinh giỏi, cho các đội tuyển chuẩn bị thi học sinh giỏi Tin học theo hướng thuật toán.

Giá sản phẩm trên Tiki đã bao gồm thuế theo luật hiện hành. Bên cạnh đó, tuỳ vào loại sản phẩm, hình thức và địa chỉ giao hàng mà có thể phát sinh thêm chi phí khác như phí vận chuyển, phụ phí hàng cồng kềnh, thuế nhập khẩu (đối với đơn hàng giao từ nước ngoài có giá trị trên 1 triệu đồng).....