Tổng hợp bài giảng môn Cấu trúc dữ liệu và thuật toán_Thầy Phạm Quang Dũng| Bài giảng môn Cấu trúc dữ liệu và thuật toán| Trường Đại học Bách Khoa Hà Nội

Tổng hợp bài giảng môn Cấu trúc dữ liệu và thuật toán_Thầy Phạm Quang Dũng| Bài giảng môn Cấu trúc dữ liệu và thuật toán| Trường Đại học Bách Khoa Hà Nội. Tài liệu gồm 308 trang giúp bạn ôn tập và đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem.

50 25 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và thuật toán HUST

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

308 trang 2 tháng trước

Tác giả:

Profile Trịnh Thảo Anh
1
CẤU TRÚC DỮ LIỆU VÀ
THUẬT TOÁN
Khái niệm cơ bản
Nội dung
• Định nghĩa và khái niệm cơ bản
• Mã giả
• Độ phức tạp tính toán
• Ký hiệu tiệm cận
• Ví dụ mở đầu
Định nghĩa và khái niệm
• Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập
nhật thuận tiện
Định nghĩa và khái niệm
• Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập
nhật thuận tiện
• Thuật toán
• Dãy hữu hạn các bước tính toán để thu được đầu ra ứng với
đầu vào
Định nghĩa và khái niệm
• Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập
nhật thuận tiện
• Thuật toán
• Dãy hữu hạn các bước tính toán để thu được đầu ra ứng với
đầu vào
• Mục tiêu môn học
• Trang bị kiến thức để thiết kế và cài đặt các cấu trúc dữ liệu
và thuật toán hiệu quả để giải quyết các bài toán tính toán
• Ứng dụng
• Hệ quản trị cơ sở dữ liệu
• Tính toán tối ưu hóa
• Trí tuệ nhân tạo, thị giác máy tính
• Hệ điều hành
• …
Mã giả
• Mô tả thuật toán đơn giản, gần gũi, ngắn gọn và không phụ thuộc vào cú
pháp ngôn ngữ lập trình cụ thể
max(a[1..n]){
ans = a[1];
for i = 2 to n do
if ans < a[i] then
max = a[i];
return ans;
}
Procedures, funtions
proc(a,b,x){
. . .
return ans;
}
For loop
for i = 1 to n do{
. . .
}
Condition
if a < b then {
. . .
}
While loop
while i 100 do{
. . .
}
Assignment
x = <expression>;
x <expression>;
Mã giả
• Một bài toán (ví dụ sắp xếp) có thể có nhiều thuật toán giải quyết
selectionSort(a[1..n]){
for k = 1 to n do{
min = k;
for j = k+1 to n do{
if a[min] > a[j] then
min = j;
}
swap(a[k],a[min]);
}
}
insertionSort(a[1..n]){
for k = 2 to n do{
last = a[k];
j = k;
while(j > 1 and a[j-1] > last){
a[j] = a[j-1];
j--;
}
a[j] = last;
}
}
Phân tích độ phức tạp thuật toán
• Phân tích độ phức tạp thuật toán
• Thời gian
• Bộ nhớ sử dụng
• Phân tích thời gian thực hiện
• Thông qua thí nghiệm
• Phân tích câu lệnh cơ bản
Phân tích độ phức tạp thuật toán
• Thực nghiệm
• Viết chương trình bằng ngôn ngữ lập trình cụ thể
• Chạy chương trình trên một máy tính với nhiều bộ dữ liệu đầu vào
khác nhau
• Vẽ biểu đồ thời gian thực hiện
Phân tích độ phức tạp thuật toán
• Thực nghiệm
• Viết chương trình bằng ngôn ngữ lập trình cụ thể
• Chạy chương trình trên một máy tính với nhiều bộ dữ liệu đầu vào
khác nhau
• Vẽ biểu đồ thời gian thực hiện
• Hạn chế của phương pháp thực nghiệm
• Cần lập trình bằng một ngôn ngữ lập trình cụ thể
• Thời gian thực hiện phụ thuộc vào cấu hình máy tính
Phân tích độ phức tạp thuật toán
• Phân tính thời gian thực hiện bằng cách đếm số câu lệnh cơ bản (như
một hàm của kích thước dữ liệu đầu vào)
• Xác định kích thước dữ liệu đầu vào
• Số bít cần thiết để biểu diễn dữ liệu
• Hoặc (ở mức cao hơn) là số phần tử của dãy số, số phần tử của ma
trận, số đỉnh của đồ thị, …
• Xác định câu lệnh cơ bản
s = 0;
for i = 1 to n do
s = s + a[i];
Câu lệnh cơ bản là câu lệnh gán → thời gian thực hiện là T(n) = n+1
Phân tích độ phức tạp thuật toán
Dòng
Thời
gian
Số
lần
2
c
2
n
3
c
3
n
-1
4
C
4
n
-1
5
C
5

6
C
6

󰇛
󰇜
7
C
7

󰇛
󰇜
9
c
9
n
-1
1. insertionSort(a[1..n]){
2. for j = 2 to n do{
3. key = a[j];
4. i = j-1;
5. while i > 0 and a[i] > key do{
6. a[i+1] = a[i];
7. i = i – 1;
8. }
9. a[i+1] = key;
10. }
11. }
Thời gian thực hiện T(n) = c
2
n + c
3
(n-1) + c
4
(n-1) +c
5

+ c
6

󰇛
󰇜
+ c
7

󰇛󰇜 + c
9
(n-1)
Ký hiệu t
j
: số lần điều kiện của vòng lặp while (dòng 5)
được thực hiện ứng với 1 giá trị j (vòng lặp bên ngoài)
Phân tích độ phức tạp thuật toán
Thời gian tính T(n) = c
2
n + c
3
(n-1) + c
4
(n-1) +c
5

+ c
6

󰇛
󰇜 +
c
7

󰇛󰇜 + c
9
(n-1)
• Tình huống tốt nhất: dãy đã được sắp xếp, t
j
= 1 (j = 2,…,n)
→ T(n) có dạng an + b (tuyến tính)
• Tình huống tồi nhất: dãy được sắp xếp theo thứ tự ngược lại, t
j
= j (j =
2,…, n)
→ T(n) có dạng an
2
+ bn + c (bình phương)
Phân tích độ phức tạp thuật toán
• Độ tăng: số hạng có số mũ cao nhất (ví dụ, n
2
trong an
2
+ bn + c) sẽ đại
diện cho độ tăng của hàm
• Độ tăng là chỉ số xác định tốc độ tăng của thời gian tính khi kích thước
dữ liệu đầu vào tăng
• Một số độ tăng điển hình thường gặp
Logarithmic algorithms
Log n
Linear algorithms
n
Quadratic algorithms
n
2
Polynomial algorithms
n
k
Exponential algorithms
c
n
Ký hiệu tiệm cận Big O
• Giả sử g(n) là một hàm từ N đến R
• O(g(n)) = {f(n) | c > 0 và n
0
sao cho 0 ≤ f(n) ≤ cg(n) n n
0
}
• (g(n)) = {f(n) | c > 0 và n
0
sao cho 0 ≤ cg(n) ≤ f(n) n n
0
}
• (g(n)) = {f(n) | c
1
, c
2
> 0 và n
0
sao cho c
1
g(n) ≤ f(n) ≤ c
2
g(n) n n
0
}
Ký hiệu tiệm cận Big O
• Ví dụ
• 10
3
n
2
+ 2n +10
6
O(n
2
)
• 10
3
n
2
+ 2n +10
6
O(n
3
)
• 10
3
n
2
+ 2n +10
6
(n
2
)
• 10
3
n
2
+ 2n +10
6
(n)
• 10
3
n
2
+ 2n +10
6
(nlogn)
Ký hiệu tiệm cận Big O
• Giả sử f và g là các hàm không âm từ N đến R
• Nếu f(n) (g(n)), thì f(n) (g(n)) và f(n) O(g(n))
• Nếu 0 < lim
n→
󰇛󰇜
󰇛󰇜
< , thì f(n) (g(n))
• Nếu lim
n→
󰇛󰇜
󰇛󰇜
= 0, thì f(n) O(g(n))
Ví dụ mở đầu
• Cho dãy a = (a
1
, a
2
, …, a
n
). Một dãy con của a được định nghĩa là dãy
gồm một số phần tử liên tiếp a
i
, a
i+1
,…,a
j
. Trọng số của dãy con là tổng
các phần tử của nó. Tìm dãy con có trọng số lớn nhất
• Ví dụ: a = 2, -10, 11, -4, 13, -5, 2 khi đó dãy 11, -4, 13 là dãy con lớn nhất
Ví dụ mở đầu
maxSubSeq3(a[1..n]){
ans = -;
for i = 1 to n do{
for j = i to n do{
s = 0;
for k = i to j do
s = s + a[k];
if s > ans then
ans = s;
}
}
return ans;
}
Thuật toán trực tiếp: thời
gian O(n
3
)
maxSubSeq2(a[1..n]){
ans = -;
for i = 1 to n do{
s = 0;
for j = i to n do{
s = s + a[k];
if s > ans then
ans = s;
}
}
return ans;
}
Cải tiến: Thời gian O(n
2
)
Ví dụ mở đầu
• Quy hoạch động
• Ký hiệu s[i]: trọng số của dãy con lớn
nhất của dãy a
1
, . . ., a
i
trong đó phần
tử cuối cùng là a
i
.
maxSubSeq1(a[1..n]){
s[1] = a[1];
ans = s[1];
for i = 2 to n do{
if s[i-1] > 0 then
s[i] = s[i-1] + a[i];
else s[i] = a[i];
if ans < s[i] then
ans = s[i];
}
return ans;
}
Thuật toán tốt nhất: Thời gian
O(n)
• s[1] = a
1
• s[i] = s[i-1] + a
i
, if s[i-1] > 0
a
i
, ngược lại
| 1/308
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN Khái niệm cơ bản 1 Nội dung
• Định nghĩa và khái niệm cơ bản • Mã giả
• Độ phức tạp tính toán • Ký hiệu tiệm cận • Ví dụ mở đầu
Định nghĩa và khái niệm • Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập nhật thuận tiện
Định nghĩa và khái niệm • Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập nhật thuận tiện • Thuật toán
• Dãy hữu hạn các bước tính toán để thu được đầu ra ứng với đầu vào
Định nghĩa và khái niệm • Cấu trúc dữ liệu
• Cách thức tổ chức dữ liệu trong bộ nhớ để truy cập và cập nhật thuận tiện • Thuật toán
• Dãy hữu hạn các bước tính toán để thu được đầu ra ứng với đầu vào • Mục tiêu môn học
• Trang bị kiến thức để thiết kế và cài đặt các cấu trúc dữ liệu
và thuật toán hiệu quả để giải quyết các bài toán tính toán • Ứng dụng
• Hệ quản trị cơ sở dữ liệu • Tính toán tối ưu hóa
• Trí tuệ nhân tạo, thị giác máy tính • Hệ điều hành • … Mã giả
• Mô tả thuật toán đơn giản, gần gũi, ngắn gọn và không phụ thuộc vào cú
pháp ngôn ngữ lập trình cụ thể Assignment Condition max(a[1..n]){ x = ; if a < b then { ans = a[1]; x  ; . . . for i = 2 to n do } if ans < a[i] then max = a[i]; return ans; For loop Procedures, funtions } for i = 1 to n do{ . . . proc(a,b,x){ } . . . return ans; While loop } while i  100 do{ . . . } Mã giả
• Một bài toán (ví dụ sắp xếp) có thể có nhiều thuật toán giải quyết selectionSort(a[1..n]){ insertionSort(a[1..n]){ for k = 1 to n do{ for k = 2 to n do{ min = k; last = a[k]; for j = k+1 to n do{ j = k; if a[min] > a[j] then
while(j > 1 and a[j-1] > last){ min = j; a[j] = a[j-1]; } j--; swap(a[k],a[min]); } } a[j] = last; } } }
Phân tích độ phức tạp thuật toán
• Phân tích độ phức tạp thuật toán • Thời gian • Bộ nhớ sử dụng
• Phân tích thời gian thực hiện • Thông qua thí nghiệm
• Phân tích câu lệnh cơ bản
Phân tích độ phức tạp thuật toán • Thực nghiệm
• Viết chương trình bằng ngôn ngữ lập trình cụ thể
• Chạy chương trình trên một máy tính với nhiều bộ dữ liệu đầu vào khác nhau
• Vẽ biểu đồ thời gian thực hiện
Phân tích độ phức tạp thuật toán • Thực nghiệm
• Viết chương trình bằng ngôn ngữ lập trình cụ thể
• Chạy chương trình trên một máy tính với nhiều bộ dữ liệu đầu vào khác nhau
• Vẽ biểu đồ thời gian thực hiện
• Hạn chế của phương pháp thực nghiệm
• Cần lập trình bằng một ngôn ngữ lập trình cụ thể
• Thời gian thực hiện phụ thuộc vào cấu hình máy tính
Phân tích độ phức tạp thuật toán
• Phân tính thời gian thực hiện bằng cách đếm số câu lệnh cơ bản (như
một hàm của kích thước dữ liệu đầu vào)
• Xác định kích thước dữ liệu đầu vào
• Số bít cần thiết để biểu diễn dữ liệu
• Hoặc (ở mức cao hơn) là số phần tử của dãy số, số phần tử của ma
trận, số đỉnh của đồ thị, …
• Xác định câu lệnh cơ bản s = 0; for i = 1 to n do s = s + a[i];
Câu lệnh cơ bản là câu lệnh gán → thời gian thực hiện là T(n) = n+1
Phân tích độ phức tạp thuật toán 1. insertionSort(a[1..n]){ Dòng Thời gian Số lần 2. for j = 2 to n do{ 2 c n 2 3. key = a[j]; 3 c n-1 3 4. i = j-1; 4 C n-1 4
5. while i > 0 and a[i] > key do{ 6. a[i+1] = a[i]; 5 C 𝑛 5 ෍ 𝑡𝑗 7. i = i – 1; 𝑗=2 8. } 6 C 𝑛 6 9. a[i+1] = key; ෍(𝑡𝑗 − 1) 10. } 𝑗=2 11. } 7 C 𝑛 7 ෍(𝑡𝑗 − 1) 𝑗=2
Ký hiệu t : số lần điều kiện của vòng lặp while (dòng 5) j
được thực hiện ứng với 1 giá trị j (vòng lặp bên ngoài) 9 c n-1 9
Thời gian thực hiện T(n) = c n + c (n-1) + c (n-1) +c σ𝑛 𝑡 σ𝑛 (𝑡 − 1) 2 3 4 5 𝑗=2 𝑗 + c6 𝑗=2 𝑗
+ c σ𝑛 (𝑡𝑗 − 1) + c (n-1) 7 𝑗=2 9
Phân tích độ phức tạp thuật toán
Thời gian tính T(n) = c n + c (n-1) + c (n-1) +c σ𝑛 𝑡 σ𝑛 (𝑡 − 1) + 2 3 4 5 𝑗=2 𝑗 + c6 𝑗=2 𝑗
c σ𝑛 (𝑡𝑗 − 1) + c (n-1) 7 𝑗=2 9
• Tình huống tốt nhất: dãy đã được sắp xếp, t = 1 (j = 2,…,n) j
→ T(n) có dạng an + b (tuyến tính)
• Tình huống tồi nhất: dãy được sắp xếp theo thứ tự ngược lại, t = j (j = j 2,…, n)
→ T(n) có dạng an2 + bn + c (bình phương)
Phân tích độ phức tạp thuật toán
• Độ tăng: số hạng có số mũ cao nhất (ví dụ, n2 trong an2 + bn + c) sẽ đại
diện cho độ tăng của hàm
• Độ tăng là chỉ số xác định tốc độ tăng của thời gian tính khi kích thước dữ liệu đầu vào tăng
• Một số độ tăng điển hình thường gặp Logarithmic algorithms Log n Linear algorithms n Quadratic algorithms n2 Polynomial algorithms nk Exponential algorithms cn
Ký hiệu tiệm cận Big O
• Giả sử g(n) là một hàm từ N đến R
• O(g(n)) = {f(n) |  c > 0 và n sao cho 0 ≤ f(n) ≤ cg(n) nn } 0 0
• (g(n)) = {f(n) |  c > 0 và n sao cho 0 ≤ cg(n) ≤ f(n) nn } 0 0
• (g(n)) = {f(n) |  c , c > 0 và n sao cho c g(n) ≤ f(n) ≤ c g(n) nn } 1 2 0 1 2 0
Ký hiệu tiệm cận Big O • Ví dụ
• 103n2 + 2n +106  O(n2)
• 103n2 + 2n +106  O(n3)
• 103n2 + 2n +106  (n2)
• 103n2 + 2n +106  (n)
• 103n2 + 2n +106  (nlogn)
Ký hiệu tiệm cận Big O
• Giả sử f và g là các hàm không âm từ N đến R
• Nếu f(n) (g(n)), thì f(n) (g(n)) và f(n) O(g(n)) • Nếu 𝑓(𝑛) 0 < lim
< , thì f(n) (g(n)) n→ 𝑔(𝑛) • Nếu 𝑓(𝑛) lim
= 0, thì f(n) O(g(n)) n→ 𝑔(𝑛) Ví dụ mở đầu
• Cho dãy a = (a , a , …, a ). Một dãy con của a được định nghĩa là dãy 1 2 n
gồm một số phần tử liên tiếp a , a ,…,a . Trọng số của dãy con là tổng i i+1 j
các phần tử của nó. Tìm dãy con có trọng số lớn nhất
• Ví dụ: a = 2, -10, 11, -4, 13, -5, 2 khi đó dãy 11, -4, 13 là dãy con lớn nhất Ví dụ mở đầu maxSubSeq3(a[1..n]){ maxSubSeq2(a[1..n]){ ans = -; ans = -; for i = 1 to n do{ for i = 1 to n do{ for j = i to n do{ s = 0; s = 0; for j = i to n do{ for k = i to j do s = s + a[k]; s = s + a[k]; if s > ans then if s > ans then ans = s; ans = s; } } } } return ans; return ans; } }
Thuật toán trực tiếp: thời
Cải tiến: Thời gian O(n2) gian O(n3) Ví dụ mở đầu • Quy hoạch động maxSubSeq1(a[1..n]){
• Ký hiệu s[i]: trọng số của dãy con lớn s[1] = a[1];
nhất của dãy a , . . ., a trong đó phần ans = s[1]; 1 i
tử cuối cùng là a . for i = 2 to n do{ i if s[i-1] > 0 then s[i] = s[i-1] + a[i]; else s[i] = a[i]; if ans < s[i] then ans = s[i]; } return ans; • s[1] = a1 }
• s[i] = s[i-1] + a , if s[i-1] > 0 i a , ngược lại i
Thuật toán tốt nhất: Thời gian O(n)