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 để…