Nhóm thực hiện
Trần Đình Anh Huy
0811062

Nguyễn Hồng Quy
0811137

Nguyễn Hoàng Quốc
0811300
GV: TS. Trần Nam Dũng
Đại Học Khoa Học Tự Nhiên Hồ Chí Minh
Khoa Toán – Tin Học
Bài Báo Cáo Môn Phân Tích Thuật Toán
Tóm tắt nội dung
Chia để trị là một mô hình thiết kế thuật toán rất quan trọng trong
ngành khoa học máy tính. Mô hình sử dụng chủ yếu giải thuật đệ quy,
được sử dụng phổ biến để giải quyết các vấn đề , bài toán phức tạp nhằm
mục đích giảm chi phí của bài toán đến mức tối ưu có thể. Tư tưởng của
phương pháp chia để trị hình thành rất sớm (khoảng 200 năm trước công
nguyên
1
) từ một bài toán sắp xếp các mặt hàng một cách đơn giản của
người Babylon. Trong khuôn khổ bài báo cáo môn học, nhóm thực hiện chỉ
nêu lên những vấn đề cơ bản của phương pháp này.
1
theo http:// en.wikipedia
Mục lục

1.1 Tại Sao Phải Chia
Tư tưởng chính mô hình chia để trị là chia một bài toán (một vấn đề)
thành hai hay nhiều bài toán (vấn đề) nhỏ hơn cùng loại hoặc liên quan
với nhau. Cho đến khi kết quả bài toán (vấn đề) đó có được từ cách tổng
hợp kết quả của những bài toán (vấn đề) cơ sở hoặc đơn giản có thể giải
quyết một cách trực tiếp dễ dàng. Nguyên lý mô hình Chia Để Trị giải xử
lý vấn đề từ trên xuống. Ta cũng có một mô hình khác giải quyết theo cách
ngược lại đó là mô hình Quy Hoạch Động xử lý vấn đề từ dưới lên.
1.1.1 Ưu Điểm
Đối với tin học mô hình chia để trị ngày này được sử dụng ngày càng
mạnh mẻ trong tin học dựa trên sự phát triển của công nghệ và sự ra đời
các bộ xử lý đa luồng, các mô hình tính toán song song. Giúp các vấn đề
nhỏ được xử lý gần như một lúc, giúp giảm thiểu thời gian và chi phí thực
thi đi gấp nhiều lần, đây là một trong những ưu điểm chính của mô hình
chia để trị. Hơn thế nữa, mô hình thuật toán còn giúp tận dụng bộ nhớ đêm
(cache) một cách hiểu quả, đó là kết quả của việc chia nhỏ vấn đề mà bản
thân các vấn để đó (đủ nhỏ đến mức cần thiết) có thể giải quyết được trên
bộ nhớ cache, không cần gửi thông tin đến bộ nhớ truy cập.
1.1.2 Nhược Điểm
Chia để trị có một nhược điểm khá lớn đó là chia để trị không thể lưu
lại kết quả của những vấn đề đã giải quyết cho lần yêu cầu tiếp theo, vì vậy
ta phải xem xét lại vấn đề bài toán có nên sử dụng chia để trị hay không.
3
Hình 1.1: Các bước của mô hình chia để trị
Một bài toán áp dụng được chia để trị tốt nhất là một bài toán có thể chia
nhỏ thành nhiều vấn đề nhỏ khác cùng loại và trong quá trình giải quyết
vấn đề số lần giải quyết lại cùng một vấn để đã giải quyết là cực tiểu.
1.2 Các Bước Thực Hiện
Các bước thiết kế thuật toán:
1. Chia vấn đề thành các vấn đề con.

n
2
) + 1 và T(1) = 1 Giả sử n = 2
k
,theo hệ thức truy hồi:
T (n) = T(
n
2
) + 1 = T(
n
2
2
) + 2 = . . . = T(
n
2
k
) + k
Theo cách đặt đó ta có: n = 2
k
,T (1) = 1, T (n) = 1 + k mà k = log
2
(n) ⇒
T (n) = log
2
(n) + 1 ⇒ T(n) = O(log
2
(n))
1.3 Các Vấn Đề Cài Đặt
1.3.1 Chia Ra Nhiều Sẽ Dễ Trị?
Trong đa số các bài toán chia để trị trên lý thuyết người ta thường chia

.2
n/2
+ x
1
.2
3n/4
y = y
4
+ y
3
.2
n/4
+ y
2
.2
n/2
+ y
1
.2
3n/4
xy = (x
4
+ x
3
.2
n/4
+ x
2
.2
n/2

khi b = 2. Vậy chia nhỏ chưa hẳn đã tốt hơn.
Định lý 1.3.1 (Định Lý Master). Nếu T(n) = aT ([
n
b
]) + O(n
d
) với a > 0,
b > 1 và d ≥ 0 thì:
T (n) = O(n
d
) nếu d > log
b
a
T (n) = O(n
d
logn) nếu d = log
b
a
T (n) = O(n
log
b
a
) nếu d < log
b
a
5
Vậy theo định lý Master, cách chia tối ưu nhất là chia sao cho d = log
a
b
Ngoài ra, để dễ dàng hơn, người ta còn chia theo định nghĩa đệ quy của

1.3.2 Mối Quan Hệ Với Đệ Quy
Đệ Qui
Để có thể hiểu được mối quan hệ giữa chia để trị với đệ quy thì ta cần
xét những điểm mạnh của đệ quy. Đệ quy mạnh ở chỗ có thể định nghĩa
một tập rất lớn các tác động chỉ bởi số rất ít mệnh đề, rất thích hợp để giải
quyết những bài toán có tính chất đệ qui. Khi dùng đệ quy, bài toán giải
quyết sẽ sáng sủa, dễ hiểu hơn. Từ đó có thể nói bản chất của của đệ quy là
giải quyết bài toán theo kiểu qui nạp, hạ bậc (ThS.Trần Đức Huyên
1
), điều
này rất có ý nghĩa trong việc chúng ta chia bài toán ra để "trị".
Theo như hiện nay, nhiều thuật toán vẫn chưa có cách giải nào khác
nếu không sử dụng đệ quy. Nhưng bên cạnh đó, không ít những bài toán
đệ quy bị khử đệ quy bằng nhiều phương pháp khác nhau. Lý do để khử đệ
quy là tránh cho máy mất quá nhiều tài nguyên hay thực hiện thừa các tác
vụ.
Mối Quan Hệ
Có thể nói rằng mối quan hệ giữa đệ quy và chia để trị là hết sức khắng
khít. Với bản chất của đệ quy, chúng ta có thể dùng nó để thiết kế việc chia
như thế nào trong thuật toán đặt ra hết sức dễ dàng, sáng sủa. Nếu như
khẳng định việc sử dụng đệ quy trong việc chia để trị là yếu tố hiển nhiên
là không sai.
Tuy nhiên, ta cần chú ý rằng đệ quy không phải là chìa khoá vàng. Đệ
quy cũng có một số khiếm khuyết như đã đề cập ở trên, cho nên đệ quy
1
NXB Giáo Dục, phương pháp giải các bài toán trong Tin Học
6
không hẳn là co đường duy nhất đi đến thành công. Chúng ta có thể sử
dụng những phương pháp khử đệ quy khác đã biết như: stack, vòng lặp,
1.3.3 Các Vấn Đề Về Cài Đặt

2
(n) lần
phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất
khó. Có các cách chọn phần tử chốt như sau:
1. Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
2. Chọn phần tử đứng giữa danh sách làm phần tử chốt.
8
3. Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng
cuối làm phần tử chốt.
4. Chọn phần tử ngẫu nhiên làm phần tử chốt. (Cách này có thể dẫn đến
khả năng rơi vào các trường hợp đặc biệt)
Thuật phân chia sau khi phần tử chốt được chọn giải thuật phân chia
nên tiến hành như thế nào? Một giải pháp đơn giản nhất cho vấn đề này là
duyệt từ đầu đến cuối lần lượt so sánh các phần tử của danh sách với phần
tử chốt. Theo cách này, ta phải tiến hành n phép so sánh, ngoài ra còn phải
dành n đơn vị bộ nhớ để lưu giữ các giá trị trung gian.
Một giải pháp khác được đề nghị là duyệt theo hai đường. Một đường từ
đầu danh sách, một đường từ cuối danh sách. Theo cách này, ta tìm phần
tử đầu tiên tính từ trái lớn hơn phần tử chốt và phần tử đầu tiên phía phải
nhỏ hơn hoặc bằng phần tử chốt rồi đổi chỗ cho nhau. Tiếp tục như vậy
cho đến khi hai đường gặp nhau.
Để có thể gọi đệ quy ta xét bài toán phân chia một danh sách con của a:
a[k1, k2] thành hai danh sách. Công thức truy hồi và cách tính độ phức tạp
giống hoàn toàn với phương pháp Merge Sort. Với một mảng n phần tử ta
cần sắp xếp theo Merge Sort. Đặt T(n) là độ phức tạp của thuật toán, ta có
được công thức truy hồi theo độ phức tạp thuật toán: T (n) = 2T(n/2) + Cn
(với Cn là chi phí thực hiện bài toán ở mức n phần tử), T (
n
2
) = 2T (

2
(n)
2.1.2 Merge Sort
Sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các
danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, (v.d:
luồng tập tin) theo một trật tự nào đó. Thuật toán này là một ví dụ tương
đối điển hình của lối thuật toán chia để trị. Nó được xếp vào thể loại sắp
xếp so sánh.
Trộn có hai danh sách đã được sắp xếp a[1 m] và b[1 n.]. Ta có thể trộn
chúng lại thành một danh sách mới c[1, m + n] được sắp xếp theo cách sau:
So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho
vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là
rỗng. Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách
kia cho vào cuối danh sách mới. Ví dụ: Cho hai danh sách a = (1, 3, 7, 9),
b = (2, 6), quá trình hòa nhập diễn ra như sau:
9
Hình 2.1: một minh họa cho thuật toán Merge Sort
10
Danh sách a Danh sách b So sánh Danh sách c
1,3,7,9 2,6 1<2 1
3,7,9 2,6 2<3 1.2
3,7,9 6 3<6 1,2,3
7,9 6 6<7 1,2,3,6
7,9 1,2,3,6,7,9
Trộn tại chỗ: giả sử trong danh sách a[1 n] có 2 danh sách con kề nhau
a[k1 k2] và a[k2 + 1 k3] đã được sắp. Ta áp dụng cách trộn tương tự như
trên để trộn hai danh sách con vào một danh sách tạm T [k1 k3] rồi trả lại
các giá trị của danh sách tạm T về danh sách A. Làm như vậy gọi là trộn tại
chỗ.
Trộn từ dưới lên nếu danh sách con chỉ gồm hai phần tử, mối nửa của

) + Cn = 4T (
n
4
) + 2Cn = = 2
k
T (
n
2
k
) + Cnk =
2
k
+ Cnk = n + Cnlog
2
(n) với n = 2
k
, T(
n
2
k
) = T (1) = 1. Vậy thuật toán
Merge Sort có độ phức tạp là O(n) = nlog
2
(n)
2.2 Nhân 2 Số Nhị Phân N Bit
Nhân 2 số tự nhiên n-bit X và Y thông thường độ phức tạp ở mức O(n
2
).
Bây giờ chúng ta sẽ xét lại bài toán này với kỹ thuật chia để trị. Ta phân
11

Và do đó T (n) = O(n
2
) nên không hiệu quả lắm với cách thông thường cho
nên chúng ta tiếp tục biến đổi XY như sau:
XY = AC2
n
+ ((A − B)(D − C) + AC + BD)2
n
2
+ BD
Đến đây ta thấy hiệu quả của phép biến đổi vừa được tạo ra, cụ thể để tính
XY ta tốn 3 phép nhân
n
2
bit: AC, BD và (A − B)(D − C), 6 phép tính
cộng trừ số
n
2
, 2 phép chuyển chữ số (nhân với luỹ thừa của 2). Do vậy với
cách tính trên ta có độ phức tạp của thuật toán này
T (1) = 1
T (n) = 3T (
n
2
) + Cn
Ta dễ thấy phương pháp chia đôi này sẽ đệ quy log
2
n bước và ở bước cuối
thì chỉ còn 1 bit. Cây đệ quy có chiều cao là log
2

12
2.3 Đọc Ảnh Vệ Tinh
Để hiện thực hoá đều này, ngoài thuật toán ra, chúng ta còn phải quan
tâm đến vấn đề Cấu Trúc Dữ Liệu, cho nên trong phương diện báo cáo
môn học Phân Tích Thuật Toán, chúng tôi chỉ đề cập đến ý tưởng chia -
trị như thế nào của thuật toán, không đề cập sâu vào Cấu Trúc Dữ Liệu.
2.3.1 Vấn Đề
Việc đọc ảnh kích thước là một nhu cầu thiết yếu trong nhiều ngành
khoa học và đời sống hiện nay. Tuy nhiên ta thường gặp nhiều khó khăn
trong việc đọc trực tiếp những bức ảnh kích thước lớn, ảnh vệ tinh là một
ví dụ. Ta biết rằng ảnh chụp của một vệ tinh về một phần nào đó của một
hành tinh hoặc vũ trụ đều là những ảnh có kích thước rất lớn. Những ảnh
này được truyền về mặt đất sau khi chụp và yêu cầu đầu tiên đặt ra cho
những người tiếp nhận là làm sao đọc được nó. Tất nhiên việc đọc trực tiếp
là không thể, vì bộ nhớ của máy có giới hạn rất nhỏ so với kích thước ảnh.
2.3.2 Ý tưởng
Ảnh lớn ban đầu sẽ được cắt thành các ảnh hình vuông nhỏ có kích
thước bằng nhau. Mỗi ảnh nhỏ đó gọi là một ảnh đơn vị. Tiếp đó, ta đánh
dấu tọa độ của các ô vuông nhỏ đó trong bức ảnh lớn. Khi đọc ảnh, ta thiết
kế sao có ảnh được gọi là “vùng nhìn thấy”, sau đó ta chỉ cần đọc những
bức ảnh kề nó.
Sau khi chia nhỏ ảnh và gán mỗi bức ảnh đơn vị thành những điểm
trong mặt phẳng Oxy thì bài toán đến đây quy về bài toán tìm kiếm điểm
kề trong không gian.
Cần lưu ý điều sau: do bức ảnh vệ tinh thường tương đối lớn, nên khi
chia ra số lượng cũng tương đối lớn, nếu dùng những thuật toán thông
thường để tìm những điểm kề với điểm thấy được (toạ độ được đánh dấu
của “vùng nhìn thấy”), khó lòng thực hiện với chi phí thấp.
2.3.3 Thực Hiện
Để thực hiện, trước hết cần một CTDL để lưu trữ, ở đây chúng tôi dùng

điểm tìm kiếm nhất, chúng ta có nhiều cách dựa trên thuật toán tìm láng
giềng gần nhất đã được trình bày phía trên, ở đây chúng tôi đề xuất cải tiến
thuật toán như sau: Trong quá trình tìm kiếm, khi đã tìm được láng giềng
gần nhất ta tiến hành bung độ lớn của bán kính vòng tròn để tìm và đánh
dấu những điểm được cho là gần nhất tiếp theo điểm đã tìm được.
15
Hình 2.4: Minh họa các bước tìm kiếm, màu xanh là các vùng bị cách ly
nhanh chóng
16
Tài liệu tham khảo
[1] ThS.Trần Đức Huyên: phương pháp giải các bài toán trong Tin Học,
NXB Giáo Dục
[2] Ian Parberry: Lecture Notes on Algorithm Analysis and Computational
Complexity Department of Computer Science, University of North
Texas
[3] Internet