Số hóa bởi Trung tâm Học liệu

1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG
Đỗ Tuấn Anh TỔ CHỨC DỮ LIỆU CHO LỚP THUẬT TOÁN
CHIA ĐỂ TRỊ VÀ ỨNG DỤNG
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01

TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2014

Số hóa bởi Trung tâm Học liệu

năm học qua. Em cũng muốn gửi lời cảm ơn tới những thành viên lớp đã có những góp ý
chuyên môn cũng như sự động viên về tinh thần rất đáng trân trọng.
Cuối cùng, em xin gửi lời cảm ơn sâu sắc tới tất cả người thân trong gia đình và
những bạn bè em với những động viên dành cho em trong công việc và trong cuộc sống.

Học viên thực hiện luận văn
Đỗ Tuấn Anh

Số hóa bởi Trung tâm Học liệu

4 MỤC LỤC
Trang
Lời cam đoan
Lời cảm ơn
Mục lục iii
Danh mục các bảng v
Danh mục các hình vẽ v

MỞ ĐẦU 1
CHƢƠNG 1. CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN 2
1.1 Các bước cơ bản khi giải bài toán trên máy tính 2
1.2 Phân tích thời gian thực hiện thuật toán 6
1.2.1 Độ phức tạp thuật toán 6
1.2.2 Xác định độ phức tạp của thuật toán 9

3.6.1 Ý tưởng chung 40
3.6.2 Phân tích thuật toán 41
3.6.3 Mô hình thuật toán chia để trị cho bài toán nhân hai số nguyên lớn 44
3.6.4 So sánh độ phức tạp giữa các thuật toán 46
3.7 Tổ chức dữ liệu cho thuật toán chia để trị 46
3.7.1 Biểu diễn dưới dạng bit 46
3.7.2 Biểu diễn dùng mảng và xâu 47
3.8 Thực nghiệm và đánh giá 51
3.8.1 Cài đặt trên C 51
3.8.2 Cài đặt trên C# 59
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN 64
TÀI LIỆU THAM KHẢO 65
Số hóa bởi Trung tâm Học liệu

6 DANH MỤC CÁC BẢNG
Bảng 1.1 Các lớp độ phức tạp tính toán 11
Bảng 1.2 Thời gian chạy của các lớp thuật toán 12
Bảng 2.1 Độ phức tạp của thuật toán tìm kiếm nhị phân 20
Bảng 2.2 Độ phức tạp của thuật toán sắp xếp nhanh 26
Bảng 3.1 So sánh độ phức tạp tính toán của các thuật toán nhân 46

DANH MỤC CÁC HÌNH
Hình 2.1 Thuật toán chia để trị 14
Hình 2.2 Tổ chức dữ liệu cho lớp bài toán chia để trị 15

lớn, luận văn được trình bày trong 3 chương với bố cục như sau:
Chƣơng 1: Các chiến lƣợc thiết kế thuật toán. Giới thiệu tổng quan về các bước
giải bài toán trên máy tính và phân tích đánh giá thời gian thực hiện thuật toán cùng các
chiến lược thiết kế thuật toán cơ bản.
Chƣơng 2: Tổ chức dữ liệu cho lớp thuật toán chia để trị.Trình bày ý tưởng, cơ sở
khoa học của thuật toán chia để trị và cách thức tổ chức dữ liệu cho thuật toán chia để trị
với các bài toán kinh điển.
Chƣơng 3: Ứng dụng thuật toán chia để trị giải bài toán nhân hai số nguyên lớn.
Tập trung phân tích các cách tiếp cận giải bài toán nhân hai số nguyên lớn. Từ đó đề xuất
thuật toán dựa trên tư tưởng chia để trị để giải quyết và thực nghiệm so sánh với các cách
tiếp cận trước đó.
Cuối cùng là kết luận và hƣớng phát triển:Tóm tắtnhững kết quả đạt được, những
hạn chế và nêu lên các hướng phát triển trong tương lai.

Số hóa bởi Trung tâm Học liệu

8 CHƢƠNG 1. CÁC CHIẾN LƢỢC THIẾT KẾ THUẬT TOÁN

1.1 Các bƣớc cơ bản khi giải bài toán trên máy tính
Một thuật toán một thủ tục tính toán được định nghĩa chính xác, mà lấy một giá trị
hoặc một tập các giá trị, được gọi là đầu vào hay dữ liệu vào và tạo ra một giá trị, hoặc
một tập các giá trị, và gọi là đầu ra. Miêu tả một vấn đề thường được xác định nói
chungqua quan hệ đầu vào/đầu ra. Một thuật toán là một dãy bước xác định để chuyển đổi
dữ liệu đầu vào thành dữ liệu đầu ra. Chúng ta có thể xem một thuật toán như một công cụ
để giải quyết một vấn đề tính toán. Việc trình bày rõ ràng một vấn đề nói chung hình
thành mối quan hệ mong muốn đầu vào/đầu ra. Một thuật toán mô tả chính xác một thủ tục
tính toán để đạt được mối liên hệ giữa dữ liệu đầu vào và dữ liệu đầu ra.

kiếm thuật toán giải quyết vấn đề.
Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu:
- Phải biểu diễn được đầy đủ các thông tin nhập và xuất của bài toán
- Phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán.
- Phải cài đặt được trên máy tính với ngôn ngữlập trình đang sửdụng.
Đối với một sốbài toán, trước khi tổchức dữliệu ta phải viết một đoạn chương trình
nhỏ để khảosátxem dữliệu cần lưu trữlớn tới mức độnào.
1.1.3 Xây dựng thuật toán
Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy
thao tác trên cấu trúc dữ liệu sao cho: Với một bộ dữ liệu vào, sau một số hữu hạn bước
thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định.Các đặc trưng của thuật toán:
1. Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng,
không gây nên sự nhập nhằng, lộn xộn, tuỳ tiện, đa nghĩa. Thực hiện đúng các
bước của thuật toán thì với một dữ liệu vào, chỉ cho duy nhất một kết quả ra.
2. Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng lại và
cho kết quả sau một số hữu hạn bước.
3. Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng quá trình
đã định, ta phải được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả
đó được kiểm chứng bằng yêu cầu bài toán.
4. Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kỳ bài toán
nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau.
5. Tính khả thi:Đối với một bài toán, có thể có nhiều thuật toán nhưng chúng phải
cho cùng một output đối với một input. Tuy nhiên chúng có thể khác nhau về
hiệu quả. Hiệu quả thời gian là tốc độ xử lý là nhanh hay chậm. Ta có thể đánh
giá căn cứ vào số bước thực hiện. Hiệu quả không gian là không gian lưu trữ
theo số các đối tượng dùng để ghi nhớ các kết quả (kể cả kết quả trung gian).
Trong Tin học có cả một ngành chuyên đánh giá độ phức tạp của giải thuật, chủ yếu
là đánh giá về hiệu quả thời gian. Thực tế sử dụng cho thấy thách thức về không gian lưu
trữ có thể giải quyết dễ hơn thách thức về thời gian thực hiện.


quan trọng của người lập trình. Kỹ năng này chỉ có được bằng kinh nghiệm tìm và sửa
chữa lỗi của chính mình.Có ba loại lỗi:
- Lỗi cú pháp: Lỗi này hay gặp nhất nhưng lại dễ sửa nhất, chỉ cần nắm vững
ngôn ngữ lập trình là đủ. Một người được coi là không biết lập trình nếu không
biết sửa lỗi cú pháp.
- Lỗi cài đặt: Việc cài đặt thể hiện không đúng thuật toán đã định, đối với lỗi này
thì phải xem lại tổng thể chương trình, kết hợp với các chức năng gỡ rối để sửa
lại cho đúng.

Số hóa bởi Trung tâm Học liệu

11
- Lỗi thuật toán: Lỗi này ít gặp nhất nhưng nguy hiểm nhất, nếu nhẹ thì phải điều
chỉnh lại thuật toán, nếu nặng thì có khi phải loại bỏ hoàn toàn thuật toán sai và
làm lại từ đầu.
1.1.5.2 Xây dựng các bộ dữ liệu kiểm tra
Có nhiều chương trình rất khó kiểm tra tính đúng đắn. Nhất là khi ta không biết kết
quả đúng là thế nào? Vì vậy nếu như chương trình vẫn chạy ra kết quả thì việc tìm lỗi rất
khó khăn. Khi đó ta nên làm các bộ dữ liệu test để thử chương trình của mình. Kinh
nghiệm khi xây dựng các bộ dữ liệu test là:
- Bắt đầu với một bộ test nhỏ, đơn giản, làm bằng tay cũng có được đáp số để so
sánh với kết quả chương trình chạy ra.
- Tiếp theo vẫn là các bộ test nhỏ, nhưng chứa các giá trị đặc biệt hoặc tầm
thường. Kinh nghiệm cho thấy đây là những test dễ sai nhất.
- Các bộ test phải đa dạng, tránh sự lặp đi lặp lại các bộ test tương tự.
- Có một vài test lớn chỉ để kiểm tra tính chịu đựng của chương trình mà thôi. Kết
quả có đúng hay không thì trong đa số trường hợp, ta không thể kiểm chứng
được với test này.
Lưu ý rằng chương trình chạy qua được hết các test không có nghĩa là chương trình
đó đã đúng. Bởi có thể ta chưa xây dựng được bộ test làm cho chương trình chạy sai. Vì

bằng ba tiêu chuẩn trên. Bởi phần cứng phát triển rất nhanh, yêu cầu hữu hiệu
không cần phải đặt ra quá nặng.
Từ những phân tích ở trên, chúng ta nhận thấy rằng việc làm ra một chương trình đòi
hỏi rất nhiều công đoạn và tiêu tốn khá nhiều công sức. Chỉ một công đoạn không hợp lý
sẽ làm tăng chi phí viết chương trình. Nghĩ ra cách giải quyết vấn đề đã khó, biến ý tưởng
đó thành hiện thực cũng không dễ chút nào.
1.2 Phân tích thời gian thực hiện thuật toán
1.2.1 Độ phức tạp thuật toán
Với một vấn đề đặt ra có thể có nhiều thuật toán giải, chẳng hạn người ta đã tìm ra rất
nhiều thuật toán sắp xếp một mảng dữ liệu. Trong các trường hợp như thế, khi cần sử dụng
thuật toán người ta thường chọn thuật toán có thời gian thực hiện ít hơn các thuật toán
khác. Mặt khác, khi bạn đưa ra một thuật toán để giải quyết một vấn đề thì một câu hỏi đặt
ra là thuật toán đó có ý nghĩa thực tế không? Nếu thuật toán đó có thời gian thực hiện quá
lớn chẳng hạn hàng năm, hàng thế kỉ thì đương nhiên không thể áp dụng thuật toán này
trong thực tế. Như vậy chúng ta cần đánh giá thời gian thực hiện thuật toán. Phân tích
thuật toán, đánh giá thời gian chạy của thuật toán là một lĩnh vực nghiên cứu quan trong
của khoa học máy tính. Trong chương này, chúng ta sẽ nghiên cứu phương pháp đánh giá
thời gian chạy của thuật toán bằng cách sử dụng ký hiệu ô lớn, và chỉ ra cách đánh giá thời
gian chạy thuật toán bằng ký hiệu ô lớn. Trước khi đi tới mục tiêu trên, chúng ta sẽ thảo
luận ngắn gọn một số vấn đề liên quan đến thuật toán và tính hiệu quả của thuật toán.
1.2.1.1 Tính hiệu quả của thuật toán
Như đã phân tích ở trên, chúng ta thường xem xét thuật toán, lựa chọn thuật toán để
áp dụng dựa vào các tiêu chí sau:
1. Thuật toán đơn giản, dễ hiểu.
2. Thuật toán dễ cài đặt (dễ viết chương trình)
3. Thuật toán cần ít bộ nhớ

Số hóa bởi Trung tâm Học liệu

13

định thức của ma trận vuông cấp n, ta có thể chọn cỡ của dữ liệu vào là cấp n của ma trận;
còn đối với thuật toán sắp xếp mảng cỡ n thì cỡ của dữ liệu vào chính là cỡ n của mảng.
Đương nhiên là có vô số dữ liệu vào cùng một cỡ. Nói chung trong phần lớn các thuật
toán, cỡ của dữ liệu vào là một số nguyên dương n. Thời gian chạy của thuật toán phụ
thuộc vào cỡ của dữ liệu vào; chẳng hạn tính định thức của ma trận cấp 20 đòi hỏi thời
gian chạy nhiều hơn tính định thức của ma trận cấp 10. Nói chung, cỡ của dữ liệu càng lớn

Số hóa bởi Trung tâm Học liệu

14
thì thời gian thực hiện thuật toán càng lớn. Nhưng thời gian thực hiện thuật toán không chỉ
phụ thuộc vào cỡ của dữ liệu vào mà còn phụ thuộc vào chính dữ liệu vào.
Trong số các dữ liệu vào cùng một cỡ, thời gian chạy của thuật toán cũng thay đổi.
Chẳng hạn, xét bài toán tìm xem đối tượng a có mặt trong danh sách (a
1
,
…
,a
i
,
…
,a
n
) hay
không. Thuật toán được sử dụng là thuật toán tìm kiếm tuần tự: Xem xét lần lượt từng
phần tử của danh sách cho tới khi phát hiện ra đối tượng cần tìm thì dừng lại, hoặc đi hết
danh sách mà không gặp phần tử nào bằng a. Ở đây cỡ của dữ liệu vào là n, nếu một danh
sách với a là phần tử đầu tiên, ta chỉ cần một lần so sánh và đây là trường hợp tốt nhất,
nhưng nếu một danh sách mà a xuất hiện ở vị trí cuối cùng hoặc a không có trong danh
sách, ta cần n lần so sánh a với từng a

như trên là không đơn giản, và biểu thức thu được có thể rất phức tạp.

Số hóa bởi Trung tâm Học liệu

15
Do đó, chúng ta sẽ chỉ quan tâm tớitốc độ tăng(Rate of growth) của hàm T(n), tức là
tốc độ tăng của thời gian chạy khi cỡ dữ liệu vào tăng. Ví dụ, giả sử thời gian chạy của
thuật toán là T(n) = 3n
2
+ 7n + 5 (phép toán sơ cấp). Khi cỡ n tăng, hạng thức 3n
2
quyết
định tốc độ tăng của hàm T(n), nên ta có thể bỏ qua các hạng thức khác và có thể nói rằng
thời gian chạy của thuật toán tỉ lệ với bình phương của cỡ dữ liệu vào.
1.2.1.2 Kí pháp để đánh giá độ phức tạp thuật toán
Giả sử T(n) là thời gian thực hiện một thuật toán nào đó và f(n), g(n), h(n) là các hàm
xác định dương với mọi n. Khi đó ta có độ phức tạp của thuật toán là:
- Hàm Theta lớn:Θ(g(n)) nếu tồn tại các hằng số dương c
1
và c
2
và n
0
sao cho:
c
1
g(n) ≤ T(n) ≤ c
2
g(n) và gọi kí pháp chữ Θ theta lớn, hàm g(n) gọi là giới hạn
chặt của hàm T(n).

>0 để T(n) ≤ c
0
.c
1
f(n) với mọi
n≥ n
0
.Đặt c=c
0
.c
1
ta có điều cần chứng minh.
Quy tắc lấy Max: Nếu đoạn chương trình P có thời gian thực hiện T(n)=O(f(n)+g(n))
thì có thể coi đoạn chương trình đó có độ phức tạp tính toán là O(max( f(n), g(n))).
Chứng minh: T(n)=O(f(n)+g(n)) nên tồn tại n
0
>0 và c>0 để T(n) ≤cf(n) + cg(n), với
mọi n ≥ n
0
vậy T(n) ≤cf(n) +cg(n) ≤ 2cmax (f(n),g(n)) với mọi n ≥ n
0
. Từ đó suy điều cần
chứng minh.
Quy tắc cộng: Nếu P
1
có thời gian thực hiện là T
1
(n)=O(f(n)) và P
2
có thời gian thực

.g(n) với
mọi n ≥ n
2.
Chọn c=max (c
1
,c
2)
và n
0
=max (n
1
,n
2
) ta có với mọi n ≥ n
0
:
T(n)=T
1
(n) + T
2
(n) ≤ c
1
f(n) + c
2
g(n) ≤ cf(n) +cg(n) = c(f(n) +g(n)).
Như vậy ta có điều cần chứng minh.
Quy tắc nhân:Nếu đoạn chương trình P có thời gian thực hiện T(n)=O(f(n)). Khi đó
nếu thực hiện k(n) lần đoạn chương trình P với k(n)=O(g(n)) thì độ phức tạp tính toán sẽ
là: O(f(n) g(n)).
Chứng minh: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n)*T(n), theo

1.2.3.1 Định nghĩa ký hiệu Big-O
Bây giờ chúng ta đưa ra định nghĩa khái niệm một hàm là “ô lớn” của một hàm khác.
Định nghĩa. Giả sử f(n) và g(n) là các hàm thực không âm của đối số nguyên không
âm n. Ta nói “f(n) là ô lớn của g(n)” và viết là f(n)=O( g(n) ) nếu tồn tại các hằng số
dương c và n
0
sao cho f(n) ≤ cg(n) với mọi n ≥ n
0
.[2]
Như vậy, f(n)=O(g(n)) có nghĩa là hàm f(n) bị chặn trên bởi hàm g(n) với một nhân
tử hằng nào đó khi n đủ lớn. Muốn chứng minh được f(n)=O(g(n)), chúng ta cần chỉ ra
nhân tử hằng c , số nguyên dương n
0
và chứng minh được f(n) ≤ cg(n) với mọi n ≥ n
o
.
Ví dụ. Giả sử f(n) = 5n
3
+ 2n
2
+ 13n + 6, ta có:
f(n) = 5n
3
+ 2n
2
+ 13n + 6 ≤ 5n
3
+ 2n
3
+ 13n

- Nếu f(n) = g(n) + g
1
(n) + + g
k
(n), trong đó các hàm g
i
(n) (i=1, ,k) tăng
chậm hơn hàm g(n) (tức là g
i
(n)/g(n) 0, khi n 0) thì f(n) = O(g(n))

Số hóa bởi Trung tâm Học liệu

17
- Nếu f(n)=O(g(n)) thì f(n)=O(d.g(n)), trong đó d là hằng số dương bất kỳ
- Nếu f(n)=O(g(n)) và g(n)=O(h(n)) thì f(n)=O(h(n)) (tính bắc cầu)
Các kết luận trên dễ dàng được chứng minh dựa vào định nghĩa của ký hiệu ô lớn.
Đến đây, ta thấy rằng, chẳng hạn nếu f(n)=O(n
2
) thì f(n)=O(75n
2
), f(n)=O(0,01n
2
),
f(n)=O(n
2
+ 7n + logn), f(n)=O(n
3
), , tức là có vô số hàm là cận trên (với một nhân tử
hằng nào đó) của hàm f(n).

O(n
3
)
O(2
n
)
hằng
logarit
tuyến tính
nlogn
bình phương
lập phương
mũ

Số hóa bởi Trung tâm Học liệu

18
Hằng số: Hầu hết các chỉ thị của các chương trình đều được thực hiện một lần hay
nhiều nhất chỉ một vài lần. Nếu tất cả các chỉ thị của cùng một chương trình có tính chất
này thì chúng ta sẽ nói rằng thời gian chạy của nó là hằng số. Điều này hiển nhiên là điều
mà ta phấn đấu để đạt được trong việc thiết kế thuật toán.
LogN: Khi thời gian chạy của chương trình là logarit tức là thời gian chạy chương
trình tiến chậm khi N lớn dần. Thời gian chạy thuộc loại này xuất hiện trong các chương
trình mà giải một bài toán lớn bằng cách chuyển nó thành một bài toán nhỏ hơn, bằng cách
cắt bớt kích thước một hằng số nào đó. Với mục đích của chúng ta, thời gian chạy có được
xem như nhỏ hơn một hằng số “lớn“. Cơ số của logarit làm thay đổi hằng số đó nhưng
không nhiều: Khi N là 1000 thì logN là 3 nếu cơ số là 10, là 10 nếu cơ số là 2; khi N là một
triệu, logN được nhân gấp đôi. bất cứ khi nào N được nhân đôi, logN tăng lên thêm một
hằng số.
N: Khi thời gian chạy của một chương trình là tuyến tính, nói chung đây là trường

k
), với

Số hóa bởi Trung tâm Học liệu

19
k=1,2,3, , được gọi là các thuật toán thời gian chạy đa thức (Polynomial-time algorithm).
Để so sánh thời gian chạy của các thuật toán thời gian đa thức và các thuật toán thời gian
mũ, chúng ta hãy xem xét bảng sau:
Bảng 1.4Thời gian chạy của các lớp thuật toán
Thời
gian
chạy
Cỡ dữ liệu vào
10
20
30
40
50
60
n
n
2
n
3
n
5
0,00001 giây
0,0001 giây
0,001 giây

17,9 phút
6,5 năm
12,7 ngày
3855 thế kỷ
35,7 năm
2.10
8
thế kỷ
366 thế kỷ
1,3. 10
13
thế kỷ
Trong bảng trên, giả sử mỗi phép toán sơ cấp cần 1 micro giây để thực hiện. Thuật
toán có thời gian chạy n
2
, với cỡ dữ liệu vào n=20 thì thời gian chạy là 20
2
x10
-6
=0,004
giây. Đối với thuật toán hàm mũ, thời gian chạy là chấp nhận được chỉ với các dữ liệu vào
có cỡ rất khiêm tốn, n < 30; khi cỡ dữ liệu vào tăng, thời gian chạy sẽ tăng lên rất nhanh
và trở thành con số khổng lồ. Chẳng hạn, thuật toán với thời gian chạy 3
n
, với dữ liệu vào
cỡ 60, nó đòi hỏi thời gian là 1,3x10
13
thế kỉ! Vì vậy nghiên cứu tìm ra các thuật toán hiệu
quả (chạy nhanh) cho các vấn đề có nhiều ứng dụng trong thực tiễn luôn luôn là sự mong
muốn của các nhà tin học.

21 CHƢƠNG 2. TỔ CHỨC DỮ LIỆU CHO LỚP
THUẬT TOÁN CHIA ĐỂ TRỊ

Trong khoa học máy tính, chia để trị là một mô hình thiết kế thuật toán quan trọng
dựa trên đệ quy với nhiều phân nhánh. Thuật toán chia để trị hoạt động bằng cách chia bài
toán thành nhiều bài toán nhỏ hơn thuộc cùng thể loại, cứ như vậy lặp lại nhiều lần, cho
đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. Sau đó lời giải của các
bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu. Kĩ thuật này là cơ sở
cho nhiều thuật toán hiệu quả. Tuy nhiên, khả năng hiểu và thiết kế thuật toán chia để trị là
một kĩ năng đòi hỏi nhiều thời gian để làm chủ. Trong chương này, tôi sẽ trình bày cách tổ
chức dữ liệu cho lớp thuật toán chia để trị và các bài toán điển hình được giải quyết theo
tiếp cận chia để trị.
2.1 Chiến lƣợc chia để trị
Ý tưởng của chiến lược này như sau: Chia vấn đề cần giải thành một số vấn đề con
cùng dạng với vấn đề đã cho, chỉ khác là cỡ của chúng nhỏ hơn. Mỗi vấn đề con được giải
quyết độc lập. Sau đó, ta kết hợp nghiệm của các vấn đề con để nhận được nghiệm của
vấn đề đã cho. Nếu vấn đề con là đủ nhỏ có thể dễ dàng tính được nghiệm, thì ta giải
quyết nó, nếu không vấn đề con được giải quyết bằng cách áp dụng đệ quy thủ tục trên
(tức là lại tiếp tục chia nó thành các vấn đề con nhỏ hơn,…) [1]. Do đó, các thuật toán
được thiết kế bằng chiến lược chia-để-trị sẽ là các thuật toán đệ quy.
Sau đây là lược đồ của kỹ thuật chia-để-trị:
DivideConquer (A,x)// Tìm nghiệm x của bài toán A.

if (A đủ nhỏ)
Solve (A);
else
Chia bài toán A thành các bài toán con A

đúng một bài toán nhỏ hơn, chẳng hạn như thuật toán tìm kiếm nhị phân, dùng cho việc
tìm khóa trong một danh sách đã sắp xếp. Khi thiết kế thuật toán giải quyết một vấn đề
bằng kỹ thuật chia-để-trị thì thuật toán chúng ta thu được là thuật toán đệ quy. Thuật toán
đệ quy được biểu diễn trong các ngôn ngữ lập trình bậc cao bởi các hàm đệ quy. Đó là các
hàm chứa các lời gọi hàm đến chính nó. Trong mục này chúng ta sẽ nêu lên các đặc điểm
của thuật toán đệ quy và phân tích hiệu quả (về không gian và thời gian) của thuật toán đệ
quy là cơ sở cho thuật toán chia đê trị. Đệ quy là một kỹ thuật đặc biệt quan trọng để giải
quyết vấn đề. Có những vấn đề rất phức tạp, nhưng chúng ta có thể đưa ra thuật toán đệ
quy rất đơn giản, sáng sủa và dễ hiểu. Cần phải hiểu rõ các đặc điểm của thuật toán đệ quy
để có thể đưa ra các thuật toán đệ quy đúng đắn.
Khi đó, tổ chức dữ liệu cho lớp bài toán chia để trị được mô tả như sau:

Hình 2.4Tổ chức dữ liệu cho lớp bài toán chia để trị
Trong đó:
 Bài toán ban đầu được chia thành k bài toán con.
 Đầu vào của bài toán ban đầu n, m, …được phân nhỏ thành đầu vào lần lượt
của các bài toán con là n
i
, m
i
(i=1 k)
 Đầu ra bài toán ban đầu o được chia thành các đầu ra o
i
(i=1 k)
Giải thuật đệ quy cho một vấn đề cần phải thoả mãn các đòi hỏi sau:
1. Chứa lời giải cho các trường hợp đơn giản nhất của vấn đề. Các trường hợp này
được gọi là các trường hợp cơ sở hay các trường hợp dừng.

Số hóa bởi Trung tâm Học liệu


lời giải các bài toán nhỏ để tạo ra kết quả của bài toán ban đầu. Để tính độ phức tạp của
các thuật toán chia để trị, người ta thường sử dụng định lý tổng quát sau:
Định lý (Mastertheorem): Cho
n
T n aT f n
b
, ta có
1. Nếu
n
af cf n
b
với c> 1 thì
log
b
a
T n n
.

Số hóa bởi Trung tâm Học liệu

24
2. Nếu
n
af cf n
b
với c< 1 thì
T n f n
.
3. Nếu
n

f n af n b a f n b a f n b

Trường hợp 1: Nếu
n
af cf n
b
với c> 1, ta có:
2
2
1
1
1
1

1
k
k
k
k
fn
c af n b
af n b
c a f n b
a f n b
c a f n b

Như vậy, tổng trên bằng tổng dãy cấp số nhân (hệ số lũy tiến bằng c) có số hạng lớn
nhất là
kk
a f n b

Một ví dụ lâu đời của thuật toán chia để trị là thuật toán Cooley-Tukey [3] cho biến
đổi Fourier rời rạc. Thuật toán này được phát hiện bởi Gauss năm 1805 nhưng ông không
phân tích số phép tính của thuật toán và thuật toán này chỉ trở nên phổ biến khi được phát
hiện lại hơn một thế kỉ sau đó. Trong toán học, phép biến đổi Fourier rời rạc, đôi khi còn
được gọi là biến đổi Fourier hữu hạn, là một biến đổi trong giải tích Fourier cho các tín
hiệu thời gian rời rạc. Đầu vào của biến đổi này là một chuỗi hữu hạn các số thực hoặc số
phức, làm biến đổi này là một công cụ lý tưởng để xử lý thông tin trên các máy tính. Đặc
biệt, biến đổi này được sử dụng rộng rãi trong xử lý tín hiệu và các ngành liên quan đến
phân tích tần số chứa trong một tín hiệu, để giải phương trình đạo hàm riêng, và để làm
các phép như tích chập. Biến đổi này có thể được tính nhanh bởi thuật toán biến đổi
Fourier nhanh [2, 3, 4].
2.4.1 Lớp bài toán tìm kiếm
2.4.1.1 Thuật toán tìm kiếm nhị phân
a) Ý tƣởng: Thuật toán tìm kiếm nhị phân là thuật toán được thiết kế dựa trên chiến
lược chia-để-trị. Cho mảng A cỡ n được sắp xếp theo thứ tự tăng dần: A[0] ≤…≤ A[n-1].
Với x cho trước, ta cần tìm xem x có chứa trong mảng A hay không, tức là có hay không
chỉ số 0 ≤ i ≤ n-1 sao cho A[i] = x[3].
Kỹ thuật chia-để-trị gợi ý ta: Chia mảng A[0…n-1] thành 2 mảng con cỡ n/2 là
A[0…k-1] và A[k+1…n-1], trong đó k là chỉ số đứng giữa mảng. So sánh x với A[k]. Nếu
x = A[k] thì mảng A chứa x và i = k. Nếu không, do tính được sắp của mảng A, nếu x
A[k] ta tìm x trong mảng A[0…k-1], còn nếu x A[k] ta tìm x trong mảng A[k+1…n-1].
Áp dụng cho bài toán sau:
- Input: Dãy gồm N số nguyên k
1
, k
2
, , k
N
đôi mộ
nguyên x.