Python: Thuật toán & Cấu trúc dữ liệu. Bài tập và lời giải. Volume 1.

Đây là cuốn sách đầu tiên về chủ đề bài tập thuật toán và cấu trúc dữ liệu trên Python. Trong sách có hơn 400 bài tập với lời giải chi tiết hướng đến đối tượng là học sinh, giáo viên cấp THPT và sinh viên năm đầu ngành Khoa học máy tính trong các trường đại học.

 Như chúng ta đã biết, chương trình Giáo dục phổ thông mới 2018 đã có những thay đổi rất lớn, mang tính cách mạng, đặc biệt với môn Tin học. Sau đây là một vài điểm cơ bản quan trọng nhất của sự thay đổi này.

- Tin học trở thành môn học bắt buộc trong chương trình giáo dục phổ thông, từ lớp 3 đến lớp 12.

- Tin học không còn là môn học mang tính thực hành, ứng dụng thuần túy nữa. Tin học trong chương trình Giáo dục phổ thông mới vừa có tính thực hành, vừa là môn học trang bị kiến thức tối thiểu hành trang số, đồng thời Tin học sẽ là môn học có tính khoa học chặt chẽ, liên thông và có tính liên môn sâu sắc. Điều này được chứng minh bởi tính kết hợp chặt chẽ và nhuần nhuyễn, hòa quyện giữa 3 mạch kiến thức CS (khoa học máy tính), ICT (ứng dụng) và DL (học vấn số hóa phổ thông).

- Lần đầu tiên học sinh được tiếp cận lập trình ngay từ cấp Tiểu học. Ngôn ngữ lập trình Scratch được học sinh làm quen ngay từ bậc Tiểu học và THCS. Đây có thể coi là một cuộc cách mạng trong việc dạy tư duy máy tính và lập trình cho học sinh tromg nhà trường phổ thông.

- Ngôn ngữ Python được đưa vào dạy cho cấp THPT, chính thức chấm dứt cho hơn 2 thập kỷ dạy Pascal trong nhà trường phổ thông. Việc đưa Python vào nhà trường phổ thông thay thế cho Pascal là một quyết định dũng cảm của Bộ GD&ĐT, thay đổi này sẽ làm thay đổi tình trạng trì trệ của môn Tin học trước đây, mang lại sinh khí mới cho môn Tin học trong nhà trường phổ thông.

- Với cấp THPT, lần đầu tiên các khái niệm, kiến thức cơ bản của khoa học máy tính, cấu trúc dữ liệu, thuật toán được đưa vào giảng dạy chính thức. Và Python sẽ là ngôn ngữ chính thức dùng để minh họa cho các kiến thức tuy hàn lâm nhưng rất hấp dẫn này.

Cuốn sách này ra đời nhằm đáp ứng nhu cầu tìm hiểu thêm về định hướng khoa học máy tính, cấu trúc dữ liệu, thuật toán trong chương trình môn Tin học cấp THPT. Tuy nhiên cuốn sách đã được viết với mục đích không chỉ gói gọn trong chương trình Giáo dục phổ thông 2018, mà còn được mở rộng lớn hơn cho khối các lớp chuyên tin, thậm chí cho các sinh viên các trường đại học.

Có hai lý do cho sự ra đời của cuốn sách này:

1. Cho đến hiện nay tại Việt Nam chưa có cuốn sách nào thuộc dạng tuyển tập Bài tập + Lời giải cho phần kiến thức thuật toán, cấu trúc dữ liệu bằng tiếng Việt cho học sinh và sinh viên. Một phần do chủ đề này được coi là rất khó, một lý do khác là có rất ít đối tượng quan tâm đến chủ đề khoa học này.
2. Từ trước đến nay, khi nói về cấu trúc dữ liệu, thuật toán, hay lập trình thi đấu, hầu như tất cả mọi người đều chỉ nghĩ đến các ngôn ngữ như C, C++, Pascal hay Java, chưa thấy nhắc đến Python. Thực tế này không chỉ đúng ở Việt Nam, mà còn đúng trên phạm vi thế giới. Chính vì vậy, sau khi Python trở thành ngôn ngữ chính thức dạy trong nhà trường phổ thông thì nhu cầu về một cuốn sách như thế này là rất cấp thiết.

Cũng nhân tiện ra mắt cuốn sách này tôi muốn nhấn mạnh thêm một ý rất quan trọng sau: Khá nhiều giáo viên, học sinh, sinh viên, kể cả một số chuyên gia CNTT đều có suy nghĩ rằng các ngôn ngữ dạng biên dịch như C, Pascal là phù hợp hơn để dạy về thuật toán. Nhưng theo quan sát của tôi thì Python mới thực sự là ngôn ngữ tốt nhất để dạy về thuật toán và cấu trúc dữ liệu vì tính đơn giản, trong sáng của ngôn ngữ này. Python có rất nhiều đặc điểm phù hợp một cách kỳ lạ với các cách mô tả thuật toán tự nhiên bằng mã giả (pseudocode).

Cuốn sách "Python: Thuật toán & Cấu trúc dữ liệu. Bài tập và lời giải" được viết thành hai tập: Volume 1 và Volume 2. Từ nay chúng ta sẽ viết tắt tên cuốn sách này là PTC cho thuận tiện tham khảo.

Tập 1 của cuốn sách bao gồm các chương kiến thức sau:

Chương 1. Ngôn ngữ lập trình Python.

Chương 2. Khái niệm thuật toán.

Chương 3. Mảng một chiều và mảng hai chiều.

Chương 4. Thuật toán sắp xếp và tìm kiếm đơn giản.

Chương 5. Đệ quy.

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

Chương 7. Kỹ thuật duyệt quay lui.

Chương 8. Chiến lược tham lam.

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

Hầu hết phần kiến thức chính định hướng CS của chương trình môn Tin học lớp 11 đều nằm trong cuốn sách này.

Dự kiến tập 2 của cuốn sách sẽ có các kiến thức tiếp theo như sau:

- Các cấu trúc dữ liệu tuyến tính (ngăn xếp, hàng đợi, danh sách liên kết).

- Kỹ thuật băm và ứng dụng băm trong giải toán.

- Một số thuật toán sắp xếp nâng cao.

- Một số cấu trúc dữ liệu nâng cao (hàng đợi ưu tiên, tập hợp rời, cây phân đoạn).

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

- Đồ thị, cấu trúc, biểu diễn, các thuật toán duyệt đồ thị.

- Một số thuật toán trên đồ thị.

Sau đây là mô tả chi tiết hơn về cuốn sách PTC. Volume 1.

- Sách được chia thành các chuyên mục kiến thức, mỗi chương có thể có các mục kiến thức con. Mỗi mục kiến thức sẽ bao gồm các bài tập và lời giải chi tiết kèm theo. Chúng tôi lựa chọn cách trình bày mô tả lời giải ngay sau mỗi bài tập.

- Không phải tất cả các bài tập đều có lời giải. Có một số rất ít các bài tập, hoặc là rất đơn giản, hoặc là có tính tương tự cao của các bài tập đã giải ở phía trên thì các bài tập này được đưa vào dạng "Bài tập thêm" và không có lời giải. Tất cả các bài tập thêm này đều có kích thước chữ nhỏ hơn khuôn dạng chữ bình thường.

- Khác biệt với nhiều cuốn sách dạng Bài tập – Lời giải khác, và đây cũng là điểm khác biệt quan trọng giữa cuốn sách này và các cuốn sách khác là tất cả các lời giải bài tập đều rất chi tiết, có thể có đủ các cấu thành đặc trưng cho các bài toán thuật toán tin học: phân tích thiết kế, mô tả thuật toán hay chương trình, chứng minh tính đúng của thuật toán hay chương trình, phân tích độ phức tạp thời gian và không gian của thuật toán.

- Một đặc điểm rất quan trọng nữa của các bài tập tin học đã được cập nhật ngay trong cuốn sách này, đó là tính "đa lời giải". Thông thường mỗi bài toán tin học sẽ có rất nhiều cách giải, lời giải khác nhau, áp dụng theo các hướng và kỹ thuật lập trình khác nhau. Có rất nhiều bài tập trong sách được giải với nhiều cách khác nhau. Đây là tính năng rất đặc biệt của cuốn sách này.

- Phần cuối sách là các phụ lục chính bao gồm:

+ Các hàm có sẵn của Python.

+ Thứ tự ưu tiên thực hiện các phép toán trong Python.

+ Các Định lý Cơ bản (Master Theorems) tính bậc tiệm cận của công thức hồi quy.

+ Phương pháp thiết kế làm mịn dần và thiết kế theo mô đun.

Đặc biệt trong phụ lục cuối cùng, chúng tôi biên dịch, viết lại các ý chính của bài báo rất nổi tiếng của nhà khoa học máy tính Thụy Sĩ Niklaus Wirth, người sáng lập ngôn ngữ Pascal. Trong một bài báo viết năm 1971, Niklaus Wirth là người đầu tiên đưa ra khái niệm "Thiết kế chương trình theo phương pháp làm mịn dần", vào thời kỳ đó đây là một ý tưởng đột phá trong lập trình. Chính khái niệm Thiết kế theo phương pháp làm mịn dần đã được đưa vào chương trình môn Tin học cấp THPT, định hướng CS trong SGK Tin học lớp 11.

- Cuối cùng là phần Chỉ số và Tài liệu tham khảo.

Chú ý một chút về ký hiệu: Do hiện nay chưa có sự thống nhất hoàn toàn các ký hiệu, thuật ngữ của khoa học máy tính với toán học, trong cuốn sách này tôi sẽ sử dụng thống nhất một số ký hiệu sau:

[a, b], [a, b), (a, b], (a, b) sẽ chỉ các khoảng đóng, mở giữa 2 số trên trục số.

A[i : j] sẽ ký hiệu dãy con của mảng A từ chỉ số i đến chỉ số j – 1. A[i j] sẽ ký hiệu dãy con của mảng A tính từ chỉ số i đến chỉ số j.

Hy vọng cuốn sách mới sẽ đáp ứng được nhu cầu của rất nhiều giáo viên, học sinh trong các trường phổ thông đang học và dạy theo chương trình môn Tin học mới. Sách hoàn toàn có thể đáp ứng nhu cầu học tập, tham khảo dành cho học sinh các trường chuyên và sinh viên các trường đại học.

Cuốn sách này nằm trong Tủ sách CS4S và là cuốn tiếp theo của mạch kiến thức "Thuật toán", "Lập trình Python".

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).....