II Konferencja Naukowa KNWS'05 Informatyka- sztuka czy ... ?· 4.1.Wyznaczyć stopień incydencji dla…

  • Published on
    01-Mar-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>NOWOCZESNA IMPLEMENTACJA HEURYSTYCZNEGO ALGORYTMU KODOWANIA STRUKTURALNEGO STANW LOKALNYCH</p> <p>W AUTOMATACH WSPBIENYCH</p> <p>Piotr Bubacz, Bartosz Mstowski, Marian Adamski </p> <p>Instytut Informatyki i Elektroniki, Uniwersytet Zielonogrski 65-246 Zielona Gra, ul. Podgrna 50 </p> <p>e-mail: {M.Adamski, P.Bubacz}@iie.uz.zgora.pl, B.Mstowski@adbglobal.com </p> <p>STRESZCZENIE</p> <p>W artykule zostaa przedstawiona nowoczesna implementacja heurystycznego algorytmu </p> <p>kodowania strukturalnego stanw lokalnych w automatach wspbie nych. W ramach pracy </p> <p>przedstawiono rodowisko .NET oraz mo liwo jego wykorzystania w implementacji </p> <p>algorytmw analizy i kodowania sieci Petriego. Wynikiem pracy jest zintegrowane rodowisko </p> <p>umo liwiaj ce projektowanie, analiz i kodowanie sieci Petriego Petri Net Workshop. </p> <p>1. WPROWADZENIE</p> <p>Nowoczesne technologie wspieraj prac inyniersk i naukow. Jednym z najwaniejszych </p> <p>elementw nowoczesnego programowania jest wielokrotne wykorzystanie moduw oraz </p> <p>atwo rozwijania aplikacji. </p> <p>Moliwoci te daje programowanie zorientowane obiektowo, gdzie klasy s atwo </p> <p>wykorzystywane w innych aplikacjach. Jednak dotychczas stosowane to byo tylko w jednym </p> <p>jzyku programowania. Programici musieli zdecydowa si na jeden jzyk i najczciej na </p> <p>jedno rodowisko programistyczne. Podejcie to zmienia firma Microsoft, prezentujc</p> <p>technologi .NET. Pozwala ona nie tylko wykorzystanie tych samych klas w wielu </p> <p>aplikacjach, ale rwnie czenie ze sob wielu jzykw programowania, tak, e kady </p> <p>programista moe tworzy elementy w dowolnym jzyku i rodowisku. Szczeglnie jest to </p> <p>wane w pracy naukowej. Kada z osb prowadzcych badania rozwija swoj cz projektu </p> <p>w dowolnym jzyku, a dziki waciwociom rodowiska .NET umoliwia to ich wzajemne </p> <p>wspdziaanie, skoordynowane w jednej aplikacji. </p> <p>Wykorzystujc zoptymalizowane struktury danych oraz moliwoci platformy .NET </p> <p>przeprowadzana jest atwa, a co najwaniejsze prosta do rozszerzania, implementacja </p> <p>algorytmw projektowania, analizy i kodowania sieci Petriego. </p> <p>87</p> <p>II Konferencja Naukowa KNWS'05</p> <p>"Informatyka- sztuka czy rzemios o"</p> <p>15-18 czerwca 2005, Z otniki Luba skie</p> <p>2. HEURYSTYCZNY ALGORYTMU KODOWANIA STRUKTURALNEGO STANW LOKALNYCHW AUTOMATACH WSPBIE NYCH</p> <p>Heurystyczny algorytmu kodowania strukturalnego stanw lokalnych w automatach </p> <p>wspbienych zosta zaproponowany w [1]. Jego zastosowanie i modyfikacje zostay </p> <p>przedstawione w pracach [2,3,4,6]. </p> <p>Algorytm strukturalnego kodowania miejsc sieci skada si z dwch gwnych etapw. </p> <p>W etapie pierwszym nastpuje kodowanie makromiejsc (makrostanw lokalnych), </p> <p>w kolejnym etapie kodowane s miejsca wewntrz tych makromiejsc. Makromiejsce </p> <p>nierwnolege stopniowo rozrnia si wprowadzajc zmienne kodujce, przyjmujce </p> <p>wartoci 0 w makromiejscu, warto 1 w makromiejscach do niego przylegych i warto </p> <p>w makromiejscach rwnolegych. </p> <p>Minimalizacja liczby zmiennych kodujcych zwizana jest z kolejnym wyborem </p> <p>wierzchokw grafu wspbienoci o najwyszym stopniu incydencji. Zakoczenie </p> <p>kodowania makromiejsc nastpuje, gdy wszystkie makromiejsca rozrniane s co najmniej </p> <p>jedn zmienna kodujc. atwo stwierdzi, e superpozycja kodw rwnoczenie</p> <p>oznakowanych makromiejsc tworzy wtedy unikalny kod wierzchoka grafu znakowa</p> <p>osigalnych makrosieci. Naley zwrci uwag na fakt, e makromiejsce w proponowanym </p> <p>sposobie kodowania reprezentuje dowolny fragment sieci otrzymanej na drodze jej </p> <p>hierarchicznego skadania (agregacji) lub rozkadania (deagregacji). </p> <p>Kodowanie miejsc w ramach makromiejsca odbywa si w sposb analogiczny do kodowania </p> <p>makromiejsc, jeeli to makromiejsce reprezentuje podsie Petriego z rwnolegoci.</p> <p>W przypadku makromiejsc typu automatowego wykorzystuje si znane metody kodowania </p> <p>teorii automatw. </p> <p>Algorytm kodowania globalnego makromiejsc: </p> <p>1. Dokona dekompozycji sieci do postaci makrosieci reprezentujcej analizowan sie</p> <p>Petriego. </p> <p>2. Wyznaczy graf znakowa osigalnych makrosieci i na jego podstawie okreli relacje: </p> <p>a) wspbienoci makromiejsc R, </p> <p>b) niewspbienoci (nastpstw) makromiejsc N. </p> <p>Relacje naley przedstawi w postaci grafw niezorientowanych lub odpowiadajcych im </p> <p>list nastpstw wierzchokw. Graf N jest dopenieniem grafu R do grafu penego. </p> <p>3. Przyj i=1 oraz Ni=N</p> <p>4. Dopki graf Ni nie jest grafem pustym (macierz niewspbienoci nie zawiera samych </p> <p>zer), wykona:</p> <p>88</p> <p>4.1.Wyznaczy stopie incydencji dla wszystkich wierzchokw grafu Ni. Wybra</p> <p>wierzchoek o najwyszym stopniu incydencji. Wierzchoki reprezentujce </p> <p>makromiejsca rwnolege, przylege do tych samych wierzchokw mona</p> <p>potraktowa jako jedno makromiejsce o stopniu incydencji rwnej sumie stopni </p> <p>poszczeglnych makromiejsc. </p> <p>4.2.Wybra wierzchoek najwyszym stopniu incydencji. </p> <p>4.3.Wybranemu makromiejscu mp przypisa kod Q(i)=0, dla kadego z pozostaych </p> <p>miejsc wykona</p> <p>4.3.1. Jeli makromiejsce jest wspbiene do danego i jednoczenie niewspbiene</p> <p>do tego samego zbioru miejsc, co mp, przypisa kod Q(i) = 0. Wykreli ten </p> <p>wierzchoek z grafu tzn. wyzerowa odpowiedni wiersz i kolumn w macierzy </p> <p>N(i) i zaznaczy jako usunite. </p> <p>4.3.2. W przeciwnym wypadku jeli makromiejsce jest niewspbiene z mp</p> <p>przypisa Q(i) = 1.</p> <p>4.3.3. Jeli makromiejsce zostao usunite z N(i) i jest niewspbiene z mp to </p> <p>przypisa kod Q(i) = . Oznacza to, e zmienna moe by wykorzystana w </p> <p>kodowaniu miejsc nalecych do makromiejsca. </p> <p>4.3.4. W przeciwnym wypadku makromiejsce wspbiene z wybranym, ktre nie </p> <p>zostao usunite otrzymuje kod Q(i) = *. Oznacza to, e zmienna ta nie moe</p> <p>by ju wykorzystana do kodowania tego makromiejsca ani adnego z miejsc </p> <p>do niego nalecych </p> <p>4.3.5. Usun mp z macierzy N(i).</p> <p>5. Dokona korekcji kodw czciowych. Dla kadego makromiejsca mp wykona:</p> <p>5.1.Dla kadej zmiennej Q(i) kodu mp, jeli Q(i) = , wykona:</p> <p>5.1.1. Znale makromiejsce mp wspbiene do mp.</p> <p>5.1.2. Jeli zmienna Q(i) kodu mp jest rna od oraz rna od *, zmieni warto</p> <p>zmiennej Q(i) kodu mp na *. </p> <p>5.1.3. Powtrzy krok 5.1.1. a do sprawdzenia wszystkich makromiejsc </p> <p>rwnolegych do mp.</p> <p>6. Zakodowa miejsca w ramach poszczeglnych makromiejsc (kodowanie lokalne) </p> <p>Szczegowy opis algorytmu i przykady kodowania mona znale w [1,6]. </p> <p>89</p> <p>3. WPROWADZENIE DO RODOWISKA .NET</p> <p>Technologia .NET jest nowatorsk technologi umoliwiajc tworzenie rozwiza</p> <p>niezalenych od systemu operacyjnego i platformy sprztowej, m.in. dla komputerw </p> <p>stacjonarnych (np. PC), mobilnych (np. Pocket PC), usug WWW (np. ASP.NET), usug </p> <p>sieciowych, rozwiza bazodanowych (ADO.NET) oraz wielu innych. Platforma .NET </p> <p>pozwala na tworzenie i uytkowanie bezpiecznych i stabilnych aplikacji - zarwno </p> <p>skupionych jak i rozproszonych. </p> <p>Sercem platformy .NET jest Common Language Runtime (w skrcie CLR), czyli wsplne dla </p> <p>rnych jzykw rodowisko wykonywania programw. Kod programu w platformie .NET </p> <p>nie jest kompilowany bezporednio do postaci kodu wykonywalnego, lecz do postaci jzyka </p> <p>Microsoft Intermediate Language (w skrcie MSIL), czyli poredniego midzy kodem </p> <p>programu a instrukcjami procesora. Do gwnych zada CLR nale: przydzielanie pamici </p> <p>obiektom oraz zarzdzanie t pamici przy pomocy bardzo efektywnych technik garbage </p> <p>collection, sprawdzanie poprawnoci typw oraz dbanie o bezpieczestwo.</p> <p>Gwn cech, ktra wyrnia platform .NET wrd innych rodowisk programistycznych, </p> <p>jest wsparcie wielu jzykw programowania. Umoliwia to grupom programistw o rnych </p> <p>umiejtnociach tworzenie komponentw oprogramowania w wybranych jzykach, a </p> <p>nastpnie poczenie opracowanych komponentw w dobrze wsppracujc cao.</p> <p>Poczenie midzy jzykami realizowane jest nawet na poziomie klasy. Programici mog</p> <p>dziedziczy po klasie zdefiniowanej w innym jzyku. </p> <p>Wraz z wprowadzeniem CLR programici uzyskali moliwo wyboru spord szerokiej </p> <p>palety jzykw, co pozwala im programowa w jzyku najbardziej odpowiadajcym ich </p> <p>umiejtnociom i najlepiej nadajcym si do wykonania otrzymanego zadania. Wsppraca </p> <p>fragmentw kodu napisanych w rnych jzykach moliwa jest ze wzgldu na to, e kady </p> <p>jzyk zgodny z platform .NET Framework kompilowany jest do kodu MSIL, uruchamianego </p> <p>nastpnie w rodowisku CLR. </p> <p>Model programowania na platformie .NET jest bardzo zwarty i uproszczony. Wszelkie usugi </p> <p>systemowe udostpniane s w postaci wsplnego modelu zorientowanego obiektowo. W ten </p> <p>sposb ukrywane s szczegy i koncepcje uyte w bibliotekach systemu. Znajomo tych </p> <p>interfejsw jest wymagana tylko wtedy, gdy programista wiadomie chce uy</p> <p>funkcjonalnoci systemu nie zdefiniowanej w kodzie .NET. </p> <p>Kolejn cech technologii .NET, ktra miaa wpyw na jej wybr jest przenoszalno</p> <p>pomidzy platformami. Jak wspomniano wczeniej kompilacja kodu .NET do jzyka IL </p> <p>pozwala w momencie uruchomienia przeoy ten kod na instrukcje niemale dowolnego </p> <p>procesora 32 i 64-bitowego. Tym zadaniem zajmuje si specjalny Just-In-Time (JIT) </p> <p>90</p> <p>kompilator w CLR, ktry kompiluje kod poredni na instrukcje natywne danej platformy. </p> <p>Kompilacja moe mie miejsce w trakcie wykonywania aplikacji lub przed jej </p> <p>uruchomieniem. Dziki czemu programy napisane w .NET osigaj zblion wydajno do </p> <p>programw napisanych w C++. </p> <p>4. PROGRAM PETRI NET WORKSHOP</p> <p>Petri Net Workshop jest zintegrowanym rodowiskiem projektowania oraz badania sieci </p> <p>Petriego zaproponowanym przez mgra in. Bartosza Mstowskiego w [6]. rodowisko zawiera </p> <p>graficzny edytor do projektowania sieci Petriego wraz z narzdziami do analizy wasnoci </p> <p>sieci i ich wykorzystania w rnych praktycznych algorytmach. Program napisany zosta </p> <p>w zarzdzanym jzyku C++ (ang. Managed C++ Extentions), bdcym rozszerzeniem jzyka </p> <p>C++ o moliwoci nowej platformy .NET [5]. </p> <p>Program posiada rwnie funkcje dydaktyczn, prezentuje kolejne kroki dekompozycji sieci. </p> <p>Moliwa jest dokadna obserwacja i analiza kolejnych krokw tworzenia makromiejsc </p> <p>i prezentowanie studentom algorytmu dekompozycji strukturalnej na przykadach. </p> <p>Wygld gwnego okna programu przedstawiono na rys 1. Interfejs tworz 4 elementy </p> <p>(oznaczone na rysunku kolejnymi numerami): menu gwne wraz z paskiem narzdzi (1), </p> <p>okna dokumentw (2), okno wasnoci (Properties) (3) oraz okno, w ktrym generowane s</p> <p>wyniki dziaania programu oraz rne komunikaty (Log Window) (4). Interfejs programu </p> <p>zosta napisany w jzyku angielskim, aby nie zawa grona jego ewentualnych </p> <p>uytkownikw. </p> <p>Rys. 1. Wygl d graficznego interfejsu u ytkownika programu Petri Net Workshop </p> <p>91</p> <p>Program jest aplikacj implementujc MDI (Multi-Document Iterface), co pozwala na </p> <p>rwnoczesn prac nad rnymi sieciami przechowywanymi w oddzielnych dokumentach. </p> <p>Zasadniczo kademu dokumentowi przypisana jest jedna sie Petriego, ktra zawiera </p> <p>dowoln liczb podsieci. Okno dokumentu ma zakadki, z ktrych pierwsza zawiera </p> <p>makrosie najwyszego poziomu hierarchii, a pozostae zawieraj podsieci nalece do </p> <p>kolejnych makromiejsc. Na rys 2. przedstawiono dwa widoki przykadowego dokumentu, </p> <p>z sieci bdc w trakcie procesu dekompozycji. </p> <p>Rys. 2. Okna dokumentu programu Petri Net Workshop </p> <p>Jako format zapisu sieci zosta wybrany jzyk PNML. Jest on niezaleny od specyficznych </p> <p>cech rnych narzdzi i platform. Pozwala zapisa dowolny typ sieci Petriego, </p> <p>w szczeglnoci zapewnia moliwo definiowania nowych typw, co jest wane dla </p> <p>projektantw nowych systemw. PNML potrafi reprezentowa kady typ sieci wraz z jego </p> <p>specyficznymi waciwociami i rozszerzeniami. Dziki czemu nie ma potrzeby wyciga lub </p> <p>ignorowa niektrych specyficznych informacji w czasie konwersji z modelu uywanego </p> <p>przez okrelone narzdzie do formatu PNML. </p> <p>5. NOWOCZESNA IMPLEMENTACJA</p> <p>Wybr platformy .NET, w prezentowanej implementacji, zosta spowodowany zaletami CLR, </p> <p>jednak kluczowe znaczenie przy jej wyborze miay inne technologie dostarczane wraz </p> <p>z platform .NET Framework: </p> <p> Managed C++ Extensions - bdc rozszerzeniem moliwoci jzyka C++, </p> <p> Base Class Library - bdc bibliotek setek gotowych do uycia klas, </p> <p> Windows Forms - zbir klas .NET opakowujcych wikszo funkcji Windows API pozwalajcych szybko tworzy aplikacje okienkowe, </p> <p> System.XML Parser narzdzie, ktre umoliwio implementacj zapisu i odczytu sieci Petriego w formacie PNML. </p> <p>92</p> <p>Nowoczesno implementacji polega na wykorzystaniu programowania zorientowanego </p> <p>obiektowo w rodowisku .NET. rodowisko to umoliwia wykorzystanie powstaych klas </p> <p>w innych jzykach wspieranych przez t technologi. Moliwe zatem jest wykorzystanie </p> <p>zaprojektowanego rodowiska, jak i zaimplementowanego algorytmu przez innych </p> <p>programistw.</p> <p>Dodatkowym atutem aplikacji jest wykorzystanie jzyka PNML jako formatu zapisu sieci. </p> <p>Format umoliwia wymian zaprojektowanych sieci z innymi programami do analizy </p> <p>i symulacji sieci Petriego tj. CPN Tools i inne [7]. </p> <p>Struktura klas zostaa szczegowo przemylana pod ktem najprostszej implementacji </p> <p>i pniejszego rozszerzania moliwoci aplikacji. Jest ona elastyczna i otwarta. </p> <p>Zaprojektowane klasy umoliwiaj graficzn reprezentacj sieci, jak rwnie s</p> <p>wykorzystywane do implementacji prezentowanego algorytmu. </p> <p>Klasa PetriNet jest gwn i najbardziej rozbudowan klas w programie (Rys. 3). Udostpnia</p> <p>ona wszelkie metody operowania na strukturze sieci: dodawanie usuwanie, pobieranie </p> <p>referencji do konkretnych jej elementw, a take metod ToMacroNet(), ktra inicjuje proces </p> <p>dekompozycji sieci. Poza tym zawiera metody pozwalajce na klasyfikacj sieci, ktre mog</p> <p>by pomocne w algorytmach, w ktrych istotn rol odgrywaj wasnoci sieci. </p> <p>Kolejn kluczow klas bdc wynikiem pracy autora jest PlaceEncoding, ktra zawiera </p> <p>zbir funkcji zwizanych z kodowaniem sieci zdekomponowanej. Poniewa gwnymi </p> <p>strukturami, na ktrych opiera si algorytm kodowania s macierze, wykorzystuje ona klas</p> <p>Matrix do enkapsulacji danych macierzy i wszelkich potrzebnych na nich operacji (rys 3).</p> <p>Klasy umoliwiajce graficzn prezentacje sieci i klasy przechowujce struktury listowe </p> <p>z powodu ograniczonego miejsca nie zostay przedstawione w niniejszym referacie, wicej </p> <p>informacji znajduje si w [6]. </p> <p>Rys. 3. Diagram klas PetriNet, PlaceEncoding oraz klas tworz cych struktur drzewa znakowa</p> <p>93</p> <p>6. WNIOSKI I KIERUNKI DALSZYCH PRAC</p> <p>Technologia .NET umoliwia znacznie efektywniejsz realizacj algorytmu kodowania </p> <p>miejsc w porwnaniu ze rodkami programistycznymi dostpnymi w czasie opracowania jego </p> <p>pierwszej wersji [1]. </p> <p>Zaprezentowana aplikacja umoliwia atwe projektowanie i kodowanie stanw lokalnych </p> <p>w automatach wspbienych opisanych interpretowanymi sieci Petriego. Posiada rwnie</p> <p>funkcje dydaktyczn umoliwia prezentacje kolejnych krokw dekompozycji sieci. </p> <p>Struktura zaprojektowanych klas jest otwarta i elastyczna. Umoliwia to atwe i szybkie </p> <p>tworzenie nowych moduw na bazie istniejcego kodu. Program stanowi baz do rozwoju </p> <p>zintegrowanej aplikacji umoliwiajcej analiz, kodowanie a w przyszoci syntez</p> <p>sterownikw cyfrowych opisanych i...</p>