Automaatide teooria, lõplikud masinad
Erinevate masinate ülesehitus, disain, tööpõhimõte on suuresti määratud selle funktsionaalse otstarbega. Eristada tehnoloogilisi, transpordi-, andmetöötlus-, sõjaväe- ja muid masinaid. Erinevates tööstusharudes võetakse laialdaselt kasutusele terveid automaatseid komplekse, mis on mõeldud keerukate tehnoloogiliste protsesside läbiviimiseks. Projekteeritakse ja ehitatakse automaate, mis täidavad erinevaid loogilisi funktsioone (loogilised masinad).
Automaatide teooria — küberneetika sektsioon, mis tekkis digitaalarvutite ja juhtimismasinate tehnoloogia nõuete mõjul. Automaatide teoorias uuritud diskreetsed masinad on reaalsete süsteemide (nii tehniliste kui ka bioloogiliste) abstraktsed mudelid, mis töötlevad diskreetset (digitaalset) teavet diskreetsete ajasammudega.
Automaaditeooria põhineb täpsetel matemaatilistel kontseptsioonidel, mis vormistavad intuitiivsed ideed automaadi toimimise (käitumise) ja selle struktuuri (sisestruktuuri) kohta.
Sel juhul mõistetakse teabe teisenduse all alati toimingut, mis muudab sisendtähestiku tähtedest koosnevad sisendjadad väljundtähestiku tähtedest koosnevateks väljundjadadeks.
Laialdaselt kasutatakse matemaatilise loogika, algebra, tõenäosusteooria, kombinatoorika ja graafiteooria aparaate.
Probleem automaatide teooriaga selle mõnes osas (automaatide struktuuriteooria) kasvas relee-kontaktahelate teooriast, mis hakkas ilmet võtma 1930. aastate lõpus. kaasa arvatud loogilise algebra meetodid.
Automaatide struktuuriteoorias uuritakse erinevat tüüpi skeeme, mille eesmärk on kirjeldada, kuidas süsteemis õigesti ühendatud lihtsamatest komponentidest (elementidest) luuakse keeruline automaat.
Teine suund, mida nimetatakse abstraktseks automaatide teooriaks, uurib automaatide käitumist (st nende poolt läbiviidava teabe teisendamise olemust), abstraheerides samal ajal nende sisemise struktuuri spetsiifikast, ja tekkis 1950. aastatel.
Automaatide abstraktse teooria raames ammendab mõistete "automaat" ja "masin" sisu sisuliselt automaatse läbiviidava teabe teisendamise standardkirjeldus. Selline teisendus võib olla deterministlik, kuid oma olemuselt ka tõenäosuslik.
Enim uuritud on deterministlikud masinad (automaadid), mille hulka kuuluvad lõplikud masinad — automaatide teooria põhiline uurimisobjekt.
Lõpliku olekuga masinat iseloomustab piiratud mälumaht (siseolekute arv) ja see defineeritakse üleminekufunktsiooni abil.Mõningase mõistliku idealiseerimisega võib kõiki kaasaegseid matemaatilisi masinaid ja isegi aju nende toimimise seisukohalt pidada lõplikeks automaatideks.
Mõisteid "järjestusmasin", "Milly automaat", "Moore'i automaat" kasutatakse kirjanduses (ja mitte kõigi autorite poolt ühetaoliselt) termini "lõplik automaat" sünonüümidena või teatud tunnuste rõhutamiseks lõpliku üleminekufunktsioonides. automaat.
Piiramatu mäluga automaat on Turingi masin, mis on võimeline teostama (potentsiaalselt) mis tahes tõhusat teabe teisendust. Mõiste "Turingi masin" tekkis varem kui "lõpliku oleku masina" mõiste ja seda uuritakse peamiselt algoritmide teoorias.
Abstraktsete automaatide teooria on tihedalt seotud tuntud algebraliste teooriatega, näiteks poolrühmateooriaga. Rakenduslikust vaatenurgast pakuvad huvi tulemused, mis iseloomustavad info muundumist automaadis mälu mahu osas.
Seda näiteks automaatidega tehtud katsete probleemide puhul (E.F. Moore’i teosed jt), kus üht või teist infot automaadi siirdefunktsioonide või selle mälu mahu kohta saadakse automaatikaga seotud tulemuste põhjal. katsed.
Teine ülesanne on arvutada välja väljundjadade perioodid, tuginedes olemasolevale infole automaati mälumahu ja sisendjadade perioodide kohta.
Väga oluline on meetodite väljatöötamine lõplike olekumasinate mälu minimeerimiseks ja nende käitumise uurimiseks juhuslikes keskkondades.
Abstraktsete automaatide teoorias on sünteesiprobleem järgmine.Mingi selgelt formaliseeritud keele mõttes on tingimused kirjutatud projekteeritud automaati käitumisele (automaadis kujutatud sündmusele). Sel juhul on vaja välja töötada meetodid, mis vastavalt igale kirjalikule tingimusele:
1) selgitab välja, kas on olemas selline olekumasin, mille poolt teisendatud teave vastab sellele tingimusele;
2) kui jah, siis konstrueeritakse sellise lõpliku oleku masina üleminekufunktsioonid või hinnatakse selle mälumahtu.
Sünteesiülesande lahendamine sellises sõnastuses eeldab eelnevalt mugava keele loomist automaadi töötingimuste salvestamiseks koos mugavate algoritmidega salvestamiselt transitiivsetele funktsioonidele üleminekuks.
Automaatide struktuuriteoorias seisneb sünteesiülesanne antud tüüpi elementide ahela konstrueerimises, mis realiseerib oma üleminekufunktsioonidega antud lõpliku automaati. Sel juhul esitavad nad tavaliselt mõne optimaalsuse kriteeriumi (näiteks minimaalse elementide arvu) ja püüavad saada optimaalset skeemi.
Nagu hiljem selgus, tähendab see, et mõned meetodid ja kontseptsioonid, mis on varem välja töötatud seoses relee-kontaktahelatega, on rakendatavad ka teist tüüpi vooluahelatele.
Seoses elektroonikatehnoloogiate arenguga on kõige levinumad skeemid funktsionaalsetest elementidest (loogilised võrgud). Loogikavõrkude erijuht on abstraktsed närvivõrgud, mille elemente nimetatakse neuroniteks.
Olenevalt ahelate tüübist ja teabe muundamisest, mille jaoks need on ette nähtud, on välja töötatud palju sünteesimeetodeid (Releeseadmete süntees).
Vaata -Kombineeritud ahelate minimeerimine, Carnot' kaardid, ahelate süntees
Lõpliku oleku masin — fikseeritud (töötamise ajal suureneda võimetu) mälumahuga juhtimissüsteemi matemaatiline mudel.
Lõpliku olekumasina mõiste on matemaatiline abstraktsioon, mis iseloomustab juhtimissüsteemide komplekti (näiteks mitmeahelalise releeseadme) üldisi omadusi. Kõigil sellistel süsteemidel on ühised tunnused, mida on loomulik aktsepteerida lõpliku automaati definitsioonina.
Igal valminud automaatil on välismõjudele ja siseelementidele avatud sissepääs. Nii sisend- kui ka siseelementide jaoks on kindel arv diskreetseid olekuid, mida nad saavad võtta.
Sisend- ja siseelementide olekute muutumine toimub diskreetsetel ajahetkedel, mille vahelisi intervalle nimetatakse tiksudeks. Siseoleku (siseosade oleku) lindi lõpus määravad täielikult sisemine olek ja sisendi olek lindi alguses.
Sellele karakteristikule saab taandada kõik muud lõpliku automaadi definitsioonid, eriti definitsioonid, mis eeldavad, et lõplikul automaadil on väljund, mis sõltub automaadi sisemisest olekust antud ajahetkel.
Sellise karakteristiku osas ei oma selle sisendite olemus ja siseolekud tervikliku automaati kirjeldamisel tähtsust. Sisendite ja olekute asemel võite lihtsalt vaadata nende numbreid juhuslikus numeratsioonis.
Olekumasin seadistatakse, kui on määratud selle sisemise olekunumbri sõltuvus eelmisest sisemisest olekunumbrist ja eelmisest sisendi olekunumbrist. Selline ülesanne võib olla finaallaua vormis.
Teine levinud viis tervikliku automaati defineerimiseks on nn ülemineku diagrammid. Sisendolekuid nimetatakse sageli lihtsalt sisenditeks ja sisemisi olekuid nimetatakse lihtsalt olekuteks.
Lõpliku olekuga masin võib olla nii tehniliste seadmete kui ka mõne bioloogilise süsteemi mudel. Esimest tüüpi automaadid on näiteks releeseadmed ja erinevad elektroonilised arvutid, sh. programmeeritavad loogikakontrollerid.
Releeseadme puhul mängivad sisendolekute rolli releeseadme tundlike elementide olekute kombinatsioonid (iga selliste olekute kombinatsioon on "kompleks olek", mida iseloomustab kõigi tundlike elementide tähis. need diskreetsed olekud, mis neil antud hetkel on). Samamoodi toimivad siseolekutena releeseadme vaheelementide olekute kombinatsioonid.
Programmeeritav loogikakontroller (PLC) on näide releetoiminguseadmest, mida võib nimetada iseseisvaks olekumasinaks.
Tegelikult, kui programm on sisestatud PLC-sse ja kontroller on hakanud arvutama, ei puutu see kokku välismõjudega ja iga järgneva oleku määrab täielikult selle eelmine olek. Võime eeldada, et sisendil on igas taktitsüklis sama olek.
Ja vastupidi, iga lõpliku olekuga masinat, millel on ainuvõimalik sisendolek, nimetatakse loomulikult autonoomseks, kuna sel juhul ei kanna väliskeskkond tema käitumist kontrollivat teavet.
Vaata ka:
Mikroprotsessorsüsteemide kasutamine elektrotehnikas PLC kasutamise näitel