Công thức truy hồi chia để trị

.. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Công thức truy hồi chia để trị1(đang sửa) Trần Vĩnh Đức HUST Ngày 7 tháng 8 năm 2013 1Tham khảo: Mathematics for CS, MIT Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 1 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Bài toán tháp Hà Nội . . . Hình : Nguồn: wikipedia Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 2 / 22 Có 3 cái cọc và trên một chiếc cọc đặt n cái đĩa với đường kính giảm dần. Cần ít nhất bao nhiêu lần di chuyển để chuyển hết cả n đĩa sang cọc bên cạnh sao cho • mỗi lần chỉ di chuyển một đĩa • mỗi đĩa có thể dịch chuyển từ một cọc này sang một cọc khác bất kỳ, nhưng không được để một chiếc đĩa lớn lên trên một chiếc đĩa khác có đường kính nhỏ hơn? .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị . .Định nghĩa .Tn := số lần chuyển ít nhất cho n đĩa. T1 = 1 T2 = 3 T3  7. Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 3 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị . . . “mcs-ftl” — 2010/9/8 — 0:40 — page 285 — #291 10.1. The Towers of Hanoi 285 2 3 4 5 6 7 8 Figure 10.2 The 7-step solution to the Towers of Hanoi problem when there are n D 3 disks. 2 3 4 Figure 10.3 A recursive solution to the Towers of Hanoi problem. Hình : Lời giải gồm 7 bước khi bài toán với 3 đĩa Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 4 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Cận trên Tn  Tn1 + 1 + Tn1 = 2Tn1 + 1: “mcs-ftl” — 2010/9/8 — 0:40 — page 285 — #291 10.1. The Towers of Hanoi 285 2 3 4 5 6 7 8 Figure 10.2 The 7-step solution to the Towers of Hanoi problem when there are n D 3 disks. 2 3 4 Figure 10.3 A recursive solution to the Towers of Hanoi problem. Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 5 / 22 Ta có một lời giải đệ quy như sau: • Đầu tiên chuyển n 1 đĩa trên cùng từ cột 1 sang cột 3: Cần ít nhất Tn1 bước. • Chuyển đĩa n sang cột 2: Cần 1 bước. • Chuyển n 1 đĩa từ cột 3 sang cột 2: Cần ít nhất Tn1 bước. Vậy Tn  Tn1 + 1 + Tn1 = 2Tn1 + 1: . .Ví dụ . • T3  2
3 + 1 = 7. • T4  2
7 + 1 = 15. .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Cận dưới Để chuyển được đĩa n lớn nhất sang cột 2: Ta phải chuyển n 1 đĩa trên nó sang cột 3:  Tn1 bước. Chuyển đĩa n sang cột 2 (sau bước cuối của chuyển đĩa n):  1 bước. Để chuyển n 1 đĩa từ cột 3 sang cột 2:  Tn1 bước Vậy ta được .. . Tn  Tn1 + 1 + Tn1 = 2Tn1 + 1 Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 6 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Công thức tường minh . . . Tn = 2Tn1 + 1 = 2n 1 . .Chứng minh quy nạp theo n. . Đặt P(n) là mệnh đề ”Tn = 2n 1”. Bước cơ sở: T1 = 21 1 = 1 đúng. Bước quy nạp: Giả sử Tn = 2n 1. Ta có Tn+1 = 2Tn + 1 = 2(2n 1) + 1 = 2n+1 1: Vậy mệnh đề P(n+ 1) là đúng. Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 7 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Một chứng minh khác Tn = 1 + 2Tn1 = 1 + 2(1 + 2Tn1) = 1 + 2 + 4(1 + 2Tn3) = 1 + 2 + 4 + 8Tn3 ... = 1 + 2 + 4 +


+ 2n2 + 2n1T1 = 2n 1 Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 8 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Sắp xếp trộn Để sắp xếp dãy x1; x2; : : : ; xn với n là lũy thừa của 2, ta thực hiện: 1 Sắp xếp hai dãy x1; x2; : : : ; xn/2 và xn/2+1; xn/2+2; : : : ; xn 2 Trộn hai dãy đã sắp Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 9 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị . .Ví dụ . Ta sắp xếp dãy sau theo thứ tự tăng dần 10; 7; 23; 5; 2; 8; 6; 9! (5; 7; 10; 23) (2; 6; 8; 9) Nửa đầu Nửa sau Kết quả 5; 7; 10; 23 2; 6; 8; 9 5; 7; 10; 23 6; 8; 9 2 7; 10; 23 6; 8; 9 2; 5 7; 10; 23 8; 9 2; 5; 6 10; 23 8; 9 2; 5; 6; 7 10; 23 9 2; 5; 6; 7; 8 10; 23 2; 5; 6; 7; 8; 9 2; 5; 6; 7; 8; 9; 10; 23 Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 10 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Đánh giá thuật toán Sắp xếp trộn T(n) := số phép so sánh thuật toán dùng: Trộn cần n 1 phép so sánh. Sắp xếp hai dãy con cần 2T(n/2) phép so sánh. Vậy ta được { T(n) = 2T(n/2) + n 1 T(1) = 0 . .Ví dụ . T(2) = 1 T(4) = 5 T(8) = 2
5 + 7 = 17 T(16) = 2
17 + 15 = 49 Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 11 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị . .Công thức tường minh . T(n) = n 1 + 2T(n/2) = n 1 + 2(n/2 1 + 2T(n/4)) = (n 1) + (n 2) + 4T(n/4) : : : = (n 1) + (n 2) +


+ (n 2i) + 2iT(n/2i) : : : = (n 1) + (n 2) +


+ (n 2logn1) + 2lognT(1) = logn1∑ i=0 ( n 2i) = logn1∑ i=0 n logn1∑ i=0 2i = n logn (2logn 1) = n logn n+ 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 12 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Một công thức truy hồi . .Ví dụ . { S(1) = 0 S(n) = S(⌊n/2⌋) + S(⌈n/2⌉) + 1 Ta thử với vài ví dụ S(1) = 0 S(2) = 1 S(3) = 2 S(4) = 3 S(5) = 1 + 2 + 1 = 4 Dự đoán: S(n) = n 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 13 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị S(n) = n 1 . .Kiểm tra bằng quy nạp mạnh. . Đặt P(n) là mệnh đề ”S(n) = n 1”. Bước cơ sở: P(1) = 0 là đúng. Bước quy nạp: Giả sử P(1);P(2); : : : ;P(n) đúng. S(n+ 1) = S(⌊(n+ 1)/2⌋) + S(⌈(n+ 1)/2⌉) + 1 = (⌊(n+ 1)/2⌋ 1) + (⌈(n+ 1)/2⌉ 1) + 1 = n+ 1 2 + 1 = n Vậy P(n+ 1) đúng. Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 14 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Công thức truy hồi Chia để trị . .Định nghĩa . Công thức truy hồi chia để trị có dạng T(x) = k∑ i=1 aiT(bix+ ϵi(x)) + g(x) với a1; a2; : : : ; ak > 0. 1 > b1; b2; : : : ; bk > 0. g(x) là một hàm thỏa mãn jg′(x)j bị chặn bởi một đa thức. jϵi(x)j = O(x/ log2 x). Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 15 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ Công thức T(x) = 2T(x 1) + 1 không phải chia để trị (b1 = 1). Công thức T(x) = 2T(x/2) + x 1 là chia để trị a1 = 2; b1 = 1/2; g(x) = x 1: Công thức S(x) = S (⌊x 2 ⌋) + S (⌈x 2 ⌉) + 1 = S (x 2 + (⌊x 2 ⌋ x 2 )) + S (x 2 + (⌈x 2 ⌉ x 2 )) + 1 là chia để trị với a1 = 1; b1 = 1/2; ϵ1(x) = ⌊x 2 ⌋ x 2 ; a2 = 1; b2 = 1/2; ϵ2(x) = ⌈x 2 ⌉ x 2 ; g(x) = 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 16 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ Công thức T(x) = 2T(x 1) + 1 không phải chia để trị (b1 = 1). Công thức T(x) = 2T(x/2) + x 1 là chia để trị a1 = 2; b1 = 1/2; g(x) = x 1: Công thức S(x) = S (⌊x 2 ⌋) + S (⌈x 2 ⌉) + 1 = S (x 2 + (⌊x 2 ⌋ x 2 )) + S (x 2 + (⌈x 2 ⌉ x 2 )) + 1 là chia để trị với a1 = 1; b1 = 1/2; ϵ1(x) = ⌊x 2 ⌋ x 2 ; a2 = 1; b2 = 1/2; ϵ2(x) = ⌈x 2 ⌉ x 2 ; g(x) = 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 16 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ Công thức T(x) = 2T(x 1) + 1 không phải chia để trị (b1 = 1). Công thức T(x) = 2T(x/2) + x 1 là chia để trị a1 = 2; b1 = 1/2; g(x) = x 1: Công thức S(x) = S (⌊x 2 ⌋) + S (⌈x 2 ⌉) + 1 = S (x 2 + (⌊x 2 ⌋ x 2 )) + S (x 2 + (⌈x 2 ⌉ x 2 )) + 1 là chia để trị với a1 = 1; b1 = 1/2; ϵ1(x) = ⌊x 2 ⌋ x 2 ; a2 = 1; b2 = 1/2; ϵ2(x) = ⌈x 2 ⌉ x 2 ; g(x) = 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 16 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Định lý Akra-Bazzi . .Định lý . Nếu T(x) là một công thức truy hồi chia để trị, thì T(x) =  ( xp + xp ∫ x 1 g(u) up+1 du ) trong đó p là số thực thỏa mãn k∑ i=1 aibip = 1: Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 17 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ 1 Công thức truy hồi T(x) = 2T(x/2) + x 1 là chia để trị với a1 = 2; b1 = 1/2; k = 1; g(x) = x 1 Trước hết ta tìm p thỏa mãn 2(1/2)p = 1: Ta được p = 1. Theo công thức Akra-Bazzi ta được T(x) =  ( x+ x ∫ x 1 u 1 u2 du ) =  ( x+ x ( ln x+ 1x 1 )) = (x ln x) Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 18 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ 2 Công thức truy hồi T(x) = 2T (x 2 ) + 8 9 T ( 3x 4 ) + x2 là chia để trị với: a1 = 2; b1 = 1/2; a2 = 8/9; b2 = 3/4; g(x) = x2: Tìm p: 2 ( 1 2 )p + 8 9 ( 3 4 )p = 1 =) p = 2: Theo công thức Akra-Bazzi, ta được: T(x) =  ( x2 + x2 ∫ x 1 u2 u3 du ) =  ( x2 + x2 ln x ) = (x2 ln x): Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 19 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ 3 Xét công thức truy hồi chia để trị T(x) = 3T(x/3) + 4T(x/4) + x2 Tìm p thỏa mãn công thức 3(1/3)p + 4(1/4)p = 1 Thử p = 1 3 1 3 + 4 1 4 = 2 > 1 Thử p = 2: 1 3 + 1 4 = 7 2 < 1 Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 20 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Ví dụ 3 (tiếp) T(x) =  ( xp + xp (∫ x 1 u2 up+1 du )) =  ( xp + xp (∫ x 1 1 up1 du )) =  ( xp + xpx2p ) =  ( xp + x2 ) =  ( x2 ) (vì p < 2) Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 21 / 22 .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . .. . Công thức truy hồi chia để trị Tổng quát hóa Ví dụ 3 . .Định lý . Nếu g(x) = (xt) với t  0 và ∑ki=1 aibit < 1, thì ta có T(x) = (g(x)): Trần Vĩnh Đức | HUST | Ngày 7 tháng 8 năm 2013 22 / 22