UL/FRI/UNI-RI/MIS/Izpiti/Ustni

Stran je v delu prečiščen članek iz napisanih vprašanj

Petrijeve mreže

Zapis Petrijeve mreže z matrikama (D ⁺ , D ⁻ , pogoj za vžig, izračun vektorja naslednjega stanja)

Napišemo matriki D ⁻ (vhodna funkcija) in D ⁺ (izhodna).

Element i,j matrike D ⁻ pomeni število povezav iz mesta i v prehod j, matrike D ⁺ pa v mesto i iz prehoda j.

Prehod, ki ga predstavlja j-ta vrstica je izbran, če trenutna označitev vsebuje več ali enako žetonov:

Po vžigu prehoda j je nova označitev: o' = o + e_j * (D ⁺ − D ⁻ )

Čas v Petrijevih mrežah.

Petrijeve mreže razširimo z vpeljavo časovnega okna v katerem se mora od izpolnitve pogojev zgoditi vžig.

Če se obenem lahko zgodi več vžigov se lahko odloči naključno, glede na prioriteto, če ni konflikta lahko hkrati, ...

Prevedba avtomata v Petrijevo mrežo

Avtomat je podan z množico stanj A, vhodno abecedo X in izhodno abecedo Z.

Vsako stanje, vhodna in izhodna črka imajo svoje mesto

P = A X Z

Prehode označimo kot pare vhodne črke in stanja (npr. (a1,x2))

T = A X

Vhoda sta iz mest enega stanja in ene vhodne črke.

I = A X

Žeton po vžigu pošljemo v mesti nekega stanje in neke izhodne črke.

O = A Z

Formalni zapis Petrijeve mreže, dualne in inverzne Petrijeve mreže

Places/Mesta, Triggers/Prehodi, Input/Vhodi, Output/Izhodi

C = (P,T,I,O)

Dualna mreža:

C = (T,P,I,O)

Inverzna mreža:

C = (P,T,O,I)

Dosegljivost v Petrijevih mrežah

Imamo začetno označitev in potem vejimo po vseh prehodih, ki se lahko vžgejo.

Če se pojavi cikel, stanje, ki smo ga že videli v drevesu, ali končno stanje(ni dovolj žetonov za katerikoli prehod), tiste veje ne nadaljujemo.

Na koncu prepišemo označitve iz drevesa v množico stanj R(C,o), vključno z začetno označitvijo.

Kako se znebimo inhibicijskega vhoda

Za inhibicijski vhod velja, da je prehod izbran samo v primeru, ko mesto, ki je povezano na inhibicijski vhod, nima nobenega žetona.

Uporabi inhibicijskega vhoda se izognemo tako, da uvedemo novo mesto, ki ima označitev, ki je nasprotna prvotnemu mestu - torej, če je staro mesto brez žetonov, jih novo ima in obratno.

Markovske verige

Zvezne markovske verige

Prehajanje stanj Markovske verige

Globalno in lokalno ravnovesje v Markovskih verigah

Časovna homogenost

Markovski proces je časovno homogen, kadar verjetnostna porazdelitev naključne spremenljivke X(t_{n + 1}) ni odvisna od trenutnega opazovanega časa.

Naključna spremenljivka je časovno homogena, kadar je invariantna za t_n.

Splošen Rojstno-smrtni sistem

Čisti rojstni sistem (v čem se razlikuje od M/M/1, diagram prehajanja stanj, enačba za verjetnost stanja k)

Osnove strežnega procesa

Ergodičnost

Stohastični sistem je ergodičen, kadar je časovno povprečje enako zbirnemu povprečju, ko gre čas T proti neskončnosti.

Zbirno povprečje stohastičnega sistema je:

Strežni sistemi

Deterministični strežni sistem D/D/1 (nariši graf števila zahtev v sistemu v odvisnosti od intenzivnosti prihajanja, nariši graf časa zadrževanja v odvisnosti od faktorja uporabnosti)

Strežni sistem M/M/1 (formule, diagram prehajanja stanj)

Primerjava sistemov D/D/1 in M/M/1 (nariši graf časa zadrževanja v odvisnosti od faktorja uporabnosti)

Primerjava sistemov čistega rojstnega sistema in M/M/1

Omahljiv strežni sistem

Strežni sistem M/M/m (diagram prehajanja stanj, razlaga količin na sliki, kako iz lokalnega ravnovesja izračunat π₁ iz π₀ in π₂ če imamo podan π₁)

Izravnani strežni sistem M/M/m/m (slika prehajanja stanj, formule, Kdaj je sistem poln)

Sistem s končno populacijo zahtev in neskončno strežniki M/M///M (čas strežbe, ali je sistem izgubni, diagram prehajanja stanj, zakaj intenzivnost prihajanja pada čim več zahtev je v sistemu, zakaj intenzivnost strežbe narašča)

Erlangovi in drugi strežniki