Link tải luận văn miễn phí cho ae Kết Nối
MỤC LỤC
PHẦN TỔNG QUAN ................................................. i
Chương 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT .......................... 1
1.1 TỔNG QUAN................................................................................................................... 1
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT....................................................... 2
1.3 THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT.............................................................. 2
1.4 TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT .......................................... 3
1.5 CÁCH TÍNH ÐỘ PHỨC TẠP.......................................................................................... 4
1.6 PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY............................................................. 7
1.7 TỔNG KẾT CHƯƠNG 1 ............................................................................................... 16
BÀI TẬP CHƯƠNG 1 ................................................................................................................. 16
Chương 2: SẮP XẾP ............................................. 18
2.1 TỔNG QUAN................................................................................................................. 18
2.2 BÀI TOÁN SẮP XẾP..................................................................................................... 19
2.3 CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN.............................................................. 20
2.4 QUICKSORT ................................................................................................................. 25
2.5 HEAPSORT.................................................................................................................... 31
2.6 BINSORT ....................................................................................................................... 39
2.7 TỔNG KẾT CHƯƠNG 2 ............................................................................................... 44
BÀI TẬP CHƯƠNG 2 ................................................................................................................. 44
Chương 3: KĨ THUẬT THIẾT KẾ GIẢI THUẬT ........................... 45
3.1 TỔNG QUAN................................................................................................................. 45
3.2 KĨ THUẬT CHIA ÐỂ TRỊ ............................................................................................. 45
3.3 KĨ THUẬT “THAM ĂN”............................................................................................... 50
3.4 QUY HOẠCH ÐỘNG .................................................................................................... 56
3.5 KĨ THUẬT QUAY LUI ................................................................................................. 63
3.6 KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG ........................................................................ 78
3.7 TỔNG KẾT CHƯƠNG 3 ............................................................................................... 82
BÀI TẬP CHƯƠNG 3 ................................................................................................................. 82
Chương 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI ......... 85
4.1 TỔNG QUAN................................................................................................................. 85
4.2 MÔ HÌNH XỬ LÝ NGOÀI............................................................................................ 85
4.3 ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI......................................................... 86
4.4 SẮP XẾP NGOÀI........................................................................................................... 87
4.5 LƯU TRỮ THÔNG TIN TRONG TẬP TIN ................................................................. 93
4.6 TỔNG KẾT CHƯƠNG 4 ............................................................................................. 103
BÀI TẬP CHƯƠNG 4 ............................................................................................................... 104Giả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â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 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiGiả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:
[7] Trang web bài giảng về giải thuật:
[8] Trang tìm kiếm các 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 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. AddisonWesley. 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:
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiGiải thuật Kĩ thuật phân tích giải thuật
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề
là cần đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông
thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
1.- Giải thuật đúng đắn.
2.- Giải thuật đơn giản.
3.- Giải thuật thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải
thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu
được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì
có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một
bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa
chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần được chứng
minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ
không đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là quan
trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có
được kết quả , thời gian thực hiện chương trình không được đề cao vì dù sao thì
chương trình đó cũng chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm
thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương
trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một
cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật.
1.3 THỜI GIAN THỰC HIỆN CỦA CHƯƠNG TRÌNH
Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là lập
trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định
đối với tập hợp được chọn lọc các dữ liệu vào.
Thời gian thực hiện không chỉ phụ thuộc vào giải thuật mà còn phụ thuộc vào tập
các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự
thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào
được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận
tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi
của giải thuật. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt
đối với sự phức tạp thời gian trong trường hợp xấu nhất.
1.3.1 Thời gian thực hiện chương trình.
Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký
hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Ví dụ 1-1: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c
là một hằng số.
1 B2 B3 B4 B5 BB6
Hình 4-3: Tập tin chỉ mục
4.5.4.2 Tìm kiếm
Ðể tìm mẩu tin r có khoá x, ta phải tìm cặp (z,p) với z là giá trị lớn nhất và z ≤ x.
Mẩu tin r có khoá x nếu tồn tại thì sẽ nằm trong khối được trỏ bởi p.
Chẳng hạn để tìm mẩu tin r có khoá 46 trong tập tin của ví dụ 4-6, ta tìm trong tập
tin chỉ mục được cặp (42, p), trong đó 42 là giá trị khoá lớn nhất trong tập tin chỉ
mục mà 42 ≤ 46 và p là con trỏ, trỏ tới khối B5 của tập tin chính. Trong khối B5, ta
tìm thấy mẩu tin có khoá 46.
Việc tìm một mẩu tin trong một khối của tập tin chính có thể tiến hành bằng tìm
kiếm tuần tự hay bằng tìm kiếm nhị phân bởi lẽ các mẩu tin trong một khối đã
được săp thứ tự.
4.5.4.3 Thêm mẩu tin
Giả sử tập tin chính được lưu trong các khối B1, B2, ..., Bm. Ðể xen một mẩu tin r
với khóa x vào trong tập tin, ta phải dùng thủ tục tìm kiếm để xác định một khối Bi
nào đó. Nếu tìm thấy thì thông báo “mẩu tin đã tồn tại”, ngược lại, Bi là nơi có thể
chứa mẩu tin r. Nếu Bi còn chỗ trống thì xen r vào đúng vị trí của nó trong Bi. Ta
phải chỉnh lại tập tin chỉ mục nếu mẩu tin mới trở thành mẩu tin đầu tiên trong khối
Bi. Nếu Bi không còn chỗ trống để xen thì ta phải xét khối Bi+1 để có thể chuyển
mẩu tin cuối cùng trong khối Bi thành mẩu tin đầu tiên của khối Bi+1 và xen mẩu tin
r vào đúng vị trí của nó trong khối Bi . Ðiều chỉnh lại tập tin chỉ mục cho phù hợp
với trạng thái mới của Bi+1. Quá trình này có thể dẫn đến việc ta phải xét khối Bm,
nếu Bm đã hết chỗ thì yêu cầu hệ thống cấp thêm một khối mới Bm+1, chuyển mẩu
tin cuối cùng của Bm sang Bm+1, mẩu tin cuối cùng của Bm-1 sang Bm… Xen mẩu tin
r vào khối Bi và cập nhật lại tập tin chỉ mục. Việc cấp phát thêm khối mới Bm+1 đòi
hỏi phải xen thêm một cặp khoá-con trỏ vào khối cuối cùng của tập tin chỉ mục, nếu
khối này hết chỗ thì xin cấp thêm một khối mới để xen cặp khóa-con trỏ này.
Ví dụ 4-7: Chẳng hạn ta cần xen mẩu tin r với khóa x = 24 vào trong tập tin được
biểu diễn trong hình 4-3. Thủ tục tìm x trong tập tin chỉ mục xác định được khối cần
xen r là khối B3. Vì khối B3 đã có đủ 3 mẩu tin nên phải xét khối B4. Khối B4 cũng
đã có đủ 3 mẩu tin nên ta lại xét khối B5. Vì B5 còn chỗ trống nên ta chuyển mẩu tin
có khoá 38 từ B4 sang B5 và chuyển mẩu tin có khóa 27 từ B3 sang B4 và xen r vào
khối B3. Vì mẩu tin đầu tiên của khối B4 bây giờ có khóa 27 nên ta phải sửa lại giá
trị này trong cặp của tập tin chỉ mục tương ứng với khối B4. Ta cũng phải làm tương
tự đối với khối B5. Cấu trúc của tập tin sau khi thêm mẩu tin r có khóa 24 như sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
PHẦN TỔNG QUAN ................................................. i
Chương 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT .......................... 1
1.1 TỔNG QUAN................................................................................................................... 1
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT....................................................... 2
1.3 THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT.............................................................. 2
1.4 TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT .......................................... 3
1.5 CÁCH TÍNH ÐỘ PHỨC TẠP.......................................................................................... 4
1.6 PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY............................................................. 7
1.7 TỔNG KẾT CHƯƠNG 1 ............................................................................................... 16
BÀI TẬP CHƯƠNG 1 ................................................................................................................. 16
Chương 2: SẮP XẾP ............................................. 18
2.1 TỔNG QUAN................................................................................................................. 18
2.2 BÀI TOÁN SẮP XẾP..................................................................................................... 19
2.3 CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN.............................................................. 20
2.4 QUICKSORT ................................................................................................................. 25
2.5 HEAPSORT.................................................................................................................... 31
2.6 BINSORT ....................................................................................................................... 39
2.7 TỔNG KẾT CHƯƠNG 2 ............................................................................................... 44
BÀI TẬP CHƯƠNG 2 ................................................................................................................. 44
Chương 3: KĨ THUẬT THIẾT KẾ GIẢI THUẬT ........................... 45
3.1 TỔNG QUAN................................................................................................................. 45
3.2 KĨ THUẬT CHIA ÐỂ TRỊ ............................................................................................. 45
3.3 KĨ THUẬT “THAM ĂN”............................................................................................... 50
3.4 QUY HOẠCH ÐỘNG .................................................................................................... 56
3.5 KĨ THUẬT QUAY LUI ................................................................................................. 63
3.6 KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG ........................................................................ 78
3.7 TỔNG KẾT CHƯƠNG 3 ............................................................................................... 82
BÀI TẬP CHƯƠNG 3 ................................................................................................................. 82
Chương 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI ......... 85
4.1 TỔNG QUAN................................................................................................................. 85
4.2 MÔ HÌNH XỬ LÝ NGOÀI............................................................................................ 85
4.3 ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI......................................................... 86
4.4 SẮP XẾP NGOÀI........................................................................................................... 87
4.5 LƯU TRỮ THÔNG TIN TRONG TẬP TIN ................................................................. 93
4.6 TỔNG KẾT CHƯƠNG 4 ............................................................................................. 103
BÀI TẬP CHƯƠNG 4 ............................................................................................................... 104Giả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â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 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiGiả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:
You must be registered for see links
[7] Trang web bài giảng về giải thuật:
You must be registered for see links
[8] Trang tìm kiếm các giải thuật:
You must be registered for see links
thuật Kĩ thuật phân tích giải thuậtCHƯƠ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 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. AddisonWesley. 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:
You must be registered for see links
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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phiGiải thuật Kĩ thuật phân tích giải thuật
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề
là cần đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông
thường thì ta sẽ căn cứ vào các tiêu chuẩn sau:
1.- Giải thuật đúng đắn.
2.- Giải thuật đơn giản.
3.- Giải thuật thực hiện nhanh.
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giải
thuật đó và cho thực hiện trên máy với một số bộ dữ liệu mẫu rồi lấy kết quả thu
được so sánh với kết quả đã biết. Thực ra thì cách làm này không chắc chắn bởi vì
có thể giải thuật đúng với tất cả các bộ dữ liệu chúng ta đã thử nhưng lại sai với một
bộ dữ liệu nào đó. Vả lại cách làm này chỉ phát hiện ra giải thuật sai chứ chưa
chứng minh được là nó đúng. Tính đúng đắn của giải thuật cần được chứng
minh bằng toán học. Tất nhiên điều này không đơn giản và do vậy chúng ta sẽ
không đề cập đến ở đây.
Khi chúng ta viết một chương trình để sử dụng một vài lần thì yêu cầu (2) là quan
trọng nhất. Chúng ta cần một giải thuật dễ viết chương trình để nhanh chóng có
được kết quả , thời gian thực hiện chương trình không được đề cao vì dù sao thì
chương trình đó cũng chỉ sử dụng một vài lần mà thôi.
Tuy nhiên khi một chương trình được sử dụng nhiều lần thì thì yêu cầu tiết kiệm
thời gian thực hiện chương trình lại rất quan trọng đặc biệt đối với những chương
trình mà khi thực hiện cần dữ liệu nhập lớn do đó yêu cầu (3) sẽ được xem xét một
cách kĩ càng. Ta gọi nó là hiệu quả thời gian thực hiện của giải thuật.
1.3 THỜI GIAN THỰC HIỆN CỦA CHƯƠNG TRÌNH
Một phương pháp để xác định hiệu quả thời gian thực hiện của một giải thuật là lập
trình nó và đo lường thời gian thực hiện của hoạt động trên một máy tính xác định
đối với tập hợp được chọn lọc các dữ liệu vào.
Thời gian thực hiện không chỉ phụ thuộc vào giải thuật mà còn phụ thuộc vào tập
các chỉ thị của máy tính, chất lượng của máy tính và kĩ xảo của người lập trình. Sự
thi hành cũng có thể điều chỉnh để thực hiện tốt trên tập đặc biệt các dữ liệu vào
được chọn. Ðể vượt qua các trở ngại này, các nhà khoa học máy tính đã chấp nhận
tính phức tạp của thời gian được tiếp cận như một sự đo lường cơ bản sự thực thi
của giải thuật. Thuật ngữ tính hiệu quả sẽ đề cập đến sự đo lường này và đặc biệt
đối với sự phức tạp thời gian trong trường hợp xấu nhất.
1.3.1 Thời gian thực hiện chương trình.
Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký
hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Ví dụ 1-1: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c
là một hằng số.
1 B2 B3 B4 B5 BB6
Hình 4-3: Tập tin chỉ mục
4.5.4.2 Tìm kiếm
Ðể tìm mẩu tin r có khoá x, ta phải tìm cặp (z,p) với z là giá trị lớn nhất và z ≤ x.
Mẩu tin r có khoá x nếu tồn tại thì sẽ nằm trong khối được trỏ bởi p.
Chẳng hạn để tìm mẩu tin r có khoá 46 trong tập tin của ví dụ 4-6, ta tìm trong tập
tin chỉ mục được cặp (42, p), trong đó 42 là giá trị khoá lớn nhất trong tập tin chỉ
mục mà 42 ≤ 46 và p là con trỏ, trỏ tới khối B5 của tập tin chính. Trong khối B5, ta
tìm thấy mẩu tin có khoá 46.
Việc tìm một mẩu tin trong một khối của tập tin chính có thể tiến hành bằng tìm
kiếm tuần tự hay bằng tìm kiếm nhị phân bởi lẽ các mẩu tin trong một khối đã
được săp thứ tự.
4.5.4.3 Thêm mẩu tin
Giả sử tập tin chính được lưu trong các khối B1, B2, ..., Bm. Ðể xen một mẩu tin r
với khóa x vào trong tập tin, ta phải dùng thủ tục tìm kiếm để xác định một khối Bi
nào đó. Nếu tìm thấy thì thông báo “mẩu tin đã tồn tại”, ngược lại, Bi là nơi có thể
chứa mẩu tin r. Nếu Bi còn chỗ trống thì xen r vào đúng vị trí của nó trong Bi. Ta
phải chỉnh lại tập tin chỉ mục nếu mẩu tin mới trở thành mẩu tin đầu tiên trong khối
Bi. Nếu Bi không còn chỗ trống để xen thì ta phải xét khối Bi+1 để có thể chuyển
mẩu tin cuối cùng trong khối Bi thành mẩu tin đầu tiên của khối Bi+1 và xen mẩu tin
r vào đúng vị trí của nó trong khối Bi . Ðiều chỉnh lại tập tin chỉ mục cho phù hợp
với trạng thái mới của Bi+1. Quá trình này có thể dẫn đến việc ta phải xét khối Bm,
nếu Bm đã hết chỗ thì yêu cầu hệ thống cấp thêm một khối mới Bm+1, chuyển mẩu
tin cuối cùng của Bm sang Bm+1, mẩu tin cuối cùng của Bm-1 sang Bm… Xen mẩu tin
r vào khối Bi và cập nhật lại tập tin chỉ mục. Việc cấp phát thêm khối mới Bm+1 đòi
hỏi phải xen thêm một cặp khoá-con trỏ vào khối cuối cùng của tập tin chỉ mục, nếu
khối này hết chỗ thì xin cấp thêm một khối mới để xen cặp khóa-con trỏ này.
Ví dụ 4-7: Chẳng hạn ta cần xen mẩu tin r với khóa x = 24 vào trong tập tin được
biểu diễn trong hình 4-3. Thủ tục tìm x trong tập tin chỉ mục xác định được khối cần
xen r là khối B3. Vì khối B3 đã có đủ 3 mẩu tin nên phải xét khối B4. Khối B4 cũng
đã có đủ 3 mẩu tin nên ta lại xét khối B5. Vì B5 còn chỗ trống nên ta chuyển mẩu tin
có khoá 38 từ B4 sang B5 và chuyển mẩu tin có khóa 27 từ B3 sang B4 và xen r vào
khối B3. Vì mẩu tin đầu tiên của khối B4 bây giờ có khóa 27 nên ta phải sửa lại giá
trị này trong cặp của tập tin chỉ mục tương ứng với khối B4. Ta cũng phải làm tương
tự đối với khối B5. Cấu trúc của tập tin sau khi thêm mẩu tin r có khóa 24 như sau:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: