chuỗi

C H U ỖI.

G iớ i t h i ệ u v à ví d ụ

Chuỗi là một danh sách các phần tử có tính tới trật tự. Chuỗi được dùng trong toán học theo nhiều cách. Chúng có thể dùng để biểu diễn nghiêm trong các bài toán đếm, nó cũng là một cấu trúc dữ liệu quan trọng trong khoa học máy tính.

Định nghĩa

• Một cách hình thức: Một {an} được chỉ định bẳng một hàm tạo f:S→A

với S⊆N (thường S=N hay S=N－{0}) và một tập A.

• Nếu f là một hàm taọu cho {an}, khi đó n∈S, thì ký tự cũng được coi

là một phần tử thứ n của S

Ví dụ:

• Nhiều khi ta viết “a1, a2, …” thay cho {an}, để cho tập chỉ ra được rõ ràng

• Một ví dụ về vô hạn:

– Xét {an} = a1, a2, …, trong đó (∀n≥1) an= f(n) = 1/n.

– Do vậy {an} = 1, 1/2, 1/3, …

• Xét thêm {bn} = b0, b1, … trong đó bn = (－1)n.

• {bn} = 1, －1, 1, －1, …

• Như vậy là lặp lại! {bn} là một vô hạn 1 và －1

N h ận d ạ n g c h u ỗ i

Một bài toán hay gặp trong toán học rời rạc là tìm ra công thức hay luật tổng quát cho một được đưa ra. Trong một số trường hợp, chỉ một số ít các phần tử đầu được biết, mục tiêu là phải xác định được . Ngay cả khi một số phần tử đầu không xác định được toàn bộ (điều này là do có rất nhiều các bắt đầu với bất kỳ một hữu hạn phần tử), nó cũng sẽ giúp phỏng đoán được. Khi có được phỏng đoán, chúng ta cần phải tìm cách chứng minh tính đúng đắn của nó.

Trong quá trình tìm ra luật của từ những các phần tử ban đầu, hãy cố gắng tìm ra các đặc điểm chung của chúng. Sau đây là một số câu hỏi giúp cho quá trình tìm kiếm dễ dàng hơn:

 Chuỗi có bị lặp lại không? Tức là các giá trị giống nhau có xảy ra nhiều lần

trên một hàng không?

 Các phần tử có đạt được từ các phần tử trước bằng cách thêm vào cùng một

giá trị hay giá trị đó có phụ thuộc thêm vào vị trí của hay không?

 Các phần tử có đạt được từ các phần tử trước bằng cách nhân vào cùng một

giá trị cụ thể hay giá trị đó phụ thuộc thêm vào vị trí của hay không?

 Các phần tử có đạt được từ các phần tử trước bằng cách kết hợp một số các

phần tử trước hay không?

 Có chu kỳ nào giữa các phần tử không?

• Ví dụ: Tìm sồ tiếp theo?

– 1,2,3,4,…

– 1,3,5,7,9,…

– 2,3,5,7,11,...

– 1, 2, 2, 3, 3, 3, 4,4, 4, 4, ...

– 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, ...

– 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047

• Khi bài toán yêu cầu tìm ra hàm tổng quát mà chỉ bằng một số các phần tử của thì đây là yêu cầu không thực sự rõ ràng. Bởi vì có thể có vô số các hàm giống nhau một số các phần tử đầu

• Chúng ta phải ngầm định là tìm hàm đơn giản nhất, tuy nhiên chúng ta nên hiểu hàm thế nào là đơn giản? Chúng ta có thể định nghĩa đơn giản là không phức tạp, tuy nhiên nó đòi hỏi nhiều những kiến thức mà chúng ta không thể thảo luận ở đây. Do vậy câu hỏi thực sự vẫn chưa có câu trả lời xác đáng.

C h u ỗi ( S tri n g)

• Trong modul này thì “ hữu hạn có dạng a1, a2, …, an”, tuy nhiên đôi

khi chúng ta cũng nói tới vô hạn.

• Chuỗi cũng thường được xét giới hạn trong các bảng chữ cái alphabet, đôi

khi chỉ là 0 và 1.

• Độ dài của là số phần tử của đấy.

• Coi Σ là tập hữu hạn các ký tự, ví dụ như bảng alphabet.

• Một s trên alphabet Σ là bất kỳ {si} ký tự nào, si∈Σ.

• Nếu a, b, c, … là các ký tự, s = a, b, c, … có thể được viết abc

…(không có dấu phẩy).

• Nếu s là một hữu hạn và t là một , khi ta nối s với t, viết là st, là một mới bao gồm các ký tự của s, theo sau là ccs ký tự của t

• Độ dài |s| của một hữu hạn s là số ký tự của nó.

• Nếu s là một và n∈N, sn ký hiệu n s nối liên tiếp nhâu.

• ε ký hiệu là một rỗng, độ dài bằng 0.

• Nếu Σ là bảng alphabet và n∈N,

Σn  {s | s là một trên Σ có độ dài n}, và

Σ*  {s | s là một hữu hạn trên Σ}.

Một số dãy hay gặp
Phần tử thứ n	10 phần tử đầu
n2	1, 4, 9, 16, 25, 36, 49, 64, 81, 100,...
n3	1, 8, 27, 64, 125, 216, 343, 512, 729, 1000,...
n4	1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000,...
2n	2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,...
3n	3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,...
n!	1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,..