I.
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
  
BÀI TẬP LỚN
PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
Giáo viên hướng dẫn: TS. Nguyễn Khanh Văn
Học viên thực hiện : Trương Thảo Nguyên CB120098
Vũ Đình Phú CB120104
Nguyễn Thị Thúy Liên CB120046
Lớp: Công nghệ thông tin 2 (KT)
Chuyên ngành: Công nghệ thông tin (KT)
Đề bài: Đề số 01
HÀ NỘI 11 – 2012
Mục lục
1. Bài 1: Sách MIT, Problem 5.2 Câu a,b,c,d
1.1. Phát biểu bài toán
Cho một mảng A chưa sắp xếp gồm n phần tử, tìm phần tử có giá trị x trong mảng A.
Cân nhắc chiến lược sử dụng ngẫu nhiên sau: lấy một số ngẫu nhiên i trong tập chỉ số của
A (1 ≤ i ≤ length of A). Nếu A[i] = x thì tìm được x trong mảng A. Nếu không, lặp lại
bước trên cho đến khi tìm được một chỉ số j của mảng A thỏa mãn A[j] = x hoặc đã duyệt
qua mọi phần tử của A.
a. Viết giả code cho thủ tục RANDOM-SEARCH để cài đặt chiến lược trên
b. Giả sử rằng, có đúng một chỉ số i thỏa mãn A[i] = x. Tính kì vọng số lần thử trước
khi tìm được x và thuật toán RANDOM-SEARCH dừng lại
c. Tổng quá hóa lời giải ở câu b, giả sửa rằng có k ≥ 1 chỉ số i mà A[i] = x. Tính kì
vọng số lần thử trước khi tìm được x và thuật toán RANDOM-SEARCH dừng lại.
d. Giả sửa rằng không có chỉ số nào để A[i] = x. Tính kì vọng số lần thử để kiểm tra
qua mọi phần tử của A và thuật toán RANDOM-SEARCH dừng lại.
1.2. Lời giải
a. Giả code của thuật toán RANDOM-SEARCH

Vậy kì vọng của số lần thử để tìm được x hoặc thuật toán kết thúc là
E = p)
j-1
* p
Mà p = 1/n Vậy E = n
c. Tính kì vọng của số lần thử nếu như tồn tại k ≥ 1 chỉ số i mà A[i] = x
Từ chứng minh câu b ta vẫn có kết quả ta vẫn có Trong đó p là xác suất để chọn đúng
chỉ số i mà A[i] = x là Pr(A[i] = x).Vậy bài toán quy về việc tính p.
Vì tồn tại k ≥ 1 chỉ số i để A[i] = x nên xác suất để chọn đúng chỉ số i mà A[i] = x là
Pr(A[i] = x) = k/n
Vậy E = 1/(k/n) = n/k
d. Tính kì vọng của số lần thử nếu như không tồn tại chỉ số i mà A[i] = x
Vì trong mảng A không tồn tại phần tử nào có giá trị là x cho nên số lần thử (số vòng lặp)
để thuật toán dừng chính là số lần thử để kiểm tra hết tất cả n phần tử trong mảng A có
chỉ số lần lượt từ 1 đến n. Bài toán này giống với bài toán “thu thập coupon”
Gọi X là số lần thử cho đến khi kiểm tra hết cả n phần tử của mảng A
Gọi X
i
là số lần thử mà khi đó đã kiểm tra được i-1 phần tử của mảng A (cho đến khi
kiểm tra được phân từ thứ i).
Vậy X =
Xác suất để tại một lần thử, kiểm tra phần tử cũ (phần tử đã so sánh giá trị với x trước đó)
khi đã mà đã có i-1 phần tử được kiểm tra là q
i
= (i-1)/n
Xác suất để tại một lần thử, kiểm tra được phần tử mới (phần tử chưa so sánh giá trị với x
trước đó) khi mà đã có i-1 phần tử được kiểm tra là p
i
= 1- q
i

- Giả sử thành phố V
n
là kề cận với V
i
. Vì chúng ta cần quảng đường ngắn nhất từ V
i

tới V
1
và tới V
n
, sau đó quay lại tới V
i
mà đi qua tất cả các thành phố.
- Định nghĩa t(i,j) , i<j là quảng đường ngắn nhất từ V
i
, đi qua V
1
, và quay lại V
j
. Khi
đó t(i, j) được tính toán như sau:
o t(i, j) = t(i, j-1) + d(v
j
-1, v
j
) if j > i + 2
o t(i, j) = min{ t(k, i) + d(v
k
, v

L(0,n-1) L(1,n-1) L(2,n-1) L(3,n-1) L(4,n-1) … L(n-2,n-1)
L(0,n) L(1,n) L(2,n) L(3,n) L(4,n) … L(n-2,n) L(n-1,n)
c. Đánh giá thuật toán
Nhận thấy, có thể tính toán số phép toán dựa trên bảng sau
1
1 1
1 1 2
1 1 1 3
1 1 1 1 4

1 1 1 1 1 n-2
1 1 1 1 1 1 n-1
Vậy ta có tổng số phép toán phải xữ lý trong bài toán shorstest bitonic là:
1 + 2+4 +6 +8 + … +2(n-1) =
3. Bài 3: Câu a&d
3.1. Phát biểu bài toán
Tại một siêu thị điện máy người ta cho mỗi khách hàng (KH) khi mua với trị giá hơn 1
triệu sẽ được bắt thăm để lĩnh thưởng (mỗi tháng một lần). Các hồ sơ gồm tên KH, CMT
và số thăm bắt được sẽ được lưu trữ theo nguyên tắc dùng bảng băm tại đó mỗi ô (slot)
có thể sẽ trỏ đến một danh sách móc nối bản ghi trong đó các số thăm đều có cùng một
giá trị băm. Giả sử trong tháng hai vừa qua số lượng KH đã được bắt thăm là 20000.
Trong câu a-b-c-d, giả thiết siêu thị dùng bảng băm kích thước 20000.
a) Kỳ vọng số lượng ô còn trống là bao nhiêu?
b) Kỳ vọng số lượng ô có đúng 2 lá thăm rơi vào là bao nhiêu?
c) Kỳ vọng số lượng ô có nhiều hơn 2 lá thăm rơi vào là bao nhiêu?
d) Giả sử số lượng KH VIP, tức là KH mua với trị giá hơn 20 triệu, trong tháng hai
không nhiều hơn 100. Tính xác suất để sự kiện tồn tại một ô có chứa ít nhất 2 lá
thăm của khách hàng VIP.
e) Siêu thị không muốn lãng phí số lượng ô trống; Vậy kích thước bảng băm phù hợp
phải là bao nhiêu để số lượng ô trống là ít hơn hơn 10%

-1
7357
d. Xác suất để tồn tại một ô có chứa ít nhất 2 lá thăm của khách hàng VIP
Với n là số khách hàng VIP (n ≤ 100) và m là số ô trong bảng băm (m=20000)
Xác suất để một lá thăm xác định rơi vào một ô trong bẳng băm là (1/m)
Xác suất để ô thứ k bất kì chứa ít nhất M=2 lá thăm của khách hàng VIP:
Pr[ô k chứa ≥ M thăm] ≤
Nhận thấy xác suất để tồn tại một ô có chứa ít nhất M lắ thăm của khách hàng VIP cũng
chính là xác suất để một ô chứa nhiều hơn hoặc bằng M lá thăm:
Pr [tồn tại ô chứa ≥ M thăm] ≤
Vậy Pr ≤

0,0012375
4. Bài 4: Thuật toán sắp xếp Bucket Sort
4.1. Phát biểu bài toán
Trình bày đầy đủ thuật toán sắp xếp Bucket Sort. Hãy cho biết trong điều kiện như thế
nào thì Bucket Sort có thể đạt được thời gian thực hiện O(n). Hãy lập luận và có chứng
minh cở sở toán học (xác suất) chặt chẽ.
4.2. Lời giải
a. Thuật toán sắp xếp Bucket Sort
Bài toán: Một tập gồm n ≤ 2
m
số nguyên được chọn ngẫu nhiên từ [0,2
k
) k ≥ m có thể
được sắp xếp với thời gian kì vọng là O(n). Để đơn giản bài toán có thể quy về một tập
gồm các số được chọn ngẫu nhiên từ [0,1) có thể được sắp xếp với thời gian kì vọng là
O(n) (chia tất cả các phần tử của dãy ban đầu cho 2
k
)

Gọi n
i
là số lượng phần tử được phân bố vào bucket B[i] Trong trường hợp tổng quát,
insertion sort chạy với chi phí là hàm bậc 2 của số phần tử nên ta có tổng thời gian để
thực hiện bucket sort là:
Thời gian tính toán trung bình (kì vọng):) (1)
Vậy ta phải tìm .
Gọi X
ij
là biến ngẫu nhiên chỉ báo (indicator random variables) của sự kiện phần tử A[j]
được phân bố vào bucket i. Xác suất để phần tử A[j] được phân bổ vào bucket I là:
Pr(A[j] rơi vào bucket i) = 1/n.
(do có n bucket và các phần tử A[j] sinh ra từ phân bố xác suất đều).Vậy :
Do đó:
Suy ra
E[(X
ij
)
2
] = 0
2
* Pr(A[j] khổng rơi vào bucket i ) + 1
2
* Pr(A[j] rơi vào bucket i)

E[(X
ij