Chuyen de BD HSG 1

MỤC LỤC
MỤC LỤC 1
§0. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC 3
I. XÁC ĐỊNH BÀI TOÁN 3
II. TÌM CẤU TRÚC DỮ LIỆU BIỂU DIỄN BÀI TOÁN 3
III. TÌM THUẬT TOÁN 4
IV. LẬP TRÌNH 5
V. KIỂM THỬ 6
VI. TỐI ƯU CHƯƠNG TRÌNH 6
§1. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT 8
I. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT 8
II. XÁC ĐỊNH ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT 8
V. ĐỘ PHỨC TẠP TÍNH TOÁN VỚI TÌNH TRẠNG DỮ LIỆU VÀO 10
VI. CHI PHÍ THỰC HIỆN THUẬT TOÁN 11
§2. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY 12
I. KHÁI NIỆM VỀ ĐỆ QUY 12
II. GIẢI THUẬT ĐỆ QUY 12
III. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY 12
IV. HIỆU LỰC CỦA ĐỆ QUY 15
§3. CẤU TRÚC DỮ LIỆU BIỂU DIỄN DANH SÁCH 17
I. KHÁI NIỆM DANH SÁCH 17
II. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH 17
§4. NGĂN XẾP VÀ HÀNG ĐỢI 21
I. NGĂN XẾP (STACK) 21
II. HÀNG ĐỢI (QUEUE) 22
§5. CÂY (TREE) 27
I. ĐỊNH NGHĨA 27
II. CÂY NHỊ PHÂN (BINARY TREE) 28
III. BIỂU DIỄN CÂY NHỊ PHÂN 29
IV. PHÉP DUYỆT CÂY NHỊ PHÂN 30
V. CÂY K_PHÂN 31
VI. CÂY TỔNG QUÁT 32
§6. KÝ PHÁP TIỀN TỐ, TRUNG TỐ VÀ HẬU TỐ 34
I. BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN 34
II. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC 34
III. CÁCH TÍNH GIÁ TRỊ BIỂU THỨC 34
IV. CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ 37
V. XÂY DỰNG CÂY NHỊ PHÂN BIỂU DIỄN BIỂU THỨC 40
§7. SẮP XẾP (SORTING) 41
I. BÀI TOÁN SẮP XẾP 41
II. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTION SORT) 43
III. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLE SORT) 43
IV. THUẬT TOÁN SẮP XẾP KIỂU CHÈN 44
V. SHELL SORT 45
VI. THUẬT TOÁN SẮP XẾP KIỂU PHÂN ĐOẠN (QUICK SORT) 46
VII. THUẬT TOÁN SẮP XẾP KIỂU VUN ĐỐNG (HEAP SORT) 48
VIII. SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI (DISTRIBUTION COUNTING) 51
IX. TÍNH ỔN ĐỊNH CỦA THUẬT TOÁN SẮP XẾP (STABILITY) 52
X. THUẬT TOÁN SẮP XẾP BẰNG CƠ SỐ (RADIX SORT) 53
XI. THUẬT TOÁN SẮP XẾP TRỘN (MERGE SORT) 56
XII. CÀI ĐẶT 58
XIII. NHỮNG NHẬN XÉT CUỐI CÙNG 66
§8. TÌM KIẾM (SEARCHING) 68
I. BÀI TOÁN TÌM KIẾM 68
II. TÌM KIẾM TUẦN TỰ (SEQUENTIAL SEARCH) 68
III. TÌM KIẾM NHỊ PHÂN (BINARY SEARCH) 68
IV. CÂY NHỊ PHÂN TÌM KIẾM (BINARY SEARCH TREE - BST) 69
V. PHÉP BĂM (HASH) 72
VI. KHOÁ SỐ VỚI BÀI TOÁN TÌM KIẾM 73
VII. CÂY TÌM KIẾM SỐ HỌC (DIGITAL SEARCH TREE - DST) 73
VIII. CÂY TÌM KIẾM CƠ SỐ (RADIX SEARCH TREE - RST) 76
IX. NHỮNG NHẬN XÉT CUỐI CÙNG 80
§0. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC
I. XÁC ĐỊNH BÀI TOÁN
Input ( Process ( Output
(Dữ liệu vào ( Xử lý ( Kết quả ra)
Việc xác định bài toán tức là phải xác định xem ta phải giải quyết vấn đề gì?, với giả thiết nào đã cho và lời giải cần phải đạt những yêu cầu nào. Khác với bài toán thuần tuý toán học chỉ cần xác định rõ giả thiết và kết luận chứ không cần xác định yêu cầu về lời giải, đôi khi những bài toán tin học ứng dụng trong thực tế chỉ cần tìm lời giải tốt tới mức nào đó, thậm chí là tồi ở mức chấp nhận được. Bởi lời giải tốt nhất đòi hỏi quá nhiều thời gian và chi phí.
Ví dụ:
Khi cài đặt các hàm số phức tạp trên máy tính. Nếu tính bằng cách khai triển chuỗi vô hạn thì độ chính xác cao hơn nhưng thời gian chậm hơn hàng tỉ lần so với phương pháp xấp xỉ. Trên thực tế việc tính toán luôn luôn cho phép chấp nhận một sai số nào đó nên các hàm số trong máy tính đều được tính bằng phương pháp xấp xỉ của giải tích số
Xác định đúng yêu cầu bài toán là rất quan trọng bởi nó ảnh hưởng tới cách thức giải quyết và chất lượng của lời giải. Một bài toán thực tế thường cho bởi