Szpyrka M.: Sieci Petriego w modelowaniu i analizie systemów współbieżnych, WNT, Warszawa, 2008

Opis

Wymaga się, by każdy system komputerowy działał poprawnie. Ze względu na specyficzne właściwości systemów współbieżnych weryfikowanie jakości tworzonego oprogramowania wyłącznie na podstawie testów jest na ogół niewystarczające. Coraz częściej do sprawdzania poprawności tworzonego systemu lub najważniejszych jego modułów korzysta się z formalnych metod analizy programów. Jednym z najbardziej popularnych formalizmów służących do modelowania i analizy systemów współbieżnych są sieci Petriego. Używa się w nich intuicyjnego języka graficznego, który ułatwia modelowanie systemu, oraz zaawansowanych metod analizy formalnej własności skonstruowanego modelu.

Tematyka książki obejmuje obszerne wprowadzenie do teorii sieci Petriego. Omówiono dziewięć klas sieci, uwzględniając zarówno klasy najczęściej spotykane w literaturze (sieci uogólnione, sieci kolorowane), jak i te nowo proponowane (RTCP-sieci). Dla każdej z omówionych klas przedstawiono przykłady ich zastosowania do modelowania rozmaitych systemów oraz metody analizy ich najważniejszych własności.

Spis treści

  • Przedmowa 1
  • Rozdział 1. Wprowadzenie 3
  • Rozdział 2. Struktura sieci 9
  • 2.1. Grafy skierowane 9
  • 2.2. Sieci i ich reprezentacja graficzna 13
  • 2.3. Własności strukturalne sieci 15
  • 2.4. Podsumowanie 19
  • Rozdział 3. Sieci znakowane 21
  • 3.1. Dynamika sieci 21
  • 3.2. Ograniczoność sieci 24
  • 3.3. Żywotność sieci 26
  • 3.4. Charakterystyczne konstrukcje sieciowe 30
  • 3.5. Modelowanie z zastosowaniem sieci znakowanych 35
  • 3.6. Podsumowanie 44
  • Rozdział 4. Sieci uogólnione 45
  • 4.1. Dynamika sieci 45
  • 4.2. Modelowanie z zastosowaniem sieci uogólnionych 47
  • 4.3. Podsumowanie 50
  • Rozdział 5. Analiza sieci uogólnionych 51
  • 5.1. Grafy osiągalności 52
  • 5.2. Grafy pokrycia 59
  • 5.3. Grafy silnie spójnych składowych 64
  • 5.4. Symetrie 69
  • 5.5. Trwałe zbiory przejść 77
  • 5.6. Algebraiczna reprezentacja sieci 81
  • 5.7. Niezmienniki miejsc 84
  • 5.8. Niezmienniki przejść 94
  • 5.9. Pułapki i zatrzaski 99
  • 5.10. Metody redukcji sieci 110
  • 5.11. Podsumowanie 116
  • Rozdział 6. Sieci miejsc i przejść 119
  • 6.1. Dynamika sieci miejsc i przejść 119
  • 6.2. Modelowanie z zastosowaniem sieci miejsc i przejść 121
  • 6.3. Symulowanie PT-sieci za pomocą sieci uogólnionych 123
  • 6.4. Podsumowanie 126
  • Rozdział 7. Sieci priorytetowe 127
  • 7.1. Dynamika sieci priorytetowych 127
  • 7.2. Modelowanie z zastosowaniem sieci priorytetowych 129
  • 7.3. Podsumowanie 137
  • Rozdział 8. Sieci czasowe 139
  • 8.1. Proste sieci czasowe 140
  • 8.2. Przedziałowe sieci czasowe 144
  • 8.3. Modelowanie z zastosowaniem sieci czasowych 147
  • 8.4. Podsumowanie 150
  • Rozdział 9. Analiza sieci czasowych 151
  • 9.1. Grafy osiągalności dla prostych sieci czasowych 151
  • 9.2. Grafy klas stanów 155
  • 9.3. Podsumowanie 160
  • Rozdział 10. Sieci kolorowane 161
  • 10.1. Wielozbiory 162
  • 10.2. Niehierarchiczne sieci kolorowane 163
  • 10.3. Ograniczoność sieci 168
  • 10.4. Żywotność sieci 172
  • 10.5. Hierarchiczne sieci kolorowane 175
  • 10.6. Modelowanie z zastosowaniem sieci kolorowanych 179
  • 10.7. Podsumowanie 185
  • Rozdział 11. Analiza sieci kolorowanych 187
  • 11.1. Grafy osiągalności 187
  • 11.2. Grafy osiągalności z klasami równoważności 192
  • 11.3. Niezmienniki sieci kolorowanych 196
  • 11.4. Podsumowanie 204
  • Rozdział 12. Czasowe sieci kolorowane 205
  • 12.1. Wielozbiory czasowe 205
  • 12.2. Dynamika sieci 207
  • 12.3. Modelowanie z zastosowaniem czasowych sieci kolorowanych 213
  • 12.4. Podsumowanie 218
  • Rozdział 13. RTCP-sieci 219
  • 13.1. Niehierarchiczne RTCP-sieci 219
  • 13.2. Hierarchiczne RTCP-sieci 227
  • 13.3. Modelowanie z zastosowaniem RTCP-sieci 239
  • 13.4. Podsumowanie 244
  • Rozdział 14. Analiza RTCP-sieci 247
  • 14.1. Grafy osiągalności 247
  • 14.2. Grafy pokrycia 251
  • 14.3. Podsumowanie 255
  • Rozdział 15. Zakończenie 257
  • Dodatek A. Polsko-angielski słownik terminów 259
  • Dodatek B. Angielsko-polski słownik terminów 265
  • Dodatek C. Wybrane narzędzia do konstruowania i analizy sieci Petriego 271
  • Dodatek D. Lista symboli 273
  • Literatura 277
  • Skorowidz 283

Okładka