VieTeX

Chương trình soạn thảo TeX

Sách: Một số vấn đề về thuật toán

Posted by nhdien on 15/08/2009

Một số vấn đề về thuật toán

thuattoan

Nhà xuất bản GD
Năm xuất bản: 2006
Khổ sách: 17×24
Số trang: 323
Lấy về tại đây

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 [11].

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 của sách

  Chương   1.    Công cụ để phân tích và    thiết    kế    thuật    toán  5
1.1.  Thuật toán và các tính chất của nó   5
1.1.1.  Giả mã mô tả thuật toán   6
1.1.2.  Một số ví dụ thuật toán   9
1.1.3.  Thuật toán hồi quy   14
1.1.4.  Bài toán tháp Hà Nội   16
1.2.  Cấu trúc dữ liệu cơ sở   18
1.3.  Phương pháp quy nạp toán học   23
1.4.  Hàm đo độ tính toán   29
1.4.1.  Định nghĩa và tính chất   29
1.4.2.  Thứ bậc trong tập hàm số   34
1.4.3.  Đánh giá một số tổng các số hạng   39
1.5.  Phương trình hồi quy   40
1.6.  Định lí cơ bản cho phân tích thuật toán   49
1.7.  Bài tập   51

  Chương   2.    Tính đúng đắn của thuật toán  53
2.1.  Giới thiệu kiểm chứng thuật toán   53
2.2.  Thuật toán hồi quy   55
2.3.  Tính đúng của thuật toán hồi quy   56
2.4.  Tính đúng của thuật toán không hồi quy   60
2.5.  Bài tập   66

  Chương   3.    Phân tích độ phức tạp thuật toán  69
3.1.  Đánh giá thuật toán qua phép toán thực hiện   70
3.2.  Xác định độ phức tạp tính toán   71
3.3.  Độ phức tạp của thuật toán   75
3.4.  Phân tích độ phức tạp thuật toán không hồi quy   80
3.5.  Phân tích thuật toán hồi quy   83
3.6.  Bài tập   88

  Chương   4.    Phương pháp chia để trị  90
 4.1.  Thuật toán sắp xếp trộn   91
4.1.1.  Thiết kế thuật toán   92
4.1.2.  Phân tích thuật toán   95
4.2.  Thuật toán nhân hai ma trận   98
4.2.1.  Cách tiếp cận chia để trị   99
4.2.2.  Cách nhân hai ma trận của Strassen   100
4.2.3.  Những thuật toán dựa trên phương pháp Strassen   104
4.3.  Nhân những số nguyên lớn   107
4.3.1.  Phương pháp nhân nhanh hai số nguyên   107
4.3.2.  Thuật toán nhân hai số nguyên   109
4.4.  Tính toán kí hiệu trên những đa thức   111
4.4.1.  Nhân hai đa thức cùng bậc   112
4.4.2.  Nhân hai đa thức khác bậc   115
4.5.  Chọn phần tử nhỏ bất kì   116
4.5.1.  Thuật toán lựa chọn   116
4.5.2.  Thuật toán chọn với trục điểm giữa   120
4.6.  Một ứng dụng cho xếp lịch thi đấu thể thao   124
4.7.  Bài tập   130

  Chương   5.    Phương pháp quy hoạch động  132
5.1.  Giới thiệu phương pháp quy hoạch động   133
5.1.1.  Ví dụ so sánh với phương pháp chia để trị   133
5.1.2.  Một số vấn đề trong phương pháp quy hoạch động   137
5.1.3.  Kĩ thuật lập thuật toán theo quy hoạch động   138
5.2.  Bài toán nhân ma trận   140
5.2.1.  Giới thiệu bài toán   140
5.2.2.  Thiết kế thuật toán theo cách chia để trị   142
5.2.3.  Thiết kế theo quy hoạch động   144
5.3.  Ghi nhớ hóa và tam giác hóa   150
5.3.1.  Ghi nhớ hóa   150
5.3.2.  Đa giác và tam giác hóa   151
5.4.  Dãy con chung dài nhất   157
5.5.  Đường đi ngắn nhất   162
5.5.1.  Nhắc lại một số khái niệm trong lí thuyết đồ thị   162
5.5.2.  Đường đi ngắn nhất giữa hai cặp đỉnh   163
5.5.3.  Thuật toán Floyd   164
5.5.4.  Thuật toán Warshall   167
5.6.  Bài toán đường đi của người bán hàng   168
5.7.  Bài tập   173

  Chương   6.    Phương pháp tham  174
6.1.  Lập chương trình cho nhiều hoạt động   176
6.1.1.  Thuật toán tham lập lịch hoạt động   177
6.1.2.  Tính đúng đắn của thuật toán   179
6.2.  Mã Huffman   180
6.2.1.  Phân tích và thiết kế thuật toán   181
6.2.2.  Chứng minh tính đúng đắn của thuật toán   184
6.3.  Bài toán ba lô   187
6.4.  Bài toán cây bao trùm nhỏ nhất và thuật toán   192
6.4.1.  Cây bao trùm nhỏ nhất   192
6.4.2.  Tiếp cận thuật toán tìm cây bao trùm nhỏ nhất   193
6.5.  Thuật toán Kruskal   196

  Chương   7.    Thuật toán quay lui  199
7.1.  Thuật toán quay lui với chuỗi nhị phân   200
7.1.1.  Những chuỗi bit   200
7.1.2.  Bài toán ba lô   205
7.1.3.  Chu trình Hamilton   206
7.1.4.  Đường đi của người bán hàng   210
7.2.  Thuật toán quay lui với những phép hoán vị   212
7.2.1.  Sinh những hoán vị   212
7.2.2.  Chu trình Hamilton với đồ thị dày đặc   216
7.2.3.  Bài toán quân hậu hòa bình   217
7.3.  Thuật toán quay lui với những tổ hợp   219
7.3.1.  Sinh tổ hợp   219
7.3.2.  Chứng minh tính đúng đắn của thuật toán   220
7.3.3.  Phân tích thuật toán   222
7.3.4.  Tính tối ưu của thuật toán   224
7.4.  Bài tập   226

Tài liệu tham khảo  227
Mục lục  228

Lấy về tại đây

2 Responses to “Sách: Một số vấn đề về thuật toán”

  1. Sang said

    Cảm ơn thầy rất nhiều về cuốn sách quý này. Em đang học cấu trúc dữ liệu và giải thuật. Ở nha trang kiếm sách thật khó. Cấu trúc dữ liệu của Nguyễn Hồng Chuơng kết hợp với cuốn này của thầy thì quá tuyệt. Hì!

  2. nguyen dai hai said

    thua thay! em co the mua sach o dau ah? ngoai ra thay co the gioi thieu cho em mot so sach ve thuat toan ko ah? em cam on thay

    Trả lời
    Cuốn thuật toán mới tái bản, vì hồi đầu năm tôi vừa sửa xong. Không biết họ in đã đưa ra hiệu sách chưa. Có nhiều sách thuật toán nhưng không viết theo kiểu phân tích như của tôi. Bận tự suy luận lấy. Bạn tìm trên mạng cũng có nhiều.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: