Nghiên cứu đặc trưng không gian trạng thái và tính ổn định của các hệ Sandpile Model mở rộng

Khóa luận tốt nghiệp nghiên cứu 1572 đặc trưng không gian trạng thái và tính ổn định của một số hệ sandpile model mở rộng luận văn, vận dụng lý thuyết vào thực tế, đề xuất giải

• Tác giả: Trần Thị Thu Hương
• Người hướng dẫn: PGS. Phan Thị Hà Dương
• Trường học: Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
• Chuyên ngành: Cơ sở Toán học cho Tin học
• Đề tài: Đặc trưng không gian trạng thái và tính ổn định của một số hệ Sandpile Model mở rộng
• Loại tài liệu: luận án tiến sĩ toán học
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Tóm tắt

I. Đặc trưng không gian trạng thái

Luận án tập trung nghiên cứu đặc trưng không gian trạng thái của các hệ Sandpile Model (SPM) mở rộng. Không gian trạng thái được định nghĩa là tập hợp tất cả các trạng thái mà hệ có thể đạt được thông qua các luật vận động. Đối với hệ SPM, mỗi trạng thái được biểu diễn bằng một dãy giảm dần, tương ứng với các cột cát. Luật vận động chính là luật rơi, khi một cột có độ cao lớn hơn cột bên phải ít nhất 2 đơn vị, nó sẽ rơi một hạt sang cột bên phải. Cấu trúc không gian trạng thái của hệ SPM được nghiên cứu thông qua các phân hoạch trơn và mối liên hệ với dàn Young. Điều này giúp hiểu rõ hơn về sự biến đổi và ổn định của hệ.

1.1. Cấu trúc dàn của phân hoạch trơn

Các phân hoạch trơn trong hệ SPM tạo thành một cấu trúc dàn, là dàn con của dàn Young. Dàn Young là tập hợp các phân hoạch số tự nhiên với quan hệ thứ tự bao hàm. Việc chứng minh cấu trúc dàn này giúp xác định mối quan hệ thứ tự giữa các trạng thái và cách chúng chuyển đổi lẫn nhau. Điều này cũng mở ra hướng nghiên cứu về các tính chất tổ hợp liên quan đến phân hoạch.

1.2. Năng lượng và thời gian hội tụ

Khái niệm năng lượng được đưa ra để đo lường sự biến thiên của hệ. Năng lượng của một trạng thái được tính toán dựa trên độ dài đường đi ngắn nhất và dài nhất để đạt đến trạng thái đó. Điều này giúp đánh giá thời gian hội tụ của hệ, từ đó hiểu rõ hơn về sự ổn định và biến động của hệ dưới tác động từ bên ngoài.

II. Tính ổn định của hệ Sandpile Model

Luận án nghiên cứu tính ổn định của hệ SPM dưới tác động từ bên ngoài. Khi hệ đạt đến trạng thái ổn định, một hạt được thêm vào một cột ngẫu nhiên, làm hệ tiếp tục vận động. Quá trình này lặp lại, tạo ra một chuỗi các trạng thái ổn định. Tính ổn định được đánh giá thông qua khả năng hệ tự điều chỉnh và hội tụ về trạng thái ổn định mới. Nghiên cứu này giúp hiểu rõ hơn về sự tự tổ chức và ổn định của các hệ động lực trong tự nhiên.

2.1. Luật thêm hạt và sự ổn định

Việc thêm hạt từ bên ngoài vào hệ SPM là một yếu tố quan trọng trong nghiên cứu tính ổn định. Mỗi khi hệ đạt đến trạng thái ổn định, một hạt được thêm vào một cột ngẫu nhiên, làm hệ tiếp tục vận động. Quá trình này tạo ra một chuỗi các trạng thái ổn định, giúp nghiên cứu sự biến đổi và ổn định của hệ.

2.2. Thời gian hội tụ

Thời gian hội tụ của hệ SPM được đánh giá thông qua thời gian ngắn nhất và dài nhất để hệ đạt đến trạng thái ổn định. Điều này giúp hiểu rõ hơn về sự biến thiên của hệ dưới tác động từ bên ngoài và khả năng tự điều chỉnh của hệ.

III. Mở rộng hệ Sandpile Model

Luận án đề xuất các mở rộng của hệ SPM, bao gồm hệ SPM đối xứng song song (PS-SPM) và hệ CFG có dấu. Hệ PS-SPM cho phép các cột rơi sang cả hai phía (đối xứng) và các cột có thể rơi đồng thời (song song). Hệ CFG có dấu cho phép các đỉnh chứa số chip âm và các đỉnh đủ âm chip cũng có thể bắn. Các mở rộng này giúp mô tả tốt hơn các hệ động lực trong thực tế và mở ra hướng nghiên cứu mới về tính chất tổ hợp và cấu trúc không gian trạng thái.

3.1. Hệ SPM đối xứng song song

Hệ PS-SPM là một mở rộng của hệ SPM, cho phép các cột rơi sang cả hai phía và các cột có thể rơi đồng thời. Nghiên cứu này chỉ ra rằng dạng ổn định của hệ PS-SPM trùng với hệ SPM đối xứng, mặc dù số lượng trạng thái ổn định ít hơn. Điều này giúp hiểu rõ hơn về sự ổn định và biến đổi của hệ trong các điều kiện khác nhau.

3.2. Hệ CFG có dấu

Hệ CFG có dấu là một mở rộng của hệ CFG, cho phép các đỉnh chứa số chip âm và các đỉnh đủ âm chip cũng có thể bắn. Nghiên cứu này chỉ ra sự đẳng cấu giữa hệ SPM đối xứng và hệ CFG có dấu, giúp mô tả tốt hơn các hệ động lực trong thực tế và mở ra hướng nghiên cứu mới về tính chất tổ hợp.

IV. Ứng dụng và ý nghĩa thực tiễn

Luận án không chỉ mang lại những hiểu biết sâu sắc về đặc trưng không gian trạng thái và tính ổn định của các hệ SPM mở rộng mà còn có nhiều ứng dụng thực tiễn. Các kết quả nghiên cứu có thể được áp dụng trong các lĩnh vực như vật lý, sinh học, và khoa học máy tính, đặc biệt là trong việc mô hình hóa các hệ thống tự tổ chức và tự điều chỉnh. Ngoài ra, các mở rộng của hệ SPM và CFG mở ra hướng nghiên cứu mới về tính chất tổ hợp và cấu trúc không gian trạng thái.

4.1. Ứng dụng trong vật lý và sinh học

Các hệ SPM và CFG được sử dụng để mô hình hóa các hiện tượng tự tổ chức trong tự nhiên, như sự hình thành các cấu trúc địa chất hoặc sự phân bố tài nguyên trong hệ sinh thái. Nghiên cứu về tính ổn định và cấu trúc không gian trạng thái giúp hiểu rõ hơn về các quá trình này.

4.2. Ứng dụng trong khoa học máy tính

Các kết quả nghiên cứu về SPM và CFG có thể được áp dụng trong lĩnh vực khoa học máy tính, đặc biệt là trong việc thiết kế các thuật toán phân phối tài nguyên và tối ưu hóa hệ thống. Các mở rộng của hệ SPM và CFG mở ra hướng nghiên cứu mới về tính chất tổ hợp và cấu trúc không gian trạng thái.

Trích đoạn nội dung tài liệu

Chương 1 Hệ động lực rời rạc Chương này nhắc lại các kiến thức chuẩn bị, một số hướng nghiên cứu và các kết quả đã biết về hai hệ được nghiên cứu chính trong luận án: Hệ SPM (Sandpile model) và hệ CFG (Chip firing game).1 Các kiến thức chuẩn bị Luận án tập trung nghiên cứu hai hệ động lực rời rạc được quan tâm rất nhiều: hệ SPM (Sand pile model) và hệ CFG (Chip firing game). Hai hệ này được định nghĩa trên một đồ thị nền. Các kết quả trên hai hệ có liên quan nhiều đến một số tính toán tổ hợp trên các phân hoạch của số tự nhiên, cấu trúc thứ tự, cấu trúc dàn trên không gian các trạng thái của các hệ. Bởi vậy, trong phần này chúng tôi sẽ trình bày các kiến thức cơ sở về đồ thị, tập thứ tự, dàn, ngôn ngữ,.

được tham khảo chủ yếu trong [2, 13, 18, 37, 44, 45].1 Đồ thị Trước hết, chúng tôi trình bày các khái niệm cho đồ thị vô hướng sau đó sẽ đề cập tương tự cho đồ thị có hướng. Một đa đồ thị vô hướng là một cặp có thứ thự G = (V, E), trong đó V là một tập hợp khác rỗng, được gọi là tập đỉnh 13 của G, và E là một đa tập trong tập các cặp không phân biệt thứ tự {u, v}, với u, v ∈ V , được gọi là tập cạnh của G. Cho G là một đa đồ thị vô hướng. Nếu e = {u, v} ∈ E thì các đỉnh u, v được gọi là các đầu mút của e và u liên thuộc với e, hơn nữa, hai đỉnh u, v được gọi là liền kề, hay hàng xóm của nhau.

Nếu e = {u, u} thì e được gọi là một khuyên. Bậc của một đỉnh u ∈ V , ký hiệu là deg(u), là số các cạnh của G liên thuộc với u, trong đó các khuyên tại u được tính hai lần. Ta cũng thường ký hiệu cạnh {u, v} ngắn gọn là uv. Trong trường hợp tập cạnh E là một đa tập trong tập các cặp có phân biệt thứ tự V × V , thì G = (V, E) được gọi là một đa đồ thị có hướng và các phần tử thuộc E đôi khi còn gọi là các cung.

Với e = (u, v) ∈ E thì u được gọi là đỉnh đầu và v được gọi là đỉnh cuối của e và ta nói cạnh e đi từ u đến v. Bậc đi ra và bậc đi vào của đỉnh u ∈ V là số các cạnh đi ra từ u và đi vào u tương ứng, được ký hiệu lần lượt là deg+ (u) và deg− (u). Nếu giữa hai đỉnh u, v ∈ V của đồ thị G = (V, E) (có hướng hoặc vô hướng) có nhiều nhất một cạnh thì đồ thị G được gọi là đơn đồ thị (có hướng hoặc vô hướng tương ứng). Một đồ thị con của G là một đồ thị thu được từ G bằng cách xóa bớt đi một số đỉnh (và các cạnh liên thuộc với các đỉnh đó) và một số cạnh của G.

Một đồ thị con bao trùm của G nếu nó có tập đỉnh trùng với tập đỉnh của G. Đồ thị con cảm sinh bởi tập đỉnh V 0 ⊆ V của G, ký hiệu là G[V 0 ], là một đồ thị con của G với tập đỉnh là V 0 và tập các cạnh là tất cả các cạnh của G mà có hai đầu mút thuộc V 0. Một đường đi có hướng độ dài k từ đỉnh u đến đỉnh v trong G là dãy v0 ,. , vk sao cho v0 = u, vk = v, vi ∈ V và (vi , vi+1 ) ∈ E với mọi i = 0,.

Khi đó, đỉnh u được gọi là đỉnh đầu và đỉnh v được gọi là đỉnh cuối của đường đi. Đường đi đơn là một đường đi mà không có hai cạnh nào được lặp lại. Một chu trình của G là một đường đi sao cho đỉnh đầu và đỉnh cuối của nó là trùng nhau. Các khái niệm đường đi và chu trình trong trường hợp vô hướng được định nghĩa một cách tương tự.

Đồ thị có hướng được gọi là liên thông mạnh nếu giữa hai đỉnh tùy ý của nó có một đường đi có hướng. Tập S ⊆ V được gọi là một thành phần liên thông của đồ thị vô hướng G = (V, E) nếu G[S] là liên thông và với mọi S 0 ) S thì G[S 0 ] không liên thông. Tập S ⊆ V được gọi là một thành phần liên thông mạnh của đồ thị có hướng G = (V, E) nếu G[S] là liên thông mạnh và với mọi S 0 ) S thì G[S 0 ] không liên thông mạnh. Tập S ⊆ V được gọi là một thành phần đóng (closed component) của đồ thị có hướng G nếu S là một thành phần liên thông mạnh và không tồn tại cạnh nào của G đi ra từ một đỉnh trong S.

Tiếp theo, chúng tôi nhắc lại khái niệm của một dạng đồ thị đặc biệt được nghiên cứu và ứng dụng rất nhiều trong tin học bởi cấu trúc đơn giản của nó, được gọi là cây. Một đồ thị vô hướng, liên thông, không có chu trình được gọi là một cây. Dễ thấy rằng trong một cây thì số đỉnh nhiều hơn số cạnh đúng là 1. Hơn nữa, ta có các điều kiện tương đương thường được sử dụng để chứng minh tính chất cây như sau: Định lý 1.

Cho G = (V, E) là một đồ thị vô hướng và |V | = n. Các mệnh đề sau là tương đương: i) G là một cây. ii) G là liên thông và |E| = |V | − 1. iii) G không có chu trình và |E| = |V | − 1.

iv) Giữa hai đỉnh của G tồn tại duy nhất một đường đi đơn. v) G không có chu trình và nếu thêm bất kỳ cạnh nào vào G thì đồ thị nhận được sẽ có một chu trình đơn. 15 vi) G liên thông và nếu xóa bỏ bất kỳ cạnh nào của G thì đồ thị nhận được không còn liên thông nữa. Cho G là một đồ thị vô hướng.

Một cây bao trùm của G là một đồ thị con bao trùm của G sao cho nó là một cây. Có rất nhiều bài toán liên quan đến cây bao trùm của một đồ thị. Trong đó, bài toán nổi tiếng nhất là tính số cây bao trùm của một đồ thị cho trước. Số này thực chất được cho bởi định thức của ma trận biểu diễn đồ thị, được gọi là ma trận Laplace.

Bên cạnh đó, ma trận Laplace cùng với ma trận liền kề (ma trận biểu diễn sự liền kề nhau của các đỉnh trong đồ thị) cũng được dùng như là một công cụ để nghiên cứu nhiều bất biến cũng như các tính chất của đồ thị.2, chúng tôi cũng sẽ sử dụng các ma trận này để mô tả luật vận động của hệ CFG và dùng để nghiên cứu các tính chất nhóm cho hệ CFG này. Ma trận liền kề của G là ma trận A = (aij )n×n , trong đó aij là số các cạnh đi từ vi tới vj. Ma trận Laplace của G được cho bởi: ∆ = D − A, trong đó D là ma trận đường chéo với các phần tử trên đường chéo dii là số bậc (bậc đi ra) của đỉnh vi và A là ma trận liền kề của G. Từ định nghĩa, ta thấy tổng các phần tử trong một hàng của ma trận Laplace luôn bằng 0.

Do vậy, ∆ luôn có một vector riêng là 0 ứng với giá trị riêng là (1, 1,. Hơn nữa, trong trường hợp G là vô hướng thì các ma trận liền kề và ma trận Laplace của G là các ma trận đối xứng. Ta ký hiệu ma trận ∆∗ là ma trận rút gọn của ∆ bằng cách xóa đi hàng và cột thứ n. Định lý sau còn được gọi là định lý Kirchhoff.

Cho G là một đa đồ thị vô hướng có ma trận Laplace ∆. Khi đó, số cây bao trùm của G đúng bằng định thức của ma trận Laplace rút gọn ∆∗. 16 Một cách tương tự, chúng ta cũng có một phiên bản khác của Định lý 1.2 cho trường hợp G là đa đồ thị có hướng và có một đỉnh đặc biệt s (thường gọi là đỉnh chìm) mà không có cạnh đi ra từ nó. Trong đó, cây bao trùm sẽ có gốc tại s.

Cây bao trùm có gốc s là cây bao trùm của G (khi bỏ qua hướng) sao mọi đỉnh khác s đều có đường có hướng đi duy nhất tới s. Ký hiệu ∆(s) là ma trận Laplace rút gọn theo s của G bằng cách xóa hàng và cột tương ứng với s. Định lý được phát biểu lại như sau: Định lý 1. Cho G là một đa đồ thị có hướng và có duy nhất một đỉnh chìm s.

Khi đó, số cây bao trùm có gốc tại s của G đúng bằng định thức của ma trận Laplace rút gọn ∆(s). Với đồ thị đầy đủ bốn đỉnh K4 như Hình 1.    −1 −1 3 −1   −1 −1 3 −1 −1 −1 3 Ta có |∆∗ | = 9 và do đó K4 có 9 cây bao trùm.1: Đồ thị đầy đủ K4 17 Hình 1.2: Biểu đồ Ferrer của phân hoạch (4, 3, 2, 2, 2, 1) 1.2 Phân hoạch của số tự nhiên, tập thứ tự bộ phận và dàn Trong phần này chúng tôi sẽ trình bày các kiến thức cơ sở về phân hoạch, tập thứ tự và cấu trúc dàn của một tập thứ tự [2, 13, 44]. (i) Một phân hoạch (partition) là một dãy các số nguyên không âm a = (a1 , a2 ,.

, ak ) sao cho a1 ≥ a2 ≥. Khi đó, ai là các phần của a; và k là độ dài của a, ký hiệu l(a) = k. Chúng ta nói rằng a là một phân hoạch của một số tự nhiên n, hay n là trọng số của a, và viết w(a) = n, nếu ki=1 ai = n. P (ii) Một phân hoạch a được gọi là trơn nếu ai − ai+1 ≤ 1 với mọi i = 1, 2,.

(iii) Một phân hoạch a được gọi là chặt nếu ai − ai+1 ≥ 1 với mọi i = 1, 2,. Các biểu diễn hình học cho các phân hoạch thì không chỉ hữu ích về mặt trực quan mà còn được sử dụng để giải thích một cách dễ dàng cho nhiều tính chất của phân hoạch. Một trong những cách biểu diễn phổ biến được trình bảy ở đây là biểu đồ Ferrer. , ak ) là một phân hoạch.

Biểu đồ Ferrer biểu diễn a thành các cột liên tiếp nhau, trong đó cột thứ i gồm ai ô vuông xếp chồng lên nhau.2 minh họa biểu đồ Ferrer của phân hoạch (4, 3, 2, 2, 2, 1).