Bài giảng Sequences

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #12:Dãy - Sequences Rosen 5th ed., §3.2 ~9 slides, ~½ lecture §3.2: Dãy, xâu & tổng Sequences, Strings, & Summations Dãy giống như bộ n có thứ tự, khác là: Mỗi phần tử trong dãy có liên kết một chỉ số. Dãy có thể là vô hạn. Xâu là dãy các ký hiệu từ một bảng chữ hữu hạn. Phép tổng là ký hiệu viết tắt của tổng các đối tượng trong một dãy (có thể vô hạn). Các dãy - Sequences Dãy {an} được đồng nhất với hàm sinh f:SA đối với tập con nào đó SN và đối với tập A nào đó. Thông thường ta có S=N hoặc S=Z+=N{0}. Dãy có thể được tổng quát là tập được đánh chỉ số, trong đó tập S không cần là tập con của N. Đối với tập được đánh chỉ số, S có thể không là tập số. Nếu f là hàm sinh cho dãy {an}, thì với nS, ký hiệu an chính là f(n), còn được gọi là phần tử thứ n của dãy. Chỉ số của an là n. (hoăc, hay dùng i) Dãy thường được ký hiệu bằng cách liệt kê một vài phần tử đầu và/hoặc cuối, và sử dụng dấu ba chấm … VD., “{an} = 0, 1, 4, 9, 16, 25, …” được dùng để ký hiệu  nN, an = n2. Sequence Examples Some authors write “the sequence a1, a2, …” instead of {an}, to ensure that the set of indices is clear. Be careful: Our book often leaves the indices ambiguous. An example of an infinite series: Consider the series {an} = a1, a2, …, where (n1) an= f(n) = 1/n. Then, we have {an} = 1, 1/2, 1/3, … Ví dụ về lặp Example with Repetitions Giống bộ, nhưng không giống tập hợp, dãy có thể chứa các đối tượng lặp của cùng một phần tử. Xst dãy {bn} = b0, b1, … (lưu ý 0 là chỉ số) trong đó bn = (1)n. Vậy, {bn} = 1, 1, 1, 1, … Lưu ý có lặp của 1 và -1! Dãy {bn} là dãy vô hạn các số 1 và 1, chứ không phải tập 2 phần tử {1, 1}. Nhận biết dãy Recognizing Sequences Đôi khi, bạn được cho một số phần tử đầu của dãy, Và bạn được yêu cầu tìm hàm sinh ra dãy, Hoặc thủ tục để tính dãy. Examples: What’s the next number? 1,2,3,4,… 1,3,5,7,9,… 2,3,5,7,11,... 5 (the 5th smallest number >0) 11 (the 6th smallest odd number >0) 13 (the 6th smallest prime number) Rắc rối nhận biết dãy Như bạn đã biết, các bài toán này được dùng nhiều để kiểm tra IQ, nhưng … Bài toán tìm hàm sinh mà chỉ cho trước một số phần tử ban đầu không là bài toán đặt chuẩn. Vì có thể có vô hạn các hàm tính toán được mà có cùng một sô phần tử ban đầu. Ta giả thiết ẩn rằng tìm hàm đơn giản nhất như vậy, nhưng Ta định nghĩa khách quan thế nào là đơn giản của hàm số? Ta có thể định nghĩa đơn giản là ngược lại của phức tạp, nhưng Nhưng có rất nhiều định nghĩa phức tạp phù hợp khác nhau, và đây đang là lĩnh vực nghiên cứu sôi động. Vậy, các câu hỏi này chưa trả lời khách quan được! Tuy nhiên, tôi vẫn yêu cầu các bạn trả lời (Vì những người khác cũng vậy) Xâu trên thực tế là gì? Sách nói “dãy hữu hạn” dạnga1, a2, …, an được gọi là xâu (strings), Nhưng xâu vô hạn đôi khi cũng được xét đến. Xâu thường hạn chế là dãy gồm các ký hiệu lấy trong bảng chữ hữu hạn, và đánh chỉ số từ 0 hoặc 1. Nhưng cũng có những hạn chế khác bổ sung. Mặt khác, độ dài của xâu hữu hạn là số các chữ của nó (hoặc số các chỉ số khác nhau). Xâu, hình thức hơn  Strings, more formally G/s  là tập hữu hạn các ký hiệu, tức là bảng chữ. Xâu s trên bảng chữ  là dãy bất kỳ các ký hiệu {si}, si, thường được đánh chỉ số bởi N hoặc N{0}. Nếu a, b, c, … là ký hiệu, thì xâu s = a, b, c, … có thể được viết dạng abc…(tức là không cần dấu phảy). Xâu s là xâu hữu hạn và t là xâu bất kỳ, thì ghép nối s với t, viết là st, Đây đơn giản là xâu gồm các ký hiệu theo thứ tự của s, được nối tiếp bởi các ký hiệu theo thứ tự của t. Tiếp về các khái niệm trên xâu Độ dài |s| của xâu hữu hạn s là số các vị trí của nó (tức là số các giá trị chỉ số i). Nếu s là xâu hữu hạn và nN, Thì sn ký hiệu ghép nối n bản sao của s.  hoặc “” ký hiệu là xâu rỗng, xâu có độ dài 0. Đây là ký hiệu chuẩn dùng chung, nhưng sách có thể dùng λ. Nếu  là bảng chữ và nN, n : {s | s là xâu trên  có độ dài n}, và * : {s | s là xâu hữu hạn trên }.