phần Mở đầu, Phần Kết luận, nội dung luận văn đƣợc chia thành 3 chƣơng: 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1 – Mạng Petri cơ sở và mạng các điều kiện - biến cố. Chƣơng này trình bày các khái niệm cơ bản về mạng Petri cơ sở và mạng các hệ điều kiện – biến cố, các quá trình của hệ điều kiện – biến cố. Chƣơng 2 - Mạng vị trí/chuyển và một số tính chất của mạng Petri. Trong chƣơng này, chúng tôi trình bày một cách hệ thống về mạng vị trí/chuyển và các tính chất của mạng Petri gồm tính chất phụ thuộc bộ đánh dấu đầu tiên và tính chất không phụ thuộc vào bộ đánh dấu đầu tiên.
Trong đó, một số tính chất điển hình của mạng Petri đƣợc đề cập là “tính bị chặn”, “tính an toàn”, “tính sống”, “tính tắc nghẽn” và “tính thuận nghịch”. Chƣơng 3 - Ứng dụng mạng Petri trong lập trình hƣớng đối tƣợng tƣơng tranh. Chúng tôi trình bày ứng dụng của lý thuyết mạng Petri kết hợp với lập trình hƣớng đối tƣợng tƣơng tranh và một ứng dụng cụ thể là mô hình Đối tƣợng hợp tác CoOperative Objects để giải quyết bài toán tƣơng tranh “Bữa ăn tối của các nhà triết học”. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1 – MẠNG PETRI CƠ SỞ VÀ MẠNG CÁC ĐIỀU KIỆN - BIẾN CỐ Mạng Petri là một công cụ toán học đƣợc phát triển trên cơ sở của otomat hữu hạn; nhằm mô hình hóa và phân tích các hệ thống không tuần tự.
Mạng Petri đƣợc đề xuất bởi C.Petri vào năm 1962 trong Luận án Tiến sĩ của ông. Ngay từ giữa những năm 70, mạng Petri trở thành đối tƣợng và một trong những động lực chính thúc đẩy việc nghiên cứu giải quyết các vấn đề về tính toán song song và phân tán. Hiện nay, mạng Petri vẫn đang đƣợc nghiên cứu phát triển mạnh mẽ và đƣợc áp dụng vào nhiều lĩnh vực. Mạng Petri có thể đƣợc xem nhƣ là một công cụ toán học và đồ thị đầy tiềm năng dùng cho việc thiết kế và phân tích các hệ - sự kiện rời rạc.
Đồng thời, nó cũng có thể giúp chúng ta trong việc mô hình hóa, phân tích, kiểm tra, lập lịch và đánh giá kết quả của giai đoạn thiết kế. Các khái niệm cơ bản về mạng Petri 1. Ví dụ về mạng Petri Việc tổ chức cho mƣợn và nhận trả sách ở một thƣ viện thông thƣờng nhƣ sau: Bạn đọc có thể truy nhập vào thƣ viện thông qua ba bàn: bàn yêu cầu, bàn nhận sách và bàn trả sách. Trong thƣ viện tất cả các sách đều đƣợc để trên giá và mỗi cuốn sách có một thẻ mục.
Bạn đọc yêu cầu: nếu cuốn sách có trong thƣ viện thì Thủ thƣ lấy sách, thẻ mục của cuốn sách đó đƣợc cập nhật và bạn đọc nhận sách tại bàn nhận sách. Bạn đọc trả sách: Thẻ mục của sách đƣợc cập nhật và sách đƣợc đặt trở lại giá. Quy trình mƣợn sách và trả sách đƣợc mô tả nhƣ hình vẽ dƣới đây. Bàn nhận sách Thư viện Bàn yêu cầu Bàn trả sách Hình 1.
Mô hình mƣợn và trả sách thƣ viện 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bổ sung vào quy trình trên hai bộ phận làm việc là: “cho mƣợn sách” và “nhận lại sách” và hai thành phần thụ động là “kho sách” và “hộp thẻ mục sách đã mƣợn”. Khi đó ta có sơ đồ thƣ viện nhƣ sau: Cho mượn sách Bàn yêu cầu Bàn mượn sách Kho sách Hộp thẻ mục sách đã mượn Nhận lại sách Bàn trả sách Hình 2. Mô hình chi tiết mƣợn và trả sách thƣ viện Đây là một ví dụ về mạng Petri. Các khái niệm cơ sở Định nghĩa 1.1: Bộ ba N = (S, T; F) đƣợc gọi là một mạng Petri nếu: S và T là hai tập hợp không giao nhau.
Các phần tử của tập S đƣợc gọi là S- phần tử, các phần tử của tập T đƣợc gọi là T-phần tử. F (S T) (T S) là một quan hệ nhị nguyên và đƣợc gọi là lƣu đồ của mạng N. Ngƣời ta thƣờng biểu diễn đồ thị định hƣớng cho mạng Petri bằng cách coi mỗi phần tử của tập S T là một đỉnh của đồ thị. Các S-phần tử đƣợc biểu diễn bằng các hình tròn còn các T-phần tử đƣợc biểu diễn bằng các hình vuông.
Quan hệ lƣu đồ F chính là các cung nối giữa các đỉnh tƣơng ứng. Giả sử N là một mạng Petri. Nếu không nhầm lẫn đôi khi ta viết N thay cho S T, đó chính là tập các phần tử của mạng N. i) Với mỗi x N thì: x = { y N (y, x) F } - đƣợc gọi là tập vào của x, x = { y N (x, y) F } - đƣợc gọi là tập ra của x.
5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com với X N thì: X = x và X = x x X x X Chú ý rằng, với x, y N ta có: x y y x ii) Cặp (s, t) S T đƣợc gọi là một chu trình hẹp (self-loop) nếu (s, t) F và (t, s) F. Mạng N đƣợc gọi là tinh khiết (pure) nếu quan hệ lƣu đồ F không chứa một chu trình hẹp nào. iii) Phần tử x N đƣợc gọi là cô lập nếu x x = . iv) Mạng N đƣợc gọi là đơn giản (simple net) nếu các phần tử khác nhau không có chung tập vào và tập ra, nghĩa là: x, y N : ( x = y ) ( x = y ) x = y Ví dụ: s2 t3 s3 t2 s5 t5 t1 s4 t4 Hình 3.
Mô hình mạng đơn giản Mạng ở trên là đơn giản, không tinh khiết và không có phần tử cô lập. Sự đẳng cấu Giả sử N và N’ là hai mạng Petri. 1) Cho một song ánh : N N’. Ta nói hai mạng N và N’ là -đẳng cấu nếu: s SN (s) SN’ và (x, y) FN ((x), (y)) FN’ 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
2) Hai mạng N và N’ đƣợc gọi là đẳng cấu nếu chúng là -đẳng cấu với một song ánh nào đó. Hai mạng đẳng cấu với nhau thì đồ thị biểu diễn của chúng cũng đẳng cấu với nhau và ngƣợc lại. Do vậy, các mạng đẳng cấu với nhau đƣợc xem là “giống nhau”. Phân loại mạng Petri Mạng Petri đƣợc nghiên cứu một cách rộng rãi trên thế giới, hiện nay có hơn 10 loại mạng Petri khác nhau, chúng tạm đƣợc phân loại thành ba cấp bậc.
Các lớp mạng Petri loại một: Là loại mạng đƣợc mô tả bởi các vị trí có khả năng biểu diễn giá trị đúng sai, mỗi vị trí đƣợc đánh dấu tối đa bởi một thẻ dấu không có cấu trúc (unstructured token). Các mạng thuộc lớp này gồm có : Mạng các điều kiện – biến cố (Condition / Event Systems) Mạng cơ sở (Elementary Net Systems) Mạng 1 – an toàn (1-safe systems) Các lớp mạng Petri loại hai: Là loại mạng đƣợc mô tả bởi các vị trí có khả năng biểu diễn giá trị là một số nguyên. Mỗi vị trí đƣợc đánh dấu bởi một số thẻ dấu không có cấu trúc (unstructured token). Đại diện cho lớp mạng này là mạng vị trí chuyển (Place/Transition Nets).
Các lớp mạng Petri loại ba: Mỗi vị trí trong mạng có khả năng biểu diễn giá trị ở mức độ cao, chúng đƣợc đánh dấu bởi tập các thẻ dấu có cấu trúc. Các mạng thuộc lớp này có thể kể đến nhƣ : Mạng Petri cao cấp với các kiểu dữ liệu trừu tƣợng (High-Level Petri Nets with Abstaract Data Types) Mạng Petri suy rộng o Mạng Petri tô màu (Coloured Petri Nets) 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com o Mạng Petri có thời gian o Mạng Petri có gán nhãn 1. Mạng các điều kiện – biến cố 1. Các trƣờng hợp và các bƣớc Ta xét các hệ thống đƣợc tạo bởi các điều kiện (condition) và các biến cố (event).
Các điều kiện đƣợc biểu diễn bằng bởi các S-phần tử còn các biến cố đƣợc biểu diễn bởi các T-phần tử. Chúng ta biết rằng, các điều kiện hoặc là thoả mãn hoặc là không thỏa mãn và sự xuất hiện của các biến cố sẽ làm thay đổi sự thoả mãn của các điều kiện. Trong mỗi một hình trạng của hệ nhƣ thế, một số điều kiện nào đó thoả mãn, số còn lại thì không. Tập các điều kiện đƣợc thoả mãn trong một hình trạng đƣợc gọi là một trƣờng hợp (case).
Biến cố e có thể xuất hiện trong trƣờng hợp c nếu các điều kiện vào của e thuộc c còn các điều kiện ra thì không. Khi biến cố e xuất hiện, các điều kiện vào của e không thoả mãn nữa còn các điều kiện ra của e bắt đầu thoả mãn. Nếu S-phần tử và T-phần tử đƣợc thể hiện nhƣ các điều kiện và các biến cố thì ta sẽ ký hiệu mạng là (B, E; F) thay cho (S, T; F).1: Giả sử N = (B, E; F) là một mạng Petri. Tập con c B đƣợc gọi là một trƣờng hợp hay trạng thái.
Giả sử e E và c B. Ta nói rằng e là kích hoạt đƣợc trong c (hay e là c- kích hoạt) nếu e c và e c = . Giả sử e E , c B và e là kích hoạt đƣợc trong c. Một biến cố của hệ mạng có thể xảy ra nếu trong hệ có trạng thái làm thoả mãn các điều kiện trƣớc (pre-conditions) của biến cố đó và khi ấy các điều kiện sau (post-conditions) của biến cố này chƣa thoả mãn.
Khi biến cố xảy ra, các điều kiện trƣớc không thoả mãn nữa và các điều kiện sau đƣợc thoả mãn. Trạng thái kế tiếp nhận đƣợc sau khi biến cố trên xảy ra phải thuộc không gian các trạng thái, để có 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com thể kích hoạt các biến cố khác. Không gian các trạng thái của hệ là môi trƣờng để dãy các bƣớc có thể xảy ra trên hệ, tạo nên các quá trình trên hệ. Nếu có điều kiện sau nào đó làm cản trở sự xuất hiện của e, nghĩa là e c và e c # thì ta gọi hiện tƣợng này là tình trạng không an toàn.
Tập G E các biến cố mà các tập vào và các tập ra của các biến cố trong G là rời nhau thì G đƣợc gọi là tách biệt. Các biến cố trong một tập tách biệt G có thể xuất hiện đồng thời trong một bƣớc nếu mọi biến cố trong G đều đƣợc kích hoạt bởi cùng một trƣờng hợp.