Boi_duong_HSG
Chia sẻ bởi Đoàn Minh Đức |
Ngày 14/10/2018 |
40
Chia sẻ tài liệu: boi_duong_HSG thuộc Tư liệu tham khảo
Nội dung tài liệu:
LÊ MINHHOÀNG
(A.K.A DSAP Textbook)
Đại học Sư phạm Hà Nội, 1999-2005
Try not to become a man of success
but rather to become a man of value.
Albert Einstein
i
MỤC LỤC
PHẦN 1. BÀI TOÁN LIỆT KÊ ......................................................................... 1
§1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP ................................................................2
1.1. CHỈNH HỢP LẶP ....................................................................................................................................... 2
1.2. CHỈNH HỢP KHÔNG LẶP........................................................................................................................ 2
1.3. HOÁN VỊ .................................................................................................................................................... 2
1.4. TỔ HỢP ....................................................................................................................................................... 3
§2. PHƯƠNG PHÁP SINH (GENERATION) ....................................................................................4
2.1. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N................................................................................................... 5
2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ..................................................................................................... 6
2.3. LIỆT KÊ CÁC HOÁN VỊ ........................................................................................................................... 8
§3. THUẬT TOÁN QUAY LUI ..........................................................................................................12
3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N ........................................................................................... 12
3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ................................................................................................... 13
3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K ............................................................................. 15
3.4. BÀI TOÁN PHÂN TÍCH SỐ .................................................................................................................... 17
3.5. BÀI TOÁN XẾP HẬU .............................................................................................................................. 19
§4. KỸ THUẬT NHÁNH CẬN ...........................................................................................................24
4.1. BÀI TOÁN TỐI ƯU.................................................................................................................................. 24
4.2. SỰ BÙNG NỔ TỔ HỢP............................................................................................................................ 24
4.3. MÔ HÌNH KỸ THUẬT NHÁNH CẬN .................................................................................................... 24
4.4. BÀI TOÁN NGƯỜI DU LỊCH ................................................................................................................. 25
4.5. DÃY ABC ................................................................................................................................................. 27
PHẦN 2. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ..................................... 33
§1. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC .........................34
1.1. XÁC ĐỊNH BÀI TOÁN ............................................................................................................................ 34
1.2. TÌM CẤU TRÚC DỮ LIỆU BIỂU DIỄN BÀI TOÁN ............................................................................. 34
1.3. TÌM THUẬT TOÁN ................................................................................................................................. 35
1.4. LẬP TRÌNH .............................................................................................................................................. 37
1.5. KIỂM THỬ................................................................................................................................................ 37
1.6. TỐI ƯU CHƯƠNG TRÌNH ...................................................................................................................... 38
§2. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT ...........................................................40
2.1. GIỚI THIỆU .............................................................................................................................................. 40
2.2. CÁC KÝ PHÁP ĐỂ ĐÁNH GIÁ ĐỘ PHỨC TẠP TÍNH TOÁN ............................................................. 40
2.3. XÁC ĐỊNH ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT ............................................................ 42
2.4. ĐỘ PHỨC TẠP TÍNH TOÁN VỚI TÌNH TRẠNG DỮ LIỆU VÀO ....................................................... 45
2.5. CHI PHÍ THỰC HIỆN THUẬT TOÁN .................................................................................................... 46
§3. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY ......................................................................................... 50
3.1. KHÁI NIỆM VỀ ĐỆ QUY ........................................................................................................................ 50
3.2. GIẢI THUẬT ĐỆ QUY............................................................................................................................. 50
3.3. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY .......................................................................................................... 51
3.4. HIỆU LỰC CỦA ĐỆ QUY ....................................................................................................................... 55
§4. CẤU TRÚC DỮ LIỆU BIỂU DIỄN DANH SÁCH .................................................................... 58
4.1. KHÁI NIỆM DANH SÁCH ...................................................................................................................... 58
4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH .................................................................................... 58
§5. NGĂN XẾP VÀ HÀNG ĐỢI ........................................................................................................ 64
5.1. NGĂN XẾP (STACK)............................................................................................................................... 64
5.2. HÀNG ĐỢI (QUEUE)............................................................................................................................... 66
§6. CÂY (TREE) .................................................................................................................................. 70
6.1. ĐỊNH NGHĨA............................................................................................................................................ 70
6.2. CÂY NHỊ PHÂN (BINARY TREE) ......................................................................................................... 71
6.3. BIỂU DIỄN CÂY NHỊ PHÂN .................................................................................................................. 73
6.4. PHÉP DUYỆT CÂY NHỊ PHÂN .............................................................................................................. 75
6.5. CÂY K_PHÂN .......................................................................................................................................... 76
6.6. CÂY TỔNG QUÁT ................................................................................................................................... 77
§7. KÝ PHÁP TIỀN TỐ, TRUNG TỐ VÀ HẬU TỐ ....................................................................... 80
7.1. BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN ......................................................................................... 80
7.2. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC.................................................................................... 80
7.3. CÁCH TÍNH GIÁ TRỊ BIỂU THỨC ........................................................................................................ 81
7.4. CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ................................................................... 84
7.5. XÂY DỰNG CÂY NHỊ PHÂN BIỂU DIỄN BIỂU THỨC ...................................................................... 87
§8. SẮP XẾP (SORTING) .................................................................................................................. 89
8.1. BÀI TOÁN SẮP XẾP................................................................................................................................ 89
8.2. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTIONSORT) ............................................................... 91
8.3. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLESORT)........................................................................... 92
8.4. THUẬT TOÁN SẮP XẾP KIỂU CHÈN (INSERTIONSORT)
(A.K.A DSAP Textbook)
Đại học Sư phạm Hà Nội, 1999-2005
Try not to become a man of success
but rather to become a man of value.
Albert Einstein
i
MỤC LỤC
PHẦN 1. BÀI TOÁN LIỆT KÊ ......................................................................... 1
§1. NHẮC LẠI MỘT SỐ KIẾN THỨC ĐẠI SỐ TỔ HỢP ................................................................2
1.1. CHỈNH HỢP LẶP ....................................................................................................................................... 2
1.2. CHỈNH HỢP KHÔNG LẶP........................................................................................................................ 2
1.3. HOÁN VỊ .................................................................................................................................................... 2
1.4. TỔ HỢP ....................................................................................................................................................... 3
§2. PHƯƠNG PHÁP SINH (GENERATION) ....................................................................................4
2.1. SINH CÁC DÃY NHỊ PHÂN ĐỘ DÀI N................................................................................................... 5
2.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ..................................................................................................... 6
2.3. LIỆT KÊ CÁC HOÁN VỊ ........................................................................................................................... 8
§3. THUẬT TOÁN QUAY LUI ..........................................................................................................12
3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N ........................................................................................... 12
3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬ ................................................................................................... 13
3.3. LIỆT KÊ CÁC CHỈNH HỢP KHÔNG LẶP CHẬP K ............................................................................. 15
3.4. BÀI TOÁN PHÂN TÍCH SỐ .................................................................................................................... 17
3.5. BÀI TOÁN XẾP HẬU .............................................................................................................................. 19
§4. KỸ THUẬT NHÁNH CẬN ...........................................................................................................24
4.1. BÀI TOÁN TỐI ƯU.................................................................................................................................. 24
4.2. SỰ BÙNG NỔ TỔ HỢP............................................................................................................................ 24
4.3. MÔ HÌNH KỸ THUẬT NHÁNH CẬN .................................................................................................... 24
4.4. BÀI TOÁN NGƯỜI DU LỊCH ................................................................................................................. 25
4.5. DÃY ABC ................................................................................................................................................. 27
PHẦN 2. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ..................................... 33
§1. CÁC BƯỚC CƠ BẢN KHI TIẾN HÀNH GIẢI CÁC BÀI TOÁN TIN HỌC .........................34
1.1. XÁC ĐỊNH BÀI TOÁN ............................................................................................................................ 34
1.2. TÌM CẤU TRÚC DỮ LIỆU BIỂU DIỄN BÀI TOÁN ............................................................................. 34
1.3. TÌM THUẬT TOÁN ................................................................................................................................. 35
1.4. LẬP TRÌNH .............................................................................................................................................. 37
1.5. KIỂM THỬ................................................................................................................................................ 37
1.6. TỐI ƯU CHƯƠNG TRÌNH ...................................................................................................................... 38
§2. PHÂN TÍCH THỜI GIAN THỰC HIỆN GIẢI THUẬT ...........................................................40
2.1. GIỚI THIỆU .............................................................................................................................................. 40
2.2. CÁC KÝ PHÁP ĐỂ ĐÁNH GIÁ ĐỘ PHỨC TẠP TÍNH TOÁN ............................................................. 40
2.3. XÁC ĐỊNH ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT ............................................................ 42
2.4. ĐỘ PHỨC TẠP TÍNH TOÁN VỚI TÌNH TRẠNG DỮ LIỆU VÀO ....................................................... 45
2.5. CHI PHÍ THỰC HIỆN THUẬT TOÁN .................................................................................................... 46
§3. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY ......................................................................................... 50
3.1. KHÁI NIỆM VỀ ĐỆ QUY ........................................................................................................................ 50
3.2. GIẢI THUẬT ĐỆ QUY............................................................................................................................. 50
3.3. VÍ DỤ VỀ GIẢI THUẬT ĐỆ QUY .......................................................................................................... 51
3.4. HIỆU LỰC CỦA ĐỆ QUY ....................................................................................................................... 55
§4. CẤU TRÚC DỮ LIỆU BIỂU DIỄN DANH SÁCH .................................................................... 58
4.1. KHÁI NIỆM DANH SÁCH ...................................................................................................................... 58
4.2. BIỂU DIỄN DANH SÁCH TRONG MÁY TÍNH .................................................................................... 58
§5. NGĂN XẾP VÀ HÀNG ĐỢI ........................................................................................................ 64
5.1. NGĂN XẾP (STACK)............................................................................................................................... 64
5.2. HÀNG ĐỢI (QUEUE)............................................................................................................................... 66
§6. CÂY (TREE) .................................................................................................................................. 70
6.1. ĐỊNH NGHĨA............................................................................................................................................ 70
6.2. CÂY NHỊ PHÂN (BINARY TREE) ......................................................................................................... 71
6.3. BIỂU DIỄN CÂY NHỊ PHÂN .................................................................................................................. 73
6.4. PHÉP DUYỆT CÂY NHỊ PHÂN .............................................................................................................. 75
6.5. CÂY K_PHÂN .......................................................................................................................................... 76
6.6. CÂY TỔNG QUÁT ................................................................................................................................... 77
§7. KÝ PHÁP TIỀN TỐ, TRUNG TỐ VÀ HẬU TỐ ....................................................................... 80
7.1. BIỂU THỨC DƯỚI DẠNG CÂY NHỊ PHÂN ......................................................................................... 80
7.2. CÁC KÝ PHÁP CHO CÙNG MỘT BIỂU THỨC.................................................................................... 80
7.3. CÁCH TÍNH GIÁ TRỊ BIỂU THỨC ........................................................................................................ 81
7.4. CHUYỂN TỪ DẠNG TRUNG TỐ SANG DẠNG HẬU TỐ................................................................... 84
7.5. XÂY DỰNG CÂY NHỊ PHÂN BIỂU DIỄN BIỂU THỨC ...................................................................... 87
§8. SẮP XẾP (SORTING) .................................................................................................................. 89
8.1. BÀI TOÁN SẮP XẾP................................................................................................................................ 89
8.2. THUẬT TOÁN SẮP XẾP KIỂU CHỌN (SELECTIONSORT) ............................................................... 91
8.3. THUẬT TOÁN SẮP XẾP NỔI BỌT (BUBBLESORT)........................................................................... 92
8.4. THUẬT TOÁN SẮP XẾP KIỂU CHÈN (INSERTIONSORT)
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Đoàn Minh Đức
Dung lượng: 20,62MB|
Lượt tài: 0
Loại file: doc
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)