Kỹ thuật giải thuật trong lập trình và ứng dụng
Th.s. NGUYỄN VĂN LINH
GIẢI THUẬT
Được biên soạn trong khuôn khổ dự án ASVIET002CNTT
”Tăng cường hiệu quả đào tạo và năng lực tự đào tạo của sinh viên
khoa Công nghệ Thông tin - Đại học Cần thơ”
ĐẠI HỌC CẦN THƠ - 12/2003
LỜI NÓI ÐẦU
N. Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn
ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông là
“Cấu trúc dữ liệu + Giải thuật = Chương trình”.
Ðiều đó nói lên tầm quan trọng của giải thuật trong lập trình nói
riêng và trong khoa học máy tính nói chung. Vì lẽ đó giải thuật, với tư
cách là một môn học, cần phải được sinh viên chuyên ngành tin học
nghiên cứu một cách có hệ thống.
Môn học “Giải thuật” được bố trí sau môn “Cấu trúc dữ liệu”
trong chương trình đào tạo kỹ sư tin học nhằm giới thiệu cho sinh viên
những kiến thức cơ bản nhất, những kỹ thuật chủ yếu nhất của việc
PHÂN TÍCH và THIẾT KẾ giải thuật. Các kỹ thuật được trình bày ở
đây đã được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt
các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh
viên khi phải giải quyết một vấn đề thực tế.
Giáo trình này được hình thành trên cơ sở tham khảo cuốn sách
“Data Structure and Algorithms” của A.V Aho, những kinh nghiệm
giảng dạy của bản thân và các bạn đồng nghiệp.
Mặc dù đã có nhiều cố gắng trong quá trình biên soạn nhưng chắc
chắn còn nhiều thiếu sót, rất mong nhận được sự đóng góp của quý bạn
đọc.
Cần thơ, ngày 8 tháng 12 năm 2003
Nguyễn Văn Linh
Giải thuật Mục lục
MỤC LỤC
................................................. i PHẦN TỔNG QUAN
.......................... 1 Chương 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT
1.1 ................................................................................................................... 1 TỔNG QUAN
1.2 ....................................................... 2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT
1.3 .............................................................. 2 THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT
1.4 .......................................... 3 TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT
1.5 .......................................................................................... 4 CÁCH TÍNH ÐỘ PHỨC TẠP
1.6 ............................................................. 7 PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY
1.7 ............................................................................................... 16 TỔNG KẾT CHƯƠNG 1
................................................................................................................. 16 BÀI TẬP CHƯƠNG 1
............................................. 18 Chương 2: SẮP XẾP
2.1 ................................................................................................................. 18 TỔNG QUAN
2.2 ..................................................................................................... 19 BÀI TOÁN SẮP XẾP
2.3 .............................................................. 20 CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN
2.4 ................................................................................................................. 25 QUICKSORT
2.5 .................................................................................................................... 31 HEAPSORT
2.6 ....................................................................................................................... 39 BINSORT
2.7 ............................................................................................... 44 TỔNG KẾT CHƯƠNG 2
................................................................................................................. 44 BÀI TẬP CHƯƠNG 2
........................... 45 Chương 3: KĨ THUẬT THIẾT KẾ GIẢI THUẬT
3.1 ................................................................................................................. 45 TỔNG QUAN
3.2 ............................................................................................. 45 KĨ THUẬT CHIA ÐỂ TRỊ
3.3 ............................................................................................... 50 KĨ THUẬT “THAM ĂN”
3.4 .................................................................................................... 56 QUY HOẠCH ÐỘNG
3.5 ................................................................................................. 63 KĨ THUẬT QUAY LUI
3.6 ........................................................................ 78 KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG
3.7 ............................................................................................... 82 TỔNG KẾT CHƯƠNG 3
................................................................................................................. 82 BÀI TẬP CHƯƠNG 3
......... 85 Chương 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI
4.1 ................................................................................................................. 85 TỔNG QUAN
4.2 ............................................................................................ 85 MÔ HÌNH XỬ LÝ NGOÀI
4.3 ......................................................... 86 ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI
4.4 ........................................................................................................... 87 SẮP XẾP NGOÀI
4.5 ................................................................. 93 LƯU TRỮ THÔNG TIN TRONG TẬP TIN
4.6 ............................................................................................. 103 TỔNG KẾT CHƯƠNG 4
............................................................................................................... 104 BÀI TẬP CHƯƠNG 4
Giải thuật Tổng quan
PHẦN TỔNG QUAN
1. Mục đích yêu cầu
Môn học giải thuật cung cấp cho sinh viên một khối lượng kiến thức tương đối
hoàn chỉnh về phân tích và thiết kế các giải thuật lập trình cho máy tính. Sau khi
học xong môn học này, sinh viên cần:
- Nắm được khái niệm thời gian thực hiện của chương trình, độ phức tạp của
giải thuật. Biết cách phân tích, đánh giá giải thuật thông qua việc tính độ
phức tạp.
- Nắm được các giải thuật sắp xếp và phân tích đánh giá được các giải thuật
sắp xếp.
- Nắm được các kĩ thuật thiết kế giải thuật, vận dụng vào việc giải một số bài
toán thực tế.
- Nắm được các phương pháp tổ chức lưu trữ thông tin trong tập tin và các giải
thuật tìm, xen, xoá thông tin trong tập tin.
2. Đối tượng sử dụng
Môn học giải thuật được dùng để giảng dạy cho các sinh viên sau:
- Sinh viên năm thứ 3 chuyên ngành Tin học.
- Sinh viên năm thứ 3 chuyên ngành Điện tử (Viễn thông, Tự động hoá…)
- Sinh viên Toán-Tin.
3. Nội dung cốt lõi
Trong khuôn khổ 45 tiết, giáo trình được cấu trúc thành 4 chương
- Chương 1: Kĩ thuật phân tích đánh giá giải thuật. Chương này đặt vấn đề tại
sao cần phải phân tích, đánh giá giải thuật và phân tích đánh giá theo phương
pháp nào. Nội dung chương 1 tập trung vào khái niệm độ phức tạp thời gian
của giải thuật và phương pháp tính độ phức tạp giải thuật của một chương
trình bình thường, của chương trình có gọi các chương trình con và của các
chương trình đệ quy.
- Chương 2: Sắp xếp. Chương này trình bày các giải thuật sắp xếp, một thao
tác thường được sử dụng trong việc giải các bài toán máy tính. Sẽ có nhiều
giải thuật sắp xếp từ đơn giản đến nâng cao sẽ được giới thiệu ở đây. Với
mỗi giải thuật, sẽ trình bày ý tưởng giải thuật, ví dụ minh hoạ, cài đặt chương
trình và phân tích đánh giá.
- Chương 3: Kĩ thuật thiết kế giải thuật. Chương này trình bày các kĩ thuật
phổ biến để thiết kế các giải thuật. Các kĩ thuật này gồm: Chia để trị, Quy
hoạch động, Tham ăn, Quay lui và Tìm kiếm địa phương. Với mỗi kĩ thuật sẽ
trình bày nội dung kĩ thuật và vận dung vào giải các bài toán khá nổi tiếng
như bài toán người giao hàng, bài toán cái ba lô, bài toán cây phủ tối thiểu...
- Chương 4: Cấu trúc dữ liệu và giải thuật lưu trữ ngoài. Chương này trình
bày các cấu trúc dữ liệu được dùng để tổ chức lưu trữ tập tin trên bộ nhớ
ngoài và các giải thuật tìm kiếm, xen xoá thông tin trên các tập tin đó.
4. Kiến thức tiên quyết
Để học tốt môn học giải thuật cần phải có các kiến thức sau:
- Kiến thức toán học.
- Kiến thức và kĩ năng lập trình căn bản.
Giải thuật Tổng quan
- Kiến thức về cấu trúc dữ liệu và các giải thuật thao tác trên các cấu trúc dữ
liệu.
Trong chương trình đào tạo, Cấu trúc dữ liệu là môn học tiên quyết của môn Giải
thuật.
5. Danh mục tài liệu tham khảo
[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman; Data Structures and Algorithms;
Addison-Wesley; 1983.
[2] Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley;
1998.
[3] Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học
và kĩ thuật; Hà nội-2001.
[4] Đỗ Xuân Lôi; Cấu trúc dữ liệu & Giải thuật; 1995.
[5] Nguyễn Đức Nghĩa, Tô Văn Thành; Toán rời rạc; 1997.
[6] Trang web phân tích giải thuật: http://pauillac.inria.fr/algo/AofA/
[7] Trang web bài giảng về giải thuật:
http://www.cs.pitt.edu/~kirk/algorithmcourses/
[8] Trang tìm kiếm các giải thuật:
http://oopweb.com/Algorithms/Files/Algorithms.html
Giải thuật Kĩ thuật phân tích giải thuật
CHƯƠNG 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT
1.1 TỔNG QUAN
1.1.1 Mục tiêu
Sau khi học chương này, sinh viên cần phải trả lời được các câu hỏi sau:
- Tại sao cần phân tích đánh giá giải thuật?
- Tiêu chuẩn nào để đánh giá một giải thuật là tốt?
- Phương pháp đánh giá như thế nào? (đánh giá chương trình không gọi
chương trình con, đánh giá một chương trình có gọi các chương trình con
không đệ quy và đánh giá chương trình đệ quy).
1.1.2 Kiến thức cơ bản cần thiết
Các kiến thức cơ bản cần thiết để học chương này bao gồm:
- Kiến thức toán học: Công thức tính tổng n số tự nhiên đầu tiên, công thức
tính tổng n số hạng đầu tiên của một cấp số nhân, phương pháp chứng minh
quy nạp và các kiến thức liên quan đến logarit (biến đổi logarit, tính chất
đồng biến của hàm số logarit).
- Kĩ thuật lập trình và lập trình đệ quy.
1.1.3 Tài liệu tham khảo
A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-
Wesley. 1983. (Chapters 1, 9).
Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 1998.
(Chapter 2).
Đinh Mạnh Tường. Cấu trúc dữ liệu & Thuật toán. Nhà xuất bản khoa học và kĩ
thuật. Hà nội-2001. (Chương 1).
Trang web phân tích giải thuật: http://pauillac.inria.fr/algo/AofA/
1.1.4 Nội dung cốt lõi
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau:
• Sự cần thiết phải phân tích các giải thuật.
• Thời gian thực hiện của chương trình.
• Tỷ suất tăng và độ phức tạp của giải thuật.
• Tính thời gian thực hiện của chương trình.
• Phân tích các chương trình đệ quy.
Nguyễn Văn Linh Trang 1
có thể bạn quan tâm
Nghiên cứu, đánh giá các giải thuật đối sánh chuỗi. Trên cơ sở đó lựa...
25
1.075
555
Thạc sĩ cao học
25
(New)
Nghiên cứu về chữ kí số và ứng dụng trong hóa đơn điện tử tại VNPT Hà...
23
726
481
Thạc sĩ cao học
23
(New)
Khái niệm phân tập và kỹ thuật phân tập đa người dùng, kỹ thuật OFDM,...
62
817
599
Kỹ thuật
62
(New)
Các thủ thuật giúp máy tình không bị nóng trong quá trình sử dụng
6
670
214
Tài liệu CNTT khác
6
(New)
Luận văn thạc sĩ: Một số thuật toán mã hóa khác ứng dụng trong bảo mật...
26
1.165
296
Thạc sĩ cao học
26
(New)
nghệ thuật trần thuật trong những đứa con trong gia đình
6
2.694
726
Giáo án, bài giảng lớp 12
6
(New)
Tìm hiểu về thuật toán và thuật giải
97
2.150
442
Cơ sở dữ liệu
97
(New)
Kỹ thuật phân tích giải thuật
7
945
324
Lập trình
7
(New)
thông tin tài liệu
Tìm hiểu rõ hơn về các kỹ thuật giải thuật trong quá trình lập trình
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Giáo trình Quản trị học của Đại học kinh tế quốc dân
Tâm lý xã hội VÀ Hệ tư tưởng
Mẫu slide chủ đề âm nhạc
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
Các hiệu ứng HTML cho trang web
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
