Quá trình tham gia quản lý khoa học và công nghệ của cộng đồng đang là một xu hướng phát triển mới ở Việt Nam. Sự phát triển này đáp ứng đòi hỏi ngày càng cao trong lĩnh vực khoa học và công nghệ và đời sống xã hội. Bài viết này sẽ tập trung trình bày 3 vấn đề chính. i. Khái quát các mô hình quản lý khoa học và công nghệ của cộng đồng hiện nay; ii. Tìm hiểu hai mô hình cộng đồng tham gia quản lý khoa học và công nghệ ở tỉnh Hà Nam; Đưa ra một số nhận xét, kiến nghị cho Hà Nam nói riêng và cả nước nói chung. Show Vi bao là phương pháp hiệu quả giúp bảo quản các chất sinh học. Thông qua cơ chế bao gói của các polymer có nguồn gốc từ protein, polysaccharide, các hợp chất tự nhiên (polyphenol, carotenoid, …) cũng như vi sinh vật có lợi (nấm men, probiotic) giúp bảo vệ trong các điều kiện bất lợi của môi trường. Ứng dụng các hạt vi bao trong chế biến thực phẩm giúp sản phẩm kéo dài thời gian sử dụng, nâng cao khả năng kháng oxy hóa và cải thiện khả năng sống sót của probiotic. Nghiên cứu nhằm đánh giá ảnh hưởng của việc sử dụng than sinh học thay thế một phần phân khoáng đến sinh trưởng và năng suất ngô tại Việt Trì, Phú Thọ. Thí nghiệm thực hiện trên giống ngô VS36. Các công thức thí nghiệm được bố trí theo kiểu khối ngẫu nhiên hoàn chỉnh với 3 lần nhắc lại. Theo dõi các chỉ tiêu về sinh trưởng, năng suất và đánh giá hiệu quả sản xuất ngô. Kết quả thí nghiệm chỉ ra rằng khi sử dụng than sinh học thay thế cho 20% lượng phân khoáng, cây ngô vẫn có khả năng sinh trưởng phát triển tốt và cho năng suất đạt 42,68 tạ/ha tương đương với công thức đối chứng. Hiện nay, tại chùa Bảo Ninh Sùng Phúc (huyện Chiêm Hóa, Tuyên Quang) còn lưu giữ được tấm bia cổ duy nhất thuộc các tỉnh miền núi phía Bắc nước ta có niên đại từ thời nhà Lý. Nội dung văn bia chép về dòng họ Hà và những đóng góp của dòng họ này đối với vùng đất Vị Long nói riêng và đất nước nói chung ở thế kỷ XI - XII. Trong đó phải kể đến công lao to lớn của nhân vật lịch sử Hà Di Khánh. Cá chình hoa (Anguilla marmorata) được nuôi thử nghiệm trong lồng nổi ở hồ Hòa Mỹ (Phong Điền – Thừa Thiên Huế) với hai loại thức ăn là cá tạp tươi và thức ăn công nghiệp. Theo dõi các yếu tố môi trường như nhiệt độ, pH, hàm lượng oxy hòa tan mặc dù có biến động nhưng đều nằm trong ngưỡng chịu đựng của cá. Sau 16 tháng nuôi cá được cho ăn bằng cá tạp tươi có trọng lượng trung bình 826,35±61,35g/con; cá nuôi bằng thức ăn công nghiệp đạt trong lượng trung bình 538,4±30,51g/con. Tốc độ tăng trưởng của cá nuôi bằng các loại thức ăn khác nhau có sự sai khác có ý nghĩa thống kê (P<0,05). Giá bán cá chình ở các kích cỡ khác nhau có sự chênh lệch nhau khá lớn và đã ảnh hưởng đến hiệu quả kinh tế ở các lô thí nghiệm. Cụ thể: lô nuôi bằng cáp tạp giá bán 320.000đ/kg đã cho lãi hơn 9,5 triệu đồng; lô nuôi bằng thức ăn công nghiệp giá bán là 290.000đ/kg, khối lượng cá thu được ít nên đã bị lỗ hơn 17,5 triệu đồng. Điều này cho thấy việc nuôi cá chình nên sử dụng thức ăn tươi sống. Từ khoá: An... Toán rời rạc là một môn toán dành riêng cho ngành Công nghệ thông tin. Toán rời rạc nghiên cứu lĩnh vực giải quyết các bài toán trên các đối tượng rời rạc, cụ thể là các cấu hình tổ hợp (chỉnh hợp, tổ hợp, hoán vị, ...), đại số Boole đồ thị. Các bài toán trên các cấu hình tổ hợp là: bài toán đếm, bài toán tồn tại, bài toán liệt kê. Các bài toán trên đại số Boole là chuẩn tắc hóa và tối thiểu hóa biểu thức Boole,. Các bài toán trên đồ thị là: bài toán tìm đường đi ngắn nhất, bài toán tìm cây phủ nhỏ nhất, bài toán tìm luồng cực đại. Trên cơ sở kinh nghiệm qua nhiều năm giảng dạy môn học này tại các trường trong Đại học Đà nẵng, chúng tôi soạn giáo trình này để dùng cho hệ kỹ sư, hệ cử nhân, hệ cao đẳng chuyên ngành công nghệ thông tin. Tài liệu được trình bày thành 7 chương: Chương 1: Bài toán đếm-Bài toán tồn tại Chương 2: Kỹ thuật đếm nâng cao Chương 3: Bài toán liệt kê Chương 4: Đại số Boole Chương 5: Đại số mệnh đề Chương 6: Đồ thị Chương 7: Các bài toán tối ưu trên đồ thị Đây là môn toán ứng dụng nên phần lý thuyết chúng tôi chỉ trình bày ngắn gọn, không đi sâu vào việc chứng minh các định lý, mà chủ yếu là rút ra các thuật toán. Các thuật toán được trình bày bằng ngôn ngữ giả C, nghĩa là ngôn ngữ C cộng với các từ tiếng Việt nhằm thuật toán được dễ hiểu. Giáo trình này có thể làm tài liệu giảng dạy tại tất cả các trường trong Đại học Đà nẵng: Đại học Bách khoa, Đại học Sư phạm, Cao đẳng Công nghệ thông tin và ôn thi cao học ngành công nghệ thông tin. Mặc dù rất cẩn thận trong quá trình biên soạn, tuy nhiên tài liệu không thể tránh khỏi những thiếu sót và hạn chế. Chúng tôi rất mong được sự góp ý quí báu của tất cả bạn đọc và các bạn đồng nghiệp. Mọi ý kiến đóng góp xin gửi về: Khoa Công nghệ thông tin, trường Đại học Bách khoa, Đại học Đà nẵng hoặc emal: pthanhtao@yahoo. Xin chân thành cảm ơn. Đà nẵng, tháng 3 năm 2012 ####### ________________________________________________________________________ Chương 1. Bài toán đếm – Bài toán tồn tạiLý thuyết tổ hợp là một phần quan trọng của toán học rời rạc. Từ một tập nguồn hữu hạn chọn ra một số phần tử có hay không có thứ tự, lặp hay không lặp. Mỗi bộ phần tử như thế gọi là một cấu hình tổ hợp. Đếm các đối tượng có những tính chất nào đó là một bài toán quan trọng của lý thuyết tổ hợp. Giải quyết tốt bài toán đếm giúp ta giải nhiều bài toán trong đánh giá độ phức tạp tính toán của các thuật toán và tìm xác suất rời rạc các biến cố. Phương pháp chung để giải bài toán đếm được dựa trên các nguyên lý đếm cơ bản (nguyên lý cộng, nguyên lý nhân, nguyên lý bù trừ). Nội dung chính được đề cập trong chương này bao gồm: Các nguyên lý cơ bản: - Nguyên lý nhân - Nguyên lý cộng
1.1. Nguyên lý nhân Một hoạt động được thực hiện bởi k bước: bước 1 có n 1 cách, bước 2 có n 2 cách, ..., bước k có nk cách. Tổng số hoạt động là n = n 1 x n 2 x ... x nk = k i ni 1 Dạng tập hợp Cho k tập A 1 , A 2 , ..., Ak. Số phần tử của tập tích Đề-các
Ví dụ. Đếm số xâu chữ độ dài 3 gồm các chữ cái trong tập X={A, B, C, D, E}: a) Bất kỳ b) Không lặp chữ cái ####### k i k i Ai Ai 1 1 ####### | | | | ####### ________________________________________________________________________ Theo ví dụ trên, |A|=|B|=2 6 =64. Có AB=Ø. Theo nguyên lý cộng, số byte có hai bit đầu 00 hoặc 11 là |A|+|B|=64+64=128. Ví dụ. Một đoàn thi OLP của Đại học Đà Nẵng đi dự thi Tin và Toán gồm 2 trường Đại học Bách khoa và Đại học Sư phạm. Mỗi sinh viên chỉ dự thi một môn. Số sinh viên Bách khoa là 9. Số sinh viên thi môn Tin là 10. Số sinh viên Bách khoa thi Tin bằng số sinh viên Sư phạm thi Toán. Toàn đoàn có mấy sinh viên? Giải. Gọi S, B là tập các sinh viên Sư phạm, Bách khoa tương ứng. S 1 , S 2 là là tập các sinh viên Sư phạm thi Tin, Toán tương ứng. B 1 , B 2 là là tập các sinh viên Bách khoa thi Tin, Toán tương ứng. Có |B 1 |+|B 2 | =9, |B 1 |+|S 1 | =10, |B 1 | = |S 2 | Suy ra |S 1 |+|S 2 | = 10. Hay số sinh viên Sư phạm là 10. Vậy, toàn đoàn có 10+9 = 19 sinh viên. Tất cả suy luận trên từ nguyên lý cộng. Ví dụ. Đếm số lệnh gán khi thực hiện đoạn lệnh sau: for (i=1; i<=m; i++) X[i] =i; for (j=1; j<=n; j++) Y[j]=1+2*j; Giải. Theo nguyên lý cộng, số lệnh gán là m+n. 1.1. Nguyên lý bù trừ Đơn giản: Cho hai tập A, B. Có |AB|=|A|+|B|-|AB| Cho ba tập A, B, C. Có |ABC| = |A|+|B|+|C| - (|AB| + |AC| + |BC|) + |ABC| Tổng quát: Cho n tập A 1 , A 2 , ..., An. ####### n k k k n k Ai N 1 1 1 ( 1 )trong đó Nk là tổng phần tử của giao k tập trong n tập A 1 , A 2 , ..., An. Ví dụ. Đếm số nguyên dương không quá 100 chia hết cho 3 hoặc 7. Giải. Gọi S={1.}, A là tập các số trong S chia hết cho 3 và B là tập các số trong S chia hết cho 7. Thì |A|=33 và |B|=14. AB là tập các số nguyên như thế chia hết cho 3 và 7, nghĩa là chia hết cho 21, AB = 4. Do đó, số nguyên dương không quá 100 chia hết cho 3 hoặc 7 là |AB| = |A|+|B| - |AB|= 33+14 - 4 = 43. ####### ________________________________________________________________________ Ví dụ. Một lớp gồm 50 sinh viên, có 30 sinh viên nữ, và có 35 sinh viên tóc vàng. Chứng tỏ rằng có ít nhất 15 sinh viên nữ tóc vàng. Giải. Gọi A là tập các sinh viên nữ, B là tập các sinh viên tóc vàng. Thì |AB| = |A|+|B| - |AB| = 30 + 35 - |AB| ≥ 15 vì |AB| ≤ 50 Ví dụ. Đếm số byte có 2 bit đầu 00 hoặc 2 bit cuối 11. Giải. Gọi A là tập các số byte có 2 bit đầu 00, B là tập các số byte có hai bit cuối 11. Có |A|=|B|=64. Số byte có 2 bit đầu 00 và 2 bit cuối 11 là |AB|=2 4 =16 ( 4 bit giữa bất kỳ). Theo nguyên lý nhân, số byte có 2 bit đầu 00 hoặc 2 bit cuối 11 là |AB|=|A|+|B|-|AB|= 64+64-16=112. 1.1. Nguyên lý Dirichlet(chuồng chim) Đơn giản Cho ánh xạ f: X→Y. Nếu |X|>|Y| thì tồn tại hai phần tử phân biệt x 1 , x 2 X sao cho f(x 1 )f(x 2 ). Tổng quát Cho ánh xạ f: X→Y. Đặt m=|X|, n=|Y| và k= m/n. Tồn tại k phần tử x 1 , x 2 , ..., xkX sao cho f(x 1 ) f(x 2 ) ... f(xk). Ví dụ. Chứng tỏ rằng trong n+1 số nguyên dương có giá trị không quá 2n thì có một số là bội của số khác. Giải. Gọi n+1 số nguyên dương a 1 , a 2 , ..., an, an+1. i=1.+1 đặt ai=2kiqi, với qi lẻ ,1 qi2n. {1.} có n số lẻ. Theo nguyên lý Dirichlet có i≠j sao cho qi =qj. Nếu ki≥kj thì ai là bội aj; ngược lại aj là bội ai. Ví dụ. Chứng tỏ rằng số hữu tỉ là một số thập phân vô hạn tuần hoàn. Giải Gọi x= q p là số hữu tỉ với pZ và qZ+. Gọi r 1 , r 2 , ... là dãy số dư khi chia p cho q để lấy dãy chữ số thập phân d 1 , d 2 , .... Có i: 0 riq-1. Xét q+1 số r 1 , r 2 , .., rq+1. Theo nguyên lý Dirichlet có i<j sao cho ri=rj. Vậy ri+1, ri+2, ..., rj là đoạn tuần hoàn trong dãy số dư r 1 , r 2 , ... Tương ứng có dãy chữ số thập phân d 1 , d 2 , .... cũng tuần hoàn. Hay số hữu tỉ là một số thập phân vô hạn tuần hoàn. Ví dụ. Một bữa tiệc có n người. Chứng tỏ rằng có hai người cùng số người quen. Giải. Gọi q 1 , q 2 , ..., qn là số người quen của người 1, 2, ..., n tương ứng. Có i =1.: 0 qin-1. ####### ________________________________________________________________________ Sau khi có s 1 thì s 2 có n-1 cách chọn. Sau khi có s 1 s 2 thì s 3 có n-2 cách chọn. ... Sau khi có s 1 s 2 ..-1 thì sk có n-k+1 cách chọn. Theo ngyên lý nhân, số chỉnh hợp không lặp n chập k là Ak n =n(n-1)...(n-k+1) Ak n = ( )! ! n k n Lưu ý k≤n, theo nguyên lý chuồng chim. 1.2. Hoán vị Cho tập X gồm n phần tử, |X|=n. Hoán vị của X là một cách sắp xếp n phần tử của X. Mỗi hoán vị của n phần tử là một chỉnh hợp không lặp n chập n. Vậy, số hoán vị của n phần tử là Pn = An n Pn = n!1.2. Tổ hợp Cho tập X gồm n phần tử, |X|=n. Tổ hợp chập k của X là một tập con gồm k phần tử của X. Nói cách khác, là một bộ không lặp và không thứ tự gồm k phần tử của X. Mỗi tổ hợp n chập k phát sinh được pk=k! hoán vị của nó là các chỉnh hợp không lặp n chập k;ngược lại, chỉnh hợp không lặp n chập k bỏ đi thứ tự là tổ hợp n chập k. Vậy, số tổ hợp n chập k là Ck n = Ak n /k! Ck n = ( )!! ! n k k n Có thể dùng ký hiệu C(n,k) hay n k ####### . Ví dụ. Cho ánh xạ f: X Y, |X|=k, |Y|=n. Đếm số ánh xạ f
Giải
! n k n ####### ________________________________________________________________________
1.2. Các công thức tổ hợp a. Cn 0 =Cnn = 1b. C nn k=Cknc. Ckn =Ckn 11 + Ckn 1
Ví dụ. Cho tập X, |X|=n.
Giải. a. Thay x = y = 1 vào nhị thức Newton có số tập con của tập X là 2n. Cách khác, gọi X={x 1 , x 2 , ..., xn}, mỗi tập con A của X đặt tương ứng với xâu bit b= b 1 b 2 .. với ý nghĩa: bi=1 khi và chỉ khi xi A. Có 2n xâu bit nên có 2n tập con A của X. b. Thay x = 1, y =-1 vào nhị thức Newton, có kết quả. Ví dụ. Cho lưới mxn. Đếm số đường đi từ góc dưới bên trái đến góc trên bên phải dọc theo các cạnh. Biết rằng hướng đi chỉ là qua phải hoặc lên trên. Giải. Mỗi đường đi là một bộ gồm m+n cạnh, trong đó có m cạnh lên trên và n cạnh qua phải. Mỗi đường đi ứng với một cách chọn m vị trí cho m cạnh lên trên trong m+n vị trí, tất nhiên n vị trí còn lại là qua phải. Vậy số đường đi bằng số tổ hợp m+n chập m và bằng C(m+n, m)= m!n! ( mn)! Các ứng dụng của nguyên lý bù trừ tổng quát Với nguyên lý bù trừ tổng quát: Cho n tập A 1 , A 2 , ..., An. ####### n k k k n k Ai N 1 1 1 ( 1 )trong đó Nk là tổng phần tử của giao k tập trong n tập A 1 , A 2 , ..., An. Tuy nhiên, có khi cần đếm số phần tử không thuộc tập nào ở trên cả. Gọi U là tập vũ trụ hữu hạn, chứa tất cả các tập trên và chứa tất cả các phần tử không thuộc tập nào cả. nk k n k k n x yn x y C 0 ####### ( ) ####### ________________________________________________________________________ Ví dụ Giả sử n=6s, trong đó s là số nguyên dương. Gọi an là số các bộ có thứ tự (i, j, k) gồm ba số nguyên không âm khác nhau từng đôi (i ≥ 0, j ≥ 0, k ≥ 0, i ≠ j, i ≠ k, j ≠ k) thỏa mãn i jkn .Tìm công thức dưới dạng hiện để tính giá trị của an. Giải Số nghiệm với i, j, k không âm là N=C(n+3,3). Có 3 khả năng hai số trùng nhau là: i=j, j=k, k=i. Xét i=j thì 0≤i≤3s: i = j = 3s => k = 0: có 1 nghiệm i = j = 3s-1 => k = 0.: có 3 nghiệm ......... i = j = 0 => k = 0.: có (n+1)=(6s+1) nghiệm i = j: có 1+3+...+(6s+1)=(3s+1) 2 nghiệm. Vậy tổng số nghiệm cho 3 khả năng là (3s+1) 2 Trong đó số nghiệm i = j = k bị trừ 3 lần. Để chỉ loại 1 lần, phải cộng vào 2 lần. Số nghiệm với i = j = k thì 0 ≤ i ≤ 2s có 2s+1 nghiệm. Vậy,
Nên số nghiệm theo đề bài là N* = C(n+3,3)- 3(3s+1) 2 +2(2s+1)
1.3. Hoán vị lặp Cho n phần tử với k loại: loại 1 có n 1 phần tử, loại 2 có n 2 phần tử, ..., loại k có nk phần tử. Một cách sắp xếp n phần tử này gọi là một hoán vị lặp. Gọi S = s 1 s 2 .. là một hoán vị lặp của n phần tử trên. Có C(n, n 1 ) cách chọn n 1 vị trí để đặt các phần tử loại 1. Sau khi đặt các phần tử loại 1 , có C(n-n 1 , n 2 ) cách chọn n 2 vị trí để đặt các phần tử loại 2. ... Sau khi đặt các phần tử với các loại 1, 2, ..., k-1 có C(n - n 1 - n 2 ... – nk -1, nk) cách chọn nk vị trí để đặt các phần tử loại k. Theo nguyên lý nhân, số hoán vị lặp trên là P(n; n 1 ,n 2 ,...,nk) = C(n, n 1 )C(n-n 1 , n 2 )..(n - n 1 -...- nk-1, nk) P(n; n 1 ,n 2 ,...,nk) = ! !...! ! n 1 n 2 nk n Lưu ý Hoán vị không lặp là trường hợp đặc biệt của hoán vị lặp với mỗi loại một phần tử. Ví dụ. Tính số cách sắp xếp các xâu chữ
11! ####### ________________________________________________________________________
7! 1.3. Tổ hợp lặp Cho n loại phần tử, mỗi loại có không ít hơn k phần tử. Một cách chọn ra k phần tử (có thể lặp) từ n loại phần tử này gọi là một tổ hợp lặp. Nói các khác: Cho |X|=n, tổ hợp lặp chập k của X là một bộ không thứ tự gồm k phần tử của X, trong đó các phần tử có thể lặp. Giả sử mỗi tổ hợp lặp S = s 1 s 2 ... sk được sắp xếp như sau: đầu tiên là tất cả các phần tử loại 1 , đến các phần tử loại 2 , ..., cuối cùng là các phần tử loại n. Dùng k dấu "x" để biểu diễn cho k phần tửvà dùng n-1 dấu"|" để ngăn cho n loại. Vậy mỗi tổ hợp lặp tương ứng với một cách chọn n-1 vị trí trong k+n-1 vị trí để đặt n-1 dấu "|". Có C(k+n-1, n-1) cách chọn. Nên số tổ hợp lặp trên là C(k+n-1, n-1) = C(k+n-1, k) = (k+n-1)/ (n-1)! k! Cn k n 1 1 =Ck k n 1 = ( 1 )!! ( 1 )! n k k n Ví dụ. Đếm số cách mua 10 trái cây với 3 loại: cam, quít, xoài. ĐS: C(10+2, 2)=C(12, 2)= Ví dụ. Đếm số nghiệm nguyên của phương trình x + y + z = 12 với x≥0, y≥0, z≥0. Giải. Dùng 12 dấu “x” để biểu diễn cho 12 đơn vị và dùng 2 dấu “|” để ngăn các đơn vị cho x, y, z. Mỗi nghiệm ứng với một tổ hợp lặp 3 chập 12. ĐS: C(12+2, 2)=C(14, 2)= Ví dụ. Đếm số nghiệm nguyên của phương trình x+y+z = 12 với x≥1, y≥-2, z≥3. Giải Đặt x'=x-1, y'=y+2, z'=z- Tương đương x'+y'+z' = 10 với x'≥0, y'≥0, z'≥0. ĐS: C(10+2, 2) = C(12, 2) = 66 Ví dụ. Đếm số nghiệm nguyên của bất phương trình x + y + z 12 với x≥0, y≥0, z≥0. Giải Đặt t=12-( x + y + z)≥0. Bất phương trình tương đương phương trình x + y + z + t = 12 với x≥0, y≥0, z≥0, t≥0. ĐS: C(12+3, 3)=C(15, 3)= Ví dụ. Đếm số nghiệm nguyên của phương trình x+y+z=11 với 0 x3, 0 y4, 0 z 6 ####### ________________________________________________________________________ Bài tậpCác nguyên lý đếm cơ bản
####### ________________________________________________________________________ Nguyên lý Dirichlet (bài toán tồn tại)
Các cấu hình tổ hợp
####### ________________________________________________________________________ Chương 2. Kỹ thuật đếm nâng caoVới các bài toán đếm, nếu không thể dùng các nguyên lý cơ bản để đếm, khi đó lập hệ thức truy hồi rồi giải.
Hệ thức truy hồi bậc k của dãy số {an} là công thức tính an qua k phần tử trước nó. Dạng: an = f(an-1, an-2,.. ., an-k) Hệ thức truy hồi tuyến tính thuần nhất bậc k hệ số hằng có dạng: an = c 1 an-1 + c 2 an-2 +... + ckan-k (*) trong đó ck 0. Lưu ý rằng với một hệ thức truy hồi bậc k, nếu có k giá trị đầu: a 0 = I 0 , a 1 = I 1 ,... , ak-1 = Ik- thì xác định duy nhất một dãy {an} Ví dụ a) Đếm số lần chuyển đĩa của bài toán tháp Hanoi (tháp Brahma: Bà-la-môn). b) Đếm số xâu nhị phân độ dài n không có hai bit 0 kề nhau. Giải a) Gọi Cn là số lần chuyển đĩa. Có hệ thức truy hồi: Cn = 2Cn-1 +1. Đây là hệ thức truy hồi bậc 1 nên cần 1 giá trị đầu là: C 1 =1. Giải sau. b) Gọi an là số xâu nhị phân độ dài n không có hai bit 0 kề nhau. Gọi b = b 1 b 2 .. là xâu nhị phân độ dài n không có hai bit 0 kề nhau. Xét 2 trường hợp: Nếu bn=1 thì số xâu b bằng số xâu b 1 b 2 .. -1 không có hai bit 0 kề nhau và bằng an-1. Nếu bn=0 thì phải có bn-1=1 và số xâu b bằng số xâu b 1 b 2 .. -2 không có hai bit 0 kề nhau và bằng an-2. Theo nguyên lý cộng, có hệ thức truy hồi: an = an-1 + an-2. Đây là hệ thức truy hồi bậc 2 nên cần 2 giá trị đầu là: a 1 =2 và a 2 =3. Giải sau.
Giải HTTH là tìm một công thức hiện(tường minh) cho số hạng tổng quát an mà không phải tính qua k phần tử trước nó. Không có phương pháp chung để giải hệ thức truy hồi tổng quát. Hai phương pháp sau để giải hệ thức truy hồi dạng đơn giản. Phương pháp thế Phương pháp phương trình đặc trưng 2.2. Phương pháp thế Phương pháp thế để giải hệ thức truy hồi bậc 1 bằng cách thay an bởi an-1, an-1 bởi an-2, ..., cho đến khi gặp giá trị đầu a 0 =I 0 thì có được một công thức rõ ràng cho an. Ví dụ. Gọi Cn là số lần chuyển n đĩa của bài toán tháp Hanoi. Có hệ thức truy hồi Cn =2Cn-1 + 1 và C 1 =1. ####### ________________________________________________________________________ Cn =2Cn-1 + 1 Cn = 2 2 Cn-2+2+ Cn = 2 3 Cn-3+2 2 +2+ ... = 2n-1C 1 +2n-2+...+2 2 +2+ = 1+2+2 2 +...+2n-2+2n-1= 2n-1 (tổng cấp số nhân) Vậy Cn =2n- Tuy nhiên, cần phải kiểm tra lại kết quả bằng cách dùng nguyên lý quy nạp. Với giới hạn của giáo trình, có thể công nhận một cách tự nhiên. 2.2. Phương pháp phương trình đặc trưng Phương pháp phương trình đặc trưng để giải hệ thức truy hồi bậc 2 tuyến tính thuần nhất hệ số hằng an = c 1 an-1 + c 2 an-2 (1) với a 0 =I 0 , a 1 =I 1. trong đó c 2 0. Với phương trình đặc trưng x 2 = c 1 x + c 2 (2) Định lý 1. Nếu 1 và 2 là hai nghiệm phân biệt của (2) thì tồn tại duy nhất các hằng b và d đểan = b 1n + d 2n Ví dụ Giải hệ thức truy hồi an=5an-1-6an-2 với a 0 = 0, a 1 = 1. Giải Phương trình đặc trưng: x 2 = 5x – 6 có 2 nghiệm phân biệt x 1 =3 , x 2 =2. an = b3n + d2n a 0 = 0, a 1 = 1 suy ra b=1 và d=-1. Vậy an = 3n - 2n Ví dụ Giả sử mỗi cặp thỏ sau 2 tháng tuối sinh liên tục mỗi tháng một cặp. Thả lên đảo hoang một cặp thỏ mới sinh và thỏ không chết. Tính số cặp thỏ sau n tháng. Giải Gọi Fn là số cặp thỏ sau n tháng. Fn bằng số cặp thỏ tháng trước (Fn-1) cộng với số cặp thỏ mới sinh. Mà số cặp thỏ mới sinh bằng số cặp thỏ đã có cách đó 2 tháng (Fn-2). Có hệ thức truy hồi: Fn=Fn-1+Fn-2 với F 0 =F 1 =1. Phương trình đặc trưng x 2 =x+1 có hai nghiệm phân biệt 1 = 21 5và 2 = 21 5####### . Fn= b 21 5 n +d ####### ####### ####### ####### ####### 2 ####### 1 5 n ####### ________________________________________________________________________ Vậy an= 33 1 27 33 23 33 n - 33 1 ####### ####### ####### ####### ####### ####### ####### ####### 2 ####### 7 33 ####### ####### ####### ####### ####### ####### ####### ####### ####### 2 ####### 3 33 n Ví dụ. Cho hàm int A(int n) { if (n<2) return n+1; else return 5A(n-1)-6A(n-2); } Đếm số lệnh return khi gọi A(n). Giải. Gọi an là số return khi gọi lệnh A(n). Có hệ thức truy hồi an=an-1+an-2 với a0=a1=1. Trùng với dãy Fibonacci. |
