PYTANIA NA EGZAMIN DYPLOMOWY, STUDIA II STOPNIA MAGISTERSKIE,
KIERUNEK INFORMATYKA, SPECJALNOŚĆ PROJEKTOWANIE SYSTEMÓW
INFORMATYCZNYCH I SIECI KOMPUTEROWYCH
(obowiązuje od roku akademickiego 2007/08 włącznie)
1. Komunikacja grupowa.
Komunikację grupową definiuje się jako mechanizm umożliwiający procesom systemu roz-
proszonego organizowanie się w sposób dynamiczny w grupy i niezawodną wymianę wiado-
mości w ramach grupy. Za każdy z tych dwóch aspektów odpowiada odrębny mechanizm:
usługa członkostwa zajmuje się zarządzaniem składem grupy (dynamiczne dołączanie i
odłączanie procesów z grupy), a usługa rozsyłania dostarcza mechanizmu rozgłaszania wia-
domości pomiędzy procesami w grupie zgodnie z przyjętym poziomem niezawodności.
Systemy komunikacji grupowej GCS powszechnie wykorzystuje się w aplikacjach, które po-
trzebują skorzystać na niższym poziomie z mechanizmów łączenia procesów w grupy oraz
niezawodnej komunikacji pomiędzy procesami w grupie. Wśród przykładowych zastosowań
można wymienić: systemy konferencyjne, gry sieciowe czy systemy o podwyższonej nieza-
wodności.
Grupa to rzeczywisty zbiór procesów, uczestniczących w danej chwili we wspólnym prze-
twarzaniu i komunikujących się poprzez przekazywanie wiadomości. Obraz grupy to z kolei
stan grupy widziany w danej chwili czasu rzeczywistego w procesie.
Z punktu widzenia aplikacji nie rozróżnia się awarii procesu od jawnego opuszczenia przez
niego grupy.
MODEL MATEMATYCZNY
W definicjach specyfikacji komunikacji grupowej występują następujące zbiory:
" P  zbiór procesów w systemie,
" M  zbiór wiadomości przesyłanych w systemie,
" VID  zbiór identyfikatorów obrazów grup.
Wyróżnia się następujące elementarne zdarzenia w systemie:
" wyślij(p,m)  proces p wysyła wiadomość m do całej grupy,
" odbierz(p,m)  proces p odbiera wiadomość m
" zmiana_obrazu(p, )  w procesie p następuje zmiana obrazu; nowy
obraz o identyfikatorze id zawiera procesy określone zmienną członkowie. Sam obraz
zaś jest parą obejmującą globalny identyfikator obrazu i należące do niego procesy.
Dwa obrazy V i V są równe gdy równe są ich identyfikatory oraz zbiory procesów.
" awaria(p)  proces p ulega awarii
" powrót(p)  proces p wznawia działanie po awarii
ARCHITEKTURA SYSTEMU
Oprogramowanie realizujące komunikację grupową stanowi warstwę usługową dla aplikacji,
stąd znajduje się poniżej aplikacji. Wejściowe zdarzenie wyślij zachodzi z inicjatywy aplika-
cji, zgłaszającej wysłanie wiadomości do grupy. Wyjściowe zdarzenia odbierz i zmia-
na_obrazu są natomiast zgłaszane przez warstwę komunikacji grupowej. Wejściowe zdarze-
nia awaria i powrót zgłasza detektor uszkodzeń, którego istnienie i poprawne działanie jest
założone.
Warstwa komunikacji grupowej jest zazwyczaj złożona z wielu podwarstw, realizujących
takie funkcje, jak np. zarządzanie grupami (membership), rozsyłanie (multicast), funkcje
wznawiania pracy procesu po awarii, uzgadnianie i inne. Na styku z aplikacjÄ… dostarcza jed-
1
nak przejrzystego interfejsu, dzięki czemu projekt i implementacja aplikacji są znacząco
uproszczone.
2. Synchronizacja zegarów.
Układ odmierzający czas jest standardowym wyposażeniem większości dzisiejszych kompu-
terów. Od jego prawidłowego działania zależy często bardzo wiele innych elementów całego
systemu komputerowego. Dopóki zegar jest używany lokalnie na jednej maszynie kwestia
jego niedokładności nie jest aż taka istotna. Procesy korzystają w tym wypadku z jednego
zegara, a więc w ramach danej maszyny jego wskazania będą spójne. Problem pojawia się
gdy dostępnych mamy kilka maszyn, z których każda posiada swój własny zegar. Ponieważ
fizyczne zegary nie są idealne i ich częstotliwości będą się w jakimś stopniu różniły, po pew-
nym czasie zaczną wskazywać różne wartości. Innymi słowy pojawią się tzw. odchylenia
wskazań zegara (ang. clock skew). W takim przypadku założenie, że zegary fizyczne w da-
nym momencie wskazują identyczny czas jest obarczone pewnym błędem.
W przypadku synchronizacji zegarów możemy wyróżnić różne cele. Jednym z nich może być
potrzeba zsynchronizowania grupy maszyn z jednÄ… dedykowanÄ… stacjÄ…. Potrzeba synchroniza-
cji może zaistnieć również, gdy nie ma wyróżnionej pewnej stacji pomiarowej, ale musimy
skoordynować działanie grupy maszyn. Do rozwiązania tych problemów istnieje wiele algo-
rytmów.
ALGORYTM CRISTIANA
Algorytm ten jest przeznaczony głównie dla środowisk rozproszonych w których jeden z wę-
złów jest serwerem czasu. W algorytmie tym zakłada się, że każda maszyna co pewien okre-
ślony czas wysyła do serwera czasu zapytanie o podanie aktualnego czasu. Po otrzymaniu
tego zapytania, serwer odpowiada prędko jak tylko może i przesyła aktualny czas UTC.
Nadawca z kolei, po otrzymaniu informacji o czasie od serwera, zanim ustawi wartość swoje-
go zegara, musi uwzględnić parę kwestii. Mianowicie, zwykłe przepisanie czasu nadesłanego
z serwera, mogłoby spowodować, że czas płynie wstecz. Może się tak zdarzyć jeżeli zegar
nadawcy wymierza czas zbyt szybko. Opcja prostego przepisania czasu więc odpada. Poza
tym istnieje pewien koszt w postaci czasu komunikacji. Taki koszt powoduje oczywiście, że
wartość czasu UTC wysłana przez serwer jest nieaktualna po nadejściu do nadawcy zapyta-
nia. Aby rozwiązać ten problem nadawca może np. zapamiętać przedział czasowy zawarty
pomiędzy momentem T0, w którym wysłano zapytanie do serwera i momentem T1, kiedy
przyszła odpowiedz
z serwera. W najprostszym przypadku przyjmuje się, że połowa tego
przedziału jest czasem komunikacji od serwera do klienta ((T1-T0)/2). Jeśli dodatkowo zna-
my czas (T2) przetwarzania zapytania przez serwer, możemy poprawić oszacowanie czasu
przez nadawcę i jako czas przesyłania komunikatu bierzemy wtedy połowę wartości (T1-T0-
T2).
W przypadku, gdy wiemy, że czas przesyłania komunikatu może się różnić przy każdym
przesłaniu wiadomości z i do serwera, zaproponowano wykonywanie kilku pomiarów i od-
powiednie ich uśrednianie.
ALGORYTM Z BERKELEY
W przeciwieństwie do algorytmu Cristiana w przypadku algorytmu z Berkeley serwer czasu
jest aktywny i co pewien okres czasu wypytuje każdą maszynę o jej aktualny czas. Po zebra-
niu odpowiedzi od grupy maszyn serwer uśrednia ich czasy. Na podstawie takiej wyliczonej
wartości czasu, serwer każe odpowiednim maszynom ustawić nową wartość czasu lub zwol-
nić działanie do chwili kiedy osiągną odpowiednią wartość.
2
Takie podejście do synchronizacji zegarów fizycznych może być użyte m.in. w systemie, w
którym nie ma specjalnych serwerów czasu, a jedynie chodzi o wspólne ustalenie jednej pod-
stawy czasu.
ALGORYTM UÅšREDNIANIA
Algorytm uśredniania jest algorytmem zdecentralizowanym. W podejściu tym czas dzieli się
na przedziały o określonym i stałym rozmiarze. Na początku każdego przedziału następuje
resynchronizacja wszystkich zegarów. Polega to na tym, że każda maszyna rozgłasza wtedy
aktualny czas swojego zegara. W momencie wysłania maszyna uruchamia lokalny czasomierz
i rozpoczyna zbieranie komunikatów od innych maszyn. Komunikaty rozgłoszeniowe mogą
przychodzić w różnych chwilach od różnych nadawców. Gdy zostaną zebrane wszystkie od-
powiedzi obliczania jest na ich podstawie nowa wartość czasu. W najprostszym przypadku
wykorzystuje się uśrednianie. W zmodyfikowanej wersji odrzuca się dodatkowo przed uśred-
nianiem skrajne wartości, aby nie zaburzały zbytnio wyniku. W jeszcze bardziej rozbudowa-
nej wersji są brane pod uwagę m.in. czasy przesyłania komunikatów.
3. Tryb iteracyjny i rekurencyjny w systemach nazewni­
czych.
Rozproszenie przestrzeni nazw na wiele serwerów przekłada się bezpośrednio na sposób re-
alizacji procesu tłumaczenia nazw, który musi angażować wiele serwerów. Tłumaczenie nazw
w systemie DNS może być realizowane na dwa sposoby: iteracyjnie lub rekurencyjnie.
TÅ‚umaczenie nazw realizowane jest przez oprogramowanie klienta zwane analizatorem
nazw. Tłumaczenie iteracyjne kontrolowane jest w całym zakresie przez klienta. Rozpoczyna
się ono od wysłania zapytania o nazwę do serwera domeny głównej. Załóżmy, że realizujemy
tłumaczenie nazwy galio.put.poznan.pl. Serwer domeny głównej nie zna odpowiedzi na to
pytanie i nie może dokonać pełnego przetłumaczenia tej nazwy na adres, ale wie jaki serwer
jest odpowiedzialny za domenę pl, która występuje na końcu tłumaczonej nazwy. W odpo-
wiedzi serwer domeny głównej wysyła adres serwera domeny pl. Klient uzyskując tą infor-
mację, wysyła kolejne zapytanie, tym razem do serwera domeny pl, próbując przetłumaczyć
pozostałą część poszukiwanej nazwy, a więc galio.put.poznan. Serwer nazw domeny pl od-
powiada wskazujÄ…c na serwer nazw domeny poznan.pl. Ostatecznie pytanie trafia do serwera
nazw domeny put.poznan.pl, gdzie przechowywane sÄ… dane o komputerach znajdujÄ…cych siÄ™
w tej domenie, a więc m.in. o komputerze galio. Klient uzyskuje w ten sposób adres odpo-
wiadajÄ…cy nazwie galio.put.poznan.pl.
Zakłada się, że klient zna adres serwera domeny głównej. W praktyce lista tych serwerów nie
jest zbyt obszerna i jest aktualizowana stosunkowo rzadko, więc jej utrzymywanie nie jest
problematyczne.
Rekurencyjne tłumaczenie nazw polega na zleceniu translacji nazwy pojedynczemu serwero-
wi. Serwer domeny głównej nie znając odpowiedzi na pytanie przekazuje je dalej, nie odsyła-
jąc odpowiedzi od razu klientowi. Zapytanie przekazywane jest do serwera, który powinien
znać odpowiedz
lub takiego, który będzie w stanie przeprowadzić dalszy proces tłumaczenia
nazwy. W analogicznym do powyższego przykładzie, serwer domeny głównej przekazuje
zapytanie do serwera domeny pl, ten do serwera domeny poznan.pl, a ten w końcu do serwera
domeny put.poznan.pl, gdzie następuje ostateczne przetłumaczenie nazwy na adres. Odpo-
wiedz
wraca tÄ… samÄ… drogÄ…, ale w przeciwnym kierunku.
Z punktu widzenia klienta, odpowiedz
zawsze nadchodzi z serwera, który został odpytany, co
jest wygodne, gdyż upraszcza oprogramowanie klienta. Wadą tego podejścia jest większe
zaangażowanie poszczególnych serwerów w proces tłumaczenia nazw, co pociąga za sobą ich
większe obciążenie. W praktyce więc serwery domeny głównej nie realizują zapytań rekuren-
3
cyjnych. Inną zaletą odpytywania rekurencyjnego jest oszczędność komunikacji. Odpytywa-
nie odległych geograficznie serwerów nazw w trybie iteracyjnym pociąga za sobą koniecz-
ność przesyłania komunikatów na duże odległości. W trybie rekurencyjnym informacja prze-
kazywana jest na mniejsze odległości.
Przesyłanie odpowiedzi wykorzystywane jest do wypełniania pamięci podręcznych poszcze-
gólnych serwerów. Przykładowo serwer domeny pl po wykonaniu powyższego zapytania
uzyskuje informację o adresie serwera nazw dla domeny put.poznan.pl, którą to informacje
może wykorzystać w przyszłości dla zoptymalizowania następnego pytania o inny komputer z
tej domeny. W ten sposób postępuje proces uczenia się serwerów, w którym dzięki przecho-
wywaniu podręcznemu serwery są w stanie bezpośrednio odpowiedzieć na najczęściej zada-
wane pytania.
W praktyce zapytania zgłaszane przez klientów nie są wysyłane bezpośrednio do serwera
domeny głównej, ale do lokalnego serwera nazw, którego głównym zadaniem jest pośredni-
czenie w tłumaczeniu nazw. Serwer taki ma za zadanie odpytywanie innych serwerów w celu
uzyskania odpowiedzi i następnie przechowuje podręcznie uzyskane wyniki. Ponieważ taki
serwer znajduje się blisko klienta, dostęp do niego jest bardzo szybki. Po pewnym czasie ser-
wer taki zna również odpowiedzi na dużą część pytań klientów lub przynajmniej zna serwery
nazw głównych domen, co pozwoli w przyszłości szybko uzyskać właściwą odpowiedz
. Z
drugiej strony uruchomienie lokalnego serwera zwalnia analizator nazw klienta z konieczno-
ści przechowywania listy adresów serwerów nazw domeny głównej. Wystarczy w celu od-
wzorowania nazwy posłużyć się adresem lokalnego serwera nazw.
4. Lokalizacja jednostek ruchomych.
Tradycyjne systemy nazewnicze nie nadają się do zarządzania często zmieniającą się infor-
macją. Sytuacja taka występuje w przypadku realizacji odwzorowań jednostek mobilnych,
zmieniajÄ…cych swoje adresy.
Tradycyjne usługi nazewnicze dokonują odwzorowania nazwy bezpośrednio na adres. Każda
zmiana adresu wymusza automatycznie konieczność zmiany odwzorowania nazwa-adres.
Lepszym rozwiązaniem jest wprowadzenie identyfikatorów jednostek. Identyfikatory nigdy
się nie zmieniają i nie mogą być użyte ponownie do identyfikacji innych jednostek. Identyfi-
katory nie muszą mieć postaci wygodnej do użycia dla człowieka; z reguły mają postać binar-
nÄ….
Usługi nazewnicze zwracają identyfikator jednostki. Ponieważ identyfikator nigdy się nie
zmienia można go lokalnie zapamiętać i dowolnie długo przechowywać. Nazwa danej jed-
nostki może się w przyszłości zmienić, ale to nie wymaga ponownego odpytywania usługi
nazewniczej, ponieważ znany jest już identyfikator poszukiwanej jednostki. Odwołanie się do
jednostki wymaga jednak jej zlokalizowania i jest to zadanie usługi lokalizacji. Usługa loka-
lizacji dokonuje odwzorowania identyfikatora jednostki na adres (lub zbiór adresów).
LOKALIZACJA  PROSTE ROZWI
ZANIA
Lokalizację jednostek można przeprowadzić z wykorzystaniem rozgłaszania, o ile warstwa
komunikacyjna umożliwia wykonywanie takiej operacji. Rozgłoszona wiadomość dociera do
wszystkich jednostek, a odpowiada tylko ta, która spełnia określone w rozgłoszeniu warunki.
Rozgłaszanie staje się nieefektywne w przypadku dużych sieci, ponieważ angażuje wszystkie
komputery i blokuje na pewien czas możliwość komunikacji wszystkich komputerów. Pew-
nym rozwiązaniem tego problemu jest zastosowanie częściowego rozgłaszania czyli rozsyła-
nia. Rozesłanie wiadomości oznacza wysłanie jej do określonej grupy odbiorców. Istnieją
protokoły w sieci Internet umożliwiające rozsyłanie wiadomości w skali całego globu.
Mechanizm ten można wykorzystać do lokalizacji komputerów firmowych, które dołączając
się do sieci uzyskują dynamicznie adresy IP. Każdy z komputerów po uzyskaniu dostępu do
4
sieci może dołączyć się do odpowiedniej grupy rozgłoszeniowej, co umożliwi póz
niejsze wy-
słanie do tej grupy pytania lokalizacyjnego.
Mechanizm rozgłaszania/rozsyłania można wykorzystać również do lokalizacji najbliższej
kopii danych. Odpowiedz
na komunikat rozgłoszeniowy wysyłana będzie w tym przypadku
przez wiele serwerów, ale istotna będzie kolejność odbioru tych wiadomości. Można założyć,
że komputer który odpowie jako pierwszy jest najbliższy.
Innym prostym rozwiÄ…zaniem problemu lokalizacji sÄ… wskaz
niki naprowadzajÄ…ce. Mecha-
nizm ten polega na pozostawianiu w starej lokalizacji. Poszukiwanie jednostki sprowadza siÄ™
wtedy do przejścia całego łańcucha wskaz
ników, aż dotrze się do właściwej jednostki. Roz-
wiÄ…zanie to jest bardzo proste koncepcyjnie i realizacyjnie ale ma kilka wad. A
ańcuch wskaz
-
ników może się bardzo wydłużyć, co spowoduje nieakceptowane wydłużenie czasu oczeki-
wania na odpowiedz
. Inna wada to konieczność przechowywania wskaz
ników w poszczegól-
nych węzłach przez cały czas funkcjonowania systemu. W końcu rozwiązanie to może, w
przypadku utraty któregoś ze wskaz
ników, doprowadzić do nieosiągalności jednostki.
LOKALIZACJA OPARTA NA SIEDZIBIE
Metoda lokalizacji oparta na wskaz
nikach naprowadzających może doprowadzić do niedo-
stępności zasobu jeżeli któryś ze wskaz
ników na ścieżce przestanie być dostępny. W takich
sytuacjach można się wspierać (jako metodą awaryjną) wprowadzeniem siedziby (stanowiska
macierzystego) dla każdej jednostki. Jest to miejsce, pod którym zawsze można uzyskać in-
formacjÄ™ o aktualnej lokalizacji jednostki.
Rozwiązanie oparte na siedzibie zastosowano w systemie Mobile IP umożliwiającym komu-
nikację z przemieszczającymi się komputerami. Dla każdego mobilnego komputera przewi-
dziano program komunikacyjny (agent siedziby), dostępny zawsze pod tym samym adresem
IP. Klient komunikuje się najpierw z agentem, próbując uzyskać aktualny adres serwera.
Agent odpowiada wysyłając adres serwera. Dalsza komunikacja odbywa się już bezpośrednio
pomiędzy klientem a serwerem. Wadą tego rozwiązania w przypadku stosowania w sieciach
na szeroką skalę jest konieczność przeprowadzenia dodatkowej wymiany komunikatów z
siedzibą, która może być zlokalizowana w zupełnie innym miejscu niż właściwy serwer.
Inną wadą metody opartej na siedzibie jest konieczność zapewnienia niezmiennej lokalizacji
siedziby i ciągłość jej istnienia. Brak dostępu do siedziby pociąga bowiem za sobą brak do-
stępu do docelowego komputera. Trwała zmiana lokalizacji komputera nadal wymaga utrzy-
mywania siedziby, być może w odległym miejscu. Pewnym rozwiązaniem jest tu zastosowa-
nie tradycyjnej usługi nazewniczej do lokalizacji siedziby. Ponieważ lokalizacja siedziby
rzadko ulega zmianie, klienci mogą sobie tą informację przechowywać podręcznie, nie tracąc
na wydajności.
5. Spójność i zwielokrotnianie.
Zwielokrotnianie (replikacja) jest bardzo ważnym mechanizmem stosowanym w systemach
rozproszonych. Polega ono na utrzymywaniu wielu kopii tych samych danych lub obiektów
na wielu, niezależnych serwerach. Podstawową motywacją dla stosowania zwielokrotniania
jest potencjalne zwiększenie efektywności oraz niezawodności przetwarzania. Osiągnięcie
tych celów wymaga jednak rozwiązania wielu problemów, wśród których najważniejszym
jest kwestia spójności danych. Modyfikacje wprowadzone są bowiem do pojedynczej kopii, a
użytkownicy odwołują się do wszystkich, co może spowodować obserwowanie niespójności i
w konsekwencji błędy w aplikacjach. Zdefiniowano wiele modeli spójności, szczególnie w
ramach prac nad rozproszoną pamięcią współdzieloną. Modele te jednak często słabo się ska-
lują, co powoduje, że trzeba dążyć do ich uproszczenia lub osłabienia, dając tym samym szan-
sę na efektywniejszą implementację. Oddzielną kwestią jest mobilność uczestników przetwa-
5
rzania, która dodaje nowy wymiar do problemu zarządzania spójnością. Istnieje klasa modeli
spójności uwzględniająca ten aspekt z punktu widzenia pojedynczego klienta.
Zwielokrotnianie może być wykorzystane do zwiększenia niezawodności systemu rozpro-
szonego. Serwer, który ulega awarii może być zastąpiony innym, który jest dostępny, a który
przechowuje te same dane. Co więcej, zmiana serwera w przypadku awarii może się dokony-
wać w sposób całkowicie przezroczysty dla użytkownika. Repliki można też wykorzystywać
do maskowania błędów poprzednich zapisów. Mając 3 kopie i odczytując z nich wszystkich,
można stwierdzić różnice i maskować błąd jednego serwera.
Zwiększanie efektywności przetwarzania może być rozpatrywane w dwóch kontekstach. Przy
wzrastającej liczbie żądań pojedynczy serwer może być niewystarczający. Należy w takiej
sytuacji system skalować w sensie liczbowym, wprowadzając serwery-repliki. Umożliwi to
współbieżne wykorzystanie mocy obliczeniowych tych jednostek przez wielu klientów.
Oczywiście należy zadbać, aby w miarę możliwości obciążenie serwerów było równomierne.
Z drugiej strony systemy rozproszone mogą wymagać skalowania w sensie geograficznym, co
może zaowocować zbliżeniem się serwerów do użytkowników końcowych. W efekcie będą
oni obserwować mniejsze opóz
nienia komunikacyjne. Trzeba jednak pamiętać, że serwery
muszą utrzymywać dane w stanie spójnym. Jeżeli są odległe od siebie, to koszty komunikacji
związanej z synchronizacją danych będą odpowiednio wyższe, a w skrajnym przypadku mogą
przekraczać zyski z lokalizacji bliżej klienta.
Skalowalność w dużej mierze sprowadza się do konieczności zapewnienia satysfakcjonującej
efektywności przetwarzania przy wzrastającej liczbie jego uczestników. Zastosowanie zwie-
lokrotniania może wspomóc osiąganie skalowalności poprzez umieszczenie kopii w pobliżu
użytkowników końcowych, co skraca czas dostępu do danych. Z drugiej jednak strony nowe
kopie danych muszą być aktualizowane tak, aby uniknąć problemu spójności. Oznacza to, że
trzeba ponieść koszty związane z dodatkową komunikacją pomiędzy poszczególnymi serwe-
rami utrzymującymi repliki. Co więcej komunikacja ta musi być zsynchronizowana, co stawia
jeszcze większe wymagania odnośnie przepustowości. Okazuje się więc, że zwielokrotnianie
daje zyski jedynie potencjalnie. Faktyczne zwiększenie efektywności jest możliwe przy sta-
rannym opracowaniu protokołów spójności, uwzględniającym charakter i faktyczne wymaga-
nia aplikacji.
Zwielokrotnianie powoduje powstawanie problemu lokalizacji danych. W typowym systemie
lokalizacja poszczególnych replik obiektów może ulegać zmianie; w każdej chwili mogą być
utworzone nowe repliki na żądanie, a repliki zbędne mogą być usunięte. Utworzenie kopii
danych i usunięcie oryginału to w istocie jest relokacja.
Problemem specyficznym dla zwielokrotniania jest również spójność danych. Istnienie wielu
kopii jest korzystne z punktu widzenia procesów czytających, ale staje się sporym problemem
dla systemu, gdy zachodzi konieczność aktualizacji tych wszystkich replik.
PROTOKÓA
KOHERENCJI
Protokół koherencji (spójności) jest algorytmem rozproszonym realizującym określony model
spójności, a więc dostarczającym użytkownikom gwarancji odnośnie uporządkowania opera-
cji modyfikujących, które są zgłaszane w systemie. Operacje odczytu nie powodują powsta-
wania problemu spójności danych. Operacje zapisu modyfikują pojedynczą kopię i muszą być
przesłane do pozostałych węzłów. Generalnie istnieją dwa podstawowe podejścia do zapew-
niania spójności: unieważnianie i aktualizacja.
Unieważnianie polega na zmianie statusu zdalnych kopii danych tak, aby nie mogły już być
wykorzystywane, co efektywnie może być traktowane jako usunięcie repliki. Zaletą unieważ-
niania jest brak konieczności dalszej komunikacji z serwerem w przypadku wprowadzania
następnych modyfikacji  kopia przestała bowiem już istnieć. Unika się w ten sposób również
przesyłania aktualizacji, które być może nigdy nie zostałyby wykorzystane (odczytane) przez
6
innych użytkowników, co powodowałoby jedynie zwiększenie obciążenia komunikacyjnego
w systemie. Wadą natomiast jest konieczność wysłania następnego komunikatu z aktualną
kopią danych, jeżeli dane te faktycznie są jednak potrzebne.
Drugim podejściem stosowanym w protokołach koherencji jest aktualizacja. Polega ona na
każdorazowym przesyłaniu komunikatu aktualizującego stan repliki. Komunikat taki może
zawierać całość zaktualizowanego stanu obiektu lub jedynie zmianę względem poprzedniej
wersji. Komunikaty muszą być wysyłane praktycznie po każdej aktualizacji, chyba że z wła-
sności modelu wynika, że dane te nie będą wykorzystywane, co pozwala na zgrupowanie kil-
ku aktualizacji w jednym komunikacie. Zaletą tego rozwiązania jest natychmiastowa dostęp-
ność zaktualizowanych replik w poszczególnych węzłach. Może się jednak zdarzyć, że aktu-
alizacje te nie będą w ogóle odczytywane.
6. Wykluczanie, a sterowane współbieżnością.
Wzajemne wykluczanie wywodzi się ze sposobu programowania systemów z wieloma proce-
sami. Do tego celu wykorzystuje się sekcje krytyczne, które na czas wykonywania operacji na
pewnych zasobach, zapewniajÄ… procesom wzajemne wykluczanie. Gdy proces wchodzi do
sekcji krytycznej, może mieć pewność, że jakiś inny proces nie wejdzie do niej w tym samym
czasie.
PODEJÅšCIE SCENTRALIZOWANE
Spośród dostępnych procesów jeden wybierany jest jako koordynator. Kiedykolwiek proces
chce wejść do sekcji krytycznej wysyła informację z żądaniem do koordynatora, określając do
której sekcji krytycznej chce wejść i pytając zarazem o pozwolenie. Jeżeli w danej chwili ża-
den z procesów nie jest w tej sekcji krytycznej, koordynator odsyła odpowiedz
udzielajÄ…cÄ…
pozwolenia. Kiedy odpowiedz
dotrze, proces, który ubiegał się o wejście do sekcji krytycznej,
uruchamia ją. Natomiast gdy inny proces zapyta o pozwolenie na wejście do tej samej sekcji
krytycznej, koordynator po prostu wstrzymuje się z odpowiedzią, blokując w ten sposób pro-
ces, który czeka na odpowiedz
.
Algorytm ten posiada kilka istotnych własności.
Jest sprawiedliwy, w tym sensie, że procesy są obsługiwane zgodnie z kolejnością żądań. Do-
datkowo każdy z procesów w końcu, będzie mógł uruchomić swoją sekcję krytyczną. Innymi
słowy algorytm nie powoduje zagłodzenia. Jest prosty w implementacji. Proces wejścia do
sekcji krytycznej wymaga tylko trzech wiadomości.
Wadą algorytmu jest scentralizowany koordynator, który może ulec awarii.
ALGORYTM LAMPORTA
Jako Ri oznaczmy zbiór żądań procesu Pi, tzn. zbiór procesów, od których Pi wymaga po-
zwolenia, kiedy chce się dostać do sekcji krytycznej. W algorytmie Lamporta zbiór żądań
każdego procesu jest zbiorem wszystkich innych procesów. Każdy proces Pi utrzymuje kolej-
kę kolejka_żądań(i), która zawiera żądania wejścia do sekcji krytycznej uszeregowane według
ich znaczników czasowych. Algorytm ten wymaga, aby wiadomości dostarczane były pomię-
dzy każdą parą procesów w kolejności FIFO.
Gdy proces Pi zamierza wejść do sekcji krytycznej, wysyła wiadomość z żądaniem do
wszystkich procesów, które znajdują się wewnątrz jego zbioru żądań Ri. Następnie umieszcza
żądanie w swojej kolejce żądań (ts(i) jest znacznikiem czasowym żądania procesu Pi). Gdy
proces Pj otrzyma żądanie od procesu Pi, odsyła ODPOWIEDy
oznaczonÄ… znacznikiem cza-
sowym do procesu Pi i umieszcza żądanie procesu Pi w swojej kolejce żądań. Proces Pi roz-
poczyna wykonywanie sekcji krytycznej, gdy spełnione są dwa następujące warunki: 1) pro-
ces Pi otrzymał wiadomość ze znacznikiem czasowym większym niż (ts(i), (i)) od wszystkich
innych procesów oraz 2) żądanie procesu Pi jest na początku jego własnej kolejki żądań.
7
Po wyjściu z sekcji krytycznej proces Pi usuwa żądanie ze swojej kolejki żądań i wysyła wia-
domość ZWOLNIJ oznaczoną znacznikiem czasowym do wszystkich procesów, znajdujących
się w jego zbiorze żądań. Jeżeli proces Pj otrzyma wiadomość zwolnij od procesu Pi, usuwa
żądanie Pi ze swojej kolejki żądań.
Kiedy proces usuwa pewne żądanie ze swojej kolejki żądań, jego własne żądanie może poja-
wić się na początku kolejki, umożliwiając mu wejście do sekcji krytycznej. Algorytm wyko-
nuje żądania wejścia do sekcji krytycznej w rosnącym porządku i zgodnie z ich znacznikami
czasowymi.
ALGORYTM RICARTA I AGRAWALI
Algorytm Ricarta i Agrawali jest zoptymalizowaną wersją algorytmu Lamporta, która obywa
się bez wiadomości ZWOLNIJ poprzez sprytne połączenie ich z wiadomościami typu OD-
POWIEDy
.
Gdy proces Pi chce wejść do sekcji krytycznej, wysyła wiadomość z żądaniem oznaczoną
znacznikiem czasowym do wszystkich procesów, które znajdują się w jego zbiorze żądań. W
momencie gdy proces Pj otrzyma żądanie od procesu Pi, wysyła odpowiedz
do procesu Pi
pod warunkiem, że nie zachodzi jedna z następujących sytuacji: 1) proces Pj wykonuje sekcję
krytyczną, 2) proces Pj żąda wykonania sekcji krytycznej, a znacznik czasowy jego żądania
jest mniejszy niż znacznik czasowy żądania procesu Pi. Jeżeli zachodzi któraś z tych dwóch
sytuacji, żądanie procesu Pi jest odkładane i trafia do kolejki żądań w procesie Pj.
Proces Pi wchodzi do sekcji krytycznej po otrzymaniu wiadomości ODPOWIEDy
od wszyst-
kich procesów, które są w jego zbiorze Ri. W chwili kiedy proces Pi kończy wykonywanie
sekcji krytycznej wysyła odpowiedzi na wszystkie odłożone wcześniej żądania, a następnie
usuwa je z kolejki.
Odpowiedzi za żądania procesu blokowane są tylko przez procesy, które ubiegają się o wej-
ście do sekcji krytycznej i mają wyższy priorytet tzn. mniejszy znacznik czasowy. W ten spo-
sób, gdy proces odsyła wiadomość typu odpowiedz
na wszystkie odroczone żądania, proces,
który ma kolejny najwyższy priorytet żądania, otrzymuje ostatnią niezbędną odpowiedz
i
wchodzi do sekcji krytycznej. Innymi słowy sekcje krytyczne w algorytmie Ricarta i Agrawa-
li wykonywane są w kolejności zgodnej z wartościami znaczników czasowych ich żądań.
ALGORYTM MAEKAWY
Algorytm Maekawy różni się od typowych algorytmów wzajemnego wykluczania. Świadczą
o tym głównie dwie jego własności.
Po pierwsze proces, który chce wejść do sekcji krytycznej, nie żąda pozwolenia od wszyst-
kich procesów, ale tylko od pewnego ich podzbioru. Jest to znacząco różne podejście w sto-
sunku do algorytmu Lamporta i algorytmu Ricarta i Agrawali, gdzie wszystkie procesy
uczestniczą w rozwiązywaniu konfliktu. W algorytmie Maekawy zbiory procesów, do których
wysyłane są żądania, wybierane są w taki sposób, aby iloczyn dowolnych dwóch różnych
zbiorów był zbiorem niepustym. W rezultacie tego każda para procesów posiada proces, który
pośredniczy między nimi w rozwiązywaniu ewentualnych konfliktów.
Po drugie w algorytmie Maekawy dowolny proces może wysłać naraz tylko jedną odpowiedz
.
Ponadto procesowi wolno wysłać odpowiedz
tylko po otrzymaniu wiadomości typu ZWOL-
NIJ, która dotyczy poprzedniej wiadomości ODPOWIEDy
. Z tego powodu proces Pi, zanim
wejdzie do sekcji krytycznej, blokuje wszystkie pozostałe procesy, które razem z nim należą
do pewnego podzbioru procesów oznaczonego przez Ri (zwanego dalej również podzbiorem
żądań procesu Pi).
W pierwszym kroku algorytmu Maekawy proces Pi, który ubiega się o wejście do sekcji kry-
tycznej, rozsyła Ż
DANIE(i) do wszystkich procesów, od których wymaga pozwolenia (pro-
cesy ze zbioru żądań Ri procesu Pi).
8
Kiedy proces Pj otrzyma komunikat Å»
DANIE(i), wysyła ODPOWIEDy
(j) do procesu Pi pod
warunkiem, że nie wysłał już komunikatu z odpowiedzią od czasu otrzymania ostatniej wia-
domości ZWOLNIJ. W przeciwnym wypadku komunikat z żądaniem trafia do kolejki, w celu
jego póz
niejszego rozpatrzenia.
W momencie kiedy proces Pi otrzyma komunikaty typu ODPOWIEDy
od wszystkich proce-
sów ze zbioru Ri, może uruchomić swoją sekcję krytyczną.
Po wykonaniu sekcji krytycznej, proces Pi wysyła wiadomości ZWOLNIJ(i) do wszystkich
procesów w Ri. W wypadku kiedy proces Pj otrzyma komunikat ZWOLNIJ(i) od procesu Pi,
wysyła ODPOWIEDy
do następnego oczekującego procesu, który jest w jego kolejce i usuwa
go z niej. Jeżeli kolejka jest pusta, wtedy proces aktualizuje swój stan, tak aby odzwierciedlał
fakt, iż proces nie wysłał żadnego komunikatu ODPOWIEDy
.
ALGORYTM SUZUKI-KASAMI
W algorytmie, który zaproponowali Suzuki i Kasami, jeżeli proces próbuje się dostać do sek-
cji krytycznej i nie ma żetonu, rozsyła wiadomość z żądaniem o żeton do innych procesów.
Proces, który posiada żeton, wysyła go do procesu, który go żądał po otrzymaniu wiadomości
Å»
DANIE. Jeżeli proces otrzyma wiadomość z żądaniem w trakcie wykonywania sesji kry-
tycznej, wysyła żeton chwilę po tym jak wyjdzie z sekcji krytycznej. Proces, który posiada
żeton może wchodzić do sekcji krytycznej dopóty dopóki nie odeśle żetonu innemu proceso-
wi.
Głównymi problemami projektowymi w tym algorytmie są: rozróżnianie przedawnionych
żądań od bieżących oraz określenie, który proces ma zaległe żądanie sekcji krytycznej.
Przedawnione żądania są rozróżniane od bieżących w następujący sposób. Wiadomość typu
Å»
DANIE procesu Pj ma postać Ż
DANIE(j, n), gdzie n=1,2,& jest liczbą porządkową, która
wskazuje, że proces Pj żąda n-tego wykonania sekcji krytycznej. Proces Pi przechowuje ta-
blicę liczb całkowitych RNi[1..N], gdzie RNi[j] jest największą liczbą porządkową otrzymaną
do tej pory w żądaniu od procesu Pj. Ż
DANIE(j, n) otrzymane przez proces Pi jest przedaw-
nione jeżeli RNi[j]>n. Kiedy proces Pi otrzymuje Ż
DANIE(j, n) to zmienia
RNi[j]:=max(RNi[j], n).
Procesy z zaległymi żądaniami sekcji krytycznej są określane przy użyciu zawartości żetonu.
Żeton składa się z kolejki żetonu Q oraz tablicy żetonu LN, gdzie Q jest kolejką procesów
żądających, natomiast LN jest tablicą o rozmiarze N taką, że LN[j] jest liczbą porządkową
żądania, które proces Pj wykonał jako ostatnie. Po wykonaniu swojej sekcji krytycznej, pro-
ces Pi aktualizuje LN[i]:=RNi[i], aby wskazywało, że żądanie odpowiadające liczbie porząd-
kowej RNi[i] zostało spełnione. Tablica żetonu LN[1..N] pozwala procesowi ustalić czy jakiś
inny proces ma zaległe żądanie sekcji krytycznej. Zauważmy, że jeżeli dla procesu Pi mamy
RNi[j]=LN[j]+1, wtedy proces Pj jest w stanie żądania żetonu. Po wykonaniu sekcji krytycz-
nej, proces sprawdza ten warunek dla wszystkich wartości j, żeby określić wszystkie procesy,
które żądają żetonu oraz umieszcza ich identyfikatory w kolejce Q, jeżeli do tej pory ich tam
nie ma. Następnie proces ten wysyła żeton do procesu, który znajduje się na początku kolejki
Q.
Algorytm składa się z następujących kroków. Jeżeli proces który żąda wejścia do sekcji kry-
tycznej, nie posiada żetonu, zwiększa swoją liczbę porządkową, RNi[i], i wysyła Ż
DANIE(i,
sn) do wszystkich procesów (sn jest zaktualizowaną wartością RNi[i].
Gdy proces Pj odbierze tę wiadomość, zmienia RNj[i] na max(RNj[i], sn). W wypadku kiedy
Pj ma bezczynny żeton, wysyła go do procesu Pi pod warunkiem, że RNj[i]=LN[i]+1.
Kiedy proces Pi otrzymuje żeton, uruchamia sekcję krytyczną.
Po ukończeniu sekcji krytycznej, proces Pi wykonuje niniejsze czynności.
Zmienia wartość elementu tablicy żetonu LN[i] na RNi[i]. Dla każdego procesu Pj, którego
identyfikatora nie ma w kolejce żetonu, dodaje jego identyfikator do tej kolejki, jeśli spełnio-
9
ny jest warunek RNi[j]=LN[j]+1. Jeżeli kolejka żetonu nie jest pusta po powyższych aktuali-
zacjach, to proces Pi usuwa identyfikator z początku kolejki i wysyła żeton do procesu ozna-
czonego tym identyfikatorem.
W ten sposób, po wykonaniu sekcji krytycznej, proces nadaje priorytet innym procesom z
zaległymi żądaniami sekcji krytycznej (priorytet, który przewyższa jego bieżące żądania w
toku).
Algorytm ten nie jest symetryczny, ponieważ proces zachowuje żeton nawet, jeśli sam nie
żąda wejścia do sekcji krytycznej. Jest to przeciwieństwem koncepcji algorytmu symetrycz-
nego autorstwa Ricarta i Agrawali, gdzie  żaden proces nie posiada prawa dostępu do swojej
sekcji krytycznej, jeżeli nie było takiego żądania .
ALGORYTM RAYMONDA
W algorytmie Raymonda, który bazuje na drzewie, procesy są logicznie zorganizowane w
postaci skierowanego drzewa, takiego, że jego krawędzie wskazują w kierunku procesu, po-
siadającego żeton (korzeń drzewa). Każdy proces ma lokalną zmienną posiadacz, która wska-
zuje na sąsiedni proces w skierowanej ścieżce do korzenia. Tym sposobem zmienna posia-
dacz definiuje w procesach strukturę logicznego drzewa procesów. Jeśli podążymy za warto-
ściami zmiennych posiadacz w procesach, zobaczymy że każdy proces znajduje się na skie-
rowanej ścieżce prowadzącej do procesu z żetonem. Wartość posiadacz korzenia wskazuje na
niego samego.
Każdy proces P utrzymuje kolejkę FIFO, oznaczoną jako kolejka_żądań, która przechowuje
żądania tych sąsiednich procesów, które wysłały żądanie do procesu P, ale nie wysłano do
nich jeszcze żetonu.
Kiedy proces Pi chce wejść do sekcji krytycznej, wysyła Ż
DANIE do procesu (wskazywany
przez posiadacza), wzdłuż skierowanej ścieżki prowadzącej do korzenia, pod warunkiem że
nie posiada żetonu i jego kolejka_żądań jest pusta. Następnie Pi dodaje swoje żądanie do
swojej kolejki_żądań(i). Należy zauważyć, że niepusta kolejka_żądań procesu oznacza, że
wysłał on Ż
DANIE do korzenia, które odnosi się do wpisu z początku kolejki.
Gdy proces Pj otrzyma Å»
DANIE, umieszcza je w swojej kolejce i wysyła Ż
DANIE wzdłuż
skierowanej ścieżki do korzenia o ile nie wysłał jakiegoś innego Ż
DANIA (które było na-
stępstwem otrzymanego wcześniej Ż
DANIA i znalazło się w kolejce żądań).
W momencie gdy proces będący korzeniem drzewa (posiadacz żetonu) odbierze wiadomość z
Å»
DANIEM, wysyła żeton do procesu Pi, od którego otrzymał to Ż
DANIE, a następnie
zmienia zmienną posiadacz, tak aby wskazywała na proces Pi.
Kiedy proces Pk otrzyma żeton, usuwa wpis ze szczytu swojej kolejki_żądań, wysyła żeton do
procesu Pj wskazywanego przez ten wpis oraz zmienia zmienną posiadacz na proces Pj. Jeśli
w tym momencie kolejka_żądań jest niepusta, to proces wysyła Ż
DANIE do procesu, który
jest wskazany przez zmiennÄ… posiadacz.
Proces Pi wchodzi do sekcji krytycznej w chwili gdy dostaje żeton, a jego własny wpis jest na
szczycie jego kolejki_żądań. W tym wypadku, proces Pi kasuje początkowy wpis ze swojej
kolejki_żądań i wchodzi do sekcji krytycznej.
Po ukończeniu sekcji krytycznej proces Pi, jeżeli jego kolejka żądań jest niepusta, kasuje wpis
z początku swojej kolejki, wysyła żeton do odpowiedniego procesu Pj i ustawia zmienną po-
siadacz na Pj. Jeśli kolejka procesu Pi jest wciąż niepusta, wtedy proces wysyła Ż
DANIE do
procesu, który jest wskazany przez zmienną posiadacz.
7. Migracja procesów, a technologia agentów.
Wędrówka kodu sprowadza się w dużej mierze do wędrówki pewnych danych. Jednakże,
wędrówka kodu to niejednokrotnie coś więcej niż przesyłanie samych danych, a mianowicie
związana z nią wędrówka procesu. Ponieważ jak wiadomo, procesy mogą być aktywne i są z
10
nimi związane pewne zasoby, problem wędrówki procesu jest o wiele bardziej skomplikowa-
ny niż wędrówka samych danych. Koszt takiej operacji jest zazwyczaj stosunkowo duży.
Mimo to, właśnie efektywność jest główną przyczyną dla której wykonuje się przeniesienia
procesów.
Jako przykład niech posłuży sieć komputerów, które wykonują pewne czasochłonne oblicze-
nia. Część z nich może być mniej obciążona od innych. W celu poprawy globalnej efektyw-
ności przetwarzania przenosimy część obliczeń z komputerów bardziej obciążonych na te
mniej obciążone. Praktyczna realizacja tej koncepcji wymaga jednak odpowiedzi na wiele
szczegółowych pytań. Jak stwierdzić które z komputerów są mniej obciążone? Jaki jest algo-
rytm, według którego procesy są przydzielane lub przenoszone na inne komputery?
PROSTE PRZYKA
ADY W
DRÓWKI KODU
Jednym z bardziej popularnych przykładów wędrówki kodu jest przenoszenie części operacji
ze strony serwera na stronę klienta, np. weryfikacja formularzy wypełnianych przez użytkow-
nika lub inne operacje na danych, które skutkują ich szybszym przesyłaniem do serwera. Ta-
kie operacje, nawet jeżeli proste, mogą często w znaczący sposób odciążyć serwery, a tym
samym znacząco zwiększyć ich efektywność.
Innym przykładem wykorzystania migracji procesów są mobilne programy, które poprzez
zwielokrotnienie się na wielu komputerach mogą przyspieszyć wykonywanie rozległych ope-
racji.
Istotną cechą wędrówki kodu jest jej elastyczność i możliwość dynamicznej konfiguracji. Za
przykład może tu posłużyć dostarczanie kodu do klienta w miarę potrzeby, tak aby nie musiał
on wcześniej instalować wszystkich niezbędnych aplikacji. Implementacją takiego modelu są
m.in. powszechnie używane aplety zrealizowane w środowisku Java.
MODELE W
DRÓWKI PROCESÓW
Operacja przenoszenia procesu z jednej maszyny na drugą może przybierać wiele postaci.
Oprócz wędrówki kodu możemy mieć tu do czynienia z koniecznością przeniesienia stanu
procesu, który jest w trakcie wykonywania. Dla uproszczenia rozważań o modelach załóżmy,
że każdy proces składa się z trzech segmentów: segmentu kodu, segmentu zasobów oraz seg-
mentu wykonania, który przechowuje dane o bieżącym stanie procesu.
W najprostszym przypadku będziemy mieli do czynienia z przenośnością słabą. W tym
przypadku przesyłany jest tylko segment kodu. Jeżeli dodamy do tego możliwość przesyłania
segmentu wykonania uzyskamy tzw. przenośność silną. Przenośność silna jest ogólniejsza od
słabej i pozwala na przenoszenie procesów w trakcie ich wykonywania. Wadą przenośności
silnej jest jednak jej większa złożoność.
Przenośność słabą można jeszcze rozróżnić w zależności od tego czy w celu wykonania prze-
słanego kodu uruchamiany jest nowy proces na maszynie docelowej, czy też kod ten wyko-
nywany jest w ramach pewnego procesu docelowego.
W wypadku przenośności silnej wyróżnia się metodę klonowania procesów, która polega na
skopiowaniu działającego programu na docelową maszynę w taki sposób, że oryginał i jego
kopia działają równolegle.
Kolejną kwestią wymagającą rozpatrzenia jest wybór inicjatora wędrówki. Jeżeli jest to pier-
wotny posiadacz procesu, mówimy o wędrówce inicjowanej przez nadawcę. Gdy natomiast
inicjatywę podejmuje maszyna docelowa, na której ma się wykonać proces, mamy do czynie-
nia z wędrówką inicjowaną przez odbiorcę.
WI
ZANIE ZASOBÓW LOKALNYCH
Wraz z wędrówką procesu pojawia się problem zarządzania zasobami lokalnymi, z których
korzysta przenoszony proces. Sposób postępowania z zasobami lokalnymi zależy od kilku
11
czynników. Jednym z nich jest sposób w jaki proces jest związany z danym zasobem. Wyróż-
niono zasadniczo trzy sposoby wiązania zasobów: wiązanie przez identyfikator, wiązanie
przez wartość, i wiązanie przez typ.
Proces, który odwołuje się do zasobu przez identyfikator oczekuje konkretnego zasobu o da-
nym identyfikatorze, czyli np. adresie internetowym. Jest to najmocniejsza forma wiÄ…zania.
Słabszą formą związania zasobu jest wiązanie przez wartość. Taki typ wiązania powoduje, że
proces odwołuje się do wartości zasobu, a nie do konkretnego zasobu. Ostatnim, najmniej
wymagającym typem wiązania, jest wiązanie przez typ, w którym wymaga się dostępu do
zasobu o określonym typie.
WI
ZANIE ZASOBÓW Z MASZYN

Wraz z wędrówką procesu często występuje konieczność zmiany odniesienia do zasobów.
Rodzaj wiązania pozostaje zawsze ten sam. To w jaki sposób zostanie zmienione odniesienie
do danego zasobu, zależy od sposobu jego powiązania z konkretną maszyną.
Zasoby niepołączone można w stosunkowo łatwy sposób przenosić między maszynami, np.
pliki z danymi. Bardziej kłopotliwymi zasobami są zasoby umocowane. Ich przeniesienie jest
możliwe, aczkolwiek koszt jest nieraz na tyle wysoki, że praktycznie jest to nieopłacalne. W
końcu mamy zasoby nieruchome, których przeniesienie jest niemożliwe. Są to m.in. urzą-
dzenia do wykonywania pewnego typu zadań, np. drukarka.
Podczas wędrówki procesu możemy postąpić z jego zasobami w różny sposób, w zależności
od rodzaju zasobu. Jeżeli zasób jest niepołączony, to zazwyczaj jest on przenoszony lub ko-
piowany, jeżeli nie jest to wiązanie przez identyfikator. Zasoby związane przez typ można
związać z reguły na nowo z zasobem dostępnym lokalnie, jeżeli taki jest oczywiście dostępny.
W przypadku zasobów nieruchomych często jedyną możliwością są globalne odniesienia.
Zasoby wiązane przez wartość dają również możliwość skopiowania samej wartości, chyba że
mamy do czynienia z zasobami nieruchomymi.
W
DRÓWKA W SYSTEMACH HETEROGENICZNYCH
W przypadku systemów rozproszonych istotnym czynnikiem przy ich projektowaniu jest he-
terogeniczność.
Szczególnie widać to właśnie w przypadku procesów i ich wędrówki. Dopóki rozpatrujemy
identyczne maszyny, czyli mamy do czynienia ze środowiskiem homogenicznym, dopóty nie
istnieje wiele problemów związanych z różnicami wewnątrz środowiska maszyn i oprogra-
mowania.
Możliwość wykonania identycznego kodu na różnych typach maszyn i właściwego przecho-
wywania stanu procesu sÄ… kluczowe dla poprawnego wykonania operacji przeniesienia proce-
su. Stopień komplikacji wędrówki procesu w systemie zależy oczywiście od typu wędrówki.
Jeżeli jest to przenośność słaba, problem sprowadza się do wygenerowania kodu dla odpo-
wiednich typów platform. Nie ma tu natomiast przeniesienia segmentu wykonania, który mo-
że znacząco się różnić w zależności od architektury maszyny.
Przykładowym rozwiązaniem, które zastosowano m.in. dla języka Java jest zezwolenie na
wędrówkę procesu tylko w określonych punktach jego wykonywania np. przy wywoływaniu
metody, wtedy też aktualizowany jest tzw. stos wędrówki. Stos wędrówki jest niczym innym
jak kopią stosu programów ale przechowywaną w sposób niezależny od maszyny.
Za każdym razem kiedy proces wchodzi do podprogramu i z niego wychodzi odpowiednie
dane ze stosu, identyfikator wywołanego podprogramu oraz etykieta powrotu (adres od które-
go należy kontynuować przetwarzanie po powrocie z podprogramu) są przetaczane i odkła-
dane na stosie wędrówki. Stos wędrówki jest w razie wędrówki procesu przenoszony na ma-
szynę docelową i tam odwrotnie przetaczany, tak aby można było odtworzyć stos fazy wy-
konywania.
12
KOMUNIKATY A W
DRÓWKA PROCESÓW
Podczas wędrówki procesu pojawia się pewna trudność w postaci stanu komunikacji przeno-
szonego procesu. Poza tym nasuwa się również pytanie, co zrobić z przyszłymi komunikata-
mi, które będą nadchodzić do wspomnianego procesu.
Odpowiedzią na te problemy mogą być trzy następujące rozwiązania: przekierowywanie
komunikatów, zapobieganie utracie komunikatów oraz odzyskiwanie utraconych komu-
nikatów.
Pierwsze z wymienionych podejść, czyli przekierowywanie komunikatów działa w ten spo-
sób, że komputer, z którego proces wywędrował musi zapamiętać wszystkie możliwe z
ródła
komunikatów dla tego procesu. Ponadto maszyna z
ródłowa musi również znać adres docelo-
wej maszyny, do której odbyła się wędrówka. Z kolei procesy-nadawcy niekoniecznie są in-
formowani o fakcie wędrówki i mogą wysyłać komunikaty do starego miejsca procesu. Jeżeli
w trakcie wędrówki procesu przychodziły komunikaty, są one zapamiętywane w starym miej-
scu i dostarczane do procesu-odbiorcy po ukończeniu operacji wędrówki. Wadą tego podej-
ścia jest łańcuch pośredników rosnący w miarę, jak proces wędruje na kolejne maszyny.
W podejściu polegającym na zapobieganiu utracie wiadomości proces, który zamierza wę-
drować, powiadamia o tym wszystkie procesy, z którymi utrzymuje komunikację, tak aby te
mogły po ukończeniu wędrówki komunikować się z nim bezpośrednio. W przeciwieństwie do
poprzedniej metody unika się tu pośredników w komunikacji, dzięki czemu ruch w systemie
jest mniejszy.
W ostatniej metodzie polegającej na odzyskiwaniu utraconych komunikatów, proces podlega-
jący wędrówce nie wysyła do procesów, z którymi się komunikuje, żadnych informacji o tym
fakcie. Wszystkie wiadomości, które nadchodzą podczas procesu migracji, są po prostu igno-
rowane i tracone. Proces po zakończeniu migracji nawiązuje ponownie komunikację z proce-
sami, z którymi ją wcześniej utrzymywał i rozpoczynany jest proces odzyskiwania utraconych
komunikatów. Metoda ta stosowana jest często w systemach, gdzie liczy się czas migracji
procesu, gdyż jest ona stosunkowo szybka i prosta.
AGENCI PROGRAMOWI
Mimo braku precyzyjnej definicji agenta programowego, można go opisać jako pewne roz-
szerzenie pojęcia procesu, w tym sensie, że jest on zdolny do samodzielnego działania; jest
autonomiczny i potrafi się również komunikować z innymi agentami. W miarę rozwoju badań
nad agentami programowymi wyróżniono kilka ich typów.
Agenci współpracujący charakteryzują się tym, że dążą do osiągnięcia pewnego wspólnego
celu poprzez współpracę ze sobą.
Agenci ruchomi potrafią z kolei się przemieszczać między różnymi maszynami, zbierając np.
różne dane.
Agenci interfejsu pomagają użytkownikom w używaniu różnych aplikacji, często ucząc się
przy tym w celu poprawienia przyszłego działania.
Ostatnią klasą agentów są agenci informacji, odpowiedzialni za zarządzanie informacjami,
np. filtrowanie.
Ważnym elementem działania agentów programowych jest sposób ich komunikacji. Do tego
celu służy tzw. kanał komunikacji agentów ACC. ACC jest między innymi odpowiedzialny
za niezawodność komunikacji i porządek komunikatów. Wraz z ACC pojawia się również
język komunikacji agentów ACL. Język ten określa pewien standard wymiany informacji
między agentami, protokół. Istotne w przypadku ACL jest rozdzielenie w komunikacie dwóch
składników: jego celu i treści. Wyróżnia się pewną skończoną liczbę celów, na które agent-
odbiorca może zareagować. Przykładowymi celami są zamówienie jakiegoś działania, pytanie
o jakiÅ› obiekt lub dostarczenie jakiejÅ› oferty.
13
8. Etapy projektowania i modelowania symulacji kompute­
rowych.
" Rozpoznanie problemu istniejącego w realnym świecie  gromadzenie jak największej
wiedzy doświadczalnej o układzie, tzn. ustalenie struktury poszukiwanych danych i
zebranie odpowiednio dużej ich ilości, aby mogły one póz
niej posłużyć do walidacji
modelu,
" Model konceptualny  zgrubne zrozumienie sytuacji problemowej, określenie celu
modelowania, zaprojektowanie modelu konceptualnego (danych wejściowych, wyj-
ściowych oraz zawartości modelu), zebranie i analiza danych do rozwinięcia modelu,
" Programowanie  zakodowanie modelu konceptualnego w języku używanego progra-
mu symulacyjnego,
" Symulacja  przeprowadzenie obliczeń pod kątem sprawdzenia zachowania układu w
różnych warunkach. Celem tego etapu jest otrzymanie przybliżonego rozwiązania za-
danego problemu (przeszukanie przestrzeni rozwiązań).
" Weryfikacja wyników  otrzymane wyniki należy szczegółowo przeanalizować pod
kątem ich poprawności formalnej, tzn.:
o Poprawności i stabilności procedury numerycznej,
o Jednoznaczności rozwiązań numerycznych,
o Zgodności typów i struktur danych,
o Wychwycenia wyników jawnie nonsensowych.
Na tym etapie sprawdza się jedynie poprawność wykonania obliczeń, a nie zgodność
modelu z wynikami obserwacji.
" Walidacja modelu  ocena, czy model w obszarze swojej stosowalności wykazuje za-
dowalającą zgodność z układem realnym. Jest ona prowadzona głównie pod kątem
falsyfikacji modelu, aczkolwiek nie należy z góry odrzucać modeli nie spełniających
wszystkich narzuconych kryteriów z uwagi na niepewności danych pomiarowych.
" Implementacja wyników  wdrożenie otrzymanych wyników w struktury posiadanej
wiedzy w celu:
o Oceny jakości teorii naukowych,
o Odkrycia nowych aspektów rzeczywistości,
o Ulepszenia realnego świata,
o Wspomagania procesu decyzyjnego.
" Kalibracja i iteracja modelu  ostatni etap symulacji przeprowadzany w przypadku
niezadowalającej oceny modelu na etapie jego walidacji, polega na zmianie wartości
parametrów i/lub postaci równań oraz powtórnego uruchomienia obliczeń w celu uzy-
skania dokładniejszych wyników.
9. Deterministyczne metody rozwiÄ…zywania równaÅ„ róż­
niczkowych  metoda Eulera i metody Rungego Kutty.
Metody Eulera i Rungego-Kutty służą do całkowania równań różniczkowych zwyczajnych.
Równaniem różniczkowym zwyczajnym nazywamy równanie zawierające niewiadomą funk-
cję jednej zmiennej oraz jej pochodne wyższych rzędów.
Rzędem równania różniczkowego nazywamy najwyższy rząd występującej w nim pochodnej
funkcji niewiadomej.
Ogólna postać równania różniczkowego zwyczajnego n-tego rzędu jest następująca:
, , , & , 0

gdzie F jest funkcją określoną w pewnym obszarze (n+2)-wymiarowym i gdzie .

14
METODA R-K 4. RZ
DU
Mamy równanie różniczkowe postaci y' = f(t,y). Znamy początkową wartość y: y(t0)=y0 i
chcemy poznać kolejne wartości y.
Przyjmując dowolne h, będące wielkością kroku różniczkowania, iteracyjny wzór na y we-
dług tej metody to:


2 2
6
gdzie

,

,
2 2

,
2 2
,
METODA R-K 2. RZ
DU
- wersja jawna, znana jako metoda punktu pośredniego.

 wersja niejawna, zwana metodÄ… Heuna.

METODA EULERA (R-K 1. RZ
DU)

10. Idea metod dynamiki molekularnej  algorytm Ver­
leta.
Symulacje dynamiki molekularnej (MD) to numeryczne, wielokrokowe metody rozwiÄ…zywa-
nia równań ruchu Newtona układów złożonych z bardzo wielu cząstek:

, 1. .

Algorytm Verleta służy do numerycznego rozwiązywania układów równań różniczkowych
zwyczajnych drugiego rzędu postaci:
, , , & , , 1,2, & ,
gdzie n oznacza liczbę równań, t jest zmienną niezależną (zwykle jest nią czas), xi to zmienne
zależne (zwykle odpowiadające położeniom), ai są dowolnymi funkcjami t i xi, natomiast za-
pis oznacza drugÄ… pochodnÄ… x po czasie.
Równaniami tego typu są m.in. równania Newtona, opisujące ruch układu oddziałujących
punktów materialnych w polu zewnętrznych sił. Z tego powodu zwykle równania te formułuje
się od razu w postaci uwzględniającej masy obiektów oraz działające na nie siły:
, , , & ,
, 1,2, & ,

gdzie mi oznacza masę i-tego ciała, a Fi jest wypadkową siłą działającą na i-te ciało w chwili
t.
PODSTAWOWA FORMA ALGORYTMU
Rozważmy równanie Newtona układu n ciał (zakładamy, że przyspieszenia nie zależą od
prędkości):

, , 1,2, & ,
,

15

Rozwijamy poszukiwane rozwiÄ…zanie na szereg Taylora:

" 1 1

" " " "

2 6
" 1 1

" " " "

2 6
Po zsumowaniu obu wyrażeń otrzymujemy podstawową formę algorytmu Verleta:

" 2 " " "

gdzie






Wielokrokowość metody Verleta polega na tym, że obliczenia przyszłych położeń cząstek
bazują na znajomości położeń bieżących i przeszłych.
Algorytm Verleta jest metodą rzędu 4 (błąd obcięcia ~" ).
Zalety:
" szybkość, stabilność, prostota implementacji, umiarkowana pamięciożerność, bezpo-
średnie całkowanie równań 2-go rzędu
Wady:
" Pośrednie obliczanie prędkości (do testów zachowania energii)


" "

2"
" Zaburzenie przyczynowości: prędkość w kroku n-tym obliczona na podstawie położe-
nia w kroku (n+1)-szym
" Dokładność obliczenia V rzędu " - błąd obcięcia metody
" Niewielka dokładność obliczenia V dla bliskich r(t)
ALGORYTM SKOKOWY (LEAPFROG)
W algorytmie skokowym położenia i prędkości liczone są w różnych chwilach czasu:

" " " 2
D
D D
" 2 " 2 "
Prędkości w chwilach tn wyznaczane są z zależności:
1
D D
" 2 " 2
2
Cechy algorytmu skokowego:
" Nie ma odejmowania dwóch podobnych wielkości, co mogłoby być przyczyną znacz-
nych błędów obliczeniowych.
" Do wyznaczenia prędkości w chwili t nie potrzeba znajomości położenia w chwili
"
ALGORYTM PR
DKOÅšCIOWY (VELOCITY VERLET)
Jest to modyfikacja oryginalnego algorytmu Verleta, w której prędkości, położenia i przyspie-
szenia cząstek w chwili " próbkowane są z różną gęstością wg schematu:
"
"

"

2
"
D
" 2
2
1

" "



D " "
" " 2
2
16
11. Rozwiązywanie zagadnień numerycznych metodami
stochastycznymi  metoda Monte Carlo.
Proces stochastyczny to funkcja losowa, czyli funkcja matematyczna, której wartości leżą w
przestrzeni zdarzeń losowych. Innymi słowy, pewnej wielkości (jakiemuś człowiekowi, licz-
bie, chwili czasu, punktowi płaszczyzny) przypisane jest zdarzenie losowe (wzrost, losowo
wybrana liczba, wartość waluty wg notowań giełdowych, liczba rzeczywista).
Metoda Monte Carlo jest stosowana do modelowania matematycznego procesów zbyt złożo-
nych (obliczania całek, łańcuchów procesów stochastycznych), aby można było przewidzieć
ich wyniki za pomocą podejścia analitycznego. Istotną rolę w metodzie MC odgrywa losowa-
nie (wybór przypadkowy) wielkości charakteryzujących proces, przy czym losowanie doko-
nywane jest zgodnie z rozkładem, który musi być znany.
Typowym przykładem może być modelowanie wyniku zderzenia cząstki o wysokiej energii z
jądrem złożonym, gdzie każdy akt zderzenia elementarnego (z pojedynczym nukleonem ją-
dra) modelowany jest oddzielnie poprzez losowanie liczby, rodzaju, kÄ…ta emisji, energii itp.
cząstek wtórnych emitowanych w wyniku takiego zderzenia. Następnym etapem jest modelo-
wanie losu każdej z cząstek wtórnych (w wyniku kolejnego losowania prawdopodobieństwa
oddziaływania lub wyjścia z jądra). Kontynuując taką procedurę można otrzymać pełny opis
 sztucznie generowanego procesu złożonego. Po zebraniu dostatecznie dużej liczby takich
informacji można zestawić ich charakterystyki z obserwowanymi wynikami doświadczalny-
mi, potwierdzając lub negując słuszność poczynionych w całej procedurze założeń.
Metodą Monte Carlo można obliczyć pole figury zdefiniowanej nierównością:
1
czyli koła o promieniu 1 i środku w punkcie (0,0).
" Losuje się n punktów z opisanego na tym kole kwadratu o współrzędnych wierzchoł-
ków (-1,-1), (-1,1), (1,1), (1,-1)
" Po wylosowaniu każdego z tych punktów trzeba sprawdzić, czy jego współrzędne
spełniają powyższą nierówność
Wynikiem losowania jest informacja, że z n wszystkich prób k było trafionych, zatem pole
koła wynosi



gdzie P jest polem kwadratu opisanego na kole.
Dokładność wyniku uzyskanego tą metodą jest zależna od liczby sprawdzeń i jakości użytego
generatora liczb pseudolosowych. Zwiększanie liczby prób nie zawsze zwiększa dokładność
wyniku, ponieważ generator liczb pseudolosowych ma skończenie wiele liczb losowych w
cyklu.
Ta metoda całkowania jest używana w przypadkach, kiedy szybkość otrzymania wyniku jest
ważniejsza od jego dokładności.
12. Generowanie liczb pseudolosowych.
Generator liczb pseudolosowych (PRNG) to program lub podprogram, który na podstawie
niewielkiej ilości informacji (ziarno, zarodek  seed) generuje deterministycznie ciąg bitów,
który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie loso-
wego z
ródła.
Generatory liczb pseudolosowych nie generują ciągów prawdziwie losowych  generator ini-
cjowany ziarnem, które może przyjąć k różnych wartości, jest w stanie wyprodukować co
najwyżej k różnych ciągów liczb. Co więcej, ponieważ rozmiar zmiennych reprezentujących
wewnętrzny stan generatora jest ograniczony (zwykle decyzją programisty, do kilkudziesięciu
lub kilkuset bitów, a rzadziej, po prostu rozmiarem pamięci komputera) i ponieważ w związ-
17
ku z tym może on znajdować się tylko w ograniczonej liczbie stanów, bez dostarczania no-
wych danych z zewnątrz musi po jakimś czasie dokonać pełnego cyklu i zacząć generować te
same wartości. Teoretyczny limit długości cyklu wyrażony jest przez 2n, gdzie n to liczba
bitów przeznaczonych na przechowywanie stanu wewnętrznego. W praktyce, większość ge-
neratorów ma znacznie krótsze okresy.
Do wielu zastosowań, opisany powyżej rodzaj deterministycznej pseudolosowości jest w zu-
pełności wystarczający. W algorytmach probabilistycznych (takich jak np. całkowanie Monte
Carlo) potrzebne jest jedynie z
ródło wartości o cechach przybliżonych do liczb prawdziwie
losowych, chociaż jakość losowości może być decydująca dla dokładności obliczeń. Dlatego
przy zastosowaniu każdego nowego generatora do celów obliczeń numerycznych należy
sprawdzić jego własności statystyczne. W przypadku skorzystania z jednego z dobrze zbada-
nych generatorów można czasem bezpośrednio obliczyć długość cyklu, a pozostałe właściwo-
ści (jak np. równomierność rozkładu) są najczęściej znane.
ZASTOSOWANIE W KRYPTOGRAFII
Szczególną klasę PRNG stanowią generatory uznane za bezpieczne do zastosowań kryptogra-
ficznych. Kryptografia opiera siÄ™ na generatorach liczb pseudolosowych przede wszystkim w
celu tworzenia unikalnych kluczy stałych oraz sesyjnych. Ze względu na fakt, że bezpieczeń-
stwo komunikacji zależy od jakości klucza, od implementacji PRNG stosowanych w takich
celach oczekuje się między innymi, że:
" Generowane wartości będą każdorazowo praktycznie nieprzewidywalne dla osób po-
stronnych (np. przez wykorzystanie odpowiednich z
ródeł danych przy tworzeniu ziar-
na).
" Nie będzie możliwe ustalenie ziarna lub stanu wewnętrznego generatora na podstawie
obserwacji dowolnie długiego ciągu wygenerowanych bitów.
" Znajomość dowolnej liczby wcześniej wygenerowanych bitów nie będzie wystarczała,
by odgadnąć dowolny przyszÅ‚y bit z prawdopodobieÅ„stwem istotnie wyższym od ½.
" Dla wszystkich możliwych wartości ziarna, zachowana będzie pewna minimalna, do-
pasowana do zastosowania długość cyklu PRNG (aby uniknąć ponownego wykorzy-
stania takiego samego klucza).
PROSTE GENERATORY
Uproszczony liniowy generator kongruencyjny określony jest następującym algorytmem (a, b
i m to odpowiednio dobrane znane stałe):
" Stan początkowy to wartość ziarna,
" Żeby wygenerować bit:
o Nowy stan = a * stary stan + b mod m
o Wygenerowany bit = nowy stan mod 2
Generator ten nie jest bezpieczny  dla pewnych kombinacji parametrów jest prawie losowy,
dla innych bardzo szybko staje się okresowy. Dodatkowo, znane są ogólne metody obliczania
parametrów i przewidywania zachowania takich PRNG na podstawie obserwacji wyników.
13. Model obliczeniowy perceptronu
Perceptron jest to jeden z modeli neuronu, czyli modelu matematycznego odwzorowujÄ…cego
działanie komórki nerwowej człowieka. Schemat perceptronu:
18
gdzie:
" n  liczba wejść w neuronie,
" , & , - sygnały wejściowe,
" , & , - wagi synaptyczne
" y  wartość wyjściowa neuronu
" w0  wartość progowa
Działanie perceptronu można opisać zależnością



Funkcja f może być nieciągłą funkcją skokową  bipolarną (przyjmuje wartości -1 lub 1) lub
unipolarną (przyjmuje wartości 0 lub 1).
Perceptron ze względu na swą funkcję aktywacji przyjmuje tylko dwie różne wartości wyj-
ściowe, może więc klasyfikować sygnały podane na jego wejście do jednej z dwóch klas. Na
przykład perceptron z dwoma wejściami dzieli płaszczyznę na dwie części. W ogólnym przy-
padku, gdy perceptron ma n wejść, wówczas dzieli n-wymiarową przestrzeń wektorów wej-
ściowych x na dwie półprzestrzenie. Są one rozdzielone n-1  wymiarową hiperpłaszczyzną,
nazywanÄ… granicÄ… decyzyjnÄ…, danÄ… wzorem

0

14. Co to znaczy : wyuczyć neuron danego pojęcia
Schemat neuronu:
19
Działanie neuronu jest bardzo proste. Najpierw sygnały wejściowe x0,& ,xn zostają pomnożo-
ne przez odpowiadające im wagi w0,& ,wn. Otrzymane w ten sposób wartości należy następ-
nie zsumować. W wyniku powstaje sygnał s odzwierciedlający działanie części liniowej neu-
ronu. Sygnał ten jest poddawany działaniu funkcji aktywacji, najczęściej nieliniowej. Zakłada
się, że wartość sygnału x0 jest równa 1, natomiast wagę w0 nazywa się progiem. Wiedza w tak
opisanym neuronie zapisana jest w wagach. Neuron można uczyć za pomocą odpowiednio
dobierając wagi za pomocą rożnych algorytmów.
Jedną z grup algorytmów jest uczenie z nauczycielem. Uczenie tego typu polega na tym, iż
podaje się na wejście neuronu sygnały x(t)=[x0(t),& ,xn(t)]T, t=1,2,& , dla których znane są
prawidłowe wartości sygnałów wyjściowych d(t), t=1,2,& , zwanych sygnałami wzorcowy-
mi.. Zbiór takich próbek wejściowych wraz z odpowiadającymi im wartościami sygnałów
wzorcowych nazywamy ciągiem uczącym. W metodach tych po podaniu wartości wejścio-
wych oblicza się sygnał wyjściowy neuronu. Następnie modyfikuje się wagi w ten sposób,
aby minimalizować błąd między sygnałem wzorcowym a wyjściem neuronu. Algorytm po-
wtarza się tak długo, aż dla wszystkich wektorów wejściowych wchodzących w skład ciągu
uczącego błąd na wyjściu będzie mniejszy od założonej tolerancji.
15. Przykład funkcji boolowskiej niewyuczalnej przez
pojedynczy neuron.
Zakres możliwych problemów, które można rozwiązać, stosując pojedynczy perceptron, jest
raczej wąski. Przykładem może być problem funkcji logicznej XOR. Ciąg uczący dla tego
problemu jest w tabeli poniżej:
x1 x2 d=XOR(x1,x2)
1 1 0
1 0 1
0 1 1
0 0 0
Jeśli zaznaczymy w układzie współrzędnych wartości ciągu uczącego, to zauważymy, że nie
istnieje prosta, która rozdzielałaby punkty o wartościach funkcji XOR równych 0 od punktów
o wartościach równych 1. W tym przypadku funkcję przykładowej granicy decyzyjnej pełni
elipsa. Nie jesteśmy w stanie tak dobrać wag pojedynczego perceptronu, aby rozwiązać pro-
blem XOR.
20
16. Zaproponuj sieć perceptronów, która wyuczy się
funkcji boolowskiej AND.
CiÄ…g uczÄ…cy:
x1 x2 d=AND(x1,x2)
1 1 1
1 0 -1
0 1 -1
0 0 -1
Epoka 1:
s f(s) w0 w1 w2
2,5 1 0,5 1 1
1,5 1 0,5 1 1
0,5 1 -0,5 0 1
-1,5 -1 -1,5 0 0
Epoka 2:
s f(s) w0 w1 w2
-1,5 -1 -1,5 0 0
0,5 1 -0,5 1 1
-0,5 -1 -1,5 0 1
-1,5 -1 -1,5 0 1
Epoka 3:
s f(s) w0 w1 w2
-0,5 -1 -1,5 0 1
0,5 1 -0,5 1 2
0,5 1 -1,5 0 2
-2,5 -1 -2,5 0 1
Epoka 4:
s f(s) w0 w1 w2
-1,5 -1 -2,5 0 1
-0,5 -1 -1,5 1 2
0,5 1 -1,5 1 2
-2,5 -1 -2,5 1 2
Epoka 5:
s f(s) w0 w1 w2
0,5 1 -2,5 1 2
-1,5 -1 -2,5 1 2
-0,5 -1 -2,5 1 2
-2,5 -1 -2,5 1 2
21
17. Idee propagacji wstecznej jako metody uczenia sieci
neuronowej
Sieci neuronowe wielowarstwowe są to odpowiednio połączone ze sobą neurony rozmiesz-
czone w dwóch lub więcej warstwach. W wielowarstwowych sieciach neuronowych muszą
istnieć co najmniej dwie warstwy: wejściowa i wyjściowa. Między nimi natomiast mogą
znajdować się warstwy ukryte. Jeżeli sieć zawiera tylko dwie warstwy, to warstwę wejściową
utożsamia się z warstwą ukrytą. Neurony przekazują sygnały tylko między różnymi war-
stwami. W obrębie tej samej warstwy neurony nie mogą łączyć się ze sobą.
Działanie algorytmu wstecznej propagacji błędów rozpoczyna się od podania wzorca uczące-
go na wejście sieci. Najpierw zostaje on przetworzony przez neurony warstwy pierwszej (po-
jęcie przetwarzania oznacza wyznaczenie sygnału wyjściowego dla każdego neuronu w danej
warstwie). Otrzymane w ten sposób sygnały stają się wejściami dla neuronów warstwy na-
stępnej. Cykl ten powtarza się, tzn. ponownie wyznacza się wartości sygnałów na wyjściach
neuronów kolejnej warstwy i przekazuje je dalej, aż do warstwy ostatniej. Znając sygnał wyj-
ściowy warstwy ostatniej oraz sygnał wzorcowy z ciągu uczącego można obliczyć błąd na
wyjściu sieci. Korzystając z odpowiednich wzorów można zmodyfikować wagi neuronów
ostatniej warstwy. Jednak w funkcji celu zmiennymi są wszystkie wagi sieci. Dlatego błąd
wyjściowy jest propagowany od tyłu zgodnie z połączeniami neuronów między warstwami i z
uwzględnieniem ich funkcji aktywacji. Nazwa algorytmu pochodzi od sposobu jego realizacji,
tzn. błąd jest  cofany od warstwy wyjściowej do wejściowej.
18. Mechanizm działania algorytmu genetycznego.
Algorytm ewolucyjny stanowi wzorowanÄ… na naturalnej ewolucji metodÄ™ rozwiÄ…zywania pro-
blemów, głównie zagadnień optymalizacyjnych. Algorytmy ewolucyjne są procedurami prze-
szukiwania opartymi na mechanizmach doboru naturalnego i dziedziczenia. KorzystajÄ… z
ewolucyjnej zasady przeżycia osobników najlepiej przystosowanych.
Algorytmy ewolucyjne korzystają z określeń zapożyczonych z genetyki. Populacją nazywa
się zbiór osobników o określonej liczebności. Osobnikami populacji w algorytmach gene-
tycznych są zakodowane w postaci chromosomów zbiory parametrów zadania, czyli rozwią-
zania, określane też jako punkty przestrzeni poszukiwań. Osobniki czasami nazywa się orga-
nizmami. Chromosomy  inaczej łańcuchy lub ciągi kodowe  to uporządkowane ciągi ge-
nów. Gen  nazywany też cechą, znakiem, detektorem  stanowi pojedynczy element genoty-
pu, w szczególności chromosomu. Genotyp, czyli struktura, to zespół chromosomów danego
osobnika. Zatem osobnikami populacji mogą być genotypy albo pojedyncze chromosomy.
Fenotyp jest zestawem wartości odpowiadających danemu genotypowi, czyli zdekodowaną
strukturą, a więc zbiorem parametrów zadania. Allel to wartość danego genu, określana też
jako wartość cechy lub wariant cechy.
Bardzo ważnym pojęciem w algorytmach genetycznych jest funkcja przystosowania (dopa-
sowania, oceny). Stanowi ona miarÄ™ przystosowania danego osobnika w populacji. W algo-
rytmie ewolucyjnym, w każdej jego iteracji, ocenia się przystosowanie każdego osobnika da-
22
nej populacji za pomocÄ… funkcji przystosowania i na tej podstawie tworzy siÄ™ nowÄ… populacjÄ™
osobników, stanowiących zbiór potencjalnych rozwiązań problemu. Kolejną iterację w algo-
rytmie ewolucyjnym nazywa się generacją, a o nowo utworzonej populacji osobników mówi
się też nowe pokolenie lub pokolenie potomków.
Na podstawowy algorytm genetyczny składają się kroki:
1) inicjacja, czyli wybór początkowej populacji chromosomów,
2) ocena przystosowania chromosomów w populacji,
3) sprawdzenie warunku zatrzymania,
4) selekcja chromosomów,
5) zastosowanie operatorów genetycznych,
6) utworzenie nowej populacji,
7) wyprowadzenie  najlepszego chromosomu.
Inicjacja, czyli utworzenie populacji początkowej, polega na losowym wyborze żądanej licz-
by chromosomów (osobników) reprezentowanych przez ciągi binarne o określonej długości.
Ocena przystosowania chromosomów w populacji polega na obliczeniu wartości funkcji
przystosowania dla każdego chromosomu z tej populacji. Im większa jest wartość tej funkcji,
tym lepsza  jakość chromosomu. Postać funkcji przystosowania zależy od rodzaju rozwią-
zywanego problemu. Zakłada się, że funkcja przystosowania przyjmuje zawsze wartości nie-
ujemne, a ponadto, że rozwiązywany problem optymalizacji jest problemem poszukiwania
maksimum tej funkcji. Jeśli pierwotna postać funkcji przystosowania nie spełnia tych założeń,
to dokonuje siÄ™ odpowiedniej transformacji.
Sprawdzenie warunku zatrzymania. Określenie warunku zatrzymania algorytmu genetycz-
nego zależy od konkretnego zastosowania tego algorytmu. W zagadnieniach optymalizacji,
jeśli znana jest wartość maksymalna (lub minimalna) funkcji przystosowania, zatrzymanie
algorytmu może nastąpić po uzyskaniu żądanej wartości optymalnej, ewentualnie z określoną
dokładnością. Zatrzymanie algorytmu może również nastąpić, jeśli dalsze jego działanie nie
poprawia już uzyskanej najlepszej wartości. Algorytm może też zostać zatrzymany po upły-
wie określonego czasu działania lub po określonej liczbie generacji. Jeśli warunek zatrzyma-
nia jest spełniony, następuje przejście do ostatniego kroku, czyli wyprowadzenia  najlepsze-
go chromosomu. Jeśli nie, to następnym krokiem jest selekcja.
Selekcja chromosomów polega na wybraniu, na podstawie obliczonych wartości funkcji
przystosowania (krok 2), tych chromosomów, które będą brały udział w tworzeniu potomków
do następnego pokolenia, czyli następnej generacji. Wybór ten odbywa się zgodnie z zasadą
23
naturalnej selekcji, tzn. największe szanse na udział w tworzeniu nowych osobników mają
chromosomy o największej wartości funkcji przystosowania.
Zastosowanie operatorów genetycznych do chromosomów wybranych metodą selekcji
prowadzi do utworzenia nowej populacji, stanowiącej populację potomków otrzymaną z po-
pulacji rodziców. W klasycznym algorytmie genetycznym stosuje się dwa podstawowe opera-
tory genetyczne: operator krzyżowania oraz operator mutacji. Należy jednak zaznaczyć, że
operator mutacji odgrywa zdecydowanie drugoplanowÄ… rolÄ™ w stosunku do operatora krzy-
żowania. Oznacza to, że krzyżowanie w klasycznym algorytmie genetycznym występuje pra-
wie zawsze, podczas gdy mutacja dość rzadko. W algorytmie genetycznym mutacja chromo-
somu może być dokonywana na populacji rodziców przed operacją krzyżowania lub na popu-
lacji potomków utworzonych w wyniku krzyżowania.
Utworzenie nowej populacji. Chromosomy otrzymane w wyniku działania operatorów gene-
tycznych wchodzą w skład nowej populacji. Populacja ta staje się tzw. populacją bieżącą dla
danej generacji algorytmu genetycznego. W każdej kolejnej generacji oblicza się wartości
funkcji przystosowania każdego z chromosomów tej populacji. Następnie sprawdza się waru-
nek zatrzymania i albo wyprowadza się wynik w postaci chromosomu o największej wartości
funkcji przystosowania, albo przechodzi siÄ™ do kolejnego kroku algorytmu genetycznego, tzn.
selekcji. W klasycznym algorytmie genetycznym cała poprzednia populacja chromosomów
zastępowana jest przez tak samo liczną nową populację potomków.
Wyprowadzenie  najlepszego chromosomu. Jeżeli spełniony jest warunek zatrzymania
algorytmu genetycznego, należy wyprowadzić wynik działania algorytmu, czyli podać roz-
wiązanie problemu. Najlepszym rozwiązaniem jest chromosom o największej wartości funk-
cji przystosowania.
19. Operacje genetyczne krzyżowania i mutacji
Operator krzyżowania. Pierwszym etapem krzyżowania jest wybór par chromosomów z
populacji rodzicielskiej. Jest to tymczasowa populacja złożona z chromosomów wybranych
metodą selekcji i przeznaczonych do dalszego przetwarzania za pomocą operatorów krzyżo-
wania i mutacji w celu utworzenia nowej populacji potomków. Na tym etapie chromosomy z
populacji rodzicielskiej kojarzone są w pary. Dokonuje się tego w sposób losowy, zgodnie z
prawdopodobieństwem krzyżowania pk. Następnie dla każdej pary wybranych w ten sposób
rodziców losuje się pozycję genu w chromosomie, określającą tzw. punkt krzyżowania. Jeżeli
chromosom każdego z rodziców składa się L genów, to oczywiście punkt krzyżowania lk jest
liczbą naturalną mniejszą od L. Zatem wybór punktu krzyżowania sprowadza się do wyloso-
wania liczby z przedziału [1,L-1]. W wyniku krzyżowania pary chromosomów rodzicielskich
otrzymuje się następującą parę potomków:
1) potomek, którego chromosom składa się z genów na pozycjach od 1 do lk, pocho-
dzących od pierwszego rodzica i następnych genów, od pozycji lk+1 do L, pocho-
dzÄ…cych od drugiego rodzica;
2) potomek, którego chromosom składa się z genów na pozycjach od 1 do lk, pocho-
dzących od drugiego rodzica i następnych genów, od pozycji lk+1 do L, pochodzą-
cych od pierwszego rodzica;
Przykład:
Rozważmy dwa chromosomy ch1=[1001001110] i ch2=[1001111110], które poddajemy ope-
racji krzyżowania. W tym przypadku chromosomy składają się z 10 genów (L=10), losujemy
więc liczbę całkowitą z przedziału [1,9]. Załóżmy, że wylosowano liczbę 5. Przebieg operacji
krzyżowania przedstawia się więc następująco:
Para rodziców: Para potomków:
krzyżowanie
ch1=[10010|01110] [10010|11110]
ch2=[10011|11110] [10011|01110]
24
gdzie symbolem | oznaczono miejsce krzyżowania, a pogrubioną czcionką zaznaczono za-
mienione geny.
Operator mutacji, zgodnie z prawdopodobieństwem mutacji pm, dokonuje zmiany wartości
genu w chromosomie na przeciwną (tzn. z 0 na 1 lub z 1 na 0). Prawdopodobieństwo zaist-
nienia mutacji jest zwykle bardzo małe i oczywiście od niego zależy, czy dany gen w chro-
mosomie podlega mutacji, czy też nie. Dokonanie mutacji zgodnie z prawdopodobieństwem
pm polega na przykład na losowaniu liczby z przedziału [0,1] dla każdego genu i wybraniu do
mutacji tych genów, dla których wylosowana liczba jest równa prawdopodobieństwu pm lub
mniejsza.
Przykład:
Dokonujemy operacji mutacji na chromosomie [1001101010]. Wartość pm wynosi 0,02. Losu-
jemy następujące liczby z przedziału [0,1]:
0,23 0,76 0,54 0,10 0,28 0,68 0,01 0,30 0,95 0,12.
Mutacji podlega gen na pozycji 7, ponieważ wylosowana liczba 0,01 jest mniejsza niż war-
tość prawdopodobieństwa mutacji pm. Wobec tego, jego wartość zmienia się z 1 na 0 i otrzy-
mujemy chromosom [1001100010].
20. Twierdzenie Hollanda o schematach
Pojęcie schematu zostało wprowadzone w celu określenia zbioru chromosomów o pewnych
wspólnych cechach, podobieństwach. Jeżeli allele (wartości genów) przyjmują wartości 0 lub
1, czyli rozważamy chromosomy o binarnym alfabecie, to schemat jest zbiorem chromoso-
mów zawierających zera i jedynki na wyszczególnionych pozycjach. Schematy wygodnie jest
rozpatrywać, korzystając z rozszerzonego alfabetu {0, 1, *}, w którym oprócz 0 i 1 wprowa-
dzono dodatkowo symbol * w celu określenia dowolnej spośród tych wartości.
Przykłady: 10*1={1001,1011}, *01*10={001010,001110,101010,101110}.
Mówi się, że chromosom należy do danego schematu, jeżeli dla każdej pozycji j=1,2,& ,L,
gdzie L jest długością chromosomu, symbol występujący na j-ej pozycji chromosomu odpo-
wiada symbolowi na j-ej pozycji schematu, przy czym zarówno 0, jak i 1 odpowiada symbo-
lowi *. Jeżeli w schemacie występuje m symboli *, to schemat ten zawiera 2m chromosomów.
Ponadto każdy chromosom (łańcuch) o długości L należy do 2L schematów.
Niech F(S,t) oznacza średnią wartość funkcji przystosowania chromosomów w populacji P(t),
" ,


pasujących do schematu S. Jeżeli , & , , , to , , gdzie
,
c(S,t) jest liczbą elementów zbioru . F(S,t) nazywa się także przystosowaniem sche-
matu S w generacji t.
Rząd schematu S, nazywany także licznością schematu i oznaczany przez o(S), jest to liczba
ustalonych pozycji w schemacie, tzn. zer i jedynek w przypadku alfabetu {0, 1, *}.
Przykłady: o(10*1)=3, o(*01*10)=4.
Rozpiętość schematu S, nazywana także długością schematu (nie należy mylić z długością
L), oznaczana przez d(S), jest to odległość między pierwszym i ostatnim ustalonym symbo-
lem.
Przykłady: d(10*1)=3, d(*01*10)=4.
Twierdzenie o schematach:
Schematy małego rzędu, o małej rozpiętości i o przystosowaniu powyżej średniej otrzymują
rosnącą wykładniczo liczbę swoich reprezentantów w kolejnych generacjach algorytmu gene-
tycznego.
25
21. Co to jest pojęcie rozmyte?
Za pomocą zbiorów rozmytych możemy formalnie określić pojęcia nieprecyzyjne i wielo-
znaczne, takie jak  wysoka temperatura ,  młody człowiek . Przed podaniem definicji zbioru
rozmytego musimy ustalić tzw. obszar rozważań. W przypadku pojęcia wieloznacznego  du-
żo pieniędzy inna suma będzie uważana za dużą, jeżeli ograniczymy się do obszaru rozwa-
żań [0; 1000 zł], a inna  jeżeli przyjmiemy przedział [0; 1 000 000 zł]. Obszar rozważań,
nazywany w dalszym ciągu przestrzenią lub zbiorem, będziemy najczęściej oznaczać literą X.
Pamiętajmy, że X jest zbiorem nierozmytym.
Zbiorem rozmytym A w pewnej (niepustej) przestrzeni X, co zapisujemy jako , nazy-
wamy zbiór par

, ; ,
w którym
: 0, 1
jest funkcją przynależności zbioru rozmytego A. Funkcja ta każdemu elementowi przy-
pisuje jego stopień przynależności do zbioru rozmytego A, przy czym można wyróżnić 3
przypadki:

1) 1 oznacza pełną przynależność elementu x do zbioru rozmytego A, tzn.
,

2) 0 oznacza brak przynależności elementu x do zbioru rozmytego A, tzn.
,

3) 0 1 oznacza częściową przynależność elementu x do zbioru rozmytego
A.
Jeżeli X jest przestrzenią o skończonej liczbie elementów, X={x1,& ,xn}, to zbiór rozmyty
zapisuje siÄ™ jako


.


Kreska ułamkowa nie oznacza dzielenia, ale przyporządkowanie poszczególnym elementom
x1,& ,xn stopni przynależności. Podobnie znak  + nie oznacza dodawania, ale sumę mnogo-
ściową.
Jeżeli X jest przestrzenią o nieskończonej liczbie elementów, to zbiór rozmyty symbo-
licznie zapisujemy jako

.


22. Jakie operacje można wykonać na zbiorach rozmy­
tych?
Przecięciem zbiorów rozmytych , jest zbiór rozmyty o funkcji przynależności

min ,
dla każdego .
Sumą zbiorów rozmytych A i B jest zbiór rozmyty określony funkcją przynależności
26

max ,
dla każdego .

Dopełnieniem zbioru rozmytego jest zbiór rozmyty o funkcji przynależności

1

dla każdego .
Iloczyn kartezjański zbiorów rozmytych i oznaczamy i definiujemy jako

min ,
dla każdego i .
23. Idea sterownika rozmytego.
W wielu zagadnieniach dotyczących sterowania procesami technologicznymi niezbędne jest
wyznaczenie modelu rozważanego procesu. Znajomość modelu pozwala dobrać właściwy
regulator (sterownik). Jednakże często znalezienie odpowiedniego modelu jest problemem
trudnym, niekiedy wymagającym przyjęcia różnego typu założeń upraszczających. Zastoso-
wanie teorii zbiorów rozmytych do sterowania procesami technologicznymi nie wymaga zna-
jomości modeli tych procesów. Należy jedynie sformułować reguły postępowania w formie
zdań typu JEŻELI & TO. Sterowniki rozmyte są szczególnymi przypadkami rozmytych
systemów wnioskujących. Typowy schemat takiego systemu składa się z następujących ele-
mentów:
1) bazy reguł,
2) bloku rozmywania,
3) bloku wnioskowania,
4) bloku wyostrzania.
BAZA REGUA

Bazę reguł stanowi zbiór rozmytych reguł R(k), k=1,& ,N, postaci

R(k): JEŻELI x1 jest I x2 jest I & I xn jest


TO y1 jest I y2 jest I & I ym jest ,
gdzie N to liczba rozmytych reguł, A, B  zbiory rozmyte, x  zmienne wejściowe, y - zmien-
ne wyjściowe.
BLOK ROZMYWANIA
System sterowania z logikÄ… rozmytÄ… operuje na zbiorach rozmytych. Dlatego konkretna war-
tość sygnału wejściowego sterownika rozmytego podlega operacji rozmywania, w wyniku
27
której zostaje odwzorowana w zbiór rozmyty A . Zbiór ten jest wejściem bloku wnioskowa-
nia.
BLOK WNIOSKOWANIA
Zakładamy, że na wejściu bloku wnioskowania mamy zbiór rozmyty A .
Przypadek 1:
Na wyjściu bloku wnioskowania otrzymujemy N zbiorów rozmytych . Zbiór roz-
myty jest określony przez złożenie zbioru rozmytego A i relacji R(k), tzn.
Przypadek 2:
Na wyjściu bloku wnioskowania otrzymujemy jeden zbiór rozmyty B , określony
wzorem
BLOK WYOSTRZANIA
Wielkością wejściową bloku wyostrzania jest bądz
N zbiorów rozmytych bądz
jeden zbiór
rozmyty B . W bloku wyostrzania dokonuje się odwzorowanie zbioru (lub zbiorów) wejścio-
wych w jedną wartość , która będzie wyznaczonym sterowaniem na wejściu obiektu. Od-
wzorowanie to nazywamy wyostrzaniem.
24. Konstrukcje drzewa decyzyjnego.
Drzewo decyzyjne jest to graficzna metoda wspomagania procesu decyzyjnego. Składa się
ono z węzłów (decyzji) i gałęzi (możliwych wariantów). Załóżmy, że mamy następującą ta-
blicÄ™ decyzyjnÄ…:
Wiek Płeć Wykształcenie Języki obce Doświadczenie Ogólne wrażenie Przyjęty
25 M 2 4 1 4 Nie
22 K 4 3 4 2 Nie
21 M 4 5 5 4 Tak
29 M 1 3 2 3 Nie
Na podstawie tabeli decyzyjnej tworzymy drzewo, którego węzłami są poszczególne atrybuty,
gałęziami wartości odpowiadające tym atrybutom, a liście tworzą poszczególne decyzje. Na
podstawie przykładowych danych wygenerowano następujące drzewo:
28
Algorytm działa rekurencyjnie dla każdego węzła drzewa. Musimy podjąć decyzję, czy węzeł
będzie:
1. liściem według kryterium stopu  kończymy to wywołanie rekurencyjne
2. węzłem rozgałęziającym się według kryterium wyboru atrybutu  dokonujemy wybo-
ru atrybutu, tworzymy rozgałęzienia według wartości, jakie przyjmuje dany atrybut, i
dla każdego węzła potomnego tworzymy rekurencyjne wywołanie algorytmu, z listą
atrybutów zmniejszoną o właśnie wybrany atrybut.
Wszystkie algorytmy działają według podanego schematu, różnice w implementacji dotyczą
kryteriów stopu i wyboru atrybutu.
25. Definicja entropii informacji i wybrane zastosowa­
nie tego pojęcia.
Entropia w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypada-
jąca na znak symbolizujący zajście zdarzenia z pewnego zbioru. Zdarzenia w tym zbiorze
mają przypisane prawdopodobieństwa wystąpienia.
Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego
w następnej chwili. Jeżeli następujące zdarzenie występuje z prawdopodobieństwem równym
1, to z prostego podstawienia wynika, że entropia wynosi 0, gdyż z góry wiadomo co się sta-
nie - nie ma niepewności.
Entropia jako miara stopnia nieuporządkowania albo inaczej nieokreśloności znalazła zasto-
sowanie np. w badaniach socjometrycznych, w których chodzi o rozkład wyborów w grupie.
Jeżeli nieuporządkowanie jest maksymalne, czyli każda osoba otrzymuje tyle samo wyborów,
entropia jest maksymalna; jeżeli natomiast wybory są zhierarchizowane, a nas interesuje z
ró-
dło tej hierarchizacji, to otrzymujemy inną wartość entropii. Entropia zatem nadaje się rów-
nież do badania struktury grupy społecznej.
26. Przykład modelu obliczeń wzorowanego na realnie
istniejÄ…cym mechanizmie biologicznym.
Jednym z modeli obliczeń, wzorowanym na realnie istniejącym mechanizmie biologicznym,
jest algorytm mrówkowy, inspirowany rzeczywistym zachowaniem mrówek. Niektóre gatun-
ki mrówek podczas wędrówki z mrowiska w kierunku z
ródła pożywienia pozostawiają na
podłożu substancję chemiczną zwaną feromonem. Gdy proces ten powtarza się, feromon po-
zostawiany jest przez mrówki w coraz większych ilościach na coraz krótszych odcinkach.
Kiedy inne mrówki dojdą do punktu decyzyjnego, którym jest skrzyżowanie wielu możliwych
ścieżek, dokonują wyboru trasy na podstawie ilości pozostawionej przez poprzedniczki sub-
stancji. Po kilku chwilach już prawie wszystkie mrówki używają najkrótszej ścieżki ze
względu na najwyższą koncentrację znajdującego się na niej feromonu. Feromon po jakimś
czasie wyparowuje, tracąc swoją intensywność. Ścieżka mało uczęszczana po pewnym czasie
po prostu zniknie.
Praca  sztucznych mrówek stosowanych w algorytmach mrówkowych różni się trochę od
ich żywych odpowiedników, a mianowicie:
a) żyją one w sztucznym dyskretnym świecie, poruszają się wobec tego po zupełnie
innym terenie, na przykład między wierzchołkami grafu;
b) ich ślad feromonowy zanika szybciej niż w rzeczywistości;
c) ilość feromonu wydzielanego przez sztuczną mrówkę uzależniona jest od jakości
rozwiÄ…zania otrzymanego przez niÄ…;
d) w większości przypadków ślad feromonowy aktualizowany jest dopiero po wyge-
nerowaniu rozwiÄ…zania.
29
Algorytmy te służą do rozwiązywania trudnych problemów kombinatorycznej optymalizacji,
takich jak na przykład problem komiwojażera. Problem komiwojażera polega na tym, że ma
on odwiedzić daną liczbę miast jak najkrótszą drogą. Miasta te są różnorodnie odległe od sie-
bie, żadnego z nich nie można pominąć i nie można dwukrotnie znalez
ć się w tym samym
mieście.
Algorytmy mrówkowe znajdują także zastosowania do rozwiązywania dyskretnych proble-
mów optymalizacyjnych, na przykład do wyznaczania tras pojazdów, sortowania sekwencyj-
nego czy wyznaczania tras w sieci komputerowej. Centrale telefoniczne czasami połączone są
ze sobą łączami o małej przepustowości. Gdy wzrasta obciążenie sieci, łącza te zatykają się.
Rozwiązaniem są wirtualni agenci, których praca opiera się na zachowaniu mrówek, dzięki
czemu kolejne centrale mogą zwiększać przepustowość poprzez omijanie przeciążonych od-
cinków sieci.
27. Pojęcie algebry Boole a. Przykłady.
Struktura , , , ,0,1 czyli zbiór A z operacjami dwuargumentowymi , , jednoargumen-
tową operacją  i stałymi 0 1 jest algebrą Boole a wtw, gdy:
" , , jest kratą rozdzielną, czyli dla każdej pary elementów , istnieje kres

górny oraz kres dolny (krata) i dla dowolnych , , zachodzi

(krata rozdzielna)
" : 0 0, 1 1
" : 0, 1
Algebrami Boole a sÄ…:
" , , , ,0,1 zwana dwuargumentowÄ… algebrÄ… Boole a

" , , , , , zwana potęgową algebrą Boole a
28. Funkcje boolowskie: bramki i sieci.
Funkcją boolowską n-argumentową nazywamy dowolną funkcję : 2 2. Zbiór wszystkich
| |
funkcji boolowskich n-argumentowych oznaczymy B(n). 2 .
Każdą funkcję boolowską n-argumentową można przedstawić w postaci ciągu zer i jedynek
długości 2 odpowiadających wartościom funkcji dla kolejnych wartościowań.
Bramki logiczne są układami cyfrowymi realizującymi funkcje logiczne jednej, dwu lub wie-
lu zmiennych.
Podstawowymi elementami logicznymi, stosowanymi powszechnie w budowie układów lo-
gicznych, sÄ… elementy realizujÄ…ce funkcje logiczne: sumy (alternatywy), iloczynu (koniunkcji)
i negacji. Są to odpowiednio bramki OR, AND i NOT. Za pomocą dwóch takich bramek (np.
OR i NOT lub AND i NOT) można zbudować układ (jesteśmy optymistami i mamy nadzieje
że układ = sieć :& ), realizujący dowolną funkcję logiczną.
30
29. Optymalizacja funkcji boolowskich.
Najczęściej optymalizacja sprowadza się do tego, że w wyrażeniu powinna występować jak
najmniejsza liczba elementów (zmiennych oraz operatorów). W rozwiązywaniu zadania i sto-
sowane są różne metody:
" metoda algebraiczna, wykorzystująca podstawowe własności algebry Boole a
" metoda tablic Karnaugha (Karno)
X1 X2 X3 F(x1,x2,x3)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
X1 x2x3 00 01 11 10
0 1 1
1 1 1 1
30. Zadanie identyfikacji modelu. Model czarnej i białej
skrzynki.
Identyfikacja modelu  wygenerowanie z istniejącego fragmentu rzeczywistości elementów
niezbędnych do zbudowania modelu z punktu widzenia potrzeby, możliwości oraz warunkówi
ograniczeń.
Model matematyczny  symboliczny model wyodrębnionej rzeczywistości, który zawiera
ilościowe i jakościowe związki między cechami tej rzeczywistości, istotnymi z punktu widze-
nia celu jego opracowywania. Może być wyrażany za pomocą: wzorów, zestawień itp.
Problemy modelowania matematycznego często klasyfikuje się jako czarne skrzynki lub
białe skrzynki, w zależności od ilości informacji o układzie posiadanych przed modelowa-
31
niem. Sytuacje pośrednie, gdy pewne parametry układu są znane, określa się terminem szarej
skrzynki.
Model czarnej skrzynki przedstawia układ, o którym nie posiadamy absolutnie żadnej infor-
macji o strukturze układu i zależności w układzie.
Model białej skrzynki przedstawia układ, o którego działaniu mamy pełną wiedzę.
W rzeczywistości wszystkie układy plasują się pomiędzy tymi dwoma idealnymi modelami,
sÄ… szarymi skrzynkami.
Często rezygnuje się z modelu białej skrzynki ze względu na złożoność opisu.
Na przykład, gdybyśmy modelowali zachowanie samolotu w powietrzu, moglibyśmy
uwzględnić w opisie zachowanie każdej najdrobniejszej części samolotu i w ten sposób
otrzymalibyśmy idealny  biało skrzynkowy model układu. Jednak koszt obliczeniowy doda-
nia tylu drobnych szczegółów praktycznie uniemożliwiłby korzystanie z modelu. Dodatkowo,
margines błędu całego modelu zwiększyłby się na skutek błędów wprowadzanych w każdym
opisie części.
Wynika stąd, że celowym jest wprowadzanie pewnych przybliżeń i uproszczeń, aby utrzy-
mać stopień złożoności modelu na rozsądnym poziomie.
POST
POWANIE W SYTUACJI CZARNEJ SKRZYNKI
Interesuje nas określenie funkcji H opisującej zależność
między wielkościami x i y.
Jeśli wartości zmiennych możemy mierzyć, to znaczy zna-
my ciągi pomiarów & oraz & , określenie funk-
cji H nazywane jest zadaniem identyfikacji modelu mate-
matycznego.
W praktyce rzadko kiedy mamy do czynienia z zaznaczonÄ…
na rysunku czarną skrzynką. Często związek łączący zmien-
ne znamy z dokładnością do n-wymiarowego wektora para-
metrów liczbowych , & , .
Skrzynka jest  szara i trzeba wyznaczyć konkretną wartość
parametrów.
31. Metody statystyczne w modelowaniu systemów.
Statystyka może służyć jako narzędzie badania danych w celu identyfikacji modelu. Modelem
matematycznym rozkładu populacji jest rozkład prawdopodobieństwa pewnej zmiennej loso-
wej.
Zmienna losowa jest to funkcja przyporzÄ…dkowujÄ…ca zdarzeniom elementarnym prawdopodo-
bieństwo ich wystąpienia. Zmienna losowa może być skokowa (zbiór jej wartości jest przeli-
czalny) lub ciągła.
ROZKA
ADY ZMIENNEJ LOSOWEJ
" Rozkład Bernoulliego
Eksperyment polega na przeprowadzeniu n (n>2) niezależnych doświadczeń, których
rezultatem może być sukces lub porażka. Zakłada się, że prawdopodobieństwo sukce-
su jest takie samo w kolejnych doświadczeniach.
Wzór:
32

1 , 0,1, & , - liczba sukcesów w n doświadcze-

niach
Wartość oczekiwana:
Wariancja: 1
Odchylenie standardowe: "

Mediana:


Wartość modalna:
Przykład:
Pewna firma posiada pięć komputerów  prawdopodobieństwo tego, że jeden kompu-
ter ulegnie awarii wynosi 0,1. Jaki jest rozkład liczby komputerów ulegających awarii?
Jakie jest prawdopodobieństwo tego, że w ciągu dnia awarii ulegną więcej niż dwa
komputery?
p=0,1, n=5
5

0 0,1 0,9 0,59049
0
5

1 0,1 0,9 0,32805
1
5

2 0,1 0,9 0,0729
2
5

3 0,1 0,9 0,0081
3
5

4 0,1 0,9 0,00045
4
5

5 0,1 0,9 0,00001
5
xi 0 1 2 3 4 5
pi 0,59049 0,32805 0,0729 0,0081 0,00045 0,00001
0,5

1 0,45

0,670820393
0
0
" Rozkład Poissona  rozkład zmiennej losowej skokowej, który stosuje się w przypad-
ku określania prawdopodobieństwa zajścia zdarzeń stosunkowo rzadkich i niezależ-
nych od siebie przy występowaniu dużej ilości doświadczeń.


,
!
Wartość oczekiwana:
Wariancja:
" Rozkład wykładniczy
0; 0

Funkcja gęstości:
; 0
0; 0

Dystrybuanta: 1 ; 0


Wartość oczekiwana:



Wariancja:

33
32. Metoda najmniejszych kwadratów. Regresja liniowa
i nieliniowa.
Regresja  dowolna metoda statystyczna pozwalająca estymować warunkową wartość ocze-
kiwaną zmiennej losowej, zwanej zmienną objaśnianą, dla zadanych wartości innej zmiennej
lub wektora zmiennych losowych (tzw. zmiennych objaśniających).
Użycie regresji w praktyce sprowadza się do dwóch faz:
" Konstruowanie modelu  budowa tzw. modelu regresyjnego, czyli funkcji opisujÄ…cej,
jak zależy wartość oczekiwana zmiennej objaśnianej od zmiennych objaśniających.
Funkcja ta może być zadana nie tylko czystym wzorem matematycznym, ale także ca-
Å‚ym algorytmem, np. w postaci drzewa regresyjnego. Model konstruuje siÄ™ tak, aby
jak najlepiej pasował do danych z próby, zawierającej zarówno zmienne objaśniające,
jak i objaśniane (tzw. zbiór uczący).
" Stosowanie modelu  użycie wyznaczonego modelu do danych w których znamy tylko
zmienne objaśniające, w celu wyznaczenia wartości oczekiwanej zmiennej objaśnia-
nej.
Regresja liniowa  regresja, w której modelem zależności między zmiennymi zależnymi a
niezależnymi jest funkcja liniowa. Model ten przyjmuje następującą postać:

gdzie:
" y  zmienna objaśniana modelu,
" x1,& ,xk  zmienne objaśniające modelu,
" µ  zmienna losowa (skÅ‚adnik losowy),
" a0,& ,ak  współczynniki modelu.
Wielkości będziemy nazywać wartościami teoretycznymi

zmiennej y odpowiadajÄ…cymi i-tej obserwacji, i=1,2,& ,n.
Model regresji liniowej można także zapisać w postaci macierzowej jako

1 &
1 &
& & & & & & &
&
1 &
Wektor wartości teoretycznych wyznacza się jako , gdzie a jest wektorem ocen esty-

matora wektora parametrów modelu ą

1 &

1 &
& & & & &
&
&
1 &

Do estymacji parametrów modelu regresji liniowej najczęściej wykorzystuje się klasyczną
metodę najmniejszych kwadratów.
Dla modelu regresji liniowej w postaci macierzowej oraz estymatorem

według metody najmniejszych kwadratów wektora ą jest wektor a wyznaczony jako
.
Regresja nieliniowa  regresja, w której postać modelu dopuszcza nieliniową zależność po-
między zmiennymi objaśniającymi a zmienną objaśnianą. Aby wyznaczyć współczynniki
takiego modelu należy sprowadzić go do postaci regresji liniowej, np. przez utworzenie
sztucznych zmiennych objaśniających (X1=Z2) lub skorzystanie z innych funkcji (logarytm).
34
33. Zagadnienia optymalizacyjne ­ przykÅ‚ady.
Optymalizacja  metoda wyznaczania najlepszego rozwiązania z punktu widzenia określone-
go kryterium. Praktycznym celem optymalizacji jest doprowadzenie decydenta do podjęcia
optymalnej decyzji, tzn. najlepszej z punktu widzenia przyjętego w danych warunkach kryte-
rium decyzyjnego. W sensie matematycznym optymalizacja jest to postępowanie prowadzące
do określenia rozwiązania ekstremalnego, zgodnego z kryterium wyrażonym w formie mini-
mum lub maksimum na zbiorze wartości X.
Przykładem zagadnienia optymalizacyjnego jest programowanie matematyczne: należy zmi-
nimalizować (lub zmaksymalizować) funkcję celu f(x) przy ograniczeniach:
" 0

" 0
gdzie x należy do X, X jest podzbiorem przestrzeni Rn, zaś f, g i h są funkcjami zdefiniowa-
nymi na tym podzbiorze.
Sformułowanie zadania optymalizacji w postaci standardowej wygląda następująco:
Znalez
ć min przy ograniczeniach g(x) i h(x) wyznaczających obszar D.
Każde zadanie maksymalizacji funkcji celu (max f(x)) można zapisać w równoważnej formie
min(-f(x)).

Przykład: określić ekstremum funkcji 4 4.

2 4

0 2  minimum funkcji.
34. Problemy decyzyjne. Podstawowe modele teorii
gier.
Matematyczny model decyzyjny to opis sytuacji decyzyjnej w języku matematyki. W opisie
tym występują zmienne decyzyjne, parametry, funkcja celu, warunki ograniczające i warunki
brzegowe.
W strukturze problemu decyzyjnego można wyróżnić pięć podstawowych elementów:
" Podmiot podejmujÄ…cy decyzje
" Zbiór kierunków działania
" Zbiór stanów świata zewnętrznego
" Funkcja korzyści
" Niepewność co do stanu świata zewnętrznego
Teoria decyzji zajmuje się zagadnieniami wyboru optymalnego rozwiązania z uwzględnie-
niem ryzyka, na jakie narażony jest decydent. Przez ryzyko rozumie się zwykle możliwość
poniesienia straty. Działanie w warunkach ryzyka oznacza sytuację, gdy każdej możliwej do
podjęcia decyzji odpowiada kilka wzajemnie się wykluczających wyników rzeczowych, a
osoba mająca podjąć decyzję jest w stanie określić w tej sytuacji:
" Liczbę tych wyników
" Ocenę zysku każdego wyniku rzeczowego
" Prawdopodobieństwo wystąpienia każdego efektu rzeczowego
Wzajemnie wykluczające się wyniki rzeczowe są niezależne od decydenta i dlatego nazywa
siÄ™ je stanami natury.
Optymalną decyzję w warunkach ryzyka znajduje się często przy użyciu wartości oczekiwa-
nej. Wartość oczekiwana jest w teorii decyzji wykorzystywana jako kryterium decyzyjne 
maksymalizowane lub minimalizowane w zależności od rodzaju problemu decyzyjnego.
Podejmowanie decyzji  sytuacja najprostsza:
" Akceptacja pewnego kierunku działania  decyzja na tak
" Odrzucenie tego kierunku działania  decyzja na nie
35
" Od decyzji na nie, która jest jednoznacznym wyborem konkretnego kierunku działa-
nia, należy odróżnić decyzję o nicnierobieniu, która jest decyzją w pełnym tego słowa
znaczeniu, ponieważ również oznacza wybór w działaniu.
Decyzja o nicnierobieniu jest dość często spotykana ponieważ:
" Czyni odpowiedzialnym los, a nie decydenta za to, co zdarzy się póz
niej
" Sprzyja jej niechęć porzucenia przyjemności związanej z możliwością dokonania wy-
boru spośród wielu kierunków działania
" Pozwala uniknąć przykrych konsekwencji związanych z pozytywnym wyborem kon-
kretnego kierunku działania.
Stany świata zewnętrznego  zdarzenia, które mogą wystąpić w przyszłości i wpłynąć na
wyniki poszczególnych kierunków działania, a które nie są w danym problemie decyzyjnym
bezpośrednio kształtowane przez podmiot podejmujący decyzje. Innymi słowy są to zdarze-
nia, które występują niezależnie od kierunków działania i ujawniają się po wyborze jednego z
nich.
Ponieważ każdej kombinacji kierunku działania i stanu świata zewnętrznego można przypisać
jednoznacznie pewną korzyść, kolejny element struktury problemu decyzyjnego nosi nazwę
funkcji korzyści.
Włączenie niepewności co do stanu świata zewnętrznego do analizy problemu decyzyjnego
jest niezbędne i wymaga wykorzystania elementarnego rachunku prawdopodobieństwa.
Drzewo decyzyjne  sposób przedstawienia problemu decyzyjnego. Jest ono szczególnie
użyteczne w przypadku występowania większej liczby decyzji i stanów natury. Składa się z
dwu rodzajów węzłów i gałęzi łączących te węzły ze sobą. Rozróżnia się węzły decyzyjne
(prostokąt), w których decydent dokonuje wyboru, oraz węzły natury (kółko), w których za-
chodzi losowe działanie przypadku.
TEORIA GIER
Teoria gier to matematyczna teoria pewnej klasy modeli, służących podejmowaniu decyzji w
warunkach konfliktu, niepewności lub nieokreśloności. Konflikt  różnica interesów np. po-
między firmami rywalizującymi o pozyskanie klientów; dodając czynnik losowy może wy-
stąpić konflikt między uczestnikami a naturą. Nieokreśloność  brak informacji o kształtowa-
niu się ważnych elementów sytuacji. Składowe sytuacji konfliktowej: uczestnicy konfliktu
(gracze), opis interesów uczestników konfliktu (strategie), stopień nieokreśloności.
Równowaga Nasha jest to profil strategii teorii gier, w którym strategia każdego z graczy jest
optymalna, przyjmując wybór jego oponentów za ustalony. W równowadze żaden z graczy
nie ma powodów jednostronnie odstępować od strategii równowagi. W tym sensie równowa-
ga jest stabilna. Każda skończona gra ma przynajmniej jedną równowagę Nasha, niekoniecz-
nie w strategiach czystych. Równowagą Nasha w grze dwuosobowej jest następujący wybór:
wybieram to, co jest dla mnie najlepsze, gdy ty robisz to, co robisz; ty robisz to, co jest dla
ciebie najlepsze, gdy ja robiÄ™ to, co robiÄ™.
GRY DWUOSOBOWE O SUMIE ZEROWEJ
Są to gry z dwoma graczami. Suma gry to różnica pomiędzy zyskiem z gry wygrywającego, a
stratą przegrywającego. Jest ona równa zero. Jeśli dodamy wszystkie wartości w grze i w wy-
niku uzyskamy zero dla każdej pary strategii to gra jest grą o sumie zero.
Strategie:
" Strategia dominująca  jeżeli jakaś strategia nie prowadzi do gorszych wypłat niż inne
strategie, a w niektórych przypadkach prowadzi do wypłat lepszych, to strategię taką
nazywa siÄ™ strategiÄ… dominujÄ…cÄ….
" Strategia maksy minowa  jest to strategia, która prowadzi do maksymalizacji najniż-
szych możliwych wypłat w danej grze.
36
" Strategia mieszana  jeżeli dla gracza A dane są strategie , , & , to strategia
mieszana jest dowolną kombinacją tych strategii stosowanych z prawdopodobień-
stwem , , & ,
GRY DWUOSOBOWE O SUMIE NIEZEROWEJ
Strategia dominująca to najlepsza możliwa reakcja na dowolną strategię zastosowaną przez
konkurenta. Jej logika nieuchronnie prowadzi do pogorszenia wyniku, gdy gra ma charakter
niekooperacyjny.
Historycznym przykładem gry niekooperacyjnej jest dylemat więz
nia.
Więzień B milczy Więzień B zeznaje
Więzień A milczy Obaj skazani na 6 miesięcy Więzień A: 10 lat
Więzień B: wolny
Więzień A zeznaje Więzień A: wolny Obaj skazani na 5 lat
Więzień B: 10 lat
Partnerzy skazani są na nieoptymalny wynik. Ze względu na brak bodz
ców, żaden nie zamie-
rza jednostronnie zmienić swojego zachowania, chyba że w drodze podjęcia skoordynowanej
współpracy, opartej na zaufaniu.
W tej grze  wsyp kompana jest strategią dominującą: niezależnie od tego co zrobi przeciw-
nik, zawsze bardziej opłaca się oszukać kolegę niż milczeć. Jeśli współwięzień milczy, oszu-
kiwanie skróci wyrok z sześciu miesięcy do zera. Jeśli współwięzień zeznaje, oszukiwanie
skróci wyrok z dziesięciu lat do pięciu.
GRY Z NATUR

Natura  przeciwnik nierozumny, niezainteresowany wynikiem gry.
Wyboru optymalnej strategii dokonuje się na podstawie jednej z reguł decyzyjnych:
" Kryterium Walda  wybiera maksymalną wygraną przy założeniu, że natura zachowa
siÄ™ jak najbardziej niekorzystnie.
" Kryterium Bayesa-Laplace a  najlepszą strategią jest ta, która daje największą prze-
ciętną wygraną.
" Kryterium Savage a  spełnia postulat minimalizacji oczekiwanych strat wynikłych z
podjęcia decyzji gorszej niż najlepsza możliwa dla danego stanu natury (z punktu wi-
dzenia gracza). Należy wybrać tę strategię, dla której strata relatywna jest najmniejsza.
35. Modelowanie rozmyte.
Zbiorem rozmytym A w pewnej (niepustej) przestrzeni X nazywamy zbiór par

, ;
gdzie

: 0,1
jest funkcją przynależności zbioru rozmytego A. Funkcja ta każdemu elementowi
przypisuje jego stopień przynależności do zbioru rozmytego A, przy czym można wyróżnić 3
przypadki:

" 1 oznacza pełną przynależność do zbioru rozmytego A

" 0 oznacza brak przynależności elementu x do zbioru rozmytego A

" 0 1 oznacza częściową przynależność do zbioru rozmytego A

Zbiór rozmyty A jest pusty jeśli 0 dla każdego .

Zbiór rozmyty A zawiera się w zbiorze rozmytym B gdy dla każdego .

Zbiór rozmyty A jest równy zbiorowi rozmytemu B, gdy dla każdego .
Przecięciem zbiorów rozmytych , jest zbiór rozmyty o funkcji przynależności

min , .
37
Sumą zbiorów rozmytych , jest zbiór rozmyty o funkcji przynależności

max , .

Dopełnieniem zbioru rozmytego jest zbiór rozmyty o funkcji przynależności

1 .


Iloczyn kartezjański zbiorów rozmytych i definiujemy jako ,

min , lub , .
Relacją rozmytą R między dwoma niepustymi zbiorami (nierozmytymi) X i Y nazywamy

zbiór rozmyty określony na iloczynie kartezjańskim , tzn. , :

, . Innymi słowy relacja rozmyta jest zbiorem par , , , gdzie

: 0,1 jest funkcją przynależności. Funkcja ta każdej parze , , ,

przypisuje jej stopień przynależności , , który ma interpretację siły powiązania między
elementami x i y.
REGUA
Y WNIOSKOWANIA
Regułę wnioskowania modus ponens w logice dwuwartościowej określa schemat:
Przesłanka
Implikacja

Wniosek
gdzie A i B symbolizujÄ… zdania.
Uogólnioną (rozmytą) regułę wnioskowania modus ponens określa schemat:
Przesłanka x jest A
Implikacja IF x jest A THEN y jest B
Wniosek y jest B
gdzie , oraz , sÄ… zbiorami rozmytymi, natomiast x i y sÄ… tzw. zmiennymi
lingwistycznymi.
Zmienne lingwistyczne to takie zmienne, które przyjmują jako swoje wartości słowa lub
zdania wypowiedziane w języku naturalnym. Przykładem może być stwierdzenie  mała pręd-
kość . Można je sformalizować poprzez przyporządkowanie im pewnych zbiorów rozmytych.
Mogą również przyjmować wartości liczbowe.
Przykład:
Przesłanka Prędkość samochodu jest duża
Implikacja Jeżeli prędkość samochodu jest bardzo duża
to poziom hałasu jest wysoki
Wniosek Poziom hałasu w samochodzie jest średnio-
wysoki
x  zmienna lingwistyczna  prędkość samochodu
y  zmienna lingwistyczna  poziom hałasu
T1 = { mała ,  średnia ,  duża ,  bardzo duża }  zbiór wartości zmiennej x
T2 = { mały ,  średni ,  średniowysoki ,  wysoki }  zbiór wartości zmiennej y
A =  bardzo duża prędkość samochodu
A =  duża prędkość samochodu
B =  wysoki poziom hałasu
B =  średniowysoki poziom hałasu
ROZMYTA IMPLIKACJA
Niech A i B będą zbiorami rozmytymi, , . Rozmytą implikacją nazywamy
relację R określoną w i zdefiniowaną za pomocą jednej z poniższych reguł:
" Reguła typu minimum, tzw. reguła Mandaniego:

, , min ,
38
" Reguła typu iloczyn, tzw. reguła Larsena:

, , ·
" Reguła A
ukasiewicza

, , min 1,1
" Reguła typu max-min, tzw. reguła Zadeha:

, , max min , , 1
" Reguła binarna:

, , max 1 ,
" Reguła Goguena:


, , min 1,

" Reguła Sharpa:
1 gdy µ x µB y

, , 0 gdy µA
x µB y
A
" Reguła Godela:
1 gdy µA x µB y

, , µ y gdy µA x µB y
B
" Reguła probabilistyczna:

, , min 1,1
" Reguła ograniczonej sumy:

, , min 1,
STEROWNIKI ROZMYTE
Zastosowanie teorii zbiorów rozmytych do sterowania procesów technologicznych nie wyma-
ga znajomości modeli tych procesów. Należy jedynie sformułować reguły postępowania w
formie rozmytych zdań warunkowych typu IF& THEN& . Zastosowania zbiorów rozmytych
obejmują obecnie całą gamę zagadnień  od prostych urządzeń domowego użytku do bardziej
złożonych systemów, np. nadzorujących wentylację tuneli podziemnych.
Klasyczny sterownik rozmyty składa się z bazy reguł, bloku rozmywania, bloku wniosko-
wania oraz bloku wyostrzania.
36. Model ODMG.
ODMG 3.0 jest to standard budowy systemów baz danych o obiektowym modelu danych,
tworzonej od podstaw. Został on opracowany przez organizację  Object Database Manage-
ment Group . Składa się on z następujących elementów:
" Opis modelu
" Definicja danych  ODL
" Język zapytań  OQL
39
" Rozszerzenie Javy, Smalltalka, C++ do przetwarzania trwałych obiektów bazy danych
 OML
OPIS MODELU
" Struktura danych
o Obiekty, literały
o Typy obiektów  atomowe, kolekcje (krotka, zbiór, wielozbiór, lista, tablica,
słownik)
o Możliwe związki binarne 1:1, 1:n, m:n poprzez referencje
" Wielodostęp, transakcje
o Transakcja jako jednostka programowa przeprowadzająca bazę ze stanu spój-
nego w inny stan spójny
o Wielodostęp realizowany przez blokady odczytu i zapisu
" Integralność danych
o Unikalności obiektów  poprzez OID
o Referencyjna  poprzez referencje w obiektach
Elementy modelu obiektowego:
" Klasa  zawiera elementy opisujące zbiór obiektów świata rzeczywistego (cechy i za-
chowanie)
" Cechy obiektów
o OID  systemowy identyfikator obiektu
o Atrybuty  definiowane przez typy danych
o Związki  odwołania do innych obiektów
" Metody  opisują działania, jakie mogą wykonać obiekty danej klasy
" Enkapsulacja  oddzielenie specyfikacji od ciała  z zewnątrz widoczne tylko deklara-
cje atrybutów i metod  implementacja w ciele
" Dziedziczenie  relacja pod/nadklasa  podklasa dziedziczy metody i atrybuty
" Przeciążanie, polimorfizm  zdefiniowanie metody o tej samej nazwie w podklasach,
wywołanie funkcji dla różnych podklas
J
ZYK ODL
" Służy do definicji danych
" Definiuje klasy
" Funkcjonalność klasy definiowana poprzez atrybuty, związki i metody
" Atrybuty  nazwa + typ
" Typy:
o Proste  liczbowe, tekstowe, daty
o Złożone: krotki  struct, zbiory  set, wielozbiory  multiset, listy  list, tablice
 array, słowniki  dictionary, odwołujące się do innej klasy
" Związki  zawierają nazwę, typ i odwołanie do związku zwrotnego
" Metody  zawierają typ zwracanej wartości, nazwę oraz listę parametrów przekazy-
wanych do metody, dodatkowo może wystąpić lista wyjątków
" Rodzaje i typy parametrów
o In, out, inout
o Typy dowolne  tak jak typy danych
OQL
" Wzorowany na SQL
" Obejmuje tylko zapytania
40
" Wyrażenia ścieżkowe  możliwość odwołania się do obiektów poprzez relację pomię-
dzy obiektami
" Operacje Å‚Ä…czenia
o Poprzez związki między obiektami
o Ustalane przez użytkownika
" Polimorfizm i dynamiczne wiÄ…zanie
37. Typy danych w OBD.
Patrz pytanie wyżej
38. Operacje algebraiczne na bazach obiektów.
Operacje algebraiczne (możliwości):
" Zapytanie zawsze dostarcza zbiór wartości (wyjętych z obiektów) z pominięciem
identyfikatora obiektu (duże ograniczenia, narusza kryterium domkniętości)
" Zapytanie dostarcza zbiór obiektów
Operacje zachowujÄ…ce obiekty
" Problem z umieszczeniem wyników zapytań w istniejącej hierarchii klas
" Selekcja  dostarcza podklasę danego argumentu o tym samym typie (trudności, gdy
klasa ma już podklasy, ich porównanie z nową podklasą zależy od ich bieżącego sta-
nu)
" Projekcja  zbiór obiektów nie ulega zmianie, natomiast zmienia się typ wyniku, który
jest podtypem typu argumentu
" Różnica  np. Osoba  Pracownik, daje osoby nie będące pracownikami; jest tworzona
podklasa osób o tym samym typie co klasa Osoba
" Unia  Udziałowiec + Pracownik, daje heterogeniczny zbiór obiektów o typie, który
jest podtypem zarówno Udziałowca jak i Pracownika
Przeciwdziałanie tym problemom
" Dopuszczenie istnienia kilku klas dla jednego typu (zgodne z językami programowa-
nia); zgodny z ODMG
" Zastosowanie operacji obiektotwórczych zamiast operacji zachowujących obiekty
Operacje obiektotwórcze
" Klasy wynikowe istnieją równolegle do wszystkich pozostałych klas w hierarchii,
więc nie mogą dziedziczyć żadnej metody zdefiniowanej na klasach argumentów
" Przy tworzeniu klasy wynikowej wartości atrybutów są kopiowane, w szczególności
są kopiowane odwołania do innych obiektów; np. przy projekcji instancji klasy Od-
dział kopiowane są odwołania do obiektów Adres; problemem jest stwierdzenie do ja-
kiego stopnia jest to dopuszczalne
" Projekcja  klasa wynikowa zawiera nowe obiekty; jej typ jest nadtypem typu argu-
mentu
39. Model relacyjny, a obiektowy baz danych.
W modelu relacyjnym strukturÄ… danych jest relacja; operacje na danych obejmujÄ… selekcjÄ™,
projekcję, połączenie i operacje na zbiorach. Ograniczenia integralnościowe w tym modelu to:
klucz podstawowy, klucz obcy, zawężenie dziedziny, unikalność wartości, możliwość nada-
wania wartości pustych/niepustych.
W modelu relacyjnym baza danych jest zbiorem relacji. Każda relacja posiada swój tzw.
schemat, który składa się z listy atrybutów. Schemat relacji R jest często oznaczany jako
41
R(A1,A2,& ,An), gdzie A1,& ,An oznaczają atrybuty. Liczbę atrybutów składających się na
schemat relacji nazywamy stopniem relacji.
Każdy atrybut posiada swoją domenę, zwaną także dziedziną. Definiuje ona zbiór wartości
jakie może przyjmować atrybut poprzez określenie tzw. typu danych.
OGRANICZENIA RELACYJNEGO MODELU DANYCH
" Płaskie, jednowymiarowe struktury danych  jedyną strukturą dostępną w relacyjnym
modelu danych jest krotka, czyli płaska lista prostych wartości.
" Potrzeba sztucznych kluczy podstawowych  potrzeba jednoznacznej identyfikacji po-
jedynczych danych wymaga rozszerzania schematów relacji o sztuczne klucze pod-
stawowe. Dotyczy to przypadków, gdy zdefiniowane atrybuty nie gwarantują unikal-
ności wartości poszczególnych danych.
" Semantyka niestandardowych operacji musi być implementowana poza bazą danych 
relacyjny model danych pozwala na korzystanie jedynie z ograniczonego zbioru pro-
stych predefiniowanych typów danych.
" Brak pojęcia związków  relacyjny model danych nie obejmuje pojęcia związków
między danymi, nie mogą więc one być składowane w bazie danych. Zależności mię-
dzy kluczem obcym a podstawowym służą jedynie do weryfikacji poprawności da-
nych i nie mogą być wykorzystane do nawigacji między danymi. Związki między da-
nymi są kreowane dynamicznie przez operacje połączenia. Systemy relacyjne realizu-
jąc operacje połączenia dopiero  w locie ustalają powiązania między danymi.
" Brak hierarchii typów  brak możliwości modelowania hierarchicznych zależności
między kolekcjami danych, między którymi zachodzi relacja podzbioru.
Podstawowym pojęciem obiektowego modelu danych jest pojęcie obiektu, który umożliwia
reprezentowanie cech strukturalnych i behawioralnych obiektów świata rzeczywistego. Struk-
tura obiektu jest opisana przez zbiór atrybutów i związków nazywanych łącznie cechami
obiektu. Wartościami atrybutów mogą być wystąpienia prostych typów danych lub obiekty
składowe. Wartościami związków są referencje na inne, zewnętrzne obiekty. Zbiór wartości
wszystkich atrybutów i związków tworzy stan obiektu. Z kolei własności behawioralne obiek-
tu są reprezentowane przez zbiór dedykowanych procedur zwanych metodami.
Obiekty sÄ… jednoznacznie identyfikowane za pomocÄ… systemowego atrybutu nazywanego
identyfikatorem obiektu. Wartości tego atrybutu są unikalne i niezmienne.
Wewnętrzna struktura obiektu oraz implementacja metod są ukryte przed użytkownikami
obiektu. Mówi się, że są to prywatne własności obiektów, niedostępne z zewnątrz. Dostęp do
obiektów umożliwia ich publiczny interfejs, czyli wywołania metod obiektu. Metody obiektu
są wywoływane przez wysyłanie do obiektu odpowiednich komunikatów.
Obiekty o tej samej strukturze i metodach należą do tej samej klasy obiektów. Klasy posiadają
dualną naturę. Z jednej strony są odpowiednikami typów danych. Są definicjami własności
obiektów. Z drugiej strony klasy są modułami programowymi, które zawierają implementację
funkcjonalności typów danych.
Klasy mogą być definiowane jako specjalizacje innych klas. Klasa wyspecjalizowana jest
nazywana podklasą i dziedziczy ona cechy i metody swojej nadklasy. Dziedziczenie umożli-
wia współdzielenie implementacji klas. Dodatkowo klasa wyspecjalizowana jest podtypem
swojej nadklasy. Umożliwia to polimorficzne przetwarzanie kolekcji klas i dynamiczne wią-
zanie przesyłanych komunikatów z metodami klasy właściwej dla danego obiektu.
40. Składowe internetowego modelu zarządzania siecią.
Internetowy model zarządzania siecią składa się z:
42
" Bazy danych informacji zarzÄ…dzania (Management Information Base)  baza danych
opisująca sprzęt komputerowy, na którym działa klient SNMP. Jest to zbiór opisanych
formalnie obiektów, z których każdy reprezentuje konkretny rodzaj informacji. Obiek-
tami MIB można zarządzać za pomocą protokołu SNMP poprzez system zarządzania
sieciÄ…. Obiekty zawierajÄ… informacje potrzebne systemowi zarzÄ…dzania i sÄ… przecho-
wywane jako zbiór zmiennych MIB.
" Struktury informacji zarzÄ…dzania (Structure of Management Information)  zawierajÄ…
model informacji zarządzania, dozwolone typy danych oraz reguły tworzenia klas in-
formacji zarzÄ…dzania; stÄ…d wywodzÄ… siÄ™ wszystkie obiekty MIB.
" Protokołu SNMP
" Funkcji zabezpieczajÄ…cych i administracyjnych
41. Protokół SNMP.
Simple Network Management Protocol  standard protokołu używanego do nadzoru i zarzą-
dzania różnymi elementami sieci telekomunikacyjnych, takimi jak routery, przełączniki,
komputery czy centrale telefoniczne.
Protokół SNMP zakłada istnienie w zarządzanej sieci dwóch rodzajów urządzeń: zarządzają-
cych i zarzÄ…dzanych. UrzÄ…dzenie (komputer) jest zarzÄ…dzajÄ…cym (NMS, Network Manage-
ment Station), gdy jest na nim uruchomiony odpowiedni program, manager SNMP. UrzÄ…-
dzenie jest zarządzane, jeśli działa na nim program agent SNMP.
W procesie zarządzania używane są bazy MIB, czyli zbiory zmiennych, które manager SNMP
w zależności od uprawnień może odczytać lub zmienić. W tym celu manager SNMP kontak-
tuje się z agentem na danym zarządzanym urządzeniu, wykorzystując jedno z dwóch wcze-
śniej skonfigurowanych haseł:
" Hasło odczytu, tzw. public community,
" Hasło zapisu, tzw. private community.
Odczytanie wybranej zmiennej daje managerowi określoną informację o stanie danego ele-
mentu sieci, podczas gdy zapis do danej zmiennej pozwala mu na sterowanie zachowaniem
siÄ™ urzÄ…dzenia w sieci.
Oprócz operacji odczytu i zapisu zmiennych w agencie przez managera istnieje również moż-
liwość takiego skonfigurowania agenta, aby sam poinformował danego managera o zmianie
swojego stanu w przypadku zajścia określonego zdarzenia. Odbywa się to przy pomocy wysy-
łanego przez agenta komunikatu TRAP lub INFORM. SNMP domyślnie działa na porcie 161
TCP oraz UDP.
42. Infrastruktura bezprzewodowej sieci komórkowej.
Na infrastrukturę bezprzewodowej sieci komórkowej składają się:
" Stacja ruchoma (abonencka) MS (Mobile Station)  jest to niezbędne wyposażenie do
dostępu do usług telekomunikacyjnych GSM PLMN (Public Land Mobile Network 
publiczna sieć lądowej łączności ruchomej). Pojęcie to dotyczy ruchomych urządzeń
końcowych i może również dotyczyć wyposażenia urządzeń końcowych i przystawek
do tych urządzeń. Niektóre z rozwiązań stosowanych konfiguracji znajdują swoje od-
bicie w oznaczeniach klas stacji ruchomych.
W systemie GSM przewidziano stosowanie różnych stacji ruchomych: przewoz
nych,
noszonych i doręcznych. W skład stacji przewoz
nej wchodzi oddzielna antena, mikro-
telefon z klawiaturą i odrębnie instalowany głośnik. Głośnik wraz z wbudowanym do
niego tzw. układem głośnomówiącym umożliwia prowadzenie rozmów przez kierow-
cÄ™ bez potrzeby odrywania rÄ…k od kierownicy. Wygodnym zamiennikiem urzÄ…dzenia
43
stacji przewoz
nej jest montowana w samochodzie specjalna kieszeń, do której wkłada
się miniaturowe urządzenie noszone, powodując automatyczne jego przekształcenie na
urzÄ…dzenia przewoz
ne.
Obecnie najczęściej używane są miniaturowe urządzenia doręczne. W takim urządze-
niu mieści się całość wyposażenia wraz z mikrotelefonem, klawiaturą, anteną i aku-
mulatorem. Korzystanie z urządzenia noszonego wymaga uzupełnienia wyposażenia o
oddzielnÄ… Å‚adowarkÄ™, najlepiej zasilanÄ… z sieci energetycznej.
Każda stacja abonencka składa się z urządzenia, wbudowanej lub zewnętrznej anteny i
karty SIM. Mikrotelefon i klawiatura mogą stanowić całość z resztą wyposażenia (sta-
cje doręczne) lub mogą być wykonane jako odrębna jednostka (duża stacja nośna lub
stacja przewoz
na).
" Stacja bazowa, BTS (Base Transceiver Station)  w systemach łączności bezprzewo-
dowej urządzenie (często z wysokim masztem) wyposażone w antenę fal elektroma-
gnetycznych, łączące terminal ruchomy z częścią stałą cyfrowej sieci telekomunika-
cyjnej.
Pojedyncza stacja bazowa może obejmować swoim zasięgiem jedną lub więcej komó-
rek sieci telekomunikacyjnej. Terminal użytkownika korzysta z tej stacji bazowej, z
której sygnał jest w danym punkcie (momencie) najsilniejszy, w razie potrzeby zmie-
nia automatycznie dotychczasową stację, następuje przełączenie połączenia radiowego
do innej stacji bazowej.
Typowe wyposażenie stacji bazowej obejmuje baterie (do zasilania awaryjnego), pro-
stownik (do ładowania baterii oraz do zasilania stacji napięciem 48 V), wydajną kli-
matyzacjÄ™, grzejnik, wentylator awaryjny (na wypadek awarii klimatyzacji), centralkÄ™
alarmową (do przekazywania alarmów do centrum eksploatacji i utrzymania sieci),
urządzenia radiolinii i urządzenia radiowe obsługujące ruch generowany przez użyt-
kowników BTS.
" Kontroler stacji bazowej, BSC to sterownik stacji bazowej sieci bezprzewodowych.
Pełni nadzór nad kilkunastoma bądz
kilkudziesięcioma stacjami bazowymi. Steruje on
takimi funkcjami jak przełączanie połączeń w ramach nadzorowanych przez siebie
stacji.
" Mobile Switching Centre, MSC  cyfrowa centrala telefoniczna będąca elementem
sieci szkieletowej telefonii komórkowej. Głównym zadaniem MSC jest zestawianie
rozmów i komutacja łączy na czas transmisji. Dodatkowo realizowane są zadania cha-
rakterystyczne dla sieci mobilnych, takie jak autoryzacja i uwierzytelnianie.
43. Zadania rejestrów HLR/VLR podczas tworzenia po­
łączenia w sieci komórkowej.
HLR (Home Location Register)  Rejestr abonentów macierzystych  element infrastruktury
telekomunikacyjnej, używany w sieciach telefonii komórkowej do przechowywania informa-
cji o abonentach, które mogą przydać się podczas zestawiania i obsługi połączeń. HLR prze-
chowuje dane należące tylko do abonentów macierzystej sieci.
VLR (Visitor Location Register)  rejestr abonentów gości  zawiera dokładne dane o poło-
żeniu danego terminala, czyli numer sektora, stacji bazowej  komórki oraz tzw. LAI (Loca-
tion Area Identity) lub RAI (Routing Area Identity), pozwalajÄ…ce na lokalizacjÄ™ i zestawienie
połączenia.
Połączenia głosowe i wideo rozmowy są realizowane za pomocą komutacji łączy dzięki cen-
tralom MSC.
44
" Gdy rozmowa jest zestawiana do danego abonenta, jest ona kierowana do GMSC (Ga-
teway Mobile Switching Centre  centrale, do których kierowane są wszystkie połą-
czenia do abonentów danej sieci.
" GMSC wysyła zapytanie do HLR przechowującego dane tego abonenta (w zapytaniu
przesyła numer telefonu użytkownika (MSISDN) do którego zestawiana jest rozmo-
wa.
" HLR na podstawie numeru MSISDN w zapytaniu z GSMC znajduje rekord z danymi
tego abonenta. Rekord ten zawiera między innymi adres VLR powiązanego z MSC na
terenie którego znajduje się ten abonent oraz numer IMSI (unikalny numer przypisany
do każdej karty SIM w sieci GSM lub UMTS, jednoznacznie ją identyfikujący) po-
wiÄ…zany z danym numerem MSISDN.
" HLR przesyła do VLR obsługującego aktualnie tego abonenta żądanie przyznania
numeru MSRN (Mobile Station Roaming Number) używając jako identyfikatora abo-
nenta przypisany mu numer IMSI.
" VLR z puli dostępnych mu numerów przydziela pewien numer MSRN temu abonen-
towi (na czas zestawiania rozmowy) i zwraca tÄ™ informacjÄ™ do HLR.
" HLR zwraca numer MSRN do GSMC, która na bazie tego numeru może przekierować
rozmowę do odpowiedniego MSC (obsługującego abonenta do którego zestawiana jest
rozmowa).
44. Schematy XML: opis dokumentów w XML.
Schemat XML służy do definiowania struktury dokumentu XML. Pozwala on na:
" zdefiniowanie elementów dokumentu,
" zdefiniowanie atrybutów poszczególnych elementów,
" określenie, które elementy są zagnieżdżone (hierarchia elementów),
" określenie kolejności elementów,
" zdefiniowanie wartości elementów,
" określenie typu wartości elementów i atrybutów,
" zdefiniowanie domyślnych i stałych wartości elementów i atrybutów.
Przykładowy dokument XML:

xsi:schemaLocation="http://localhost note.xsd">>
Rambo I
5
10

Definicja XML Schema:











45

45. Wbudowane w XML typy danych, przestrzenie nazw,
niestandardowe typy danych.
PRZESTRZEC
NAZW
Format XML nie zawiera predefiniowanego zestawu znaczników. Nazwy znaczników i ich
znaczenie są ustalane przez twórców dokumentów i aplikacji. Powstaje wiele słowników
dziedzinowych w postaci zbiorów znaczników. Autorzy dokumentów powinni móc korzystać
w jednym dokumencie z wielu słowników i dodawać własne. W takim wypadku pojawia się
ryzyko konfliktów nazw znaczników.
Rozwiązaniem problemu potencjalnych konfliktów nazw znaczników są przestrzenie nazw.
W przypadku wykorzystywania w dokumencie kilku definiowanych niezależnie zbiorów
znaczników, z każdym zbiorem związana jest przestrzeń nazw określająca ich położenie. Z
przestrzeniami nazw wykorzystywanymi w dokumencie wiązane są prefiksy, którymi następ-
nie poprzedzane są nazwy znaczników. Jedna przestrzeń nazw może być wskazana jako do-
myślna  znaczniki z niej pochodzące nie będą poprzedzane prefiksem.
Definiowanie przestrzeni nazw odbywa siÄ™ przez podanie specjalnego atrybutu
xmlns:prefiks_przestrzeni. Wartością atrybutu jest URI (Uniform Resource Identifier  ciąg
znaków identyfikujący zasób internetowy) przestrzeni nazw. Przestrzeń zdefiniowana w ele-
mencie nadrzędnym morze być wykorzystywana w podrzędnych.
Przykład poniżej przedstawia dokument XML wykorzystujący znaczniki z dwóch przestrzeni
nazw. Przestrzenią domyślną (bez prefiksu) jest http://www.w3.org/HTML/1998/html4. Dru-
ga przestrzeń to http://mysite.com/employees z odpowiadającym jej prefiksem  emp . Obie
przestrzenie definiują znacznik przypisując mu inne znaczenie. Dzięki przestrzeniom
nazw i odpowiadającym im prefiksom możliwe jest jednoczesne wykorzystanie obu znaczni-
ków w sposób umożliwiający ich rozróżnienie aplikacji, która będzie przetwarzać
dokument.
xmlns:emp="http://mysite.com/employees">



Employees

Scott

2300

WBUDOWANE TYPY DANYCH
XML Schema posiada wiele wbudowanych typów danych. Najczęściej używane to:
" xs:string

John Smith
" xs:decimal  liczba rzeczywista, do 18 cyfr

999.50
46
" xs:integer  liczba całkowita

999
" xs:boolean  true, false, 0, 1

999
" xs:date  data w formacie yyyy-mm-dd

2002-09-24
" xs:time  czas w formacie hh:mm:ss

09:00:00
" normalizedString  pochodna typu string, parser XML usunie z ciÄ…gu znaki nowej li-
nii, powrotu karetki i tabulatory

John Smith => John Smith
" token  również pochodna typu string, parser XML usunie z ciągu znaki nowej linii,
powrotu karetki, tabulatory, początkową i końcową spację oraz podwójne spacje

John Smith => John Smith
" dateTime  data i czas w formacie  yyyy-mm-ddThh:mm:ss (T  poczÄ…tek sekcji cza-
su)

2002-05-30T09:00:00
" duration  interwał czasowy w formacie  PnYnMnDTnHnMnS

P5Y2M10DT15H - 5 lat, 2 miesiÄ…ce, 10 dni, 15 godzin
NIESTANDARDOWE TYPY DANYCH






46. Protokół SOAP: przeznaczenie, budowa wiadomości,
atrybuty.
SOAP (Simple Object Access Protocol) to prosty protokół komunikacyjny oparty na języku
XML, umożliwiający przekazywanie wywołań zdalnych komponentów zarejestrowanych w
sieci komputerowej. SOAP może współdziałać z dowolnym niskopoziomowym sieciowym
mechanizmem transportowym, np. http, https, smtp, rmi.
Podstawowymi znacznikami wykorzystywanymi do budowy komunikatów SOAP są:
" - otacza cały komunikat,
"

- zawiera informacje nagłówkowe,
" - zawiera informacje o żądaniu i odpowiedzi,
" - opisuje błędy, jakie wystąpiły podczas przetwarzania wywołania.
47
Protokół SOAP umożliwia wywoływanie komponentów w dwóch trybach: (1) Remote Proce-
dure Call (RPC) i (2) dokumentowym (document-oriented). Tryby te różnią się formą przeka-
zywania parametrów. W trybie RPC wywołanie ma charakter tradycyjny  komponentowi
przekazywana jest lista parametrów formalnych wraz z ich bieżącymi wartościami. W trybie
dokumentowym usługa otrzymuje tylko jeden parametr wywołania, którym jest dokument
XML.
Wywołania komponentów usługowych mogą mieć charakter synchroniczny lub asynchro-
niczny. W trybie wywołania synchronicznego aplikacja klienta wysyła żądanie uruchomienia
zdalnej funkcji biznesowej i wstrzymuje pracę aż do chwili otrzymania wyników jej realiza-
cji. W trybie wywołania asynchronicznego aplikacja klienta wysyła żądanie uruchomienia
zdalnej funkcji biznesowej lecz nie oczekuje na jej wynik, kontynuując działanie. Zwykle tryb
synchroniczny jest wykorzystywany przez komponenty RPC, natomiast tryb asynchroniczny
 przez komponenty dokumentowe.
Przykładowy dokument żądania SOAP został przedstawiony poniżej. Dotyczy on wywołania
komponentu o nazwie  demo , zawierajÄ…cego funkcjÄ™  multiply(int val1, int val2) . Komuni-
kat zawiera sparametryzowane wywołanie funkcji  multiply(3,2) .

soap:encodingStyle="http://www.w3.org/2001/12/soap-encoding">


3
2



Przykładowy komunikat odpowiedzi SOAP został przedstawiony poniżej. Dotyczy on wywo-
Å‚ania komponentu o nazwie  demo , zawierajÄ…cego funkcjÄ™  multiply(int val1, int val2) .
Przykład obrazuje komunikat wynikowy, przekazujący klientowi rezultat wywołania funkcji
 multiply  liczbÄ™ 6.

soap:encodingStyle="http://www.w3.org/2001/12/soap-encoding">


6



47. Język Java: koncepcje, architektura systemu.
Java jest wysoko poziomowym, kompilowanym, obiektowym językiem programowania z
silną kontrolą typów. Składnia Javy jest wzorowana na C/C++. Jednym z założeń projekto-
wych Javy było stworzenie języka wzorowanego na C++ ale bezpieczniejszego, dlatego w
Javie nie ma na przykład wskaz
ników. Inne założenie projektowe dotyczyło przenośności
programów w Javie. Ponieważ Java m.in. została zaprojektowana z myślą o uruchamianiu
programów pobieranych przez sieć, język musiał być tak zaprojektowany i wyspecyfikowany,
by efekt działania programu nie zależał od tego, jakiej implementacji języka użyto. Ciekawą
cechą Javy jest to, że kompilator Javy nie generuje kodu maszynowego, lecz kod pośredni,
który jest wykonywany przez wirtualną maszynę Javy. Programy w Javie składają się z klas.
48
Wykonanie całego programu w Javie polega na wykonaniu metody main z głównej klasy pro-
gramu. Metoda main musi być przygotowana na przyjęcie jako argumentu tablicy napisów,
zawierającej argumenty podane w wierszu polecenia przy wywołaniu programu:
public static void main (String[] args) {}
System programowania Javy składa się z dużej liczby klas definiujących obiekty różnego
typu. Klasy te są pogrupowane w hierarchicznie ułożone pakiety związane z pewnym kon-
kretnym zastosowaniem języka. Oto najważniejsze z nich:
" java.lang
" java.io
" java.util
" java.math
" javax.swing
" java.applet
48. Język Java: konstruktory, pakiety, interfejsy.
Konstruktor jest specjalnym rodzajem metody. Służy do tworzenia nowych obiektów klasy,
w której jest on zadeklarowany. Jego nazwa musi być taka sama jak nazwa klasy, w której
jest zadeklarowany. Dla konstruktora nie podaje się typu wyniku. Liczba parametrów kon-
struktora może być dowolna. Definicja języka gwarantuje, że nie da się utworzyć żadnego
obiektu, bez jednoczesnego wywołania konstruktora. Jest to niezwykle cenne, bo oznacza, że
mamy gwarancję, że każdy utworzony obiekt zostanie zainicjowany w określony przez nas
sposób. To jak ma wyglądać inicjalizacja obiektu opisujemy w treści komentarza, zwykle są
to przypisania wartości do poszczególnych atrybutów, można też wywoływać metody. Jeśli
sami nie zdefiniujemy konstruktora, to kompilator sam wygeneruje bezargumentowy kon-
struktor domyślny.
Dla przejrzystości klasy pogrupowane są w hierarchicznie ułożone pakiety. Każdy pakiet
grupuje klasy związane z pewnym szerokim zakresem zastosowań języka np. java.io (klasy
wejścia-wyjścia), java.util.prefs (klasy użytkowe do obsługi preferencji) czy java.awt (system
obsługi trybu graficznego). Hierarchię klas oddają nazwy pakietów, które skonstruowane są
podobnie jak ścieżki dostępu do plików. Na przykład klasa Preferences znajdująca się w pa-
kiecie java.util.prefs ma pełną nazwę: java.util.prefs.Preferences, co oznacza:
" java - pakiet należy do zestawu standardowych pakietów Javy,
" util - to różnego typu klasy użytkowe (pomocnicze) głównie organizujące obsługę
różnego typu struktur danych,
" prefs - system obsługi preferencji w sposób niezależny od platformy, w którym prefe-
rencje systemowe i użytkownika są składowane w postaci hierarchicznego rejestru,
" Preferences - konkretna nazwa klasy.
Zwykle po to tworzymy klasy by tworzyć ich egzemplarze. Okazuje się jednak często, że de-
finiujemy klasy, które z założenia nie będą nigdy miały swoich egzemplarzy. Takie klasy na-
zywamy klasami abstrakcyjnymi. Wbrew temu, co mogłoby się wydawać na pierwszy rzut
oka, te klasy pełnią bardzo ważną rolę przy projektowaniu hierarchii klas. Pozwalają bowiem
na wyabstrahowanie wspólnych cech wielu definiowanych pojęć (klas) i jawne wskazanie, że
wszystkie dziedziczące klasy muszą te cechy posiadać.
Czasami w klasie abstrakcyjnej chcemy opisać tylko interfejs, bez żadnych danych ani im-
plementacji metod. Ponieważ takie wyabstrahowanie samego interfejsu jest bardzo ważne w
Javie nadano mu specjalną postać składniową i nazwano ją interfejsem.
49
49. Aplety Javy.
Dość często Java jest kojarzona z narzędziem przeznaczonym do pisania specjalnych progra-
mów, tzw. apletów, umieszczanych na stronach WWW. Wprowadzenie tego elementu do
języka Java miało ogromne znaczenie w rozwoju Internetu. Zastosowanie apletów umożliwiło
tworzenie przenośnych, dynamiczne pobieranych programów, które są bezpiecznie urucha-
miane w środowisku przeglądarki internetowej. Dzięki apletom możliwe stało się dostarcza-
nie zmieniających się zawartości dokumentów z wykorzystaniem statycznych stron WWW
tworzonych w języku HTML.
Kod z
ródłowy apletu schematycznie wygląda następująco:
import javax.swing.JApplet; // klasy obsługujące wykorzystanie apletów
import java.awt.*; // pakiet obsługujący grafikę, czcionki itp
import java.util.*; // pakiet użytecznych klas: daty, kalendarze, itp.
public class Aplet_Wakacje extends JApplet
{ /* W tej części deklarujemy metody realizujące zadania apletu oraz opisane niżej
opcjonalne metody init( ), start( ), stop( ), destroy( ) określające tryby wywoływania apletu
lub go usunięcia z przeglądarki.
Nie ma tu głównej metody main, która odgrywa rolę silnika w aplikacjach. W postaci
rozrusznika apletu występuje przeglądarka internetowa, która go wywołuje i wykonuje, loku-
jąc wyniki na wyświetlanych stronach WWW */
}
Do głównych metod odpowiedzialnych za przepływ sterowania podczas działania apletu na-
leżą: init, start, stop, destroy . Znaczenie tych metod jest następujące:
" init - wykonuje siÄ™ tylko jeden raz, gdy strona WWW zawierajÄ…ca aplet po raz pierwszy
jest ładowana. Jeśli opuścimy stronę WWW zawierającą aplet (bez zamknięcia przeglą-
darki) i wrócimy na nią, metoda init nie będzie wykonana ponownie;
" start - metoda odpowiadająca za wykonanie pracy apletu jest wykonywana za każdym
razem, gdy strona, na której znajduje się aplet, staje się stroną bieżącą w przeglądarce.
" stop - jest wykonywana, gdy do przeglądarki jest ładowana następna strona WWW;
" destroy - zasoby apletu zwalnia się jeden raz, kiedy aplet kończy swoje działanie.
UWAGI.
1) Zakresy pytań: 1  7 systemy rozproszone; 8  12 symulacje komputerowe;
13  26 systemy sztucznej inteligencji; 27  29 algebry Boole a; 30  35 ma-
tematyczne modelowanie systemów; 36  39 obiektowe bazy danych; 40  43
systemy zarzÄ…dzania sieciami komputerowymi; 44  49 zaawansowane sys-
temy programowania.
2) Zakres 1  26 jak dla specjalności techniki multimedialne.
50