Hiện tại sách khoa học về tin học bằng tiếng Việt rất hiếm. Đa số là các sách hướng dẫn sử dụng phần mềm, kể cả việc dạy lập trình cũng chủ yếu dựa trên cơ sở một phần mềm biên dịch nào đó.
Tin học đã được phát triển dựa vào ngành Toán học, tất cả những lí luận của ngành này rất chặt chẽ dựa vào những nguyên lí toán học. Tin học trong quá trình phát triển cũng nảy sinh đặc thù riêng và những lí luận riêng đáp ứng công nghệ thực tế của nó. Đặc biệt khái niệm về thuật toán thì bất cứ một người học tin học nào cũng cần phải nắm vững.
Thuật toán đã được các nhà tin học phát triển và nghiên cứu khá kĩ, thuật toán có mặt trong mọi lĩnh vực của công nghệ. Nhưng cách thức người ta phân tích và thiết kế một thuật toán như thế nào thì không phải ai cũng hiểu thấu đáo. Cuốn sách này giới thiệu các vấn đề về thuật toán với độ phức tạp tính toán của nó. Để chứng minh và phân tích thuật toán một cách đúng đắn ta phải dùng một số công cụ toán học cơ bản như phương pháp chứng minh quy nạp toán học, phương pháp dùng hàm đánh giá O-lớn hoặc o-nhỏ, phương trình hồi quy, …và các kiến thức cơ bản của toán học rời rạc.
Cuốn sách này được biên soạn nhằm phục vụ cho các bạn yêu thích toán học ứng dụng và tin học, các bạn ở lớp chuyên toán, chuyên tin, các thầy cô giáo và những người quan tâm đến giáo dục toán học, tin học ở trường phổ thông cũng như đại học. Mỗi chương đều đi từ đơn giản đến phức tạp, mỗi khái niệm mới đều được định nghĩa trước khi vào bài tập. Xương sống trong lí luận của cuốn sách này, ngoài những định nghĩa cơ bản của các khái niệm, là phương pháp lập luận theo quy nạp toán học mà bạn đọc có thể xem trong cuốn sách riêng về chuyên đề này.
Chương 1 của cuốn sách hoàn toàn mang tính công cụ toán học. Những bài tập trong chương này rất hay về mặt toán học và nó còn tạo đà cho các chương sau chuyên về tin học. Chương 2 nói về tính đúng đắn của thuật toán và cách chứng minh tính đúng đắn đó cho các thuật toán quen thuộc. Những chương còn lại chỉ ra độ phức tạp tính toán của các thuật toán kết hợp với phương pháp thiết kế chúng như phương pháp chia để trị, phương pháp quy hoạch động, phương pháp tham, phương pháp quy lui, …. Việc chỉ ra độ phức tạp tính toán của các thuật toán còn cho ta hướng phân tích và thiết kế thuật toán một cách tối ưu nhất. Các thuật toán được thể hiện bằng ngôn ngữ giả mã gần như ngôn ngữ lập trình Pascal mà nhiều người đã quen thuộc. Các bước của mỗi thuật toán được đánh số theo dòng, những giải thích và lập luận đều dựa trên các số dòng này. Mỗi mục đều có những bài giải mẫu và sau đó là những bài tập. Những bài tập có thể có lời giải hoặc gợi ý hoặc bạn đọc phải suy ngẫm dựa trên các ví dụ đã giải.
Do thời gian biên soạn cuốn sách bị eo hẹp nên có thể còn vài sai sót, mong bạn đọc góp ý. Hơn nữa, còn nhiều vấn đề về thuật toán liên quan đến độ phức tạp tính toán của chúng không được trình bày ở đây. Xin hẹn trong một tài liệu khác, chúng tôi sẽ giới thiệu về các chuyên đề như thuật toán sắp xếp, tìm kiếm, thuật toán số học, các thuật toán trong lí thuyết đồ thị, … cùng các hàm thời gian tính toán của chúng và các chủ đề tính toán với thuật toán có độ phức tạp $P$, $NP$, $NP$ đầy đủ,…Trình bày và biên soạn cuốn sách bằng chương trình \LaTeX\ có cài dấu tiếng Việt do tác giả thực hiện[12].
Mọi góp ý gửi về địa chỉ: Ban biên tập sách Toán, Nhà xuất bản Giáo dục, 187B Giảng Võ, Hà Nội.
Tác giả cảm ơn ban biên tập Toán – Nhà xuất bản Giáo dục Hà Nội đã hết sức giúp đỡ để cuốn sách được in ra. Tác giả đặc biệt cảm ơn các đồng nghiệp ở Khoa Toán – Cơ – Tin học, ĐHKHTN, ĐHQGHN; Phòng Giải tích số và Tính toán Khoa học, Viện Toán học, đã giúp đỡ và động viên rất nhiều trong quá trình hoàn thành cuốn sách.
Hà Nội, tháng 09 năm 2005
Nguyễn Hữu Điển
2. Mục lục
Chương 1. Công cụ để phân tích và thiết kế thuật toán 1.1. Thuật toán và các tính chất của nó 1.1.1. Giả mã mô tả thuật toán 1.1.2. Một số ví dụ thuật toán 1.1.3. Thuật toán hồi quy 1.1.4. Bài toán tháp Hà Nội 1.2. Cấu trúc dữ liệu cơ sở 1.3. Phương pháp quy nạp toán học 1.4. Hàm đo độ tính toán 1.4.1. Định nghĩa và tính chất 1.4.2. Thứ bậc trong tập hàm số 1.4.3. Đánh giá một số tổng các số hạng 1.5. Phương trình hồi quy 1.6. Định lí cơ bản cho phân tích thuật toán 1.7. Bài tập
Chương 2. Tính đúng đắn của thuật toán 2.1. Giới thiệu kiểm chứng thuật toán 2.2. Thuật toán hồi quy 2.3. Tính đúng của thuật toán hồi quy 2.4. Tính đúng của thuật toán không hồi quy 2.5. Bài tập
Chương 3. Phân tích độ phức tạp thuật toán 3.1. Đánh giá thuật toán qua phép toán thực hiện 3.2. Xác định độ phức tạp tính toán 3.3. Độ phức tạp của thuật toán 3.4. Phân tích độ phức tạp thuật toán không hồi quy 3.5. Phân tích thuật toán hồi quy 3.6. Bài tập
Chương 4. Phương pháp chia để trị 4.1. Thuật toán sắp xếp trộn 4.1.1. Thiết kế thuật toán 4.1.2. Phân tích thuật toán 4.2. Thuật toán nhân hai ma trận 4.2.1. Cách tiếp cận chia để trị 4.2.2. Cách nhân hai ma trận của Strassen 4.2.3. Những thuật toán dựa trên phương pháp Strassen 4.3. Nhân những số nguyên lớn 4.3.1. Phương pháp nhân nhanh hai số nguyên 4.3.2. Thuật toán nhân hai số nguyên 4.4. Tính toán kí hiệu trên những đa thức 4.4.1. Nhân hai đa thức cùng bậc 4.4.2. Nhân hai đa thức khác bậc 4.5. Chọn phần tử nhỏ bất kì 4.5.1. Thuật toán lựa chọn 4.5.2. Thuật toán chọn với trục điểm giữa 4.6. Một ứng dụng cho xếp lịch thi đấu thể thao 4.7. Bài tập
Chương 5. Phương pháp quy hoạch động 5.1. Giới thiệu phương pháp quy hoạch động 5.1.1. Ví dụ so sánh với phương pháp chia để trị 5.1.2. Một số vấn đề trong phương pháp quy hoạch động 5.1.3. Kĩ thuật lập thuật toán theo quy hoạch động 5.2. Bài toán nhân ma trận 5.2.1. Giới thiệu bài toán 5.2.2. Thiết kế thuật toán theo cách chia để trị 5.2.3. Thiết kế theo quy hoạch động 5.3. Ghi nhớ hóa và tam giác hóa 5.3.1. Ghi nhớ hóa 5.3.2. Đa giác và tam giác hóa 5.4. Dãy con chung dài nhất 5.5. Đường đi ngắn nhất 5.5.1. Nhắc lại một số khái niệm trong lí thuyết đồ thị 5.5.2. Đường đi ngắn nhất giữa hai cặp đỉnh 5.5.3. Thuật toán Floyd 5.5.4. Thuật toán Warshall 5.6. Bài toán đường đi của người bán hàng 5.7. Bài tập
Chương 6. Phương pháp tham 6.1. Lập chương trình cho nhiều hoạt động 6.1.1. Thuật toán tham lập lịch hoạt động 6.1.2. Tính đúng đắn của thuật toán 6.2. Mã Huffman 6.2.1. Phân tích và thiết kế thuật toán 6.2.2. Chứng minh tính đúng đắn của thuật toán 6.3. Bài toán ba lô 6.4. Bài toán cây bao trùm nhỏ nhất và thuật toán 6.4.1. Cây bao trùm nhỏ nhất 6.4.2. Tiếp cận thuật toán tìm cây bao trùm nhỏ nhất 6.5. Thuật toán Kruskal
Chương 7. Thuật toán quay lui 7.1. Thuật toán quay lui với chuỗi nhị phân 7.1.1. Những chuỗi bit 7.1.2. Bài toán ba lô 7.1.3. Chu trình Hamilton 7.1.4. Đường đi của người bán hàng 7.2. Thuật toán quay lui với những phép hoán vị 7.2.1. Sinh những hoán vị 7.2.2. Chu trình Hamilton với đồ thị dày đặc 7.2.3. Bài toán quân hậu hòa bình 7.3. Thuật toán quay lui với những tổ hợp 7.3.1. Sinh tổ hợp 7.3.2. Chứng minh tính đúng đắn của thuật toán 7.3.3. Phân tích thuật toán 7.3.4. Tính tối ưu của thuật toán 7.4. Bài tập
Description:
1. Lời giới thiệu
Hiện tại sách khoa học về tin học bằng tiếng Việt rất hiếm. Đa số là các sách hướng dẫn sử dụng phần mềm, kể cả việc dạy lập trình cũng chủ yếu dựa trên cơ sở một phần mềm biên dịch nào đó.
Tin học đã được phát triển dựa vào ngành Toán học, tất cả những lí luận của ngành này rất chặt chẽ dựa vào những nguyên lí toán học. Tin học trong quá trình phát triển cũng nảy sinh đặc thù riêng và những lí luận riêng đáp ứng công nghệ thực tế của nó. Đặc biệt khái niệm về thuật toán thì bất cứ một người học tin học nào cũng cần phải nắm vững.
Thuật toán đã được các nhà tin học phát triển và nghiên cứu khá kĩ, thuật toán có mặt trong mọi lĩnh vực của công nghệ. Nhưng cách thức người ta phân tích và thiết kế một thuật toán như thế nào thì không phải ai cũng hiểu thấu đáo. Cuốn sách này giới thiệu các vấn đề về thuật toán với độ phức tạp tính toán của nó. Để chứng minh và phân tích thuật toán một cách đúng đắn ta phải dùng một số công cụ toán học cơ bản như phương pháp chứng minh quy nạp toán học, phương pháp dùng hàm đánh giá O-lớn hoặc o-nhỏ, phương trình hồi quy, …và các kiến thức cơ bản của toán học rời rạc.
Cuốn sách này được biên soạn nhằm phục vụ cho các bạn yêu thích toán học ứng dụng và tin học, các bạn ở lớp chuyên toán, chuyên tin, các thầy cô giáo và những người quan tâm đến giáo dục toán học, tin học ở trường phổ thông cũng như đại học. Mỗi chương đều đi từ đơn giản đến phức tạp, mỗi khái niệm mới đều được định nghĩa trước khi vào bài tập. Xương sống trong lí luận của cuốn sách này, ngoài những định nghĩa cơ bản của các khái niệm, là phương pháp lập luận theo quy nạp toán học mà bạn đọc có thể xem trong cuốn sách riêng về chuyên đề này.
Chương 1 của cuốn sách hoàn toàn mang tính công cụ toán học. Những bài tập trong chương này rất hay về mặt toán học và nó còn tạo đà cho các chương sau chuyên về tin học. Chương 2 nói về tính đúng đắn của thuật toán và cách chứng minh tính đúng đắn đó cho các thuật toán quen thuộc. Những chương còn lại chỉ ra độ phức tạp tính toán của các thuật toán kết hợp với phương pháp thiết kế chúng như phương pháp chia để trị, phương pháp quy hoạch động, phương pháp tham, phương pháp quy lui, …. Việc chỉ ra độ phức tạp tính toán của các thuật toán còn cho ta hướng phân tích và thiết kế thuật toán một cách tối ưu nhất. Các thuật toán được thể hiện bằng ngôn ngữ giả mã gần như ngôn ngữ lập trình Pascal mà nhiều người đã quen thuộc. Các bước của mỗi thuật toán được đánh số theo dòng, những giải thích và lập luận đều dựa trên các số dòng này. Mỗi mục đều có những bài giải mẫu và sau đó là những bài tập. Những bài tập có thể có lời giải hoặc gợi ý hoặc bạn đọc phải suy ngẫm dựa trên các ví dụ đã giải.
Do thời gian biên soạn cuốn sách bị eo hẹp nên có thể còn vài sai sót, mong bạn đọc góp ý. Hơn nữa, còn nhiều vấn đề về thuật toán liên quan đến độ phức tạp tính toán của chúng không được trình bày ở đây. Xin hẹn trong một tài liệu khác, chúng tôi sẽ giới thiệu về các chuyên đề như thuật toán sắp xếp, tìm kiếm, thuật toán số học, các thuật toán trong lí thuyết đồ thị, … cùng các hàm thời gian tính toán của chúng và các chủ đề tính toán với thuật toán có độ phức tạp $P$, $NP$, $NP$ đầy đủ,…Trình bày và biên soạn cuốn sách bằng chương trình \LaTeX\ có cài dấu tiếng Việt do tác giả thực hiện[12].
Mọi góp ý gửi về địa chỉ: Ban biên tập sách Toán, Nhà xuất bản Giáo dục, 187B Giảng Võ, Hà Nội.
Tác giả cảm ơn ban biên tập Toán – Nhà xuất bản Giáo dục Hà Nội đã hết sức giúp đỡ để cuốn sách được in ra. Tác giả đặc biệt cảm ơn các đồng nghiệp ở Khoa Toán – Cơ – Tin học, ĐHKHTN, ĐHQGHN; Phòng Giải tích số và Tính toán Khoa học, Viện Toán học, đã giúp đỡ và động viên rất nhiều trong quá trình hoàn thành cuốn sách.
Hà Nội, tháng 09 năm 2005
Nguyễn Hữu Điển
2. Mục lục
Chương 1. Công cụ để phân tích và thiết kế thuật toán
1.1. Thuật toán và các tính chất của nó
1.1.1. Giả mã mô tả thuật toán
1.1.2. Một số ví dụ thuật toán
1.1.3. Thuật toán hồi quy
1.1.4. Bài toán tháp Hà Nội
1.2. Cấu trúc dữ liệu cơ sở
1.3. Phương pháp quy nạp toán học
1.4. Hàm đo độ tính toán
1.4.1. Định nghĩa và tính chất
1.4.2. Thứ bậc trong tập hàm số
1.4.3. Đánh giá một số tổng các số hạng
1.5. Phương trình hồi quy
1.6. Định lí cơ bản cho phân tích thuật toán
1.7. Bài tập
Chương 2. Tính đúng đắn của thuật toán
2.1. Giới thiệu kiểm chứng thuật toán
2.2. Thuật toán hồi quy
2.3. Tính đúng của thuật toán hồi quy
2.4. Tính đúng của thuật toán không hồi quy
2.5. Bài tập
Chương 3. Phân tích độ phức tạp thuật toán
3.1. Đánh giá thuật toán qua phép toán thực hiện
3.2. Xác định độ phức tạp tính toán
3.3. Độ phức tạp của thuật toán
3.4. Phân tích độ phức tạp thuật toán không hồi quy
3.5. Phân tích thuật toán hồi quy
3.6. Bài tập
Chương 4. Phương pháp chia để trị
4.1. Thuật toán sắp xếp trộn
4.1.1. Thiết kế thuật toán
4.1.2. Phân tích thuật toán
4.2. Thuật toán nhân hai ma trận
4.2.1. Cách tiếp cận chia để trị
4.2.2. Cách nhân hai ma trận của Strassen
4.2.3. Những thuật toán dựa trên phương pháp Strassen
4.3. Nhân những số nguyên lớn
4.3.1. Phương pháp nhân nhanh hai số nguyên
4.3.2. Thuật toán nhân hai số nguyên
4.4. Tính toán kí hiệu trên những đa thức
4.4.1. Nhân hai đa thức cùng bậc
4.4.2. Nhân hai đa thức khác bậc
4.5. Chọn phần tử nhỏ bất kì
4.5.1. Thuật toán lựa chọn
4.5.2. Thuật toán chọn với trục điểm giữa
4.6. Một ứng dụng cho xếp lịch thi đấu thể thao
4.7. Bài tập
Chương 5. Phương pháp quy hoạch động
5.1. Giới thiệu phương pháp quy hoạch động
5.1.1. Ví dụ so sánh với phương pháp chia để trị
5.1.2. Một số vấn đề trong phương pháp quy hoạch động
5.1.3. Kĩ thuật lập thuật toán theo quy hoạch động
5.2. Bài toán nhân ma trận
5.2.1. Giới thiệu bài toán
5.2.2. Thiết kế thuật toán theo cách chia để trị
5.2.3. Thiết kế theo quy hoạch động
5.3. Ghi nhớ hóa và tam giác hóa
5.3.1. Ghi nhớ hóa
5.3.2. Đa giác và tam giác hóa
5.4. Dãy con chung dài nhất
5.5. Đường đi ngắn nhất
5.5.1. Nhắc lại một số khái niệm trong lí thuyết đồ thị
5.5.2. Đường đi ngắn nhất giữa hai cặp đỉnh
5.5.3. Thuật toán Floyd
5.5.4. Thuật toán Warshall
5.6. Bài toán đường đi của người bán hàng
5.7. Bài tập
Chương 6. Phương pháp tham
6.1. Lập chương trình cho nhiều hoạt động
6.1.1. Thuật toán tham lập lịch hoạt động
6.1.2. Tính đúng đắn của thuật toán
6.2. Mã Huffman
6.2.1. Phân tích và thiết kế thuật toán
6.2.2. Chứng minh tính đúng đắn của thuật toán
6.3. Bài toán ba lô
6.4. Bài toán cây bao trùm nhỏ nhất và thuật toán
6.4.1. Cây bao trùm nhỏ nhất
6.4.2. Tiếp cận thuật toán tìm cây bao trùm nhỏ nhất
6.5. Thuật toán Kruskal
Chương 7. Thuật toán quay lui
7.1. Thuật toán quay lui với chuỗi nhị phân
7.1.1. Những chuỗi bit
7.1.2. Bài toán ba lô
7.1.3. Chu trình Hamilton
7.1.4. Đường đi của người bán hàng
7.2. Thuật toán quay lui với những phép hoán vị
7.2.1. Sinh những hoán vị
7.2.2. Chu trình Hamilton với đồ thị dày đặc
7.2.3. Bài toán quân hậu hòa bình
7.3. Thuật toán quay lui với những tổ hợp
7.3.1. Sinh tổ hợp
7.3.2. Chứng minh tính đúng đắn của thuật toán
7.3.3. Phân tích thuật toán
7.3.4. Tính tối ưu của thuật toán
7.4. Bài tập
Tài liệu tham khảo