CTDL&TT

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
• 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
• 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 = <expression>; if a < b then { ans = a[1];
x  <expression>; . . . for i = 2 to n do
} if ans < a[i] then
max = a[i];
For loop Procedures, funtions return ans;
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
• 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
• 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í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
1. insertionSort(a[1..n]){ Dòng Thời gian Số lần
2. for j = 2 to n do{ 2 c2 n
3. key = a[j];
3 c3 n-1
4. i = j-1;
5. while i > 0 and a[i] > key do{ 4 C4 n-1
𝑛
6. a[i+1] = a[i]; 5 C5
7. i = i – 1; ෍ 𝑡𝑗
𝑗=2
8. }
𝑛
9. a[i+1] = key; 6 C6
෍(𝑡𝑗 − 1)
10. } 𝑗=2
11. } 𝑛
7 C7
෍(𝑡𝑗 − 1)
𝑗=2
Ký hiệu tj: 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) 9 c9 n-1
Thời gian thực hiện T(n) = c2n + c3(n-1) + c4(n-1) +c5σ𝑛𝑗=2 𝑡𝑗 + c6σ𝑛𝑗=2(𝑡𝑗 − 1)
+ c7σ𝑛𝑗=2(𝑡𝑗 − 1) + c9(n-1)
Thời gian tính T(n) = c2n + c3(n-1) + c4(n-1) +c5σ𝑛𝑗=2 𝑡𝑗 + c6σ𝑛𝑗=2(𝑡𝑗 − 1) +

c7σ𝑛𝑗=2(𝑡𝑗 − 1) + c9(n-1)
• Tình huống tốt nhất: dãy đã được sắp xếp, tj = 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, tj = j (j =
2,…, n)
→ T(n) có dạng an2 + bn + c (bình phương)
• Độ 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à n0 sao cho 0 ≤ f(n) ≤ cg(n) n  n0}
• (g(n)) = {f(n) |  c > 0 và n0 sao cho 0 ≤ cg(n) ≤ f(n) n  n0}
• (g(n)) = {f(n) |  c1, c2 > 0 và n0 sao cho c1g(n) ≤ f(n) ≤ c2g(n) n  n0}
• Ví dụ
• 103n2 + 2n +106  O(n2)
• 103n2 + 2n +106  O(n3)
• 103n2 + 2n +106  (n2)
• 103n2 + 2n +106  (n)
• 103n2 + 2n +106  (nlogn)
• 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 < limn→ < , thì f(n) (g(n))
𝑔(𝑛)
𝑓(𝑛)
• Nếu limn→ = 0, thì f(n) O(g(n))
𝑔(𝑛)
Ví dụ mở đầu
• Cho dãy a = (a1, a2, …, an). 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 ai, ai+1,…,aj. 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
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)
• 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 a1, . . ., ai trong đó phần ans = s[1];
tử cuối cùng là ai. 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];
}
• s[1] = a1 return ans;
}
• s[i] = s[i-1] + ai, if s[i-1] > 0
ai, ngược lại
Thuật toán tốt nhất: Thời gian
O(n)
CẤU TRÚC DỮ LIỆU
VÀ THUẬT TOÁN
Sơ đồ thuật toán cơ bản
NỘI DUNG
• Đệ quy
• Đệ quy có nhớ
• Đệ quy quay lui
• Thuật toán nhánh và cận
• Thuật toán tham lam
• Thuật toán chia để trị
• Thuật toán quy hoạch động
ĐỆ QUY
• Hàm được định nghĩa đệ quy
• Bước cơ sở: định nghĩa giá trị hàm với tham số cơ sở (nhỏ nhất)
• Bước đệ quy: giá trị hàm phụ thuộc vào giá trị của hàm với tham
số nhỏ hơn
F(n) = 1, nếu n = 1 (bước cơ sở)
F(n-1) + n, với n > 1 (bước đệ quy)
ĐỆ QUY
• Hàm được định nghĩa đệ quy
• Bước cơ sở: định nghĩa giá trị hàm với tham số cơ sở (nhỏ nhất)
• Bước đệ quy: giá trị hàm phụ thuộc vào giá trị của hàm với tham
số nhỏ hơn
F(n) = 1, nếu n = 1 (bước cơ sở)
F(n-1) + n, với n > 1 (bước đệ quy)
• Tập hợp được định nghĩa đệ quy

• Bước cơ sở: xác định các phần tử đầu tiên của tập hợp
• Bước đệ quy: Luật để xác định các phần tử khác thuộc tập hợp từ
những phần từ đã thuộc tập hợp từ trước
Bước cơ sở: 3S

Bước đệ quy: nếu x  S và y  S thì x + y  S
ĐỆ QUY
• Một chương trình con (thủ tục/hàm) Ví dụ: tổng 1 + 2 + … + n

đưa ra lời gọi đến chính nó nhưng
với dữ liệu đầu vào nhỏ hơn
int sum(int n) {
• Tình huống cơ sở if (n <= 1) return 1;
• Dữ liệu đầu vào nhỏ đủ để đưa int s = sum(n-1);
ra kết quả một cách trực tiếp return n + s;
mà không cần đưa ra lời gọi đệ }
quy
• Tổng hợp kết quả
• Kết quả của chương trình còn
được xây dựng từ kết quả của
lời gọi đệ quy và một số thông
tin khác
ĐỆ QUY
• Ví dụ: hằng số tổ hợp int C(int k, int n) {

if (k == 0 || k == n)
𝑛!
C(k, n) = return 1;
𝑘! 𝑛−𝑘 !
int C1 = C(k-1,n-1);
• C(k, n) = C(k-1, n-1) + int C2 = C(k,n-1);
C(k, n-1) return C1 + C2;
}
• Trường hợp cơ sở:
C(0, n) = C(n, n) = 1
THÁP HÀ NỘI
• Bài toán tháp Hà Nội
• Có n đĩa với kích thước khác
nhau và 3 cọc A, B, C
• Ban đầu n đĩa nằm ở cọc A
theo thứ tự đĩa nhỏ nằm trên
và đĩa lớn nằm dưới
A B C
THÁP HÀ NỘI
• Tìm cách chuyển n đĩa này từ
A B C
cọc A sang cọc B, sử dụng
cọc C làm trung gian theo
nguyên tắc
• Mỗi lần chỉ được chuyển 1
đĩa trên cùng từ 1 cọc
sang cọc khác
• Không được phép để xảy
ra tình trạng đĩa to nằm
bên trên đĩa nhỏ
THÁP HÀ NỘI
• Tìm cách chuyển n đĩa này từ
A B C
cọc A sang cọc B, sử dụng
cọc C làm trung gian theo
Lời giải
nguyên tắc
 B1: A → B
• Mỗi lần chỉ được chuyển 1
 B2: A → C
đĩa trên cùng từ 1 cọc
 B3: B → C
sang cọc khác
 B4: A → B
• Không được phép để xảy
 B5: C → A
ra tình trạng đĩa to nằm
 B6: C → B
bên trên đĩa nhỏ
 B7: A → B
THÁP HÀ NỘI
A B C A B C
move(n, A, B, C) {
if(n == 1) {
print(“Move 1 disk from A to B”)
}else{
move(n-1, A, C, B);
move(1, A, B, C);
move(n-1, C, B, A);
}
A B C }
ĐỆ QUY CÓ NHỚ
C(3,5)
C(2,4) C(3,4)
C(1,3) C(2,3) C(2,3) C(3,3)
C(0,2) C(1,2) C(1,2) C(2,2) C(1,2) C(2,2)
C(0,1) C(1,1) C(0,1) C(1,1) C(0,1) C(1,1)

ĐỆ QUY CÓ NHỚ
int m[MAX][MAX];
• Khắc phục tình trạng một chương
trình con với tham số xác định int C(int k, int n) {
được gọi đệ quy nhiều lần if (k == 0 || k == n)
m[k][n] = 1;
• Sử dụng bộ nhớ để lưu trữ kết else {
quả của một chương trình con với if(m[k][n] < 0){
tham số xác định m[k][n] = C(k-1,n-1) +
C(k,n-1);
• Bộ nhớ được khởi tạo với giá trị }
đặc biệt để ghi nhận mỗi chương }
trình con chưa được gọi lần nào return m[k][n];
}
• Địa chỉ bộ nhớ sẽ được ánh xạ int main() {
với các giá trị tham số của for(int i = 0; i < MAX; i++)
chương trình con for(int j = 0; j < MAX; j++)
m[i][j] = -1;
printf(“%d\n”,C(16,32));
}
ĐỆ QUY QUAY LUI
• Áp dụng để giải các bài toán liệt kê, bài toán tối ưu tổ hợp
• A = {(x1, x2, . . ., xn ) | xi  Ai,  i = 1,. . ., n}
• Liệt kê tất cả các bộ x A thoả mãn một thuộc tính P nào đó
• Thủ tục TRY(k):
• Thử các giá trị v có thể gán cho xk mà không vi phạm thuộc tính P
• Với mỗi giá trị hợp lệ v:
• Gán v cho xk
• Nếu k < n: gọi đệ quy TRY(k+1) để thử tiếp giá trị cho xk+1
• Nếu k = n: ghi nhận cấu hình
ĐỆ QUY QUAY LUI
TRY(k)
Begin
Foreach v thuộc Ak
if check(v,k) /* kiểm tra xem v có hợp lệ không */
Begin
xk = v;
if(k = n) ghi_nhan_cau_hinh;
else TRY(k+1);
End
End
Main()
Begin
TRY(1);
End
ĐỆ QUY QUAY LUI: liệt kê xâu nhị phân
• Mô hình hoá cấu hình:
• Mảng x[n] trong đó x[i] {0,1} là bít thứ i của xâu nhị phân
(i= 1, . . ., n)
X1 = 0 X1 = 1
X2 = 0 X2 = 1 X2 = 0 X2 = 1
X3 = 0 X3 = 1 X3 = 0 X3 = 1
X3 = 0 X3 = 1 X3 = 0 X3 = 1
void solution(){
• Mô hình hoá cấu hình: for(int i = 1; i<= n; i++)
• Mảng x[n] trong đó x[i] {0,1}

printf("%d ",x[i]);
printf("\n");
là bít thứ i của xâu nhị phân
}
(i= 1, . . ., n) int check(int v, int k){
return 1;
}
void Try(int k){
for(int v = 0; v <= 1; v++){
if(check(v,k)){
x[k] = v;
if(k == n) solution();
else Try(k+1);
}
}
}
int main() {
Try(1);
}
• Liệt kê các xâu nhị phân sao cho int TRY(int k) {

không có 2 bit 1 nào đứng cạnh for(int v = 0; v <= 1; v++){
nhau if(x[k-1] + v < 2){
x[k] = v;
if(k == n)
• Mảng x[n] trong đó x[i] {0,1} printSolution();
là bít thứ i của xâu nhị phân else TRY(k+1);
(i= 1, . . ., n) }
• Thuộc tính P: không có 2 bít 1 }
nào đứng cạnh nhau }
int main() {
x[0] = 0;
TRY(1);
}
ĐỆ QUY QUAY LUI: liệt kê tổ hợp
• Liệt kê các tổ hợp chập k của 1, 2, int TRY(int i) {

…, n for(int v = x[i-1]+1; v <= n-k+i;
v++){
x[i] = v;
• Mảng x[k] trong đó x[i] {1, . . ., if(i == k)
n} là phần tử thứ i của cấu hình printSolution();
tổ hợp (i = 1, . . ., k) else TRY(i+1);
• Thuộc tính P: x[i] < x[i+1], với }
mọi i = 1, 2, …, k-1 }
int main() {
x[0] = 0;
TRY(1);
}
ĐỆ QUY QUAY LUI: liệt kê hoán vị
void TRY(int i) {
• Liệt kê các hoán vị của 1, 2, …, n for(int v = 1; v <= n; v++){
• Mô hình hoá cấu hình: if(!m[v]) {
• Mảng x[1,. . . , n] trong đó x[i] {1, . x[i] = v;
m[v] = 1; // đánh dấu
. ., n} là phần tử thứ i của cấu hình
if(i == n)
hoán vị (i = 1, . . ., n) printSolution();
• Thuộc tính P: else TRY(i+1);
• x[i]  x[j], với mọi 1  i < j  n m[v] = 0;// khôi phục
}
• Mảng đánh dấu m[v] = 1 (0) nếu
}
giá trị v đã xuất hiện (chưa xuất }
hiện) trong cấu hình bộ phận, với
mọi v = 1, …, n void main() {
for(int v = 1; v <= n; v++)
m[v] = 0;
TRY(1);
}
ĐỆ QUY QUAY LUI: bài toán xếp hậu
• Xếp n quân hậu trên một bàn cờ quốc tế
sao cho không có 2 quân hậu nào ăn được
nhau
• Mô hình hoá 1 2 3 4
• x[1, . . ., n] trong đó x[i] là hàng của 1 X
quân hậu xếp trên cột i, với mọi i = 1, 2 X
…, n
• Thuộc tính P 3 X
• x[i]  x[j], với mọi 1  i < j  n 4 X
• x[i] + i  x[j] + j, với mọi 1  i < j  n
• x[i] – i  x[j] - j, với mọi 1  i < j  n Lời giải x = (3, 1, 4, 2)
ĐỆ QUY QUAY LUI: bài toán xếp hậu
int check(int v, int k) { void TRY(int k) {

// kiểm tra xem v có thể gán được for(int v = 1; v <= n; v++) {
// cho x[k] không if(check(v,k)) {
for(int i = 1; i <= k-1; i++) { x[k] = v;

if(k == n) printSolution();
if(x[i] == v) return 0;
else TRY(k+1);
if(x[i] + i == v + k) return 0;
}
if(x[i] – i == v – k) return 0;
}
}
}
return 1; void main() {
} TRY(1);
}
ĐỆ QUY QUAY LUI: bài toán Sudoku
• Điền các chữ số từ 1 đến 9 vào các 1 2 3 4 5 6 7 8 9

ô trong bảng vuông 9x9 sao cho
trên mỗi hàng, mỗi cột và mỗi bảng 4 5 6 7 8 9 1 2 3
vuông con 3x3 đều có mặt đầy đủ 1 7 8 9 1 2 3 4 5 6
chữ số từ 1 đến 9 2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2
0 1 2
• Mô hình hoá
1 2 3 4 5 6 7 8 9
• Mảng 2 chiều x[0..8, 0..8]
4 5 6 7 8 9 1 2 3
• Thuộc tính P
• x[i, j2]  x[i, j1], với mọi i = 7 8 9 1 2 3 4 5 6
0,…,8, và 0  j1 < j2  8 2 1 4 3 6 5 8 9 7
• x[i1, j]  x[i2, j], với mọi j = 3 6 5 8 9 7 2 1 4
0,…,8, và 0  i1 < i2  8
8 9 7 2 1 4 3 6 5
• x[3I+i1, 3J+j1]  x[3I+i2, 3J+j2],
với mọi I, J = 0,…, 2, và i1, j1, 5 3 1 6 4 2 9 7 8
i2, j2  {0,1, 2} sao cho i1  i2 6 4 2 9 7 8 5 3 1
hoặc j1  j2 9 7 8 5 3 1 6 4 2
• Thứ tự duyệt: từ ô (0,0), theo thứ tự từ

trái qua phải và từ trên xuống dưới 1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9
bool check(int v, int r, int c){ void TRY(int r, int c){
for(int i = 0; i <= r-1; i++) for(int v = 1; v <= 9; v++){
if(x[i][c] == v) return false; if(check(v,r,c)){
for(int j = 0; j <= c-1; j++)
x[r][c] = v;
if(x[r][j] == v) return false;
if(r == 8 && c == 8){
int I = r/3;
printSolution();
int J = c/3;
}else{
int i = r - 3*I;
if(c == 8) TRY(r+1,0);
int j = c - 3*J;
else TRY(r,c+1);
for(int i1 = 0; i1 <= i-1; i1++)
}
for(int j1 = 0; j1 <= 2; j1++)
if(x[3*I+i1][3*J+j1] == v) }
return false; }
for(int j1 = 0; j1 <= j-1; j1++) }
if(x[3*I+i][3*J+j1] == v)
return false; void main(){
return true; TRY(0,0);
} }
ĐỆ QUY QUAY LUI: bài tập
Cho số nguyên dương M, N và N số nguyên dương A1, A2, …, AN. Liệt

kê các nghiệm nguyên dương của phương trình
A1X1 + A2X2 + . . . + ANXN = M
ĐỆ QUY QUAY LUI: bài tập
1. Liệt kê tất cả các cách chọn ra k phần tử từ 1, 2, …, n sao cho

không có 2 phần tử nào đứng cạnh nhau cũng được chọn
2. Liệt kê tất cả các cách chọn ra k phần tử từ 1, 2, …, n sao cho
không có 3 phần tử nào đứng cạnh nhau cùng đồng thời được
chọn
3. Liệt kê tất cả các xâu nhị phân độ dài n trong đó không có 3 bit 1
nào đứng cạnh nhau
4. Liệt kê tất cả các cách phân tích số N thành tổng của các số
nguyên dương
5. Giải bài toán Sudoku, xếp hậu sử dụng kỹ thuật đánh dấu
6. Giải bài toán Sudoku với 1 số ô đã được điền từ trước
Thuật toán nhánh và cận
• Bài toán tối ưu tổ hợp

• Phương án x = (x1, x2, …, xn) trong đó xi  Ai cho trước
• Phương án thoả mãn ràng buộc C
• Hàm mục tiêu f(x) → min (max)
• Bài toán người du lịch

• Có n thành phố 1, 2, …, n. Chi phí đi từ thành phố i đến thành
phố j là c(i, j). Hãy tìm một hành trình xuất phát từ thành phố thứ
1, đi qua các thành phố khác, mỗi thành phố đúng 1 lần và quay
về thành phố 1 với tổng chi phí nhỏ nhất
• Mô hình hoá
• Phương án x = (x1, x2, …, xn) trong đó xi  {1, 2, …, n}
• Ràng buộc C: xi  xj,  1  i < j  n
• Hàm mục tiêu
f(x) = c(x1, x2) + c(x2, x3) + … + c(xn, x1) → min
• Duyệt toàn bộ: TRY(k)

Begin
• Liệt kê tất cả các phương án
Foreach v thuộc Ak
bằng phương pháp đệ quy
quay lui if check(v,k)
Begin
• Với mỗi phương án, tính
xk = v;
toán hàm mục tiêu
if(k = n)
• Giữ lại phương án có hàm ghi_nhan_cau_hinh;
mục tiêu nhỏ nhất
cập nhật kỷ lục f*;
else TRY(k+1);
End
End
Main()
Begin
TRY(1);
End
• Duyệt nhánh và cận: TRY(k) {
• Phương án bộ phận (a1,…, ak) trong đó Foreach v thuộc Ak
a1 gán cho x1,… ak gán cho xk if check(v,k) {

xk = v;
• Phương án (a1,…, ak, bk+1,…,bn) là một
if(k = n) {
phương án đầy đủ được phát triển từ
ghi_nhan_cau_hinh;
(a1,…,ak) trong đó bk+1 gán cho xk+1,…,
bn được gán cho xn cập nhật kỷ lục f*;
} {
if g(x1,…,xk) < f*
TRY(k+1);
}
}
}
Main()
{ f* = ;
TRY(1);
}

xk = v;
if(k = n) {
ghi_nhan_cau_hinh;
} {
• Với mỗi phương án bộ phận (x1,…, xk),
if g(x1,…,xk) < f*
hàm cận dưới g(x1,…, xk) có giá trị
TRY(k+1);
không lớn hơn giá trị hàm mục tiêu của
phương án đầy đủ phát triển từ }
(x1,…,xk) }
}
Main()
{ f* = ;
TRY(1);
}

xk = v;
if(k = n) {
ghi_nhan_cau_hinh;
} {
• Với mỗi phương án bộ phận (x1,…, xk),
if g(x1,…,xk) < f*
hàm cận dưới g(x1,…, xk) có giá trị
TRY(k+1);
không lớn hơn giá trị hàm mục tiêu của
phương án đầy đủ phát triển từ }
(x1,…,xk) }
• Nếu g(x1,…,xk)  f* thì không phát triển }

Main()
lời giải từ (x1,…,xk)
{ f* = ;
TRY(1);
}
Thuật toán nhánh và cận: bài toán TSP
• cm là chi phí nhỏ nhất trong số các x1

chi phí đi giữa 2 thành phố khác x2
nhau xn
• Phương án bộ phận (x1,…, xk) x3
• Chi phí bộ phận f = c(x1, x2) +
c(x2, x3) + … + c(xk-1, xk) Xn-1 . . .
• Hàm cận dưới
. . .
g(x1,…, xk) = f + cm(n-k+1) Xk-1
xk
Thuật toán nhánh và cận: bài toán TSP
void TRY(int k){ void process() {
for(int v = 1; v <= n; v++){ if(f + c[x[n]][x[1]] < f_min){
if(marked[v] == false){ f_min = f + c[x[n]][x[1]];
a[k] = v; }
f = f + c[a[k-1]][a[k]]; }
marked[v] = true; void main() {
if(k == n){ f_min = 9999999999;
process(); for(int v = 1; v <= n; v++)
}else{ marked[v] = false;
int g = f + cmin*(n-k+1); x[1] = 1; marked[1] = true;
if(g < f_min) TRY(2);
TRY(k+1); }
}
marked[v] = false;
f = f - c[a[k-1]][a[k]];
}
}
}
Thuật toán nhánh và cận: bài tập
• Bài toán dãy con tăng dần cực đại

• Đầu vào: dãy số nguyên a = a1, a2, …, an (gồm các phần tử đôi một
khác nhau)
• Đầu ra: tìm dãy con (bằng cách loại bỏ 1 số phần tử) của dãy đã cho
tăng dần có số lượng phần tử là lớn nhất (gọi là dãy con cực đại)
Thuật toán tham lam
• Được ứng dụng để giải một số bài toán tối ưu tổ hợp
• Đơn giản và tự nhiên
• Quá trình tìm lời giải diễn ra qua các bước
• Tại mỗi bước, ra quyết định dựa trên các thông tin hiện tại mà không
quan tâm đến ảnh hưởng của nó trong tương lai
• Dễ đề xuất, cài đặt
• Thường không tìm được phương án tối ưu toàn cục
• Lời giải được biểu diễn bởi tập S Greedy() {

S = {};
• C biểu diễn các ứng cử viên
while C   and
• select(C): chọn ra ứng cử viên tiềm not solution(S){
năng nhất x = select(C);
• solution(S): trả về true nếu S là lời giải C = C \ {x};

của bài toán if feasible(S  {x}) {
S = S  {x};
• feasible(S): trả về true nếu S không vi }
phạm ràng buộc nào của bài toán
}
return S;
}
• Bài toán tập đoạn không giao nhau
• Đầu vào: cho tập các đoạn thẳng X = {(a1, b1), . . . , (an, bn)} trong đó
ai < bi là toạ độ đầu mút của đoạn thứ i trên đường thẳng, với mọi i =
1, …, n.
• Đầu ra: Tìm tập con các đoạn đôi một không giao nhau có số đoạn
lớn nhất
• Bài toán tập đoạn không giao nhau
• Đầu vào: cho tập các đoạn thẳng X = {(a1, b1), . . . , (an, bn)} trong đó
ai < bi là toạ độ đầu mút của đoạn thứ i trên đường thẳng, với mọi i =
1, …, n.
• Đầu ra: Tìm tập con các đoạn đôi một không giao nhau có số đoạn
lớn nhất
Lời giải tối ưu là S = {(3,7), (9,11), (12,15), (17,19)}

• Tham lam 1 Greedy1() {
• Sắp xếp các đoạn theo thứ tự S = {};
không giảm của ai được danh L = Sắp xếp các đoạn trong X
sách L theo thứ tự không giảm của ai;
while (L  ) {
• Lặp lại thao tác sau cho đến khi L
(ac,bc) = chọn đoạn đầu tiên
không còn phần tử nào
trong L;
• Chọn đoạn (ac, bc) đầu tiên
Loại bỏ (ac,bc) khỏi L;
trong L và loại nó ra khỏi L
if feasible(S  {(ac,bc)}) {
• Nếu (ac, bc) không có giao S = S  {(ac,bc)};
nhau với đoạn nào trong lời }
giải thì đưa (ac, bc) vào lời giải
}
return S;
}
• Tham lam 1 không đảm bảo cho lời giải tối ưu, ví dụ
X = {(1,11), (2,5), (6,10)}
• Greedy 1 sẽ cho lời giải là {(1,11)} trong khi lời giải tối ưu là {(2,5),
(6,10)}
• Sắp xếp các đoạn theo thứ tự S = {};
không giảm của độ dài bi - ai được L = Sắp xếp các đoạn trong X
danh sách L theo thứ tự không giảm của
bi- ai;
while (L  ) {
• Chọn đoạn (ac, bc) đầu tiên
trong L;
• Nếu (ac, bc) không có giao nhau if feasible(S  {(ac,bc)}) {
với đoạn nào trong lời giải thì S = S  {(ac,bc)};
đưa (ac, bc) vào lời giải
}
}
return S;
}
• Tham lam 2 không đảm bảo cho lời giải tối ưu, ví dụ
X = {(1,5), (4,7), (6,11)}
• Greedy 1 sẽ cho lời giải là {(4,7)} trong khi lời giải tối ưu là {(1,5),
(6,11)}
• Sắp xếp các đoạn theo thứ tự không S = {};
giảm của bi được danh sách L L = Sắp xếp các đoạn trong X
theo thứ tự không giảm của bi;
while (L  ) {
• Chọn đoạn (ac, bc) đầu tiên trong L;
• Nếu (ac, bc) không có giao nhau if feasible(S  {(ac,bc)}) {
với đoạn nào trong lời giải thì S = S  {(ac,bc)};
đưa (ac, bc) vào lời giải }
• Tham lam 3 đảm bảo cho lời giải tối ưu }
return S;
}
Thuật toán tham lam: bài tập
• Có n công việc 1, 2, ..., n. Công việc i có thời hạn hoàn thành là d[i] và có
lợi nhuận khi được đưa vào thực hiện là p[i] (i=1,...,n). Biết rằng chỉ
được nhiều nhất 1 công việc được thực hiện tại mỗi thời điểm và khi thời
gian thực hiện xong mỗi công việc đều là 1 đơn vị. Hãy tìm cách chọn ra
các công việc để đưa vào thực hiện sao cho tổng lợi nhuận thu được là
nhiều nhất đồng thời mỗi công việc phải hoàn thành trước hoặc đúng
thời hạn.
Thuật toán tham lam: bài tập
• Ví dụ: có 4 công việc với thời hạn hoàn thành d[i] và lợi nhuận là p[i] được
cho như sau:
• Công việc 1: 4 20
• Khi đó giải pháp tối ưu là chọn công việc 1 và 3 để thực hiện với thứ tư
thực hiện là 3 trước rồi đến 1:
• công việc 3 bắt đầu thực hiện tại thời điểm 0 và kết thúc tại thời
điểm 1
• tiếp đó, công việc 1 được bắt đầu thực hiện tại thời điểm 1 và kết
thúc tại thời điểm 2
• tổng lợi nhuận thu được là 20 + 40 = 60
Thuật toán chia để trị
• Sơ đồ chung
• Chia bài toán xuất phát thành các bài toán con độc lập nhau
• Giải các bài toán con (đệ quy)
• Tổng hợp lời giải của các bài toán con để xây dựng lời giải của bài
toán xuất phát
Thuật toán chia để trị: tìm kiếm nhị phân
• Bài toán tìm kiếm nhị phân: bSearch(x, start, finish, y) {
cho dãy x[1..n] được sắp xếp if(start == finish) {
theo thứ tự tăng dần và 1 giá if(x[start] == y)
trị y. Tìm chỉ số i sao cho x[i] return start;
=y else return -1;
}else{
m = (start + finish)/2;
if(x[m] == y) return m;
if(x[m] < y)
return bSearch(x, m+1,finish,y);
else
return bSearch(x,start,m-1,y);
}
}
Thuật toán chia để trị: dãy con cực đại
• Bài toán dãy con cực đại int maxSeq(int* a, int l, int r){
• Đầu vào: dãy số nguyên if(l == r) return a[l];
a1, a2, …, an int max;

int mid = (l+r)/2;
• Đầu ra: tìm dãy con bao
int mL = maxSeq(a,l,mid);
gồm các phần tử liên tiếp
int mR = maxSeq(a,mid+1,r);
của dãy đã cho có tổng
cực đại int mLR = maxLeft(a,l,mid) +
maxRight(a,mid+1,r);
max = mL;
if(max < mR) max = mR;
if(max < mLR) max = mLR;
return max;
}
Thuật toán chia để trị: dãy con cực đại
int maxLeft(int* a, int l, int r){ void main() {
int max = -9999999; readData();
int s = 0; int rs = maxSeq(a,0,n-1);
for(int i = r; i >= l; i--){ printf(“result = %d”,rs);
s += a[i]; }
if(s > max) max = s;
}
return max;
}
int maxRight(int* a, int l, int r){
int max = -99999999;
int s = 0;
for(int i = l; i <= r; i++){
s += a[i];
if(s > max) max = s;
}
return max;
}
Thuật toán chia để trị: định lí thợ
• Chia bài toán xuất phát thành a bài toán procedure D-and-C(n) {
con, mỗi bài toán con kích thước n/b 1. if(n  n0)
2. xử lý trực tiếp
• T(n): thời gian của bài toán kích thước
3. else{
n
4. chia bài toán xuất phát
• Thời gian phân chia (dòng 4): D(n) thành a bài toán con kích thước n/b
• Thời gian tổng hợp lời giải (dòng 6): 5. gọi đệ quy a bài toán con
C(n) 6. tổng hợp lời giải
7. }
• Công thức truy hồi:
}
 1 , 𝑛 ≤ 𝑛0
T 𝑛 =ቐ 𝑛
𝑎𝑇 + 𝐶 𝑛 + 𝐷 𝑛 , 𝑛 > 𝑛0
𝑏
52
Thuật toán chia để trị: định lí thợ
• Độ phức tạp của thuật toán chia để trị (định lí thợ)

• Công thức truy hồi:
T(n) = aT(n/b) + cnk, với các hằng số a  1, b > 1, c > 0
• Nếu a > bk thì T(n) = (𝑛𝑙𝑜𝑔𝑏𝑎 )
• Nếu a = bk thì T(n) = (𝑛𝑘 𝑙𝑜𝑔𝑛) với logn = 𝑙𝑜𝑔2 𝑛
• Nếu a < bk thì T(n) = (𝑛𝑘 )
53
Thuật toán quy hoạch động
• Sơ đồ chung
• Chia bài toán xuất phát thành các bài toán con không nhất thiết độc
lập với nhau
• Giải các bài toán con từ nhỏ đến lớn, lời giải được lưu trữ lại vào 1
bảng
• Bài toán con nhỏ nhất phải được giải 1 cách trực tiếp
• Xây dựng lời giải của bài toán lớn hơn từ lời giải đã có của các bài
toán con nhỏ hơn (truy hồi)
• Số lượng bài toán con cần được bị chặn bởi đa thức của kích
thước dữ liệu đầu vào
• Phù hợp để giải hiệu quả một số bài toán tối ưu tổ hợp
54
• Bài toán dãy con cực đại

• Đầu vào: dãy số nguyên a1, a2, …, an
• Đầu ra: tìm dãy con bao gồm các phần tử liên tiếp của dãy đã cho có
tổng cực đại
• Phân chia
• Ký hiệu Pi là bài toán tìm dãy con bao gồm các phần tử liên tiếp có
tổng cực đại mà phần tử cuối cùng là ai, với mọi i = 1,…, n
• Ký hiệu Si là tổng các phần tử của lời giải của Pi,  i = 1,…, n
• S1 = a1
• Si = Si -1 + ai, nếu Si-1 > 0
ai, nếu Si-1  0
• Tổng các phần tử của dãy con cực đại của bài toán xuất phát là
max{S1, S2, …, Sn}
55
• Bài toán dãy con tăng dần cực đại

• Đầu vào: dãy số nguyên a = a1, a2, …, an (gồm các phần tử đôi một
khác nhau)
• Đầu ra: tìm dãy con (bằng cách loại bỏ 1 số phần tử) của dãy đã cho
tăng dần có số lượng phần tử là lớn nhất (gọi là dãy con cực đại)
56
• Phân chia void solve(){
• Ký hiệu Pi là bài toán tìm dãy con S[0] = 1;
cực đại mà phần tử cuối cùng là ai, rs = S[0];
với mọi i = 1,…, n for(int i = 1; i < n; i++){

S[i] = 1;
• Ký hiệu Si là số phần tử của lời giải
của Pi,  i = 1,…, n for(int j = i-1; j >= 0; j--){
if(a[i] > a[j]){
• S1 = 1
if(S[j] + 1 > S[i])
• Si = max{1, max{Sj +1| j < i  aj < S[i] = S[j] + 1;
ai }} }
• Số phần tử của dãy con cực đại }
của bài toán xuất phát là rs = S[i] > rs ? S[i] : rs;
max{S1, S2, …, Sn} }
printf("rs = %d\n",rs);
}
57
• Bài toán dãy con chung dài nhất

• Ký hiệu X = X1, X2, …, Xn, một dãy con của X là dãy được tạo ra
bằng việc loại bỏ 1 số phần tử nào đó của X đi
• Đầu vào
• Cho 2 dãy X = X1, X2, …, Xn và Y = Y1, Y2, …, Ym
• Đầu ra
• Tìm dãy con chung của X và Y có độ dài lớn nhất
58
• Bài toán dãy con chung dài nhất

• Phân rã
• Ký hiệu S(i, j) là độ dài dãy con chung dài nhất của dãy X1, …,
Xi và Y1, …, Yj, với  i = 1, …, n và j = 1, …, m
• Bài toán con nhỏ nhất
•  j = 1,…, m: S(1, j) = 1, nếu X1 xuất hiện trong Y1, …, Yj
0, ngược lại
•  i = 1,…, n: S(i, 1) = 1, nếu Y1 xuất hiện trong X1, …, Xi
0, ngược lại
• Tổng hợp lời giải
S(i, j) = S(i-1, j-1) + 1, nếu Xi = Yj
max{S(i-1, j), S(i, j-1)}
59
X 3 7 2 5 1 4 9
Y 4 3 2 3 6 1 5 4 9 7
1 2 3 4 5 6 7 8 9 10
1 0 1 1 1 1 1 1 1 1 1
2 0 1 1 1 1 1 1 1 1 2
3 0 1 2 2 2 2 2 2 2 2
4 0 1 2 2 2 2 3 3 3 3
5 0 1 2 2 2 3 3 3 3 3
6 1 1 2 2 2 3 3 4 4 4
7 1 1 2 2 2 3 3 4 5 5
60
void solve(){
rs = 0;
for(int i = 0; i <= n; i++) S[i][0] = 0;
for(int j = 0; j <= m; j++) S[0][j] = 0;
for(int i = 1; i <= n; i++){

for(int j = 1; j <= m; j++){
if(X[i] == Y[j]) S[i][j] = S[i-1][j-1] + 1;
else{
S[i][j] = S[i-1][j] > S[i][j-1] ?
S[i-1][j] : S[i][j-1];
}
rs = S[i][j] > rs ? S[i][j] : rs;
}
}
printf("result = %d\n",rs);
}
61
Thuật toán quy hoạch động: Bài tập
• Cho dãy a = a1, a2, . . ., an. Một dãy con của dãy a là một dãy thu được
bằng cách loại bỏ 1 số phần tử khỏi a. Tìm dãy con của a là một cấp số
cộng với bước nhảy bằng 1 có độ dài lớn nhất
62
Thank you
for your
attentions!
THUẬT TOÁN
Danh sách tuyến tính
Nội dung
• Định nghĩa danh sách tuyến tính

• Kiểu dữ liệu trừu tượng danh sách tuyến tính
• Mảng
• Danh sách liên kết
• Ngăn xếp
• Hàng đợi
2
Định nghĩa danh sách tuyến tính
• Các đối tượng được lưu trữ có thứ tự

• Các đối tượng có thể lặp lại giá trị
• Quan hệ trước-sau giữa các đối tượng
3
Kiểu dữ liệu trừu tượng danh sách tuyến tính
• Lưu trữ các đối tượng với quan hệ trước-sau

• Kí hiệu:
• L: danh sách
• x: đối tượng (phần tử của danh sách)
• p: kiểu vị trí
• END(L): hàm trả về vị trí sau vị trí của phần tử cuối cùng của danh
sách L
4
Kiểu dữ liệu trừu tượng danh sách tuyến tính
• Thao tác
• Insert(x, p, L): chèn phần tử x vào vị trí p trên danh sách L
• Locate(x, L): trả về vị trí của phần tử x trên danh sách L
• Retrieve(p, L): trả về phần tử ở vị trí p trong danh sách L
• Delete(p, L): loại bỏ phần tử ở vị trí p trên danh sách L
• Next(p, L): trả về vị trí tiếp theo của p trên danh sách L
• Prev(p, L): trả về vị trí trước của p trên danh sách L
• MakeNull(L): thiết lập danh sách L về danh sách rỗng
• First(L): trả về vị trí đầu tiên của danh sách L
5
Kiểu mảng
• Các đối tượng được cấp phát liên tiếp nhau trong bộ nhớ
• Truy cập các đối tượng thông qua chỉ số (kiểu vị trí chính là giá trị
nguyên xác định chỉ số)
• Việc thêm hoặc loại bỏ phần tử khỏi mảng cần thiết phải dồn mảng
6
Kiểu mảng
• Tổ chức dữ liệu void insert(int x, int p) {

for(int j = n-1; j >= p; j--)
• int a[100000]; // bộ nhớ lưu trữ
a[j+1] = a[j];
• int n; // số phần tử của mảng a[p] = x; n = n + 1;
(bắt đầu từ chỉ số 0) }
void delete(int p) {
for(int j = p+1; j <= n-1; j++)
a[j-1] = a[j];
n = n – 1;
}
int retrieve(int p) {
return a[p];
}
7
Kiểu mảng
int locate(int x) {// vi trí đầu tiên của
x trong danh sách
• Tổ chức dữ liệu for(int j= 0; j <= n-1; j++)
• int a[100000]; // bộ nhớ lưu if(a[j] == x) return j;
trữ return -1;
• int n; // số phần tử của }

mảng (bắt đầu từ chỉ số 0) void makeNull() {
n = 0;
}
int next(int p) {
if(0 <= p && p < n-1) return p+1;
return -1;
}
int prev(int p) {
if(p > 0 && p <= n-1) return p-1;
return -1;
}
8
Con trỏ và danh sách liên kết đơn
• Con trỏ: địa chỉ của biến
• int* p: p là con trỏ trỏ đến 1 biến int. Giá trị của p xác định địa chỉ của
biến
• int a; int* p = &a;// p trỏ vào biến a
• Kiểu cấu trúc
typedef struct TNode{
int a;
double b;
char* s;
}TNode;
• TNode* q: q là con trỏ trỏ đến 1 biến có kiểu TNode
9
Con trỏ và danh sách liên kết đơn
 q->a: truy nhập đến thành phần a của int main() {

kiểu cấu trúc int a = 123;
 q = (TNode*)malloc(sizeof(TNode)): int* p;
cấp phát bộ nhớ cho 1 kiểu TNode và q p = &a;
trỏ vào vùng nhớ được cấp phát *p = 456;

printf(“a = %d\n”,a);
}
10
Danh sách liên kết đơn
• Mỗi phần tử, ngoài trường dữ liệu, có thêm con trỏ để trỏ đến phần tử
tiếp theo
struct Node{
int value;
Node* next;
};
Node* head;
head
5 9 3 ... 6 4
11
h
5 9 3 ... 6 4
void printList(Node* h){
Node* p = h;
p while(p != NULL){
printf(“%d “,p->value);
p = p->next;
 Tìm kiếm
}
 cần duyệt lần lượt từ phần
}
tử đầu tiên của danh sách Node* findLast(Node* h){
 Dùng con trỏ next để truy Node* p = h;
cập đến phần tử tiếp theo while(p != NULL){
if(p->next == NULL) return p;
p = p->next;
}
return NULL;
}
12
h
5 9 3 ... 6 4
Node* makeNode(int x){
Node* q = new Node;
p
q->value = x; q->next = NULL;
return q;
 Chèn 1 phần tử mới có value }
bằng x vào sau phần tử được
trỏ bởi p Node* insertAfter(Node* h, Node* p, int x){
if(p == NULL) return h;
Node* q = makeNode(x);
if(h == NULL) return q;
q->next = p->next;
p->next = q;
return h;
}
13
h
5 9 3 ... 6 4
h
5 9 3 ... 6 4
 Chèn 1 phần tử mới có Node* insertLast(Node* h, int x){
value bằng x vào cuối Node* q = makeNode(x); x

if(h == NULL)
danh sách có con trỏ
return q;
đầu là h
Node* p = h;
while(p->next != NULL)
p = p->next;
p->next = q;
return h;
}
14
h
5 9 3 ... 6 4
 Tìm một phần tử đầu tiên kể Node* locate(Node* h, int x){
từ trái có value bằng x trên Node* p = h;

while(p != NULL){
danh sách có con trỏ đầu là h
if(p->value == x) return p;
p = p->next;
}
return NULL;
}
15
h
5 9 3 ... 6 4
p
Node* prev(Node* h, Node* p){
 Tìm một phần tử đứng trước Node* q = h;
một phần tử được trỏ bởi con while(q != NULL){
trỏ p if(q->next == p) return q;
q = q->next;
}
return NULL;
}
16
h
5 9 3 ... 6 4
Node* insertAt(Node* h, Node* p, int x){

p Node* pp = prev(h,p);
if(pp == NULL && p != NULL) return h;
Node* q = new Node;
 Chèn 1 phần tử mới có value q->value = x; q->next = NULL;
bằng x vào trước phần tử if(pp == NULL){
được trỏ bởi p if(h == NULL)
return q;
q->next = h;
return q;
}
q->next = p; pp->next = q;
return h;
}
17
h
5 9 3 ... 6 4
p
Node* insertAtRecursive(Node* h, Node* p, int x){
 Chèn 1 phần tử mới có value
if(p == NULL) return h;
bằng x vào trước phần tử
if(h == NULL || p == h){
được trỏ bởi p (đệ quy)
return makeNode(x);
}else{
h->next = insertAtRecursive(h->next,p,x);
return h;
}
}
18
h
5 9 3 ... 6 4
p Node* remove(Node* h, Node* p){

if(h == NULL || p == NULL) return h;
 Xóa phần tử được trỏ bởi con if(h == p){

h = h->next;
trỏ p
delete p;
return h;
}else{
h->next = remove(h->next,p);
return h;
}
}
19
h
5 9 3 ... 6 4
Node* sum(Node* h){

p Node* p = h;
int S = 0;
 Tính tổng giá trị của các phần while(p != NULL) {
tử của một danh sách liên kết S = S + p->value;
được trỏ bởi h p = p->next;
}
return S;
}
int sumRecursive(Node* h){
if(h == NULL) return 0;
return h->value + sumRecursive(h->next);
}
20
Danh sách liên kết đôi
struct DNode{
int val;
DNode* prev; prev next
DNode* next;
}; val
DNode* first;
DNode* last;
first last
3 3 ... 3
21
first last
3 3 ... 3
p
DNode* makeNode(int v){
 Tạo mới phần tử DNode* p = new DNode;
p->val = v;
p->next = NULL;
p->prev = NULL;
return p;
}
22
p
first last
3 3 ... 3
void remove(DNode* p) {
if(p == NULL) return;
if(first == last && p == first){
first = NULL; last = NULL; delete p;
}
if(p == first){
first = p->next; first->prev = NULL;
delete p; return;
}
if(p == last){
last = p->prev; last->next = NULL;
delete p; return;
}
p->prev->next = p->next; p->next->prev = p->prev; delete p;
}
23
first last
3 3 ... 3
p
void insertLast(int x){
DNode* q = makeNode(x);
if(first == NULL && last == NULL){
first = q;
last = q;
return;
}
q->prev = last;
last->next = q;
last = q;
}
24
Thư viện C++
• Kiểu list:
http://www.cplusplus.com/refer
ence/list/list/ #include <list>
#include <stdio.h>
• Phương thức using namespace std;
• push_front()
• push_back() int main(){
list<int> L;
• pop_front() for(int i = 1; i <= 10; i++)
• pop_back() L.push_back(i);
list<int>::iterator it;
• size() for(it = L.begin(); it != L.end();
• clear() it++){
• erase() int x = *it;
printf("%d ",x);
}
}
25
Ngăn xếp (Stack)
• Danh sách các đối tượng

• Thao tác thêm mới và loại bỏ được thực hiện ở 1 đầu (đỉnh hay top)
của danh sách (Last In First Out – LIFO)
• Thao tác
• Push(x, S): chèn 1 phần tử x vào ngăn xếp
• Pop(S): lấy ra 1 phần tử khỏi ngăn xếp
• Top(S): truy cập phần tử ở đỉnh của ngăn xếp
• Empty(S): trả về true nếu ngăn xếp rỗng
26
Ngăn xếp (Stack)
• Ví dụ: kiểm tra tính hợp lệ của dãy ngoặc
• [({})](): hợp lệ
• ([} {}): không hợp lệ
27
Ngăn xếp (Stack)
• [({})](): hợp lệ
• Thuật toán:
• Sử dụng 1 ngăn xếp S
• Duyệt dãy ngoặc từ trái qua phải
• Nếu gặp ngoặc mở thì đẩy vào S
• Nếu gặp ngoặc đóng
• Nếu S rỗng thì trả về FALSE
• Nếu S còn phần tử thì lấy 1 ngoặc mở ra khỏi S, kiểm tra
đối sánh với ngoặc đóng: nếu ngoặc mở và đóng không
tương ứng với nhau thì trả về FALSE
• Kết thúc việc duyệt, nếu S vẫn còn phần tử thì trả về FALSE,
ngược lại thì trả về TRUE
28
Ngăn xếp (Stack)

• [({})](): hợp lệ
#include <stack>
#include <stdio.h>
using namespace std;
bool match(char a, char b){

if(a == '(' && b == ')') return true;
if(a == '{' && b == '}') return true;
if(a == '[' && b == ']') return true;
return false;
}
29
Ngăn xếp (Stack)
• Ví dụ: kiểm tra tính hợp lệ bool solve(char* x, int n){
của dãy ngoặc stack<char> S;

for(int i = 0; i <= n-1; i++){
• [({})](): hợp lệ if(x[i] == '[' || x[i] == '(' || x[i] == '{'){
• ([} {}): không hợp lệ S.push(x[i]);
}else{
if(S.empty()){
return false;
}else{
char c = S.top(); S.pop();
if(!match(c,x[i])) return false;
}
}
}
return S.empty();
}
int main() {
bool ok = solve(“[({})]()”,8);
}
30
Hàng đợi (Queue)
• Danh sách các đối tượng với 2 đầu head và tail

• Thao tác thêm mới được thực hiện ở tail
• Thao tác loại bỏ được thực hiện ở head (First In First Out – FIFO)
• Thao tác
• Enqueue(x, Q): chèn 1 phần tử x vào hàng đợi
• Dequeue(Q): lấy ra 1 phần tử khỏi hàng đợi
• Empty(Q): trả về true nếu hàng đợi rỗng
31
• Bài toán rót nước

• Có 1 bể chứa nước (vô hạn)
• Có 2 cốc với dung tích là a, b (nguyên dương) lít
• Tìm cách đong đúng c (nguyên dương) lít nước
32
• Bài toán rót nước: a = 6, b = 8, c = 4
Bước Thực hiện Trạng thái

1 Đổ đầy nước vào cốc 1 (6,0)
2 Đổ hết nước từ cốc 1 sang cốc 2 (0,6)
4 Đổ nước từ cốc 1 vào đầy cốc 2 (4,8)
33
• Bài toán rót nước: a = 4, b = 19, c = 21
Bướ Thực hiện Trạng thái

c
10 Đổ nước từ cốc 1 vào đầy cốc 2 (1,19)
11 Đổ hết nước ở cốc 2 ra ngoài (1,0)
34
• Bài toán rót nước: a = 4, b = 19, c = 21 (tiếp)
Bướ Thực hiện Trạng thái

c
35
• Thiết kế thuật toán và cấu trúc dữ liệu
• Trạng thái là bộ (x, y): lượng nước có trong cốc 1 và 2
• Trạng thái ban đầu (0, 0)
• Trạng thái kết thúc: x = c hoặc y = c hoặc x + y = c
• Chuyển trạng thái
• (1) Đổ đầy nước từ bể vào cốc 1: (a, y)
• (2) Đổ đầy nước từ bể vào cốc 2: (x, b)
• (3) Đổ hết nước từ cốc 1 ra ngoài: (0, y)
• (4) Đổ hết nước từ cốc 2 ra ngoài: (x, 0)
• (5) Đổ nước từ cốc 1 vào đầy cốc 2: (x + y - b, b), nếu x + y  b
• (6) Đổ hết nước từ cốc 1 sang cốc 2: (0, x + y), nếu x + y  b
• (7) Đổ nước từ cốc 2 vào đầy cốc 1: (a, x + y - a), nếu x + y  a
• (8) Đổ hết nước từ cốc 2 sang cốc 1: (x + y, 0), nếu x + y  a
36
• Đưa (0,0) vào hàng đợi
(0,0)
• Lấy (0,0) ra và đưa (6,0), (0,8) vào hàng đợi

(0,0) (6,0) (0,8)
• Lấy (6,0) ra và đưa (0,6) và (6,8) vào hàng đợi

(0,0) (6,0) (0,8) (0,6) (6,8)
• Lấy (0,8) ra và đưa (6,2) vào hàng đợi

(0,0) (6,0) (0,8) (0,6) (6,8) (6,2)
37
• Đưa (0,6) ra và đưa (6,6) vào hàng đợi

(0,0) (6,0) (0,8) (0,6) (6,8) (6,2) (6,6)
• Lấy (6,8) ra và không đưa trạng thái mới nào vào hàng
đợi
(0,0) (6,0) (0,8) (0,6) (6,8) (6,2) (6,6)

(0,0) (6,0) (0,8) (0,6) (6,8) (6,2) (6,6) (0,2)

(0,0) (6,0) (0,8) (0,6) (6,8) (6,2) (6,6) (0,2) (4,8)
38
• Thiết kế thuật toán và cấu trúc dữ liệu

• Hàng đợi Q để ghi nhận các trạng thái được sinh ra
• Mảng 2 chiều để đánh dấu trạng thái đã được xét đến
• visited[x][y] = true, nếu trạng thái (x, y) đã được sinh ra
• Ngăn xếp để in ra chuỗi các hành động để đạt được kết quả
• Danh sách L để lưu các con trỏ trỏ đến các vùng nhớ được cấp
phát động (phục vụ cho việc thu hồi bộ nhớ khi kết thúc chương
trình)
39
#include <stdio.h>
• Khai báo cấu trúc dữ liệu #include <stdlib.h>
#include <queue>
#include <stack>
#include <list>
struct State{
int x;
int y;
char* msg;// action to generate current state
State* p;// pointer to the state generating current state
};
bool visited[10000][10000];
queue<State*> Q;
list<State*> L;
State* target;
int a,b,c;
40
void initVisited(){
• Các hàm khởi tạo mảng for(int x = 0; x < 10000; x++)
đánh dấu, đánh dấu trạng for(int y = 0; y < 10000; y++)
thái, kiểm tra trạng thái visited[x][y] = false;
đích, giải phóng bộ nhớ }
bool reachTarget(State* S){
return S->x == c || S->y == c ||
S->x + S->y == c;
}
void markVisit(State* S){
visited[S->x][S->y] = true;
}
void freeMemory(){
list<State*>::iterator it;
for(it = L.begin(); it != L.end(); it++){
delete *it;
}
}
41
bool genMove1Out(State* S){

• Hàm sinh trạng thái bởi if(visited[0][S->y]) return false;
hành động (3): đổ hết State* newS = new State;
nước từ cốc 1 ra ngoài newS->x = 0;
newS->y = S->y;
newS->msg = "Do het nuoc o coc 1 ra ngoai";
newS->p = S;
Q.push(newS); markVisit(newS);
L.push_back(newS);
if(reachTarget(newS)){
target = newS;
return true;
}
return false;
}
42
bool genMove2Out(State* S){

• Hàm sinh trạng thái bởi if(visited[S->x][0]) return false;
nước từ cốc 2 ra ngoài newS->x = S->x;
newS->y = 0;
newS->msg = "Do het nuoc o coc 2 ra ngoai";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
43
bool genMove1Full2(State* S){
if(S->x+S->y < b) return false;
• Hàm sinh trạng thái bởi if(visited[S->x + S->y - b][b]) return false;
hành động (5): đổ nước từ State* newS = new State;
cốc 1 vào đầy cốc 2 newS->x = S->x + S->y - b;
newS->y = b;
newS->msg = "Do nuoc tu coc 1 vao day coc 2";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
44
bool genMove2Full1(State* S){
if(S->x+S->y < a) return false;
• Hàm sinh trạng thái bởi
if(visited[a][S->x + S->y - a]) return false;
hành động (7): đổ nước từ
State* newS = new State;
cốc 2 vào đầy cốc 1
newS->x = a;
newS->y = S->x + S->y - a;
newS->msg = "Do nuoc tu coc 2 vao day coc 1";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
45
bool genMoveAll12(State* S){
if(S->x + S->y > b) return false;
• Hàm sinh trạng thái bởi if(visited[0][S->x + S->y]) return false;
nước từ cốc 1 sang cốc 2 newS->x = 0;
newS->y = S->x + S->y;
newS->msg = "Do het nuoc tu coc 1 sang coc 2";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
46
bool genMoveAll21(State* S){
if(S->x + S->y > a) return false;
• Hàm sinh trạng thái bởi if(visited[S->x + S->y][0]) return false;
nước từ cốc 2 sang cốc 1 newS->x = S->x + S->y;
newS->y = 0;
newS->msg = "Do het nuoc tu coc 2 sang coc 1";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
47
bool genMoveFill1(State* S){
if(visited[a][S->y]) return false;
• Hàm sinh trạng thái bởi
State* newS = new State;
hành động (1): đổ đầy
newS->x = a;
nước từ bể vào cốc 1
newS->y = S->y;
newS->msg = "Do day nuoc vao coc 1";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
}
48
bool genMoveFill2(State* S){
if(visited[S->x][b]) return false;
• Hàm sinh trạng thái bởi State* newS = new State;
hành động (2): đổ đầy newS->x = S->x;
nước từ bể vào cốc 2 newS->y = b;
newS->msg = "Do day nuoc vao coc 2";
newS->p = S;
L.push_back(newS);
target = newS;
return true;
}
return false;
49
void print(State* target){
printf("-----------RESULT------------\n");
• Hàm in chuỗi hành động if(target == NULL)
để thu được kết quả printf("Khong co loi giai!!!!!!!");
State* currentS = target;
stack<State*> actions;
while(currentS != NULL){
actions.push(currentS);
currentS = currentS->p;
}
while(actions.size() > 0){
currentS = actions.top();
actions.pop();
printf("%s, (%d,%d)\n",
currentS->msg,currentS->x,
currentS->y);
}
}
50
• Khởi tạo, sinh trạng thái void solve(){
ban đầu và đưa vào hàng initVisited();
đợi // sinh ra trang thai ban dau (0,0) va dua vao Q
State* S = new State;
• Tại mỗi bước, lấy 1 trạng
S->x = 0; S->y = 0; S->p = NULL;
thái ra khỏi hàng đợi, sinh
Q.push(S); markVisit(S);
trạng thái mới và đưa vào
while(!Q.empty()){
hàng đợi
State* S = Q.front(); Q.pop();
if(genMove1Out(S)) break;
if(genMove2Out(S)) break;
if(genMove1Full2(S)) break;
if(genMoveAll12(S)) break;
if(genMove2Full1(S)) break;
if(genMoveAll21(S)) break;
if(genMoveFill1(S)) break;
if(genMoveFill2(S)) break;
}
}
51
int main(){
a = 4;
• Hàm main
b = 7;
• Thử nghiệm với bộ dữ liệu: a = c = 9;
4, b = 7, c = 9 target = NULL;
solve();
print(target);
freeMemory();
}
52
THUẬT TOÁN
Cây
1
Nội dung
• Định nghĩa cây

• Các khái niệm trên cây
• Các phép duyệt cây
• Cấu trúc lưu trữ
• Các thao tác trên cây
2
Cây
10
... 11 1 3
5 4 8 2 7
6 9
3
Định nghĩa cây
 Cấu trúc lưu trữ các đối tượng có
quan hệ phân cấp
 Định nghĩa đệ quy
r
 Bước cơ sở: r là 1 nút, cây T
có nút gốc là r
 Bước đệ quy:
 Giả sử T1, T2, …, Tk là các r1 r2 ... rk
cây có gốc là r1, r2, …, rk
 Nút r
 Liên kết các nút r1, r2, .., rk
như la nút con của r sẽ tạo
ra cây T
4
Các ứng dụng của cây: Cây gia phả
• Cây gia phả của các nhà toán học dòng họ Bernoulli
Nikolaus
1623-1708
Johan I Nikolaus Jacob I

1667-1748 1662-1716 1654-1705
Nikolaus II Daniel Johan II Nikolaus I

1695-1726 1700-1782 1710-1790 1687-1759
Johan III Jacob II

1746-1807 1759-1789
5
Các ứng dụng của cây
Mục lục sách Cây thư mục
6
Các ứng dụng của cây: cây biểu thức
+
/ /
1 3 * 4
6 7
1/3 + 6*7 / 4
7
Các khái niệm trên cây
• Đường đi: dãy các nút x1, x2, …, xq trong đó xi là cha của xi+1, i = 1, 2,
…, q-1. Độ dài đường đi là q-1
• Nút lá: không có nút con
• Nút trong: có nút con
• Nút anh em: 2 nút u và v là 2 nút anh em nếu có cùng nút cha
• Tổ tiên: nút u là tổ tiên của v nếu có đường đi từ u đến v
• Con cháu: nút u là con cháu của v nếu v là tổ tiên của u
• Độ cao: độ cao của 1 nút là độ dài đường đi dài nhất từ nút đó đến nút
lá + 1
• Độ sâu: độ sâu của 1 nút v là độ dài đường đi duy nhất từ nút gốc tới
nút đó + 1
8
• Gốc: nút không có cha (ví dụ: nút A)
• Anh em: nút có cùng cha (ví dụ: B, C, D là anh em; I, J, K là anh em; E và F là anh
em; G và H là anh em)
• Nút trong: nút có ít nhất 1 con (ví dụ: các nút màu xanh dương: A, B, C, F)
• Nút ngoài (lá ): nút không có con (ví dụ: các nút xanh lá: E, I, J, K, G, H, D)
• Tổ tiên của 1 nút: là các nút cha / ông bà / cụ.. của nút đó.
• Hậu duệ của 1 nút: là các nút con/cháu/chắt… của nút đó
• Cây con của 1 nút: là cây có gốc là con của nút đó A
Con của B:
• E, F B C D
Cha của E:
• B
Tổ tiên của F: E F G H
• B, A
Hậu duệ của B: Cây con của nút A
• E, F, I, J, K I J K
9
sâu=1 A cao=3
Chiều cao của cây= 3
sâu=2 sâu=2 C
B D sâu=2
cao=1 cao=2 cao=1
sâu=3 E sâu=3 F
cao=1 cao=1
10
Phép duyệt cây
• Thăm các nút của 1 cây theo 1 thứ tự nào đó

• 3 phép duyệt cây cơ bản
• Duyệt theo thứ tự trước
• Duyệt theo thứ tự giữa
• Duyệt theo thứ tự sau
• Xét cây T có cấu trúc
• Nút gốc r
• Cây con T1 (gốc r1), T2 (gốc r2), …, Tk (gốc rk) theo thứ tự từ trái qua
phải
11
Phép duyệt cây
• Duyệt theo thứ tự trước

• Thăm nút gốc preOrder(r){
if(r = NULL) return;
• Duyệt cây T1 theo thứ tự trước
visit(r);
• Duyệt cây T2 theo thứ tự trước
for each p = r1, r2, .., rk {
• … preOrder(p);
• Duyệt cây Tk theo thứ tự trước }
}
12
Phép duyệt cây
• Duyệt theo thứ tự giữa

• Duyệt cây T1 theo thứ tự giữa inOrder(r){
• Thăm nút gốc r
inOrder(r1);
• Duyệt cây T2 theo thứ tự giữa
visit(r);
• … for each p = r2, .., rk {
• Duyệt cây Tk theo thứ tự giữa inOrder(p);
}
}
13
Phép duyệt cây
• Duyệt theo thứ tự sau

• Duyệt cây T1 theo thứ tự sau postOrder(r){
• Duyệt cây T2 theo thứ tự sau
for each p = r1, r2, .., rk {
• …
postOrder(p);
• Duyệt cây Tk theo thứ tự sau }
• Thăm nút gốc visit(r);
}
14
Cấu trúc dữ liệu biểu diễn cây
• Mảng:
• Giả sử các nút trên cây được định danh 1, 2, …, n
• a[1..n] trong đó a[i] là nút cha của nút i
• Cấu trúc lưu trữ đơn giản, tuy nhiên khó cài đặt rất nhiều thao tác
trên cây
• Con trỏ liên kết: với mỗi nút, lưu 2 con trỏ
• Con trỏ trỏ đến nút con trái nhất
• Con trỏ trỏ đến nút anh em bên phải
15
Cấu trúc dữ liệu biểu diễn cây
struct Node{
int id;
Node* leftMostChild;// con tro tro den nut con trai nhat
Node* rightSibling;// con tro tro den nut anh em ben phai
};
Node* root;// con tro tro den nut goc
16
Thao tác trên cây
• find(r, id): tìm nút có định danh là id trên cây có gốc là r

• insert(r, p, id): tạo một nút có định danh là id, chèn vào cuối danh sách
nút con của nút p trên cây có gốc là r
• height(r, p): trả về độ cao của nút p trên cây có gốc là r
• depth(r, p): trả về độ sâu của nút p trên cây có gốc là r
• parent(r, p): trả về nút cha của nút p trên cây có gốc r
• count(r): trả về số nút trên cây có gốc là r
• countLeaves(r): trả về số nút lá trên cây có gốc là r
17
• Tìm một nút có nhãn cho trước Node* find(Node* r, int v){
trên cây if(r == NULL) return NULL;
if(r->id == v) return r;
Node* p = r->leftMostChild;
while(p != NULL){
Node* h = find(p,v);
if(h != NULL) return h;
p = p->rightSibling;
}
return NULL;
}
18
• Duyệt theo thứ tự trước void preOrder(Node* r){

if(r == NULL) return;
printf("%d ",r->id);
while(p != NULL){
preOrder(p);
}
}
19
• Duyệt theo thứ tự giữa void inOrder(Node* r){

inOrder(p);
if(p != NULL)
while(p != NULL){
inOrder(p);
}
}
20
• Duyệt theo thứ tự sau void postOrder(Node* r){

while(p != NULL){
postOrder(p);
}
}
21
• Đếm số nút trên cây int count(Node* r){

if(r == NULL) return 0;
int s = 1;
while(p != NULL){
s += count(p);
}
return s;
}
22
• Đếm số nút lá trên cây int countLeaves(Node* r){

int s = 0;
if(p == NULL) s = 1;
while(p != NULL){
s += countLeaves(p);
}
return s;
}
23
• Độ cao của một nút int height(Node* p){

if(p == NULL) return 0;
int maxh = 0;
Node* q = p->leftMostChild;
while(q != NULL){
int h = height(q);
if(h > maxh) maxh = h;
q = q->rightSibling;
}
return maxh + 1;
}
24
int depth(Node* r, int v, int d){
// d la do sau cua nut r
• Độ sâu của một nút if(r == NULL) return -1;
if(r->id == v) return d;
while(p != NULL){
if(p->id == v) return d+1;
int dv = depth(p,v,d+1);
if(dv > 0) return dv;
}
return -1;
}
int depth(Node* r, int v){
return depth(r,v,1);
}
25
• Tìm nút cha của một nút Node* parent(Node* p, Node* r){
if(r == NULL) return NULL;
Node* q = r->leftMostChild;
while(q != NULL){
if(p == q) return r;
Node* pp = parent(p, q);
if(pp != NULL) return pp;
q = q->rightSibling;
}
return NULL;
}
26
Cây nhị phân
• Mỗi nút có nhiều nhất 2 nút con

• Hai con trỏ xác định nút con trái và nút con bên phải
struct BNode{
int id;
BNode* leftChild; // con trỏ đến nút con trái
BNode* rightChild;// con trỏ đến nút con phải
};
• leftChild = NULL: có nghĩa nút hiện tại không có con trái
• rightChild = NULL: có nghĩa nút hiện tại không có con phải
• Có thể áp dụng sơ đồ thuật toán trên cây tổng quát cho trường hợp
cây nhị phân
27
Cây nhị phân
• Phân loại
10 10 10
1 2 1 2 1 2
5 6 4 7 5 6 5 4 7
Cây nhị phân hoàn chỉnh Cây nhị phân đầy đủ Cây nhị phân cân bằng
28
Thao tác trên cây nhị phân
• Duyệt theo thứ tự giữa void inOrder(BNode* r) {

• Duyệt theo thứ tự giữa cây if(r == NULL) return;
con bên trái inOrder(r->leftChild);
• Thăm nút gốc printf("%d ",r->id);

inOrder(r->rightChild);
• Duyệt theo thứ tự giữa cây
}
con bên phải
29
• Duyệt theo thứ tự trước void preOrder(BNode* r) {

• Thăm nút gốc if(r == NULL) return;
preOrder(r->leftChild);
con bên trái
preOrder(r->rightChild);
}
con bên phải
30
• Duyệt theo thứ tự sau void postOrder(BNode* r) {

• Duyệt theo thứ tự giữa cây if(r == NULL) return;
con bên trái postOrder(r->leftChild);
• Duyệt theo thứ tự giữa cây postOrder(r->rightChild);
con bên phải printf("%d ",r->id);
• Thăm nút gốc

}
31
• Đếm số nút trên cây nhị phân int count(BNode* r) {

return 1 + count(r->leftChild) +
count(r->rightChild);
}
32
Cây biểu thức
• Là cây nhị phân

• Nút giữa biểu diễn toán tử
• Nút lá biểu diện các toán hạng *
(biến, hằng)
• Biểu thức trung tố: dãy các nút
được thăm trong phép duyệt cây - +
theo thứ tự giữa:
(5 - x/y) * (a + 7)
5 / a 7
• Biểu thức hậu tố: dãy các nút
được thăm trong phép duyệt cây
theo thứ tự sau:
5 x y / - a 7 + * x y
33
Tính giá trị của biểu thức hậu tố
• Khởi tạo stack S ban đầu rỗng
34

• Duyệt các phần tử của biểu thức hậu tố từ trái qua phải
35

• Nếu gặp toán hạng thì đẩy toán hạng đó vào S
36

• Nếu gặp toán tử op thì lần lượt lấy 2 toán hạng A và B ra khỏi S, thực
hiện C = B op A, và đẩy C vào S
37

• Nếu gặp toán tử op thì lần lượt lấy 2 toán hạng A và B ra khỏi S, thực
hiện C = B op A, và đẩy C vào S
• Khi biểu thức hậu tố được duyệt xong thì giá trị còn lại trong S chính là
giá trị của biểu thức đã cho
38
VÀ THUẬT TOÁN
Sắp xếp
NỘI DUNG
• Tổng quan bài toán sắp xếp
• Thuật toán sắp xếp lựa chọn
• Thuật toán sắp xếp chèn
• Thuật toán sắp xếp nổi bọt
• Thuật toán sắp xếp trộn
• Thuật toán sắp xếp nhanh
• Thuật toán sắp xếp vun đống
TỔNG QUAN BÀI TOÁN SẮP XẾP
• Sắp xếp là việc đưa các phần tử của một dãy theo đúng thứ tự (không
giảm hoặc không tăng) dựa vào 1 giá trị khoá
• Thiết kế thuật toán sắp xếp hiệu quả là một việc đặc biệt quan trọng do
việc sắp xếp xuất hiện trong rất nhiều tình huống tính toán
• Hai thao tác cơ bản trong một thuật toán sắp xếp
• Compare(a, b): so sánh khoá của 2 phần tử a và b
• Swap(a, b): đổi chỗ 2 phần tử a và b cho nhau
• Không giảm tổng quát, giả sử cần sắp xếp dãy a1, a2, …, an theo thứ tự
không giảm của giá trị
TỔNG QUAN BÀI TOÁN SẮP XẾP
• Phân loại thuật toán sắp xếp
• Sắp xếp tại chỗ: sử dụng bộ nhớ trung gian là hằng số, không phụ
thuộc độ dài dãy đầu vào
• Sắp xếp ổn định: duy trì thứ tự tương đối giữa 2 phần tử có cùng giá
trị khoá (vị trí tương đối giữa 2 phần tử có cùng khoá không đổi trước
và sau khi sắp xếp)
• Thuật toán sắp xếp dựa trên so sánh: sử dụng phép so sánh để
quyết định thứ tự phần tử (counting sort không phải là thuật toán sắp
xếp dựa trên so sánh)
SẮP XẾP LỰA CHỌN
• Chọn số nhỏ nhất xếp vào vị trí void selectionSort(int A[], int N) {
thứ 1 // index tu 1 -> N
for(int k = 1; k <= N; k++){
• Chọn số nhỏ thứ 2 xếp vào vị trí
thứ 2 int min = k;
for(int j = k+1; j <= N; j++){
• Chọn số nhỏ thứ 3 xếp vào vị trí if(A[min] > A[j]) min = j;
thứ 3 }
• … int tmp = A[min];
A[min] = A[k];
A[k] = tmp;
}
}
SẮP XẾP LỰA CHỌN
• Ví dụ: 5, 7, 3, 8, 1, 2, 9, 4, 6
5 7 3 8 1 2 9 4 6 1 2 3 4 5 7 9 8 6
1 7 3 8 5 2 9 4 6 1 2 3 4 5 6 9 8 7
1 2 3 8 5 7 9 4 6 1 2 3 4 5 6 7 8 9
1 2 3 8 5 7 9 4 6
1 2 3 4 5 7 9 8 6
SẮP XẾP CHÈN
• Thuật toán diễn ra qua các bước void insertionSort(int A[], int N) {
lặp k = 2, 3, …, n // index tu 1 -> N
for(int k = 2; k <= N; k++){
• Tại mỗi bước thứ k: chèn ak vào
đúng vị trí trong dãy đã được sắp int last = A[k];
a1, a2, …, ak-1 để thu được dãy int j = k;

được sắp đúng thứ tự while(j > 1 && A[j-1] >
last){
• Sau bước thứ k thì dãy a1, a3, …, ak A[j] = A[j-1];
đã được sắp đúng thứ tự, dãy còn
j--;
lại ak+1, . . ., an giữ nguyên vị trí
}
A[j] = last;
}
}
7
SẮP XẾP CHÈN
• Ví dụ: 5, 7, 3, 8, 1, 2, 9, 4, 6
5 7 3 8 1 2 9 4 6 1 2 3 5 7 8 9 4 6
3 5 7 8 1 2 9 4 6 1 2 3 4 5 7 8 9 6
3 5 7 8 1 2 9 4 6 1 2 3 4 5 6 7 8 9
1 3 5 7 8 2 9 4 6
1 2 3 5 7 8 9 4 6
8
SẮP XẾP NỔI BỌT
• Duyệt dãy từ trái qua phải (hoặc từ void bubleSort(int A[], int N) {
phải qua trái) // index tu 1 den N

int swapped;
• Tại mỗi bước, so sánh 2 phần tử
do{
đứng cạnh nhau và tiến hành đổi
chỗ 2 phần tử đó nếu phần tử swapped = 0;
trước lớn hơn phần tử sau for(int i = 1; i < N; i++){

if(A[i] > A[i+1]){
• Lặp lại quá trình trên khi nào trong int tmp = A[i];
dãy vẫn còn 2 phần tử đứng cạnh A[i] = A[i+1];
nhau mà phần tử trước lớn hơn phần
A[i+1] = tmp;
tử sau
swapped = 1;
}
}
}while(swapped == 1);
}
9
SẮP XẾP NỔI BỌT
• Ví dụ: 5, 7, 3, 8, 1, 2, 9, 4, 6
5 3 7 1 2 8 4 6 9
3 5 1 2 7 4 6 8 9
3 1 2 5 4 6 7 8 9
1 2 3 4 5 6 7 8 9
10
SẮP XẾP TRỘN
• Dựa trên chia để trị void mergeSort(int A[], int L, int R) {

if(L < R){
• Chia dãy a1, …, an thành 2 dãy con
int M = (L+R)/2;
có độ dài bằng nhau
mergeSort(A,L,M);
• Sắp xếp 2 dãy con bằng thuật toán mergeSort(A,M+1,R);
sắp xếp trộn merge(A,L,M,R);
• Trộn 2 dãy con đã được sắp với }
nhau để thu được dãy ban đầu được }
sắp thứ tự
11
SẮP XẾP TRỘN
void merge(int A[], int L, int M, int R) {
• Sử dụng mảng trung gian để // tron 2 day da sap A[L..M] va A[M+1..R]

lưu trữ tạm thời trong quá trình int i = L; int j = M+1;
trộn for(int k = L; k <= R; k++){
if(i > M){ TA[k] = A[j]; j++;}
else if(j > R){TA[k] = A[i]; i++;}
else{
if(A[i] < A[j]){
TA[k] = A[i]; i++;
}
else {
TA[k] = A[j]; j++;
}
}
}
for(int k = L; k <= R; k++) A[k] = TA[k];
}
12
SẮP XẾP TRỘN
5 7 3 8 1 2 9 4 6
• Ví dụ: 5, 7, 3, 8, 1, 2, 9, 4, 6
5 7 3 8 1 2 9 4 6
5 7 3 8 1 2 9 4 6
5 7 3 1 8 2 9 4 6
5 7 3 1 8 2 4 6 9
3 5 7 1 8 2 4 6 9
1 3 5 7 8 2 4 6 9
1 2 3 4 5 6 7 8 9
13
SẮP XẾP NHANH
• Chọn một phần tử bất kỳ dùng làm phần tử trụ (pivot)

• Sắp xếp lại dãy sao cho
• Các phần tử đứng trước phần tử trụ sẽ không lớn hơn phần tử trụ
• Các phần tử đứng sau phần tử trụ không nhỏ hơn phần tử trụ
• Khi đó phần tử trụ (có thể bị thay đổi vị trí) đã đứng đúng vị trí trong dãy
khi được sắp thứ tự
• Tiến hành sắp xếp dãy con đứng trước và sau phần tử trụ bằng sắp xếp
nhanh
14
SẮP XẾP NHANH
void quickSort(int A[], int L, int R) { int partition(int A[], int L, int R, int
if(L < R){ indexPivot) {
int index = (L + R)/2; int pivot = A[indexPivot];
index = partition(A, L, R, index); swap(A[indexPivot], A[R]);
if(L < index)
int storeIndex = L;
quickSort(A, L, index-1);
for(int i = L; i <= R-1; i++){
if(index < R)
if(A[i] < pivot){
quickSort(A, index+1, R);
swap(A[storeIndex], A[i]);
}
} storeIndex++;
}
}
swap(A[storeIndex], A[R]);
return storeIndex;
}
15
SẮP XẾP NHANH
• Ví dụ: 5, 7, 3, 8, 1, 2, 9, 4, 6
Pivot = 5
5 7 3 8 1 2 9 4 6 3 1 2 4 5 6 9 8 7
Pivot = 3
3 1 2 4 1 2 3 4
Pivot = 7
6 9 8 7 6 7 8 9
16
SẮP XẾP VUN ĐỐNG
• Cấu trúc đống (max-heap)
• Cây nhị phân đầy đủ (complete tree) 19
• Khoá của mỗi nút lớn hơn hoặc bằng
khoá của 2 nút con (tính chất của
max-heap) 11 9
• Ánh xạ từ dãy A[1…N] sang cây nhị phân
đầy đủ
• Gốc là A[1] 8 4 6 7
• A[2i] và A[2i+1] là con trái và con phải
của A[i]
• Chiều cao của cây là logN + 1 6 2
17
• Vun lại đống (heapify) 19

• Tình trạng:
• Tính chất max-heap ở A[i] bị phá
vỡ 11 9
• Tính chất max-heap ở các cây
con của A[i] đã được thoả mãn
• Vun lại đống để khôi phục tại tính chất 8 4 6 7
max-heap trên cây gốc A[i]
6 2
18
• Vun lại đống (heapify) void heapify(int A[], int i, int N)

{
• Chọn nút con lớn nhất
int L = 2*i;
• Đổi chỗ nút con và A[i] cho nhau int R = 2*i+1;
nếu nút con này lớn hơn A[i] và int max = i;
vun lại đống bắt đầu từ nút con
if(L <= N && A[L] > A[i])
này
max = L;
if(R <= N && A[R] > A[max])
max = R;
if(max != i){
swap(A[i], A[max]);
heapify(A,max,N);
}
}
19
• Sắp xếp vun đống void buildHeap(int A[], int N) {

• Xây dựng max-heap (thủ tục for(int i = N/2; i >= 1; i--)
buildHeap) heapify(A,i,N);
• Đổi chỗ A[1] và A[N] cho nhau }

void heapSort(int A[], int N) {
• Vun lại đống bắt đầu từ A[1] cho
// index tu 1 -> N
A[1..N-1]
buildHeap(A,N);
• Đổi chỗ A[1] và A[N-1] cho nhau for(int i = N; i > 1; i--) {
• Vun lại đống bắt đầu từ A[1] cho swap(A[1], A[i]);
A[1..N-2] heapify(A, 1, i-1);
• … }
}
20
• Sắp xếp dãy sau theo thứ tự không giảm của

khoá: 8, 4, 2, 7, 6, 9, 11, 19, 5
8
4 2
Cây nhị phân đầy đủ
7 6 9 11
19 5
8, 4, 2, 7, 6, 9, 11, 19, 5
21
8 8
4 2 4 11
Vun nút 2
19 6 9 11 19 6 9 2
7 5 7 5
8, 4, 2, 19, 6, 9, 11, 7, 5 8, 4, 11, 19, 6, 9, 2, 7, 5
22
8 8
4 11 19 11
Vun nút 4
19 6 9 2 7 6 9 2
7 5 4 5
8, 4, 11, 19, 6, 9, 2, 7, 5 8, 19, 11, 7, 6, 9, 2, 4, 5
23
19 11
Đổi chỗ 19 và
8 11 5 cho nhau, 8 9
vun lại heap
7 6 9 2 7 6 5 2
4 5 4 19
19, 8, 11, 7, 6, 9, 2, 4, 5 11, 8, 9, 7, 6, 5, 2, 4, 19
24
11 9
Đổi chỗ 11 và
8 9 4 cho nhau, 8 5
vun lại heap
7 6 5 2 7 6 4 2
4 19 11 19
11, 8, 9, 7, 6, 5, 2, 4, 19 9, 8, 5, 7, 6, 4, 2, 11, 19
25
9 8
Đổi chỗ 9 và
8 5 2 cho nhau, 7 5
vun lại heap
7 6 4 2 2 6 4 9
11 19 11 19
9, 8, 5, 7, 6, 4, 2, 11, 19 8, 7, 5, 2, 6, 4, 9, 11, 19
26
8 7
Đổi chỗ 8 và
7 5 4 cho nhau, 6 5
vun lại heap
2 6 4 9 2 4 8 9
11 19 11 19
8, 7, 5, 2, 6, 4, 9, 11, 19 7, 6, 5, 2, 4, 8, 9, 11, 19
27
7 6
Đổi chỗ 7 và
6 5 4 cho nhau, 4 5
vun lại heap
2 4 8 9 2 7 8 9
11 19 11 19
7, 6, 5, 2, 4, 8, 9, 11, 19 6, 4, 5, 2, 7, 8, 9, 11, 19
28
6 5
Đổi chỗ 6 và
4 5 2 cho nhau, 4 2
vun lại heap
2 7 8 9 6 7 8 9
11 19 11 19
6, 4, 5, 2, 7, 8, 9, 11, 19 5, 4, 2, 6, 7, 8, 9, 11, 19
29
5 4
Đổi chỗ 5 và
4 2 2 cho nhau, 2 5
vun lại heap
6 7 8 9 6 7 8 9
11 19 11 19
5, 4, 2, 6, 7, 8, 9, 11, 19 4, 2, 5, 6, 7, 8, 9, 11, 19
30
4 2
Đổi chỗ 4 và
2 5 2 cho nhau, 4 5
vun lại heap
6 7 8 9 6 7 8 9
11 19 11 19
4, 2, 5, 6, 7, 8, 9, 11, 19 2, 4, 5, 6, 7, 8, 9, 11, 19
31
Thank you
for your
attentions!
THUẬT TOÁN
Tìm kiếm
1
Nội dung
• Tìm kiếm tuần tự
• Tìm kiếm nhị phân
• Cây nhị phân tìm kiếm
• Bảng băm
2
Tìm kiếm tuần tự
• Cho dãy X[L..R] và một giá trị Y. sequentialSearch(X[], int L, int R,

Tìm chỉ số i sao cho X[i] = Y int Y) {
for(i = L; i <= R; i++)
if(X[i] = Y) return i;
return -1;
}
3
Tìm kiếm nhị phân
• Dãy đối tượng được sắp xếp theo binarySearch(X[], int L, int R,
thứ tự không tăng (hoặc không giảm) int Y) {
của giá trị khóa if(L = R){
if(X[L] = Y) return L;
• Dựa trên chia để trị:
return -1;
• So sánh khóa đầu vào Y với }
phần tử ở chính giữa của dãy, và int mid = (L+R)/2;
quyết định tiếp tục tìm kiếm ở
if(X[mid] = Y) return mid;
nửa bên trái hoặc nửa bên phải
if(X[mid] < Y)
đối với phần tử ở chính giữa
return binarySearch(X,mid+1,R,Y);
• Độ phức tạp thời gian: O(logn) return binarySearch(X,L,mid-1,Y);
}
4
Tìm kiếm nhị phân
• Bài tập Cho dãy số gồm các phần tử đôi một khác nhau a1, a2, …, aN
và một giá trị b. Đếm số cặp (ai, aj) sao cho ai + aj = b (i < j)
5
Cây nhị phân tìm kiếm - BST
• BST là một cấu trúc dữ liệu lưu trữ
các đối tượng dưới dạng cây nhị
phân:
• Khóa của mỗi nút lớn hơn
khóa của tất cả các nút ở cây 20
con trái và nhỏ hơn khóa của
tất cả các nút ở cây con bên
phải 26
10
struct Node{ 7 15 23 30
int key;
Node* leftChild;
Node* rightChild;
};
Node* root; 3 8
6
• Các thao tác

• Node* makeNode(int v): tạo ra một nút mới có khóa v
• Node* insert(Node* r, int v): tạo ra 1 nút có khóa là v và chèn vào
BST có gốc là r
• Node* search(Node* r, int v): tìm và trả về nút có khóa bằng v
trong BST gốc r
• Node* findMin(Node* r): tìm và trả về nút có khóa nhỏ nhất trên
BST gốc r
• Node* del(Node* r, int v): loại bỏ nút có khóa bằng v khỏi BST
gốc r
7
Node* makeNode(int v) { Node* insert(Node* r, int v) {

Node* p = new Node; if(r == NULL)
p->key = v; r = makeNode(v);
p->leftChild = NULL; else if(r->key > v)
p->rightChild = NULL; r->leftChild = insert(r->leftChild,v);
return p; else if(r->key <= v)
} r->rightChild = insert(r->rightChild,v);
return r;
}
8
Node* search(Node* r, int v) { Node* findMin(Node* r) {

if(r == NULL) if(r == NULL)
return NULL; return NULL;
if(r->key == v) Node* lmin = findMin(r->leftChild);
return r; if(lmin != NULL) return lmin;
else if(r->key > v) return r;
return search(r->leftChild, v); }
return search(r->rightChild, v);
}
9
Node* del(Node* r, int v) {
if(r == NULL) return NULL;
else if(v < r->key) r->leftChild = del(r->leftChild, v);
else if(v > r->key) r->rightChild = del(r->rightChild, v);
else{
if(r->leftChild != NULL && r->rightChild != NULL){
Node* tmp = findMin(r->rightChild);
r->key = tmp->key; r->rightChild = del(r->rightChild, tmp->key);
}else{
Node* tmp = r;
if(r->leftChild == NULL) r = r->rightChild;
else r = r->leftChild;
delete tmp;
}
}
return r;
}
10
Cây nhị phân tìm kiếm cân bằng - AVL
• AVL là một BST với thuộc tính cân bằng

• Chênh lệch khóa của nút con trái và con phải của mỗi nút nhiều
nhất là 1 đơn vị
• Chiều cao của AVL là logN (N là số nút của cây)
• Thao tác thêm 1 phần tử hoặc loại bỏ 1 phần tử khỏi AVL phải bảo
tồn thuộc tính cân bằng
11
20 20
10 26 10 26
7 15 23 30 7
3 8 3 8
AVL BST nhưng không phải AVL
12
• Chênh lệnh độ cao của 2 nút con của một nút nào đó có thể bằng 2
sau khi thêm mới hoặc loại bỏ 1 nút khỏi AVL
• Thực hiện các phép xoay để khôi phục thuộc tính cân bằng của AVL
13
Case 1: Thực hiện xoay phải
K2 K1
K1 C K2
Right rotation at K2 A
A B B C
TC
TA
TB TB TC
TA
14
Balanced Binary Search Tree - AVL
Case 2
Left rotation at K1 Right rotation at K3 K2

K3 K3
K1 C K2 C K3
K1
A K2 K1 B
TC TC A D B C
D B A D
TA TB
TA TD TB TC
TD TB TA TD
15
Bảng băm
• Ánh xạ: một cấu trúc dữ liệu lưu trữ các cặp khóa – giá trị (key, value)
• put(k,v): Ánh xạ khóa k với giá trị v
• get(k): trả về giá trị tương ứng với khóa k
• Cài đặt
• Cây nhị phân tìm kiếm
• Bảng băm
16
Bảng băm
• Địa chỉ trực tiếp

• Giá trị của khóa k được sử dụng làm địa chỉ trực tiếp, xác định vị
trí cặp khóa – giá trị (k,v) được lưu trữ
• Ưu điểm: đơn giản, tìm kiếm nhanh
• Nhược điểm: hiệu quả sử dụng bộ nhớ kém khi miền giá trị của
khóa trải rộng và số lượng khóa được dung rất ít
17
Bảng băm
• Hàm băm h(k) xác định địa chỉ nơi (k, value) được lưu trữ
• h(k) cần đơn giản và tính toán hiệu quả
18
Bảng băm
• Xung đột: hai khóa khác nhau cho cùng giá trị hàm băm
• Giải quyết xung đột:
• Nhóm chuỗi (chaining): nhóm các khóa có cùng giá trị hàm băm
vào các cụm
• Địa chỉ mở (Open addressing)
19
Hashing
• Modulo: h(k) = k mod m trong đó m là kích thước bảng lưu trữ
20
Bảng băm: địa chỉ mở
• Cặp (key, value) được lưu vào các slot của bảng
• Các thao tác put(k, v) và get(k) cần thực hiện việc dò (probe) để tìm ra
vị trí mong muốn trong bảng nới lưu trữ khóa – giá trị
• put(k, v): dò để tìm ra vị trí trống để lưu (k, v)
• get(k): dò để tìm ra vị trí trong bảng nơi k được lưu trữ
• Thứ tự dò: h(k, 0), h(k, 1), h(k, 2), …, h(k, m-1)
• Các phương pháp dò
• Dò tuyến tính: h(k, i) = (h1(k) + i) mod m trong đó h1 làm hàm
băm thông thường
• Dò toàn phương: h(k, i) = (h1(k) + c1i + c2i2) mod m trong đó h1
là hàm băm thông thường
• Băm kép: h(k, i) = (h1(k) + i * h2(k) mod m trong đó h1 và h2 là
các hàm băm thông thường
21
get(k) put(k, v)
{ {
// T: the table // T: the table
i = 0; x.key = k; x.value = v;
while(i < m) { i = 0;
j = h(k,i); while(i < m) {
if(T[j].key = k) { j = h(k,i);
return T[j]; if(T[j] = NULL) {
} T[j] = x; return j;
i = i + 1; }
} i = i + 1;
return NULL; }
} error(“Hash table overflow”);
}
22
• Bài tập: Một bảng có m ô lưu trữ, áp dụng chiến lược địa chỉ mở với
h(k, i) có dạng:
h(k, i) = (k mod m + i) mod m
• Ban đầu, bảng trống rỗng, hãy cho biết trạng thái của bảng sau khi
thực hiện chèn lần lượt các khóa 7, 8, 6, 17, 4, 28 vào bảng với m = 10
23
VÀ THUẬT TOÁN
Đồ thị
NỘI DUNG
• Khái niệm và định nghĩa

• Biểu diễn đồ thị
• Duyệt đồ thị
• Đồ thị Euler và đồ thị Hamilton
• Cây khung nhỏ nhất của đồ thị
• Đường đi ngắn nhất trên đồ thị
KHÁI NIỆM VÀ ĐỊNH NGHĨA
• Đồ thị là một đối tượng toán học mô hình hoá các thực thể và các liên
kết giữa các thực thể đó
• Đồ thị G = (V, E) trong đó V là tập đỉnh và E là tập cạnh (cung)
• Với mỗi (u, v)  E: ta nói v kề với u
6 2 6 2
1 5 1 5
3 4 3 4
Đồ thị vô hướng Đồ thị có hướng
 V = {1, 2, 3, 4, 5, 6}  V = {1, 2, 3, 4, 5, 6}
 E = {(1, 3), (1,6), (2, 4), (2, 5),  E = {(1, 3), (1,6), (2, 4), (2, 5),
(2, 6), (3, 4), (3, 6), (4, 5)} (6, 2), (3, 4), (6, 3), (4, 5)}
• Bậc của một đỉnh trên đồ thị vô hướng là số đỉnh kề với đỉnh đó:
deg(v) = #{u | (u, v)  E}
• Bán bậc vào (ra) của một đỉnh trên đồ thị có hướng là số cung đi vào
(ra) đỉnh đó:
deg-(v) = #{u | (u, v)  E}, deg+(v) = #{u | (v, u) E}
6 2 6 2
1 5 1 5
3 4 3 4
đồ thị vô hướng đồ thị có hướng

deg(1) = 2, deg(4) = 3 deg-(1) = 0, deg+(1)=2
• Cho đồ thị G=(V, E) và 2 đỉnh s, t V, đường đi từ s đến t trên G là dãy

s = x0, x1, …, xk = t trong đó (xi, xi+1)E, với  i = 0, 1, …, k-1
6 2 6 2
1 5 1 5
3 4 3 4
Đường đi từ 1 đến 5: Đường đi từ 1 đến 5:

 1, 3, 4, 5  1, 3, 4, 5
 1, 6, 2, 5  1, 6, 4, 5
BIỂU DIỄN ĐỒ THỊ
• Ma trận kề  Ma trận trọng số
6 2 6
4 2
3 6
1 5 1 5 9 5
2
3 4
7 3
8 4
1 2 3 4 5 6 1 2 3 4 5 6
1 0 0 1 0 0 1 1 0 0 7 0 0 3
2 0 0 0 1 1 1 2 0 0 0 9 6 4
3 1 0 0 1 0 1 3 7 0 0 8 0 5
4 0 1 1 0 1 0 4 0 9 8 0 2 0
5 0 1 0 1 0 0 5 0 6 0 4 0 0
6 1 1 1 0 0 0 6 3 4 5 0 0 0
BIỂU DIỄN ĐỒ THỊ
 Danh sách kề
 Với mỗi v  V, A(v) là tập các bộ (v, u, w) trong đó w là trọng
số của cung (v, u)
 A(1) = {(1, 6, 3), (1, 3, 7)}
6
4 2
 A(2) = {(2, 4, 9), (2, 5, 6)} 3 6
 A(3) = {(3, 4, 8)}
1 5 9 5
 A(4) = {(4, 5, 2)} 2
 A(5) = {}
7 3
8 4
 A(6) = {(6, 3, 5), (6, 2, 4)}
DUYỆT ĐỒ THỊ
• Duyệt các đỉnh của đồ thị theo một thứ tự nào đó

• Các đỉnh được duyệt (thăm) đúng 1 lần
• Hai phương pháp cơ bản:
• Duyệt theo chiều sâu (DFS)
• Duyệt theo chiều rộng (BFS)
DUYỆT THEO CHIỀU SÂU
• DFS(u): duyệt theo chiều sâu bắt đầu từ đỉnh u
• Nếu tồn tại đỉnh v trong danh sách kề của u chưa được thăm thì tiến
hành thăm v và gọi DFS(v)
• Nếu tất cả các đỉnh kề với u đã được thăm thì DFS quay trở lại đỉnh
x mà từ đó thăm u để tiến hành thăm các đỉnh khác kề với x mà
chưa được thăm. Lúc này đỉnh u được gọi là đã duyệt xong
• Cấu trúc dữ liệu: với mỗi đỉnh v của đồ thị
• p(v): là đỉnh từ đó thăm v
• d(v): thời điểm v được thăm nhưng chưa duyệt xong
• f(v): thời điểm đỉnh v đã được duyệt xong
• color(v)
• WHITE: chưa thăm
• GRAY: đã được thăm nhưng chưa duyệt xong
• BLACK: đã duyệt xong
DFS(u) { DFS() {
t = t + 1; foreach (đỉnh u thuộc V) {
d(u) = t; color(u) = WHITE;
color(u) = GRAY; p(u) = NIL;
}
foreach (đỉnh v kề với u) {
foreach(đỉnh u thuộc V) {
if(color(v) = WHITE) {
if(color(u) = WHITE) {
p(v) = u;
DFS(u);
DFS(v);
}
} }
} }
t = t + 1;
f(u) = t;
color(u) = BLACK;
}
6 2
đỉnh 1 2 3 4 5 6 7
1 5 d
f
3 4 p - - - - - - -
color W W W W W W W
7
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 d 1
f
p - - - - - - -
color G W W W W W W
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 d 1 2
f
3 p - - 1 - - - -
color G W G W W W W
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 d 1 2 3
f
3 4 p - - 1 3 - - -
color G W G G W W W
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4
f
3 4 p - - 1 3 4 - -
color G W G G G W W
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4
f 5
3 4 p - - 1 3 4 - -
color G W G G B W W
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4 6
f 5
3 4 p - - 1 3 4 - 4
color G W G G B W G
7
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4 6
f 5 7
3 4 p - - 1 3 4 - 4
color G W G G B W B
7
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4 6
f 8 5 7
3 4 p - - 1 3 4 - 4
color G W G B B W B
7
DFS(1)
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4 6
f 9 8 5 7
3 4 p - - 1 3 4 - 4
color G W B B B W B
7
DFS(1)
6
đỉnh 1 2 3 4 5 6 7
1 5 d 1 2 3 4 10 6
f 9 8 5 7
3 4 p - - 1 3 4 1 4
color G W B B B G B
7
DFS(1)
6 2
đỉnh 1 2 3 4 5 6 7
1 5 d 1 11 2 3 4 10 6
f 9 8 5 7
3 4 p - 6 1 3 4 1 4
color G G B B B G B
7
DFS(1)
6 2
đỉnh 1 2 3 4 5 6 7
1 5 d 1 11 2 3 4 10 6
f 12 9 8 5 7
3 4 p - 6 1 3 4 1 4
color G B B B B G B
7
DFS(1)
6 2
đỉnh 1 2 3 4 5 6 7
1 5 d 1 11 2 3 4 10 6
f 12 9 8 5 13 7
3 4 p - 6 1 3 4 1 4
color G B B B B B B
7
DFS(1)
6 2
đỉnh 1 2 3 4 5 6 7
1 5 d 1 11 2 3 4 10 6
f 14 12 9 8 5 13 7
3 4 p - 6 1 3 4 1 4
color B B B B B B B
7
• Kết quả DFS trên đồ thị sẽ cho 1 rừng, bao gồm các cây DFS
• Phân loại cạnh
• Cạnh của cây (tree edge): (u,v) là cạnh của cây nếu v được thăm từ
u
• Cạnh ngược (back edge): (u,v) là cạnh ngược nếu v là tổ tiên của u
trong cây DFS
• Cạnh thuận (forward edge): (u,v) là cạnh thuận nếu u là tổ tiên của v
trong cây DFS
• Cạnh ngang (crossing edge): các cạnh còn lại
• Phân loại cạnh 6 2

• Cạnh của cây: (1, 6), (1, 3), (6, 2), (3, 1 5
4), (4, 5), (4, 7)
• Cạnh ngược:
• Cạnh thuận: (3, 7) 3 4
• Cạnh ngang: (6, 3), (6, 4), (2, 4), (2,5)
7
6 2
1 5
3 4
7
• Cài đặt thuật toán DFS tìm các thành phần liên thông của đồ thị
• Cài đặt thuật toán minh họa thuật toán DFS tìm các thành phần liên
thông của đồ thị
• Dữ liệu đầu vào
• Dòng 1: ghi n và m (số đỉnh và số cạnh của đồ thị)
• Dòng i+1 (i = 1,…,m): ghi u và v là đầu mút của 1 cạnh (u,v) của đồ
thị
• Kết quả đầu ra
• Dòng thứ k: ghi danh sách các đỉnh thuộc thành phần liên thông
thứ k
#include <stdio.h>
#define N 1000
int n,m;
int A[N][N];// A[v] is the list of adjacent nodes of v
int szA[N];// szA[v] is the size of A[v]
// data structure for connected component
int ncc;
int icc[N];// icc[u] is the index of connected component of u
void input(){
scanf("%d%d",&n,&m);
for(int v = 1; v <= n; v++) szA[v] = 0;
for(int k = 1; k <= m; k++){
int u,v;
scanf("%d%d",&u,&v);
A[v][szA[v]] = u; A[u][szA[u]] = v;
szA[v]++; szA[u]++;
}
}
void dfs(int u){
icc[u] = ncc;
for(int i = 0; i < szA[u]; i++){
int v = A[u][i];
if(icc[v] == -1){// not visited
dfs(v);
}
}
}
void dfsGraph(){
for(int v = 1; v <= n; v++) icc[v] = -1;
ncc = 0;
for(int v = 1; v <= n; v++) if(icc[v] == -1){
ncc++;
dfs(v);
}
for(int k = 1; k <= ncc; k++){
printf("connected component %d: ",k);
for(int v = 1; v <= n; v++) if(icc[v] == k) printf("%d ",v);
printf("\n");
}
}
void main(){
input();
dfsGraph();
}
DUYỆT THEO CHIỀU RỘNG
• BFS(u): duyệt theo chiều rộng xuất phát từ đỉnh u

• Thăm các đỉnh u
• Thăm các đỉnh kề với u mà chưa được thăm (gọi là các đỉnh mức 1)
• Thăm các đỉnh kề với các đỉnh mức 1 mà chưa được thăm (gọi là
các đỉnh mức 2)
• Thăm các đỉnh kề với các đỉnh mức 2 mà chưa được thăm (gọi là
các đỉnh mức 3)
• ...
• Sử dụng cấu trúc hàng đợi (queue) để cài đặt
BFS(u) { BFS() {
d(u) = 0; foreach (đỉnh u thuộc V) {
khởi tạo hàng đợi Q; color(u) = WHITE;
enqueue(Q,u); p(u) = NIL;
color(u) = GRAY; }
while(Q khác rỗng) { foreach(đỉnh u thuộc V) {
v = dequeue(Q); if(color(u) = WHITE) {
foreach(x kề với v) { BFS(u);
if(color(x) = WHITE){ }
d(x) = d(v) + 1; }
color(x) = GRAY; }
enqueue(Q,x);
}
}
}
}
BFS(1)
6 2
1 5
3 4
7
BFS(1)
1
BFS(1)
6
3
BFS(1)
6 2
3 4
7
BFS(1)
6 2
1 5
3 4
7
• Cài đặt thuật toán minh họa thuật toán BFS tìm các thành phần liên
thông của đồ thị
• Dữ liệu đầu vào
• Dòng 1: ghi n và m (số đỉnh và số cạnh của đồ thị)
• Dòng i+1 (i = 1,…,m): ghi u và v là đầu mút của 1 cạnh (u,v) của đồ
thị
• Kết quả đầu ra
• Dòng thứ k: ghi danh sách các đỉnh thuộc thành phần liên thông
thứ k
#include <stdio.h>
#define N 1000
// Data Structure for the queue
int q[N];
int head = -1, tail = -1;
// data structure for the graph
int n,m;// number of nodes and edges
int A[N][N]; // A[v] is the list of adjacent nodes to v
int szA[N];// szA[v] is the size of A[v]
// data structure for BFS connected component

int ncc; // number of connected component
int icc[N]; // icc[v] is the index of connected component of v
int d[N];// d[v] is the distance from the starting node to v in the BFS tree
void initQueue(){
head = -1; tail = -1;
}
void pushQ(int v){
tail++; q[tail] = v; if(head == -1) head = tail;
}
int popQ(){
if(head == -1) return -1;// queue empty
int v = q[head];
if(head == tail){
head = -1; tail = -1;
}else
head++;
return v;
}
int empty(){
return head == -1 && tail == -1;
}
void input(){
for(int v = 1; v <= n; v++) szA[v] = 0;
for(int k = 1; k <= m; k++){
int u,v;
scanf("%d%d",&u,&v);
A[v][szA[v]] = u; A[u][szA[u]] = v;
szA[v]++; szA[u]++;
}
}
void bfs(int u){
initQueue();
icc[u] = ncc;
pushQ(u);
d[u] = 0;
while(!empty()){
int v = popQ();
for(int i = 0; i < szA[v]; i++){
int x = A[v][i];
if(d[x] == -1){
d[x] = d[v] + 1;
pushQ(x);
icc[x] = ncc;
}
}
}
}
void bfsGraph(){
for(int v = 1; v <= n; v++) d[v] = -1;
ncc = 0;
for(int v = 1; v <= n; v++) if(d[v] == -1){
ncc++;
bfs(v);
}
for(int k = 1; k <= ncc; k++){
printf("Connected component %d: ",k);
for(int v = 1; v <= n; v++) if(icc[v] == k) printf("%d ",v);
printf("\n");
}
}
int main(){
input();
bfsGraph();
}
Cây khung nhỏ nhất của đồ thị
• Cho đồ thị vô hướng G = (V, E, w).

• Mỗi cạnh (u, v) E có trọng số w(u, v)
• Nếu (u, v)  E thì w(u, v) = 
• Một cây khung của G là một đồ thị con liên thông của G không chứa chu
trình và chứa tất cả các đỉnh của G.
• T = (V, F) trong đó F E
• Trọng số của T: w(T) =σ𝑒∈𝐹 𝑤(𝑒)
• Tìm cây khung của G có trọng số nhỏ nhất
Cây khung nhỏ nhất: thuật toán Kruskal
• Thuật toán tham làm KRUSKAL(G = (V,E)){

• Mỗi bước, chọn cạnh nhỏ ET = {}; C = E;
nhất bổ sung vào T với điều while(|ET| < |V|-1 and |C| > 0){
kiện không tạo ra chu trình e = select minimum-cost edge of C;
C = C \ {e};
if(ET  {e} create no cycle){
ET = ET  {e};
}
}
if(|ET| = |V|-1) return ET;
else return null;
}
Disjoint Sets
• Là cấu trúc dữ liệu biểu diễn
các tập không giao nhau với 2 1 8
thao tác chính
• FindSet(x): trả về định danh
của tập chứa x 3 2 4 9 c 10
• Unify(r1, r2): Hợp nhất 2 c
tập hợp định danh là r1 và 5 12
r2 làm một
• Mỗi tập được biểu diễn bởi cây 6 7 11
c
có gốc
• Mỗi nút của cây là một
phần tử
• Mỗi nút có 1 nút cha duy
nhất (cha của nút gốc là
chính nó)
• Nút gốc là định danh của
tập
Disjoint Sets
• Thao tác FindSet(x)
• Di chuyển từ x theo đường 1 1
đi duy nhất từ nó đến nút
gốc của cây chứa x (thời 3 2 4 3 2 4
gian tính tỉ lệ với độ dài của
đường đi) 5 FindSet(7) 5
• Điều chỉnh cây mỗi khi thực
hiện truy vấn: biến tất cả
6 7 6 7
các nút dọc theo đường đi
từ x đến nút gốc thành nút
con trực tiếp của nút gốc →
Rút ngắn thời gian của các
truy vấn về sau
Disjoint Sets
• Thao tác Unify(r1, r2)
• Biến một trong hai nút r1, 1
hoặc r2 làm nút con của nút
còn lại (tiêu chí nút nào có 3 2 4 8
độ cao thấp hơn thì biến
thành nút con của nút còn 5 9 10
lại để đảm bảo duy trì độ
cao của các cây thấp)
6 7 12
• Việc cài đặt duy trì 2 cấu trúc

Độ cao của 8 nhỏ hơn độ cao của 1, nên
• p(x): cha của nút x biến 8 thành con của 1
• r(x): hạng của nút x (độ
cao)
#include <iostream>
#define MAX 100001
// data structure for input graph

int N, M;
int u[MAX];
int v[MAX];
int c[MAX];
int ET[MAX];
int nET;
// data structure for disjoint-set
int r[MAX];// r[v] is the rank of the set v
int p[MAX];// p[v] is the parent of v
long long rs;
void unify(int x, int y){
if(r[x] > r[y]) p[y] = x;
else{
p[x] = y;
if(r[x] == r[y]) r[y] = r[y] + 1;
}
}
void makeSet(int x){
p[x] = x;
r[x] = 0;
}
int findSet(int x){
if(x != p[x])
p[x] = findSet(p[x]);
return p[x];
}
void swap(int& a, int& b){
int tmp = a; a = b; b = tmp;
}
void swapEdge(int i, int j){
swap(c[i],c[j]); swap(u[i],u[j]); swap(v[i],v[j]);
}
int partition(int L, int R, int index){
int pivot = c[index];
swapEdge(index,R);
int storeIndex = L;
for(int i = L; i <= R-1; i++){
if(c[i] < pivot){
swapEdge(storeIndex,i);
storeIndex++;
}
}
swapEdge(storeIndex,R);
return storeIndex;
}
void quickSort(int L, int R){
if(L < R){
int index = (L+R)/2;
index = partition(L,R,index);
if(L < index) quickSort(L,index-1);
if(index < R) quickSort(index+1,R);
}
}
void quickSort(){
quickSort(0,M-1);
}
void solve(){
for(int x = 1; x <= N; x++) makeSet(x);
quickSort();
rs = 0;
int count = 0;
nET = 0;
for(int i = 0;i < M; i++){
int ru = findSet(u[i]);
int rv = findSet(v[i]);
if(ru != rv){
unify(ru,rv);
nET++; ET[nET] = i;
rs += c[i];
count++;
if(count == N-1) break;
}
}
cout << rs;
}
void input(){
cin >> N >> M;
for(int i = 0; i < M; i++){
cin >> u[i] >> v[i] >> c[i];
}
}
int main(){
input();
solve();
}
Đường đi ngắn nhất – thuật toán Dijkstra
• Cho đồ thị trọng số không âm G = (V, E, w).

• Mỗi cạnh (u, v) E có trọng số không âm w(u, v)
• Nếu (u, v)  E thì w(u, v) = 
• Cho đỉnh s của V, thì đường đi ngắn nhất từ s đến tất cả các đỉnh còn
lại của G
• Thuật toán Dijkstra:

• Mỗi đỉnh v  V:
• P(v) đường đi cận trên của đường đi ngắn nhất từ s đến v
• d(v): trọng số của P(v)
• p(v): đỉnh trước đỉnh v trên P(v)
• Khởi tạo
• P(v) = s, v, d(v) = w(s,v), p(v) = s
• Cải tiến cận trên
• Nếu phát hiện một đỉnh u sao cho d(v) > d(u) + w(u, v) thì cập
nhật:
• d(v) = d(u) + w(u, v)
• p(v) = u
Dijkstra(G = (V,E,w)) {
for(v  V) {
d(v) = w(s,v); p(v) = s;
}
S = V \ {s};
while(S  {}) {
u = select a node  S having minimum d(u);
S = S \ {u};
for(v  S) {
if(d(v) > d(u) + w(u,v) {
d(v) = d(u) + w(u,v); p(v) = u;
}
}
}
}
6
4 2
6 • Mỗi ô của bảng tương ứng với 1
3
đỉnh v của bảng có nhãn (d(v),
1 5 1 9 5 p(v))
2 • Nút nguồn s = 1
7 3
8 4 1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1)
Step 1 -
Step 2 -
Step 3 -
Step 4 -
Step 5 -
6
4 2
6
3
1 5 1 9 5
2
7 3
8 4
1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) *
Step 1 - (7,6) (7,1) (4,6) (,1) -
Step 2 - -
Step 3 - -
Step 4 - -
Step 5 - -
6
4 2
6
3
1 5 1 9 5
2
7 3
8 4
1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) *
Step 1 - (7,6) (7,1) (4,6) * (,1) -
Step 2 - (7,6) (7,1) - (6, 4) -
Step 3 - - -
Step 4 - - -
Step 5 - - -
6
4 2
6
3
1 5 1 9 5
2
7 3
8 4
1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) *
Step 1 - (7,6) (7,1) (4,6) * (,1) -
Step 2 - (7,6) (7,1) - (6, 4) * -
Step 3 - (7,6) (7,1) - - -
Step 4 - - - -
Step 5 - - - -
6
4 2
6
3
1 5 1 9 5
2
7 3
8 4 1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) *
Step 1 - (7,6) (7,1) (4,6) * (,1) -
Step 2 - (7,6) (7,1) - (6, 4) * -
Step 3 - (7,6) (7,1) * - - -
Step 4 - (7,6) - - - -
Step 5 - - - - -
6
4 2
6
3
1 5 1 9 5
2
7 3
8 4
1 2 3 4 5 6
Init (0,1) (,1) (7, 1) (, 1) (, 1) (3,1) *
Step 1 - (7,6) (7,1) (4,6) * (,1) -
Step 2 - (7,6) (7,1) - (6, 4) * -
Step 3 - (7,6) (7,1) * - - -
Step 4 - (7,6) * - - - -
Step 5 - - - - - -
• Hàng đợi ưu tiên (Priority queues)

• Cấu trúc dữ liệu lưu trữ các đỉnh v và khóa d(v)
• Các thao tác
• (e,k) = deleteMin(): Lấy ra đỉnh e có khóa k nhỏ nhất
• insert(v,k): chèn một nút e và khóa k của nó vào hàng đợi
• updateKey(v,k): Cập nhật nút v với khóa mới bằng k
• Cài đặt priority queue bằng cấu trúc min-heap
• Các phần tử lưu trữ theo cây nhị phân đầy đủ
• Khóa của mỗi nút (đỉnh của đồ thị) nhỏ hơn hoặc bằng khóa của
2 nút con
3,2
1,5 4,8
6,7 7,9 5,10 2,12
8,10 9,11
3,2 Đảo (3,2) và (9,11) 9,11
1,5 4,8 1,5 4,8
6,7 7,9 5,10 2,12 6,7 7,9 5,10 2,12
8,10 9,11 8,10 3,2

Down Heap from (9,11)
9,11 1,5
1,5 4,8 9,11 4,8
6,7 7,9 5,10 2,12 6,7 7,9 5,10 2,12
8,10 3,2 8,10 3,2
1,5 1,5
6,7 4,8 6,7 4,8
8,10 7,9 5,10 2,12 9,11 7,9 5,10 2,12
9,11 3,2 Cut and return

this node 8,10 3,2
#include <stdio.h>
#include <vector>
#define MAX 100001
#define INF 1000000
vector<int> A[MAX]; // A[v][i] is the i^th adjacent node to v

vector<int> c[MAX]; // c[v][i] is the weight of the i^th adjacent arc
// (v,A[v][i]) to v
int n,m; // number of nodes and arcs of the given graph
int s,t; // source and destination nodes
// priority queue data structure (BINARY HEAP)

int d[MAX];// d[v] is the upper bound of the length of the shortest path from s
// to v (key)
int node[MAX];// node[i] the i^th element in the HEAP
int idx[MAX];// idx[v] is the index of v in the HEAP (idx[node[i]] = i)
int sH;// size of the HEAP
bool fixed[MAX];
void swap(int i, int j){
int tmp = node[i]; node[i] = node[j]; node[j] = tmp;
idx[node[i]] = i; idx[node[j]] = j;
}
void upHeap(int i){
if(i == 0) return;
while(i > 0){
int pi = (i-1)/2;
if(d[node[i]] < d[node[pi]]){
swap(i,pi);
}else{
break;
}
i = pi;
}
}
void downHeap(int i){
int L = 2*i+1;
int R = 2*i+2;
int maxIdx = i;
if(L < sH && d[node[L]] < d[node[maxIdx]]) maxIdx = L;
if(R < sH && d[node[R]] < d[node[maxIdx]]) maxIdx = R;
if(maxIdx != i){
swap(i,maxIdx); downHeap(maxIdx);
}
}
void insert(int v, int k){
// add element key = k, value = v into HEAP
d[v] = k;
node[sH] = v;
idx[node[sH]] = sH;
upHeap(sH);
sH++;
}
int inHeap(int v){

return idx[v] >= 0;
}
void updateKey(int v, int k){
if(d[v] > k){
d[v] = k;
upHeap(idx[v]);
}else{
d[v] = k;
downHeap(idx[v]);
}
}
int deleteMin(){
int sel_node = node[0];
swap(0,sH-1);
sH--;
downHeap(0);
return sel_node;
}
void input(){
for(int k = 1; k <= m; k++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
A[u].push_back(v);
c[u].push_back(w);
}
scanf("%d%d",&s,&t);
}
void init(int s){
sH = 0;
for(int v = 1; v <= n; v++){
fixed[v] = false; idx[v] = -1;
}
d[s] = 0; fixed[s] = true;
for(int i = 0; i < A[s].size(); i++){
int v = A[s][i];
insert(v,c[s][i]);
}
}
void solve(){
init(s);
while(sH > 0){
int u = deleteMin(); fixed[u] = true;
for(int i = 0; i < A[u].size(); i++){
int v = A[u][i];
if(fixed[v]) continue;
if(!inHeap(v)){
int w = d[u] + c[u][i]; insert(v,w);
}else{
if(d[v] > d[u] + c[u][i]) updateKey(v,d[u]+c[u][i]);
}
}
}
int rs = d[t]; if(!fixed[t]) rs = -1;
printf("%d",rs);
}
int main(){
input();
solve();
}
Thank you
for your
attentions!

CTDL&TT

Uploaded by

Copyright:

Available Formats

CTDL&TT

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CTDL&TT

Uploaded by

Copyright:

Available Formats

CẤU TRÚC DỮ LIỆU VÀ

• Hạn chế của phương pháp thực nghiệm

Thời gian tính T(n) = c2n + c3(n-1) + c4(n-1) +c5σ𝑛𝑗=2 𝑡𝑗 + c6σ𝑛𝑗=2(𝑡𝑗 − 1) +

• Tình huống tốt nhất: dãy đã được sắp xếp, tj = 1 (j = 2,…,n)

• Độ tăng: số hạng có số mũ cao nhất (ví dụ, n2 trong an2 + bn + c) sẽ đại

Logarithmic algorithms Log n

• Tập hợp được định nghĩa đệ quy

Bước cơ sở: 3S

• Một chương trình con (thủ tục/hàm) Ví dụ: tổng 1 + 2 + … + n

• Ví dụ: hằng số tổ hợp int C(int k, int n) {

C(1,3) C(2,3) C(2,3) C(3,3)

C(0,2) C(1,2) C(1,2) C(2,2) C(1,2) C(2,2)

C(0,1) C(1,1) C(0,1) C(1,1) C(0,1) C(1,1)

• Mô hình hoá cấu hình: for(int i = 1; i<= n; i++)

• Mảng x[n] trong đó x[i] {0,1}

• Liệt kê các xâu nhị phân sao cho int TRY(int k) {

• Liệt kê các tổ hợp chập k của 1, 2, int TRY(int i) {

int check(int v, int k) { void TRY(int k) {

for(int i = 1; i <= k-1; i++) { x[k] = v;

• Điền các chữ số từ 1 đến 9 vào các 1 2 3 4 5 6 7 8 9

• Thứ tự duyệt: từ ô (0,0), theo thứ tự từ

Cho số nguyên dương M, N và N số nguyên dương A1, A2, …, AN. Liệt

1. Liệt kê tất cả các cách chọn ra k phần tử từ 1, 2, …, n sao cho

• Bài toán tối ưu tổ hợp

• Bài toán người du lịch

• Duyệt toàn bộ: TRY(k)

• Phương án bộ phận (a1,…, ak) trong đó Foreach v thuộc Ak

a1 gán cho x1,… ak gán cho xk if check(v,k) {

• Phương án bộ phận (a1,…, ak) trong đó Foreach v thuộc Ak

a1 gán cho x1,… ak gán cho xk if check(v,k) {

• Phương án bộ phận (a1,…, ak) trong đó Foreach v thuộc Ak

a1 gán cho x1,… ak gán cho xk if check(v,k) {

• Nếu g(x1,…,xk)  f* thì không phát triển }

• cm là chi phí nhỏ nhất trong số các x1

• Bài toán dãy con tăng dần cực đại

• Lời giải được biểu diễn bởi tập S Greedy() {

• solution(S): trả về true nếu S là lời giải C = C \ {x};

Lời giải tối ưu là S = {(3,7), (9,11), (12,15), (17,19)}

• Tham lam 1 Greedy1() {

• Sắp xếp các đoạn theo thứ tự S = {};

• Sắp xếp các đoạn theo thứ tự S = {};

• Tham lam 3 Greedy3() {

• Sắp xếp các đoạn theo thứ tự không S = {};

• Đầu vào: dãy số nguyên if(l == r) return a[l];

a1, a2, …, an int max;

• Độ phức tạp của thuật toán chia để trị (định lí thợ)

• Bài toán dãy con cực đại

• Bài toán dãy con tăng dần cực đại

• Phân chia void solve(){

• Ký hiệu Pi là bài toán tìm dãy con S[0] = 1;

cực đại mà phần tử cuối cùng là ai, rs = S[0];

với mọi i = 1,…, n for(int i = 1; i < n; i++){

• Bài toán dãy con chung dài nhất

• Bài toán dãy con chung dài nhất

for(int i = 1; i <= n; i++){

• Định nghĩa danh sách tuyến tính

• Các đối tượng được lưu trữ có thứ tự

• Lưu trữ các đối tượng với quan hệ trước-sau

• Tổ chức dữ liệu void insert(int x, int p) {

• int n; // số phần tử của }