cii5 informatica 1 YU ISSN 0350-5596 SISTEM ZA ŠALTERSKO POSLOVANJE V BANKAH IN NA POŠTAH FBČunBtnišhi sistemi dehB Sistem za šaltersko poslovanje je sodobna računalniška oprema za deb v bankah in na poštah, opremljen z ustrezno programsko opremo. Sistem omogoča samostojno ažumo poslovanje - od posameznih operativnih del na šalterjih do zajema podatkov za nadaljnjo obdelavo. Deluje lahko povsem samostojno ali v povezavi z glavnim računalnikom (prenos informacij je rtK^oč prek stalno najetih ali navadnih telefonskih linij). Delovanje sistema tudi ni odvisno od razpoložljivosti računalniških kapacitet glavnega računalnika. Sistem nadome^ raznovrstno opremo, ki se uporablja pri šalterskem poslovanju - od klasičnih mehanografskih strojev, pisalnih strojev do kalkulatorjev in deloma mikročitalni-kov. Sistem za šaltersko poslovanje je savremena računarska oprema za rad u bankama i poštama, opremljen sa odgovar-jajućom programskom opremom. Sistem omogućava samostalno ažurno poštovanje - od pojedinih operativnih poslova na šalterima do zahvata podataka za dalju obradu. Može da radi sasvim samostalno, ili da komunicira sa glavnim računarorn (prenos informacija je moguć preko stalno iznajmljenih Ili običnih telefonskih linija). Rad sistema |e takođe nezavisan od raspoložijivosti računarskih kapaciteta glavnog računara. Sistem zamenjuje raznovrstnu opremu, koja se upotrebljava u šatorskom poslovanju - od klasičnih mehanografskih mašina, pisaćih mašina do kalkulatora i delimično čitača mikrofiševa. ormatica JOURNAL OF COMPUTING AND INFORMATICS Published by INFORMATIKA, Slovene Society for Informatics, Parmova 41, 61000 Ljubljana, Yugoslavia EDITORIAL BOARD: T, Aleksld, Beograd; D. Bitrakov, Skopje; P. Dragojlovič, Rijeka; S. Hođžar, Ljubljana; B. Horvat, Maribor; A. Manđžić, Sarajevo; S. Mihalić, Varaždin; S. Turk, Zagreb EDITOR-IN-CHIEF! Anton P. Železnikar TECHNICAL DEPARTMENTS EDITORS: V. Batagelj, D. Vitas — Programming I. Bratko — Artificial Intelligence D. Ćećez-Kecmanovlć — Information Systems M, Exel — Operating Systems B. Džonova-Jerman-Blažič/ ~ Meetings L. Lenart — Process Informatics D. Novak — Microcomputers Neda Papid — Editor's Assistant L. Pipan — Terminology V. RajkoviC — Education M. Špegel, M. Vukobratović — Robotics P. Tancig — Computing ih Humanities and Social Sciences S. Turk — Computer Hardware A. Gorup — Editor in SOZD Gorenje EXECUTIVE EDITOR: Rudolf Murn PUBLISHING COUNCIL: T. Banovec, Zavod SR Slovenije za statistiko, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 41, Ljubljana B. Klemen&ič, Iskra Telematika, Kranj S. Saksida, Institut za sociolégijo Univerze Edvarda Kardelja, Ljubljana J. Virant, Fakulteta za elektrotehniko. Tržaška 25, Ljubljana HEADQUARTERS: Info3:matlca, Parmova 41, 61000 Ljubljana, Yugoslavia Phone: 61-312-988; Telex: 31366 YU DELTA ANNUAL SUBSCRIPTION RATE: USiJ 22 for companies, and US^ 10 for individuals Opinions expressed in the contributions are not necessarily shared by the Editorial Board PRINTED BY: Tiskarna Kresija, Ljubljana DESIGN: Rasto Kirn YU ISSN 0350-5596 VOLUME 10, 1986-NO. 1 Z. Kernend T. Turčič M. Gerkeš B. Lakner F. Dacar I. Verdenlk J. Jamšek I. Konraienko I. Bratko E. Roškar M. Bohaneo ■ M. Gams N. Lavrač N.' Bogunovlć M. Radovan M. Malekovič M. Gams T. Zriirec C O N T E H T S 3 . An Approach to Enlarge the set of control statements of the RATFOR Preprocessor for FORTRAN 7 Logical Models for Computer Structures II 23 SCAN-Converting with a Micro conputer 28 Application of VME Bus for Robot Controllers 32 ■ IBM OperatiiTR system VM/SP 43 An Inductive Learning System Assistant 53 An Expert System for Bank Liquidity Managing 62 Analytical Procedures of Estimation the Overhead Processing Time for a Class of Real-Time Ccnputer Systems. 69 A Model of Deductive Database Inplemented in PROLOG 76 Irplicatlon Problem for Functional Dependencies and Mechanical Theorem Proving 80 MICRO-PROLOG informatica časopis izdaja Slovensko društvo INFORMATIKA. 61000 Ljubljana, Parmova 41, Jugoslavija UREDNIŠKI ODBOR: T, Aleksid, Beograd; D. Bltrakov, Skopje; P. Dragojlovič, Rijeka? S. Hodžar, Ljubljana; B. Horvat, Maribor; A. Mandžić, Sarajevo; S. Mlhalić, Varaždin; S. Turk, Zagreb GLAVNI IN ODGOVORNI UREDNIK: Anton P. Železnikar TEHNIČNI ODBOR: V. Batagelj, D.Vitas — programiranje I. Bratko — umetna inteligenca D. Ćećez-Kecmanovid — informacijski sistemi M. Exel — operacijski sistemi B. Džonova-Jerman-BlažiC — srečanja L. Lenart — procesna Informatika D. Novak — mikroračunalniki Neda Papié — pomočnik glavnega urednika L. Pipan — terminologija V. Rajkovič — vzgoja in izobraževanje M. Špegel, M. Vukobratovič — robotika P, Tancig — računalništvo v humanističnih in družbenih vedah S. Turk — materialna oprema A. Gorup — urednik v SOZD Gorenje TEHNIČNI UREDNIK: Rudolf Murn ZALOŽNIŠKI SVET; T. Banovec, Zavod SR Slovenije za statistiko, Vožarski pot 12, Ljubljana A. Jerman-Blažič, DO Iskra Delta, Parmova 41, Ljubljana B. Klemenčič, Iskra Telematika, Kranj S. Saksida, Institut za sociologijo Univerze Edvarda Kardelja, Ljubljana J, Virent, Fakulteta za elektrotehniko, Trža- ka 25, Ljubljana UREDNIŠT\'0 IN UPRAVA: „Informatica, Parmova 41, 61000 Ljubljana; telefon (061) 312-988; teleks 31366 YU Delta LETNA NAROČNINA za delovne organizacije znaša 1900 din, za redne člane 490 din, za študente 190 din; posamezna številke 590 din. ŽIRO RAČUN: 50101-678-51841 Pri financiranju časopisa sodeluje Raziskovalna skupnost Slovenije. Na podlagi mnenja Republiškega sekretariata za prosveto in kulturo št. 4210-44/79, z dne 1.2.1979, je časopis oproščen temeljnega davka, od prometa proizvodov TISK: Tiskarna Kresija, Ljubljeina GRAFIČNA OPREMA.: RastO Kirn ČASOPIS ZA TEHNOLOGIJO RAČUNALNIŠTVA IN PROBLEME INFORMATIKE ČASOPIS ZA RAČUNARSKU TEHNOLOGIJU I PROBLEME INFORMATIKE SPISANI E ZA TEHNOLOGIJA NA SMETANJETO I PROBLEMI OD OBLASTA NA INFORMATI KATA YU ISSN 0350-5596 LETNIK 10,1986-ST. 1 VSEBINA Z. Keftiencl 3 Jedna mogućnost proširen,1a skupa T. Turčić upravljačkih naredbi RATFK? pre- procesora za POOTRAN ti. Gerkeš 7 Logični modeli računalniških struktur II B. Laknei» 23 Realizacija z mikroračunalnikom F. Dacar I. Verdenlk 28 Uporaba VME vodila pri robotskih krmilnih sistemih J. Jamšek 32 Operacijski sistem VM/SP I. Kononenko 43 Sistem za induktivno u?enje I. Bratko Asistent E. Roškaf M. Bohanec • 53 Ekspertni sistem za pomoč pri M. Gams vodenju bančne likvidnosti IJ. Lavrač N. Bogunović 62 , Analitički postupci u određi- vanju neproduktivne obrade za Jednu vrstu procesnih računai^- skih sastava M. Radovan 69 Model dedu! dužina I linija (i) == RAZMAK) ENDROPROCEDURE =ifkraj procedure 2 ENO ^.kraj modula Slika 2. Kod u RATFOR-u i promeniji va. Zbog ograničenja jezika FORTRAN: - maksimalna dužina simbola je 6 znakova, - laDeäe su brojevi sa maKsimalnora dužinom od ä znakova, - nazivi promenljiva počinju slovnim znakom, deo simbola koji odgovara tekstualnom nazivu procedure ograničen je na 4 znaka. Očigledno je da: - mogiićin tekstualnih naziva ima viäe nego varijacija sa 4 znaka, - nazivi mogu biti slični do te mere da se r.tzlikiiju u samo nekoliko znakova, - dužina tekstualnog naziva je ograničena na neku realnu vrednost (napr.: 40 znakova), pa i", kao rešenje nameče odgovarajući "hash" a I cori ; aio. koji tekstualni naziv pretvara u eoa bt'i'j u opsegu od 1000 do 9999 jer se: - vaiijom cifre (1, 3, 4, ...) ispred tog i.i (lobija labela koj.i se sa velikom ve- fovd ..noćoiii razlikuje od korisničkih labela. Ova l.ihel.i se koristi za označavanje počet-i< .i .-ücerture ; - ì;j>! ■. ..,'.11 jera slova isprod l.og broja dobija se. celoorojna promenljiva koja sn koristi u "issigrted GOTO" naredbi na kraju procedure. i!ici 3. prikazan je sistem prsvodjenja liPrav I j.iiikih naredbi vezanih za procedure, öro,; Koji se dobija "hash " • I ran jtin naziva procedi: ? označen je sa /broj/; 3. METODA PREVODJENOA TEKSTUALNOG NAZIVA U ODGOVARAJUĆI BROJ: "HASH" ALGORITAM "Hash" algoritam koriščen za pretvaranje tekstualnog naziva u odgovarajući broj osniva se na deljenju ASCII kodova znakova velikim prostim brojevima i uzimanjem prvih nekoliko decimalnih cifara rezultata. Ulazni niz znakova A dužine N n;'"i = i-l) b(i)=0 n = MAX (3, n) FOR (i = 3; i < = n; i=i+l) u'|"<■^. b(i) = (b(i-2)/1231.+b(i-1)/n63.+b{i)/881.j* * 3275./9. r=b{n) - i to r(INT(b(n))) ^t^O < = r 1163, p3 = 881 : . - i to_r, c_to_i odgovarajuće funkcije konverzije različitih tipova podataka (Tnteger - real, character - integer). Za različite FORTRAN prevodioce oni mogu imati različite oblike ili se mogu jednostavno izostaviti. 4. ZAKLJUČAK Opisani metod uvodjenja struktuiranih naredbi za rukovanje unutrašnjim potprogramima je poslužio kao osnova za implementiranje makro funkcije za "hash" - iranje raznih tekstual-nin naziva u RATFOR preprocesor. Pomoću te i ostalih postojećih makro funkcija definisane su naredbe tipa PERFORM. PROCEDURE i ENDRO-PROCEDURE. Njihovo koriščenje prilikom pisanja programskih celina u znatnoj meri doprinosi mogućnosti "top-down" projektovanja i razumljivosti koda, dok sa druge strane, ne vezuje za odredjeni jezik, jer se i sam preprocesor a i generisani programski moduli oslanjaju na običan standardni FORTRAN. Na kraju, autori se zahvaljuju prof, dr Danilu Obradoviću sa Instituta za mernu tehniku i upravljanje u Novom Sadu, na korisnim sugestijama datim u toku, razvoja rada. 5. LITERATURA 1. 8.W. Kernighan, P.J.Plauger: Software Tools. Addison - Wesley 1976. 2. J.Martin: Computer Data-base Organization. Prenjtice - Hall, Englewood Cliffs, N.J. 1975. LOGIČNI MODELI RAČUNALNIŠKIH STRUKTUR II MAKSIMILJAN GERKEŠ TEHNIŠKA FAKU LTETA, MAR IBOR VTO ELEKTROTEHNIKA, RAČUNALNIŠTVO IN INFORMATIKA METALNA, MARIBOR TOZD TOVARNA INVESTICIJSKE OPREME UDK : 681 J.517.11/12 POVZETEK: Poljuben označen usmerjen grat z ehim začetnim in končnim vozliščem, pri katerem se vse poti sklenejo med tems vozliščema, jtì preoblikovan v vaso >;aključeno selektorsko operacijo, tudi če vsebuje zanke s končno mnogo pono-vitv.-,n)i. Za izgradi jo iv sekvenči^ih in mikrojJrogramiranih strojev so izdelani postopki dekompozicije s pomočjo karaktGrističnili lastno:;i.i, kar lahko vcH do realizacije, ki ima več sekvenčnih oz. mikroprogramiranih strojev kot začetni inodel. De?ii.' rna je p u,|ilošen me' I operatorja s selektorsko operacijo in ga je možno razgraditi do poljubnih detalj'-?>/. Izdelani so inr.cIüU k'^'ualniških struktur. ABSTRACT: LOGlC.'l, MOn.a-; '.•OR COMc'VJTER STRUCTURES II. Any labelled directed graph with single input and single out; It node in '.vhii.-h ;iU diiictod paths .»'e terminated at the output node, can be modelled with a select operation in the sell loop, even if looi.v? wii.U a Unite nun-.h-u" of repetitions are presented in the initial graph. For a model design of a scq'.Jential or micropi ogrLU-n.r,.xl mascliino procedures were defined, that can lead to realizations %vith some sequential or ivticroprograniiTioj l i-;s, altcwjii initial model was single maschine model. Abstract operator with the ability to decompose it into .iny cequi . c I detail is dofined. Models for well known computer structures were built. ÜVOD: Poljubevv označbo vsiuerj.nx y'. al. , ki iina začetno in eno končno vozlišče in v katerem vse usmerjene poti vodijo od začetnega h končnemu vozlišču lahko preoblikujemo v graf vase / :ljučc3ne .sol -ktorske operacije. Takšno preoblikovanje usinoi jencjn graCa je incžno tudi, če graf vsebuje operacije v zaiikau, ki imajo končno število ponovitev. Iz tccji\ '-òzVcn-^ ".iku tjoljlibeii program, mikro-program, ... rc.ili^.iramo v obliki sekvenčnega stroja oz. mikroprogi atiisko kriuiljcrveoa stvoja. Kadar pa vase zaključena selekfooska opor.icija rabi kot izhodiščni model za snovanje izbrane računalniške strukture lahko s postopki dekompozicije preoblikujemo lo operacijo v sestavljeno vase zaključeno selektorsko operacijo, katere realizacija Inliko v splošnem zsihteva izgradnjo več povezanih sekvenčnih strojev ali mikroprogramsko krmiljenih strojev. Pri dekompoziciji kompleksnih sekvenčnih strojev - kot so naprimcr modeli procesorjev je smiselno uporabiti splošnejši pristop k dekompoziciji in sicer z uporabo karakterističnih lastnosti specifilcacije, katerim podrejamo dekompozicijo izbrane strukture. Odstopanja od karakterističnih lastnosti pa obravnavamo kot izjeme, s katerimi korigiramo osnovno strukturo, dobljeno samo na podlagi ufx^stevapja karakterističnih lastnosti. Za snovanje operatorjev sekvenčnih oz. mikroprogrami- ranih strojev je uporabljen abstraktni pristop, ki omogoča definicijo posplošenega modèla operatorja ter njegovo dekompozicijo do poljubnih detaljev. Predlagani so modeli konkretnih računalniških struktur, izgrajeni s po-močj o opisanih postopkov modeliranja od krmilnih enot / preko pomnilnih struktur do operatorjev.. / 1. PRETVORBA GRAFA OPERACIJ V GRAF VASE ZAKUU-ČENE SELEKTORSKE OPERACIJE Kot iztočnico vzemimo.označen usmerjen graf z enim začetnim in enim končnim vozliščem. Graf naj ne vsebuje operacij v zankah. Vse poti, ki izhajajo iz začetnega vozlišča morajo končati v končnem vozlišču. Vsem operacijskim vozliščem (Op., i = 1, 2, ..., n) pripišemo izjave ki specificirajo naslednjaoperacijska vozlišča. Vsaki usmerjeni poti, ki povezujé začetno in končno vozlišče lahko tedaj priredimo graf samih sekvenčno povezanih operacij. Tak graf - sekvenčno operacijo pa lahko po [l] preoblikujemo v vase zaključeno selektorsko operacijo. Vzemimo, da najdemo v označenem usmerjenem grafu G n-usmerjenih poti, ki vodijo od začetnega h končnemu vozlišču. Tedaj lahko narišemo n-sekvenčnih operacij, s katerimi ponazorimo prehode po grafu G v izbranih trenutkih. Začetna vozlišča teh grafov (sekvenčnih operacij) niso enaka, če je žačetno vozlišče grafa selektor-ska opcracija; enaka so, če je začetno vozlišče opera- cijsko vozlišče. Podobno velja za končna vozlišča, da niso vsa enaka, če je graf zaključen s selektorsko operacijo, drugače so vsa vozlišča enaka. Na sliki 1.1 je podan splošei) primer, če je število neenakih začetnih in končnih vozlišč različno. Poljubno operacijsko vozlišče Op. je določeno z izjavo Q., ki jo pridružimo predhodnemu vozlišču Op^. in v bistvu določa usmerjeno vejo od Op^, k Opj, ali s konjunkcijo k vozlišču Opj usmerjena pot preko več ali ene selektor-skih operacij. "^sako vejo določa ^^v- različnih v splošnem sestav- 1 začetnih Ijena izjava vozlišč operacijska vozlišča \t- različnih končnih vozlišč Slika 1.1: Ponazoritev usmerjenega grafa G z n-usmer-jenimi grafi - sekvenčnimi operacijami Po opisanem postopku pretvorbe se lahko nekatere operacije v vase zaključeni selektorski operaciji ponovijo tudi do n-krat, saj lahko isto vozlišče večkrat "prehodimo" po različnih usmerjenih poteh. Tedaj reduciramo veje, ki se v vase zaključeni selektorski operaciji ponavljajo takole: Q.AOp.VQjAOp.V...yQ.AOp.= Q.AOp. (1.1) Operacije, ki se v vase zaključeni selektorski operaciji ponavljajo (l.l) nadomestimo z eno samo operacijo. Slika 1.2 podaja zgled tako preoblikovanega grafa G, ki ustreza modelu sekvenčncga stroja opisanega v [ij . Slika 1.2: Usmerjen graf G preoblikovan v vase zaključeno sclcktorskó operacijo 1.1. Preoblikovanje operacij v zanki Sedaj sprostimo pogoj, da usmerjen graf G ne sme vsebovati operacij v zanki. Obdržimo pa omejitev, da morajo imeti zanke končno mnogo ponovitev. Tvorimo nov graf, v katerem operacije v zanki ponazorimo kot vozlišča z enim vhodom in enim izhodom. Slika 1.3 podaja zgled takšne pretvorbe, kjer je lahko operacija Op^ tudi sestavljena operacija, ki vsebuje nove operacije v zanki. Slika 1.3: Pretvorba operacije v zanki v vozliščno operacijo Tako dobljen graf sedaj ustreza pogojem, da ga lahko preoblikujemo v vase zaključeno selektorsko operacijo. Ugotovimo lahko, da vsaka operacija v zanki, če govorimo o njeni logični realizaciji v bistvu predstavlja avtonomen sekvenčni stroj. Pri logični realizaciji usmerjenega grafa, ki vsebuje več zank, bi tedaj morali izdelati še toliko sekvenčnih strojev, kolikor je operacij v zanki. Takšen pristop pa je v splošnem preveč tog, zato dcuša-mo operacije v zanki prevesti v koncept ene vase zaključene selektorske operacije oz. enega sekvenčnega stroja. Takoj pripomnimo, da končni cilj ni vedno ena sama vase zaključena selektorska operacija oz. en sekvenčni stroj, ampak da želimo imeti možnost, da sami odločamo o številu vase zaključenih selektorskih operacij oz. o organizaciji sistema. Vzemimo, da smo označen usmerjen graf G, ki vsebuje operacijo Op. v zanki preoblikovali v vase zaključeno selektorsko operacijo, ki jo podaja slika 1.4. Slika l.'l: Graf G preoblikovan v vaso zaključeno selektorsko operocijo Na sliki 1.4 so P^, P^, P^ v splošnem sestavljene izjave oblike: Q., Q^aPj» ••• • Sedaj pa opazujmo graf s slike 1.4 v trenutku, ko se operacija Op. ponovi m-krat. Tedaj lahko narišemo graf na sliki 1.5. m-ponovitev Slika 1.5: Graf G v primeru, ko se operacija Op. ponovi m-krat Sekvenčno operacijo v grafu s slike 1.5 lahko po preoblikujemo v vase zaključeno selektorsko operacijo. Graf na sliki 1.5 tedaj preide v graf na sliki 1.6. Pravkar opisano pretvorbo zančnc opcracije laliko verificiramo tudi s popolno indukcijo in s tem potrdimo pravilnost pretvorbe. Za graf na sliki 1.6 izdelajmo še simbolični zapis: SAP Slika 1.6: Preoblikovaria zančna operacija sel (S, P.): Op OPo 1 . P. , - Op. , 1-1 'i-l P. i+1 Op. i+1 P — Op n ^n P,. — Op,. SAP Ol,), kjer je za izjavo S (in tudi izjave Q., i=l, 2, ...) v praksi snovanja strojne opreme udomačen izraz stanje. Zančni operaciji Op^ smo izjavo S pripisali zato, da zagotovimo enoličnost selektorske operacije - samo ena izmed izjav P^, P^, ..., P., ... , P^, P je lahko naenkrat pravilna. V ta namen vzemimo, da so izjave P^, P^,..., P^ izbra- ne kot konjunktivne kombinacije niza izjav p m-1' ^m-2'" ..., p^, Pq in velja 2'"-n > 1. Tedaj lahko za S izberemo iz preostalih konjunktivnih kombinacij iz niza p , p ,..., p . m-1 m-2 u Z zgornjim primerom smo pokazali, kako je mogoče z dodatno izjavo S ohraniti enoličnost selektorske operacije. Če sta v usmerjenem grafu dve ali več zančnih operacij jih reduciramo postopoma - z nekaj Izkušnjami pa lahko reduciramo tudi vse hkrati. Vzemimo primer, da sta nam pri preoblikovanju grafa G v vase zaključeno selektorsko operacijo preostali dve operaciji v zanki. Slika 1.7 podaja tak primer. Slika 1.7: Preoblikovan greif G z dvema zančnima operacijama Najprej preoblikujemo zančno operacijo Op. in pustimo zančno operacijo Op. nedotaknjeno. Graf s slike 1.7 preide tedaj v graf na sliki 1.8. Slika 1.8: Prvi korak preoblikovanja Postopek jiionovimo nad zančno operacijo Op^ in dobimo 10 graf na sliki 1.9. P Slika 1.9: Preoblikovan graf s slike 1.7 Zapišimo še selektorsko operacijo v simboličnem zapisu: sel: - °Pi-l - P j+1 Op- 1 J+1 P. - Op. SjAP— Opj P. - J S AQ- Op. op. Vzemimo j da so izjavo P^, P^» • • • , Pj» iz f onjunktivnih kombinacij niza izjev; in ,, P., P^ i. 2 Tedaj lahko za S^ in S^ izberemo iz j K-eostalih konjunktiv-nih kombinacij zgornjega niza. Obdelajmo še primer, ko zančna operacija v vase zaključeni selcktorski operaciji tudi sama vsebuje zančno ope-.racijo. Tako oblikovan graf G podaja slika 1.10. Preoblikovanje grafa s slike 1.10 pričnemo tako, da si zanko določeno z izjavo Q zamislimo kot sestavljeno operacijo (Op.). Tedaj preide graf v obliko na sliki 1.4, ki jo ŽG znamo preoblikovati. Če opravimo postopek preoblikovanja, preide graf s slike 1.10 v obliko na sliki 1.11. Ponovno si zamislimo zančni operaciji Op^ kot operaciji Op. in dobimo graf, v katerem sta po dve selcvenčno povezani operaciji, ki ju lahko preoblikujemo po [l] v vase zaključeno selektorsko operacijo. S tem dobimo graf na sliki 1.12. Slika 1.10: Graf G z vgnezdeno zančno operacijo Slika 1.11: Prvi korak pri preoblikovanju vgnezdene zanke Graf na sliki 1.12 pa je s stališča preoblikovanja zančnih operacij enak grafu na sliki 1.7, zato lahko narišemo kar končno obliko grafa vase zaključene selektorske operacije na sliki 1.13. P, P 1 n 1 rop^-M (op Slika 1.12: Drugi korak preoblikovanja vgnezdene zanke Slika 1.13: Preoblikovan graf vgnezdene zanke Posplošitev opisane translormacije na n-vgnezdenih zank je enostavna in lahko shajamo z doslej definiranimi transformacijami. Opravimo pa še preobSikravawje grafa s sUke 1.14. ...... Slika 1.14: Graf G z operacij« v povratni veji zanke Grafu G smo ko?-s sir-.isclno u-;orah > cio:-lej opisanih transformacij. Zato lahkO;nariŠGn-.o k '.r graf vase zaključene selektorske operacije na sliki 1 . 15. Slika 1.15: Graf vase zaključene selektorske operacije za graf s slike 1.14 Z zvezdico označeno operacijo Op^ smo vrisali zato, ker laliko pogosto izvorni grof G preoblikujemo tako kot na sliki 1.14. Sicer bi morali vpeljati namesto vozlišča Op^ na sliki 1.15 vozlišče O^, ki izvai" "nrazno" operacijo. Pri fizičnem snovanju moramo zagotoviti tudi iniciaüUza-cijo operacij v naših grafih. To dosežemo s tem, da v vhodno vozlišče "pripieljemo" izjavo, ki izbere začetno vejo v vase zaključeni selektorski operaciji - sistem postavimo v začetno stanje. 2. DEKOMPOZICIJA VASE ZAKLJUČENE SELEKTORSKE OPERACIJE - SEKVENČNEGA STROJA; NAVZDOLNJE SNOVANJE V tem razdelku se omejimo na dekompozicijo kompleksnih vase zaključenih selektorskih operacij - sekvenčnih strojev. Pri enostavnih sekvenčnih strojih lahko neposredno z uporabo transformacij definiranih v [l] in v 1. razdelku preoblikujemo graf sekvenčnega stroja v želeno obliko. Izhajajmo iz vase zaključene selektorske operacije na sliki 2.1. Slika 2.1: Izhodiščni graf za dekompozicijo Dekompozicijo takšnega grafa lahko pričnemo, če imamo na voljo specifikacijo o operacijah, stanjih in pogojih, ki morajo biti izpolnjeni, da se operacije lahko izvedejo. V splošnem lahko isti graf ob upoštevanju njegovega opisa (specifikacije) razgradimo na množico različnih načinov. kako bo potekala razgradnja in kdaj bo postopek -končan je odvisno od lastnosti operacij in zunanjih zahtev, ki smo jih postavili kot cilje snovanja." Omejimo se na en sam primer dekompozicije sekvenčnega-stroja, ki pa bo pretežno ilustriral karakteristike dekompozicije sekvenčnih strojev. Pri tem bomo uporabili poenostavljen zapis, saj bi bil formaliziran zapis preobsežen. Izhajajmo iz naloge, da je potrebno izdelati procesor, ki izvaja instrukcije kompleksne računalniške arhitekture (CISC), katere opis obsega nekaj sto strani. Že sam zapis selektorske operacije za tako instrukcijsko množico v smislu slike 2.1 bi bil toliko nepregleden, da iz njega ne bi kaj dosti razbrali. Zato uporabimo nekoU- ko splošnejši pristop. Iz specifikacije naše instrukcijske množice ugotovimo, da je splošna zgradba instrukcije npr. takšna: code src 1. rx src 2. rx ... src m.rx dst.wx (2.1) V 2.1 je code ime operacije, iz katerega razberemo tudi tipe operandov, src j . rx so določila operandov ali kar operandi in dst . wx določilo destinacijskega operanda. Naša specifikacija dovoljuje, da lahko oblika 2.1 degenerira v code, v code z izvornimi operandi brez destinacijskega operanda ali code s samo destinacijskim ope-random. Pri izvajanju vsake instrukcije se postavi še niz izjav, ki v splošnem laliko vplivajo na izbiro naslednje instrukcija za izvajanje. Značilna lastnost instrukcijske množice naj bo, da instrukcije i+1 ni možno pričeti dekodirati, dokler ni v celoti dekodirana instrukcija i, čili dokler ni v celoti dekodirana instrukcija i in izvedena zahtevana operacija, ki postavi niz izjav te instrukcije. To lastnost lahko ugotovimo iz imena operacije v instrukciji. Ta opis nam zaenkrat zadošča, da lahko pričnemo z dekompozicijo. Izhajajmo iz slike 2.1 in predpostavimo, da imajo vse instrukcije splošno zgradbo (2.1). Tedaj lahko obdelavo poljubne instrukcijc ponazorimo s tremi sekvenčno povezanimi operacijami in sicer z operacijo dekodiranja instrukcije Od., operacijo izvajanja Oe^ in operacijo vpisa destinacijskega operanda Ow.. Eksplicitna definicija operacij nas ne zanima in jo lahko za konkretno instrukcijsko množico izpeljemo s pomočjo [l] in [2] . Model iz katerega smo izhajali na sliki 2.1 lahko sedaj preoblikujemo tako kot podaja slika 2.2. prerežemo — prerežemo Slika 2.2: Začetni korak dekompozicije Odstopanja bd idealizirane zgradbe instrukcij (2.1) bomo upoštevali kasneje. Takšen pristop nam omogoča, da se v določenih fazah snovanja osredotočimo na karakteristične lastnosti instrukcijske množice in prilagodimo izgradnjo modela tistim lastnostim arhitekture, ki so na določenem nivoju snovanja dominantne. Na ta način imamo ves čas pred seboj bistvo problema in se ne izgubljamo v detaljih. Seveda pa mora končni model naše arhitekture verno posnemati vse njene lastnosti. Lahko se zgodi, da pri takšnem pristopu "vidimo" tudi lastnosti, ki jih "ni" oz. tiste ki niso dovolj karakteristične, da bi jih upoštevali že na tekočem nivoju snovanja, ampak šele kasneje. Skrajna možna posledica je lahko, da je rezultat snovanja nezadovoljiv in je potrei^no postopek snovanja ponoviti. Da minimiziramo subjektivno komponento pri ugotavljanju karakterističnih lastnosti lahko koristimo razmeroma obsežen matematični aparat za analizo sistemov. Graf s slike 2.2 lahko ponazorimo kot tri sekvenčno povezane vase zaključene selektorske operacije. Upoštevamo še, da lahko instrukcije, ki imajo enako operacijo Odj, "enako" operacijo Oe. (odvisno od organizacije operacijske enote) in enako operacijo OWj nadomestimo z eno samo operacijo, če ustrezno prilagodimo izjave P.,. ,P v vseh treh novih selektorskih operacijah. Ta- . 1 n ko dobimo krmilni model na sliki 2.3. Na sliki 2.3 (b) je podan zgoščen graf za sliko 2.3 (a). 2.3 (b) nam bo omogočal dovolj zgoščen zapis, zato nadaljujemo snovanje s tako oblikovanim grafom. Poiskusi-mo sedaj združiti operaciji Od in Ow v eno samo sestavljeno operacijo. V ta namen definirajmo izjavo W-past, ki trdi, da je rezultat operacije Oe^, j = 1,2,..., s določen. Ko postane izjava W-past pravilna se lahko sproži izvajanje operacije Ow. Graf s slike 2.3 (b) preide tako v obliko na sliki 2.4. S tem smo dobili dve sekvenčno povezani sestavljeni operaciji Oi in Oe. Pri tem je Oi že v svoji zanki, kar pomeni, da jo bomo realizirali kot sekvenčni stroj. Tudi opie-racijo Oe bomo realizirali kot sekvenčni stroj, saj so operacije, definirane s kompleksno instrukcijsko množico toliko kompleksne, da zahtevajo pri logični realizaciji dodatno interpretacijo z enostavnejšimi operacijami. Graf na sUki 2.4 (b) lahko preoblikujemo v paralelno operacijo, če dovolimo, da se ob izvajanju operacije Oe instrukcije i paralelno dekodira instrukcija i+1, torej izva- Slika 2.3: Ponazoritev:s tremi sekvenčno ^vezanimi selektorskimi operacijami. izvajanje strežba nadaljevanje Od W-past operacij Od Slika 2.4: Združitev operacij Ow in Od v sestavljeno operacijo Oi janje operacije Oi. Takšna paralelna operacija je možna, če lahko po končanem dekodiranju instrukcije i pričnemo o* z dekodiranjem instrukcije i+1. Dekodiranje instrukcije i+1 se lahko izvede v ccloti, £o ni odvisnosti med izvor- nimi operandi instrukcije i+1 in destinacijskim operan-dom instrukcije i. Sicer je potrebno ob ugotovljeni od-visnosü med operandi, prekiniü izvajanje dekodiranja instrukcije i+1 ter pocakaü, da nastopi W-past, ustreči W-past, ter nadaljevati pri prekinjenem d^odiranju. Izjavo s katero ugotovimo odvisnost poimenujmo z O-past in jo definirajmo takole: O-past postane pravilna, če nastopi odvisnost med izvornimi operandi instrukcije i+1 in destinacijskim operandom instrukcije i, za katero se izvaja operacija De. Na sliki 2.5 sta podana grafa, ki ponazarjata strežbo pasti W-past in O-past. SI. 2.5: Strežba W-pasti in O-pasti Iz sUke 2.5 razberemo, da se strežba W-pasti vrine med izvajanje operacij Op. in Op^. (Od) in da se po končani strežbi izvaja operacija Op^, ki je določena z iqavo , ki jo mora stroj pomniti, da lahko nadaljuje izvajanje. Pri strežbi O-pasti pa se oporacija Op. med izvajanjem spremeni v operacijo On, ki izvede "prazno" operacijo, nato nastopi čakanje na W-past in po končani strežbi W-pasti se ponovi izvajanje operacije Op. (Od). Slika 2.6 podaja paralelno vase zaključeno operacijo Oi Oe. Uvedimo še termina za Oi in Oe za fizično izvedbo in sicer instinikcijski procesor za Oi ter operacijski procesor za Oe. Sedaj imamo na voljo parametre za pričetek definicije krmilnih grafov za instrukcijski In operacijski procesor. Na sliki 2.7 je podan krmilni graf za instrukcijski procesor oz. za sestavljeno operacijo Oi s slike 2.^. Pri tem smo vpeljali še izjavi next in dec, ki omogočata -prva interpretacijo operacij dekodiranja in druga dekodi-. ranje instrukcijskega niza. Nabor potrebnih krmilnih izjav s tem sicer,še ni zaključen, vendar se bomo s takim krmilnim modelom zadovoljili in ga bomo prevedU na izhodiščno organizacijsko shemo instrukcijskega procepor-ja. Zato najprej preoblikujemo graf s sUke 2.7 v gra| vase zaključene selektorske operacije, tako kot jo podaja slika 2.8. Za preoblikovanje smo uporabili postopke 14 W-past Oi i i+1 i+2 Oe i i+1 0-past W-past Oi i i+1 i+2 Oe • i i+1 SI. 2.6: Paralelni model izvajanja operacij opisane v [l] in v 1. razdelku. V naslednjem koraku pa sliko 2.8 prevedemo v mikroprogramsko krmiljen model sekvenčnega stroja po sliki 2.9. Tako dobljeni model še ne izpolnjuje specifikacije naše kompleksne instrukcijske množice. Zato specificiramo, da se instirukcije, katerih pričetek dekodiranja je odvisen od postavljenih izjav Instrukcije v operacijskem procesorju, v celoti dekodirajo in izvedejo v instrukcijskem procesorju. Pri instrukcijah, ki nimajo destinacijskega operanda pa W-past sproži v in- Slika 2.7: Začetni približek k realnemu krmilnemu modelu instrukcijskega procesorja next ' W-past next W-past O-past (Od -next W-past O-past W-past '2 W-past W-ret O-ret W-past dec W-past O-past dec W-past O-past W-past ( Od )On^ ( On^ 2 W-past W-ret S^ in lahko definiramo kot izjavi poljubno izbrani iz niza možnih konjunktivnih kombinacij izjav a^ ^,..., a^. next izjava določa niz a.^ J»---, a Q kot vir, ki določa naslednjo operacijo. Izjava dec določa niz i^ i^kotvirjki določa operacije pri dekodiranju nove instrukcije. Izjava W-ret določa niz r^ ^,..., r^, kot vir, ki določa naslednjo operacijo ter W-ret ob aktivni izjavi O-ret niz p^ ^,..., p^ kot vir, ki določa novo operacijo. Izjava W-past izbira niz /iVW (h-l:0> kot vir, ki določa naslenjo operacijo, ter izjava O-past niz /i V O {n-1:0) kot vir, ki določa naslednjo operacijo. Definiramo še selektorsko operacijo MUX, ki specificira eno izmed izjav next, dec, W-ret. Slika 2.8: Vase zaključena seloktorska operacija za 2.7 MUX, Oq) 0-i>ast .Slik.T2.9: Mikropronramsko krmiljen modol inslrukcijskcya procesorja - začetni približek strukcijskem procesorju izvajanje opcracije On. h) lom z.\kljiicinio snovniije modela instrukcijskeya procesorja; doslej dobljeno blokovno shemo podaja slika 2.10. 1'oikjben postopek opravimo pri snovanju začctjiegn modela opcracijskcfja procesorja. Opcracija Oe s slike 2.5 tako preide v sestavljeno operacijo, katere graf podaja slika 2.11. Pri tem je F-past izjava, ki pove, da se v operacijskem procesorju Izvaja opjeracija, ki bo zahtevala strežbo W-pasti v instrukcijskem procesorju, hkrati pa v le-tem še tece strežba prejšnje W-pasti. Zato je potrebno počakati na zaključek strežbe W-pasti in nato ponoviti mikrooperacijo, ki je bila prekinjena ob strežbi W-pasti. Graf na sliki 2.12 podaja strežbo F-pasti. Izjava enext specificira izvajanje na- O-past Slika 2.10: Začetni približek k blokovni shemi instrukcijskega procesorja Slika 2.11: Začetni krmilni model operacijskega procesorja siednjc mikrooperacije, izjava edcc pa pričetck izvajanja novega mikroprograma, ki interpretira operacijo Os^» katero je določil instrukcijski procesor, če je tudi ready izjava, ki trdi da so vsi parametri za strežbo na voljo, pravilna. W-rct W-ret Slika 2.12: Graf strežbe F-pastì Graf s slike 2.11 po opisanih postopkih preoblikujemo v mikroprogramski model sekvenčnega stroja, katerega graf podaja slika 2.13. Začetno blokovno shemo operacijskega procesorja,dobljenoiz tega grafa, pa podaja slika W-ret MUX, .....ag) l''-pnst •Slika 2.13: Mikroprotjramski model opcracijskcrja procesorja - začetni približek Doslej smo podali le pričetek dekompozicije sekvenčnega stroja (slika 2.1), s katerim smo pričeli razgradnjo. S smiselno uporabo doslej opisanih postopkov lahko krmilno strukturo obeh procesorjev razvijemo do potrebnih detaljev. , Čeprav smo se omejili na en sam primer dekompozicije, so v splošnem postopki razgradnje kompleksnih sekvenč-nih strojev podobni doslej opisanim. Preostane nam še izgradnja modelov operacijskih enot za takšne stroje. Slika 2-14: Blokovna shem a operacijskega procesorja -začetni približek 3. MODEU OPERACIJSKIH ENOT Predpostavimo, da smo za izbrano instrukcijsko množico razvili po postopkih [2] algoritme v simboličnem zapisu ali v poljubnem formalnem jeziku, ki opisujejo operacije določene z instrukcijsko množico na abstraktnem nivoju, primernem za logično realizacijo. Iz tako pripravljenih algoritmov laliko razberemo, katere operacije se izvajajo, katere komponente stanj moramo pomniti, katere komponente stanj dobimo iz instrukcijskega niza oz. zunanjega pomnilnika, katere izjave povzročijo vejit-ve itd. Skratka na voljo imamo vse podatke, da lahko v celoti realiziramo tako krmilno kot operacijsko strukturo sekvenčnega stroja oz. krmilno in operacijsko strukture sckvcnčnili strojev, odvisno ocl tega kcilco smo defi- nirali organizacijo sistema. Načeloma lahko pričnemo 2 izgradnjo modela operacijske enote iz različnih izhodišč. V našem primeru pa definirajmo operacijsko enoto kot selektof^sko operacijo, ki odvisno od pravilnostiizjav P^, P- ,... ,P izvede pripadajočo operacijo nad začetnim 2 n stanjem in producira končno stanje za to operacijo. Model operacijske enote lahko tedaj izgradimo iz selektor-ske operacije, katere graf podaja slika 3.1. Izpolnjenost začetnih pogojev Pi^, j = 1, 2, ..., n lahko ugotavljamo med izvajanjem operacij in sprožimo pasti, če ti pogoji niso izpolnjeni, ali pa smo ugotavljanje iz-IX)lnjenosti teh pogojev že vgradili v krmilne algoritme in jih ugotavljamo s pomočjo vejitev. Slika 3.1= Začetni približek k modelu operacijske enote. ■ V praksi pogosto uporabljamo oba načina. V našem primeru bomo smatrali Pi^ = 1, j = 1, 2,..., n. V splošnem lahko rečemo, da glede na pravilno , j = 1, 2,... .., n najprej izberemo tej izjavi pripadajoče začetno stanje Si., nato aktiviramo izbrano operacijsko enoto, ki izvede operacijo Op^, dobljene vrednosti pa priredimo imenom končnega stanja So^.. Graf s slike 3.1 preide tedaj v obliko na sliki 3.2. V praksi so pogosto končna stanja nekaterih operacij ali njihove komponente hkrati tudi začetna stanja ali komponente operacij, ki se bodo šele izvršile. V ta namen predpostavimo, da imajo začetna stanja do p komponent in ustrezno preoblikujmo prvo selektorsko operacijo s sli:-ke 3.2 v p^alelno selektorsko operacijo nad komponentami stanj po sliki 3.3. Pri tem dovolimo, da so lahko komponente stanj prazne -C.j^=0, j e (1, 2,...,n3 , k£ (1, 2,..., p} . Za končna stanja So^, j = 1, 2, ..., h predpostavimo, da imajo do r komponent. je [1, 2, ..., n] , k £ , 2, ..., r j . Slika 3.4 podaja graf paralelne se-loklorskc opcracije, ki vrednosti Icomponent priredi imo- Si. -v. iz začetnega stanja dobimo vrednosti v,,. _ Op^ (v.) operacija določi vrednosti končnega stanja So. •— w. J } imena končnega stanja dobijo vrednosti Slika 3.2: Model delovanja operacijske enote Slika 3.3: Odjem vrednosti stanj Si^. po komponentah nom končnega stanja So.. Tudi tukaj dovolimo, da se lahko izvedejo prazne prireditve B. = 0. Jk Sedaj pa upoštevajmo, da so laliko končne komponente tudi začetne komponente novih operacij. V ta namen definirajmo tabelarično prireditev imen komponent in B^.j^ novim imenom C^, C^,..., C^, tako da bo v tabeli vsaka komponenta, ki je likrati začetna in končna imela eno samo ime. Nad preimenovanimi komponentami definirajmo novo paralelno selektorsko operacijo, pri kateri načeloma dovolimo, da laliko vsaJco vredrost komponente 18 w ' ,1k )k Slika 3.4: l>ripis vrednosti stanju So^ po komponentah stanja odjemanno ali priredimo (beremo oz. vpišemo). Izjave R.,1^1,2,..., p bodo določale odjem, izjave Rj , j = 1, 2,..., r pa prireditev vrednosti. Izjave j « 1, 2,..., p oz r in k = 1, 2, ..., m bomo v ko-njunkciji z izjavami R. oz. R. uporabili za izbiro vozlišč katerim bomo odjemali vrednosti v^, z = 1, 2,..., m oz. priredili vrednosti w^, 1 =1, 2,...,r. Za opis tako definirane sestavljene paralelne selektorske operacije uporabimo simbolični zapis. Sel: Rj —- sel: Sel: Rg— sel: Sel: R —sel: P Si - ^ Q, — v Im m ^22-^2 V-' Q — v pm m R^ — sel: R — sel: r «12 - - Im m 1 Qrl-^V-^r Qr2 7 (S^ - -r Q - (C ) — W rm m r (3.1) Sestavljena paralelna selektorska operacija je definirana tako, da lahko "preberemo" poljubno pyermutacijo p vrednosti in "vpišemo" poljubno pcrmutacijo do r vrednosti. Na ta način lahko dobimo vrednosti poljubnega začetnega stanja Si^ in priredimo vrednosti poljubnemu končnemu stanju SOj. V praksi običajno ne potrebujemo tako splošne organizacije "pomnilnega prostora", zato lahko pri realizaciji konkretno naloge sestavljeno operacijo (3.1) primerno ■ poenostavinlo. 3.1. Model pomnilne celice Izhajajmo iz selektorske operacije: Sel (V): V — P (Q, Q) (3.2) V — P (Q, D), kjer je P relacija zamenjave vrednosti Q z vrednostjo Q ali vrednosti Q z vrednostjo D. (3.2) preoblikujemo v disjunktivno obliko : VAP (Q,Q) V VAP (Q, D) (3.3) Modelirajmo V, Q, D z izjavami po [l] takole: WE izjava, ki bo ekvivalentna izjavi V, niz izjav, s katerimi modeliramo Q, ter D D niz iz- n-1 o jav, s katerimi modeliramo D. Relacijo zamenjave pa ponazorimo 2 logično ekvivalenco. WEA(Q =Q ,)VWA(Q„ =D J n-1 n-1 n-1 n-1 n-2 n-2_ n-2 n-2 WEA(Q = Q ) VWEA(Q = D ) o o o o Izraz (3.4) poenostavimo in dobimo: Q =Q ,AWEVD n-1 n-1 n-1 q^_2= qn_2awevd^_2a^ (3.5) Q = Q A WEVD A WE o o o (3.5) imenujmo relacije pomnjenja,za pomnilno celico ki jo te relacije opisujejo pa uporabimo simbol na sUki 3.5. D D SEL / VE Slika 3.5: Simbol pomnilne celice tipa zapah 3.2. Model pomnilnika s serijskim odjemom in serijsko prireditvijo Da ne bi ponovno v celoti izvajali vseh relacij tako kot pri pomnilni celici, uporabimo nekoliko poenostavljen zapis. Z Doznačimo vrednost, ki je na vhodu pomnilnika, z D , D D, označimo vrednosti v pomnilniku n n-1 1 (pomnilnih celicah) z Q pa označimo vrednost na izhodu pomnilnika. Z A., i = 1, 2,..., n označimo poljubne konjunktivne kombinacije niza izjav (a ,, a .. m-l m-2 a^), kjer velja 2 Vn, Z izjavo R pa bomo zahtevali prireditve vrednosti, z iz> j avo R pa odjem vrednosti. Sedaj lahko definiramo selektorsko operacijo : Sel: Aj — sel: R —P (Q, Dj) A^ -—sel: R — P (Q, D^) R — P (D^, D ) (3.6) A — sel: n R — P (Q, D ) __n R — P (D^, D) Če upoštevamo model pomnilne celice in simbolični zapis (3.6), lahko kar narišemo eno izmed možnih blokovnih shem takega pomnilnika na sliki 3.6. D Ai RClov ^ A ar [>_n- iZl -C lema » SEL odobritev odjema Slika 3.6: Blokovna shema serijsko organiziranoga pomnilnika 3.3. Model paralelnega pomnilnika Model serijskega pomnilnika posplošimo tako, da bo možno paralelno branje p vrednosti in paralelni vpis do r vrednosti ter s tem logično realizacijo sestavljene paralelne selektorske operacije (3.1). Predpostavimo p >r in definirajmo ADR J., i = 1, 2,..., m,..., ADR^..., ADR^. , ter so ADR J.,..., ADR^^, i in j = 1, 2, ...,' m, poljubne konjunkcije izjav » • • •, o'' pogoju da, če je i = j imamo opraviti z eno in isto konjunktivno kombinacijo iz-jnv a^^ D^ , D^ ^ ,..., D^ so vrednosti na vho- du paralelnega pomnilnika, Q^, Q^ so vred- nosti na izhodu ter V^, V^,... vrednosti v pomnilnih celicah. R^, R^,..., Rp specificirajo branje iz paralelnega pomnilnika, izjave Rj^, R^,..., R^ pa vpis v paralelni pomnilnik. Sestavljena paralelna operacija se tedaj glasi: Sel: Rj — sel: R —sel: P ADR , —P(Q ,V,) pl P 1 ADR pl P2' -P(Qp,V. ADR_ -P(Q,,V ) ADR -P(Q , V ) Im 1' m pm p m R^ — sel: R — sel: r ADRj2-P(V2,Dj) ADR, -P(V ,DJ ADR_-P(V ,D ) Im m' 1 rm m r Paralelna selektorska operacija, ki odloča o vpisu v pomnilne celice sicer ni enolična, vendar hi običajno, da bi istemu imenu komponente stanja skušali hkrati prirediti dve ali več vrednosti. Eno izmed možnih blokoviih shem takega pomnilnika podaja slika 3.7. Slika 3.7: Blokovna shema paralelnega pomnilnika 20 Tak paralelni pomnilnik v praksi omogoča precej več kot realno potrebujemo. Zato ga lahko pri reševanju konkretne naloge primerno poenostavimo. i 3.4. Modeli operatorjev V tem razdelku bomo pod operatorjem razumeli predvsem enote, ki izvajajo operacije določene s selektorskö operacijo kot začetnim krmilnim modelom, ki ga lahko po potrebi razgradimo do primernega abstraktnega nivoja. V ta sklop sodi tudi selektorska operacija s slike 3.2, ki izvaja operacije Op^ (v^). Na sliki 3.8 je ponovno narisan graf selektorske operacije, iz katerega bomo razvili modele operatorjev. Op. v. i w. 1 Slika 3.8: Začetni približek k modelu operatorja Selektorske operacijo zapišimo v disjunktivni obliki : P J A Op^ ( v^ )VP^Op2(v2) V.. .VP^AOp^C v^). ( 3.8 ) Op.(v.) pa pomeni vrednost w., ki jo dobimo kot rezul- J J " j tat operacije. (3.8) laliko tedaj zapišemo: Pj A w J V P^A w^V ... V P^ A (3.9) Vendar (3.9) opisuje samo odjem vrednosti w. iz izhoda operatorja, ne pa tudi izvajanje operacije. Zakaj sedaj nenadoma težave s selektorsko operacijo? Selektorska operacija, kot je definirana, je logični (krmilni) model kamor lahko zapišemo "karkoli" . Če sledimo pot i skozi selektorsko operacijo, laliko rečemo da, če je pravilna Pj potem se izvede operacija Op. nad vrednostmi stanja Si^ in kot rezultat določi vrednosti končnega stanja So.. Ostale poti v selektorski operaciji lahko v tem trenutku ignoriramo. Pri fizični izvedbi modela selektorske operacije pa je tako, da moramo definirati podatkovno poti, definirati logično izvilo .operatorjev, poskrbeti za krmiljenje celotnega operatorja in na koncu odvzeti pravilen rezultat. V ta namen najprej definirajmo realizacijo operacije Opj, i=l,2, ...,n, z operatorjem OP. .V splošnem lahko operatorje realiziramo na dva načina; s pomočjo logičnih tabel ali s pomočjo logičnih izrazov. Slika 3.9 logična tabela ali D logični izraz ^ ^ i o Slika 3.9: Definicija logičnega modela operatorja podaja koncept po katerem operacijo Op^ prevedemo v njen logični model. f in g sta surjektivni preslikavi, f ^ in g ^ pa sta v splošnem relaciji. D. in D^ so nizi pravilnostnih vrednosti izjav, s katerimi smo modelirali vrednosti v. in w. glede na [l] . V splošnem lahko tedaj tudi operatorje ponazarjamo s selektorsko operacijo, saj lahko poljubno logično tabelo prevedemo v disjunktivno obliko prav tako pa tudi poljuben logični izrsiz. Sedaj pa ponovno izhajajmo iz (3.8). Tedaj lahko glede na zgornja izvajanja narišemo naslednjo blokovno shemo operatorja za sliko 3.8 na sliki 3.10. Slika 3.10: Začetni model operatorja Kjer so Op^, Op^,-.., OPj, ^ splošnem zopet selektorske operacijeki jih lahko definiramo takole: Sel: P. Av,^ — 11 1 > OPj (3.10) P.Av.'' — 11 1 Z v. smo označili različne vrednosti začetnih stanj definiranih z začetnim pogojem Pi. (Si.) in z w^^^ vrednosti končnih stanj So^. V splošnem desna stran (3.10) ni eno-1 ična. Sedaj pa definirajmo äe nekatere enalfovrcdnc blokovne sheme operatorjev. Izhajajmo iz grafa na sUki 3.11. Slika 3.11: Preoblikovana '.slektorska operacij.v UgoUjvimc lahko, da s slike 3.11 gratu s slike 3.8. V^el;a namreč : OV...^'OVp.AOp. (v.)VOV...VO (3.11) in P.AO_^(v.)VP,AOp,(v.) (3.12) P AO (v )VP ACp (v ) n n n n n n Ce je P. pravilna tedaj zgornje relacije pr cirff jo v obliko: P^AOpjCv.) kar je enako (3.11). Pri tem je opreci j,i O ^ ■^s■!ni^ana tako, da velja = O , i = l,2,...,n . Blokovno shemo za ta primer podaja slik,' 3 .i:'.. /i.:: ■Slika 3.12: Enalvovrccion za^^ctni niocici operatorja Iz razlogov, ki so snovalcem dobro znani lahko SEL operacijo s slike 3.12 pogosto nadomestimo z Ali operacijo ali s skupnim vodilom s tremi stanji. V praksi se pogosto uporablja tudi poenostavljena blokovna shema operatorja s slike 3.12, ki jo podaja slika 3.13. SEL operatorji niso krmiljeni s P. Slika 3.13: Poenostavljeri mcfdel operatorja Poimenujmo operator s sliKè 3.10 univerzalni operator. Sedaj pa izhajajmo iz krmilnega grafa na sliki 3.14. Slika 3.14: Sestavljena šelektoi-ska operacija kot krmilni model Vzemimo, da lahko notranje selektorske operacije realiziramo z operatorji OP , OP ,..., OP . Tedaj lahko ta-a D .z koj narišemo blokovno shemo za celotno krmilno shemo s slike 3.14 na sliki 3.15. SEL a SEI^ 1 SEL • o SEL z Op. Op, izbira izbira opera- operacije torja , ■ ' Slika 3.15: Model operatorja in krmilna struktura ža krmilni gral s slike 3.14 Nn sliki 3.15 so SliL. krmilili ukazi, tlo knlcrili pridemo s preoblikovanjem iisjav Tj,...,Q^,..., v iiizc okvivalcMlmli izjnv 1X3 iioslopku [l] . Pri snovanju mikroproQramiranih sisiomov so jo ianje utiomačil iz) raz mikroukazi, za cclotno polje pa izraz vcrükalno lunk-cionaliw> polje. V lem smislu sUi na sliki 3.16 poilani 5e blokovni shemi iu struktura krmilncfja polja za sekvenčno in paralelno vezane univerzalne operatorje. M-K SKL SI-: S, ---- SKL Op. OPu Op.. Slika 3.16: Blokovni sliemi in struktura krmilnega polja za sekvenčno in paralelno povezane operatorje Snovanje operatorjev laliko tedaj pričnemo z izdelavo graia, ki je v začetku sclektorska operacija, ki jo po (»trobi razgradimo v sestavljeno opcracijo, sestavljeno iz scicktnrskili, sckvenčnili in paralelnih operacij. Tako dobljen graf pogosto imenujemo krmilni graf operatorja, snj določa precedence o|)oracij pri izvajanju. S r>omočjo krmilnega grafa pa nato izdelamo blokovno shemo o|5era-torja, ki izvede operacije določeno z krmilnim grafom. Nnslotlnji korak je logično snovanje, ki nas pripelje do logične sheme operatorja. 1. ZAKUUČEK rrcdlariani postopki snovanja in izgradnje logičnih modelov računalniških struktur so splošni in niso omejeni samo na snovanje mikroprogramiranlh sistemov. Osnova postopkov so sclektorska, sokvcnčna in paralelna opcracija, ki so lahko UkU vase zaključeno. Z dodajanjem semantike laliko z njimi modeliramo najrazličnejše računalniške strukture na različnih abstraktnih nivojih. Pokazali smo, kako lahko isto al^strakttie strukture uporabljamo tako za snovanje krmilnih mehanizmov kot operatorjev, ki jili le-ti krmilijo. Izkazalo so jo, da v splošnem ni mogoče postaviti ostro meje mod krmilno in operacijsko strukturo izbrane računalniške strukture. Meja je s stališča zunaiijaja opazovalca (uixjrabnika, programerja itd.) določena z.abstrnktnim nivojem na katerem oi>azujcnio obnašanje izbrano računalniško strukture. Od tod izhaja tudi programski model izbrane računalniško strukture za izbrani abstraktni nivo opazovanja. Po drugi strani pa laliko v splošnem Isto računalniško strukturo opazujemo kot krmilno strukturo, operacijsko ali pomml-no strukturo. Ugotovili smo namreč, da v splošnem sestavljene strukturo vsebujejo vse tri komponente. Od konteksta opazovanja je odvisno kako bomo "videli" takšno strukturo. Potrdimo to z zgledom: mikroprogramiraiia krmilna enota jo brez dvoma krmilna struktura, saj določa operacije in njihovo zaix>redje pri izvajanju. Hkrati pa je tudi pomnilna struktura, saj na adrese iz različnih virov odgovarja z različnimi podaji, ne glede na to kaj Ü podatki predstavljajo. V njej laliko vidimo tudi operacijsko strukturo, posebej če jo opazujemo v kontekstu i nstrukcijski niz - mikroprogramirana krmilna enota -m ikroinstrukcija - operacijska enota - izjave po končani operaciji, kjer je krmilna enota prva izmed dveh sekvenčno povezanih operatorjev (operacij ). Takšno metyavo kontekstov opazovanja pri snovanju pogosto uporabljamo, s.-y nam menjava konteksta prikaže problem v novi dimenziji in nas s lem navede na rešitve, do katerih bi laliko težko prišli z drugačnim kontekstom opazovanja. S. LimRATUKA Q] M. Gerkeš: Logični modeli računalniških struktur, Informaüca 3, str. 1 - 12, Ljubljana 1985. [2] C. D. Jones: Software Design: A Rigorous Approach Prentico-Hall International, 1980. £3] J. Vlrant: Preklopne funkcije, strukture in sistemi. Univerza Edvarda Kardelja v Ljubijai»i, Fakulteta za elcktroteliiUko, Ljubljana 1983. [4] M. Gerkeš, M. Pernek, M. Paglavec: Aplikacija biixjlnrnega mikroprocesorja. Poročilo o delu za lo-^ to lOB-l, UUP/HP: RačutuilniSka oprema 03-2370, PORS 3, Visoka teliiuška šola, Maribor, 198-1. Raziskavo je sofinancirala Raziskovalna skupnost Slovenije PoRS 03. RA8TER12AC1JA Z HIKR0RAÖUNALN1K0I1 Barta«r« L«kn«r, Frana« Daa«r Institut JoX«f Stelan, LJubljana UDK : 6813:514.1 V prispevku je apisana rasterizaciJa z nikroraCunalnikam. Ker v mikroračunalniku ni dovolj prostora za predstavitev cele rastrske mreSe, zgradimo najprej model slike, ki je sestavljen ii t!rt, vodoravnih tekstov in pik in s tehniko postopnega preiskovanja ravnine pregledamo model od leve proti desni, postopoma rasteriziraoo in sproti izrisujemo sliko na grafifini napravi. SCAN-CONVERTING WITH A MlCRO-COMPUTER In the article scan-converting with a micro-computer is desoribed. Because ol the lack of memory to save the whole raster grid, we build a model ol a picture. The model consists oi lines, horizontal teKts and dots. Then we sweep the model from left to right with the plape-^weep technique (or scan-line approach), gradually scan-convert and simultaneously draw the picture on a graphics device. 1. UVOD RasterizaciJa je predstavitev Črtne slike s pikami (piksli), ki so razporejeno na doloCenl dvodimenzionalni rastrski'mreSi. Osnovna naloga rasterizacije za Crte je torej raCunanje koordinat pikslov, ki leäe v neposredni bliSini Crte na tej mreSi. Ce imamo v raCunalniku dovolj prostora za predstavitev take mreSe, nimamo nobenih posebnih teSavi uporabimo enega izmed znanih algoritmov ([13, >, s katerim Srtam priredimo ustrezne piksle na mreSi in nato ob pregledovanju te mreüe poSiljamo ustrezne ukaze v izbrano grafitino napravo (npr. matriCni printer). V mikroračunalniku, npr. LSl-11 Sal nimamo dovolj prostora za predstavitev cele rastrske mreSe. Opisali bomo implementacijo preprostega grafičnega paketa na mikroračunalniku. Paket ima procedure za premikanje peresa s spufiCeno in dviqnjono knnicn, pir.;njđ pikslov. Kc j» preiskovalna premica priöla do desnega roba kosa rastrske mreSe, kos mreSe izriSemo, jo inicializiramo in nadaljujemo s preiskovanjsa »odela od leve proti desni (slika 1). Tako smo pri rasterizaciji z nikroraCunalnikon uporabili pristop, ki se v raCunalniSki grafiki pojavlja z imenom "scan-line approach", v računalniški geometriji pa "plane-sweep paradigm". J r — n n -1 n r" "1 _ 1 n _ _ _ Ij 1 _ _ _ _ _ _ _ 1 —1 _ _ _ _ _ _ _ _ — — — d — - — — — — J J — — - — — — — — — — — — — — — — _ -j j „ n J Is s; J J v J J n z 5 7 J i; J J _ > _i 1 2 J J L r" L— C J KOS X. 3. Koi Slika 1: Celotna rastrska rrrcr.a in ponanezni koai 2. OPIS 2H0SUJIV0STI PAKETA Opisani paket za raster i zacijo je namenjen risanju slik z matriCnim printerjem in ima naslednje procedure in funkcije: procedure StartPlotj proced'Vir'e StopPlotj procedure PaperUidth(real); procedure SetU'indowtWxmin, Uyrain, Wxmàx, WymaK; real ) ; procedure SetViewPort 0) then FrintPart; end J endi (• PrintPict *1 Rasterlzacija firt A.2.1. Bresenhamov algoritem ù'rte smo r as t er i r i ra 1 i z inaiJico Bresenhamovega algoritma L2]. Ker izpeljava ni dolga, si jo oglejmo. Vzemimo, da rasteriziramo daljico s krajiSCema (0,0) in (deltàx, deltay). Naj bo deltax > O, deltay > O in deltay <= deltax (1) Daljici prirejamo piksle s koor.dintami (x,y), kjer je J .7 ,inax kos mre?.e. ki ,ie v pomnilnikih O <= X <= deltax in deltay/dBltax»x - t/2 <= y y < deltay/deltax»x +1/2 Tako leSe piksli, ki predstavljajo daljico, v pasu, ki je narisan na sliki 5. Gornjo neenakost preuredimo O <= 2«deltax*y - 2*deltay«x + deltax < -< 2»deltax m imamo O < = kjer je z(x,y) = z(x,y) < 2»delta) 2, ki zadoSäa predpostavkam (1). Naj bo deltax 1= xl - xO in deltay yl - yO z := deltax; y i= yO; PlotOotCxO.yO); for X :» 1 to deltax do begin I t« * - 2*deltayt if z < O then begin I !• z + 2«daltaK; y !■ y + 1 ; end ; PlotDot absy then begin sx :» sgnx; sy «= 0; n <3 absx; b t" 2«absy; end else begin sx j" 0; sy i= sgny; n i k v J KiK^ Di« + / D«; \ Dimn f.f / Uni ; 4 K- X(s') —>- 11 L—-kb.VC.V^L- S0» a to Slika 1 členi nelinearne funkcije, odvisne od geometrije in pozicije manipulatorja. Iskanje oziroma izračun vseh teh členov je inverzni dinamični problem. Za izračun tega modela je bilo razvitih in uporabljenih precej metod /3/, v zadnjem času pa kaže, da je NewtonrEulerjeva metoda najučinkovitejša numerična metoda.za reševanje dinamike industrijskega manipulator-ja v realnem času. V tabeli 1, ki jo podajamo po Hollerbachu /3/, so podana števila množenj in seštevanj-, potrebna za izračun modela po različnih metodah. metoda št.množenj/deljenj St.seštevanj/ odštevanj Lagrange (Uicker-Kahn) 66271 51548 rekurzivna Lagr. (Waters) 70B1 5652 rekurzivna Lagr. (Hollerbach) t388 3586 rekurzivna Lagr. (Hollerbach) 2135 1719 Newton-r-uler 852 738 3. PARALELNO PROCESIRANJE PRI IZRAČUNAVANJU DINAMIČNEGA MODELA Z Newton-Eulerjevo metodo je možen izračun dinamike. v realnem času na srednje velikih mini-računalnikih, kot je npr. PDP 11 /2,3,5/. Ce želimo opraviti ves izračun na mikroračunalniku, moramo poskrbeti za zmogljiv računski sistem. Jasno je, da paralelno procesiranje občutno poveča hitrost računanja. Z nižanjem cene procesorskih komponent je postala zamisel o večprocesorskem krmilniku manipulatorja uresničljiva. Luh in Lin /2/ sta predlagala paralelni način krmiljenja, kjer vsakemu sklepu ma-nipulatorja pripada svoj procesor z lokalnim pomnilnikom ža podatke in program ter globalni pomnilnik za spremenljivke, ki jih potrebuje več procesorjev. Problem razvrščanja nalog po procesorjih je na ta način poenostavljen, saj omogoča iskanje optimalnega, razvrščanja. Boljši način razvrščanja nalog po procesorjih pa je tisti, kjer vsak procesor lahko opravi vsako nalogo. Pri tem načinu zaradi velikega števila nalog ne moremo najti optimuma, temveč se mu . lahko z raznimi hevrističnimi metodami le približamo /4,6/. Na ta način se za manipulator s šestimi prostostnimi stopnjami in šestimi pro- . cesorji čas računanja zmanjša za 40 % glede na način, kjer je vsakemu aktuatorju prirejen svoj procesor. Ta prihranek časa gre na račun dejstva, da pri metodi, ko ima vsak sklep svoj . procesor, prihaja do mrtvega časa, ko en procesor čaka na rezultate drugega. Ta zakasnitev je pri drugem načinu mnogo manjša. Problem strukture robotskega pomnilnika je navezan na tip procesorskih modulov, ki jih uporabljamo, saj čas prencsa podatkov ned 30 posameznimi procesorji glede na vsa potrebna množenja in druge aritmetične operacije, ni kritičen. čas računanja kinematike manipulatorja, to je pretvorbe iz kartezijevih v notranje koordinate, je zanemarljiv v primerjavi s časom računanja celotne dinamike. Morali pa bi ga upoäte-vati, ée bi želeli zgraditi krmilnik s poenostavljenim dinamičnim modelom, torej z zanemarjanjem določenih dinamičnih parametrov sistema (običajno se zanemarja centrifugalni ali Coriolisov pospešek ali oba). VME VODILO VME vodilo predstavlja vmesniški sistem za procesiranje, shranjevanje podatkov in za vodenje perifernih naprav v tesno vezani konfiguraciji. Tako VME vodilo omogoča: - komunikacijo med napravami na vodilu brez motenj njihovih internih aktivnosti - specificira električne in mehanske karakteristike sistema, ki so potrebne, za razvoj in zanesljivo delovanje sistema - specifv-.ira protokol in natančno definira odnose med napravami na vodilu • predpisuje terminologijo in definicije za preci/.en opis sistemskega protokola ■ 'lovoljuje širok spekter različnih naprav na vodilu, ne da bi se zmanjšala kompatibilnost sistema -• omogoča sistem, ki je omejen s sposobnostjo naprav lia vodilu in ne z vodilom samim. Glede na možnosti VME vodila in zahteve paralelnega procesiranja dinamičnega krmiljenja vidimo, da.se ponujata dve alternativni izvedbi krmilnika manipulatorja. Pri prvi izvedbi (si. 2) so vse procesorske enote podrejene centralni enoti, ki skrbi za prenos podatkov med moduli, za povezavo z regulatorskimi enotami in za komunikacijo z uporabnikom (operacijski sistem). Prednost te izvedbe je v tem, da sistem ne izgublja časa s stalnim razsojanjem, komu pripada vodilo ob vsakem trenutku ter prepusti celotno računanje posebej prirejenim procesorskim modulom. V drugi izvedbi (si.3) ima vsak procesor možnost postati nadrejena enota vodila (bus master). Tako se izognemo posebnemu centralnemu procesorju za koordinacijo posameznih procesnih modulov. To delo prepustimo modulom samim in sistemskemu dodeljevalcu vodila (arbitration module). Porazdelitev pomnilnika po modulih vodila je odvisna od posamezne aplikacije. Globalni pomnilnik uporablja glavni sistemski procesor oziroma vsi procesorji za podatke, ki so rezultat ali vhodna veličina v določen podprogram. Lokalni pomnilnik pa uporablja vsak procesor za svoje lokalne spremenljivke.Pri tem lahko ugotovimo, da je zahtevana velikost pomnilnika majhna, medtem ko je čas dostopa bolj kritičen, saj direktno vpliva na hitrost delovanja posameznega procesorja. NadrmJmni proovmonoki Slika 2 Simtmmaki dadmj Jevalat vodila pr-eommofBki modul 1 pr-oommor^mhi modul 2 JUU._VODILO Slika 3 Slabost VME vodila za gradnjo robotskega krmilnika je predvsem v tem, da gre za uporabo uni^ verzalnih modulov v sistemu, ki je zelo specifičen. Vendar pa to pomanjkljivost odtehta razširjenost, cenenost in fleksibilnost VME standarda. Poleg že naštetih prednosti VME vodila je iz-rednegà pomena razširijivost sistema, saj lahko dodamo množico standardnih modulov (gibki disk, serijsko komunikacijsko enoto, analogne vhode/izhode...) in uporabimo že obstoječo programsko opremo (operacijski sistemi, prevajalniki...). S tem dosežemo, da je naš sistem vedno učinkovito prirejen posamezni aplikaciji, kar rezultira v optimalni ceni robotizacije. Pomembno pa je tudi poenostavljanje razvojnega dela, saj v času razvoja lahko uporabljamo module, s katerimi razvoj poteka hitreje, ko pa je projekt končan, opremimo sistem z najmanjšim potrebnim številom modulov. 5. ZAKLJUČEK V delu smo podali pomembne zahteve za gradnjo v(!čprocesorskega krmilnika dinamično vodenega industrijskega manipulatorja. Problemov izračuna kineraacičnega modela nismo upoštevali, saj so glede na dinamični model enostavnejši. VMi: vodilo, kot zelo razširjen (tudi pri nas -Iskra Deli:a-Triglav) in zmogljiv računalniški sistem, so, je pokazal kot najprimernejša osnova ZA razvoj kompleksnega robotskega krmilnika. 6. ZAHVALA Raziskava je bila opravljena v Laboratoriju za robotiko na Fakulteti za elektrotheniko v Ljubljani. Delo sta financirali delno RSS in delno Iskra Delta. Zahvaljujem se prof.dr. A.Kralju za mentorstvo pri opravljanju naloge ter sodelavcem laboratorija za mnoge koristne pripombe in predloge. 7. LITERATURA (1) J.Y.S.Luh, "Conventional Controller Design for Industrial Robots - A Tutorial, "IEEE Trans.Sys., Man, Cybern., vol. SMC-13, pp. 298-316, May/June 1983 (2) J.Y.S.Luh and C.S.Lin, "Scheduling of Parallel Computation for a Computer-Controlled Mechanical Manipulator",IEEE Trans. Sys,, Man, Cybdrn., vol. SMC-12, pp. 2114-23U, March/April 1982. (3) J.M.Hollerbach, "A Recursive Lagrangian Formulation of Manipulator Dynamics and a Comparative Study of Dynamics Formulation Complexity," IEEE Trans. Sys., Man, Cybern., vol. SMC-10, pp. 730-736, November 1980 (4) L.S.Gang, "Jedan postupak paralelnog procesiranja matematičkog modela manipulaci-onih robota". Zbornik, U.jug.simpozij o. uporabni robotiki, Vrnjačka Banja, pp. t2-S5, maj 1985. (5) J.Y.S.Luh, M.W.Walker and R.P.C.Paul, "On Line Computational scheme for Mechanical Manipulators", ASME Trans. Journal of Dynamic Systems, Measurement and Control, Vol. 102, No. 2, pp. 69-75, June 1980. (6) N.Kasahira and S.Narita, "Load Distribution Among Real Time Control Computers Connected via Còmmunication Media", pp. 194-199, Proceedings of 9th IFAC World Congress, Budapest, July 1984. (7) R.P.Paul, "Robot Manipulators: Mathematics Programming and Control", MIT Press, Cambridge, 1981. (8) P.Coiffet, "Modelling and Control", Kogan Page, London 1983. (9) H.Kirrmann, "Events and Interrupts in" Tightly Coupled Microprocessors", IEEE Micro, Vol.S, No.2, pp.53-65, Feb. 1985. (10) W.Fischer, "IEEE P1014 - A Standard for the High-Performance VME Bus", IEEE Micro, Vol. 5, No.2, pp. 31-41, februar 1985 (11) "VME Bus Specification Mannual, Rev. B", VME bus Manufacturers Group, August 1982. U?i:liAClJSKI SISTER VH/SP JAKA JAHSEK 1NT£GIEAI;{. LJUBLJANA UDK : 681J.06 POVlilEK: -Prispeve*. govori o lEMuven oi-eracijsXtiB sistcnu VM/SP. Glavna značilnost VH/SPja je sxBulacxja voC ndvicit^ziiiù raCunaluikov, od katerih je vsak ^jo funkcijah ekvivalenten realneaa cdCundlnik«, tiiKo v ^lialu uparuLutntì kot jjro^jratske opteae. V navideznih računalnikih lahko teCejo vjlavr.etj v.sti. ojetacijsiii siütuai. kot aa rtiilniii računalnikih; interaktivni operacijski sistea CBS, ki jv liol ii/jA, i'.i je namenjen losche j za navidezni raCunalnik. AESVhACl; Vhe acticla rtiiroctnts iB.i o£>ecating systbs VM/St. TLe main characteristic of VH/SP is s^ioulatiou Ol vi.ctiial cooputors CvirLu.ui.a 2a delo vseh navideznih L.ičjniiinkov, razdeljuje Vü/SP. V raCun^iniKU z j^^Kiu 2i:itr>noji Vii/Si' torej deluj« i.kratj. v^jC ua v icoz nii; uaC ji.aliiikov , ki imajo iJhko raziiCr.e oj-e raci jsko sisteoie, opravljajo ,.dhetr.o ali sprotno ubaelave ter uporacljajo iikruLuo i;;vdjanj'i pto.j ca tov. iiuvu: NE - navidezni računalnik va/SP - Virtual Machines/System Product CüS - Conversational Monitor Systea CP - Control Proyram DCS - Disk Operating Systea V/I - Vhodiio/izhodni 2-_sP!.gs»g_o_TH/sp 2.1 Koaponente fD/^P Bistveni komponenti operacijskega sisteaa vn/:iP sta CP (Control Prograa] in CHS (Conversational flcnitor System). CP ali Krailni progran se pri zaCetni naložitvi operacijskega sistema napolni v pomnilnik in tam ostane ves Cas .delovanja VH/SP. Njegova naloga je, da omogoCa obstoj in delovanje navideznih rdCunalnikov ter Cicbolj ekonoaiCno porazduljuje sistemska sredstva kot so proctisorski Cas, količina polnilnika, sisteasni progcuai in datoteko oud ^usanczDo navidezna rdCuiialnikc. J CHS , je sam idse opuracijski sistem, predviden zjio) ; Izvaja sc pod koiitroiu <.;i5a i.r. ujio'jciča sočutno oblikovanj« :jj.loiisKih olik. l-.jOto7ljoiic iaslonskfc slike se nato i.iii/io u p o ,■ j I j.,! ; o v cazaiii aplikacijah tod C.Ijoi. CCr {üocusKjct Coinj osi t ion Facility) : Tuùi ta teCe f"- kor.trolo L;iSa, u.iüjoca i'd oulikovanje besedila tci: izi>i:: ua raz^ii^iic izhodne enote, kot so tiskalnik, turniiial iit diski. 2.2 navidezni raCunaloik Kot 2e oa.;njono, jc Liütv«r.a znaiiinost VR/i'i'3'i to, . Uu.o.jOtci uiistoj iiaviacznega raCuTidlnika. Ta po J.ui;kcij.iii uiiak rcalntau rdCuridlniku, saj iaa simuliiano tako araraturuo kot i;rograD3ko oi-roao. L'od «adzorstvOB CPja lahko istoCaoiio dola poljubno število i;2ov, očvisiio Ovi v^iiKüoLi. poariiiiiii.J. Ni trcLa, da 30 OliaKi i/l luči lijiilOVO JtCVilo se IdhKC spreaiiija, posaaezoi NH se ziaareC lahko vkljuCi ali izključi. Kaprioer: V zaCetXu sta vkljuCeaa 2 SUA, od katerih iaa vsak siauliran procesor, pomnilnik v velikosti 4 ab, 8 diskov, 3 nagnetne trakovu, Citalnik, tiskalnik ter, kot pcogransko opremo, operacijski sistea DOS; očcuoB je vključeno 15 NRov, ki iBajo siaoliran procesor, poanilnik v velikosti 512 Kb, 4 di^kd, Citalnik ic tiskalnik, kot prograasko opreno pa inajo CHS. V teku dela IzkljuCiao 1 NB z oi>eracijskÌB sisteaoa DOS in vkljuCiBO 10 ll&ov z op. sistesoB CHS. Posdoeznemu iifiu lahko sproti spreainjaao bodisi aparaturno. Lodisi prograasko opreao, npr. dodano nekaj enot diskov, poveCaao ali zsanjSaniO pomnilnik, caloZiao vanj drog operacijski sistea itd. V realnea caCunalniku torej lahko pod va/SPjea dela hkrati veC NHov, po potrebi pa jih vključujemo in izkljuCujeao. T VH/SPjo obstaja poseben imenik, v katerea so vpisani vsi Nhi, in üiccr njihova imena, gesla io kontiguracija. V vsakem Nhu je simuliran t.i. navidezni proccsor, ki izvaja instrukcije in sprejeaa prekinitve. Ker deluje v Vfl/SPju veC NRov hkrati, je treba hkrati simulirati veC navideznih procesorjev - to oaojoca deljena izrdua realnega procesorja (timesharing). Bdvno täko se v vsakem NEu sioulira poanilnik (navidezni), in sicer v velikosti od B Kb QO li) Mb; velikost je vpisana v prej on«^njcneE ineniku, v tekn dela pa jo je aogoCe spreminjati. Ker simulacijo pomnilnika OBOgoCa princip stranjenja, lahke velikost navideznega pomnilnika preseZe velikost realnega 34 KQNTROLNA ENOTA ic: PROCESOR CJTALNIK TISKALNI» 9 tr.\K)- --- [jvONZOlA r" ZT 33 Ui o ,___ ::] r V. ' \ I -in. I____J --1 ' r "1 r i____J L_ . X NAVIDEZNI RAČUNALNIK SliX.i 1, KoiiCi.-jucAc.ijd ; ' Uiuya näviUtizne^a taCunalnika oecìIiuKa. I'ciioc: V caCuiidliilku a c:i>la a siüu 1 ira□ ini registri, ilJ. 2. Prek navidezoe konzole lahko uporabnik spreminja lastnosti NBa, npr. velikost pomnilnika, naCin dela nafidezoeya procesorja in število vbodno/izhodnih enot. J. Komunikacija z aplikacijo, ki se izvaja v enem ali veC NKov, poteka z navidezne konzole. Kot konzola H£a sluzi teroinal, lahko pa RB aeluje Lrez konzole, v ti. izkljuCenea stanja (disconnect), ki ga povzroCi uporabnik s posebni» ukazom. 2.3 Havidezoe Thodno/izliodne enoto V NBu je BoZno' definirati navidezne vhodno/dzhodne «note istega tipa kot so vhodno/izhodne enote pri realnem računalnika, in sicer pod kontrolo operacijskega sistema * NBu. Opisane so v imeniku, njihovo Število In tip pa se lahko v teku dela spreminja. Tsaka navidezna V/I euota iaa svoj naslov, ki s« imonüje navidezni naslov. Ob zahtevi za Čitanje ali pisanje, spremeni Krmilni program navidezni naslov v. ustrezni realni naslov in napravi tudi druge potrebne spremembe, npr. preračuna lokacijo podatkov na disku. LoCimo već tipov navideznih V/l enot: liaviiiezni-diski Navidezni diski se iseuujejo miiiidi.ski, ker navadno, zavzemajo le del realnega diska. Lahko so tazliCaih velikosti in tipov; uporabljajo jih razni operacijski sistemi. Slika prikazuje 3 minidisice na enem realnem disku. Številke na levi pomenijo navidezne cilindre za posamezni minidisk, Številke na desni pa realne cilindre. Posamezni minidisk lakho pripada enemu ali veC Nnom, po drugi strani pa je NB lahko brez NAVIDEZNI aUNDRI 126 MINI 01 MINI 02 MINI 03 202 Slika 2. uualr.i disk iii nav iđcv. ni diski - mitiiiano», IdiiiiO i>a ima eiicja .tli veC Ic-ttìh. Krmilni pcOjTao voai cvideiico za vciiik posaaezni ioiiiidislt, lil sictr tid ka terna ce:gov navidt.ziii naslov, Cc minidisk pripaua vtC Sifon, it.a laLko v vüakoiD izosed ujiii druyaCon iiavidv.'i.i^i naslov. ninidi^k zavztiKü Tift. JCl lOaininJd tiisKä Z iiciiilovoB ICO, in siccr cJ cilindra DO do üy. Pripada KEu i, v k.iterca irea naslov l'ai, ubeneo i.citđtid tudi NRu li, jijt:r iim naülov 2jii ter Nhu C, kjer ina r.asiov 007. Cc izda n.i E lU3LI:u^c^jo za Čitanje podatkov s J., ciliiiura miniaiska 2Jlt, jo Krcilr.i [.^ojLM» i-Litedi v instrukcijo za Čitanje z uiskalCO, cilindcr 5J. V VH/Sfju uLiitajjjo služnostni programi za oZLaCtvjiijC i;i spronilijjnjf air.iaiskov, zaSCita podatkov j.i JO (iosri2»^na na naslednji naCio: Lastnik itiniiiskd (uiJorabnik !fna, ki mu minidisk pripada) navouc, ali ija bo uporabljal saao za Citanjtì (read) ali za pihanje in Citanjč (rcad-wriLt;) ail i-ii (iuvoli veC Niioci, aa nanj piäejo (ffluiti-write). Ce £eli kak drag uporabnik pristop do tega sinidiska. Bora poznati ustrezna gesla, paC glede na to, ali Zeli samo Citati ali Citati in pisati ltd. Bed .delom je oogoCe ustvariti zaCasne aiaiđiske, ki ■ trajajo le do izključitve NBa, zanje iaa TH/SP predviden poseben prostor. Navidezni Citalniki in tiskalniki Vsak NU ima navadno svoj Citalnik, luknjalnik ter ontga ali veC tiskalnikov, vsi so seveda navidezni. Dejansko i-redstavlja navidezni Citalnik ali tiskalnik del vmesnega prostora oa disku (spool). Po potrebi se posameznemu Il£u za nekaj Casa dodeli roalni tiskalnik, na kattirega labko direktno izpisuje izhodne podatk«. Kadar pa tiskalnik ne pripada Dobenein NHu, lahko sprejema podatke iz raznih navideznih tiskalnikov in jih po vrsti izpisuje. Ista p^avi-^a veijajao za realni Citalnik in luknjalnik. Mlii si lahko izmenjujejo podatke, uporabljajoč navidezne enote: MB A s posebnia ukazom usmeri svoj luknjalnik k Citalniku 8Ba a, s tem doseže, da se podatki, ki jih luknja, zapiiSejo v Citalnik Nha B. Navidezni magnetni trakovi NIiu lahko dodelimo magnetni trak, ki postane . zaCasno njegova last. NE mu lahko dodeli naslov, vsi zapisi nanj pa potekajo prek Krmiliiogd programa. Primer: KHu dodelimo ma^jnetni trak z naslovom 340, ki ga ta spremeni v navidezni naslov 181. Krmilni prograa si zapomni realni in navidezni naslov traka ter podatek, kateremu NKu trak pripada. Vse instrukcije, s katerimi N£ piSe na tr'ak'^^ai, CP . Vi? prevede v ustrezne instrukcije za trak 300. Zato je BogoCe, da ima veC NHov trakove z ■ naslovi IBI, ki pa pripadajo razliCnia realnim naslovom. 2.4 Sistemski iaenik in tkljuCite* HBa ^istcjiski im-nit; KR je znaCilca Lju^ova definicija v sistb'B^äiieCi ioeciku (Jircctory), tau isa vsak NK oi>is, ki äoloCd njeyovc l.iütnosti. C{:is aed (ironia vstcuju; • iuentir ikdci jo (jusIo, potrebno za dostop do Niia • zaCiitoü in cajvtiCjo aoZiio vclikcst jiosnilii i « opis uKar.uv, ki so dovuljciii za upocatnika Nhd • Ddviaexiio tisKalaiko in Citalnlku • aiuidxsko z uàviac^niai naslovi • povezavo z aiii^ai.äki arujih Niiov • i-d "a act co, ki vplivajo na iTioriteto NBa (iri. rfo.iol jc-.vùu JU £;iocijsoLS/'.<.:'ja Casa ia kcliCiüo crialüt.jd jiOBDilnika 1 r i.ikazu JO ùi-is v sistC:CSii.cD imeniku. USER alfa 2XXXZXX 960K 2H G ICCOUNI 910030 alta ipl chs ra&h aoiocb consoli: 009 321S spool ooc 2SU0 beadeb • spool Ü0D 2540 punch a spciül ooe 1H03 a link rainl 190 190 bk link haint 19E 19E kb hdisk 123 3350 527 002 chshbk ti ZX ZZ XZ «disk 191 3350 246 005 c.1swbk h ZX ZZ XX Slika 3. Opis v sisteBskea imeniku upccaLlja za nadzor nad Niioa). Terainal, sa kattirea sc ju uporabnik prijavil, postane koi.zola NBa. 2 ustrezniai ukazi lahko uporabnik sprtainja karakteristike HJia, zapisane t sisteaskea iacniAU, vendar te spreaeabe veljajo le do njegove odjave. Py^iavllanie Kadar 2uli uporaunik delati z doloCenia NHoa, se prijavi, v terainal vtipka identifikacijo NKa in takoj zatea geslo. CP oboje preveri, zgradi NB po opisu v inenikn in o toa prek teroinala obvesti uporabnika, ki labko pato s poseliniB ukazoa naloZi v HB dolcCen opracijski sistea. iuui.ik jb' züpisjri na siüteEsV.äB dibxu ir. ju poii kui.trolo CP. ^o uporabnik s.iCfti litio z ooloconj.31 tu-.ci, ae prijavi (izvode 'lojoa ). ci poiSCo v sistcrskea iBitninu ■ zahtuvdiii i;«, ii-zecvira ustrezno koliciiio Lualnuja i'OCiiliniKa in zuradi potrctn«: kcntrciiio llokc ( zji-is v foaniliiiku, ki ga CP Kot le onccjeno, s« labko NB nabaja t izkljuCenea stanju, kar poaeni, da niaa konzolo-terminala, njegovo delo pa ostaja uesprenenjeno. Eotea ko se je prijavil tet z ukazi nalo2il H{iu doloCeao delo, se uporabnik po potrebi lahko izključi (. disconnect ) in uporabi terminal za druge naaene. 2.S Operacijski sisteai v navideznea raConalniko > V VB/S?ju deluje jo i.'Ri htiodvisuo od drugcya, zato laiiAO ndlollDio v vsak NB lasten Oi'«.racijsXi fiistuui, hot oa ^.tiaiet: ens • DCS/VSE - üiük operatiiKj Syston / Virtual Stoca^t txtfciidod • MVS - HuJtijilc Virliifil i;Loi.njc • VM/St' V i;oäaati;r.j.h iil-.ih lOhKo delujejo tudi razlj.eno vtrzijc ali. iJ kupije istoya oi,«rnci jsktga sictbBa. PROCESOR I----|-""> r-1_____J ■ I I j DOS/VSE I j .JL j^/SP_j T I I I I I I ."Z. J I i-i CMS I ___I —i CMS I L • r L-al CMS CMS j m «mJ Slika <<. Operacijski sistcai t navideznem caCucalnika Ce se uuhdja v Hitu sisten, ki oaoyaCa sprotno dttlo ^iLck t^rsiualov, potea en.tccBinal deluje kot kcii;zol.i Slika, aedtma kc druge priiiljuCiEO na |(» o posebnim ukazon (tlAL). 2.6 Oporatia opexacijsksga sisteaa in/Sg Navcdiao nekaj 'naCinov, kako se lahko izrabijo iioinosti, ki jih nudi vn/SP. VoCir.u /jjiuJ navodeniii o^etaci jukih sistumov ui-otdliiju slcanjunje. rte iJtlujcjo v Nka, ^rioč lio .ivujncivjd öttanjuoja, naoceC stcanjenjč oji. üi.;»t.c!c.i ic sLranjeiij« VH/SPja; vtnaar s« to z aoloćtjriiiii paruaetri laLko prepreci in uporüLija it eiiojuo atraiijenjc. Priacr operacijski»! sii;tci3ü» v tJKu: i-od VS/Si? jtf 3Ü :.U; V NK ALFA r.alolinio op. sisttiK CCS/VSf., iife uporablja iz^ljuCcc za pakbtne üLüälav«j; v : Tuäl ens uuo^oCa razvoj novih aplikacij, npr- s področja iintaciitju projranicanja, raCunaliAÌSkt! jratike itd. Uporatuxki lahko v CMSu urejujejo datotete, ki jin nato pošljejo na izvajanje » op. sisteiL OCb' ali I'trs. Poley tega oaCina odloCanja pa CP upoStera tudi uporabo poaoilnika in T/I operacije. Ce NB, ki pričakuje svoj .Časovno rezino! , Se niaa oa razpolago 'zadostne količine polnilnika, ali Ce Caka na izvršite» V/I operacije, tudi za dodtìlitev DrezineD ne pride v postev »ai, ki se potegujejo za sistenska sredstva', konkurirajo torej najprej za dodelitev polnilnika, nato pa za procesorski Cas. 3.2 Poaoilnik t navldeznea raCanalnlka 3a._KIBiiSi_tB0Gl*a_f_CP fcot 2e omenjeno, ja CP dui va/SPja, ki oao.joCa obstoj navideznih računalnikov, in siccr tdKo, da nadiioruje pcoce;sorski Cas, realni potinilni»., V/I oriate itd. ter jih iorazueljuje xed posanoznt: liiiC. 3.) Maridezoi procesor Uporati.ik.u IJIia se zdi, da se pcoctisorske inatcui.cije i^vajoju v ;jd pücazdei jevau ju ( tise-slicLiiJ ), sa] dobivajo NEi periodično Dd ra^j clacjo ^cocesur, in sicer za zelo kratek Casovr..! ird^liiüttK, u.iv.idno nfjkaj milisekund. Kako pajostu ill kako veliko DCasovno reziuoD bo [.'fc JjLil, odloCa ce, ylede na Število tfcLExiij isi.ih v-iiniitev, ki jih je UR povzročil v Caüu izrabe jtedUoJno časovne rezine", če je bilo it..V4.io veiiko, bo KS dotiil tanjSe L, d iiolj pOjOsLo, v iidsprotnuB prineru pa veijo v ledKCjSih časovnih razdobjih. Ka ta i.aCiii CP Sftoti t orazilfcl ju je navidezne r aCuiiair.iKe. na sploLiio lu pa/ictriO usmerjene. S por.oiiiinii ukani CPju lahko vplivamo jia Jou«.!j-jvar.je prccc.óor;;>.o'ja ùasa in s ttni dajemo . ini.-iO:;t (.'lic'jia ili Vuč linoj. Vsak Nfl ima svoj siiculirani pomnilnik -navidezni pomnilnik, katerega velikost je določena » sistemske;i imeniku. Ker navidezne pomnilnike ustvarja in nadzoruje CP, so le-ti lahko večji ud realnega pomnilnika. Kačin, kako CP omogoča simulacijo posnilnika, je na kratko naslednji: Bealni poaailoik je logično razdeljen na dele, velike 1 Kb, ki jih imenujeac okvirji (fraaes). Pomnilnik NBa pa je razdeljen na segmente (64 Kb) in znotraj sugnentcv na strani velikosti ».cac.i.jof.t; ja sisLtaa v «üu. . 1« enote so ,1. C i; ij ; Navidezni diski ali minidiski lahko pripadajo veC Ni npr. za prenos strani, niso podvržene prevajanju m se izvajajo direktno. 3.« Delo z vaesDia poanilnikoa 40 Äii Si ffioü aetoj lahko dulijo realne V/l eoott:. PoJatki, ici jih i-o^aDozni Nhi tiskajo, se aaarec Zdpisujejo na navidezne tiskalnike t.t.'aLbr v t^-Oi i.tiDijiu Lciiti ncKaj datotek z vnesnvja j.'oaciinik aii pa n ivide/nis enctaa dodeli üoddtRO iJodcoCju. üisic, na katerea se voiusni i>ooinil:iik nahaju, pripada CPJu, zato pri Zdilsovanju nu prili'ijđ do prevajanja. Kcauuikdcija neu Nhi jc umoyo^:en-d s prej oatnojaiji u:ii»(ìe kunfKjuracj.in ì{i;a CRS nima kaXib poseunih 2aiit«!v. KtC pondvjdi dcXa istoCdsno c.n0c dclo s pro^tuai. . 1 Dato.t-.a:sn casn CfJS cuzàiìii n-iji.sk V l;Lok(; Jlđlni; CioI2iĐC aOO ali IdOO kl. Tako tortoiitizic.);i iKinidisk se nato upotaLlja 'i-n latotokc z z.ipisr si-cilne ali spreienljiv« JoU'ii.u. Tuiii d.ihoteko na aagbetnen tcaku iiiajo laiiko uoljut:(io dolge zapisu Stali:«: ali si i'cnauiiljivo dol'ine. Siu^aojtni pcuijrajii c;i:i.i oiaogoCajo torcatiziran JÜ ainia i ì>kov, i-iii-iuje i'. i":itanje s trakov, sopLcanj<., pirt^ir.onov.ir.ji? fa brisanje ciatotuK, itti. u^^tajdjo pOj=;;r.« služnostni pro.jraai z,\ oLdolitvo iii-iU'imkih bibliotek, ki vsciiujejo aiaino-vicriiuCi JU aij. ( rot7 Last. Uporatnik Cilia iiua poltij .'i-iliijk.i lahko do 25 ainidiskov vsdktaiu jc joii.i cna firka. ite ilatutfckü v Lrliia -o^Lojl trei; ^omi.oni>iit: iilKEÌaie - ijtì, ki ya dolori ujiorauiiiii tilutype - iae, ki ozr.aCUjo tin datoteko filoBO.ie - it30 lai Iii.,li:jka (vii.i CL'Ka} Na prinor: o datoteki i luitiiora TZSt COliüL A venu, da viJtuujt pro.jiaa v coiioiu, iii da Sd jidi.dja na ciiiLdi^Ku A. Cu i>i;i d^iu z datoteko ne naređenu vseh treh kcu^.oiiunt iacna, CKS uj,oStoTù i ravila iilotyt .1 in iiikaii ja ;jo abtccdnfc» zai-credju hiniđisko?. Pri«er: Upocalinik 2Cli prevesti z asscablerjea trogcaa V datoteki li^STI; v ta naacn izda ukaz ASSEHBLS TESTI. CHS iäCe datoteko TESTI ASSEHBLE, in siccc najprej ua ai^idisku A, nato po vrstaea redu na B, f, S itd. Da se Cas iskanja Ciabolj znaiijSa, se dodelijo najbolj nporatl jania ainidiskoo najniZjc Crke. Datoteke v CHSa navadno ne zavzeiaajo nepretrganega.podroCja na Dicidisku, vendar pa ina vsak aioiäisk iaenik datotek, ki vsebuje kazalce na verige zapisov; ki tvorijo posamezno datoteko. Vsebuje tudi informacije o formata in dolžini zapisov ter o prostoru, ki ga posaaezna datoteka zaseda. CKS vseiiuje pristopne aetode kot so TSAH (Virtual Stura za PASCAL. Uporalinik lahko določi osejitve okrajšav in si deiiiiira svoje besede (sinoniae) za ^osasezne ukaze. Poijubneau prograau v strojni kodi, ki ne nahaja na ainidisku, lahko nporaJjnik dudoli ime ic ga uporabi kot CBS ukaz, s;katerim program izvede. CÄ50V int^jCf/Ccti^r i.i;xx üio'jüCa povezovanje CüS-UA-dZov, pojojiiü izvajdnjt, izvajanje » zar.Kdà^ itč. Poi«.;^ tti'ja oiuojoCa aritaetiCue in lo<,iCüe opeiđci.je, Zai-iis &toviL 2 arsno vtijico, intcCDe in enstoriie t;ođpco9ra aio, veCuimcnixonalne sj/ce aeri i ji vko in vyrajene fufcfccije. 5. IZBOLJŠA?* PEBFOBBANS Ko 'ix)Vütimo o (Jcriormansah taćunalnika, Bislimo £ tem na • odzivni Cds pei üptotncDi aoiu • Cu;;, >;i >3.1 iioiatijo jjakatuc oliùelavo, izLoijž.injc jjcrtornirtns ^^oineiii izl oijSanje oliali ojenjciiih Cajov. Xu<.aiiii i-ii.;;top k iztoijSjnju iietiottaiiE l'otiika tako, da si upocatinik raCunainika (tu 50VOCÌ1BO o tealüci caCun-alniku) tostavi kot i;ahLevo üoioCeno mejo odzivnega Caca pei i;,iot;n.'ii ir. paxctr.om tioiu. IzLoljSav«-au nat.o dondejo z joioConiaii r.ixumeoiijaiii v tazpo reJ't V1 j tc jiaankc o'l-tcae, s Cia pri kläii ne jio la^i-ocMÙilvi jo oLdclav ter evvntvilnu z luz-ufo.! dodatne laCunal/iiäke V Vil/iil'J'J òo£,c'i>;;bo izboljšavo i:ei:£or[iiai4S s i-iJieiciiiLar.i i.a vhoii.o/i;;liodt.uiii üiateiu ter z tol^io i^iaLo i.'i.oc<;i.oci:f.eij.i tai;a in poECilnika. Kd jValne jie ao iv.'i«-.sLo na vhodno/iihodncn :jist>,aiu, pcyaoc joùotAov na diske naurtaC zai.tt.va ^olo vi^iikj CaJid » [liiuerjavi 2 izvajanje! ir.JtiUKcij. Kai.aii so vhcdi.o/izhcdne tniutK, Ki i-rev i-aoie jo i-renos wouutAüv. in ii teil r-iübrciniiijo (.cuccsor. iJavatiUO düia on .kanal z iiejiaj uiciti, m Ce jt prcveC i zastìoen, oiiroü/a C^.- jd Kanali ntienaküsierno Oi;r«.ic;: ;fiii, j 3 ^j.iLajov. ^.jto jc trtia BoCuo obremenjene datoteke porazdeliti Ciacolj enakomerno glede na kanale. lipiCen priaer take datoteke je prostor, kamor se izpisujejo strani navideznega pomnilnika. Navadno kreiraao veC takih datotek ic jih razporediao na diske, priključene na različne kanale. Izrabo procesorskega Casa izboljšano 2 vključitvijo i-csetne funkcije VMASSIST, ki najpogostejše operacije, npr. prevajanje naslovov iinidiskov, prenese v aikrokodo. Ce dela v navideznem računalniku operacijski üisteD z velikiiu Steviloa progranov v hkratni obdelavi, se doseze Loljiia izraba procesorskega Casd s porazdelitvijo programov na veC op. sjictuinov v različnih NH. S te« naioreC dosc2e»o, da DrazpeCevalnet lunkcije Vfl/SPja, ki bolje izkoriščajo procesor, prevzamejo hkratne obdelave programov. izrabo pomnilnikd izboIjSaao s tes, àa omejimo veliKosti navideznih pomnilnikov » posameznih NE. S tem tudi zmanjšamo zahteve po stranjenju. Cim voC CHS sistemskih prograao* damo v podroCje, ki se istoCasno deli med NE, saj s tem ravno tako prihranimo na stranjenju. Ce Želimo dati j^rednost enemu izmed NBov, au C posebnimi ukazi poveCaco prioriteto pri CrazpeCovanjuD in stranjenju. Seveda pa s tea upočasnimo delo ostalih N&ov. Si-iSIIBAiaB* • performance Heasureisent -Tools fot VK - System Journal heprint • Tuning a Virtual Storage System - Systea Journal Bepnnt SISTEM INDUKTIVNO UĆENJE ASISTENT IGOR KONONENKO (1). IVAN BRATKO (1,2), EGIĐIJfl ROiKAR (1) (1) Fakulteta za eleKt m tehni Ko, Ljubljana (2) Inititut Joief Stefan, LJubljana UD K : 681.3:159.953 POVZETEK I: Guinlanousaa sistema ID3 za seneriranJe odloiituenih dreues na- osnoui znanih primerov smo razuili sistem. Ki sno 3a imenovali ASISTENT. Osnouni alaoritem smo izpopolnili taKo, da omoaota uporaäo nepopolnih podatKou, obravnavanje zveznih atributov. Klasificiranje v kombinaciji : Sa/esouim verjetnostnim principom, avtomatsko i-ffbiro dobrih ufinih primerov, enakovredno obravnavanje večurednostnih atributov z binarno sradnJo in rezanje nezanesljivih delov od 1oč11 v eni h dreues . Vse izpopolnitve imaJo teoretično osnovo. Njihova prav i 1 nos t Je potrjena z eksperiment: v 5 razlifiili medicinskih domenah. Odloćitvena drevesa so «anJäa in s tem razum 1J i ve J5a za uporatn:K.T. hS'iti p.i so natanćneJSa pri Klasifikaciji novih primerov. ASISTENT Je v vseh medicinskih domenah doiJ:iel razred nataninosti zdravnikov specialistov. ZaraJena odločitvena drevesa so razmeroma razumljiva in uporabni); lahko iz nJih razbere doloCen«" zakonitosti iz svoje domene. Lahko se uporabljajo brez r.-ilunalni Ka. npr. Kot priročnik za d i aanos t i c i ran Je . ASISTENT je implementiran v pašcaiv i ..cscjj pribl. 5000 vr s t i C . i zvorne kode. Trenutna implementacija omosofia hifro aeneracijo in Jestiv i'ije pravil. Proaramska koda Je Komentirana in dokumentirana z navodili za uPorabniKa in z navodili zi proaramerJa. Sistem Je zrel za rutinsko uporabo v poljubni ustrezno definirani problemski do.reni. AM INDUCTIVE LEARNING SYSTEM - ASSISTANT (ASSISTANT is an inductive learnina s/stem for oonstructins the decision trees from examples. It is d>;rived from Quinlan's ID3 (Quinlan 79.73a,82). Extensions to ID3 include: multivalued attribute:-,, continuous attributes, incoapletelr specified learnina examples, binari- construction, autoM.:'ic selection of 300d trainina examples, tree-prunina with naxinal classification precision prin;iple and Plausible classification in combination with statistical method, based on Baresian principle. ASSISTANT was applied to a number of learnina problems in medical diaanosis and proanosis: location of prinarr tumor, proanosis in breast cancer, 1rmphoaraphic inuest iaat ion> hepatitis and lower urinary tract disfunctions. Some earlier experiments are described in (KononenKo et. al. 8*, Roäkar et. al. SS). A comparison with a statistical method based on the Baresian principle is presented. Sr the comprehensib i 1 i t y-cri terion decision tree has nani' advantaaes (Zwitter et. al. B3). The ■liaanostic rules ( dec i s ion: trees ) aenerated from examples, perform on new cases trpicalli- in the ri>l iai) i 1 i t f ranse of human specialists. Ther can be used without the computer, simplr printed on the pjpit. ASSISTANT can be used for automatic s/nthesis of the Knowledae-bas es, which is the bottleneck in t:tj development of expert systems (Bratko et. al. B5) . 1. U'.-OD Kot alternativa standardnim statistiinim metodam za. razpoznavanje in arupiranje vzorcev se Je pojavilo s*.ruKt-i'''>c avtomatsko uCenJe, Ki temelji na metodah UTietne inieliaence (alej npr. Nilsson 82). Bistvena prednost 5iruKturneaa (lahKo birekli tudi injuktivneaa, simbolifnesa ali loaifineaa) avtomatsKeaa učenja Je v razumlJivssli nauJenih pravil. Ki so simboliini OPisi paJavov. teorij, objektov ali Konceptov. Za osnovne principe strukturneaa avtomatsKeaa u6enja aleJ (Kononenko S5). V tem prispevku nas bo zanimalo avlomalsKo učenJe odloiitvenih pravil na. osnovi primerDv. froble.,! induKtivneaa uÄenJa o d 1 oC i-VvéS i^^prav i 1 Je de rIn i ran tako 1 e ; Sr'iNO l .finoiica ućnih primerpTu j-ópisank^ z ^«nož.ico. , . atributov. Usak obJela pripada enemu od moln.ih razredov. rg I j g 1 ; Pravilo, Ki raz 1 prav 1,1 no klasificira') uCne prineri in Ki se aa lahke uPorab i.', za k^las i f i kic i^o' nov'ih .- 1 r C v . . ' ■ ' . . Sistem ASISTENT sno razvili iz Guinlanoveaa sistema ID3 (Suinlan 73,73a,S2). Osnovna ideJa sistema Je aradnja odloiitueneaa drevesa. OdloSitveno drevo Je drevo, Katereaa voz 1 i.ustrezaJo atributom, veJe iz vozla ustrezajo posameznim vrednostim atributa v vozlu in' listi drevesa ustrezajo razredom. Zaled od 1oii tveneaa drevesa Je na sliki 1.1. Odločitveno drevo pravi : ie Je vreme oblafno, poten se odpeljem v slulbo z avton, £e Je vreme deievno ali pa sneii, potem se odpeljem v sluibo z av'.obuson, in de Je vreme sonino, potem, Ce Je temperatura zunaJ pod +E st C, arem v sluJbo pe4, če Je temparatura zunaj nad + 13 st C, aren v sluibo s Kolesom, druaaSe pa ne znam izbrati prevozneaa sredstva. ohltj'no___' „ciCiuje., . " " -------------- f Av/roj đjjm^^-uP^ [^^^OP.L'J] s 11 V. a .1.1 Odločitveno drevo- po .t:aterem se odločamo o izbiri prevazneaa sredstva z ä f 5 i u : 6 o . Osnovni alsoritca aradnJe oilloSituencsa drtutsa Je v s^-ol)*« sltdeCr E( vsi Friairi sfadijo v isti razr«d> rotta postavi Ust s te« razredoM» drusaft 1. izbtri za voztl naJbolJ infomativtn atrikut 2> razbij anoiieo priatrov v vozlu po posaatznih urtdnoitih atributa v disJunKtnt podanoüet 3. za vsaXo podana2ieo ponovi eelottn alioritta vo. Bistvo alaoritaa J« atributai ki Jt podrobntJt sKust z uporabo sisttaa Alaoritta rtkurzivno aradi dre izbira naJbolJ inForaativneaa OPisana v 2. poslavJu. Prvt po 103 V MtdicinsKi diagnostiki s in Ptter Multe (BOp altJ tudi bili obttavnir zato sao nadalJ Osnovni alaoritem sao izpopoln ASISTENT se razUKuJe od 103 v TnaC ilnostih: ta napravila Ivan Bratko Multe 80). Rezultati so evali z razvoJea sisteaa. ili na uei naiinov. arobea v naslednjih (a) ASISTENT uporablja binarno aradnJo: vtaK atribut postane binaren» tako da se vrednosti aruPiraJo v dve disJunktni podanolici» ki naKsiaizirata njeaouo inForaativnos"!. Dobljena drevesa so nanjia in iaajo vetJo Klasifikacijsko natantnost (vefJi Jt eFtkt aentralizaciJt nad ućniai priaeri). NaJnoveJSa raziskovanja Rossa Quinlana (BS) so bila PoaoJtna z rtzultati naJih raziskav in nakazujejo dodatne izboIJiave h aradnJi odlofitvtnih drevts. Verjetnostno sklepanje v kombinaciji z Baresovi« verjetnostni« principo« oaoaoia ASISTENTU razrtiiti konfliktne situacije. Id) Bezanje nezanesljivih delov drevesa po principu maksimalne klasifikacijske nataninosti caotoCa ASISTENTui da se izosi^* slabosti« ocenitvene funkcije nad aaJhniai anoücaai priaerov « vozlu. Slika 2.1 V korenu drevesa so verjetnosti razrjaou Pj , l-l-.H, v v-tea nasledniku korena so verjetnosti razredov IV V so apriorne verjetnosti posaaeznih vrednosti A. OaleJmo si nekaj lastnosti funkcij E in I. V nadaljevanju so podani nekateri izreki. Ki so dokazani v (Kononenko B5a). Izreka 1 in 2 sta splolno znana in sta tu dodana zaradi koapletnosti. Eksperiaenti v aedicinsKih doaenah so pokazali na pravilnost izpopolnitev. ASISTENT Je v vseh medicinskih domenah doseael diaanostifno natantnost zdravnikov specialistov. ZaraJena odloiitvena drevesa se daJo direktno interpretirati v naravnem Jeziku in so zlahka dojemljiva. Lahko se uporabljajo brez raCunalnika (izpisana na papirli npr. Kot prirofnik za diaanostieiranJe. Za uporabnika so zaniaivai Ker iz nJih lahko razbere doloiene relacije in zakonitosti iz svoJe domene. ASISTENT Je sploien sistemi le poskuse sao do sedaJ delali saao na podatkih iz aedicine. ASISTENT Je inpleaentiran v PASCALu (cca SOOO vrstic) in s.! PoaanJaao na radunalniku OEC-10. Za aradnJo drtvts Porabi tiPitno ntkaJ stkund CPU za ntkaJ sto primerov in nekaJ ainut za nekaJ tisof uCnih priaerov. 2.1.1 EKSTREMNE VREONOSTI IZREKJL: Se Je v danem univerzumu priaerov z R razliSnimi razredi verjetnost nekeaa razreda r enaka 1, potem Je potrebna količina informacije za klasifikacijo eneaa priaera E enaka 0. 2: če iaamo v danea univerzumu R molnih razredov, rotea Je naJveČJa moina potrebna količina inforaaciJe E za klasifikacijo eneaa primera enaka E = - loa^tl/R) in takrat velJa P^= 1/R, i > i..r. V 2. poalavju so podane nekatere formalne izpelJavei ki so osnova izpopolnitvaa v sisteau ASISTENT. V 3. poalavJu so opisane izpopolnitvt sisteaa ASISTENT. V 4. PoalavJu so prikazani tksptriaenti z ASISTENToa v petih različnih medicinskih domenah. Implementacija sisteaa Je opisana v poalavJu S. 2. TEORETIČNE OSNOVE V tem PoalavJu so podane Formalne izpeljave, ki so podlaaa izpopolnitvaa v sisteau ASISTENT. Najprej so podane lastnosti informacijske funkeiJei ki Jo Je Ouinlan uPorablJal v sisteau ID3. V poal. 2.2 Je podana izpeljava ocene verjetnosti klasifikacijske točnosti s sisteaoa ASISTENT. V poal. 2.3 Je izpelJan Baresov verjetnostni princip. Katertaa klasifikacijsko natančnost sao primerjali s sistenon ASISTENT (alej poal, 4.4). y Poal. 2.4 Je poJan Kriterij ocenjevanja klasifikacijske natančnosti, ki upoSteua apriorne verjetnost: posameznih razredov. 2.1.2 INFORMATIVNOST ATRIBUTOM DEFINICIJA: Informativnost atributa A definiramo kot razliko potrebne količine informacije za klasifikacijo eneaa priaera pred in po uporabi atributa: Inf(A) » E - KA) IZREK 3: Informa enaka 0. ■ li IZRELJ.: Informativnost atributa Je naJveč E, pri čemer mora biti itevilo vrednosti V atributa A vtčJe ali enako Številu razredov R : V ^ R. 2.1.3 VEČUREDNOSTNI ATRIBUTI s: ImeJao atribut A z V vrednostmi. Dodajmo atributu« it eno vrednost tako. da prvo vrednost V^ razbijemo na 2 vrednosti V^ in in imenujemo tako dobljeni atribut A'. Velja: InFtA'l ^ inF(A) in Inf (AM . InF(A) <■> ^r Ä ^ Pvi' fv, i . 2.1.4 PRINCIP NAJVEiJE KLASIFIKACIJSKE NATANSNOSTI it imat v vozlu anožio« pritierour lihKo vtrJttnoiti rizndov Ri v vozlu aproktimirano z rtiativnimi FrtRvtneani priatrov, TaKo doblJcnt verjetnosti P;. i«t..R lahko uporabitto za klasifikacijo novih priaerov taks. da vsak priaer razvVstino v razred H z naJveCJo verjetnostjo P^. klasifikacije N^ko kar verjetnost pravilne klasifikacije P^: K.. Ph- »a. Pi i Ce izbereao za koren poddrevesa danesa vozla atribut A z V vrednostni» naa ta razbije nnoiieo primerov na. V podanožie. Ustreme verjetnosti so narisane na sliki 2.1. Natančnost klasifikacije novih primerov po preJ »••isanefi Pos^oPku bo sedaJ! "f* Z-'V-"'"' "vt v i jiFINlCUa: Princip naJveiJe klasifikacijske rj'.antnosti izbere za koren drevesa atribut, ki maktimizira N^. IZREK s: laeJas dva univerzuma U1 in UZ. v obeh so obJekti razdeljeni v R razredov. Trditvi EiUt) > EtUZ) <"> N,(U1) < N,(U2) in E{Ul) • E(U2I <»> N,{U1) » N^CUZ) veljat« vedno natanko takrat. Ko Je R-Z. Z.Z OCENA KLASIFIKACIJSKE NATANČNOSTI 2.2.1 POLNA nN02ICA ATRIBUTOV Ouinlan (S3) Je pokazal naslednje: Vzeaiaoi da. za dan univerzum, katereaa objekti so cisani s kontno anoiico atributov in pripadajo kontno rnoao razliCni« razredom, eksistira eksaktno odločitveno drevo'(drevo, ki pravilno Klasificira vse objekte iz univerzuma). To pomeni, da Je nnoiica atributov, s kateriai so objekti opisani, polna. Recimo, da ima naJaanJii eksaktno dreno L listov, in v vsakem listu Li Je množica priaerov 6i. i»l..L. definicija: Poppln sistem za učenje odločitvenih pravil za dani univerzum Je sistem, ki na osnovi učnih primerov zsenèriri odločitveno pravilo, ki pravilno klasificira vse.primere iz mnolice Bi. i'i .L. če Je bil med učnimi primeri vsaJ'en primer iz množice Bi. QuinJtn' Je Pokazal I da če bi imeli tak popoln sistem, bi na osnovi učnih primerov dobili odločitveno pravilo, ki bi poljuben primer klasificiralo pravilno z verjetnostjo: P • 1 -(L/(I.72 N)) • (1 - K p!") + d, d > 0. kJer Je L;.ttevilo vozlov v naJminJiem eksaktnen drevesu. N Je Itevlä«'učnih primerov, P^Je apriorna verjetnost, da naklJučrti izbran primer pripada r-temu razredu in d Je pozitivna konstanta napake, če opustimo d. imamo . sPOdnJo'me'io verjetnosti pravilne klasifikacije P3l Jubneaa^-priaera. poskusih v iahovskih končnicah s «olnimi množicami atributov Je ID3 vedno presesel ::enJen: spodnJo meJc natančnosti klasificiranja novih Z.2.2 NEPOLNA HNOilCA ATRIBUTOV ImeJao stdaJ univerzua z nepolno nnoiieo atributov. toreJ atributi n* zidasluJtJo za pravilno KlatifiKaciJo vseh objektov. Dtniao» da atributi zadostujejo za klasifikacijo nx vseh priaerov v univerzuau. Vzeniao. da imaao niniaalno odločitveno drtvot ki zadotča za nz klatifIkaclJsko natančnoit in iaa L listov. V vsakta listu Je anofiea priaerov Bif i>!..L. Hnožica Bi j't « sploinea sestavljena iz anožio Bri' r*l.,R> pri čeatr Jt ELanožiea priaerov z r-tia razredoa iz i-tesa lista. Listu pripiieao razred, ki maksinizira noč anožice Btf. če Je več razredov z naJvečJo «oČJo v listu, sistea naključno izbere med njimi en razred. definicija: Popoln sistea za učenJe odločitvenih pravil v univerzumu z nepolno množico atributov Je sistea. Ki na osnovi učnih primerov zsenerira,odločitveno pravilo, ki z nz natančnostjo Klasificira vše primere iz množice Bi. če Je bil v učni anožici vsaJ en priaer iz množice Bf. Izpeljava verjetnosti pravilne klasifikacije PolJubnesa objekta Je analogna izpelJavi v (Quinlan 63). Verjetnost, da med učnimi prineri ni objekta iz > Kateremu pripada obJekt. Ki sa želimo Klasificirati. Je: kr " o P(Bi)'(l- P{Bi)) . 1 N • itevilo učnih frimerm' Verjetnost» da med uCniai priaeri Je tafi obJekt. Je enaka'f-Ai. Verjetnost, da bo odločitveno pravilo naključno uaanilo praifi KcLtreJ. objeltin^ je. enaifa: ■ t'.' Soč pravilno klasificiran: P ■ <1-P„)-I1/100 + ri d fi, tJil Ker ve I Ja: dfCliì pri P(l Je Tihr -0. ; Končna ocena spodnJe neJe verjetnosti pravilne Klasifikacije primera z odločitvenia praviloa Je enaka: JL HOO Pri tea Je N anožica učnih primerov in d' Je pozitivna Klasifikacijska napaka. Za konkreten problem lahKo L ocenimo s Ctevilon listov v doblJenea drevesu. Problematična Je ocena paraaetra n. 2.3 BAYESOV VERJETNOSTNI PROUCÌP' Problem klasifikacije novih primerov pri danih učnih rrimerihi ki Je poun v poal. 1.4, lahko reSimc z Baresovin verjetnostnim principom. Verjetnost razreda R' pn danih vrednostih n atributov A« Je enaka: (it Je PIR) apriorna verJelnosl razreda R in P{A«) apriorna verjetnost, lianih uretinostl atributov inte oznaÜBO posaiacne vrednosti atributov : Aiy: = pa)' P( l n) p i i j će predpostaviiio Medsebojno neodvisnost atributovf dobino: ttpMČ; PiAc) Verjetnosti na desni strani enaibe lahKo aproksimirano z relativnini FreKvencani iz dane «nojice uinih primerov. Na ta način lahKo KiasiFici ramo poljuben nov primer. Primer K lasiFi Girano v razred/ Ki «aksinizira verjetnost P(Rlfl*), pri feiner so A« vrednosti pasameznih atributov pri dane« primeru. 2.4 KRITERIJI OCENJEVANJA KLASIFIKACIJSKE NATAMSNOSTI 4) ASISTENT omoaoia avtomatsko izbiro dobrih uCnih Primerov. 5) ASISTENT sam avtomatiino doloSa »eJe intervalov «rednosti zveznih atributov. El V ASISTENTU Je reiena ponanklJivost informacijske funkcije pri ocenjevanju vefvrednostnih atributov z binarno aradnJo dreves. 7) ASISTENT omosoCa avtomatsko rezanJe nezanesljivih delov drevesa. V eksperimentih v 5 razliinih medicinskih domenah so raziiritve prispevale k bolJii dia3nosti^ni natanfnosti in k veiJi razumljivosti aeneriranih diaanost i in i h pravil v obliki odloiitvenih dreves. I.' tem poalavju so opisane posamezne izboljšave. M 4. poalavJu so opisani rezultati eksperimentov z ASISTENTom v primerjavi z osnovnim alaoritmom in s statistiino metodot Ki temelji na Earesouem principu verjetnosti. Podana Je tudi primerjava diaanostićne natanänosti odločitvenih dreves in zdravnikov specialistov. V 5. poalavju Je na kratko opisana ixplementaciJa sistema ASISTENT. će Je v dani anoJici primerov en razred zelo verjeten, '^jtem lahko vedno dosefemo dobro natančnost klasificiranja. Preprosto klasificiramo vsak primer v -.jzred, ki Je naJbolJ verjeten. Tako klasificiranje nima ■•pavesa pomena. Zato Jslimo namesto preprosteaa seJtevanJa pravilnih odsovorov dobiti kriterij za jcenJevanJe natančnosti klasificiranja, ki bo izpolnjeval naslednje poaojel t) Pravilno klasificiranje primera iz razreda, ki Je .unj verjeten, mora bili več vredno kot pravilno 'klasificiranje primera iz razreda. Ki Je bolj verjeten. ; I te so vsi razredi enako verjetni, mora biti kriterij enak Kot kriterij seStevanJa pravilnih odaovorov. i;) če Je klasifikacija popolnoma naključna, tako da Je verjetnost, da razvrstimo primer v razred r enaka 1/R> potem mora biti natančnost klasificiranja enaka 1/R (R j« itevilo razredov!. d) če pravilno Klasificiramo vse primere, rezultat lOOZ. mora biti e) če klasificir.amo vse primere v en razred, natančnost klasifikacije enaka l/R. mora biti IZREK 7: če pri StetJu pravilnih odaovorov namesto enK seštevano izrazeC R Pr R Je Število vseh razredov. Pr Je apriorna verjetnost razreda r primera. Ki smo aa pravilno klasificirali. in Je dobljeni rezultat klasificiranja enak : 3.1 GRADNJA DREVESA EREZ ITERACIJ Ouinlan (82) Je v svojih poskusih uporabljal naslednji iterativni alaoritem za aradnJo dreves: 1. Iz množice učnih primerov naklJuino izberi primerov. 2. Ponavljaj 2.1 Nad izbrano množico primerov zaradi drevo. 2.2 Testiraj drevo s preostalimi primeri. 2.3 K izbrani «noiici primerov dodaJ )ic!rK Ker se verjetnosti v informacijski funkciji (aleJ posi. 2) aproksimirajo z relativnimi Frekvencami iz množice učnih primerov, bo aproksimacija tem bolJia. čim vetJi bo množica učnih primerov za aradnJo drevesa, te postavimo za učno množico celotno množico razpoložljivih primerov, bo aproKsimaciJa naJbolJia. S tem se tudi izoanema iteraciJam. saJ se drevo zaradi samo enkrat. Problem nastopi, če Je hitri pomnilnik premajhen z» celotno množico učnih primerov. V ASISTENTU Je problem reJen tako. da se relativne freKvence primero« računajo ob branju datoteke s primeri tolika časa. dokler množica primerov v vozlu ni zadosti maJhna. da Jo lahko spravimo v hitri pomnilnik. Alaoritem Je zaradi tesa za velike množice primerov (npr. nekaJ sto tisoč primerov) počasnejši, vendar so dobljena drevesa manJSa. Za manJSe množice primerov (npr, nekaJ tisoč primerov) pa Je alaoritem seveda hitreJSi. Oo istih zaključkov Je priSel tudi 0'Keefe (83). Rez N R I Kr —. Kr Je Število pravilnih odaovorov iz 'T R Pr ratrčJit. ut Je ii.nrvtiĆ'tM/h/»riiHf m patent dobljeni kriterij zadovoljuje posoJe a), b) in c). Poaoja d) in e) sta izpolnjena, če v množici testnih primerov velJaJo apriorne verjetnosti razredov Pr, r=l..R. 3. ASISTENT Sisten, Ki smo aa razvili iz Quinlanoveaa ID3 (Quinlan 791. smo poimenovali SSISTENT. Osnovni alaoritem sistema 1D3 (aleJ posi. 1) smo razSirili in izpopolnili v naslednjih smerehi 1) V ASISTENTU Je implementirana aradnja odločitvenih dreves brez iteraciJ. fišISTEST lahKc oSravnaus nepopolne podatke. 3) fiS!3TE! Ki nina podane vr'ednosti atributa v uozlu> se upoitevajo sano apriorne verjetnosti vrednosti v vozlu (P(V1), V poal. 4.3.1 Je podana priaerjavi eKiperiaentalnih rezultatov dobljenih z dvtaa opisaniaa naiinoiia obravnavanja nepopolnih podatKov. 3.3 KLASIFICIRANJE S PQMQiJQ BAVESQUEGA PRINCIPA 21 Dobljeni intervali so lahKo pristranskir neobjektivni.-povrini ali neuporabni za aradnJa odloSitveneaa drevesa (npr. strokovnjak bo vrednosti atributa starost razbil na intervale po 10 letr teprav pri svoJe« delu ne dela razlik» ned vrednostni od SO do 70 let in od 70 do 80 let). Reiitev. ki Je inple«entirana in preizkuSena v ASlSTENTu Je ta> da vsak zvezni atribut postane binaren. neJat ki razdeli interval Hoinih vrednosti na dva podintervalar se doloti avtonatsko: to Je laeJa. ki maksiaizira atributovo inFomativnost. AtribuJ se lahko ponovno poJavi v poddrevesu. katereaa prednik Je sa«r vendar z nanjiin intervalon «oinih vrednosti. Ista reiitev Je privzeta v sistenu ACLS (Paterson in Niblett 82). adloiitveno drevo je nezanesljivo» te nimaaia polne nnoiice atributov (nnoiica atributov ne zadostuje za eKsaktno klasifikacijo vseh pritierov). Je iuasio prenalo ufnih priaerov. Je drevo ie toliko slabSe. Zanesljivost drevesa se izraJa v {tevilu primerov v listih drevesa, de Je v listu sano en uSni primer, pote» Je KlasiFikaciJa s ten listom nezanesljiva. Ekstremni primer Je prazen list (NULLS. Klasifikacija priserov s praznimi lis'ti Je nemoaoäa. z listi z malo prìKeri pa nezanesljiva. k' ASISTENTU je reSen problem praznih listov z Ea/esovim usrjetnostni» principom, ki Je izpeljan v Poal. 2.3. fted samo aradnjo se vsakemu listu pripiieJo verjetnosti razredov, dobljene po Baresovem verjetnostnem principu z 'jpoitevanje« atributov, ki nastopajo od korena drevesa lio daneaa lista, ie Je list prazen, poten se mu pripi&e rizred z naJvefJo izračunano verjetnostjo. Ce se v n:fprazenn listu izračunane verjetnosti uJeeaJo s primeri v listu. Je list zanesljivejši za klasiFikaciJo novih primerov. IZBIRA DOBRIH UtNiH PRIMEROV te mnoiica atributov ni polna da binarna drevesa oponaiajo ilovekov naCin razaiiljanJa. Zdravniki so naa povedali» da saai ne aoreJo naenkrat driati v Mislih vseh aoinih vrednosti za atribute z vet-razliiniai vrednostai. Zato v aislih arupiraJo podobne vrednosti, pozneje pa. ko 2eliJo detajlizirati svoJe razaillJanJe. razbiJeJo arupe vrednosti na posaaezne vrednosti atributa. ToreJ Je binarno drevo razualJivo KlJub navidezni slabi strukturiranosti. Polea tesa so dobljena drevesa nekajkrat aanJia (aleJ posl. 4.3.3) in 19 it zaradi teaa preoeJ laiJe razualJiva. Suinlan (B3>^Jc predlasal druaatno norairanJe ocenitvene funkcije: norairanJt na potrebno kolitino infornaciJe za pridobitev vrednosti daneaa atributa. Tako Je norairana inforaativnost QN1 atributa A> Ki iaa V aolnih vrednosti »naka: Inf(A) ONKA) • —^----------. P» Je verjetnost - y Pv loa Pv v-ttf vrednosti atributa A. v 2 T» norairanJe Je posplolitev norairane funkcije NI. »•.inKciJi sta enaki, ko velJa Pv « I/V. v«t..V: natantnosti zelo podoben inForaaciJski funkciji. Vendar za uporabo pri rezanju PotrebuJeao nove priaere za testiranje kl-asif ikaci Jske'nataninosti. Ker Jih niaaao nf razpolaao. aoraao eksperiaentirati z uiniai priaeri v vozlu. Princip rezanJa Je definiran takole: 1. Za vsak priaer v vozlu drevesa ponovi: 1.1 Izlod aa iz anoiice priaerov v vozlu. 1.2 Izberi naJbolJii atribut alede na preostalo anotieo. 1.3 Za dani priaer izrajunaJ klasifikacijske napake z in brez upoltevanJa izbranesa atributa. 1.4 PrilteJ napaka k vsotaaa napak z in brez upottevanJa izbranih atributov. 2. ee Je vsota napak brez upoltevanJa atributov aanJia ali enaka vsoti napak z upoltevanJea izbranih atributov. potea prenehaj aradnJo na tea aestu. sicer nadaljuj aradnJo poddrevesa. Zaradi veCJ* uiinkovitosti Jt alsoritea iapltaentiran tako. da ponovitve pod i. todko opravlja la doloteno itevilo naktJufno izbranih naJhnih podanolic priaerov. Porezana drevesa so aanJia. zaradi teaa bolJ razualJiva in tudi bolJ natandna pri klasifikaciji novih priaerov (alej poal. 4.3.6). 4. POSKUSI V HEDICINl Sistea ASISTENT sno preizkusili v 5 razUJnih inedicinskih doaenah. Eksperimenti so potrdili pravilnost izpopolnitev, opisanih v 3 poalavJu. Tu so opisana Medicinska PodrotJa in podatki, ki sao Jih uporabili v eKsperiaentih. Opisan Je naiin eksperinentiranJa in priaerJava diaanostifne natandnosti ASISTENTa z natandnostJo osnovneaa alaoritaa ID3. z nataninostjo nekaterih statistiinih aetod in z nataninostjo zdravnikov spteialistcu. • T ONKA'). Druaa trditev sledi iz prve: ©viU)" ToreJ. deprav iaata atributa enako inforaaciJsko vsebino. Je norairana ocena atributa A boljia od. ocene atributa A', kar poaeni. da funkcija ONI daJe prednost atributna i anoso vredneitat. 3.7 REZANJE NEZANESLJIVIH DELOV DREVESA Verjetnosti v informacijski ocenitveni funkciji se aproksiairaJo z relaiivBial frekvencami priaerov v trenutno siedane» veilu «ed aradnJo drevesa. Zato Je ocenitvena funkcija zanesljiva samo nad velikiai anoiicaai učnih priaerov v vozlu. Zaradi tesa Je aradnJa drevesa na niijih nivojih, kjer.Je aalo priaerov v vozlih, nezanesljiva. Teau se izosneao z rezaeJea nezanesljivih delov drevesa. V listih ostaja ved razredov, kar pa Je za nepolne anoSice atributov nuJno lalej Poal. 2.2.2). Porezano drevo Je bolJie od drevesa, ki Je zsrajeno nad saao dobriai uCniai priaeri laleJ poal. 3.4). ker opozarja uporabnika ne saao na naJbolJ verjetne razrede. amPak tudi na ao2ne izJeae (nrr. zdravnika opozori na vse aa!ne daisnoze). V AEISTEr^Tu UPorablJamc la rezanje princip uaKsimalne Klasif iKaciJsKe pravi Inrst i. IzreC. S (poal. 2.1.4) »raji. Ja je Kriterij ajSsiaalne KlasifikaciJsKe 4.1 OPIS NEDICINSKIH PODROČIJ IN PODATKOV 4.1.1 LOKALIZACIJA PRIMARNEGA TUMORJA Pri pacientih z odkritiai aetastazaai Je zdravljenje udinkouiteJie. 6e Je znana lokaciJa priearnesa tuaorJa v telesu. Zdravniki loCiJo «ed 22 razliCniai lokaciJaai. Podatki o pacientu, na osnovi katerih zdravnik sklepa na lokacijo priaarneaa tuaorJa. so starost pacienta, spol. histoloiki tiP karcinoaa. stopnJa diferenciacije in 14 MOinih lokacij odkritih metastaz. Diaanostiini problea Je torej podan z 18 atributi in 22 aoiniai razredi (diasnozaai). Iz Gnkolo Nie in sod. 75> Roikar 84, RoSliar in sod. B5), Ki predpostavlja, da vsaK priaer predstavlja totKo v n-dinen:ionalnea prostoru (n Je itevilo atributov, ki opisuJeJo priaere). Metoda iiCe funkcije, ki dolotuJeJo hiperravnine, ki loCiJo ned seboj arupaciJe primerov z istimi razredi. , . , - .. . J.___t " aetoda lupin v n-di«ieniionalneM prostoru (SoKliJ T'D"» Rezultat, aradnje drevesa v 3 «ed.c.nskih doaenah p^j.^rov z istiai nad vse«i utniai primeri in samo nad dobrini uln.i»i primeri, 4.3.5 BINARNA GRADNJA V poalavJu 3.S so opisani razloai za binarno sradnja dreves. Binarna aradnJa Je precej ziiianJSala dobljena odločitvena drevesa. Ki so zaradi teaa lalje razualJiva. V tabeli 4.5 so podani rezultati binarne aradnje v primerjavi z nebinarno aradnjo. doaena način aradnJe it.vozlov it.listov natanCnost primarni nebinarna 242 140 41X tumor b inarna IBB 90 41* rak na nebinarna 130 133 67* doJki binarna 120 83 67* Iimfoara- nebinarna SO 40 ■ 75* fiJa b inarna 3S 22 76* okvare sp.tr. nebinarna 525 33S ezx pri moiKih binarna 353 139 66* Tabela 4.5 Rezultati binarne aradnJe drevesa v 4 medicinskih domenah v primerjavi z nebinarno aradnJo. domena rezanje it. vozlov it. listov natančnost ____________________ -------------------------- ----------- primarni da 35 18 46* tumor ne 1B8 30 41* rak na da 18 3 72* doJKi ne 120 S3 67X 1imfoara- da 25 14 77X fiJa ne 38 22 76* hepa- da 17 3 BOX titis ne 21 11 BOX okvare sp.tr. da 107 5B 67* pri aoikih ne 353 199 66X okvare sp.tr. da 174 92 81* pri /enskah ne E35 357 78X Tabela 4.5 Rezultati aradnJe drevesa v 5 »edicinsKih domenah z in brez rezanja nezanesljivih delov drevesa. 4.3.B REZANJE V poslavJu 3.7 nezanesljivih drevesa. Ki so razpolollJivo ■olne diagnoze pri klasifikac reranjr res re tabeli 4.B so prinerJavi z a ■Ireuesä. so opisani razloai za rezanje delov drevesa. Z rezanjem dobimo manJIa bolJ razumljiva, vendar nosiJo v sebi vso informacijo (opozoriJo zdravnika na vse ). Dobljena drevesa so tudi bolj natančna iJi novih primerov, kar PotrJuJe, da Je zanJe nezanesljivih delov drevesa. V podani rezultati sradnJe z rezanjem v radnJo brez rezanja nezanesljivih delov V tabeli 4,7 so primerjalni rezultati (doselena natančnost diaanosticiranJa) eksperimentiranja v 6 različnih medicinskih domenah. Vse metode, tako statistične kot ASISTENT, so doseale v vseh domenah natančnost diaanosticiran Ja zdravnikov specialistov. Bistvena prednost ASISTENTa Je v razumljivosti doblJeneaa odločitvenesa pravila, iz katereaa lahko zdravnik direktno razbere loaiko sklepanja in lahko celo uaotovi določene relacije in zakonitosti v svoJi domeni (Zuitter in sod. S3). Odločitveno drevo se lahko uporablja tudi brez računalnika, npr. Kot priročnik za diaanosticiranJe. domena primarni tumor raK na dcJki hepatitis liafoaraFiJa okv.ur,tr.Maitti oKv.ur.tr.ienske Bares disKr.anal. lupine ASISTENT 45* - 47r. 4SI 74X(B3X) - - 721(631) BSXOOX) - - B0Z(7tZ) 67X - sax G5X 67* - - 67* 79X BU - 81* Tabela 4.7 PriaerJava doseiene diaanostične natančnosti treh statističnih netod za avtomatsko učenje in sistema ASISTENT. Znak pomeni, da ustrezni poskus ni bil izveden. V oklepajih so dodane ocenjene natančnosti, oblelene z obratnimi apriorniai verjetnostmi (alej poal. 2.4). Pri limfoarafiJi so z» p'ùterjo.iro z metodo lupin podani rezultati eksperimentov, kjer Je aoinih 6 različnih diaanoz (aleJ 4.1.3). 4.5 PRIMERJAVA ASISTENTa Z ZDRAVNIKI SPECIALISTI Dobljeni rezultati (diaanostična natančnost) v primerjavi z zdravniki specialisti »o podani v tabeli 4.8. domena primarni tumor rak na doJKi limfoarafiJa ASISTENT 46X 727. (B3X) 77* ZDRAVNIKI 42X E4X(63X) 85X-ocena Tabela 4.S Primerjava dose!ene diaanostične natančnosti sistema ASISTENT in zdravnikov specialistov. V oKlepaJih so dodane ocene natančnosti, obtežene z obratnimi apriornimi verjetnostmi razredov (aleJ 2.4), Ob teh rezultatih bi aoaoče Kdo pomislil, da računalnik lahko nadomesti človeka, kar Je zmotno mnenJe. Računalnik ne bo in ne more izpodriniti zdravnika, lahko pa mu pomaaa, da svoje delo opravlja hitreJe, laiJe in natančneje. ASISTENT Je sploien sistem, le poskuse smo do sedaj delali samo na podatfiih iz medicine. 5. IMPLEHENTACIJA Podrobnosti iapleatntac i Je so podane v (KononenKo SSa). Tu Je OPisana osnovna ideJa implenentaciJe in neKatere dodatne lastnosti sistena ASISTENT. 5. ZflKLJUtKI. 6.1 UPORABNOST ASISTENTA NaJueiJa teia alaoritna za aradnJo odločitvenih dreves Je v izbfri naJbolJ infornativneaa atributa. Pri binarni aradnJi Je naloaa ie zahteuneJSa. ker Je potrebno za vsaK atribut PoisKati dve disJunttni podnnoüci «rednosti» ki nalisisizirata atributovo inFornativnost, Za utinkovito opravljanje te naloge Je Quinlan (79) uPorablJal iterativni principr opisan v poal. 3.It taKo da Je vse priaerer nad katerimi Je aradil drevo (okno)> hranil v hitrem pomnilniku. IdeJa isplenentaciJe v ASISTENTU Je tat da primerov ni potrebno drjati u hitrem pomni 1 nikui ampak zadostuje samo statistika primerov po atributihi vrednostih atributov in po razredih. Pri tem se intervali moinih vrednosti za zvezne atribute razbiJeJo na dovolj maJhiie podintervale. katerih indeksi predstavljajo Kodo vseh vrednosti v dane« podintervalu. TaKo Je poraba -ponniInijkeaa prostora neodvisna od števila primerov. Npr. te Jelj,BO hraniti v hitrem pomnilniku 200 primerov. 0'isanih z 20 atributi, potrebujemo pribliJno 4K pomniIniJkeaa prostora. Ce Je «oSnih 10 razredov in naJvei 15 možnih vrednosti za en atribut, potem za i'.atistiKo poIJubneaa Števila primerov iz iste fi-ob.lemske domene porabimo tudi pribl. 4K pomni Ini SKeaa prostora. Statistiko sestavimo vedno za usak vozel drevesa ."isebeJ. Primeri iz vozlov so na datoteki. Ko Je primerov v vozlu zadosti mala> Jih prenesemo v hitri HoanilniKt da pospeiimo sestavljanje statistike. Enkrat n.jreJena statistika za en vozel omoaofa hitreJSe izraJunavanJe informativnosti atributov» kot Je Jo delamo posebej za vsak atribut in za-vsako motno razdelitev vrednosti atributa na dve disJunl'.tni podmnožici. Pri binarni aradnJi Je Kritićno arupiranje vrednosti diskretnih atributov, »i kombinatoriSno naraJJa s jtevilo« razlitnih vrednosti atributa. V trenutni implementaciji smo se temu delno izoanili tako. da diskretne atribute oeenJuJe naJpreJ normirana ocenitvena funkcija (aleJ 3.B). Nekaj naJbolJSih diskretnih atributov se zatem octnJuJe z iztrpno arupaciJo vrednosti v dve disJuektni podmnoiici na vse mo2ne. načine. Iskanje hitrih in douolJ dobrih hevristienih alaoritmov za arupaciJo vrednosti.diskretnih atributov Je predmet nadalJnJesi dela. V sistemu ASISTENT Je implementirana tudi statistiC.na metoda. Ki temelji na Saresovea verjetnostnem principu Pr 41.IX 42 13 237 O.III S3.3X S4 8 200 0.580 E2.EX 85 14 105 0.35B prim.tumor 4SX rak na doJki 72X limfoarafiJa 77X S.l Primerjava natanCnosti ASISTENTa in ocenjene spodnJe mej« natanCnosti popo1neaa; s i s tema (aleJ poal. 2.2.2). Meja M naJveCJe možne natanCnosti razvrSCanJa pri dani množici atributov Je ocenjena z natanCnostJo zdravnikov specialistov. 52 IzKaie s Ci] VAX/VMS GUIDE TO USING COMMANO PROCEDURES, Digital Equipment Corporation, 1982. C53 Bratko, I.: INTELIGENTNI INFORMACIJSKI SISTEMI, Univerza Edvarda Kardelja, Fakulteta za elektrotehniko« Ljubljana, 1981. C6D Bratko, 1.: EXPERT SYSTEMS AND. PROLOG, Supercomputer Systems- Technology (ed. F. Sumner), Infotech State of the Art Report, Vol. 10, No. 6, 1982. ANALITIČKI POSTUPCI U ODREDIVANJU NEPRODUKTIVNE OBRADE ZA JEDNU VRSTU PROCESNIH RAČUNARSKIH SUSTAVA Nikola Bcgunović, Institut "Ruder Bošković", Zagreb UOK: 6813.012 SAŽETAK: U radu se razmatraju nekonzervativni procesni računarski sustavi s jednorazinskim prioritetnim raspoređivanjem grupa ulaznih događaja. Pokazuje se da, pri visokim ulaznim intenzitetima, računarski sustav troši značajan dio ukupnog vremena na neproduktivan rad oko pripreme i prihvata događaja, te reorijentacije na istu ili novu obradu. Za neke jednostavnije primjere procesnih računarskih sustava dati su postupci za određivanje globalnih radnih indeksa koji najvjernije opisuju aktivnost sustava i omogućuju ocjenu efikasnosti. ANALYTICAL PROCEDURES OF ESTIMATION THE OVERHEAD PROCESSING TIME FOR A CLASS OF REAL-TIME COMPUTER SYSTEMS: In this paper nonconservative real-time computer systems with single level priority scheduling of input events are considered. It is shown that under high data arrival rates computer consumes a considerable portion of the total system time on nonproductive work such as event acquisition and set up conduct for the continuation of the processing. The procedures for estimating the global descriptor indexes, which most accurately characterize the performance of the system and enable measurement of the efficiency, are given for some prevalent models. 1. UVOD Procesni, ugrađeni računarski sustavi djeluju u sredini s vlastitim dinamičkim karakteristikama, koje na taj način nameću ograničenja i na procese unutar računala. U takvim sustavima gotovo u pravilu susrećemo više asinhronih zadataka koji se u strukturi računala s jednim procesorom međusobno prekidaju kako bi poslužili ulazno-izlazne ili druge prioritetne zahtjeve. Prema sadašnjem stanju građe i organizacije takvih sustava može se uočiti da često usvojena pretpostavka o konzervativnosti predstavlja samo grubu aproksimaciju realnih sustava. Pri visokin intenzitetima dolazaka vanjskih događaja, računarski sustav troši značajan dio ukupnog vremena na neproduktivan rad oko suspendiranja procesa u toku, pripreme i prihvata novog ulaznog događaja, te reorijenta-cije na istu ili nrivu obradu. Razumljivo je da takav neproduktivan rad degradira osnovne parametre sustava (odzivno vrijeme ili pi»opusnost, broj neobrađenih događaja u čekanju i si.) U ovom radu istražit će se utjecaj neproduktivne obrade na efikasnost računarskih sustava koji prihvaćaju niz različitih događaja iz ulaznih jedinica koje su direktno vezane na tehnološki, nijemi ili neki drugi proces. Razmatrani a-.3del ugrađenih računarskih sustava sadrži velit broj izvora događaja koji su razdijeljeni u k prioritetnih grupa ( i = I ,2 , . ., ,k ) pren;a osnovnim fizikalr.ir. veliči--a-a kcje predstavljaju. Općenito gledano, ulazni procesi pokazuju stohastička obilježja i najvjernije se mogu modelirati nezavisnim Poissonovim procesima /1/,/2/.U razmatranju procesa obrade često se može pretpostaviti homogena populacija pristiglih događaja. Razdiobe vremena obrade homogenih događaja imaju jednak oblik ali različite intenzitete po grupama, međutim točan oblik te razdiobe nije jednostavno odrediti. Zbog toga će se u nastavku analizirati sustav s općom razdiobom vremena obrade iako to unosi određene poteškoće u matematičko analitičke postupke. Prema standardnim oznakama u teoriji repova, predmet analize biti će sustavi koji se mogu opisati modelom M/G/1 s k grupa prioritetno raspoređenih izvora slučajnih događaja (i=1 ima najveći prioritet). Nesmetano odvijanje nekoliko nezavisnih zadataka u računarskom sustavu zahtjeva da se ovi procesi mogu prekinuti i nastaviti kasnije s jednoznačnim konačnim rezultatom. Stanje sustava nakon k koraka možemo označiti višedimen- • zionalnim vektorom Stanje sustava izraženo vektorom , nakon k+1 koraka, jednoznačno je određeno prethodnim stanjem Sj^. Uvjet za ovakvo ponašanje jest, da se stanje procesa između prekidanja i njegovog nastavka sačuva, da procesi u računarskom sustavu jedan drugom ne mijenjaju stanja, te da se svaki odvija na vlas'itorr. skupu registara i mentori iskih Isksoi-jp.. 3uriuói da sačuvanje i obnavljanje star.;a zadataka traži konačno vrijeme,posebice u sus- tavima s Jednim kompletom registara, to je računarski sustav nekonzervativan. 2. UTJECAJ NEPRODUKTIVNE OBRADE NA GLOBALNE PARAflETRE SUSTAVA Kvantitativan utjecaj neproduktivne obrade, zbog reorijentacije na novi zadatak možemo razmotriti na primjeru sustava s disciplinom odabiranja događaja u obradu prema redoslijedu dolaska (FCFS). Na slici l.dati su rezultati mjerenja u M/D/1/FCFS sustavu. obrade. Opažamo strmi porast omjera izmjerene srednje vrijednosti broja događaja u repu čekanja i očekivane vrijednosti u stacionarnom sustavu bez utjecaja neproduktivne.obrade. [1-41 »hhl-l'cf» r-u 1 .'■^«L- _______ y.o,. Slika 2. E(n )/n M/M/1/FCFS sustavu q q .to' Slika 1. E(n„)/n„ u M/D/1FCFS sustavu q q Ha apscisi je dat intenzitet dolazaka događaja, a na ordinati omjer izmjerenog srednjeg broja neobrađenih događaja u repu čekanja (n^) prema izračunatoj i izmjerenoj očekivanoj vrijednosti E(nj^), za stacionaran sustav bez utjecaja neproduktivne obrade. Očekivanje E(n^) izračunato je za ,M/D/1/FCFS sustav iz Pollaczek-Khin-chin izraza. Eksperiment je izveden na računarskom sustavu DEC PDP-11/03L. Ulazni Poissonov proces ostvaren je pseudo-slučajnom binarnom sekvencom generiranom iz posmičnog registra s linearnim povratnim vezama. Dobivena diskretna razdioba poslužila Je kao aproksimacija eksponencijalne kontinuirane razdiobe Poissonovog procesa 121. Srednje odzivno vrijeme, kao moment kontinuirane slučajne veličine, teško je mjerljiv direktno, već se može odrediti iz srednjeg broja neobrađenih događaja u čekanju, koristeći teorem J .D.C.Littlea , koji predstavlja invari-jantu u sustavima s repovima čekanja. Na slici 1 opažamo da pri niskim intenzitetima n^ = E(nq), što Je i razumljivo jer neproduktivna obrada nije zamjetljiva. S pa.ve-ćanjem intenziteta računarski siistav troši proporcionalno sve više vremena na neproduktivan rad, te razlika TT^ - E(n^) postaje sve veća. Na slici 2 prikazan je"utjecaj neproduktivne obrade u sustavu N/M/1/FCFS, t.j. s eks-poner.cijslr.or. razdiobom vremena između poj-ave i eksponenoiJalnoir. razdiobom vremena U oba mjerenja odabran je faktor iskorištenja sustava (^ = 0.8. To je umnožak intenziteta ulaznih događaja i očekivanog vremena obrade E(x) i predstavlja ustvari srednji uneseni posao u sustav. Iz rezultata mjerenja zaključujemo da Je utjecaj neproduktivne obrade doista značajan i u krajnjim točkama znatno veći nego što bi se moglo kompenzirati s teoretski uspješnijim disciplinama odabiranja događaja u obradu /3/. 3. NEPRODUKTIVNA OBRADA U M/G/1/FCFS SUSTAVU Sustav s eksponencijalnom razdiobom između podave ulaznih događaja, općom razdiobom vremena obrade i odabiranjem događaja u obradu prema redoslijedu dolaska, vrlo je detaljno istražen. Glavni parametri sustava dati su Pol-laczek-Khinchin izrazima, od kojih se najčešće koristi očekivanje broja događaja u repu čekanja.: A^E(x^) p ( r, 1 -A C. V X 1 (3.1) E{x) i (Ex'^) su momenti vremena obrade, a faktor iskorištenja ^=Ae(x). Prema teoremu Littlea, očekivano vrijeme u repu čekanja Je: XE{x^) (3.2) Neproduktivnu obradu možemo definirati kao slučajnu veličinu o koja je opisana funkcijom razdiobe V(o) i funkcijom gustoće razdiobe v(o). U sustavima bez raspoređivanja ulaznih događaja u prioritetne grupe, neproduktivnu obradu možemo zamisliti kao dio vremena koje se dodaje vremenu obrade x. Iz ove pretpostavke slijedi da u analizi M/G/1/FCFS sustava s neproduktivnom obradom, ukuono vrijeme obrade x , ' o shvaćamo kao sumu nezavisnih kontinuiranih slučajnih veličina:•=X + o. Tada Je.očekivanje. 64 i varijancija sume: E(x„> = E{x) + E(o) O o (3-3) Na temelju izraza (3.3) odredimo i E(x^) koje uvrstimo u (3.1) i (3.2) i tirne su najvažniji parametri za ocjenu aktivnosti M/G/1/FCFS sustava odredeni. Funkcija razdiobe i funkcija gustoće razdiobe složene slučajne veličine date su konvolucijama : B(x^) = B(x)»f-V(o) b(x^) = b(x)«-v(o) (3.t) gdje su B(x) i b(x) funkcije razdiobe i gustoće razdiobe vremena obrade x. Neka je b(x) data eksponencijalom b(x) = u exp (-ux), a gustoća razdiobe neproduktivne obrade također eksponencijalom v(o)= aexp(-av), gdje su u i a odgovarajući intenziteti u = 1/E(x), a = 1/E(o). Jednostavno se može izračunati da je u tom slučaju gustoća razdiobe veličine Jednaka: Ako je b(x) data eksponencijalom, a v(o) uniformnom razdiobom v(o) = 1/h za Oaosh, v(o) r 0 za o>h, tada je gustoća razdiobe sume: 1 b(x„) = ^-"^e"^ 1) Ako je b(x) data eksponencijalom, a V(o) je deterministička t.j. v(o) = cl (o - 0"), gdje je cfio) Dirac delta funkcija, gustoća razdiobe sume ovih slučajnih veličina iznosi: , -u (x - a) b(x^) : u e o Pri uniforranoj razdiobi veličina x i o: b(x) = 1/a Osx^a. b(x) = 0 x> a v(o) : 1/b 0b slijedi : = -iV «''o - ^=<0 - ^^ = - - s(x^-b) » (Xp-a-b) s(x^-a-b)) gdje je s(x-a) pomaknuta funkcija jediničnog skoka. Uz obje determinističke razdiobe b(x) =J;x-a), v(o) = d(v-ff) slijedi trivijalno: b(x^) = o - a - a) Konačno za uniformnu i determinističku razdiobu slučajnih veličina x i o: r ( >: ) = ■ / h 0 £ X i" h b ( x ) = 0 x > h , v;-) = d (o - 3-) slijedi: b(x^) r i/h(s(Xjj - O") - s(x^ - h - Or) ) Izraz se jednostavno računa uz upotrebu Lapla-ceove transformacije. - O) je pomaknuta funkcija jediničnog skoka. t. NEPRODUKTIVNA OBRADA U SUSTAVU M/C/1FCFS SA K GRUPA IZVORA ULAZNIH DOCADAJA Razmotrimo računarski sustav s k grupa izvora slučajnih dogadaja na ulazu ali s disciplinom obrade.prema redoslijedu dolaska (FCFS) bez obzira na pripadnost grupi. Pretpostavimo da postoji značajna neproduktivna obrada kao slučajna veličina o, samo kad se uzima u obradu događaj iz grupe različite od grupe prethodnog dogadaja. Pretpostavimo nadalje jednake intenzitete grupa = A/k , i = 1 ,2, . . . ,k, te opće razdiobe vremena obrade B^(x) =G. Svaki događaj traži vrijeme obrade: = X s vjerojatnošću 1/r (pripada istoj grupi) =X+o 3 vjerojatnošću (1-1/r) (pripada različitoj grupi) Potrebno je izračunati momente slučajne e X . Bi m visne slijedi: = E(x)/r H + (1 - l/r) E(o) veličine x . Budući da su veličine x i 0 neza-m E(Xj^)=E(x)/r + E(x + o)(l-1/r)rE(x) E(x^) = E(x2)/r + E(x + 0)^(1 - 1/r) = E(x^) + (1 - 1/r)(2E(x)E(o) + E(o^)) Faktor iskorištenja sustava se povećava zbog dodatnog vremena obrade o i iznosi: Sm = S' * - E(x.^o) = (j( + (1 -1/r) E(o) Pri tome je zbog nezavisnosti E(x + o) = E(x) + + E(o). Dobiveni izrazi mogu se" uvrstiti u Pollaczek-Khinchin izraze (3.1) i (3-2). Ra? P zumljivo je da momente E(x), E(x ), E(o), E(o ) treba računati iz pretpostavljenih razdioba vremena obrade B(x) i vremena neproduktivne obrade . 5. NEPRODUKTIVNA OBRADA U PRIORITETNIM SUSTAVIMA M/G/I/PRI BEZ MOGUĆNOSTI PREKIDANJA Razmotrimo stacionaran i ergodičan računarski sustav s k prioritetno raspoređenih grupa ulaznih događaja. Pri dolasku dogadaja iz prioritetni je grupe obrada događaja koja je u toku se ne prekida, već se prioritetniji događaj uzima u obradu tek po završetku prethodne obrade. U literaturi ne nalazimo razrađen postupak primjenljiv u općem slučaju za sustave s k ulaznih grupa. Analizirat će se jednostavniji primjer s dvije prioritetno raspoređene grupe izvora slučajnih događaja (k=:2) interzile- ta A, i Ap. Sustav je dat na slici 3 a. susi4v za obmadu o I rep čekanja Slika 3. M/G/1/PRIORIX, sustav bez prekidanja Neka je vrijeme neproduktivne obrade za reori-jentaciju s grupe 1 na grupu 2 dato vremenom . Nakon reorijentacije, ako je rep čekanja grupe 2 prazan, ponovo nastupa reorijentacija s grupe 2 na 1 tokom vremena jfi- Ako je rep čeka- nja grupe 2 neprazan, obrađuje se događaj u vremenu x^ i ponovo se sustav reorijentira na grupu 1 u vremenu j. Ako je rep čekanja grupe 1 neprazan, obraduje se događaj u vremenu i ispita se stanje repa u vremenu Pretpos- tavimo da su slučajne veličine x i nezavisne i date razdiobama B(x) i R^(t) odnosno gustoćama b(x) i rj^ (t). U /U/ je .predloženo da se ovakvi sustavi raogu riješiti analizom jednostavnijeg modela s jednim repom čekanja i neproduktivnim dijelom vremena obrade ^^ i .6^ (slika 3b). Zamislimo da sustav■za obradu nakon vremena obrade ispituje jedini rep u čekanju u vremenu Ako je rep prazan sustav miruje tijekom vremena 'S j. Nakon toga, ako je rep neprazan, sustav prolazi ciklus + 3.. Definiramo vjerojatnost g^^ da se u času ispitivanja u čekanju nalazimo n dogadaja. Primjenjujući relaciju za prijelazne Vjerojatnosti u M/G.'1 sustavu /5/, na model dat r.a slici 3b, te budući da se rep čekanja ispituje u cva trenutka (nakon mirovanja i nakon obrade) slijedi: n 0 j n. :--> I \ <= J g, vjerojatnost da u-časi. ispitivanja 0 nal3-'.:::o prazan rep čekanja, a rit) su gustoće r^zžiczs kontinuiranih sijč-fijnih veličina vre- mena. Slično, u trenutku završenog vremena obrade broj dogadaja u sustavu iznosi: "s = "s «0 n t- 1 I i = 1 o (n-i. 1)! ^ r^(t)dt (5.2) Ako načinimo z - transformaciju izraza (5.1) i (5-2) slijedi formula za transformaciju razdiobe vjerojatnosti broja dogadaja u sustavu da-tom na slici 3b: Q(z) = i (X - Xz) - 1 Ri ( >. - Xz) (5.3) gdje su R (s) Laplaceove transformacije gustoća razdioba vjerojatnosti r(t). Koristeći .-so-ment generirajuće svojstvo transformacija, iz (5.3) Jednostavno se izračuna ju očekivanja broja dogadaja u sustavu kao i vjerojatnost za prazan rep: g^/(l- g^) = (1 . \E{ k * /3^))/ X E( /Ij) (5.4) Primjenjujući analogno razmatranje možemo analizirati model dat na slici 3a. Promatrajući neprioritetni rep uočavamo da je vremenski ciklus obrade jednog dogadaja iz repa 2 i ispitivanje repa 2, jednak poopćenom periodu zauzetosti repa 1. Taj se period sastoji iz dijelova ispitivanja ( ), »obrade (X2), reorijenta^ cije na rep ( , početne obrade dogadaja koji su stigli u rep 1 za vrijeme + x^ + Jj , te obrade ostalih dogadaja u repu 1 od početka njegovog perioda zauzetosti. Prema ideji L. Ta-kacsa i D.P.Caverà /5/, a zbog nezavisnosti vremenskih razmaka, slijedi za poopćene periode zauzetosti: YC21 = X,- >,Y''(s)) Y'^CS)). ^3 (s h X, - X, y''(s)) (5.5) Pri tome je Y^^j^Cs) Laplaceova transformacija gustoće razdiobe vremena ciklusa obrade dogadaja iz druge grupe, B* (s) Je Laplaceova transformacija gustoće räzaiobe vremena obrade događaja iz druge grupe, a Y*(s) je transfor.t.acija giistoće razdiobe standardnih perioda zauzetosti y 'Koji, budući da se sastoje iz nezavisnih dijelova i zadovoljavaju relaciju: y''(s) r B^ (s-X. -x, Y*(s)) R", (s-^X, ->.,y''(s)) 1 . 63 ' ' Na identičan način možemo razmotriti vremenski ciklus u slučaju praznog repa 2 i pisati za "i^^^is) izraz kao (5.5). uz supstituciju jf, un^jesto Xj. Usporedbom modela sa slike 3a s T-odelon:' 3b,. opažamo da u izrazu (Ö.3) ur.jesto :lavi-i r.oavl ja- 66 mo a umjesto H* nLriv]Jrimo n* . Iz tnko dobivene relacije možemo odrediti momente t.J. očekivani broj događaja u repu 2. Promotrimo sada prioritetnu grupu događaja u codelu na slici 3a. Ciklus obrade sastoji se iz vremenskih razmaka X-] + jfj - Prema tome relacija analogne (5.5) glasi: Ciklus praznog hoda nešto je kompliciraniji. Alco je rep 1 prazan vremenski razmak sastoji se iz nezavisnih vremenskih sekvenci jj-^ , Xg s vjerojatnošću (1 - gjg^' Ifs ^ vjerojatnošću (5.6) Usporedbom modela 3a i 3b opažamo da u relaciji (5.3) umjesto R^^ stavljamo if^ig' ""J^sto P-x+.S, stavljamo a umjesto R^t stavljamo B* ■ Iz dobivenog izraza, koristeći moment ge-nerrirajuće svojstvo izračunamo očekivanje broja događaja u prioritetnom repu 1. Vjerojatnost gjQ (prazan rep 2) izračunamo iz (S.fJ) tako da umjesto E(oc»/3^) stavimo očekivanje perioda zauzetosti E'Vjs' dobivenog moment generirajućim postupkom iz ' ^ "mjesto ii^) stavimo očekivanje ^(j-gi) dobiveno iz Intenzitet > = Xj- Prema /5/, transfor-nacija razdiobe vjerojatnosti broja dogadaja Q(z) i Laplaceova transformacija gustoće razdiobe vjerojatnosti vremena u M/G/1 sustavu • W* (s), vezani su jednostavno Q(z)=W* ( X - Xz), "s "s te su time relacijom (5.3) određeni i vremenski parametri sustava. 6. NEPRODUKTIVNA OBRADA U PRIORITETNIM SUSTAVIMA H/G/I/PRI S PREKIDANJEM Razmotrit će se model računarskog sustava s k-grupa izvora slučajnih dogadaja uz mogućnost prekida obrade i nastavka u točki prekida. Unutar pojedine■prioritetne grupe sustav odabire događaje u obradu prema redoslijedu dolaska (FCFS). Prema slici «a, u času t^ događaj dj dolazi u sustav i priključuje se repu čekanja. U času t.^ događaj dj prvi puta ulazi u obradu. Vrijeme čekanja u repu iznosi w . i t, - t . Prije svakog početka obra-qj 1 o de, potrebno je kompletno pripremno neproduktivno- vri jerae , koje za događaj dj iznosi Iza kompletnog pripremnog neproduktivnog vremena o^j^, slijedi obrada (dio od Xj), pa mogući prekid, tokom kojeg je obrada blokirana kroz vremenski razmak "(jj^i zatim cpet kom-, pletno pripremno neproduktivno vrijeme-o^j2, te se tako ciklus ponavlja do trenutka t^ kad ''i 511. ZavRSElAK OSRiOE prdiidl ■"dj obrada ćr«t| prio(»mo iOiji'Oj/ cl •v prekidi segmenti pn'preme b) V kompletno pripremno vrijtme Slika t. M/G/1/PRI0RIT. sustav s prekidanjem događaj konačno napušta obradu. Kompletno pripremno neproduktivno vrijeme o^^jj^. sastoji se prema slici tb, od segmenta izgubljenog neproduktivnog vremena o segmenta blokiranog vre-w j mena w^^j .i konačno segmenta uspješnog pripremnog vremena Oj, budući da pretpostavljamo mogućnost prekida i tokom neproduktivnog vremena pripreme obrade. Slučajna veličina o^ data je za pojedinu grupu izvora slučajnih događaja razdiobom V^(o), gustoćom razdiobe Vj(o) i pridruženom transformacijom V*j(s). Slučajni vremenski razmak od trenutka prvog ulaska događaja dj u obradu do trenutka potpunog završetka obrade (rezidentna vrijeme) = zäuzi^ä'^IJ^JČnu ulogu u analizi pri- oritetnih sustava s prekidanjem dogadaja u obradi. U sustavima bez prekidati ja, evidentno je "rj - '^j- Opisani model sustava s neproduktivnom programskom podrškom može se dekpmponirati na prekidne sustave bez neproduktivne programske podrške s nastavkom obrade u točki prekida (M/G/1/PRI-PRN) te na sustave s nastavkom obrade s početnim vremenom obrade (H/G/1/PRI-PRP). Za sustav bez neproduktivne obrade i nastavkom obrade u točki prekida, rezidentno vrijeme dogadaja d. sastoji se iz segmenta obJ rade x^j te vremena blokade w^^j, odnosno iz totalnog vremena obrade (Xj) i segmenata vremena blokade U sustavu s nastavkom u točki pre- kida, ukupno vrijeme obrade jednako je za-htje-vanom vremenu obrade j-te grupe, tj. = xj , pa su transformacije pridruženih gustoća razdioba identične. U sustavu bez neproduktivne obrade i nastavkom obrade u točki prekida s identičnim, početnim, vremenom obrade izabranim iz Ej(x), ukupno vrijeme obrade sadrž: nekoliko izgubljenih (prekinutih) segmenata obrade i jedno uspješno vrijeme obrade Xj. Rezidentno vrijeme u takvom sustavu sastoji se iz N zavisnih parova + Xj^j i jednog vremenskog razmaka uspješne obrade Xj. U literaturi /5/ nalazimo transformaciju gustoće razdiobe rezidentnog vremena (s). r1 - Budući da u ovom slučaju ukupno vrijeme obrade x^j nije jednako zahtjevanom vremenu obrade Xj, to se transformacija pridružena veličini x„. dobije iz Y* (s) uz supstituciju K * j Y (s) = 1; tj. izostavljanjem segmenata vre- b j ]c mena blokiranja: Y (s) je transformacija gus-bj toče razdiobe vremena blokiranja. U literaturi /7/ također nalazimo Lapla- ceovu transformaciju razdiobe vremena u prekid- nim sustavima (s) izraženu preko rezident-s i nos vremenaT i vremena blokiranja. ,Pazumljivo je da relacija za (s) vrijedi za sve prekidne sustave (PRN, P^P) jer se razlučivanje odvija baš u rezidentnom vremenu odnosno pridruženoj transformaciji Y* (s). "r j Iz tih izraza koristeći, svojstvo generiranja momenata izvedeno je očekivanje vremena u repu čekanja grupe j: ECw^j) = (6.1) Relacija (6.1) daje nam najvažnije parametre u sustavu, ali izražene preko slučajnih veličina i j • Xg je intenzitet prekidanja t. j. xg = x, ♦ xj ♦ ... * xj.i- U trenutku prekida (početak segmenta w^^j) obrade dpgadaja dj, u sustavu se nalazi samo jedan dogadaj višeg prioriteta (s indeksom 1 r.jfl ' Analizirajući sliku Ua, uočavamo da se nakon prvog segmenta o^j^ promatrani sustav ponaša kao M/G/VPRI-PRN s intervalima blokira- "bji * ®cji' nezavisnosti slijedi za rezidentno vrijeme: y* (s) = y" (s)-b"(s+X, -X y* (s) y" (s)) "rj °cj J ^ ^ "bj ^ "cj Iz gornjeg izraza iskoristimo moment generira-juće svojstvo i izračunamo momente: _E.(wj,j) = f,(E(o^j), E(w^j), E(xj)) (6.8) E(w2j) = f2(E(o^j). E(o2J), E(w2.), E(XJ), E(x2)) (6.9) Prema s'lici Hb, kompletno neproduktivno vrijeme o^j analogno je rezidentnom vremenu u sustavu s prekidima i nastavkom obrade s početnim vremenom, ti/6/ nalazimo izraz za transformaciju rezidentnog vremena, koja s novim oznakama glasi: ' -(s- (s) = °oj (s. >^)e Iz (6.10) izračunaju se momenti: E(o^j) = f3(E(w^,j),E(o^j)) E(o2j) = f,(E(w,,),E(w2,), E(o„,),E(of,)) _ v,(o) do (6.10) -(s+xjo J bj' "bj/ gj gj' (6.11) (6.12) Period blokiranja dogadaja iz grupe j + 1 -jed- Stavljajući u izraz (6.10) (s) = i", slijedi b j Laplaceova transformacija pridružena ukupnom vremenu neproduktivne obrade iz koje se mogu 68 izračunati momenti E(Ogj) i E(Ogj). Time su dati svi izrazi potrebni u iterativnom postupku odredivanja očekivanja vremena u sustavu i repu čekanja prema izrazu (6.1). > Iteracija započinje s prvom prioritetnom grupom (J : 1) za koju Xg= 0, Wj^j = 0, w^^ = Xj , te se E(w ,) i E(w„.) određuju iz (6.1) direk- H J S J tno. Za ostale grupe, npr. j + 1, za dati E(wjj.), E(w^j), E(w^j), E(w^j), iz (6.5) i (6.6) slijedi E(w^ J+1^' ^^"b j+1^" Supstitucijom u (6.11) i (6.12) slijedi E(o c,j i+1)' j+1^ slijedi nezavisno iz modi- ficiranog izraza (6.10) stavljanjem Y* (s)=1. Si;pstifJcijorr: u (6.3) i (6.9) slijedi r,j+l E(w_ te konačno iz (6.1) slijede "očekiva- nje vremena u sustavu ili repu čekanja gru^e j - 1. /K/ C.E.Skinner: A priority Queueing System with Server Walking Time, Operations Research, mi966) str. 279-285. /5/ L.Kleinrock: Queueing Systems, Vol.n, John Wiley, 1975, 1976. /6/ B.Avi Itzak: Preemptive Repeat Priority Queues as a Special Case of the Multipurpose Server Problem, Operations Research, JM (1963) No.K, str 303-320. /7/ R.W.Conway, W.L.Maxwell, L.W.Miller: Theory . of Scheduling, Addison - Wesley, 1967. 7. ZAKLJUČAK U ovom radu pokazano je i dokazano mjerenjem da često usvojena pretpostavka o konzervativnosti sustava nije ispravna. Pri visokim ulaznim intenzitetima dogadaja, neproduktivni dio vremena u sustavu ima dominantan utjecaj na odzivno vrijeme. Ako je povećanje vremena obrade jednako za sve događaje, bez obzira na pripadnost prioritetnoj grupi, razdioba ukupnog vr'ènena obrade može se izračunati konvolucij-skin teoremom. Ako je neproduktivni vremenski razaak vezan uz promjenu grupe pri obradi FCFS disciplinom, momenti složene slučajne veličine obrade mogu se odrediti uz poznavanje vjerojatnosti pripadnosti-dogadaja istoj grupi. Ta je vjerojatnost proporcionalna udjelu grupe u ukupnom ulaznom intenzitetu. Proračun osnovnih stohastičkih parametara u prioritetnim sustavima bez prekidanja i s prekidanjem pokazao je da analitički pristup može dati općenito upo-trbljive rezultate za relativno jednostavne modele. Nađene su transformacije razdioba vjerojatnosti nekih stohastičkih parametara i pokazano je kako se do momenata traženih slučajnih veličina može doći direktno ili iteracijskim postupkom. RE.-EREN'CIJE: n/ L ..Kleinrock: Queueing Systems, Vol.1: Theory, John Wiley & Sons, 1975. /2/ N.Bogunović: Response Time Measurement of Real-Time Computer Systems with Priority Structures, 10th IMEKO World Congress Proceedings, Prag, CSSR, 22-26.OH.1985. /3' L.Schräge: Optimal Scheduling Discipline, Äcrking paper, Graduate School of Business, Univ. of Chica?" . 197'i . MODEL DEDUKTIVNE BAZE PODATAKA IMPLEMENTIRAN U PROLOGU MARIO RADOVAN, SVEUČILIŠTE RIJEKA, SET-PULA UDK : 6813.01 U eianku je dat je prikaz (prijedlog) modela deduktivne baze podataka, implementiranog u Prologu. Dat je prijedlog naCina kontrole (i tretmana) redundance, uslova integriteta i generirane redundance. Opisane su i primjerima ilustrirane osnovne (do sada implementirane) instrukcije za ažuriranje i komunikaciju sa bazom podataka. U-pred 1oženom modelu naglasak je dat na razvoj kooperativnog komunikacijskog sistema, sposobnog da korisnika Cim potpunije obaviještava o stanju sistema, kao i (mogućim) konsekvencama pojedinih akcija na s i s t e mu. A rODEL OF DEPUCTIVE DATABASE IMPLEMENTED IN PROLOG The article presents a model ai a deductive database, implemented in Prolog, which provides mechanisms lor controlling redundancy and checking integrity constraints and generated redundancies. The query and update instructions (implemented so far) are described and illustrated by examples. The proposed model develops a cooperative communication system, capable of informing'the user, about the state of the system and the (possible) consequences of his actions. 1. UVOD Kod relacijskog modela baze podataka, informacije (podatke) predstavljamo n-torkama, koje u terminima logike prvoga reda moiemo smatrati temeljnim atomarnin formulama. Pojam deduktivne baze podataka odnosi se na proširenje relacijskog modela, dobiveno prihvaćanjem ne saro atomarnih formula (n-torki), već i (zatvorenih) neatomarnih formula slijedećeg oblika: Al A2 An —> B-, gdje su Al, A2, . ., An i B atomarne formule, a rnak konjunkcije ili disjunkcije. Ova- kve formule nazivamo definitnim (definite) klauzulama, a bazu podataka u kojoj nastupaju, definitnom deduktivnom bazom podataka. Bazu 'podataka pritom dijelimo na ekstenzi ona 1 ni die, u koji spadaju temeljne atomanite formule (ti. one kod kojih je n = 0, a konsekvens ne sairži varijable), i intenziona 1 ni dio, koji iine formule kod kojih je n > 0. Skup svib dsducibilnìh temeljnih atomarnih formula (dakle n-torki, u relacijskoj terminologiji), koje su ili eksplicitno prisutne u ekstenziji baze ili pak deducibilne pomoću pravila (formula iz intenzije), zvati ćemo ukupnom ekstenzijom baze podataka. Teoretska zasnova relacijskog modela baze podataka u terminima logike, data je npr. u /Gallaire,7B/ i /Rei-ter,fl4/, a mogućnosti ekstenzije na deduktivni (logifiki) sistem razmatrane su u /Gallaire,53/, /Lloyd,83/ i /Ga 1 1 a ire , Si,/. Programski je:ik Prolog je za implementaciju deouktivne baze podataka posebno pogodan,jer =u instrukcije jezika Prolog zapravo definitne 'ciac:uVe, sa dodatkom kontrolnih funkcija '.r.pr. "'"), sistemskih funkcija ("read", .../, i "Negacije kao neuspijeha". Stoga su informacije u deduktivnoj bazi podataka (date u obliku definitnih klauzula), ujedno instrukcije jezika Prolog. Promatrajući deduktivnu bazu podataka kao teoriju (tj. kao konsistentan skup zatvorenih formula - rečenica), davanje odgovora na upit postavljen bazi, svodi se na njegovu logićku dedukciju iz informacija prisutnih u bazi. Prolog interpreter to Cini na taj način, da negiranu formulu (implicitnu tvrnju) iz upita doda postojećim formulama u bazi, i pokuSa (primjenom linearne rezolucije), dokazati da je teorija (tj. baza), tim dodavanjem postala nekonsistentna. Ukoliko u tome uspije, onda je implicitna tvrdnja iz upita (odnosno neka njena instanca), zaista deducibilna iz date baze podataka, te odgovor na upit (u kojem ne nastupaju varijable), glasi "DA", odnosno odgovor na upit (koji sadri i var ijable), su one instance varijabli iz upita za koje teorija postaje nekonsistentnem. (Relacijskim terminima rečeno, te bi instance bile zapravo upitom tražene vrijednosti atributa.) Temeljni problemi vezani za proložku implementaciju baze podataka razmatrani su u /Kowalski,79/, /Bowen,81/ i /Lloyd,B2/. Relacijski sistemi implementirani u Prologu dati su u /Pereira,62/ i /Li,84/. Pritom Li Prolog upotrebljava prije svega kao jezik za pisanje interfejsa, kojim se omogućava, da se na istom DBM sistemu koristi viäe različitih relacijskih jezika. Mogućnosti poboljSanja koopera-tivnosti (/Kaplan,82/), kod relacijskog jezika OBE date su u /Neves,83/, a analiza prološke implementacije uslova integriteta (integrity constraints) kod relacijskog modela data je j /Williams,83/. "Sistem za asimilaciju znan.ia (knowledge assimilation), kao osnova la e- kspertne sisteme odnosno baze znanja (knowledge bases) potpuno implementiran u Prologu,- dat je u /Miyachi,B4/, ali baza nije deduktivna u ovdje definiranom smislu jer ne sadrii pravila (formule), već ostaje relacijskom. Rad na razvoju sistema, koji sadrü i pravila opisan Je u /Kitakani,S4/, stime fito je u tom sistemu naglasak dat na razvoj mogućnosti induktivnog zaključivanja. U modelu koji ovdje razvijamo naglasak Je dat na kooperativnost sistema, pod Cima podrazumi-Jivamo sposobnost sistema, da sa korisnikom-kkmunicira u Jeziku za korisnika Cim prikladnijem, te da daje obrazloženja uspjeSnih (i neuspješnih) poku&aja dedukcije traiene informacije, kao i upozorenja korisniku o mogućim jonsekvencama pojedinih akcija u sistemu. 2rikazane su osnovne konture sistema, naglašeni neki specifiini problemi, koje uvođenje pravila u bazu podataka donosi, te ilustriran rad dosad implementiranih funkcija. 2. OPIS MODELA U ovom odjeljku dat Je.kratak opis modela i osnovnih (do sada implementiranih) instrukcija. ProloSka implementacija deduktivne baze pogodna je za razvoj Jezika sa Širokim mogućnostima postavljanja upita (i komuniciranja uopće /Radovan,aS/>. Primjena datih instrukcija ilustrirana je primjerima u odjeljku (3). novom. 1 ama. zahtjevu po sigurnim (safe) formu- Kod unosa, najprije se provjerava redun-dantnost nove informacije. Informaciju smatramo redunrantnom, ukoliko je u trenutku unoSenja već deducibilna (logiCki izvediva (slijedi)), iz baze podataka. U sistemu se to provjerava tako, da se u slućaju unofienja Činjenica (n-torki), iste 'pokufiaju najprije deducirati iz baze. U sluCaju unoSenja pravila (formula), pokufia se pokazati da ekstenzija antece-densa (deducibilna iz baze), nije veća od ekstenzije konsekvensa (deducibilne iz baze). Drugim riJeCima, pokuCavamo pokazati, da iz baze nije moguće deducirati takvu instancu antecedensa, za koju nebi istodobno bila (već) deducibilna i odgovarajuća instanca konsekvensa. Ukoliko u tome uspijemo, to onda znaCi da je informacija koja se unosi redundantna (tj. da ne puvećava ukupne ekstenzije!). Sistem na to upozorava, te se prema zahtjevu korisnika, informaciju unosi ili ne unosi u sistem. U slijedećem koraku provjerava se da li unoSenje nove informacije dovodi do krSe-nja uslova integriteta baze podatka. 0-graniCenJa, koja se uslovima integriteta baze postavljju, mogu se podijeliti na tri osnovne grupe: - ograničenje dopuStene . vrijednosti (tJ. domene), za pojedine atribute u shemi relacije, Osnovne instrukcije sistema Ifiledme.dat). Izlistava (doslovni) sadrZaj datoteke "I-me_dat'. Pravila pritom ostaju u izvornom obliku, a ukupna ekstenzija baze ne daje se eksplicitno. lext(Ime_dat>. Izlistava ukupnu ekstenziju datoteke "I-me.dat". Pravila iz intenzije baze bivaju pritom "prevedena" u pripadne ekstenzije, pomoću njih deducibilne. insert. •I (Informacija). Instrukcija "insert." je temeljna instrukcija sistema, te Ju podrobnije opisujemo. Informacija, koja se unosi, mo2e biti atomarna formula ("n-torka", odnosno temeljna instanca sheme relacije), ili pak pravila (zatvorena formula), tipa Consec i- Anti * Ant2 * ...* AntN. gdje su Anti, Ant2.....AntN literal i (tj. atomarne formule ili negirane atomarne formule), a Consec atomarna formula. Dakle, pravila, kao elementi baze podataka (i ujedno Prolog instrukcije (klauzule)). Cine Siru klasu formula od klase definitnih klauzula (definiranih u odjeljku (D), upravo dopuštanjem i negi-ranih atomarnih formula u pravilu. Pritom vati (meta)princip, da je cilj "not-(A)" zadovoljen (istinit), onda kada cilj "A" nije zadovoljen (istinit) u datoj bazi podataka. Primjena negacije ograni-ćena je na temeljne instance atoma (i formula, uopće), a to znaCi da u trenutku pozivanja cilja "not(A)", moraju (eventualne) varijable iz "A" biti već instanci-rane od strane cilju "not(A)" prethodećih ciljeva. Ovaj zahtjev izgleda (barem u operativnom smislu), ekvivalentnim Ullma- - strukturna ograniCenja, u koja spadaju funkcijske ovisnosti, - ograniCenja na naCine i pravo koristenja baze podataka. Od navedenih, u modelu je razmatrana samo problematika kontrole i oCuvanJa funkcijske ovisnosti. Ujedno Je pokazano koje sve probleme prisustvo pravila u bazi postavlja pred kontrolu integriteta baze. Uslovi integriteta predstavljeni su ovdje u "negativnom obliku", tj. ciljem, koji u bazi ne smije biti zadovoljen (deduci-bilan). Ukoliko bi pak unoSenJem nove informacije taj cilj postao zadovoljiv (deducibilan), onda se nova informacija ne prihvaća a korisnok obavještava. Prihvaćena informacija unosi se u bazu, a zatim se vrSi kontrola generirane redun-dantnosti. To se izvodi na taj naCin, da se svaku eksplicitno prisutnu informaciju iz baze redom (privremeno) odstrani, pa zatim istu pokuSa deducirati. Ukoliko pokuSaj dedukcije uspije, daje se obavijest o (stvorenoj) redundantnosti, i informacija zatim briSe ili zadrjava, prema zahtjevu korisnika. Kontrolom generirane redundantnosti, proces unosa (prihvaćene i (u odnosu na IO, valjane), informacije zavrSava. Navodimo slijedeće (potencijalne) razloge za zadržavanje redundantnih informacija u sistemu : eksplicitno prisustvo Činjenice ubrzati proces dedukcije, moZe néke informacije, koje su u datom trenutku redundantne, mogu kasnijim ažuriranjima (bilo unosom bilo brisanjem drugih informacija), to prestati biti, te bi njihovo obavezno iskljuCvanje (ili nedopuStanJe unosa), nepotrebno oteiavàlo posao aluriranja baze, - dopuštanje prisutnosti redundance može znatno olakSati rad u fazi razvijanja baze znanja i to upravo iz rzloga ^navedenih u gornjoj točci. Valja međutim napomenuti, da prisustvo redundantnih informacija u bazi postavlja dodatne teSkoće Cili bar zahtjeve) pred valjanu implementaciju funkcija agregaci-je, pout "suma", "prosjek" i sličnih. delete. (Informacija). Naredbom "delete" briSemo informaciju da-tu kao argument naredbe. Informacija moie biti činjenica ili pravilo; ukoliko se informacija ne nalazi u bazi podataka, ne poduzima se niSta, a korisnik o tome obavještava. eKpI . •! (Cilj). Ovom instrukcijom tražimo od sistema odgovor, da li Je (potencijalno slolen) cilj "Cilj" deducibilan iz sistema, té ako jeste, traiimo objašnjenja, koji su (sve) mogući "putovi" njegova deducira-» nja. Program, kojim je navedena instrukcija implementirana, navodima u cjelini, jer nam dato programsko rjeSenje izgleda jednostavnijim od programa za analogne instrukcije (predikate), kao Sto su "denio " i "deduce" (vidi npr. /Kowalski,79/, /Bowen,81/, /Kitakami,8«/, /Miyachi,84/). /• izvođenje i obrazlaganje dedukcije •/ expl :- read(X), decomp(X,A), prove(A,L), ni, 5how(L), ni, writeCAnother explanation ?(y./n.)'), read(Ans), ni, nBxt_one(AnB). expl ;- writeCNo (more) deduction(s) ' ) ,nl, !. prove((A,e),L) prove(A, LI), prove(B, L2), append(Ll,L2,L). prove((AjB),L) s- prove(A,L); prove(B,L). prove(not((A)), _) prove((A) , _),! , fail. prove(not(A),Cnot(A)3). prove(A,CA from BIC3) :- clause(A,B), prove(B,C). prove(A, Eis_true(A)3) :- functor(A, F, N), not(member(F,C',', not,'j',true])), prolog_system_predicate(F, N) , calKA), prove(true,C3). Slijedeće tri instrukcije omogućavaju nam da prije insertiranja neke informacije u sistem (tj. u bazu),provjerimo neka njezina svojstva i (buduće) učinke na bazu podataka. check. (Antec implies Consec). Upitom toga tipa tražimo od sistema da provjeri, vrijedi li (već) u bazi podataka promatrano pravilo tipa "Antecedens implicira Konsekvens". Ukoliko ne vrijedi, sisten navodi one instance antecedensa deducibilne iz baze, za - koje iz baze nisu deducibilne odgovarajuće instance konsekvensa. extinf. * : (Informacija) . Ovom i-nstrukoijom tražimo "ekstenziju informacije", tj. koje su sve instance sheme relacije deducibilne iz antecedens« razmatranog pravila. Uloliko je riječ o činjenici, onda Je njena ekstenzija samo ona sama. newext. ♦j (Informacija). Instrukcija slična gornjoj, stime da se njome provjerava koje su instance deducibilne samo iz ''Inf ormaci Je" (pravila), koje razmatramo, a bez primjene tog pravila ne bi uopće bile deducibilne. Drugim riječima tražimo koliko "proSirenJe" ukupne ekstenzije donosi primjena toga pravila. Ukoliko se radi o činjenici (a ne pravilu), onda Je "newext" činjenice Jednaka njoj samoj, ako ista nije već deducibilna iz baze, odnosno praznom skupu, ako jeste deducibilna. ali. •« ((N-torke) suoh_that Uvjeti). Ovaj tip upita analogan je upitima (SE-LECT-FROM-UHERE) iz relacijskog jezika SOL. Odgovor na upit je lista svih N-torki, koje zadovoljavaju Uvjete. Pritom u Uvjetima mogu nastupati logički operatori kao i funkcije agregacije. Činjenica, da Je neka iformacija (instanca sheme u bazi), ponekad deducibilna na dva ili vifie načina (Sto možemo provjeriti pomoću naredbe "expl."), jeste razlogom da uobičajene proloSke funkcije "bag.of" i "set_of" nisu direktno upotrebljive za ' implementaciju fukcija (instrukcija) tipa "ali.", kojima zahtjevamo od sistema sve one "n-torke", za koje su ispunjeni uslo-vi iz upita. "Bag_of" funkcija bila bi neprikladna jer bi svaku informaciju (element ukupne extenzije baze), uzela u obzir (prilikom sumiranja i slično), onoliko puta na koliko Je načina ta informacija deducibilna u sistemu! -'Sto, naravno, u slučajevima' gdje postoji redundanca u sistemu, ne bi davalo ispravne rezultate. S druge strane, primjena funkcije .tipa "set_of", kojom se viSestruko dedu-, cibilna informacij tretira samo Jedanput, ne bi radila u slučaju kada Je potrebno izvrSiti npr. zbrajanje vrijednosti nekog atributa na skupu n_torki iz datoteke. Naime, u tom slučaju, svaka različita vrijednost atributa bila bi uzeta u obzir samo jednom, Sto, naravno, nije ispravno Jer više različitih n-torki (instanci) može imati jednaku vrijednost promatranog atributa, a pribrojiti treba ipak sve (tJ. svaku!). Taj smo problem ovdje rijeSili modifikacijom funkcije "set_of" - konkretno, procedurom "ali _u(T,G,L)", koja ujedno čini osnov za implementaciju svih funkcija tipa "SE-LECT-FROM-WHERE". SuStina modifikacije astoji se u tome, da' se u klasičnoj "trojci" (N_torka, Cilj, Lista), Listu formira tako, da se najprije generiraju Jedinstveni (tj. bez ponavljanja!), parovi (N_torka, Cilj), a zatim sve N_torke iz parova (među kojima može biti i viSe jednakih N_torki!), "pokupe" u Listu. Taj postupak (program slijedi), uspješno riješava oba gore navedena problema u vezi sa dupliciranjem. /♦ instr. "ali" i podr. fun. »/ all ;- read(X such_that Cond), decomp(Cond,Dcond), all_u(X,Decond,L) , sho_w(L) , all_u(T,G,_) !- f ind_tuples_u(T,'G) . 72 all.u(T,G,L) !- collect_them_u(C3,L),!. f inil_tuples_u(T,S) asserti(found(mark,mark)), call(6), a5s(T,G), fail. as«(T,6) found(T,G),!. a«« —> Z. Temeljne atomarne formule oblika predikat(argl, ..., argN). nazivamo fiinjenicaraa (facts), i njihovo prisustvo u u bazi znafi istinitost navedene instance sheme datoteke (relacije). Pravilo iz datoteke "pp" pp(X,Y,Z) qq(X,Y,Z), not(rr(X,Y)). kazuje, . da je u bazi (toSnije: datoteci "pp"),istinita svaka instanca sheme pp(X,Y,Z), za koju je istinita pripadna instanca sheme qq(X,Y,Z) datoteke "qq", a pritom nije istinita pripadna instanca sheme rr(X,Y) datoteke "rr" . Primjeri Doslovni sadržaj datoteke "iz 1istavamo" pomoću instrukcije "Hiledme.datoteke) ?- Uile(pp). pp(a, d, 4) :- true pp(a, c, 4) !- true pp(b, c, 3) :- true pp(_l. _2, _3) !- qq(_l. _2, _3) , not(rr(_l, _2)) yes 7- Ifile(qq). qq(a, b, 6) true qq(c, d, 8) true. qq(u, V, 8) :- true qq(u, B, 5) ;- true qq(a, d, 4) :- true yes ?- Ifile(rr). rr(b, a) true rr(o, d) !- true rr(a, d) i- true yes Uno» informacije vržimo naredbom "insert." Pokuäajmo unijeti informaciju "pp(u,v,8)". ?- insert. •I pp(u,v,8). Information is redundant Insert it ? (y./n.) * : n. yes Sistem nas obavještava da je ta informacija redundantna, tj. već deducibilna iz baze, ta tra2i odgovor da li da ju prihvati ili ne. U ovan slučaju informaciju nismo prihvatili (od-govorivSi "n."). Ukoliko želimo provjeriti je li informacija (u ovom slufiaju:' činjenica), koju smo željeli unijeti, zaista redundantna, izlistamo ukupnu ekstenziju odgovarajuće datoteke (tj. relacije). To činimo instrukcijom "lext(Ime_datoteke)". lext(pp). pp(a, d, 4) pp(a, o, 4) pp(b, c, 3) pp(a, b, 6) pp(u, V, 8) pp(u, e, 5) yes Iz date ukupne ekstenzije datoteke "pp" očito je da je spomenuta informacija (kao ulazna), zaista redundantna jer je iz datoteke "pp" već deducibilna, na što ukazuje njeno prisustvo u ukupnoj ekstenziji datoteke "pp". No, obzirom da ista nije prisutna u (eksplicitno- datoj) ekstenziji datoteke "pp", slijedi da mora biti deducibilna pomoću intenzionalnog dijela datoteke "pp", tj. primjenom pravila. Objašnjenja o (svim mogućim) načinima njenog deduciranja možemo zatražiti pomoću instrukcije "expl.". ?- expl. * : pp(u,v,8). pp(u, V, 8) follows from qq(u, v, 8) and not(rr(u, v)) qq(u, v, 8) is a fact in DB it is true that; NOT rr(u, v) Another explanation ? (y./n.) y. No (more) deduction(s) yes Dobivena obrazloženja Čitamo na slijedeći na-Cln: Da je "ppCu,v,8>" deducibitno (a tine i "istinito u bazi"), slijedi iz toga Sto je deducibilno "qq(u,v,8)" i "not(rr(u,v))". "qq(u,v,8)" je deducibilno jer je to (eksplicitno prisutna) činjenica u bazi. "not(rr-(u,v))"' slijedi iz toga Sto rr(u,v) nije deducibilno iz baze - a općenito vaii tneta) princip, da je "notCTvrdnja)" deducibilno (a saain tine i istinito), onda kada "Tvrdnja" nije. Pokutajno unijeti "pp". ?- valid(pp). File ««pp»* violates IC, because pp(u, v, 8) and pp(u, v, 9> and 9 \ are deducible from DB yes i== 8 Dakle, ažuriranjem jedne datoteke, možemo narušiti integritet druge. Jer, čak da su i bili dati uvjeti integriteta za datoteku "qq", ti ne bi morali zahtjevati upravo ona ograničenja, koja bi garantirala očuvanje integriteta u datoteci "pp". Očito, na posredno kräe-nje integriteta presudno utječe postojanje pravila (intenzije) u bazi podataka. Zatražimo stoga, najprije obrazloženje odakle slijede "inkriminirane" informacije. . ?- expl. *: pp(u,v,S> and pp(u,v,9). pp(u, v, 8) follows from qq(u, v, 8) and not(rr(u, v)) qq(u, v, 8) is a fact in DB it is true that; NOT rr(u, v) pp(u, v, 9 follows from qq(u, v, 9) and not(rr(u, v)) qq(u, V, 9) is a fact in DB it is true that: NOT rr(u, v) Another explanation ? (y./n.) •! y. No (more) deductionCs) yes Očito dedukcija nedopustivih . informacija u datoteci "pp" ide preko informacija "qq(u,v,8) " i "qq(u,v,9)" - koje u samoj datoteci "qq" na smetajil - i nededucibi1nosti informacije "rr(u,v)"! Stoga i postoji viSe načina da se .datoteka "pp" vrati u valjana stanje. Najzanimljivijim izgleda slijedeći: ?- insert. »I rr(u,v). Infornation inserted ye« ■ I ?- valid(pp). File pp is in accordance with'IC yes Dakle, insertiranjem neke informacije u datoteku možemo "povratiti integritet" nekoj drugoj datoteci. No, isto tako i brisanjem informacije, kako to slijedeći primjer pokazuje, integritet naruSiti. 7- delete. ■»; rr(u,v). Infformationd deleted yes ?- val id(pp). File ««pp»« violate IC, because pp(u, V, 8) and pp(u, v, 9) and 9 \== 8 are deducible from DB yes IzbriSimo konačno "pravog uzročnika" krSenja integriteta datoteke "pp". ?- delete. «! qq(u,v,9). Infformationd deleted yes ?- valid(pp). File pp is in accordance with IC yes Naravno, takvo nepouzdano djelovanje sistema nije prihvatljivo. Utoliko smo navedenim pri-njerima željeli prvestveno ukazati na neke od "popratnih efekata" uvođenja pravila u bazu, koji zaslužuju posebnu pažnju. Napomenimo samo, da bi jednostavno ali i najneefikasnije riješenje problema moglo bit, da se prilikom svakog (pojedinačnog!) ažuriranja, bilo koje datoteke u bazi provjerava integritet svake pojedine datoteke u bazi.: Slijedeća instrukcija nam omogućava da prije pokuSaja insertiranja nekog novog pravila (tj. zakona ili pak "znanja"), provjeri».^ CneKe) od njegovih efekata na bazu podataka. ?- check. •: qq(X,Y,Z) implies pp(X,Y,Z;. The rule does not hold because : qq(_l, _2, 3' is true but PP(_li _2, _3) is NOT true for the following instances: qq(o, d, 8) yes Dakle, promatrano pravilo (implikacija) u bazi ne važi (ili, u terminima teorije modela rečeno, ukupna ekstenzija baze (shvaćena kao struktura), nije model promatrane implikativne ti prećutno univerzalno zatvorene!) formule. To pak ujedno znači, da će njeno insertiranje u bazu (promatranu sada kao teoriju), povećati ukupnu ekstenziju baze (točnije; konsekven-sa!), za instancu, koja odgovara navedenoj instanci antecedensa (tj. za "pp(c,d,8)"). Jednostavnije rečencloo, instrukcija "check." p kazala nam je da je iz baze deducibilna informacija "qq(c,d,6)", a da istqdobno nije deducibilna informacija "pp(c,d,8)"w To pak ujedno-znači, da ako promatrano pravilo u bazu 66 mo a umjesto r.Lnvljnmo dJJ . Iz tako dobivene relacije možemo odrediti momente t.j. očekivani broj događaja u repu 2. Promotrimo sada prioritetnu grupu događaja u codelu na slici 3a. Ciklus obrade sastoji se iz vremenskih razmaka + jj-^. Prema tome relacija analogna (5.5) glasi: Ciklus praznog hoda nešto je kompliciraniji.. Ako je rep 1 prazan vremenski razmak sastoji se iz nezavisnih vremenskih sekvenci , Xj s vjerojatnošću (1 - gjo'- ^ vjerojatnošću g2Q, te tome: (5.6) Usporedbom modela 3a i 3b opažamo da u relaciji (5.3) umjesto rJsj stavljamo umjesto stavljamo Y*,,, a umjesto rJ stavljamo B* . Iz dobivenog izraza, koristeći moment ge-nerrirajuće svojstvo izračunamo očekivanje broja događaja u prioritetnom repu 1. Vjerojatnost gjQ (prazan rep 2) izračunamo iz (.5.^) tako da umjesto £(«.+ ,'3^) stavimo očekivanje perioda zauzetosti Eiy^^^ dobivenog moment generirajućim postupkom iz ® umjesto E( stavimo očekivanje ^(y^^) dobiveno iz Intenzitet > = Xj- Prema /5/, transformacija razdiobe vjerojatnosti broja događaja Q(z) i Laplaceova transformacija gustoće razdiobe vjerojatnosti vremena u M/G/1 sustavu W* (s), vezani su jednostavno Q(z):W* (X-Xz), "s "ä te su time relacijom (5.3) određeni i vremenski parametri sustava. 6. NEPRODUKTIVNA OBRADA U PRIORITETNIM SUSTAVIMA M/G/1/PRI S PREKIDANJEM Razmotrit će se model računarskog sustava s k-grupa izvora slučajnih događaja uz mogućnost prekida obrade i nastavka u točki prekida. Unutar pojedine prioritetne grupe sustav odabire dogadaje u obradu prema redoslijedu dolaska (FCFS). Prema slici ta, u času t^ događaj dj dolazi u sustav i priključuje se repu čekanja. U času t.| događaj dj prvi puta ulazi u obradu. Vrijeme čekanja u repu iznosi w . I t, - t . Prije svakog početka obra-qj 1 o de, potrebno je kompletno pripremno-neproduktivno vrijeme, koje za događaj đ^ iznosi o^j" Iza kompletnog pripremnog neproduktivnog vremena o .,, slijedi obrada (dio od x.), pa mo-c j 1 j gući prekid,. tokom kojeg je obrada blokirana kroz vremenski razmak zatim opet kom- pletno pripremno neproduktivno vrijeme o^jj, te se tako ciklus ponavlja do trenutka t^ kad 1' ''i završetak OBRADE ptrkidi ^ obrado t_ "i/ pript»mo r»;,, .Oj, V '•1 1 prekidi »«gm«f\t4 priprem« 1 komple]r>o pripremno Slika 14. M/G/1/PRI0RIT. sustav s prekidanjem događaj konačno napušta obradu. Kompletno pripremno neproduktivno vrijeme sastoji se prema slici '4b, od segmenta izgubljenog neproduktivnog vremena o ., segmenta blokiranog vre-w j mena w^^j .i konačno segmenta uspješnog pripremnog vremena Oj, budući da pretpostavljamo mogućnost prekida i tokom neproduktivnog vremena pripreme obrade. Slučajna veličina o^ data je za pojedinu grupu izvora slučajnih događaja razdiobom Vj(o), gustoćom razdiobe Vj(o) i pridruženom transformacijom V*j(s). Slučajni vremenski razmak od trenutka prvog ulaska događaja dj u obradu do trenutka potpunog završetka obrade (rezidentna vrijeme) = tj - t.| zauzima ključnu ulogu u analizi prioritetnih sustava s prekidanjem događaja u obradi. U sustavima bez prekidauja, evidentno je "rj = '^j- Opisani model sustava s neproduktivnom programskom podrškom može se dekomponirati na prekidne sustave bez neproduktivne programske podrške s nastavkom obrade u točki prekida (M/G/1/PRI-PRN) te na sustave s nastavkom obrade s početnim vremenom obrade (M/G/1/PRI-PRP). Za sustav bez neproduktivne obrade i nastavkom obrade u točki prekida, rezidentno vrijeme dogadaja dj sastoji se iz segmenta obrade te vremena blokade j > odnosno iz totalnog vremena obrade (Xj) i segmenata vremena blokade "jjj • U sustavu s nastavkom u točki prekida, ukupno vrijeme obrade jednako je zahtjevanom vremenu obrade j-te grupe, tj. Xgj = Xj, pa su transformacije pridruženih gustoća razdioba identične. U sustavu bez neproduktivne obrade i nastavkom obrade u točki prekida s identičnim, početnim, vremenom obrade izabranim iz B.(x), •j ukupno vrijeme obrade sadrz; nekoliko izgubljenih (prekinutih) segmenata cbrade i jedno uspješno vrijeme obrade Xj. Rezidentno vrijeme u takvon sustavu sastoji se iz N zavisnih' parova + Xj^j i jednog vremenskog razmaka uspješ- • ne obrade Xj. U literaturi /6/ nalazimo transformaciju 'gustoće razdiobe rezidentnog vremena ■J Budući da u ovom slučaju ukupno vrijeme obrade x^j nije jednako zahtjevanom vremenu obrade Xj, to se transformacija pridružena veličini dobije iz Y* (s) uz supstituciju SJ ' ' (s) : 1; tj. izostavljanjem segmenata vre-^ J w mena blokiranja: Y (s) je transformacija gus-b j toće razdiobe vremena blokiranja. U literaturi /7/ također nalazimo Lapla- ceovu transformaciju razdiobe vremena u prekid- nim .sustavima w'' (s) izraženu preko rezident-'^s i no^, vremenaT i vremena blokiranja. Bazumljivo je da relacija za W* (s) vrijedi za sve prekidne sustave (PRN, P^P) jer se razlučivanje odvija baš u rezidentnom vremenu odnosno pridruženoj transformaciji (s). Iz tih izraza koristeći svojstvo generiranja momenata izvedeno je očekivanje vremena u repu čekanja grupe j: (6.1) Relacija (6.1) daje nam najvažnije parametre u sustavu, ali izražene preko slučajnih veličina i Xg Je intenzitet prekidanja t.j. Xg = x^ * * ■■■ * Xj-1- u trenutku prekida (početak segmenta w^^j) obrade dpgadaja dj, u sustavu se nalazi samo jedan dogadaj višeg prioriteta (s indeksom r (B M H- < tO a Cl. Đ> o X" 01 ■d ►1 •d t-« •-n •d O •d H- ►t d Cj. •d •d N Cj. ct c: o ct H» ta m O ►1 p n P < rt •1 ►1 P rt p H- H- H- O- o N H o ct o P- ct CJ. ct o O 01 pr rt O « p o B cr P cr ►1 H- A P cr a" •1 ct P rt p O) rt CJ- 01 M t-* C ct »-< M rt rt O 01 O 01 rt » p. n (n H. P H- n rt •d p- rt f- •d C D B < B o P B B ►1 i-r ta P- P ct O 01 O E P S O B ct P rt p ct o. rt o p rt rt (n • P- H- rt 01 N 1 p- p- p. o N o B •d M •d tO m P < rt p o« N m rt Cj. 01 c< "i » 1 N< M ►J m O P C •d 03 ej. P H- p H- rt H- o P H- H- ct p- Ct ct < rt •d ct ct 01 p< t-" P- cr «S B ct o H- P rt 01 o h"- ►1 H- Cj. H- ct p p 1» M P O rt Cj. O ►1 « Cj. 01 o- o ►1 rt n< n p M P rt ct ct H- P P- p- rt P 0> o" 1» B P H- B H- P P P Cj. ta p* O N M B 1 rt o •d P • P • 01 P P «s rt- t O m C 01 « rt «!■ O u I" ct B N •d H- ta 01 O M P- p- h-' to 01 p < ►1 t-* C p. 1 a" •C P «S P Cj. •d P P o H- H- p Cj. •d O rt C p. • P> P ►1 p X( N <5 CJ. ►1 N rt «s ct •d Cj. H- O o Cj. O P m H- rt o r—, 01< C rt H- rt M p ►1 P- cr P s O P p> .t Cj. P <: M hI O- o B O H» o n ■d n l—l rt «i CJ. o P o O 4 P cr rt o> »i F: hi C • « P rt P Cj. •d »i B P B rt C rt D r—1 cr P ct Cj. O. H- o P P P- rt P M •d t-" f—i tu ■O p CJ. P rt rt p- w CJ. • P w o P> P t—> N C • « Cj. p. p rt ►i O X rt H- N N p- P< rt p. o rt ■ rt CJ p- o M O H- »—1 H H- e O fs- o cr rt o M rt p ►1 O p B o p »-• o- ►1 M p p. P rt P p O. P i—J p •d H- fr P K o o Cj. o P P- B ct H" rt ( P • M 01 B o If H- o ►1 rt p- P p- O H- P 01< « p H- p •d O 9 e 0» O fj rt U> ) O. o p K' 11 t-' •d 0) rt rt P •d cr rt m ■<: 01 O P p H- Pf ta IV • P rt p p N 01 C K O X < O S" p Cj. o N 01 01 p • p m o H- 01 P o p •d o rt 01< cr P ct C < o. s H- P O p O m ct •d p rt >-' SI H- C C O P H- M o C •O B n •d P H, 01 o ■d rt O •d O ct O B P (R < rt S o p. C P H* o cr ►1 •d m o P p H* < P- O p. 1» p O B < p H- ct N O H* 1 m p •7 1 1 o B m rt 1 P 1 (N o 1 1 p a X Ole O ct < C nj N •d B M P- 01< p B B P- p a ^ rt rt rt p- • O •i rt p P ct p- O rt N I-" K! B , 4 01 O l-J o P o P* o 01 ct < D p m P H- H- a < N M P o D p- Cj. ct P Cj. o a P M o o P S O rt ct o rt Cj. rt 01 rt <=: P P- P- ta Cj. < •d p- p- P p B rt B p. P 01 o N • P O li rt P- i-j CJ. P p- P 01 p P p. a & P- P p- 01 P p- 01 li p- •d P- ct O n < M a rt P X P rt m rt •d B rt H- N 01 ■P o N IS- O p o N o" rt ■d rt B ti P- ta p o tn o B P- o p ct o P p- ta C a P p p- p- ct p- o t-J N •d K B • p» a Cj. o N •d S B & o. p- o •d IV P P O p o p p. rt U1 o rt ■d p p- • p H P O 01 N N< SS N 01 ct O B t-" p p- p- N p- •d ct P rt .P C p» Mi j, cr p p- p p P P- Cj. o p P P- p w P i>r < •d o < 01 a < O p. B a- (71 p- ct o. p >1 o p. P p o rt p O ^ H rt o rt a o 13 P O ct O. e X- N X) < p p. p. M p- o- p O. OT p p p P- li O cr aj o P B M « P B tD M ct >1 rt li P p O O rt « B P o rt P O P P- P' ct p. p- B P- rt ft rt n« 3 M a 1 p H-" o •d S ct P •d O P- P O O O 1 -J •d P o N ffl O O P o p- o B N« ■t • C Cj. P B o. P/ N Cj. 01 rt C-i. K a * o P O rt P B p P- O ct P B O It cr 01< B Pl • P' p >i P P- m« N w rt C C M ■< < p- r> O P (9 B P rt O O p • 01 "i B p. < > a P P i>r rt P p rt p O rt » rt 1-' P o vn a- ct o. O rt < P ct S - ?r p. p P »-I rt < o< p- O o X O • rt P o o N H» vD O p- p" rt P< • p- p p- Cj. ct m p •d u O o p li P ^ rt p ct Cj. i-i p > o p p p P o oc p p> P rt C a B p. p- p p Cj. ct »i p' ta< o p o p p« rt P O rt p- p »i p> ,V o p p •d Cj. p B B o O o p. p K rt P p- rt rt IS- rt P I n H- o P P 01 p" p rt P» B •d O 1 N rt n • O p P p» 1 P sr 1 P 1 rt 1 rt 1 a P< « O m M 1 rt 1 C < o E>< c+ O tr (t o H, H H- <11 II B CO •tì 3 < H- M g O. M n O 0 o »t H- tr (I) HO) 01 « g ^ » •d « < o o o K- p ►1 t"» « O tn D a o •C •D M O O H» •o s o o pp ►1 ffl 0) £ tJ-Ho tr p n m P- (S < ra M o "O 'J a< Ha B iD O cr 0 P Ho 01 o (a < n o •d B 4 n o rt- "0 cr o o D) Pb IV p, H- n |B o- B (S (D P g. <0 O o u 0) H- o< (D g rl-HO El O CD rt HO P O >1 rt tr (D B •O ct O O •Ö » ct HO P (-1 (B ►1 >1 a •O tn 4 O >1 H- O cr O rt a ►1 a m Oa o 0 P 01 ct 0) HP ct CO ct p» ct ct pA 01 PP- m g> p ct p) ^ S ct ta p- e p- ta n> M co ct ct p- n o M ct <«J P (t a P ^^ ct (S H- ca ct I-» p- Vi a ct o o o to B ct O ►J p, O a H- !-• ä 0) o » ct prt <0 H 0 ct HO g B M ct O O p. Kj p ^^ ct a ta o o- H H- C cc p u o rt O* HS H, m o M B c: p. rt M tJ |D rt 0) p (B p, p. ct (S tr ct rt D •d p, (U rt ^i •d ct rt P O P. H, rt P ct O tr p 01 rt 01 0 p- <0 g 01 Hen ct prt 01 ■d C3 H ct •d y o. P e-i rt P- ►1 o rt < rt p- O ta rt Cj. p. P ■d cr ct P ■■ rt P P o M p- s ct p p- t) rt • P o< o B < o fT o» p o O IV p. o p p. P O oq N P,- Cj. ■ < p> p "d O p p- o P o f< o •i p> P ta B P w B ci rt O p- P P P P- cr 1 er N 1- pf B p P P- P O •d o •d < p- p" N n P t-" O p- P o P o ■p pr p- p. cr Cj. m p o p O p" P p- M o rt < rt pr P p- rt o 0 rt rt rt o »1 M p rt p rt Cj. O •d N p- 01 P P ►1 •i P P < rt 4 < >d P ct o P- ■i ta rt rt m 0) o P P- o P cr n P p" P H p- rt 01 rt < n CJ. P- ct B Cj. p" P- p p. « rt P • rt o •d p- C P- p- ►i 3 o o •d rt o P ,p CJ. ct < P n P- O O t» IV B P B < m< ct CJ. P rt p- rt Cj. 1 P B H P rt P P- P P P- P- P O- P N p. CLl. •d P P P B N < o P- "d P- cr o H li 01 p- rt rt P rt P n P" P- P p. O B 3 P pj 01 o O f=f i Cf^ -<-1. Ovdje, Cif^ f znači da nije CM-f, a ^f znači da nije f. U slučaju nezavisnosti, f treba dodati skupu C. Ako C>=» f, onda je nekorisno da dodajemo f u C jer bismo dobili redundantan skup C U {f J tj. vrijedilo bi K(C)=M(CU U li )• Ako C»='vr, onda je CU{f] kontradiktoran skup uvjeta, pa je operacija dodavanja zabranjena. U teoriji funkcionalnih zavisnosti su razvijeni formalni sistemi gdje je jedan od glavnih zadataka pokazati točnost i kompletnost formalnog sistema. Dokaz točnosti formalnog sistema vodi na implikacioni problem. Cijela sek-j cija bit će posvećena ispitivanju točnosti formalnog sistema predloženog u [9]. 3. Reprezentacija funkcionalne zavisnosti, pomoću Skolemove standardne formule Neka je .. .A^^) relaciona šema, r primjer od R i . Rekli smo da funkcionalna zavisnost X—vrijedi u r ako i samo ako l/t^.tgcr (t^[X] =t2CX]=^t^[Y]=t2Ly]). Ako uvedemo predikat gdje intendirano značenje: tiplovi tj^ i tg su jedna ki na skupu atributa X tj. t^ [X] »tg^X], funkcionalnoj zavisnosti možemo dati oblik: (1) X-^y:,VtiVt2[E3^(t^,t2)=9E^Ctj^,t2)] . Prema tome, formulu (1) interpretiramo na skupu tiplova (relaciji) r. Ponovimo, da je inter pretacija r model za (1) ako (1) vrijedi u r, te da (1) vrijedi u R ako je svaki primjer od R model od (1) Primjer 1. Keka je zadana relaciona šema R(A,3,C), koja je u danom trenutku vreciena predstavljena relacijom r : ABC a 1 0 2 b 1 o o C 1 o 1 U tabeli, a,b,C su oznake za tiplove relacije r. Lako uočavamo da je r model za A—dok nije model za fAiBj^C. Da r 'nije model za {A,BWC slijedi iz činjenice da je E,. -Ca.b) _ r , » 1A > C) 1 ~Ejcj(a,b). U skladu sa uobičajenom notacijom u teoriji baza podataka, jednočlan skup {Aj pisat čemo kao A , a uniju XUI skupova X i Y atributa kao XY. Napišimo sada Skolenovu standardnu formu za X —Iz (1) lako dibijemo da je tražena forma kspertne sisteme odnosna baze 2nanja (knowledge bases) potpuno implementiran u Prologu, dat je u /niyachi,B4/, ali baza nije deduktivna u ovdje definiranom smislu jer ne sadrü pravila (formule), već ostaje relacijskom. Rad na razvoju sistema, koji sadrü i pravila opisan je u /Kitakami,84/, stime Sto je u tom sistemu naglasak dat na razvoj mogućnosti induktivnog zaključivanja. U modelu- koji ovdje razvijamo naglasak je dat na kooperativnost sistema, pod čime podrazumi-jžvamo sposobnost sistema, da sa korisnikom kkmunicira u jeziku za korisnika Cim prikladnijem, te da daje obrazloženja uspješnih (i neuspješnih) pokuSaja dedukcije tražene informacije, kao i upozorenja korisniku o mogućim jonsekvencama pojedinih akcija u sistemu. Zrikazane su osnovne konture sistema, naglaSe-ni neki specifi$ni problemi, kaje uvaInf ormaci je" (pravila), koje razmatramo, a bez primjene tog pravila ne bi uopće bile deducibilne. Drugim rijeCina tratino koliko "proSirenje" ukupne ekstenzije donosi primjena toga pravila. Ukoliko se radi o činjenici (a ne pravilu), onda je "newext" činjenice jednaka njoj samoj, ako ista nije već deducibilna iz baze, odnosno praznom sku-' pu, ako jeste deducibilna. ali. •I ((N-torke) such.that Uvjeti). Ovaj tip upita analogan je upitima (SE-LECT-FROM-UHERE) iz relacijskog jezika SOL. Odgovor na upit je lista svih N-torki, koje zadovoljavaju Uvjete. Pritom u Uvjetima mogu nastupati logički operatori kao i funkcije agregacije. Činjenica, da je neka iformacija (instanca sheme u bazi), ponekad deducibilna na dva ili više načina (5to moiemo provjeriti pomoću naredbe "expl.">, jeste razlogom da uobičajene proloSke funkcije "bag_of" i "set_of" nisu direktno upotrebljive za ' implementaciju fukcija (instrukcija) tipa "ali.", kojima zahtjevamo od sistema sve one "n-torke", za koje su ispunjeni uslo-vi iz upita. "Bag_of" funkcija bila bi neprikladna jer bi svaku informaciju (a-, lement ukupne extenzije baze), uzela u obzir (prilikom sumiranja i slično), onoliko puta na koliko je načina ta informacija deducibilna u sistemu! -žto, naravno, u slučajevima'gdje postoji redundanca u sistemu, ne bi davalo ispravne rezulta-. te. S druge strane, primjena funkcije tipa "set_of", kojom sé viSestruko deducibilna informacij tretira samo jedanput, ne bi radila u slučaju kada Je potrebno izvršiti npr. zbrajanje vrijednosti nekog atributa na skupu n_torki iz datoteke. Naime, u tom slučaju^ svaka različita vrijednost atributa bila bi 'uzeta u obzir samo jednom, Sto, naravno, nije ispravno jer više različitih n-torki (instanci) mo2e imati jednaku vrijednost promatranog atributa, a pribrojiti treba ipak sve (tj. svaku!). Taj smo problem ovdje rijeSili modifikacijom funkcije "set_of" - konkretno, procedurom "ali _u(T,G,L)", koja ujedno čini osnov za implementaciju svih funkcija tipa "SE-LECT.-FROM-HHERE". Suština modifikacije astoji se u tone, da se u klasičnoj "trojci" (N.torka, Cilj, Lista), Listu formira tako, da se najprije generiraju jedinstveni (tj. bez ponavljanja!), parovi ?voted to exp'.ri;. ices with te--žching youngest pupils and adults thus evaluitii-.g -full spectrum oi learning character istics. 1. Uvod - zgodovina razvoja Idejna zasnova logike kot programskega jezika se pojavlja Sf? okrog leta 1V70 /1,2/, vendar pot od ideje clo realizacije ni bila enostavna in premočrtna. nb prvih implementacijah pa se je pojavilo prvo veliko razpotje. Ena prvih implemcäntaci j je bil PLANNER ko ga dobimo na raznih operacijskih siste.t.ih, recimo CPM/SO, CPM/Bó ali MED03/PCDG5 /Z,', Mnd avtorji mikroprologa omenimo predvsem i.^owal skega, Ennalsa in McCaba /3,4,5/. Posebej za.-iimiv je Robert Kowalski, saj je poloSil tt?frii?lje logičnega pr ogr ami r an j a /1,2/. F.G.McCabs ja pravzaprav glavni implementator mikroprologa, J.R. Ennals pa se je ukvarjal predvsem z uporabo mikroprologa v pedagoške namene, v okviru projekta "Logic as a Computer Language for Children". VeČina dela je potekala na imperial College v Veliki Britaniji od leta 1930 dalje. Prolog kot implementacij a logiCnega programiranja je osnova japonske 5. generacije računalnikov in polsg Japonske doSivlja velik vzpon predvsem v Evropi. Prolog je precej raz Sirj en zlasti v Slovi?niji in tudi d'-uaod v Jugoslaviji. Velil:o zaslug pri nvsjpnju jezika gre na raCun I. trati.a. /6,7/. prolog te nekaj let redni uCni [.»«-edpTiet n- t atc-d'^i r? ra^iu^alni — Stvo.in informatika Fakultete za elektrotehniko Ljubljana, veČino prevajalnikov za prolog pa smo nakupili ali dobili preko Instituta Jo2ef Stefan, kjer dokonCujemo prevajalnik za prolog v pascalu. 2. Nekaj enostavnih primerov V nasprotju s klasiCnim programiranjem, ki zahteva "strog" in dobro premiSljen pristop ter toCno doloCen potek izvajanja /8/, omogoCa mikroprolog programi ranj e vzorCno vodenih sistemov (pattern-directed systems). Taki sistemi temeljijo na samostojnih kosih informacij (pravila ali dejstva), ki veljajo za doloCeno problemsko področje. Interpreter sam izvaja pravila tako, da primerja, te se med podatki v podatkovni bazi pojavi ustrezen vzorec. Ravno ta zamisel, da lahko v sistem dodajamo (ali pa briSemo ali spreminjamo) pravila ali dejstva neodvisno od ostalega sistema, moCno olajSa programiranje Se zlasti za najmlajSe uCence, saj je ob pravilnosti vseh vloženih pravil za-jamCeno tudi pravilno delovanje celotnega sistema. V mikroprologu obiCajno programiramo tako, da 1. definiramo dejstva, objekte in relacije med n j i mi 2. definiramo pravila, s katerimi doloCimo zakonitosti problemskega prdstora 3. postavljamo razna vpraSanja o vpisanih dejstvih in pravilih ter zakljuCkih sestavljenih pravil. Tako način programiranj a kot komunikacija sama ot-r- bi i Se opisovanju v naravnem jeziku kot pri ostalih prc.grr3m = |i.ih jezikih. Na nekaj enostavnih uvodnih primerih si oglejmo izraCanje v si ovenilCi ni , prologu in mi krocrol ogu, oziroma dodatku SIMPLE, ki ga dobimo hkrati s kaseto z mikroprologom ea mikroraCunalni k Sinclair ZX. Slo'venStina: Jaka je oCe od Andreja. Prolog : ocefjaka, andrej). Mikroprolog: Jal.a oce-od Andrej ' ali oce(Jaka Andrej) ali oce(jaka andrej) Komentar: Pri prologu se konstante zatnejo. z malo začetnico, zato piSemo npr. "andrej". V mikroprologu lahko piSemo konstante z veliko ali malo. V osnovnem prologu imamo pre-fiksno notacijo, v mikroprologu (programu SIMPLE -glej dodatek 1 ) pa lahko izbirama med pre-fiksno in infiksno notacijo za enega ali dva argumenta. Zaivet argumentov lahko izbiramo med pre-fiksno notacijo in in-fiksno z veC argumenti zdruSenimi^v seznam. SlovenSCina; Janez ljubi Majdo; Prolog ; ljubi(janež, majda). Mikroprolog: Janez Ijtibi Majda Komentar: V obeh prologih razumljivo ne moremo sklanjati, spregati itd., «Se zlasti ne v slovenščini. Zato moramo povsod pisati popolnoma enake oblike besed. SlovenSCina: Janez prodaja krompir. Janez je,zelje. Jansz prodaja paradižnik. Janez je krompir. Prolog : prodaja(janež, krompir). je(jane2, zelje), prodaja(janež, paradižnik). je(janez, krompir). Mikroprolog: Janez prodaja krompir Janez je zelje Janez prodaja paradižnik Janez je krompir Slovenščina: Ali Janez je in prodaja zelje? Prolog : jB(janež, zelje), prodajafjanez, zelje). Odgovor : -^VES Mikroprolog: is( Janez je zelje and Janez prodaja zelje) Odgovor : YES Komentar: Konjunkcije (AND) delamo v prologu : vejicami, v SIMPLu z "and". Disjunkcije (OR) običajno delamo z veC samostojnimi stavki. SlovenSCina: Kdo je in prodaja krompir? Prolog : je(X, krompir), prodaja(X, krompir). Odgovor : X = janež Mikroprolog: whi,ch(X: X X Odgovor : Janez' je krompir and prodaja krompir) Komentar: Spremenljivke so vezane znotraj enega stavka, to pomeni, da mora X znotraj stavka imeti natanko isto vrednost, dva X-a v dveh stavkih pa nimata neposredne povezave preko imena. Spremenljivke v mikroprologu so !<,.X, y, Y, z. Z. lahko pa jim dodamo üe Številko, npr.: Kil. SlovenSCina: Prolog Odgovor : Mi kroprolog: Odyovnr Janez pripoveduje:" Moja mama je, rodila otroka, pa mi ni ne brat ne sestra. Kdo je to?" mati(mama, Janez). ,kdo(X) :- mati (mama, X), not bratf.janea, X), not 5estra(X, janez). X = janez moja-mama je-mati-od Janez which'To je X: moj.3-mama je-mati-od X and not .Jacifrr. .ly-brot-ud X and Komentar: Pri takem presi i kovanju iz naravnega jezika v katerikoli prolog je seveda treba upoštevati, da je v prologu zelo malo predprogra-miranega znanja v obliki podprogramov. Zato moramo CloveSko znanje (angl. common sense) zakodirati za vsak primer posebej, npr. v zgornjem primeru moramo de-finirati relaciji "brat" in "sestra". Čeprav program tokrat pravilno deluje tudi brez tega. V teh primerih smo prviC sreCali I negacijo'- konstrukt "not". 3. Primerjava med prologom in mikroprologom To J C not X č»ner . jt^-J snez. Eno zanimivih vpraSanj o mikroprologu (programu SIMPLE) je, v kolikšni meri so dodatki in spremembe boljSe kot v standardnih verzijah prologa. To' bi nam povedalo, v kolikSni meri lahko pričakujemo nadaljne spremembe v razvoju logi-Cnega programiranja. Odgovor na to je'precej opurtunistiCen, saj spremembe le malenkostno spreminjajo osnovni koncept. DoloCeni dodatki kot moSnost infiksnega zapisa so verjetno smiselni tudi za resno programi ranje, za uCenje pa so po mnenju avtorjev izredno koristni. Drugi dodatki kot moSnost pisanja konstant z veliko zaCetnico so ugodni, vendar potegnejo za seboj težave pri pisanju spremenljivk (ni mnemoniCnih spremenljivk - glej /8/). Tudi pri pisanju nu-meriCnih izrazov na prvi pogled pridobimo v obrnljivosti in imamo tako eno izjemo manj, saj lahko numeriCni izraz obravnavamo kot obiCajno relacijo in lahko iSCemo katerokoli spremenljivko. V obiCajnih prologih to ni .mogoCe, saj lahko raCunamo le v eno smer, npr. Y is X + 5,. v mikroprologu pa bi zapi sal i" BUM(X 5 Y) in bi lahko računali X npr. s SUM(X 5 7) ali Y s SUM(2 5 Y). Nekatere druge spremembe kot pisanje presledkov namesto vejic, pisanje "and" za' konjunkcije itd. pa so bolj ali manj oblikovne narave. Omenimo Se nekatere dodatne lastnosti kot ukaze za delo z nizi*, solidno realno aritmetiko (vsaj za jezike umetne inteligence), ukaze za delo z datotekami ... Creprav so doloCene oblikovne razlike, pa lahko v mikroprologu naredimo pral-.tiCno vse operacije kot v prologu, tako lahko uporabljamo tudi na-jmoCnéjSe programske prijeme iz obiCajnega prologa celo na najmanjših mikroraCunalni ki h. tal pa nekateri moduli skoraj ne pridejo v poStev na najmanjših raCunalni ki h, recimb ukazi za sledenje izvajanju, saj na najmanjSih mikroračunalnikih hitro zmanjka pomni 1 niSkega prosto- tehniCné karakter i st ike mikroprologa so' prav tako med najboljšimi glede na ostale inaCice. V enem stavku bi jih naSteli z: izredno majhen in hiter prevajalnik z nekaj opcijami (osnovni mikroprolog, standardni prolog, SIMPLE...), modularna struktura, izdelana, komunikacija s perifernimi napravami. Modularno programiranje je moCno izraženo. Ve-Cji program razbijemo na logiCno zakljuCene manjSe dele in jih deklariramo za module. Med izvajanjem lahko izvajamo samo nekaj modulov. Ko potrebujemo kakSen modul, ki ga nimamo v centralnem pomnilniku, ga naložimo z ustrezne periferne enote (diskete, diska, ...) in ga ponovno odložimo, ko ga ne potrebujemo veC. T^ko lahko izvajamo precej obsežnejSe programe, kci pa nam to omogoCa pri mi kror aCunal ni ki h prece,; omejeni centralni pomnilnik. Tudi komunikacija s perifernimi napravami je zelo u"inl.;ovita in enostavna, saj preko vmesnike- R3232 dosegamo naprave od , t i sk^al n i kov do gibl:ih ali trdih disk;ov. .Literatura o mikroprologu je dokaj solidna, ponekod pa je nepotrebno prilagojena mlaj Si m uCencem. Oglejmo si primer is /4/ s strani 129: (x y) sums-to 2 if BUM(x y 2) uins-to O saj j» krajft«, bolj univerzalno in bolj "Cisto" logiCno razmišljanje. Take drobne ohlapnosti so nepomembne pri programiranju malih primerov, pri zahtevnejših programih pa so eden poglavitnih vzrokov za nezanesljivo in nepravilno delovanje, saj podobno Uot gornji primer puSCajo prostor za nepredvidene situacije Kar preberemo kot: povpreCje od x je y. Ce je vsota elementov iz n enaka z in je x sestavljen iz X elementov in y = z/X. Podprograme "ima-vsoto", "dolg" in "deljeno" moramo sami sprogramirati s O ima-vsoto O (:•. I y) ima-vsoto z i-f y ima-vsoto zl and SUMCzl X z) Komentar: Vsota praznega seznama je 0. Vsota seznama s prvim elementom x in ostankom seznama y je z pri Čemer je y vsota z I in z « zl + X. l> dolg O (X ! y) dolg z if y dolg zl and SUM(zl 1 z) deljeno(x y z) if TIMES(y z x) Operacije nad množicami: N presek (y z) if x isalltX: X ON y and X ON 2> X razlika (y z) if x isall(X: X ON y and not X ON z) X Clan X if X ON X Komentar; Npr. presek: množica x je presek množic y in z. Ce je sestavljena iz elementov, ki so v y in z hkrati. Tu smo sreCali konstrukt "i sali", ki zgradi seznam iz elementov, ki ustrezajo logiCnemu pogoju v oklepajih. ZGODOVINA: (zaCetek druge svetovne vojne) datum 1941 Informbiro datum 194S (konec druge svetovne vojne) datum 1945 which (x se je zgodil leta 1941: x datum 1941) (zaCetek druge svetovne vojne) se je zgodil leta 1941 which( Informbiro je bil leta.X: Informbiro datum X) Informbiro je bil leta 1948 Hitler je nacist nacist hoče nadvlado nacist hoče vojno UCenec skuSa odgovoriti na vpraSanje, kaj hoCe Hi tier : which(;!: Hitler hoče x ) No (more) answers (prvo vprašanje ni rodilo sadov) which(;;: Hitler je x) nacist which(Hitler hoče x: nacist hoče m) Hitler hoče nadvlado Hitler hoče vojno Z gradnjo obsežnih baz, ki vsebujejo veliko med seboj povezanih podatkov, lahko uCenci povezujejo informacije med seboj in se tako uCijo spoznavati povezave, ne samo gola dejstva. Poleg tega je enostavno pisati programe za simulacijo zgodovinskih dogajanj /4/. Ti programi so prav tako primerni za uCenje zemljepisa, sociologije, spoznavanje narave, uCenje kemije ali arheologije /9/. UerENJE JE: I KOV Za S-alo prepiSinio nii i:ropr ol og v " si oven^il i no: dodaj (:.'? i-f odc1<::> kateri(Ä) if which(x) en(x) i-f one(x> vsDta(x y z) if SUM(x y z) X element y if x ON y dodaj (Jane: ljubi Micl;a> kateri (>;: >; ljubi MickaJ Janer Poskusimo Se s prevajanjem mc>d jeziki: I je jaz you je ti sun je sonce see je vidim hollidays je pocitnice sea je morje and je in 0 angl-sl O (:< ' X) angl-sl !y I Y> i f :: j e y and X angi-sl Y which<;<: x angl-sl (jaz vidim Gonce) ) 1 see sun . which (;;: (see hollidays and sun and sea) ang 1 -si' ;; ) vidim počitnice in sonce in morje Komentar: zaradi bogastva slovničnih oblik v slovanskih ali germanskih jezikih takSni prime-rtki niso tako uspeSni kot npr. v angleSCini ali -francoSeini . TeSave pri -poutevanju: Te;;avB pri praktiCnem pouCevanju so izvirale iz. vc'd; vzrokov. Nekaj težav je izviralo iz opreme, tako npr. je bilo tipkanje na računalnikih Sinclair z gumijastimi tipkami izredno zamudno. Fri najmlajših uCencih je bilo opaziti tudi probleme z motiviranostjo, saj bi se vCasih ra-'.; j5ii igrali kakSne" i gr i ce. Pri izobraževanju ra-. CunalniSko podkovanih kadrov je bilo opazno razumevanje tudi na globjeiti proceduralnem nivoju, medtem ko so učenci v računalniškem vrtcu ostali na nivoju deklar at ivno-intuitivnega razumevanja rekurzije in nekako niso uspeli preskočiti tega praga. Rezultati testiranja; Ne predlog dr. M. Ribarita (idejni pobudnik in vodja celotnega projekta računalniških vrtcev) smo poskusili ugotoviti, ali je osnovni cilj učenja z mikroprologom uspel ali ne. Ker je osnovni cilj učenje logičnega razmišljanja, smo izbrali naloge - logične uganke - iz /11/ in primerjali rezultate testov ob začetku in koncu tečaja iz mikroprologi v računal niSkem vrtcu. Učenci so reSevali ■ pismene teste načeloma v sl!upi.nah po dva, tako kot je običajen način dela v vrtcu. Obakrat so imeli reSevalci na voljo 25 minut. V tabelah vidimo rezultate prvega in drugega testiranja. Številke na levem robu pomenijo Številke nalog iz /11/, Številke na zgornjem robu zaporedno Število izdelka, enice znotraj tabele pa uspeSno reSene naloge. Rezultati prvega testiranja: 1 2 3 4 5 6 7 8 Seznam vaj iz računalniSkega vrtca je v dodatku Po mnenju avtorjev je ena večjih prednosti poučevanja mikroprologa ravno v obsežni zbirki zanimivih vaj, ki so hkrati zanimive in poučne. Tako se učimo postavljati vpraSanja (query) v detektivskih nalogah, npr. iSčemo Jacka Razpa-rača v podatkih o osumljencih, izbiramo miss sveta izmed kandidatk itd. Po drugi strani pa je zaporedje učne snovi v /4/ nelcoliko prepočasi tempirano za sposobnej'ie učence, saj prepočasi pride do praktičnega progrsmiranj a. Ena večjih pomankl j i voditi" predvsem za mlaj Se učence je pomanjkanje spec i--si i z i r ani h konstru-ktov za risanje. Tfjko v bssicu kot v logoju večina začetnega poučevanja temelji na grafiki, v mikroprologu pa kljub podatkom iz literature nismo uspeli dobiti posebne grafilje na.sinclai-rju /"i in učnih' materialov zanjo. Seveda pa lahko 5i>mi napi^oitio svoje gr-r-fične rutine s pomočjo izpisovanja l::rmilr:ih zn3l:ov. 6. IrkuSn.ie = poučevanjem V /4,' Enn?.ls tjr edst s-.! j a ^olsk.e materiale za britansl-.i proj ekt ( naj ve«; v cblit;i seznama vaj). Učenje je potekalo v običajnih Šolskih razredih z cnitTv r rt "un.51 n i kom in velil:ifn zaslonom. V razredu je balo 26 učencev v starosti 10-11 let. Pouk je potekal v ok'viru. rednega pouka in je t'-ajal 2 uri 20 minut tedensko. Učenci so imeli popoldne motnost učenjč^ na üolskih računalnik ih.. V Jugoslaviji je pote(:alD učenje mikroprologa na Institutu "Jo^ef Ste-fan" v okviru izobraževanja zaposlenih na Institutu in v okviru Računalniškega vrtca za učence v starosti 10-14 let P'OLii štirinajstih Tijt-d'^h uCencev je pots-' t.? ^iS.ni.'-. TiklGpJh '.äi-ii:; t rio ave uri m . 1 r 1'.T v üf" "i žt i r^^poslenih' pa v 26 1 1 1 1 1 1 1 27 23 1 1 34 1 1 37 1 11 41 3. izdelki niso dobili nobene točke Skupno 14 reSenih nalog, 11 izdelkov. Število reSenih nalog na izdelek: 14/11 = 1.27. Rezultati drugega testiranja: 1 23456789 29 1 1 1 1 1 1 1 1 30 1.11 36 11111 1 38 1 1 1 1 1 -.9 Sk:upno 22 reSenih nalog, 9 izdelkov. Število rešenih nalog na izdelel^: 22/9 2. 44. Rezultati testiranja nakazujejo pòzitiven vpliv učenja mikroprologa na logično' razmišljanje, saj je Število uspeSno reSenih nalog na izdelek narastlo z 1.27 na 2.44. Vendar ti rezultati nimajo neoporečne znanstvene teže, saj je izstop.ilo nokaj učencev, ki jt imelo največ težav, tudi zasedba dvojic ni bila enaka med pr— vj m in drugim testiranjem. Z.arđdi tog» im#jo rezultati le informativno vrednost. V obeh testiranjih so bile izbrane približno enako težke naloge, tako da je bila ena očitno pretežka, za ostale pa smo upali, da jih bodo lahko reSl1 i. Glede na dosežene rezultate pa so bile nekatere naloge le preteži-e, zato bi bilo za veCjo objektivnost rezultatov smiselno ponoviti testiranje z večjim S^tevilom lažjih nalog. UCenci BO se večinoma^ pritoževali, da... so bile drugiC naloge težje kot prvič. Kljub vsemu pa testi kažejo na to, da obstaja močan positiven ùCinek učenja mikroprologa na logično rastni SI janje, saj se je pa vsem sodeč močno, dvignilo povpre-Č.1-- isti''. u.!:E?r,cev. Poglejmo si Število dvojic uCencev, ki so resili po 1, Z, 2 in 1 nalogo v ubeli mur jenj i h: Nalog PrviC 4 1 ? i 1 5 O 3 Drugi C O 4 5 O O 7. Diskusija Osebne iskuSnje; Pri prehodu s prologa na mikroprolog so doloCene težave, tez nekaj Casa pa se pokaSe, da je svoboda izražanja nekoliko vetja v mikroprologu, oblika zapisa pa nekoliko enostavnejša. Tudi poučevanje v mikroprologu je bolj učinkovito. Kljub pogostim trditvam, da je prolog enostaven za uCenje, se avtorja ne strinjata povsem s tem. Utenje prologa je predvsem učinkovito in hitro, to pomeni, da lahko uCenci kmalu zaCrrejo pisati zahtevne programe. Pred tem pa morajo narediti zahteven miselen preskok. Ta preskok je dokaj enostaven za tehniCno izobražene kadre, npr. matematike ali za usmeritve, ki podpirajo logiCno razmišljanje. Pri drugih izobrazbah pa se pokažejo težave. Posebno rekurzija in proceduralni pomen prologa delajo veliko težav tudi raCunalniSko izobraženim kadrom, ki so navajeni programirati v starejSih jezikih brez rekurrije (cobol, -fortran). Z mi-kroprologom je uCenje potekalo opazno hitreje in bolj uspeSno. Mikroprolog kot programski jezik: S stalifiCa pro-fesionalnega programiranja mikroprolog ne prinaSa velikih sprememb glede na ustaljene inaCice kljub temu, da. ima nekaj dodatkov, ki nekoliko polepSajo logiCno celovitost jezika. Ti dodatki so vCasih celo nekoliko dolgovezni s staliSCa izurjenega programerja, zato pa so veliko bolj koristni za uCenje programiranja, saj ne samo olajSujejo uCenje,. ampak omogoCajo Se nekoliko viSji - bolj deklarativni nivo in s tem dajejo možnost veCjega poudarka uCenju logičnega razmišljanja. Druga misel, ki se ponuja, pa je, da je osnovni mehanizem prologa zelo moCno orodje, ki ga inaCice niti v peti generaciji ne bodo bistveno spremenile vsaj z logičnega staliSCa. TehniCno-uporabniSko gledano pa je mikroprolog veliko bliže jezikom za pro-fesi-onalno programiranje, saj ima izdelano komunikacijo z zunanjimi napravami, omogoCa modularno programiranje, prevajalnik sam pa je med najmanjšimi in najhitrejšimi. Mikroprolog kot uCni jezik: Mikroprolog je verjetno Se nekoliko primernejši za uCenje glede na ostale inaCice, Se posebej pokaže prednosti pri poučevanju učencev z ne pretirano predizo-brazbo. Celo primerjava s programskim jezikom logo /4/ polnaSe kar nekaj prednosti za uCence, ki 50 stari nad 10 let. Le za ml aj Se uCence pod 10 let je mikroprolog pretežak. Poglavitne prednosti uCenja z mikroprologom so razvijanje lo-giCnega miSljenja, razvijanje kreativnega in samostojnega r&zmiSljanja in uCenja programerskih principov pete generacije raCunalnikov. B. Literatura 1. Kowalski R.': Predicate logic as programming language, Proc. IFIP 74 Conf.. North-Hol1 and 1974 Kowalski R.; CACM, Vol . 22 Algorithm = Logic + Control, , No.7, 572-5^5, 1979 Cleri: K.L., McCabe F.G., Ennals J.R.j A Micro-PROLOG Primer, Logic Programming ftssoci-ater., 1933 4. Ennals R.: Beginning Hi ero-PROLOG, Ellis Ho-rwood Ltd., London, 1904 5. McCabe F.G., Clark K.L., Steel B.D.: MicroPROLOG Programmers .Re-ference Manual, Logic Programming Associates, 1984 é>. Bratko I., Gams M.: Prolog: osnove in principi strukturiranja podatkov. Informatica 4/1980, str. 40-46, 1980 7. Bratko I.: Expert Systems and Prolog, Perga-mon Infotech State o-f the Art Report; Supercomputer Systems Technology, F. Sumners (ed.) Series 10, No. ć>, Pergamon In-fotech Ltd., 1982 8. Gams M.; Osnove dobrega programiranj a, Cankarjeva založba, 1985 9. Ennals R.: Micro-PROLOG across the Curriculum, Collected papers 1982-1984, Research Report DoC 84/17, Imperial College, 1984 10.Gams M.: Mikroprolog, seminarski materiali, str. 50, 1985 ll.Smullyan R.M.: Alica v deželi ugank. Državna založba Slovenije, Ljubljana 1984 DODATEK 1 4. Seznam osnovnih ukazov za delo s programom "SIMPLE" Opomba! Nekateri ukazi so vezani na Sinclair ZX: "caps Shi-ft" "Z" "break space" istoCasno (prekinitev izvajanja) "caps shift" "a" istoCasno (no scrool) accept -za vpisovanje veC stavkov z isto re-l aci jo. Primer: accept i ma-rad ima-rad. (Lojze Mojca) ima-rad.(bbb ccc) ime-rad.end ^ add -za dodajanje stavkov bazo podatkov Primer: add(Jure ima-rad Meri) (doda stavek v bazo) add 2 (Mira ima-rad Miha) (doda stavek na tretje mesto med stavke relacije "ima-rad") delete -zbriSe stavek dane relacije r ustrezno zaporedno Številko Primer : delete ima-rad 1 edit -eoitiranjt in popravljanje stavkov programa. SploSna oblika: edit ime-relacije zaporedna-Stevi1ka- stavka Pri mer: edit ima-rad 1 1 (Lojze ima-rad Mojca) Zdaj se lahko premikamo po stavku s tipkami/puSCicami in ga sproti popravi j amo. kill -unici vse stavke za dano relacijo ali cel program. Pri mer : kili ima-rad (zbriSe vse stavke relacije ima-rad) kili ali (zbriSe ves program) list -izpiSe vse stavke dane relacije ali cel program. Pr i mer : list ima-rad whi eh all one i s isall not load reserved de-f i néd (izpiSe vse stavke relacije "ima- rad") list aH (ispiSe cel program) -iSCe vse raoSne odgovore, -sinonim za "which", -daje samo en odgovor naenkrat, -preveri pravilnost in odgovarja z "YES" ali "NO", -grajenje seznamov. Pr i mer: which(x:x isall (y:y ima-rad Mezi)> (izpiSe se seznam vseh, ki imajo radi Mezija) O' -negiranje pogojev. -naloSi program v raCunalnik z kasetofona. SploSna oblika; load ime-programa -shrani celotni' program iz računalnika na kasetofon. BploSna oblika: save ime-programa -za iskanje rezerviranih besed.. Primer; which ! reserved) (izpiSe vse rezervirane besede) -tte hoCemo izvedeti, Icatere relacije so definirane. Primer; which (>;::< de-fined) (izpiSe imena vseh relacij, ki so definirane v naSem programu) -Članstvo v seznamu. Je izpolnjen, ko je"objekt Clan seznama. Primers is(5 ON (1 2 3 4 5)) YES -doda objekt na prvo mesto v danem seznamu. Pri mer s which(x:C0NS(3 (4 5 é>) ) ) (3 4 5 6)-No (more) answers -združi dva seznama v tretjega. Pr i mer s which (>! s APPEND ( (1 2 3 4) (5 6 7 8) x)) (1 2 3 4 5 6 7 8) No (more) answers DODATEK 2 Tu so zbirno navedene vaje teCaja iz mikropro-loga, ki je potekal v okviru raCuns1 niSkega vrtca /10/: 0. seznanjanje z raCunalni k;om, seznanjanje z osnovnimi ukazi tipa "add", "1 i st","accept", "delete", "kill", "edit" 1. enostavni stavki, opisovanje podatkov/stanj (ukaz "add", vaje na nivoju "Pavle ima-rad Meri", vaje na nivoju opisovanja sedeSnega reda uCencev v uCilnici) 2. postavljanje vpraSanj (ukaz "is", enostavne vaje) 3. pretvarjanje stavkov iz slovenSCine v mikroprolog (trditve, vprašanja, vaje v pretvarjanju drugih jezikov) 4. uporaba spremenljivk in ukaza "which" (vaje na nivoju enostavnih družinskih relacij) ON CONS APPEND 5. sestavljena vpraSahja s konstruktom "is" (tvorjerije logičnih konjunkcij z uporabo konstrukta "and") 6. sestavljena vpraSanja s konstruktom "which" (tvorj enje : logiCnih konjunkcij z uporabo konstrukta "and") 7. vaje - izpraševanje o vpisanih podatkih -kaj je nad, viSje.. B. enostavna aritmetika (LESS, SUM, TIMES in uporaba teh konstruktov za raCunanje) 9. sploSna oblika stavka "which" 10. pravila (A if B and C and ...) 11. pravila z uporabo spremenljivk (vaje, npr. detektivske naloge tipa iskanje Jacka RazparaCa) 12. predstavitev enostavnih pravil z diagrami/ mrežami ( vaje iz družinskih relacij, npr. Jože je-oCe-od Lojze) 13. predstavitev pravil s, spremenljivkami v obliki semantičnih mrež (vaje iz družinskih relacij, npr. k je-oCe-od y if y je-sin-od x) 14. prehod na zapletene oblike pravil, ki se med seboj povezujejo (npr. stric je brat od oteta ali ...) 15. aritmetične in.1ogiCne reiacij e (npr. kdo je viSji ali starejSi od koga) 16. seznami (npr. pretvarjanje iz slovenSCine v mikroprolog) 17. dostop do elementov seznama (uporaba vzorcev in operatorja za loCevanje glave od seznama) 18. vaje s seznami 19. konstrukt "one" 20. vaje s seznami in bazami podatkov (npr. izbiranje miss sveta, iskanje asociacij, zamenjevanje besed ...) 21. rekurzija (vaje na nivoju družinskih relacij - npr. "prednik") 22. Članstvo v seznamu (konstrukt "ON" in njegova definicija) 23. vaje s seznami (programi za dolžino seznamov, združevanje seznamov) 24. negacija . ° (uporaba konstrukta "not") 25. enomestne"relacije (npr. Nika bere) 26. grajenje seznamov (uporaba konstrukta "isall") 27. naloge s seznami (seštevanje elementov seznamov, • množenje elementov seznamov) 28. nekoliko težje naloge s seznami ( kupovanje najprimernejSega avtomobila , iskanje raznih povpreCij) 29. grajenje verig (npr. iskanje verig potomcev v družinskih drevesih) 30. vaje (npr. potapljanje ladjic, ugibanje skritih informacij, iskanje "kdo j,e najviSji" itd.) 31. sistemski ukazi O irti SVEUČILIŠNI RAČUNSKI CENTAR UNIVERSITY COMPUTING CENTRE POZIV NA SUDJELOVANJE VIII MEĐUNARODNI SIMPOZIJ "KOMPJUTER NA SVEUČILIŠTU" SVIBANJ 12.- 15. 1986. Mjesto: DUBROVNIK/CAVTAT, HOTEL CROATIA Organizator: SVEUClLlSNI RAČUNSKI CENTAR, ZAGREB Teme: ■ INFORMATIČKA IZOBRAZBA ■ RAČUNSKI SISTEMI I MRE2E RAČUNALA ■ OSOBNA RAČUNALA ■ SOFTVERSKO IN2INJERSTV0 ■ INFORMACIJSKI SISTEMI I BAZE PODATAKA ■ STATISTIKA I STATISTIČKI SOFTVER ■ ANALIZA PODATAKA ■ MODELIRANJE, SIMULACIJA I OPTIMIZACIJA ■ DIZAJN I PROIZVODNJA POMOCU RAČUNALA (CAD/CAM) ■ UMJETNA INTELIGENCIJA I EKSPERTNI SISTEMI ■ PRIMJENA INFORMATIČKIH SREDSTAVA I METODA U PRIRODNIM I DRUŠTVENIM ZNANOSTIMA ■ DRUŠTVENI I PRAVNI ASPEKTI INFORMATIKE Rok za sažetke: 15. PROSINAC, 1985. Rok za radove: 15. 02UJAK, 1986. Obavijest o prihvaćanju: 1. VELJAČA, 1986. Struktura Simpozija: PREDAVANJA, POSTER SEKCIJE, PREZENTACIJE HARDVERA I SOFTVERA, PANEL DISKUSIJE, IZL02BE Informacije: Branka Radić Sekretarica Simpozija SVEUČILIŠNI RAČUNSKI CENTAR, 41000 Zagreb, Engelsova b.b., Jugoslavija. Tel.: 041/510 099, Tlx.: 21871