Bài giảng Toán rời rạc: Phần V & VI - GVC ThS.Võ Minh Đức

Bài giảng Toán rời rạc trình bày về hệ thức truy hồi và quan hệ chia để trị trong Toán rời rạc. Tài liệu giúp các bạn củng cố thêm kiến thức về Toán rời rạc là nền tảng cho việc học nhiều môn khoa học tự nhiên sau này.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Phần V & VI - GVC ThS.Võ Minh Đức TOÁN RỜI RẠC CH1: Hãy cho một ví dụ về định nghĩa đệ  quy? 1. Định nghĩa giai thừa của n: n! = n * (n­1)! 2. Lũy thừa nguyên của một số: an = a * an­1 CH2: Có thể ĐN hai khái niệm trên không  dùng đệ quy được không? 25/08/2014 GVC, ThS.Võ Minh Đức 1 TOÁN RỜI RẠC CH1: Đọc giá trị của dãy số gồm các giai  thừa của một số, bắt đầu từ 0: 0, 1, 2, 6, 12, 20,..,n!  a1, a2, a3, a4…an 25/08/2014 GVC, ThS.Võ Minh Đức 2 TOÁN RỜI RẠC 1. Định nghĩa 1:  V. Hệ  thức  truy  hồi  đối  với  dãy  số  Hệ {an}  là  công  thức  biểu  diễn  an  qua  thức một hay nhiều số hạng đi trước của  dãy. Dãy số được gọi là lời giải hay  truy nghiệm  của  hệ  thức  truy  hồi  nếu  hồi các  số  hạng  của  nó  thỏa  mãn  hệ  thức truy hồi này. 25/08/2014 GVC, ThS.Võ Minh Đức 3 TOÁN RỜI RẠC CÁC VÍ DỤ Ví  dụ  1(Lãi  kép):  Giả  sử  một  người  gửi 10.000 đô la vào tài khoản của mình  V. tại  một  ngân  hàng  với  lãi  suất  kép  11%  Hệ mỗi  năm.  Sau  30  năm  anh  ta  có  bao  thức nhiêu tiền trong tài khoản của mình? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 4 TOÁN RỜI RẠC GIẢI Gọi  Pn  là  tổng  số  tiền  có  trong  tài  khoản  sau  n  năm.  Vì  số  tiền  có  trong  tài khoản sau n năm bằng số có sau n  V. ­  1 năm cộng lãi suất của năm thứ n,  Hệ nên ta thấy dãy {Pn} thoả mãn hệ thức  thức truy hồi sau:    truy Pn = Pn­1 + 0,11Pn­1 = (1,11)Pn­1 với  điều  kiện  đầu  P0  =  10.000  đô  la.  hồi Từ đó suy ra Pn = (1,11)n.10.000.  Thay  n  =  30  cho  ta  P30  =  228922,97  đô la. 25/08/2014 GVC, ThS.Võ Minh Đức 5 TOÁN RỜI RẠC VÍ DỤ 2 Tìm  hệ  thức  truy  hồi  và  cho  điều  kiện  đầu để tính số các xâu nhị phân độ dài  V. n và không có hai số 0 liên tiếp.  Hệ Có bao nhiêu xâu nhị phân như thế có  thức độ dài bằng 5? truy hồi 25/08/2014 GVC, ThS.Võ Minh Đức 6 TOÁN RỜI RẠC GIẢI Gọi  an  là  số  các  xâu  nhị  phân  (np)  độ dài n và không có hai số 0 liên tiếp.  V. Ta có: Hệ Số các xâu np độ dài n và không có hai  số 0 liên tiếp (an) = số các xâu np như  thức thế  kết  thúc  bằng  số  1  (bn)  +  số  các  truy xâu np như thế kết thúc bằng số 0 (cn). hồi Vậy an = bn + cn  (1) 25/08/2014 GVC, ThS.Võ Minh Đức 7 TOÁN RỜI RẠC GIẢI Giả sử n ‡  3. *  bn  chính  là  số  xâu  np  như  thế,  độ  dài  n  ­   1  và  thêm  số  1  vào  cuối  của  V. chúng. Hỏi có tất cả là bao nhiêu xâu? Hệ có tất cả là an­1xâu. thức Vậy bn = ? * cn  là số các xâu np có bit thứ n ­  1  truy bằng 1, nếu không thì chúng có hai số 0  hồi ở  hai  bit  cuối  cùng.  Hỏi  có  tất  cả  là  bao  nhiêu xâu như thế ? có tất cả là an­2 xâu. Vậy cn = ? 25/08/2014 GVC, ThS.Võ Minh Đức 8 TOÁN RỜI RẠC GIẢI Vậy: an = an­1 + an­2   với n ‡  3. V. Hệ •  n = 1 ta có 2 xâu: 0, 1.  Vậy: a1 = 2  thức •  n = 2, ta có 3 xâu: ???.  truy Vậy a2 = 3 hồi Khi đó a5 = a4 + a3 = a3 + a2 + a3         = 2(a2 + a1) + a2 = 13. 25/08/2014 GVC, ThS.Võ Minh Đức 9 TOÁN RỜI RẠC 2. Giải các hệ thức truy hồi. Định nghĩa 2: Một hệ thức truy hồi V. tuyến tính thuần nhất bậc k là hệ Hệ thức truy hồi có dạng: thức an = c1an-1 + c2an-2 + ... + ckan-k truy trong đó c1, c2, ..., ck là các số thực và ck  0. hồi 25/08/2014 GVC, ThS.Võ Minh Đức 10 Hệ thức truy hồi 2. Là tuyến tính vì vế phải của nó là Giải tổng các tích của các số hạng trước các nhân với một hệ số hệ Là thuần nhất vì các số hạng đều là thức ai và hệ số đều là hằng số. truy Có bậc k vì an được biểu diễn qua k hồi. số hạng đứng trước nó. 25/08/2014 GVC, ThS.Võ Minh Đức 11 ...