Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 1: Các khái niệm cơ bản - Nguyễn Khánh Phương
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Cấu trúc dữ liệu và thuật toán
Nguyễn Khánh Phƣơng
Computer Science department
School of Information and Communication technology
E-mail: [email protected]n
Nội dung khóa học
Chương 1. Các khái niệm cơ bản
Chương 2. Các sơ đồ thuật toán
Chương 3. Các cấu trúc dữ liệu cơ bản
Chương 4. Cây
Chương 5. Sắp xếp
Chương 6. Tìm kiếm
Chương 7. Đồ thị
2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Chương 1. Các khái niệm cơ bản
Nguyễn Khánh Phƣơng
Computer Science department
School of Information and Communication technology
E-mail: [email protected]n
Nội dung
1.1. Ví dụ mở đầu
1.2. Thuật toán và độ phức tạp
1.3. Kí hiệu tiệm cận
1.4. Giả ngôn ngữ (Pseudo code)
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
4
Nội dung
1.1. Ví dụ mở đầu
1.2. Thuật toán và độ phức tạp
1.3. Kí hiệu tiệm cận
1.4. Giả ngôn ngữ (Pseudo code)
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
5
Ví dụ: Tìm dãy con lớn nhất
(The maximum subarray problem)
6
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
1.1.3 Thuật toán đệ quy (Recursive algorithm)
1.1.4. Thuật toán quy hoạch động (Dynamic programming)
NGUYỄN KHÁNH PHƢƠNG7
Bộ môn KHMT – ĐHBK HN
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
1.1.3 Thuật toán đệ quy (Recursive algorithm)
1.1.4. Thuật toán quy hoạch động (Dynamic programming)
8
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
ra là: Duyệt tất cả các dãy con có thể :
ai, ai+1 , …, aj với 1 ≤ i ≤ j ≤ n,
và tính tổng của mỗi dãy con để tìm ra trọng lượng lớn nhất.
• Trước hết nhận thấy rằng, tổng số các dãy con có thể của
dãy đã cho là:
C(n, 1) + C(n, 2) = n2/2 + n/2
9
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
Giá
100 112 109 85
105 102 86
63
81
101 94
106 101 79
93
89
95
• 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 ?
– 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
cho lợi nhuận cao nhất
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$
bán ra ở ngày 3 cũng không phải là giá cao nhất
– 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
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
• 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
• Nhìn vào giá của từng ngày
– 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:
Ngày
1
2
3
4
5
6
7
8
9
10
101 94
20 -7
11
12
106 101 79
12 -5 -22
13
14
15
93
14
16
89
-4
17
95
6
Giá
100 112 109 85
12 -3 -24
105 102 86
20 -3 -16
63
-23
81
18
Thay
đổi
– Tìm dãy con liên tiếp có tổng lớn nhất
• 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
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
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
a[i]
-2
11
-4
13
-5
2
i = 0: (-2), (-2, 11), (-2,11, -4), (-2,11,-4,13), (-2,11,-
4,13,-5), (-2,11,-4,13,-5,2)
i = 1: (11), (11, -4), (11, -4, 13), (11, -4, 13, -5), (11, -4,
13, -5, 2)
i = 2: (-4), (-4, 13), (-4, 13, -5), (-4,13,-5,2)
i = 3: (13), (13,-5), (13, -5,2)
int maxSum = 0;
i = 4: (-5), (-5, 2)
for (int i=0; i<n; i++) {
i = 5: (2)
for (int j=i; j<n; j++) {
Với mỗi chỉ số i : duyệt tất cả các dãy con bắt đầu từ phần tử
a[i] có 1 phần tử, có 2 phần tử, … :
int sum = 0;
for (int k=i; k<=j; k++)
sum += a[k];
•
i = 0: tất cả các dãy con bắt đầu từ a[0] có 1 phần tử, 2 phần
tử, … 6 phần tử
i = 1: tất cả các dãy con bắt đầu từ a[1] có 1 phần tử, 2 phần
tử, … 5 phần tử
•
if (sum > maxSum)
maxSum = sum;
•
•
…
i = 5: tất cả các dãy con bắt đầu từ a[5] có 1 phần tử
}
12
}
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
sum += a[k]
phải thực hiện bao nhiều lần. Số lượng phép cộng là:
n
i
2
i
0
j
i
0
i
0
n
1
2
2
k
1
k
1
k
1
n 3
n 2
n
int maxSum = 0;
6
2
3
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
int sum = 0;
for (int k=i; k<=j; k++)
sum += a[k];
if (sum > maxSum)
maxSum = sum;
}
13
}
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
1.1.3 Thuật toán đệ quy (Recursive algorithm)
1.1.4. Thuật toán quy hoạch động (Dynamic programming)
14
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
a[i]
-2
11
-4
13
-5
2
i = 0: (-2), (-2, 11), (-2,11, -4), (-2,11,-4,13), (-2,11,-4,13,-5), (-2,11,-
4,13,-5,2)
i = 1: (11), (11, -4), (11, -4, 13), (11, -4, 13, -5), (11, -4, 13, -5, 2)
i = 2: (-4), (-4, 13), (-4, 13, -5), (-4,13,-5,2)
i = 3: (13), (13,-5), (13, -5,2)
i = 4: (-5), (-5, 2)
i = 5: (2)
int maxSum = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
int sum = 0;
int maxSum = a[0];
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum += a[j];
for (int k=i; k<=j; k++)
sum += a[k];
if (sum > maxSum)
maxSum = sum;
}
if (sum > maxSum)
maxSum = sum;
}
5
}
}
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
tử từ i đến j-1 chỉ bằng 1 phép cộng:
j
j
k
i
k
i
Tổng các phần tử từ i đến j
Tổng các phần tử từ i đến j-1
int maxSum = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
int sum = 0;
int maxSum = a[0];
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum += a[j];
for (int k=i; k<=j; k++)
sum += a[k];
if (sum > maxSum)
maxSum = sum;
}
if (sum > maxSum)
maxSum = sum;
}
}
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
• 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]
Và thu được kết quả:
n 2
n
n
( n 1) ... 1
2
2
i
0
• Để ý 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.
int maxSum = a[0];
for (int i=0; i<n; i++) {
int sum = 0;
for (int j=i; j<n; j++) {
sum += a[j];
if (sum > maxSum)
maxSum = sum;
}
17
}
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
1.1.3 Thuật toán đệ quy (Recursive algorithm)
1.1.4. Thuật toán quy hoạch động (Dynamic programming)
18
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:
– Chia bài toán cần giải ra thành các bài toán con cùng dạng
– Giải mỗi bài toán con một cách đệ qui
• Trường hợp cơ sở: khi bài toán con có kích thước đủ nhỏ, ta giải
nó bằng phương pháp duyệt toàn bộ.
– 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
xuất phát.
• Để giải bài toán dãy con lớn nhất:
– 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à
dãy nửa trái và dãy nửa phải) với độ dài giảm đi một nửa
low
mid
high
mid +1
Nửa trái A[low..mid]
Nửa phải A[mid+1..high]
19
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)
– 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)
– 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}
• 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
là wM, thì trọng lượng lớn nhất cần tìm là max(wL, wR, wM)
20
Tải về để xem bản đầy đủ
173 trang
13620
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 1: Các khái niệm cơ bản - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_1_cac_khai_n.pdf
