Sau đây là một số bài tập các chương mình đã giải kết hợp sự giải thích của thầy ,hy vọng có thể giúp các anh (chị ) qua tốt được môn này !
Chương 1:
----------------------------------------------------------------------------------
Chương 2:
----------------------------------------------------------------------------------
1. Given a recursive program with the following
recurrence relation:
C(n) =
2C(n/3) + 1 for n >1
with C(1) = 1
Solve the recurrence relation to find the complexity of the program.
Solution:
Ta có:
C(n)=2C(n/3)+1
C(n/3)=2C(n/9)+1
C(n/9)=2C(n/27)+1
-
C(n)=2*C(n/3)+1
-
C(n)=2[2C(n/9)+1]+1=4C(n/9)+2+1=4*C(n/9)+3
-
C(n)=4[2C(n/27)+1]+2+1=8C(n/27)+4+2+1=8*C(n/9)+7
ð C(k)=2^k * C(n/3^k)+ (2^k-1)
Áp dụng dữ
kiện đề C(1)=1.
Để
ð C(k)=2^(log3n)*C(1)+ (2^(log3n)-1)=2*2^(log3n)-1=2*n^(log32)-1
Vậy độ phức tạp
của chương trình trên là : O
.
Chương 3:----------------------------------------------------------------------------------
Chương 4:
----------------------------------------------------------------------------------
Chương 5:
----------------------------------------------------------------------------------
Chương 7:
----------------------------------------------------------------------------------
2. Can combining backtracking and heuristics be a method to solve a NP-complete problem? Explain your answer.
Kết hợp backtracking và heuristics có thể là một phương pháp để giải bài toán NP-đầy đủ không ? Giải thích câu trả lời của bạn.
Solution: (Xem trong slide có 1 số phương pháp giải )
OK! Tuy nhiên thời gian chạy sẽ là hàm mũ , kết hợp heuristisc vào backtracking nhầm tăng hiệu quả của giải thuật backtracking,hiệu quả ở đây là chất lượng của lời giải ,cũng như thời gian chạy.
3. Can greedy algorithm be a method to solve an NP-complete problem? Explain your answer.
Giải thuật tham lam(Greedy) có thể là một phương pháp để giải bài toán NP-đầy đủ không ? Giải thích câu trả lời của bạn.
Solution:
Ok! Chúng ta có thể ứng dụng, tuy nhiên chất lượng lời giai không phải lúc nào cũng là tối ưu.
4. What are metaheuristics? Can we use a metaheuristics to solve a NP-complete problem? Metaheuristics là gì ?Chúng ta có thể sử dụng metaheuristic để giải bài toán NP-đầy đủ không ?
Solution:
Meta heuristic là loại heuristic tổng quát có thể áp dụng cho nhiều lớp bài toán ,thường nó họ của những giải thuật tìm kiếm như: giải thuật mô phỏng luyện kim, giải thuật di truyền.... Chúng ta có thể sẽ sử dụng metaheuristics để giải bài toán NP-complete, tuy nhiên metaheuristic cũng như 1 số giải thuật khác cố gắng tìm lời giải tối ưu của bài toán trong thời gian đa thức,nhưng nó không đảm bảo rằng sẽ tìm ra lời giải tối ứu.
