4
MỤC LỤC Trang
Trang phụ bìa
1
Lời cam đoan
2
Mục lục
4
Danh mục các thuật ngữ
6
Danh mục các hình vẽ
9
MỞ ĐẦU
10
Chƣơng 1. Các khái niệm cơ sở
15
1.1. Đại cƣơng về đồ thị
15
1.1.1. Định nghĩa đồ thị
15
1.1.2. Đƣờng đi trên đồ thị
16
1.1.3. Một số cách biểu diễn đồ thị trong máy tính
17
1.1.4. Bài toán đƣờng đi trên đồ thị
trên hệ mạng và độ phức tạp của chúng
2.1. Bài toán điều khiển tƣơng tranh các quá trình
49
2.2. Thuật toán điều khiển tƣơng tranh trên các hệ mạng điều kiện
- biến cố
51
2.2.1. Đồ thị các trƣờng hợp
51
2.2.2. Các bƣớc tƣơng tranh trên hệ mạng điều kiện - biến cố
53
2.2.3. Đầy đủ hoá đồ thị các trƣờng hợp
55
2.3. Thuật toán điều khiển tƣơng tranh trên các hệ mạng vị trí -
chuyển
59
2.3.1. Đồ thị phủ của hệ mạng vị trí - chuyển
59
2.3.2. Các bƣớc tƣơng tranh trên hệ mạng vị trí - chuyển
62
2.3.3. Tìm bƣớc tƣơng tranh bằng cách rút gọn đồ thị phủ
63
2.4. Kết luận cuối chƣơng
67
Chƣơng 3. Độ phức tạp otomat của các thuật toán
đoán nhận ngôn ngữ
68
3.1. Độ phức tạp otomat của nguồn
69
3.2. Độ phức tạp otomat của biểu thức chính quy
70
DANH MỤC CÁC THUẬT NGỮ
Đồ thị
Graph
Tập đỉnh
Set of vertices
Tập cạnh
Set of edges
ánh xạ kề
Adjacency mapping
Đƣờng đi
Path
Chu trình
Cycle
Đồ thị vô hƣớng
Undirected graph
Đồ thị có hƣớng
Directed graph
Đa đồ thị
Multigraph
Đồ thị phủ
Coverage graph
Ngôn ngữ hình thức
Formal language
Bảng chữ cái
Alphabet
Từ
Word
Từ vô hạn
Infinitive word
7
Văn phạm
Grammar
Văn phạm cảm ngữ cảnh
Context-sensitive grammar
Văn phạm phi ngữ cảnh
Context-free grammar
Văn phạm chính quy
Regular grammar
Chùm đầu
Heading bunch
-ngôn ngữ
-language
Thuật toán đoán nhận
Recognition algorithm
Thuật toán phân tích
Parsing algorithm
Độ phức tạp
Complexity
Độ phức tạp đoán nhận
Recognition complexity
Độ phức tạp otomat
Automata complexity
Hệ mạng
Net system
Mạng Petri
Petri net
Tập vào
Pre-set
Tập ra
Dung l-ợng
Capacity
Bộ đánh dấu
Marking
Hệ mạng sống
Live net system
Hệ mạng chu trình
Cycle net system
Quá trình
Process
Quá trình tuần tự
Sequential process
Quá trình t-ơng tranh
Concurrent process
Hành vi
Behaviour
Hành vi tuần tự
Sequential behaviour
Hành vi t-ơng tranh
Concurrent behaviour
Hỡnh 1.5. Th t ca cỏc nh c duyt theo chiu sõu
23
Hỡnh 1.6. Th t ca cỏc nh c duyt theo chiu rng
24
Hỡnh 1.7. Ngun I
1
29
Hỡnh 1.8. Ngun n nh y K
1
32
Hỡnh 1.9. Ngun K
2
l ngun bự ca ngun K
1
33
Hỡnh 1.10. Mng Petri n gin
39
Hỡnh 1.11. Mt h mng v trớ - chuyn
45
Hỡnh 2.1. S bin i tng tranh mt quỏ trỡnh tun t
50
Hình 2.2. Đồ thị các tr-ờng hợp của hệ
52
Hình 2.3. Đồ thị các tr-ờng hợp đầy đủ
58
Hình 2.4. Minh hoạ Định lý 2.9
65
))
84
Hình 3.5. Minh hoạ hàm Z
Ii
(pa)
87
10
MỞ ĐẦU
Lý thuyết đồ thị là một ngành khoa học ra đời rất sớm và có nhiều ứng
dụng. Nhờ lý thuyết đồ thị mà nhiều bài toán phức tạp, diễn giải dài dòng
đƣợc mô tả hình học một cách trực quan và cô đọng. Lý thuyết đồ thị đã trở
thành công cụ đắc lực cho việc thiết kế các thuật toán [4,7,12,23], mô hình
hình học và phân tích các hệ thống [9,49,62], biểu diễn các quá trình của hệ
thống [34,60]
Việc tổ chức thực hiện một cách nhanh chóng các quá trình xảy ra trên
một hệ thống phân tán là một trong những mục tiêu của bài toán điều khiển
hệ thống. Ngoài kỹ thuật đồng bộ hoá thì kỹ thuật thực thi song song đã đƣợc
xây dựng thành công nhờ một số công cụ nhƣ: ngôn ngữ vết [11,13], phép
đẩy trái [62] Chính điều này đã khích lệ tác giả trong việc nghiên cứu ứng
dụng lý thuyết đồ thị để xây dựng các thuật toán điều khiển tối ƣu các quá
trình tuần tự trên một số hệ thống phân tán đƣợc biểu diễn bởi các hệ mạng
điều kiện - biến cố và hệ mạng vị trí - chuyển.
Từ một hệ mạng đã cho chúng ta có thể xây dựng đƣợc ngôn ngữ sinh
nhu cầu ứng dụng của thực tiễn, việc nghiên cứu tính chất của các lớp ngôn
ngữ từ vô hạn (
-ngôn ngữ) trở nên cần thiết. Lý thuyết ngôn ngữ từ vô hạn
đƣợc đề xuất từ các công trình nghiên cứu về logic của J. R. Buchi [20], lý
thuyết mạch điện của D. Muller [43], otomat của R. McNaughton [41]
Ngôn ngữ từ vô hạn đƣợc tiếp tục quan tâm nghiên cứu và ứng dụng trong
nhiều lĩnh vực khác nhau, chẳng hạn nhƣ: lý thuyết mật mã của G. Hansel
[28], L. Staiger [59], Nguyễn Hƣơng Lâm và Đỗ Long Vân [37], lý thuyết
12
các quá trình của M. Nivat [45], lý thuyết đô phức tạp của Đặng Huy Ruận
[52,53], Đỗ Long Vân và Phan Trung Huy [32,70], hành vi hệ thống của A.
W. Roscoe [50], mạng Petri của Phạm Trà Ân [14], V. E. Kotov [34], W.
Reisig [49], Hoàng Chí Thành [60], lý thuyết trò chơi của M. Davis [25],
ngôn ngữ vết của J. I. Aalbersberg và G. Rozenberg [13] …
Một trong những vấn đề quan trọng đƣợc nhiều ngƣời quan tâm nghiên
cứu trong lý thuyết ngôn ngữ hình thức là tính toán độ phức tạp otomat đoán
nhận các lớp ngôn ngữ sinh bởi các công cụ khác nhau. Trên cơ sở đó đƣa ra
các đặc trƣng cho các công cụ sinh và các lớp ngôn ngữ tƣơng ứng. Hơn nữa
các ngôn ngữ này còn đƣợc dùng để biểu diễn hành vi tuần tự của các hệ
thống nói chung và các hệ thống phân tán nói riêng.
Nhiều nhà khoa học trên thế giới đã tập trung nghiên cứu và phát triển
ngôn ngữ vết trong các bài toán điều khiển hệ thống [13,50], xác định độ
phức tạp otomat của các thuật toán đoán nhận các -ngôn ngữ phi ngữ cảnh
[38], độ phức tạp của các -otomat [56], áp dụng lý thuyết ngôn ngữ cho các
bài toán quyết định [39,57]. Ở Việt Nam, việc nghiên cứu điều khiển hệ
thống tƣơng tranh và độ phức tạp tính toán trên ngôn ngữ hình thức đƣợc tập
mạng vị trí - chuyển.
4) Tính toán cận trên của độ phức tạp otomat đoán nhận các ngôn ngữ
sinh bởi nguồn, biểu thức chính quy, sơ đồ sinh và chùm đầu.
Các kết quả chính của luận án đã đƣợc trình bày tại:
1. Hội thảo Khoa học Quốc gia “Một số vấn đề chọn lọc của Công nghệ
Thông tin và Truyền thông”.
2. Hội thảo Khoa học Quốc gia “Nghiên cứu cơ bản và ứng dụng Công nghệ
Thông tin”.
3. Tạp chí Tin học và Điều khển học.
4. Xemina Tin học tại Bộ môn Tin học, Khoa Toán - Cơ - Tin học, Trƣờng
Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
14
Luận án có cấu trúc nhƣ sau. Sau phần mở đầu là 3 chƣơng chính.
Chƣơng 1 trình bày các khái niệm cơ sở và các kết quả liên quan sẽ đƣợc
dùng trong hai chƣơng sau. Những khái niệm cơ bản xuyên suốt luận án là lý
thuyết đồ thị. Đó là công cụ toán học hữu ích mà tác giả đã sử dụng để biểu
diễn các khái niệm, các hệ thống và xây dựng nên các thuật toán hữu hiệu.
Bên cạnh đó, tác giả cũng nhắc lại các khái niệm cơ bản của ngôn ngữ hình
thức, otomat và của các hệ mạng.
Chƣơng 2 trình bày bài toán điều khiển tƣơng tranh các quá trình xảy
ra trên một hệ thống và xây dựng hai thuật toán điều khiển tƣơng tranh dựa
trên đồ thị gán nhãn có hƣớng và phân tích độ phức tạp của chúng. Thuật
toán thứ nhất làm đầy đủ đồ thị các trƣờng hợp của một hệ mạng điều kiện -
biến cố. Từ đó ta nhận đƣợc một bức tranh đầy đủ về hành vi tƣơng tranh của
hệ thống đƣợc biểu diễn bởi hệ mạng này. Đồng thời ta cũng nhận ra đƣợc
Những khái niệm này đƣợc trích dẫn từ các tài liệu [1,4,8,12,23,29,49] và là
các công cụ để xây dựng lên các kết quả đƣợc trình bày ở hai chƣơng sau của
bản luận án.
1.1. ĐẠI CƢƠNG VỀ ĐỒ THỊ
Lý thuyết đồ thị là một ngành khoa học phát triển rất sớm và trở thành
công cụ hữu ích cho sự phát triển của nhiều ngành khoa học khác. Với trực
quan hình học, lý thuyết đồ thị đã giúp chúng ta thiết kế và phân tích nhiều
thuật toán lớn để giải quyết các bài toán phức tạp.
1.1.1. Định nghĩa đồ thị
Định nghĩa 1.1: Đồ thị là một cặp G = (V, E), trong đó:
1) V là tập hợp các đỉnh,
2) E V V, là tập hợp các cạnh.
16
Ví dụ 1.1: Một đồ thị có 5 đỉnh 8 cạnh.
Hình 1.1: Đồ thị hữu hạn
Đồ thị G cho ở Hình 1.1 có tập các đỉnh V = {a, b, c, d, e} và tập các
cạnh E = {(a, b), (a, c), (b, c), (d, b), (d, c), (e, a), (e, b), (e, d)}.
Giữa hai đỉnh của một đồ thị có thể có nhiều cạnh nối chúng. Đồ thị
17
hướng, còn nếu nó có sắp thứ tự thì đƣợc gọi là cạnh có hướng. Cạnh có
hƣớng còn đƣợc gọi là cung của đồ thị. Ngƣời ta thƣờng phân các đồ thị
thành hai lớp.
Định nghĩa 1.3: Đồ thị chỉ chứa các cạnh vô hƣớng đƣợc gọi là đồ thị vô
hướng còn đồ thị chỉ chứa các cạnh có hƣớng (cung) đƣợc gọi là đồ thị có
hướng.
1.1.2. Đường đi trên đồ thị
Giả sử G = (V, E) là một đồ thị.
Định nghĩa 1.4: Đường đi trên đồ thị G là một dãy các đỉnh của đồ thị: < x
1
,
x
2
, , x
i
, x
j+1
, , x
k-1
, x
k
> sao cho, mỗi đỉnh trong dãy (không kể đỉnh đầu
tiên) kề với đỉnh trƣớc nó bằng một cạnh nào đó, nghĩa là:
i = 2, 3, , k-1, k : (x
i-1
,x
i
0 0 1 0
0 1 1 0
A = 18
Hình 1.2. Đa đồ thị có hƣớng và ma trận kề tƣơng ứng
b) Biểu diễn đồ thị bằng các danh sách kề
Với mỗi đỉnh của đồ thị ta xây dựng một danh sách liên kết chứa các
đỉnh kề với đỉnh này. Danh sách này đƣợc gọi là danh sách kề. Một đồ thị
đƣợc biểu diễn bằng một mảng các danh sách kề.
Ví dụ 1.3: Biểu diễn mảng các danh sách kề của đồ thị G trong Ví dụ 1.2.
p[a] b c
p[c]
p[d]
Hình 1.3. Mảng các danh sách kề biểu diễn đồ thị
1.1.4. Bài toán tìm đường đi trên đồ thị
Bài toán: Cho đồ thị G và hai đỉnh a, b thuộc G. Có hay không một đƣờng đi
từ đỉnh a đến đỉnh b trên đồ thị G?
Dựa vào các kết quả đã có, chúng ta xây dựng thuật toán sau đây để
giải bài toán trên.
Thuật toán 1.1 (Xác định đường đi) [4,12]
Đầu vào: Đồ thị G = (V, E) và ha đỉnh a, b thuộc V.
Đầu ra: Câu trả lời: ”có / không”.
1) Xây dựng ma trận kề A cho đồ thị G.
19
2) Tính ma trận tổng các luỹ thừa T = A
1
+ A
2
+ + A
n-1
.
3) Nếu T[a,b] 1 thì kết luận là có đƣờng đi từ đỉnh a đến đỉnh b, ngƣợc
lại thì kết luận là không có.
Hiển nhiên, thuật toán trên có độ phức tạp là O(n
4
).
, l
k-1 k
, x
k
> sao cho, mỗi đỉnh
trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trƣớc nó bằng một cạnh nào
đó có nhãn tƣơng ứng, nghĩa là: i = 2, 3, , k-1, k : (x
i-1
, x
i
) E và
n((x
i-1
, x
i
)) = l
i-1 i
.
Ta nói rằng đƣờng đi này đi từ đỉnh đầu x
1
đến đỉnh cuối x
k
với dãy
nhãn là = l
12
l
23
l
k-1 k
.
một cách “đi qua” tất cả các đỉnh của đồ thị để truy nhập, thêm bớt thông tin
ở các đỉnh của đồ thị này. Với các đồ thị không liên thông thì thuật toán sẽ
duyệt lần lƣợt từng mảng liên thông và kết quả sẽ là danh sách ghép của các
danh sách các đỉnh trong từng mảng liên thông của đồ thị đã cho. Các thuật
toán duyệt đồ thị đã đƣợc trình bày trong [4,12,23]. Chúng tôi nhắc lại các
thuật toán này để sử dụng trong các thuật toán điều khiển tƣơng tranh sẽ đƣợc
trình bày ở Chƣơng 2.
a) Thuật toán duyệt đồ thị tổng quát
Giả sử G là một đồ thị đã cho. Ký hiệu DS là một cấu trúc dữ liệu kiểu
danh sách dùng để chứa các đỉnh của đồ thị, L là một danh sách dùng để lƣu
21
dãy các đỉnh. Thuật toán tổng quát duyệt đồ thị đƣợc trình bày sơ lƣợc nhƣ
sau.
Thuật toán 1.2 (Duyệt đồ thị) [4,12]
Đầu vào: Đồ thị G = (V, F) đƣợc cho dƣới dạng ánh xạ kề.
Đầu ra: Danh sách L chứa tất cả các đỉnh của đồ thị G.
1) Đánh dấu “chưa duyệt” cho mọi đỉnh v V ;
2) Khởi tạo danh sách L rỗng, L ;
3) Với mỗi đỉnh v V, nếu v chƣa đƣợc duyệt thì thực hiện vòng lặp sau:
4) Khởi tạo danh sách DS rỗng, DS ;
5) Nạp đỉnh v vào danh sách DS ;
6) Lấy đỉnh x ở đầu danh sách DS và loại nó ra khỏi danh sách ;
7) Duyệt đỉnh x ;
8) Thêm x vào cuối danh sách L, L L . x ;
9) Đổi thành dấu “đã duyệt” cho đỉnh x ;
10) Nạp các đỉnh chƣa đƣợc duyệt trong tập đỉnh kề F(x) vào danh sách
11 if NOT Duyet [x] then
12 begin
13 Thăm_đỉnh (x) ;
14 L L . x ;
15 Duyet [x] true ;
16 push x onto S ;
17 end ;
18 pop(S) ; {loại bỏ phần tử ở đỉnh của S}
19 end ;
20 end ;
21 BEGIN { Chƣơng trình chính }
22 for v V do Duyet [v] false ;
23 L ;
23
24 for v V do
25 if NOT Duyet [v] then D_SAU (v) ;
26 END.
Độ phức tạp của thật toán duyệt theo chiều sâu
Vòng lặp 24) có độ phức tạp là O(n). Với mỗi đỉnh v V thủ tục
D_SAU đƣợc gọi đúng một lần có độ phức tạp là O(|DK[v]|). Mà
Vv
mvDK .2|)(|
. Do vậy, độ phức tạp của thật toán duyệt theo chiều sâu là:
8 dequeue x from Q ; {loại x ra khỏi đầu hàng đợi Q}
9 Thăm_đỉnh (x) ;
10 L L . x ;
11 for u DK[x] do
12 if NOT Duyet [u] then
13 begin
14 enqueue u into Q ;
15 Duyet [u] true ;
16 end ;
17 end ;
18 end ;
19 BEGIN { Chƣơng trình chính }
20 for v V do Duyet [v] false ;
21 L ;
22 for v V do
23 if NOT Duyet [v] then D_RONG (v) ;
24 END .
25
Độ phức tạp của thật toán duyệt theo chiều rộng
Tƣơng tự nhƣ phân tích độ phức tạp của thuật toán duyệt đồ thị theo
chiều sâu, thuật toán duyệt đồ thị theo chiều rộng cũng có độ phức tạp là:
O(n+m).
Ví dụ 1.6: Đồ thị trong Ví dụ 1.5 đƣợc duyệt theo chiều rộng.
*
là ngôn ngữ bao gồm tất cả các từ trên bảng chữ cái , còn
+
là ngôn ngữ bao gồm tất cả các từ không rỗng trên bảng chũ cái .
Hiển nhiên, =
+ {}, trong đó là ký hiệu từ rỗng.
1.2.2. Các phép toán trên ngôn ngữ
1) Tích ghép của hai ngôn ngữ L
1
và L
2
trên cùng bảng chữ cái , ký
hiệu là L
1
.L
2
, là một ngôn ngữ trên và đƣợc xác định nhƣ sau:
L
1
.L
2
= {u.v u L
1
và v L
2
và đƣợc xác định nhƣ sau:
L
1
L
2
= {u u L
1
và u L
2
}.
4) Hiệu của hai ngôn ngữ L
1
và L
2
trên cùng bảng chữ cái là một
ngôn ngữ trên bảng chữ cái , ký hiệu là L
1
\ L
2
, đƣợc xác định nhƣ sau:
L
1
\ L
2
= {u u L
1
và u L
2
}.
5) Phần bù của ngôn ngữ L trên bảng chữ cái là ngôn ngữ trên bảng
27
7) Lặp cắt của ngôn ngữ L trên bảng chữ cái là ngôn ngữ trên , ký
hiệu là L
+
, đƣợc xác định bởi: L
+
= L
1
L
2
Hiển nhiên, L
+
= L
*
\ {}.
1.2.3. Một số công cụ sinh ngôn ngữ chính quy và mối quan hệ giữa chúng
Ngôn ngữ chính quy đƣợc sinh ra từ một số công cụ nhƣ: văn phạm
chính quy, otomat hữu hạn, nguồn …
a) Văn phạm chính quy
Định nghĩa 1.6: Văn phạm là bộ bốn G = (, V, P, S), trong đó:
- là bảng chữ cái chính,
- V là bảng chữ cái phụ,
- S là một chữ cái phụ và đƣợc gọi là ký hiệu khởi đầu,
- P là tập hữu hạn các quy tắc sinh có dạng , với ,
(
V)
*
v x
2
và u v là một quy tắc
dẫn xuất trong P.
Ta nói rằng từ x dẫn ra từ y, ký hiệu x
*
y, nếu tồn tại một dãy các từ
x
0
, x
1
, , x
k
(
V)
*
với k
0, sao cho: x
0
= x, x
k
= y và x
i
x
i+1
, với 0
1
,
2
(
V)
*
, A V,
(
V)
+
và
. Ngôn ngữ sinh bởi văn phạm cảm ngữ cảnh đƣợc gọi là
ngôn ngữ cảm ngữ cảnh.
Ví dụ 1.8: Xét văn phạm cảm ngữ cảnh dƣới đây.
G
2
= ({a,b,c}, {S,B,C}, P, S ) với:
P = {S aSBC, S aBC, CB BC, aB ab, bB bb, C c}.
Ngôn ngữ cảm ngữ cảnh sinh bởi văn phạm trên là:
L(G
2
) = {a
n
w
là đảo ngƣợc của từ w.
Văn phạm phi ngữ cảnh mở rộng là văn phạm phi ngữ cảnh có chứa
quy tắc rỗng.
Ví dụ 1.10: Văn phạm phi ngữ cảnh mở rộng.
G
4
= ({a,b,c}, {S,X,Y,Z}, P, S ) với:
P = {S XYc, S YXcc, X YZ, Z ac, Y Xa, Y }.
Copyright: Tài liệu đại học ©