Đề thi Phân Tích và Thiết Kế Giải Thuật Cuối kì đại học Bách Khoa TPHCM
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (102.05 KB, 2 trang )
Đại Học Quốc Gia Tp. HCM
Trường Đại Học Bách Khoa
Khoa Khoa Học và Kỹ Thuật Máy Tính
---------------Đề thi Phân Tích và Thiết Kế Giải Thuật
HK2/2013-2014 - Thời gian: 100 phút
(Đề thi gồm 2 trang. Sinh viên khơng được tham khảo tài liệu ngoại trừ một tờ giấy khổ A4
chứa những ghi chú cần thiết)
Câu 1. (2.75 điểm) Hãy trả lời ngắn gọn 6 câu hỏi sau đây.
1.1 Trong số các giải thuật đã được học, hãy nêu một thí dụ về sự đánh đổi giữa thời gian thực thi và
chỗ bộ nhớ (tức là nếu chúng ta chịu tốn thêm chỗ bộ nhớ, thì có thể làm cho thời gian thực thi được
nhanh hơn).
(0.5 điểm)
1.2 Giải thuật xấp xỉ là gì? Cận tỉ số (ratio bound) của một giải thuật xấp xỉ là gì ?
(0.5 điểm)
1.3 Heuristic là gì? Hãy cho một thí dụ về heuristic?
(0.5 điểm)
1.4 Kết hợp giải thuật nhánh-và-cận và heuristic có thể là một phương pháp để giải một bài tốn NPđầy đủ khơng? Hãy giải thích câu trả lời của bạn?
(0.5 điểm)
1.5 Hãy nêu một thí dụ cho mỗi loại bài tốn sau đây: bài tốn bất khả quyết (undecidable), bài tốn P
và bài tốn NP-đầy đủ.
(0.5 điểm)
1.6 Phát biểu độ phức tạp của giải thuật quay lui
(0.25 điểm)
Câu 2 (1.75 điểm)
Tính các bảng m và s khi ta áp dụng giải thuật quy hoạch động để giải bài tốn tính tích chuỗi
ma trận với
n (số ma trận ) = 4, p0 = 8, p1 = 3, p2 = 2, p3 = 19, p4 = 18.
Câu 3 (1.25 điểm)
Xét bài tốn đổi tiền xu cho một số tiền có giá trị tương đương n xu Mỹ sao cho số đồng xu
đổi ra là nhỏ nhất. Thiết kế một giải thuật tham lam để giải bài tốn đổi tiền mà dùng những
loại đồng xu sau đây: quarter, dime, nickel và penny. (Lưu ý: 1 quarter = 25 xu, 1 dime = 10
xu, 1 nickel = 5 xu, 1 penny = 1 xu).
Câu 4 (2 điểm)
Cho một bài tốn tơ màu đồ thị với đồ thị được cho ở hình sau. Trong hình này, một tập màu
hợp lệ để gán cho mỗi đỉnh được ghi bên trong đỉnh.
a) Vẽ cây khơng gian trạng thái minh họa q trình giải bài tốn tơ màu đồ thị dùng giải
thuật backtracking đệ quy. Giả sử thứ tự đỉnh được xét để tơ màu là: x 1, x7, x4, x5, x6, x3, x2.
Chú ý rằng cây khơng gian tìm kiếm phải cho ra mọi lời giải khả hữu của bài tốn.
(1.5 điểm)
1
b) Hãy nêu một ứng dụng thực tế của bài toán tô màu đồ thị.
Câu 5 (2.25 điểm) Cho giải thuật Prim để xây dựng cây bao trùm tối thiểu như sau.
(0.5 điểm)
procedure MST-PRIM (G, w, r);
/* G = (V,E) là đồ thị có trọng số với hàm trọng số w, và r là một đỉnh xuất phát bất kỳ */
begin
Q: = V[G]; /* tạo hàng đợi có thứ tự ưu tiên Q từ tập đỉnh của đồ thị */
for each u ∈ Q do key[u]: = ∞;
key[r]: = 0; p[r]: = NIL;
while Q is not empty do
begin
u: = EXTRACT-MIN(Q);
for each v ∈ Q and w(u, v) < key[v] then
/ * cập nhật các thành phần p và key của đỉnh v */
begin
p[v] := u;
key[v]: = w(u, v)
end
end
end;
a) Phân tích độ phức tạp của giải thuật Prim khi dùng heap hiện thực hàng đợi có thứ tự ưu
tiên và đồ thị là một đồ thị đầy đủ. Giả sử đồ thị được biểu diễn bằng tập danh sách kế cận.
(0.5 điểm)
b) Cho một đồ thị đầy đủ và có trọng số gồm 5 đỉnh A, B, C, D, E. Các trọng số của các cạnh
trong đồ thị như sau: AB = 3, AC = 4, AD = 2, AE = 7, BC = 4, BD = 6, BE = 3, CD = 5, CE
= 8, DE = 6.
Giả sử thành phố xuất phát biểu thị bằng đỉnh A. Cho bài toán Người Thương gia Du hành
(TSP) với đồ thị đầy đủ và có trọng số vừa nêu. Hãy áp dụng giải thuật xấp xỉ để giải bài toán
này. Cho biết lộ trình cận tối ưu tìm thấy và tổng chi phí của lộ trình này. Phát biểu độ phức
tạp của giải thuật xấp xỉ này.
(1.75 điểm)
2
