1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - Nguyễn Khánh Phương

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - Nguyễn Khánh Phương

Chương 1 - Các khái niệm cơ bản. Trong chương này, người học có thể hiểu được một số kiến thức cơ bản về: Ví dụ mở đầu, thuật toán và độ phức tạp, kí hiệu tiệm cận, giả ngôn ngữ (pseudo code), một số kĩ thuật phân tích thuật toán, giải công thức đệ quy. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science department School of Information and Communication technology E-mail: phuo

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 173

Ngày tạo 10/10/2021 7:16:14 PM +00:00

Loại tệp PDF

Kích thước 6.18 M

Tên tệp

Tải Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1... (.pdf)

Xem mẫu

  1. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Cấu trúc dữ liệu và thuật toán an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Nội dung khóa học Chương 1. Các khái niệm cơ bản om Chương 2. Các sơ đồ thuật toán .c ng Chương 3. Các cấu trúc dữ liệu cơ bản co Chương 4. Cây an Chương 5. Sắp xếp th o ng du Chương 6. Tìm kiếm u cu Chương 7. Đồ thị 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG om .c ng co Chương 1. Các khái niệm cơ bản an th o ng Nguyễn Khánh Phƣơng du u cu Computer Science department School of Information and Communication technology E-mail: phuongnk@soict.hust.edu.vn CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Nội dung 1.1. Ví dụ mở đầu om 1.2. Thuật toán và độ phức tạp .c 1.3. Kí hiệu tiệm cận ng 1.4. Giả ngôn ngữ (Pseudo code) co an 1.5. Một số kĩ thuật phân tích thuật toán 1.6. Giải công thức đệ quy th o ng du u cu 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. Nội dung 1.1. Ví dụ mở đầu om 1.2. Thuật toán và độ phức tạp .c 1.3. Kí hiệu tiệm cận ng 1.4. Giả ngôn ngữ (Pseudo code) co an 1.5. Một số kĩ thuật phân tích thuật toán 1.6. Giải công thức đệ quy th o ng du u cu 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. Ví dụ: Tìm dãy con lớn nhất (The maximum subarray problem) om .c ng co an th o ng du u cu 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. Ví dụ: Tìm dãy con lớn nhất (The maximum subarray problem) 1.1.1. Duyệt toàn bộ (Brute force) 1.1.2. Duyệt toàn bộ có cải tiến om .c 1.1.3 Thuật toán đệ quy (Recursive algorithm) ng 1.1.4. Thuật toán quy hoạch động (Dynamic programming) co an th o ng du u cu NGUYỄN KHÁNH PHƢƠNG7 Bộ môn KHMT – ĐHBK HN CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. Ví dụ: Tìm dãy con lớn nhất (The maximum subarray problem) 1.1.1. Duyệt toàn bộ (Brute force) 1.1.2. Duyệt toàn bộ có cải tiến om .c 1.1.3 Thuật toán đệ quy (Recursive algorithm) ng 1.1.4. Thuật toán quy hoạch động (Dynamic programming) co an th o ng du u cu 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. 1.1.1. Thuật toán duyệt toàn bộ giải bài toán dãy con lớn nhất • Thuật toán đơn giản đầu tiên có thể nghĩ để giải bài toán đặt om ra là: Duyệt tất cả các dãy con có thể : .c ng ai, ai+1 , …, aj với 1 ≤ i ≤ j ≤ n, co và tính tổng của mỗi dãy con để tìm ra trọng lượng lớn nhất. an th • Trước hết nhận thấy rằng, tổng số các dãy con có thể của o ng du dãy đã cho là: u cu C(n, 1) + C(n, 2) = n2/2 + n/2 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. Ví dụ ứng dụng • Giả sử ta biết giá của cổ phiếu của công ty A từ ngày i đến ngày j như sau: Ngày 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 om Giá 100 112 109 85 105 102 86 63 81 101 94 106 101 79 93 89 95 .c • Ta cần mua một số cổ phiếu, duy nhất 1 lần, rồi bán ra tại một ngày nào đó sau đấy. • Làm thế nào để tối đa hóa lợi nhuận ? ng – Chiến lược: mua vào lúc giá thấp, bán ra lúc giá cao [buy low, sell high] không phải lúc nào cũng co cho lợi nhuận cao nhất an Ví dụ: Cho giá cổ phiếu như ở đồ thị. Ta thu được lợi nhuận cao nhất là 3$ nếu mua vào ở thứ 2 với giá 7$, và bán ra ở ngày thứ 3 với giá 10$. Giá 7$ mua vào ở ngày 2 không phải là giá thấp nhất, và giá 10$ th bán ra ở ngày 3 cũng không phải là giá cao nhất ng o du u cu – Lời giải: Ta dễ dàng tìm được bằng cách duyệt hết tất cả các khả năng: • Có bao nhiêu cặp ngày mua/bán có thể có trong khoảng thời gian n ngày? • Tính lợi nhuận thu được cho mỗi cặp ngày, để tìm cặp ngày có lợi nhuận cao nhất – Liệu ta có thể làm tốt hơn hay không? 10 • Câu trả lời: Có, bằng cách quy về bài toán dãy con lớn nhất CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. Quy về bài toán dãy con lớn nhất Ngày 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Giá 100 112 109 85 105 102 86 63 81 101 94 106 101 79 93 89 95 om • Tìm dãy các ngày liên tiếp sao cho: – Tổng lượng giá thay đổi ở ngày cuối so với ngày đầu là lớn nhất .c • Nhìn vào giá của từng ngày ng – Lượng giá thay thay đổi vào ngày i: giá cổ phiếu ngày i trừ đi giá cổ phiếu ngày i-1 – Ta có mảng giá thay đổi như sau: co Ngày 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 an Giá 100 112 109 85 105 102 86 63 81 101 94 106 101 79 93 89 95 th Thay 12 -3 -24 20 -3 -16 -23 18 20 -7 12 -5 -22 14 -4 6 đổi ng – Tìm dãy con liên tiếp có tổng lớn nhất o du • Dãy con lớn nhất e.g.: 12,-3,-24,20,-3,-16,-23,18,20,-7,12,-5,-22,14,-4,6 u cu Dãy con lớn nhất: 18+20+(-7)+12 = 43  Mua sau ngày thứ 7, bán ra sau ngày thứ 11: mua với giá = 63, bán ra với lúc = 106  Lợi nhuận =106-63=43 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. Thuật toán duyệt toàn bộ: duyệt tất cả các dãy con Chỉ số i 0 1 2 3 4 5 om a[i] -2 11 -4 13 -5 2 .c i = 0: (-2), (-2, 11), (-2,11, -4), (-2,11,-4,13), (-2,11,- ng 4,13,-5), (-2,11,-4,13,-5,2) i = 1: (11), (11, -4), (11, -4, 13), (11, -4, 13, -5), (11, -4, co 13, -5, 2) an i = 2: (-4), (-4, 13), (-4, 13, -5), (-4,13,-5,2) th i = 3: (13), (13,-5), (13, -5,2) ng i = 4: (-5), (-5, 2) int maxSum = 0; o i = 5: (2) for (int i=0; i
  13. Thuật toán duyệt toàn bộ: duyệt tất cả các dãy con • Phân tích thuật toán: Ta sẽ tính số lượng phép cộng mà thuật toán phải thực hiện, tức là đếm xem dòng lệnh om sum += a[k] phải thực hiện bao nhiều lần. Số lượng phép cộng là: .c n 1 n 1 n 1 n 1 ng (n i)( n i 1) ( j i 1) (1 2 ... (n i)) co i 0 j i i 0 i 0 2 n n n an 1 1 2 1 n(n 1) ( 2 n 1) n(n 1) k (k 1) k k th 2 k 1 2 k 1 k 1 2 6 2 3 2 n n n ng int maxSum = 0; o 6 2 3 for (int i=0; i
  14. Ví dụ: Tìm dãy con lớn nhất (The maximum subarray problem) 1.1.1. Duyệt toàn bộ (Brute force) 1.1.2. Duyệt toàn bộ có cải tiến om .c 1.1.3 Thuật toán đệ quy (Recursive algorithm) ng 1.1.4. Thuật toán quy hoạch động (Dynamic programming) co an th o ng du u cu 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. 1.1.2. Duyệt toàn bộ có cải tiến Thuật toán duyệt toàn bộ: duyệt tất cả các dãy con Chỉ số i 0 1 2 3 4 5 om a[i] -2 11 -4 13 -5 2 .c i = 0: (-2), (-2, 11), (-2,11, -4), (-2,11,-4,13), (-2,11,-4,13,-5), (-2,11,- 4,13,-5,2) ng i = 1: (11), (11, -4), (11, -4, 13), (11, -4, 13, -5), (11, -4, 13, -5, 2) co i = 2: (-4), (-4, 13), (-4, 13, -5), (-4,13,-5,2) i = 3: (13), (13,-5), (13, -5,2) an i = 4: (-5), (-5, 2) th i = 5: (2) ng int maxSum = 0; int maxSum = a[0]; o for (int i=0; i
  16. 1.1.2. Duyệt toàn bộ có cải tiến Thuật toán duyệt toàn bộ: duyệt tất cả các dãy con • Cài đặt cải tiến: Nhận thấy, ta có thể tính tổng các phần tử từ vị trí i đến j từ tổng của các phần om tử từ i đến j-1 chỉ bằng 1 phép cộng: .c j j 1 a[k ] a[ j] a[k ] ng k i k i co Tổng các phần tử từ i đến j Tổng các phần tử từ i đến j-1 an th int maxSum = 0; int maxSum = a[0]; ng for (int i=0; i
  17. 1.1.2. Duyệt toàn bộ có cải tiến Thuật toán duyệt toàn bộ: duyệt tất cả các dãy con • Phân tích thuật toán. Ta lại tính số lần thực hiện phép cộng: Sum += a[j] om Và thu được kết quả: .c n 1 2 n n ng (n i) n (n 1) ... 1 2 2 co i 0 an • Để ý rằng số này là đúng bằng số lượng dãy con. Dường như thuật toán thu được là rất tốt, vì ta phải xét mỗi dãy con đúng 1 lần. th o ng int maxSum = a[0]; du for (int i=0; i
  18. Ví dụ: Tìm dãy con lớn nhất (The maximum subarray problem) 1.1.1. Duyệt toàn bộ (Brute force) 1.1.2. Duyệt toàn bộ có cải tiến om .c 1.1.3 Thuật toán đệ quy (Recursive algorithm) ng 1.1.4. Thuật toán quy hoạch động (Dynamic programming) co an th o ng du u cu 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. 1.1.3. Thuật toán đệ quy giải bài toán dãy con lớn nhất • Ta còn có thể xây dựng thuật toán tốt hơn nữa bằng kỹ thuật chia để trị (divide-and-conquer). Kỹ thuật này bao gồm các bước sau: om – Chia bài toán cần giải ra thành các bài toán con cùng dạng .c – Giải mỗi bài toán con một cách đệ qui ng • Trường hợp cơ sở: khi bài toán con có kích thước đủ nhỏ, ta giải co nó bằng phương pháp duyệt toàn bộ. an – Tổ hợp lời giải của các bài toán con để thu được lời giải của bài toán th xuất phát. ng • Để giải bài toán dãy con lớn nhất: o – Sử dụng phần tử chính giữa để chia đôi dãy đã cho thành hai dãy con (gọi tắt là du dãy nửa trái và dãy nửa phải) với độ dài giảm đi một nửa u low mid high cu mid +1 Nửa trái A[low..mid] Nửa phải A[mid+1..high] 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  20. 1.1.3. Thuật toán đệ quy giải bài toán dãy con lớn nhất • Để tổ hợp lời giải, nhận thấy rằng dãy con lớn nhất A[i..j] của dãy A[low..high] chỉ có thể xảy ra một trong 3 trường hợp (với mid = (low+high)/2 ): – Dãy con lớn nhất nằm ở dãy nửa bên trái A[low..mid] (low i j mid) om – Dãy con lớn nhất nằm ở dãy nửa bên phải A[mid+1..high] (mid < i j high) .c – Giao điểm giữa mid (low i mid < j high) {dãy con lớn nhất bắt đầu ở nửa trái và kết thúc ở nửa phải} ng co an th • Do đó, nếu kí hiệu trọng lượng của dãy con lớn nhất ở nửa trái là wL, ở nửa phải làwR, và giao điểm giữa ng là wM, thì trọng lượng lớn nhất cần tìm là max(wL, wR, wM) o du u cu 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường