Luận Văn Cấu trúc không gian trạng thái và tính đạt được của một số hệ động lực rời rạc

VIỆN TOÁN HỌC
Cấu trúc không gian trạng thái và tính đạt được của một số hệ động lực rời rạc
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NĂM - 2010

Mục lục
Mở đầu 1
Chương 1. Kiến thức chuẩn bị 5
1.1 Tập thứ tự - Dàn 5
1.1.1 Tập thứ tự 5
1.1.2 Dàn . 8
1.2 Một số kiến thức cơ bản về lý thuyết đồ thị . 12
1.3 Hàm sinh 16
1.4 Hệ động lực rời rạc . 18


Chương 2. Mô hình cột cát và phân hoạch của số tự nhiên 20
2.1 Phân hoạch số tự nhiên và hệ động lực rời rạc 21
2.1.1 Các định nghĩa và ký hiệu . 21
2.1.2 Cấu trúc của d-P(n) 23
2.1.3 Mối quan hệ giữa d-P(n + 1) và d-P(n) . 26
2.1.4 Dàn vô hạn d-P(1) 28
2.1.5 Cây vô hạn Td-P(1) 30
2.2 Phương pháp ECO và phân hoạch số tự nhiên 30
2.2.1 Phương pháp ECO . 31
2.2.2 Phân hoạch d-chặt và phương pháp ECO . 33
2.2.3 Cấu trúc đệ quy của cây vô hạn Td-P(1) . 34
2.3 Một số tính toán trên cây vô hạn . 38
2.4 Kết luận chương 2 . 42


Chương 3. Các hệ động lực CFG và mạng Petri 44
3.1 CFG cổ điển 44
3.1.1 Các định nghĩa . 44
3.1.2 Cấu trúc dàn của không gian trạng thái 46
3.1.3 Mô phỏng hệ SPM bằng CFG . 48
3.1.4 CFG tô màu 48
3.2 Hệ động lực CCFG . 52
3.3 Mạng Petri . 55
3.4 Mối quan hệ giữa hệ động lực CFGs và mạng Petri . 59
3.4.1 CFG và mạng Petri . 59
3.4.2 CCFG và mạng Petri 61
3.4.3 CFG tô màu và mạng Petri 62
3.5 Kết luận chương 3 . 67


Chương 4. Tính đạt được của hệ CCFG trên đồ thị có hướng 68
4.1 Tính đạt được của một số mạng Petri . 69
4.2 Cấu trúc thứ tự của CCFG trên DAG . 71
4.3 Thuật toán xác định thứ tự của hệ CCFG trên DAG . 75
4.3.1 Thuật toán sinh ra các lọc . 77
4.3.2 Thuật toán so sánh hai trạng thái . 82
4.4 Mạng vận tải 83
4.5 Tính đạt được của hệ CCFG trên đồ thị có hướng 86
4.6 Thuật toán 91
4.7 Kết luận chương 4 . 93
Kết luận của luận án 94
Các công trình liên quan đến luận án 96
Tài liệu tham khảo 98


Danh sách các hình vẽ
1.1 Một số ví dụ về tập thứ tự 6
1.2 Một số ví dụ về các dàn . 9
1.3 Ví dụ về đa đồ thị vô hướng (trái) và đa đồ thị có hướng (phải) . 14
1.4 Ví dụ về đồ thị vô hướng (trái) và đồ thị có hướng (phải) . 14
1.5 Ví dụ về đồ thị có hướng 16
2.1 Luật rơi (V) và luật trượt (H) trong hệ Brylawsky . 22
2.2 Luật dọc (V) và luật ngang (H) trong trường hợp d = 2 24
2.3 Các phần tử đầu tiên của dàn vô hạn 2-P(1) 28
2.4 Cây các phân hoạch 2-chặt . 31
2.5 Cấu trúc đệ quy của các cây con Xk . 35
2.6 Biểu diễn cây Td-P như một dây chuyền 35
2.7 Biểu diễn cây TP như một dây chuyền 35
2.8 Cây các phân hoạch chặt 37
2.9 Biểu diễn cây TSP như một dây chuyền 37
3.1 Quá trình chuyển trạng thái của một CFG với 9 chips 45
3.2 Mã hoá một SPM bằng một CFG . 48
3.3 CFG và không gian trạng thái tương ứng . 49
3.4 Dàn ULD không là không gian trạng thái của một CFG nào . 50
3.5 Không gian trạng thái của một CFG tô màu . 51
3.6 Không gian trạng thái của một CCFG 2 chips 54
3.7 Ví dụ về mạng Petri . 57
3.8 Quá trình chuyển trạng thái sau một bước . 58
3.9 CFG và mạng Petri tương ứng . 60
3.10 CCFG và mạng Petri tương ứng 62
3.11 CFG tô màu và mạng Petri tương ứng . 65
4.1 Không gian trạng thái của một CCFG với 2 chips . 73
4.2 Xét đỉnh 1 và đánh số lại các đỉnh . 80
4.3 Đỉnh 6 được thêm vào phản xích f1g và được đánh số lại . 81
4.4 Đánh số lại các đỉnh liên quan đến đỉnh 2 và sinh lọc . 81
4.5 Thêm đỉnh 3, đỉnh 6, đánh số lại và sinh lọc tương ứng 82
4.6 Thêm đỉnh 5, đánh số lại và sinh lọc 82
4.7 Đầu vào và đầu ra của chương trình in ra các lọc 83
4.8 Một số kết quả của thuật toán so sánh hai trạng thái. Trái: đầu vào;phải: đầu ra . 84
4.9 Một trạng thái C trên đồ thị G . 87
4.10 Mạng vận tải tương ứng với trạng thái c 87
4.11 Luồng cực đại f được xây dựng dựa trên luồng f1 trong trường hợp


Mở đầu
Năm 1987, Bak, Tang và Wiesenfeld [7, 8] đã đưa ra vấn đề đột biến tự tổ chức (Self Organization Criticality - SOC) trong vật lý: khi một hệ đang ở trạng thái ổn định (steady state, critical state) được nhiễu bằng một tác động nhỏ, thì hệ sẽ biến đổi đến một trạng thái ổn định mới. Tác động nhỏ này có thể gây nên những biến đổi lớn của hệ. Chẳng hạn như hiện tượng tuyết lở hay hiện tượng cát lở, chỉ cần sự chuyển động nhỏ mang tính địa phương của từng hạt (grain) có thể gây nên những biến đổi lớn toàn cục của cả núi tuyết hay các cột cát (sand piles). Đây là một trong những đặc trưng của hiện tượng SOC. Hiện tượng này thường xảy ra đối với các hệ vật lý trong tự nhiên và được các nhà Vật lý học trên mô hình hóa thành mô hình SPM (Sand Piles Model) của toán rời rạc. Từ đó có rất nhiều nghiên cứu về hiện
tượng SOC và hệ SPM [20], [22], [24] , [25], [26], [27], [28], [30], [44], [78]. Hệ SPM đã được nghiên cứu trong nhiều lĩnh vực khác nhau với nhiều cách tiếp cận khác nhau, điển hình là các công trình của Dhar (1990) [20, 21, 25] và Cori, Rossin (1998) [18] nghiên cứu hệ SPM bằng cách tiếp cận đại số và liên hệ với cây bao trùm của đồ thị; Goles và Kiwi [27] nghiên cứu các điểm dừng của hệ SPM. Đặc biệt, vào những năm 1990, Bjorner, Lovász và Shor [4, 5] đã nghiên cứu hệ động lực CFG - một mở rộng của hệ SPM - bằng cách tiếp cận của lý thuyết ngôn ngữ; N. Biggs (1993) [3] nghiên cứu tính hội tụ của một số hệ kinh tế để tìm ra các thời điểm có những biến động lớn. Morvan, Goles và Phan [30, 31, 32, 33, 34, 64] đã sử dụng cấu trúc dàn để chứng minh tính hội tụ; Phan, Latapy và Lê [52, 54, 57] đã sử dụng phương pháp cây hàm sinh nghiên cứu các mở rộng vô hạn của một số hệ cơ bản, tìm ra tính chất truy hồi của chúng và xây dựng một số thuật toán cũng
như chương trình mô phỏng hệ.
Mục đích của luận án này là nghiên cứu các hệ theo hướng tiếp cận cấu trúc của không gian trạng thái. Luận án sử dụng cấu trúc dàn để tìm hiểu tính hội tụ của các hệ mới, về các điểm đột biến của chúng và sử dụng kỹ thuật đếm bằng phương pháp ECO (Enumeration of Combinatorial Objects) để tính toán lực lượng của hệ. Việc chứng minh cấu trúc dàn của không gian trạng thái (configuration space) của hệ cho phép xác định tính hội tụ và trong một số trường hợp có thể chỉ ra được điểm dừng hay điểm đột biến của hệ. Ngoài ra, cấu trúc dàn cho phép xác định tính đạt được: những trạng thái đạt được từ hai trạng thái a và b cho trước có thể đạt được từ trạng thái c = a ^ b, c là cận dưới lớn nhất của a và b. Phương pháp ECO là phương pháp mới [9], [10] rất hữu hiệu trong việc tính toán lực lượng của các hệ
nhờ vào cấu trúc đệ quy của cây ECO, và có mối liên hệ chặt chẽ với hàm sinh. Tiếp theo, chúng tôi tìm hiểu mối quan hệ giữa các hệ CFG và mở rộng của nó với các hệ tin học nổi tiếng (mạng Petri). Mạng Petri đã được định nghĩa từ những năm 1962 [67], và đã được nghiên cứu trong nhiều công trình [13], [39], [42], [43], [45], [63], [65], [66], [68], [77]. Việc chứng minh mối liên hệ giữa các hệ CFG và mạng Petri cho phép sử dụng các phương pháp nghiên cứu cũng như các thuật toán của mạng Petri vào nghiên cứu các hệ CFG. Cuối cùng, chúng tôi sử dụng lý thuyết tập sắp thứ tự (order theory) để nghiên cứu cấu trúc thứ tự của không gian trạng thái của các hệ CFG mở rộng. Đặc biệt, chúng tôi còn tìm hiểu mối liên hệ giữa các hệ CFG mở rộng và lý thuyết luồng trong mạng để giải bài toán đạt được (reachability problem) của hệ CFG mở rộng. Bài toán đạt được là một bài toán quan trọng trong việc nghiên cứu các hệ. Một mặt nó cho biết các trạng thái nào
có thể xảy ra, các trạng thái nào không bao giờ xảy ra. Mặt khác, nó cho ta biết mối quan hệ giữa các trạng thái, từ trạng thái nào được đến trạng thái nào. Trong trường hợp mạng Petri tổng quát, đây là bài toán mở. Chỉ có một số ít trường hợp giải được trong thời gian đa thức, còn nhiều trường hợp đã được chứng minh là NP đầy đủ. Trong luận án, chúng tôi đã xây dựng thuật toán giải bài toán đạt được của
hệ CCFG trong thời gian O(jV j3), trong đó jV j là số đỉnh của đồ thị nền.