Giới thiệu:
Trong chương trình Tin học mới 2018 của Bộ Giáo dục và Đào tạo, môn Tin học đã được bổ sung nội dung kiến thức Khoa học máy tính (CS) vào chương trình giáo dục phổ thông. Điều này tạo ra một cách thức mới và đặc biệt để giải quyết các vấn đề với sự trợ giúp của máy tính. Đây là một bước tiến quan trọng trong chương trình Tin học mới 2018 và các giáo viên và ngành giáo dục cần hiểu rõ những thay đổi đáng kể này.
Xu hướng mới trong giáo dục:
Trong chương trình Tin học mới, những kiến thức cơ bản nhất về Khoa học máy tính là Thuật toán và lập trình. Đây là những điểm nổi bật và mới mẻ trong chương trình Tin học mới của Chương trình Giáo dục Phổ thông 2018. Hiện tại, các sách tham khảo về định hướng này vẫn còn hiếm tại Việt Nam.
Cuốn sách nhằm mục đích hướng dẫn giáo viên và học sinh từ cấp THCS lớp 8 trở lên với nội dung cốt lõi của Khoa học máy tính trong nhà trường. Nội dung sách tập trung vào giảng dạy lý thuyết thuật toán cho học sinh. Dưới đây là tóm tắt nội dung quan trọng trong cuốn sách.
Nội dung sách:
Chương 1: Thuật toán là gì?
Chương này giới thiệu các khái niệm cơ bản liên quan đến thuật toán. Nội dung chính của chương là 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 của thuật toán. Điều này là mới mẻ đối với học sinh và giáo viên ở Việt Nam. Chương này cũng giới thiệu về định hướng Khoa học máy tính trong Chương trình Giáo dục Phổ thông 2018 và 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ỏ"
Chương này trình bày thiết kế một số thuật toán đơn giản tự nhiên như tìm kiếm và sắp xếp dãy số. Phân tích chi tiết độ phức tạp thời gian và không gian của từng thuật toán. Chương này cũng giới thiệu thuật toán tìm kiếm nhị phân trên dãy các phần tử đã sắp xếp và tính thời gian chạy của thuật toán này. Cuối chương, các thuật toán "tự nhiên" hay còn gọi là "trâu bò" được giới thiệu như công cụ chung để giải quyết mọi bài toán.
Chương 3: Đệ quy
Chương này 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. Chương này 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ị, để minh họa cho kỹ thuật đệ quy. Kỹ thuật đệ quy sẽ được sử dụng trong 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ị
Chương này mô tả phương pháp chia để trị, phương pháp quan trọng hay dùng cho thiết kế thuật toán. Chương này trình bày hai 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 đơn giản và dễ hiểu, trình bày như ví dụ cho việc thiết kế thuật toán bằng phương pháp chia để trị.
Chương 5: Tham lam
Chương này giới thiệu kỹ thuật tham lam, một kỹ thuật đặc thù và đơn giản để giải một lớp các bài toán tối ưu. Tham lam không phải lúc nào cũng cho lời giải tối ưu, nhưng cách tiếp cận tham lam 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 nhau. Chương này sử dụng kỹ thuật 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, v.v.
Chương 6: Quy hoạch động
Chương này giới thiệu phương pháp quy hoạch động là một phương pháp vô cùng nổi tiếng được áp dụng trong các bài toán tối ưu. Quy hoạch động là một phương pháp hoàn hảo để 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 được áp 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, v.v.
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 này giới thiệu một số cấu trúc dữ liệu cơ bản nhất 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 như mảng tuyến tính, ngăn xếp, hàng đợi, danh sách liên kết, heap, hàng đợi ưu tiên, cây, cây nhị phân và cây nhị phân tìm kiếm. Chương này đòi hỏi khá đầu tư từ học sinh cấp THCS, nhưng học sinh có thể bỏ qua phần này cho đến lần đọc sau.
Chương 8: Một vài thuật toán đơn giản trên đồ thị
Chương này giới thiệu cấu trúc dữ liệu đồ thị và một số thuật toán đơn giản nhất trên đồ thị. Chương này không đi sâu vào các bài toán nổi tiếng liên quan đến đồ thị, chỉ là một lời giới thiệu 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ị. Chương 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. Sau đó, 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) được trình bày. Cuối chương, thuật toán Dijkstra được giới thiệu để giải 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
Chương này giới thiệu kỹ thuật vét cạn quay lui, một kỹ thuật đặc biệt để 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. Kỹ thuật này là 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, v.v.
Cuối mỗi chương của sách đều có bài tập kèm theo, gồm hơn 300 bài tập từ dễ đến khó. Sách cũng bao gồm hai phụ lục: một về phân tích thời gian khấu hao và một liệt kê danh sách các thuật toán đã được mô tả trong sách.
Sách có thể được sử dụng cho 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, giúp nâng cao kiến thức và giảng dạy tốt hơn môn Tin học trong nhà trường phổ thông.
- Sách cho các học sinh giỏi cấp THCS và THPT muốn tự học và khám phá kiến thức mới của môn Khoa học máy tính trong chương trình Tin học mới.
- Sách dành cho các lớp chuyên Tin, luyện thi học sinh giỏi, đội tuyển - chuẩn bị thi học sinh giỏi Tin học theo hướng thuật toán.
Trong cuối sách, có phần đánh số trang và danh sách các tài liệu tham khảo với hơn 100 đầu mục.
Đó là những điểm nổi bật trong cuốn sách "Nhập Môn Thuật Toán". Sách có thể truy cập tại đây và đây.
Trân trọng giới thiệu...
