Pagrindinės abstrakčių automatų teorijos sąvokos. Automatų teorija.docx – Automatų teorija
Ieškokite medžiagų:
Jūsų medžiagų skaičius: 0.
Pridėkite 1 medžiagą
Sertifikatas
apie kūrybą el. portfelis
Pridėkite 5 medžiagas
Paslaptis
dovana
Pridėkite 10 medžiagų
Diplomas už
švietimo informatizavimas
Pridėkite 12 medžiagų
Apžvalga
ant bet kokios medžiagos nemokamai
Pridėkite 15 medžiagų
Video pamokos
greitai sukurti įspūdingus pristatymus
Pridėkite 17 medžiagų
Per pastaruosius dešimtmečius buvo ir vyksta intensyvus darbas kuriant
ir naudoti įvairios sistemos ir diskrečių apdorojimo įrenginiai
informacija. Diskretūs informacijos keitikliai yra plačiai naudojami kaip
įvairių rūšių techniniai automatai, skaičiavimo įrenginiai ir jų funkciniai
blokai, roboto valdymo įrenginiai, kurie valdo objektus pagal duotą
algoritmas. Plati tokių keitiklių klasė yra vienijanti bendruoju pavadinimu
automatai. Šie įrenginiai turi ribotą skaičių įvesčių, kurios priima informaciją,
ir baigtinis skaičius išėjimų apdorotai informacijai išduoti. Santykiai tarp
įvestis ir išvestis pateikiami pagal nustatytą informacijos apdorojimo algoritmą.
Įvesties ir išvesties informacija pavaizduota simboliais, fizinėmis laikmenomis
kurie yra laiko kvantuoti signalai.
Jei "K" simboliai vienu metu po lygiagrečios įvesties arba išvesties
kanalus, bus traktuojami kaip vienas simbolis iš atitinkamos abėcėlės
į vieną „priklijuotą“ kanalą, tuomet tokį automatą galima pavaizduoti kaip įrenginį su
vienas įėjimas ir vienas išėjimas (1 pav.).
Fig.1 - Bendrasis diskrečiosios informacijos keitiklio funkcinis modelis
Yra du automato termino apibrėžimo būdai. Iš pradžių interpretuojama
kaip prietaisas, kuris, tiesiogiai nedalyvaujant asmeniui, atlieka funkcijas
priimti, konvertuoti ir perduoti energiją, informaciją ir kt. pagal
joje įdėta programa, o antroji – kaip matematinis tikrojo modelis
diskretieji informacijos keitikliai. Jo veikimas yra
baigtinių arba apskritai begalinių simbolių seka z1,z2,...
abėcėlės Z, patekusi į įvestį, savo išvestyje sukelia tam tikrą
tos pačios ar kitos abėcėlės simbolių seka w1,w2,.... Šiuo būdu,
bendriausias matematinis diskrečiosios informacijos keitiklio modelis yra
sekos funkcija, rodanti visų sekų Z rinkinį
abėcėlės Z simbolius į kitą W abėcėlės simbolių sekų rinkinį W*.
Šis aiškinimas leidžia schematiškai pavaizduoti keitiklį kaip įrenginį,
realizuojant vienos aibės susiejimą su kita (2a pav.).
Fig.2a – formalus keitiklio modelis
Šis žemėlapių sudarymas vadinamas abėcėliniu žemėlapiu arba abėcėliniu
operatorius.
Automatų teorija yra valdymo sistemų teorijos šaka, tirianti matematiką
diskrečiųjų informacijos keitiklių modeliai, vadinami automatais. NUO
tam tikru požiūriu tokie keitikliai yra kaip tikri įrenginiai
(kompiuteriai, gyvi organizmai) ir abstrakčios sistemos
(pavyzdžiui, formali sistema yra abstrakčių, nesusijusių objektų rinkinys
su išoriniu pasauliu, kuriame pateikiamos veikimo su simbolių rinkiniu taisyklės
griežtai sintaksinė interpretacija neatsižvelgiant į semantinį turinį, t.y.
semantika; aksiomatinės teorijos, apibūdinančios tam tikrą reiškinių rinkinį
jų priežastiniame ryšyje vienas su kitu).
Automatų teorija glaudžiausiai susijusi su algoritmų teorija. Tai paaiškinama faktu
kad automatas diskrečią informaciją žingsniais paverčia diskretiškais momentais
laiko ir generuoja gautą informaciją apie tam tikro algoritmo veiksmus. Šie
transformacijos galimos techninių ir/ar programinių priemonių pagalba. Mašina
gali būti pavaizduotas kaip koks nors įrenginys (juodoji dėžė), prie kurio
imami įėjimai ir išėjimai ir kurie gali turėti tam tikrą vidinį
teigia. Analizuojant automatus, jų elgesys tiriamas esant įvairiems sutrikimams.
įtakoja ir sumažina automato būsenų skaičių dirbant pagal duotybę
algoritmas. Toks automatas vadinamas abstrakčiu, nes abstrahuotas nuo tikrojo
fizinius įvesties ir išvesties signalus, laikydami juos tiesiog kai kurių raidėmis
abėcėlė ir ryšys su idealizuotu diskrečiu laiku. Sintezuojant automatus
(jungimo ar susiejimo procesas) sudaro elementariųjų automatų sistemą,
lygiavertis duotam abstrakčiam automatui. Toks automatas
vadinamas struktūriniu. Ypatingą vietą automatų teorijoje užima baigtinio sąvoka
mašina.
Transformacijos įvesties => išvesties rezultatas (2a pav.) dažnai priklauso ne tik nuo įvesties į
Šis momentas laiko, bet ir iš to, kas buvo anksčiau prie įvesties, iš įvesties istorijos, t.y.
iš transformacijos istorijos. Galimų įvesties istorijų skaičius yra begalinis (skaičiuojamas),
net jei automatas turi baigtinį skaičių skirtingų įvesties informacijos elementų (kaip pvz
galutinis funkcinis keitiklis). Norint kažkaip prisiminti šias istorijas ir
Norėdami atskirti vienas nuo kito, keitiklis turi turėti atmintį. Tam prietaisas
(1.1,6 pav.) įvedama būsenų Q = (qx,q2,...qm) abėcėlė.
Valstybės q samprata čia vaidina labai svarbų vaidmenį. Jų valstybėse mašina
prisimena savo koncentruotą praeitį. Dėl tos pačios įvesties
keitiklis gali reaguoti skirtingai, priklausomai nuo būsenos, kurioje
jis šiuo metu yra.
Baigtinis automatas (2b pav.) – matematinė abstrakcija, leidžianti apibūdinti kelius
pakeisti objekto būseną, atsižvelgiant į jo esamą būseną ir įvesties duomenis,
su sąlyga, kad bendras galimas būsenų Q skaičius ir įvesties signalų rinkinys
Z yra baigtiniai. Baigtinis automatas yra ypatingas abstraktaus automato atvejis.
2b pav. – Būsenos mašina
Būsenos mašina yra viena iš svarbiausių valdymo sistemų tipų.
Pagrindinis baigtinių automatų privalumas yra tai, kad jie natūraliai
taip aprašomos išorinių įvykių valdomos sistemos.
Automatų teorija nagrinėja procesus, vykstančius įvairiuose automatuose
natūra, ir bendrieji modeliai, kuriems jie taikomi, plačiai naudojami tam
algebrinis aparatas, matematinė logika, kombinatorinė analizė ir teorija
tikimybės.
Projektuojant patikimus, gerai veikiančius automatus tenka spręsti nepaprastus
sunkių užduočių. Pavyzdžiui, norint sumažinti, būtina nustatyti sistemų stabilumą
įvairūs automatinių mašinų veikimo nukrypimai. Reikia mokytis ir jautrumo
automatai, nes veikimo procese valdymo sistemų savybės neišlieka
nuolatinis.
Automatų teorija pritaikoma tiek matematikoje, tiek sprendžiant praktines problemas.
užduotys. Pavyzdžiui, pasitelkus automatų teoriją įrodomas kai kurių išsprendžiamumas
formalusis skaičiavimas. Automatų teorijos metodų ir sampratų taikymas studijoms
formalios ir natūralios kalbos paskatino matematikos atsiradimą
lingvistika (matematinė kalbotyra yra matematinė disciplina, dalykas
kuri yra formalaus aparato kūrimas gamtos struktūrai apibūdinti
o kai kurios dirbtinės kalbos.) Automato samprata gali pasitarnauti kaip modelis
objektą atliekant įvairiausias užduotis, o tai leidžia pritaikyti teoriją
automatai įvairiuose moksliniuose ir taikomuosiuose tyrimuose.
Automatų teorijos aktualumas
Yra daug valdymo objektų, susijusių su dideliu
Atsakomybė: branduoliniai ir cheminiai reaktoriai, pramoniniai kompleksai,
gynyba, kosmosas, kasyba. Sėkmės su jais tiesiogiai susidoroti
priklauso nuo veiksmų aiškumo ir nuoseklumo, nuo gebėjimo priimti pagrįstus sprendimus ir
kompetentingai išanalizuoti situaciją, atsižvelgiant į vienareikšmiško aiškinimo galimybę
informacija. skirtinga prigimtis fiziniai procesai tekantys objektais, kompleksiniai
jų ir valdymo sistemų sąveikos pobūdis lemia
valdymo užduočių kūrimo, algoritmizavimo ir programavimo sunkumai. Kilti
sunkumai, susiję su poreikiu pasiekti matomumą ir struktūrą.
Šioms problemoms spręsti naudojamas sukurtas automatų teorijos matematinis aparatas.
Elgesio logikos aprašymas (kokiomis sąlygomis būtina atlikti tam tikrus
veiksmai) automatinio požiūrio struktūroje. Ši savybė daro automatinį
aiškiai ir glaustai apibūdina sudėtingą elgesį. Darbo teisingumas
automatinių mašinų naudojimas yra numatytas projektavimo etape, dėka
grafinis vaizdas, t.y.
vizualiai atvaizduoja valdymo automatų elgesį (grafiškai, lentelėse)
ir kompozicijos iš jų;
Rodomos norimos būsenos;
atspindi automato perėjimų iš būsenos į būseną dinamiką ir sąlygas;
nesunkiai matote galimas dizaino klaidas, pvz., trūkstamas
tam tikras perėjimas, nepasiekiama būsena ir pan.
Visa tai leidžia aiškiai suprasti įrenginio veikimą. valdymo procesai,
dizainai gali būti pavaizduoti kaip elementai, kurių elgesys yra nuspėjamas.
Pavyzdys: vienas didžiausių pasaulyje aviacijos, kosmoso ir
karinė įranga– Amerikos korporacija „Boeing“ užsiima stabilizavimo sistemomis
orlaivių naudojant grynąją automatų teoriją. Dauguma automatų teorija
buvo sėkmingai naudojamas sistemos programose ir teksto filtruose UNIX OS.
Tai leidžia daugeliui žmonių dirbti aukšto lygio ir labai tobulėti
veiksmingos programos.
TA taikymo sritys yra įspūdingos savo apimtimi ir neapsiriboja siauromis
dėmesys ir specializacija. Panagrinėkime kai kuriuos iš jų.
Programavimas
Kyla klausimas, kodėl automatų teorijos baigtinių automatų modelis yra ypatingas
aktualu dabar, kai yra daug kalbų
programavimo ir programinės įrangos kūrimo aplinkos? Yra dvi problemos:
nenuspėjamas išskirtinai sukurtos programos kodo elgesys
RAD įrankiai (Rapid Application Development – greito kūrimo įrankiai
programos);
„programavimo kultūros“ „išblukimas“.
RAD pavyzdžiai: „Borland Delphi“ ir „C++“ pagreitintam kūrimui
taikomąsias programas naudojant objektinį ir vizualinį
programavimas. Jie leidžia ne tik programuoti įprasta to žodžio prasme,
bet ir iš tikrųjų piešti programas (ir sąsają, ir įgyvendinimą) naudojant
vaizdiniai VCL komponentai.
Bet kuris vizualinis VCL objektas pasižymi daugybe savybių, metodų ir įvykių.
Atrodytų, kad paprasčiausiai manipuliuojant išvardytais atributais galima priversti
kuriama programa, kad padarytų tai, ko iš jos reikalauja programuotojas kūrėjas. Bet
tai toli gražu nėra tiesa.
Jau seniai buvo aišku, kad VCL linkęs slėpti tikslų įgyvendinimą
objektus, taip užkertant kelią pašaliniams asmenims pakeisti numatytąją kodo elgseną. Kaip
praktika rodo, kad programos, sukurtos naudojant RAD priemones, kodo elgesys ne
visada nuspėjamas net labai patyrusiam programuotojui, jau nekalbant apie pradedančiajam.
Programa, nepaisant autoriaus kodo „akivaizdumo“, visada stengiasi eiti savo keliu.
būdu, patekti į tokius sudėtingus įvykių tvarkytojus, kurių egzistavimas
tu gali net neatspėti.
AT modernus pasaulis Kuriamų programų apimtis ir sudėtingumas didėja
kiekvieną dieną, todėl šis metodas žymiai padidina programinės įrangos testavimo ir derinimo laiką.
Automatų teorijos mechanizmas leidžia valdyti kodo elgesį.
prieš keturiasdešimt metų.
Programavimo stiliai skiriasi pagrindinėmis sąvokomis, kurios yra
vartojamos tokios sąvokos kaip „įvykis“, „paprogramė“, „funkcija“, „klasė“.
("objektas") ir tt Programavimo stilius, pagrįstas aiškiu būsenos paskirstymu
ir automatų naudojimas programų veikimui apibūdinti, vadinamas „automatiniu“.
programavimas“, ir atitinkamas programos dizaino stilius –
„automatizuotas dizainas“. Automatinis programavimas gali būti laikomas ne
tik kaip savarankiškas programavimo stilius, bet ir kaip priedas prie kitų
stilių, pavyzdžiui, į objektinį, nes Mes kalbame ne tik ir ne tiek
naudojant baigtinių būsenų mašinas programuojant, kiek apie kūrimo metodą
programas apskritai, kurių elgesį apibūdina automatai. Tie. kaip atskiras
komponentas, o visa programa gali būti įdiegta kaip automatas.
Yra dvi automatinio programavimo kryptys: SWITH technologija ir
KA (finite-automatic) technologija. Komutatorių technologija – sistemų kūrimo technologija
loginis valdymas, pagrįstas baigtiniais automatais, apimantis procesą
projektavimas, įgyvendinimas, derinimas, tikrinimas (patikrinimas), dokumentacija ir
palydos.
Automatų kodavimas/programavimas KA technologijos rėmuose remiasi
šiais principais:
supažindino su dinaminio objekto, kuriam gali būti suteiktas algoritmas, samprata
elgesys laikui bėgant;
objekto elgesio algoritmas pateikiamas baigtinio automato modeliu;
automato aprašymo kalba paremta automatų vaizdavimu lentelėje;
objekto elgesio logika (automatų perėjimo lentelė) atskirta nuo metodų
automato objektas (predikatai ir veiksmai), susiję su jo įgyvendinimu
elgesys laikui bėgant;
Lygiagrečiai gali būti vykdomi bet kokie dinaminiai objektai.
Pažvelkime į šias technologijas atidžiau:
1) SWITH technologija. Pagrindinės nuostatos: siūloma „valstybės“ sąvoką padaryti
pirminis, o algoritmai pateikiami pereinamųjų grafikų (būsenų diagramų) pavidalu, t.y.
vaizduoti programą kaip sąveikaujančių baigtinių automatų sistemą,
aprašyti pereinamaisiais grafikais. Būsenos yra užkoduotos, kad būtų galima jas atskirti.
Grafikai vaizdine forma žmogui atspindi perėjimus tarp būsenų, taip pat
„suriša“ išvesties veiksmus ir kitus automatus su būsenomis ir (arba) perėjimais.
Programos viduje automatai gali sąveikauti:
sudėjus lizdus (vienas automatas yra įdėtas į vieną ar kelias kito būsenas
mašina)
pagal iškviečiamumą (iš išvesties su tam tikru įvykiu iškviečiamas vienas automatas
įtaka, susidariusi perėjus kitam automatui)
pranešimų siuntimas (vienas automatas gauna pranešimus iš kito)
pagal būsenos numerius (vienas automatas patikrina, kokia būsena
kita mašina).
Neribojamas nei tam tikroje būsenoje įdėtų automatų skaičius, nei lizdo gylis.
Pagrindinis valdymo automatų optimalaus įgyvendinimo kriterijus yra galimybė
perėjimo grafiko konvertavimas į programos kodą.<><><>Žinomas didelis skaičius
įrankiai, skirti generuoti programas, kurios įgyvendina perėjimo grafikus:
Visio2Switch įrankis Visio2Switch leidžia grafiškai
perėjimai, sukurti naudojant „Microsoft Visio“ redaktorių automatiškai
įgyvendinti ją kaip izomorfinę C programą.Visio2Switch Converter
šiuo metu naudojamas kuriant programinę įrangą daugeliui
atsakingos realaus laiko sistemos.
MetaAuto MetaAuto įrankis leidžia, atsižvelgiant į perėjimo grafiką,
sukurtas naudojant tą patį redaktorių, automatiškai įdiekite jį formoje
izomorfinė programa bet kuria programavimo kalba, kuriai
iš anksto sukurtas šablonas (C, C#, Turbo Assembler ir kt.).
UniMod įrankis UniMod skirtas palaikyti
automatinis programavimas ir ne tik automatų, bet ir automatų konstravimas bei diegimas
programos apskritai.
Praktika parodė, kad daugeliui programų klasių programinės įrangos tik 20-30 proc
kodas kuriamas rankiniu būdu.
SWITCH technologijos pagrindu jau sukurtos aplikacijos: prekybos įrenginiams
sodos vanduo, bankomatas (žr. 1 pavyzdį), šviesoforai, valdymo sistemos
keleivinis liftas, automobilio signalizacijos valdymo sistema (žr. 2 pavyzdį),
automatizuota mokėjimo sistema Mobilusis telefonas, valiutos keitimo įrenginiai,
bilietų pardavimo įrenginiai ir kt.
2) KA technologija leidžia įgyvendinti lygiagretumo idėją. Plėtros technologijos
iš viršaus į apačią, iš apačios į viršų, struktūrinis požiūris į tokias galimybes ar ne
turi arba jie yra riboti. Net ir objektinėje technologijoje
programavimas (OOP), objektų lygiagrečio veikimo klausimai iš jo ribų išbraukiami.
Kitų technologijų, pagrįstų gerai žinomais lygiagrečiais modeliais, naudojimas,
yra kupinas sunkumų, susijusių, jei ne su jų taikymo srities apribojimais, tai
su vėlesnio diegimo programinės ir (arba) aparatinės įrangos lygiais problemomis.
Lygiagretūs modeliai yra viena iš pagrindinių ir perspektyvių plėtros sričių
programavimas ir techninė įranga. Lygiagretumo idėja yra labai patraukli. Bet
norint juo naudotis, būtina, pirma, išspręsti aprašymo problemą, t.y. pasirinkimas
formalus paralelinis modelis, ir, antra, modelio įgyvendinimo problema. KA
technologija naudoja modelį su lygiagretumo vaizdavimo ir aprašymo priemonėmis,
kurie savo galimybėmis nėra prastesni už kitus lygiagrečius modelius, o jos
įgyvendinti daug lengviau. Be to, naudojant standartinius metodus, tai lengva
pereiti nuo lygiagrečio baigtinio automato vaizdavimo į nuoseklųjį
apibūdinimas.
KA technologijos taikymo pavyzdžiai: skaičiavimo tipo apskaitos programos
darbo užmokesčio arba nuomos apskaita, projektų valdymo sistema
technologinis kristalų auginimo procesas su daugeliu dinamiškai
generuojami lygiagrečiai veikiančiuose objektuose, kurie įgyvendina pašalinimo procesus
duomenys iš jutiklių, valdymo veiksmų suteikimas objektui, automatų algoritmai
vairuotojų darbas su įvairia įranga, rodymo ir skaičiavimo procesai.
3) Pagrindinis skirtumas tarp nagrinėjamų technologijų yra logikos įgyvendinimas
automatines programas. SWITCH technologijoje jis įgyvendinamas perkeliant automatinį
aprašymai programavimo kalbos programiniame kode, KA yra įdiegta technologija
tiesioginis automatų vykdymas, interpretuojant jo pirminę lentelę
atstovavimas. Tai trumpesnis ir aiškesnis automatų diegimo būdas, nors ir daugiau
lėtas, jei atsižvelgsime į atskiro tinklo komponento automato lygį
mašinos.
Išvada: šiuo metu naudojamas automatinis programavimas
kritinių objektų automatizavimo sistemų programinės įrangos projektavimas
valdymas (automatinis kriogeninio-vakuuminio bloko valdymas, dyzelinis generatorius).
Valstybės mašina veikia principu „žingsnis į šoną – nepriimtina“. Įgyvendinti
būsenos mašina neduos vartotojui nenumatytų veiksmų (originalas
kodo variantas), nei pati programa (modifikuotas kodo variantas).
Šiuo metu kompiuterinių žaidimų kūrimo srityje jaučiamas bumas. Dažniau
žaidimo valdymo logika, kuria gali žaisti žaidimo srityje judantys personažai
veikti įvairiais režimais (pavyzdžiui, veikėjas bėga pirmyn arba atgal, lipa
laiptai, kritimai ir pan.) yra įgyvendinama kaip valstybės mašina.
Diskretinės matematikos ir programavimo algoritmų vizualizatorių diegimas
Tiriant informacijos apdorojimo algoritmus, atstovaujamus įvairiems
duomenų struktūras, svarbų vaidmenį atlieka algoritmų vizualizatoriai, leidžiantys
vaizdinė forma dinamiškai parodo savo darbo detales.
Vizualizatorius yra programa, kuri savo veikimo metu yra kompiuterio ekrane
dinamiškai demonstruoja algoritmo pritaikymą pasirinktam duomenų rinkiniui.
Vizualizatoriai leidžia tyrinėti algoritmų veikimą žingsnis po žingsnio režimu, panašiu į
programos sekimo režimas. Jie leidžia atsekti, jei reikia.
išplėsti žingsniai, ignoruojant įprastą skaičiavimo proceso dalį, kuri
būtini, pavyzdžiui, surašymo algoritmams.
Kai kuriems algoritmams yra dinaminė jo darbo demonstravimo versija
natūraliau nei statiškų iliustracijų rinkinys.
Mokant daugumą algoritmų, kartu su „žingsnio į priekį“ režimu, tai labai naudinga
taip pat „žingsnio atgal“ režimas, leidžiantis greičiau ir visapusiškai suprasti algoritmą.
Pavyzdžiui, naudojant atgalinio sekimo algoritmus gali prireikti atlikti kelis veiksmus
atgal, kad suprastų, kodėl buvo atmesta ta ar kita paieškos atšaka.
Vizualizatorių pavyzdžiai: dvejetainio medžio perėjimas, planavimo algoritmai,
rūšiavimas ir kt. Tie. sudėtingi algoritmai su daugybe perėjimų, sąlygų ir
šakas galima pavaizduoti kompaktiškiau ir aiškiau: baigtinio automato pavidalu su
nuspėjamas ir matomas elgesys.
Dirbtinis intelektas
Dirbtiniai neuroniniai tinklai (ANN) – matematiniai modeliai, taip pat jų programinė įranga
arba techninės įrangos diegimai, sukurti organizacijos ir veikimo principu
biologiniai neuroniniai tinklai – gyvo organizmo nervinių ląstelių tinklai. Ši sąvoka
atsirado tiriant smegenyse vykstančius procesus ir bandant juos modeliuoti
procesus.
Neuroniniai tinklai yra išskirtinai galinga modeliavimo technika, leidžianti
atkurti itin sudėtingas priklausomybes. ANN yra konfigūruojami ir
mokymasis. Automatų naudojimas dirbtiniams neuroniniams tinklams kurti
leidžia neįtraukti nenumatytų būsenų darbe.
Neuroninės technologijos ypač intensyviai naudojamos ekspertinėse sistemose.
indėlių ir finansinių reikalų prognozavimas vertinant investicijas.
Pavyzdys: skystųjų raketų varikliuose (LRE), kurie yra sudėtingi
techninė sistema, susidedanti iš daugelio tarpusavyje sąveikaujančių vienetų
pati, būtina greita valdymo sistemos reakcija į vykstančius procesus.
viename iš kritiškiausių ir labiausiai įtemptų agregatų – turbosiurblio bloke
(TNA). Naudojant neuroninius tinklus ir automatus, tai tampa įmanoma
ankstyva ekstremaliųjų situacijų diagnostika, o tai sumažina avarijos pasekmes
ir užkirsti kelią variklio sunaikinimui atliekant gaisro bandymus (žr. 3 pavyzdį).
Kai veikia, TNA vaizduojama kaip baigtinės būsenos mašina. valstijos, in
kuris gali būti: budėjimo režimas, paleidimas, pagrindinis režimas, sustabdymas, avarinis režimas
būsena (suskirstyta į daugybę būsenų, klasifikuojančių gedimo pobūdį).
Ribinio nuokrypio reikšmė parenkama taip, kad būtų
minimalus ir tuo pačiu leidžiantis nedidelius variantus. Atsisakymo atveju (išeiti
bet kuris iš keturių tinklų yra lygus vienetui), neuroniniai tinklai treniruojami
būdingas TNA gedimams, pagal kurių parodymus galima nustatyti, kas tarnavo
gedimo priežastis (tinklo išvestis lygi vienetui). Jei tai nepavyksta (keli
tinklo išėjimai yra lygūs vienetui), tada laikoma, kad gedimas sujungiamas – tuo pačiu metu
buvo keletas gedimų, o esant netikrumui (visi tinklo išėjimai yra vienodi
nulis), įrenginys persijungia į Naujo gedimo būseną.
Sukurta technika leidžia aptikti turbosiurblio bloko gedimus. Nes
šis prietaisas yra labai sudėtingas, tada po avarinės situacijos
sunku nustatyti gedimo tipą, kokioje darbo būsenoje šiuo metu
įrenginio vieta ir kaip jį grąžinti į darbinę būklę. Neuroninis tinklas
leidžia išvengti avarijos arba nustato laiką, kada įvyko gedimas, ir
nustato gedimo tipą. SWITCH technologijos taikymas kuriant valdymą
Programinė įranga leidžia gauti visą diagnostikos mašinos veikimo protokolą - bet kuriuo metu
jos veikimo metu galite sužinoti, kokios būklės ir kokios yra mašina
jos būsena gali būti išversta.
Programinės įrangos kūrimas mobiliuosius įrenginius ir mikrovaldikliai
Kuriant serverio programas, kurios reaguoja į užklausas, svarbų vaidmenį atlieka
„be pilietybės“ – nebūtina saugoti būsenų tarp dviejų
nuoseklūs prašymai.
Kuriant sėkmingą interaktyvią įvykiais pagrįstą programą, daug
priklauso nuo to, ar gerai apgalvotas valstybės valdymo modelis.
Valstybės mašina yra labai patogi koncepcija, kuri yra naudinga
struktūrizavimo programos.
Nes mobiliosios programos turėtų naudoti ekrano erdvę ir sistemą
išteklius efektyviai, būsenos mašinos ypač naudingos, kai
programinės įrangos kūrimas tokioms programoms.
Programa yra baigtinių sąveikaujančių automatų rinkinys
tarpusavyje ir su išoriniu pasauliu. KA perėjimo diagramoje aprašomi perėjimai tarp
ekrano formos, perėjimo lankai iš būsenos į būseną aprašo veiksmus
Vartotojas. Kiekviena sukonstruota forma turi būti susieta su būsenos mašina,
kontroliuojantis vizualinį formos elgesį. Jei pačioje formoje yra keletas
puslapiuose, pavyzdžiui, dialogo languose su skirtukais, tada jis pateikiamas kiekvienam iš jų
subpuslapiai savo būsenos mašiną.
Būsenos mašinos labai pagerina vykdymo kontrolę
fono užduotis. Jų naudojimas leidžia sukurti fono gijas
informacija apie vykdymo būklę, taip pat kitų gijų kreipimasis su prašymais į
fono giją tam tikriems veiksmams atlikti, pavyzdžiui, su užklausa
nustokite vykdyti foninį darbą. Tuo pačiu vaizdine grafine forma
tiek jungtys tarp automatų ir jų vidinių
struktūra. Pagrindinis privalumas: daugkartinis kodo naudojimas, greitas
modifikavimas, matomumas, kuris yra svarbus mobiliųjų įrenginių programoms,
reikalaujantis taupiai išnaudoti ekrano erdvę, atmintį, kompiuteriją
galia ir kiti ištekliai.
Darbo eigos modelių kūrimas remiantis baigtinio automato teorijos modeliu
kulkosvaidis
Šiuolaikinėje visuomenėje vyksta skaičiavimo intensyvėjimo procesas ir
informacines technologijas visose veiklos šakose.
Dokumentų srautas – dokumentų judėjimas organizacijoje nuo jų sukūrimo momento arba
gavimas prieš užbaigiant vykdymą: siuntimas ir (arba) siuntimas į bylą. Įgyvendinimas
elektroninis dokumentų valdymas yra neatidėliotinas uždavinys šiuolaikinė visuomenė, nes
tai leidžia padaryti dokumentų judėjimo procesą valdomą ir kontroliuojamą, o tai
teikia geresnes valdymo paslaugas. Įmonės ir organizacijos, skirtos
Šios problemos sprendimas reikalauja daug laiko ir pinigų. Tuo pačiu metu kiekvienas
dokumentų valdymo sistemos kūrimas yra unikalus ir galimybė pakartoti
praktiškai nenaudojama visa įgyta patirtis. Teisingai
šio proceso organizavimas lemia bet kurio darbo kokybę ir stabilumą
įmonių.
Naudojant automato modelį kuriant dokumentų srautų specifikacijas ir
programinės įrangos produktas leidžia sukurti sistemas, labiau atitinkančias reikalavimus
vartotojų ir suteikia galimybę pasiekti programų suderinamumą.
Automatų teorija leidžia įgyvendinti dokumentų judėjimo šakojimo tarp logiką
dokumentų valdymo procesų dalyviai. Aparatas leidžia nustatyti reakciją
darbo eigos sistemos elementai sistemos pokyčiams.
Sumodeliuotu objektu laikomas vadinamasis sudėtinis objektas.
dokumentų srautas, tai yra toks dokumentų srautas, kuriame jie dalyvauja, tiek elektroninis,
taip pat popieriniai pareiškimai. Sudėtinė darbo eiga
pavaizduotas trigubu: Dm = (U, D, F), kur
Дт – formalus darbo eigos modelis;
Y – dalyvių rinkinys;
D – veiksmų rinkinys;
F – dokumento būsenų rinkinys.
Dokumento būsenų rinkinys S gaunamas analizuojant gyvavimo ciklą
dokumentas. Tai visų būsenų, kurias gali priimti dokumentas, rinkinys
modeliuojamoje darbo eigoje, kur kiekviena reikšmė yra unikali: (S)=(Ф).
Pradinė būsena yra pradinė būsena, į kurią patenka
dokumentas po proceso inicijavimo. Pateikiant dokumento srautą formoje
procesų rinkinys, pradinė būsena yra pirmasis žingsnis, po kurio
galime sakyti, kad dokumentas egzistuoja ir procesas suaktyvintas. Šiuo būdu,
pradinės būsenos – tai objektai, aibės Ф elementai, turintys vieną arba
keli išeinantys ryšiai ir nė vieno įeinančio.
Darbo eiga susideda iš procesų rinkinio, kurių kiekvienas vyksta
vieną ar daugiau dokumentų. Darbo eigos proceso gyvavimo ciklas
yra nulemtas dokumentų judėjimo iš pradinių būsenų į galutines būsenas.
Nagrinėjamame modelyje galutinės automato būsenos apibrėžiamos kaip būsenos
dokumentus, kuriems atsiradus mašinos veikimas sustoja, t.y.
darbo eiga nustoja egzistuoti. Taigi, finalas
būsenas galima apibrėžti kaip aibės Ф objektus, kurie turi vieną arba
keli įeinantys ryšiai ir nė vienas išeinantis.
Darbo eigoje dokumentas įgauna tokią būseną, priklausomai nuo
su juo atliktų veiksmų rezultatas. automatinio perėjimo funkcija
darbo eigos modelius galima apibrėžti kaip i-tąjį veiksmų rinkinio elementą (D)
darbo eiga, po kurios būsena pasikeičia į
sąlyga. (F) = (D)
Automato abėcėlė yra simbolių rinkinys, kurio rinkiniai ateina arba gali
veikti automatiškai. Kaip automato abėcėlę, reikėtų atsižvelgti į sąrašą
dalyvių.
Galima vienareikšmiškai apibrėžti automatą, kuris tinkamai įgyvendins modelį
darbo eiga. Deterministinių automatų pagrindu sukurtas modelis leidžia
kurti modelius, kuriuos lengviau suvokti vizualiai. Jiems lengviau statyti
programinės įrangos diegimas. Tuo pačiu metu kuriant proceso modelius, kurie turi
sudėtinga išsišakojusi struktūra, automato modelis deterministiniuose automatuose
jis tampa didelis ir masyvus.
Nedeterministiniai automatai leidžia nurodyti sudėtingus procesus naudojant
mažiau aprašomosios medžiagos. Tačiau aiškumo dėlei jie
daug sunkiau.
Išvada: mažiems, šiek tiek šakotiems procesams geriau naudoti
deterministiniai automatai, o nedeterministiniai yra patogesni
nurodant procesus su daugybe žingsnių ir atšakų.
Sukūrus teorinę bazę, įdiegiama programinė įranga,
taikant praktikoje automatinius ir grafinius darbo eigos modelius. Kiekvienas iš
dalyviai turi galimybę pasiekti tam tikrų tipų dokumentus ir
atlikti su jais griežtai apibrėžtus veiksmus.
Sudėtinių darbo eigos sistemų įdiegimas leidžia dirbti biure
skaidresnis ir nuspėjamas, mažina asmeninę atlikėjo įtaką
darbuotojai už galutinį rezultatą.
Nagrinėjama pramonė šiuo metu sparčiai vystosi. Toliau
šios krypties tyrimai, ypač kalbant apie CSgrammatics naudojimą ir
sukurti programinę įrangą, kuri įgyvendina aprašytą automato modelį
visa sudėtinė darbo eiga.
Eilučių paieška tekste
Remiantis oficialia statistika, apie 85% interneto vartotojų nuolat
susisiekite su paieškos sistemomis
(„Google“, „Yandex“, „Rambler“, „Yahoo!“, „Aport“, „[email protected]“ ir kt.), kad surastumėte
jiems reikalingos informacijos apie prekes ar paslaugas.
Automatų teorijos nuostatos puikiai tinka tokiai realybei apibūdinti
užduotys, atsirandančios programose, pvz., paieška internete ir ištraukimas
informacija iš teksto. Daugelis šiuolaikinių paieškos sistemos Interneto naudojimas
speciali programa- paieškos robotas, kuris yra automatas.
Interneto amžiuje ir skaitmenines bibliotekas su nuolatine prieiga įprasta yra
kita problema. Jums duotas žodžių rinkinys ir norite juos rasti
dokumentai, kuriuose yra vienas (arba visi) iš jų. Populiarus tokio pavyzdys
procesas yra paieškos sistemos, kuri naudoja specialią technologiją, darbas
paieška, vadinama atvirkštiniais indeksais (apverstais indeksais). Už kiekvieną žodį
rasti internete (o jų yra apie 100 000 000), visų vietų, kur
tai susitinka. Mašinos su labai dideliu kiekiu RAM suteikia
nuolatinė prieiga prie labiausiai pageidaujamų sąrašų, leidžianti daugeliui žmonių
vienu metu ieškoti dokumentų.
Atvirkštinio indekso metodas naudoja ne būsenos mašinas, o šį metodą
Nukopijuoti ir perrašyti tinklo turinį užtrunka daug laiko
indeksai. Yra daug susijusių programų, kuriose taikoma technika
atvirkštiniai indeksai neįmanomi, tačiau galite sėkmingai naudoti metodus, pagrįstus
mašinos. Tos programos, kurioms tinka automatinė paieškos technologija,
turi šias išskirtines savybes:
1. Ieškomas tekstų parduotuvės turinys yra greitas
keičiasi.
Štai du pavyzdžiai:
o kiekvieną dieną analitikai ieško straipsnių su naujausiomis naujienomis
aktualiomis temomis. Pavyzdžiui, finansų analitikas gali ieškoti
straipsniai su tam tikromis santrumpos vertingų popierių arba vardai
įmonės;
o „robotas pirkėjas“ kliento pageidavimu stebi esamas kainas
tam tikrų produktų pavadinimų. Jis nuskaito puslapius iš žiniatinklio,
su katalogais, tada nuskaito tuos puslapius, kurių ieško
konkrečios prekės kainos informacija.
2. Ieškomi dokumentai negali būti kataloguojami.
Pavyzdžiui, labai sunku internete rasti visus puslapius, kuriuose yra informacijos apie
visų Amazon.com parduodamų knygų, nes šie puslapiai
yra generuojami tarsi „kelyje“ atsakant į užklausą. Tačiau užklausą galime išsiųsti el
knygas konkrečia tema, pasakykite „valstybės mašinos“ ir ieškokite toje dalyje
tekstas, esantis pasirodžiusiuose puslapiuose, pvz., tam tikras žodis
žodis „gražus“.
ATM veikimo modeliavimas
Bankomatas yra automatizuotas įrenginys, leidžiantis atlikti nuotoliniu būdu
operacijos, susijusios su vartotojo autentifikavimu (banko sąskaitos turėtojas),
esamos sąskaitos būklės peržiūra, pinigų išėmimas iš sąskaitos ir uždirbimas
įvairūs mokėjimai. Šiame pavyzdyje nagrinėjamas bankomato veikimas, įskaitant
tik kliento dalis, bet ir serverio dalis, kuri apdoroja užklausas, taip pat
leidimų posistemis.
Pagrindinis uždavinys diegiant tokias sistemas yra garantija aukštas lygis patikimumas
klientų, banko vartotojų ir banko informacinės sistemos.
Nepaisant ryšio tarp automatų trūkumo, AServer yra įdėtas į AClient. At
kai AKliento automatas yra būsenose „Įgaliojimas“, „Balanso užklausa“ ir
„Pinigų prašymas“ programos valdymas perkeliamas į mašiną AServer , kuri
siunčia užklausą į serverį, gauna atsakymą ir grąžina valdymą mašinai
AClient. Pats serveris sukurtas tradiciniu būdu ir įgyvendintas kaip
konsolės programa.
Programos sąsaja:
Pavyzdys rodo, kad UniMod įrankis supaprastina procesą
sukurti programą, palyginti su tradiciniu požiūriu. Tuo pačiu metu dauguma
Kūrėjo laikas skiriamas sistemos projektavimui. Nuo pagrindinės dalies
kodas generuojamas automatiškai, padidinamas programos patikimumas.
Automobilio signalizacijos valdymo sistemos priekiniai žibintai, sirena ir LED kaip valdymo objektai. Naudojant sudėtingą būseną
"2. Įjungta“ (yra 3 būsenos) suteikia galimybę išjungti
nesvarbu, kokioje būsenoje yra mašina.
Sistemos įvykių generatoriai
Įvykių generatorius p1. Šis objektas apibūdina konsolės sukurtus įvykius.
signalizacijos valdymas. Pokyčiai:
e11 - mygtuko "1" paspaudimas;
e12 - mygtuko "2" paspaudimas;
e13 - paspaudus mygtuką "3".
p2 įvykių generatorius. Šis objektas atitinka smūgio jutiklį. Jis gali išduoti du
įvykiai:
e21 - silpno smūgio fiksavimas;
e22 – stipraus smūgio fiksavimas.
p3 įvykių generatorius. Šis objektas paleidžia vieną iš trijų laikmačių. Kai atgalinis skaičiavimas
užbaigia, sugeneruoja atitinkamą įvykį. Laikmatis paleidžiamas paprašius
valdymo objektas „o2“, nurodantis numerį ir reikiamą laiką.
e31 - laikmatis "1" baigė skaičiuoti (laikmatis skaičiuoja laiką būsenoje "3.
aliarmas“ mašinos A1);
e32 - laikmatis "2" baigė skaičiuoti (laikmatis skaičiuoja laiką būsenoje "2.
Pavojaus būsena“ mašinos A1);
• e33 - laikmatis "3" baigė skaičiuoti (laikmatis nutildymo valdymui).
Sistemos valdymo objektai
Valdymo objektas o1. Šis objektas apibūdina priekinių žibintų atliekamus veiksmus
automobilis.
z1 – sumirksi vieną kartą;
• z2 – mirksėti du kartus;
• z3 – sumirksi tris kartus;
z5 – nutraukti bet kokį veiksmą.
Valdymo objektas o2. Šis objektas naudojamas „p3“ laikmačiui paleisti.
z1 – paleisti laikmatį "1" 15 s;
z2 – paleisti laikmatį "2" 5 s;
z3 – paleisti laikmatį "3" 3 s;
z4 - sustabdyti visus laikmačius.
Valdymo objektas o3. Šis valdymo objektas atspindi sirenos veikimą. Jo
išėjimo veiksmai beveik sutampa su priekinių žibintų išėjimo veiksmais.
x1 yra loginis kintamasis, nurodantis, kad garsas įjungtas (ty gali
signalai) ar ne;
z1 – garso generavimas, atitinkantis automobilio įjungimą į signalizaciją;
z2 – garso generavimas, atitinkantis automobilio išėmimą iš signalizacijos;
z3 – garso generavimas, atitinkantis reakciją į silpną smūgį;
z4 – pradeda duoti pavojaus signalą;
z5 - nutraukti garsą;
z6 – įjungti garsą (leisti duoti signalus);
• z7 – išjungti garsą (uždrausti duoti signalus).
Valdymo objektas o4. Šis valdymo objektas apibūdina šviesos diodo veikimą,
esantis automobilyje. Rodo esamą aliarmo būseną.
z1 – pradeda mirksėti;
z2 – nustoti mirksėti.
Valdymo objektas o5. Šis valdymo objektas naudojamas išvesti
Automatų teorija
Automatų teorija- diskrečiosios matematikos skyrius, studijuojantis abstrakčiuosius automatus - kompiuterius, pateiktus matematinių modelių pavidalu - ir problemas, kurias jie gali išspręsti.
Automatų teorija glaudžiausiai susijusi su algoritmų teorija: automatas diskrečią informaciją paverčia žingsniais į atskirus laiko momentus, o rezultatą formuoja duoto algoritmo žingsneliais.
Terminija
Simbolis- bet koks atominis duomenų blokas, galintis turėti įtakos mašinai. Dažniausiai simbolis yra raidė bendrine kalba, tačiau tai gali būti, pavyzdžiui, grafinis diagramos elementas.
- Žodis- simbolių eilutė, sukurta sujungimo (sujungimo) būdu.
- Abėcėlė- baigtinis skirtingų simbolių rinkinys (daug simbolių)
- Kalba- žodžių rinkinys, sudarytas iš nurodytos abėcėlės simbolių. Gali būti baigtinis arba begalinis.
Sakoma, kad kalba yra L perskaityta (gauta) automatu M, jei jį sudaro žodžiai w pagal abėcėlę taip, kad jei šie žodžiai įvedami į M, apdorojimo pabaigoje jis patenka į vieną iš priimančių būsenų F:
Paprastai automatas pereina iš būsenos į būseną naudodamas perėjimo funkciją, skaitydamas vieną simbolį iš įvesties. Taip pat yra automatų, kurie gali pereiti į naują būseną neskaitydami simbolio. Šuolio funkcija neskaitant simbolio vadinama - perėjimas(epsilono perėjimas).
Taikymas
Praktikoje automatų teorija naudojama kuriant formaliųjų kalbų (įskaitant programavimo kalbas) lekserius ir analizatorius, taip pat kuriant kompiliatorius ir kuriant pačias programavimo kalbas.
Kitas svarbus automatų teorijos pritaikymas yra matematiškai griežtas problemų sprendžiamumo ir sudėtingumo nustatymas.
Tipiškos užduotys
- Automatų konstravimas ir minimizavimas- abstraktaus automato sukūrimas iš tam tikros klasės, kuris išsprendžia duotą problemą (priima tam tikrą kalbą), galbūt vėliau sumažinant būsenų skaičių arba perėjimų skaičių.
- Automatų sintezė- sistemos sukūrimas iš duotų "elementarių automatų", lygiaverčių tam tikram automatui. Toks automatas vadinamas struktūrinės. Jis naudojamas, pavyzdžiui, skaitmeninių elektros grandinių sintezei tam tikro elemento bazėje.
taip pat žr
Literatūra
- Johnas Hopcroftas, Rajeevas Motwani, Jeffrey UllmanasĮvadas į automatų teoriją, kalbas ir skaičiavimą. - M .: Williams, 2002. - S. 528. - ISBN 0-201-44124-1
- Kasjanovas V. N. Paskaitos apie formaliųjų kalbų teoriją, automatus ir skaičiavimo sudėtingumą. - Novosibirskas: NSU, 1995. - C. 112.
Nuorodos
Wikimedia fondas. 2010 m.
- Azijos futbolo konfederacija
- Skaičiavimo sudėtingumo teorija
Pažiūrėkite, kas yra „Automatų teorija“ kituose žodynuose:
Automatų teorija
Automatų teorija- teorinės kibernetikos skyrius, tiriantis realių ar galimų įrenginių, kurie diskrečią informaciją apdoroja diskrečiaisiais ciklais, matematinius modelius (čia vadinamus automatais arba mašinomis). Pagrindinis ... ... Ekonomikos ir matematikos žodynas
automatų teorija– Teorinės kibernetikos šaka, tirianti realių ar galimų įrenginių, kurie diskrečią informaciją apdoroja diskrečiaisiais ciklais, matematinius modelius (čia vadinami automatais arba mašinomis). Pagrindinės šios teorijos sąvokos ...... Techninis vertėjo vadovas
automatų teorija- daiktavardis, sinonimų skaičius: 1 tavt (1) ASIS Sinonimų žodynas. V.N. Trišinas. 2013... Sinonimų žodynas
automatų teorija- automatų teorija statusas T sritis automatika atitikmenys: angl. automato teorija vok. Automatenteorija, f rus. automatų teorija, f pranc. theorie des automates, f … Automatikos terminų žodynas
Būsenos diagrama (automato teorija)- Šis terminas turi kitas reikšmes, žr. būsenos diagramą. Būsenos diagrama yra nukreiptas baigtinio automato grafikas, kuriame viršūnės rodo lanko būsenas, rodo perėjimus tarp dviejų būsenų Praktikoje ... ... Vikipedija
Mechanizmų ir mašinų teorija- Mašinų ir mechanizmų teorija (TMM) – tai mokslinė disciplina apie bendruosius mechanizmų ir mašinų tyrimo metodus, konstravimą, kinematiką ir dinamiką bei mokslinius jų projektavimo pagrindus. Turinys 1 Drausmės raidos istorija 2 Pagrindinės sąvokos ... Vikipedija
TEORIJA- (1) mokslinių idėjų ir principų sistema, apibendrinanti praktinę patirtį, atspindinti objektyvius prigimtinius dėsnius ir reguliavimus, kurie sudaro (žr.) arba bet kurio mokslo dalį, taip pat taisyklių rinkinį bet kokios rūšies žinių srityje mln. ... ... Didžioji politechnikos enciklopedija
Algoritmų teorija Ekonomikos ir matematikos žodynas
Algoritmų teorija– matematikos šaka, tirianti bendrąsias algoritmų savybes. Algoritmo su tam tikromis savybėmis konstravimo problema vadinama algoritmine problema, jos neišsprendžiamumas reiškia tinkamo algoritmo nebuvimą; jei…… Ekonomikos ir matematikos žodynas
Knygos
- Automatų teorija. Vadovėlis bakalauro ir magistrantūros studijoms, Kudryavtsev V.B. Vadovėlyje yra daug medžiagos apie automatų teoriją. Jame pristatoma automato sąvoka, pateikiamos teorijos ...
Vyatkos valstybinis universitetas
AUTOMATIKOS IR SKAIČIAVIMO INŽINERIJOS FAKULTETAS
Elektroninių kompiuterių katedra
Automatų teorija (I dalis) Paskaitų konspektas
Automatų teorija (I dalis). Paskaitų konspektas /Kirov, Vyatsky Valstijos universitetas, 2010, 56s.
Kurso „Automatų teorija“ (I dalis) paskaitų konspektuose pateikiama reikiama teorinė medžiaga, apimanti taikomosios skaitmeninių automatų teorijos pagrindus, pagrindinius abstrakčių baigtinių automatų, diskrečiųjų automatų grandinės apibrėžimus ir sintezės taisykles. konverteris V.M. Gluškovas ir trys pagrindiniai baigtinių automatų modeliai: Mealy modelis, Moore modelis ir C automato modelis. Toliau aptariame atminties elementų kodavimo metodus, automatų sumažinimą naudojant atmintį ir kanoninį struktūrinių automatų sintezės metodą. Ypatingas dėmesys skiriamas optimalios automato kombinacinės schemos konstravimo taisyklėms pagal kanonines lygtis, atsižvelgiant į pasirinktus atminties elementus. Nurodyta atitinkama literatūra.
Paskaitų kursas skirtas 230101 – „Kompiuteriai, kompleksai, sistemos ir tinklai“ specialybės dieninių studijų studentams, taip pat krypties 230100.62 – „Kompiuterija ir kompiuterinės technologijos“ bakalaurams.
Sudarė: Ph.D., katedros docentas. Kompiuteris V.Yu. Melcovas.
Vyatkos valstybinis universitetas, 2010 m
Meltsovas V. Ju.
1. Įvadas 4
2. Analizės ir sintezės problemos 4
3. Abstraktaus valdymo automatas 7
4. Abstrakčių automatų sintezė 9
5. Sinchroninė mašina 10
6. Asinchroninės mašinos 11
7. Mealy ir Moore mašinos 12
8. Automatų nustatymo būdai 14
8.1 Lentelinis automatų nurodymo būdas 15
8.2. Automato nustatymas naudojant 17 stulpelį
8.3. Matricinis automatų nurodymo metodas 19
9. Perėjimas nuo Mealy mašinos prie Moore mašinos ir atvirkščiai 19
10. Automatų sintezės etapai 23
11. Automato vidinių būsenų skaičiaus sumažinimas 26
12. Visiškai apibrėžtų automatų sumažinimas. 27
13. Kombinuotas automato modelis (C-automatas) 31
14. Struktūrinė automato sintezė 32
14.1. Kanoninis automato struktūrinės sintezės metodas 32
14.2. Struktūrinė C automato sintezė 35
15. Automato būsenų kodavimas 41
15.1. Automato būsenų kodavimo prieš lenktynes metodas 42
15.2. Kaimyninis automato būsenų kodavimas 45
15.3. Kodavimo automato būsenos, siekiant sumažinti kombinuotą grandinę 47
16. Elementariosios atminties automatai 50
17. Automatų sintezė PLM ir ROM 54
1. Įvadas
Pastaraisiais metais itin intensyviai vykdomi įvairių automatinių informacijos apdorojimo sistemų kūrimo ir taikymo tyrimai bei darbai. Tokios sistemos dažniausiai diegiamos blokų pavidalu, kurie sudaro informacijos valdymo ir apdorojimo sistemą. Atsižvelgiant į tai, atsirado nauja mokslo disciplina, kuri vadinosi „Sistemų teorija“.
Sistemų teorijos tikslas – sukurti idėjų ir priemonių arsenalą, kuris būtų vienodai naudingas įvairių sričių (elektros inžinerijos, mechanikos, fizikos, chemijos, sociologijos ir kt.) specialistams. Šis tikslas pasiekiamas nagrinėjant sistemą ne per jos vidinę struktūrą, o per matematinius dėsnius, lemiančius jos stebimą elgesį. Šiuo atveju dažniausiai naudojamas metodas vadinamas „juodosios dėžės“ metodu (t. y. metodu, kai analizuojami įvesties duomenys ir mašinos išvestyje gauti duomenys, neatsižvelgiant į vidinius procesus). Įrodyta, kad visas sistemas galima apibūdinti tais pačiais terminais ir analizuoti naudojant tą patį taisyklių rinkinį.
Neatsiejama sistemų teorijos dalis yra automatų teorija. Jame nagrinėjami matematiniai modeliai, skirti daugiau ar mažiau apytiksliai parodyti fizikinius reiškinius. Automatų teorijos modelio taikymas neapsiriboja jokia konkrečia sritimi, bet gali išspręsti beveik bet kurios studijų srities problemas.
sąveikaujančių procesų sistemų tikrinimas;Tai galima spręsti iš mokslininkų ir specialistų pranešimų seminare „Programinė įranga 2000...“.
Dougas Rossas: "...80 ar net 90% kompiuterių mokslo (Computer Science) ateityje bus paremta baigtinių automatų teorija..."
Herveris Gallaire'as: "Žinau, kad "Boeing" žmonės dirba su orlaivių stabilizavimo sistemomis, naudojant gryną automatų teoriją. Sunku įsivaizduoti, ką jie padarė su šia teorija."
Brianas Randelas: „Dauguma automatų teorijos buvo sėkmingai panaudota sistemos programos ir teksto filtrai UNIX OS. Tai leidžia daugybei žmonių dirbti aukštu lygiu ir kurti labai veiksmingas programas.
1.1. Pagrindinės sąvokos ir apibrėžimai.
Paprasčiausias informacijos keitiklis (1.1 pav., a) atvaizduoja tam tikrą informacijos elementų rinkinį Xincoming į įėjimą į tam tikrą rinkinį išėjime Y. Jei aibės X ir Y yra baigtinės ir diskrečios, tai yra, transformacija vykdoma diskrečiu laiku, tai tokie informacijos keitikliai vadinami baigtiniais keitikliais. Nustatykite elementus X ir Y šiuo atveju yra iš anksto užkoduoti dvejetainiais kodais ir sukuriama vienos rinkinio transformacija į kitą.
Transformacijos rezultatas dažnai priklauso ne tik nuo to, kokia informacija šiuo metu pasirodė įvedime, bet ir nuo to, kas įvyko anksčiau, tai yra nuo transformacijos istorijos. Pavyzdžiui, tas pats indėlis – kaimyno atsiprašymas po to, kai sausakimšame autobuse jis užlipo tau ant kojos – pirmą kartą sukels vienokią reakciją, o penktą – visiškai kitokią.
Ryžiai. 1.1.
Taigi yra sudėtingesnių informacijos transformatorių (IT), kurių atsakas priklauso ne tik nuo įvesties signalų šiuo metu, bet ir nuo to, kas vyko anksčiau, nuo įvesties istorijos. Tokie PI vadinami automatais (atminties grandinėmis). Šiuo atveju kalbama apie automatinį informacijos transformavimą (1.1 pav., b). Automatas gali skirtingai reaguoti į tą patį įvesties signalą, priklausomai nuo būsenos, kurioje jis buvo. Automatas keičia savo būseną su kiekvienu įvesties signalu.
Pažvelkime į keletą pavyzdžių.
1 pavyzdys 1 Karpovas Yu.G. Automatų teorija-Sankt Peterburgas: Sankt Peterburgas, 2003 m. Automatas, apibūdinantis „protingo“ tėvo elgesį.
Apibūdinkime, kaip elgiasi tėvas, kurio sūnus eina į mokyklą ir atneša dvejetus ir penketukus. Tėvas nesinori kiekvieną kartą griebtis diržo, vos tik sūnus gauna dvikovą, ir pasirenka subtilesnę auklėjimo taktiką. Tokį automatą apibrėžiame grafiku, kuriame viršūnės atitinka būsenas, o lankas iš būsenos s į būseną q, pažymėtas x/y, nubrėžiamas, kai automatas iš būsenos s, veikiamas įvesties signalo x, pereina į būseną. q su išvesties reakcija y. Išmanųjį tėvų elgesį imituojančio automato grafikas parodytas 1.2 pav. Šis automatas turi keturias būsenas 
, du įvesties signalai – įvertinimai ir išvesties signalai , kuriuos interpretuosime kaip pirminio veiksmus taip:
Paimkite diržą;
barti sūnų;
Nuramink sūnų;
viltis;
džiaugtis;
Džiaukis.
Ryžiai. 1.2.
Sūnus, gavęs tą patį pažymį – dvikovą, namuose tikisi visai kitokios tėvo reakcijos, priklausomai nuo studijų fono. Pvz., po trečio dvikovo istorijoje sūnus bus pasveikintas diržu, o istorijoje bus nuramintas ir t.t.
Būsenos mašina gali būti įdiegta tiek programinėje, tiek techninėje įrangoje. Programinės įrangos diegimas galima padaryti bet kuriuo aukšto lygio kalba Skirtingi keliai. 1.3 paveiksle parodyta programos, kuri įgyvendina 1 pavyzdžio automato elgesį, blokinė schema. Nesunku pastebėti, kad programos blokinės diagramos topologija pakartoja automato perėjimo grafiko topologiją. Kiekviena būsena yra susieta su operacija NEXT , kuri atlieka funkciją laukti kito naujo įvesties signalo atėjimo įvykio ir nuskaityti jį į kokį nors standartinį buferį x , taip pat vėliau analizuoti, koks tai signalas. Priklausomai nuo to, koks signalas atėjo į įvestį, ta ar kita funkcija vykdoma ir įvyksta perėjimas į naują būseną.
Ryžiai. 1.3.
Antroje šio skyriaus dalyje bus aptariamas automato aparatinis įgyvendinimas.
2 pavyzdys. „Studentas“
Automatas , kurio modelis parodytas 1.4 pav., apibūdina mokinio ir dėstytojų elgesį.
Ryžiai. 1.4.
valstybėse;
- įvesties signalai: "n", "2" ir "5".
Išvesties reakcijos:
3 pavyzdys 1 . Elektroninis laikrodis (1.5 pav.).
Įvairių funkcionalumų elektroniniai laikrodžiai – vienas plačiausiai kasdieniame gyvenime naudojamų elektroninių prietaisų, kurio valdymas sukonstruotas baigtinio automato modelio pagrindu. Paprastai jie rodo: laiką, datą; jie turi tokias funkcijas kaip „laiko ir datos nustatymas“, „chronometras“, „žadintuvas“ ir kt. Supaprastinta struktūrinė schema elektroninis laikrodis parodytas 1.5 pav
Ryžiai. 1.5.
Registrai rodo arba laiką, arba datą, arba chronometrą, priklausomai nuo „Valdymo“. Valdymo įtaisas pastatytas baigtinio automato modelio pagrindu. Būsenos mašina reaguoja į mygtuko „a“ paspaudimus ant kūno pereidama į būseną „Nustatyti minutes“, kai paspaudus mygtuką „b“ skaičius padidės.
Visi aukščiau aptarti įrenginiai priklauso kombinuotų grandinių klasei, ty diskretiesiems įrenginiams be atminties. Kartu su jais skaitmeninėse technologijose paplito nuoseklūs automatai, arba, kitaip tariant, kombinacinės grandinės, sujungtos su atminties elementais.
Pagal terminą mašina pagal abu būsenos signalus galima suprasti kokio nors tikro įrenginio funkcionavimą išorinė aplinka, ir vidinius signalus apie paties automato būseną. Šiuo atžvilgiu kompiuteris gali būti laikomas skaitmenine mašina. Skaitmeninė mašina yra įrenginys, skirtas skaitmeninei informacijai konvertuoti. Kita vertus, pagal terminą mašina galite suprasti kai kurių prietaisų matematinį modelį. Bendroji automatų teorija yra padalinta į dvi dalis: abstrakčiai ir struktūrinės automatų teorija. Skirtumas tarp jų yra tas, kad abstrakčioji teorija abstrahuojasi tiek nuo paties automato, tiek nuo įvesties ir išvesties signalų struktūros. AT abstrakčioji teorija analizuojami automato perėjimai, veikiami abstrakčių įvesties žodžių, ir ant šių perėjimų suformuoti abstraktūs išvesties žodžiai.
Struktūrinėje teorijoje nagrinėjama tiek paties automato, tiek jo įvesties ir išvesties signalų struktūra, automatų konstravimo iš elementarių automatų metodai, įvesties ir išvesties signalų kodavimo metodai, automato būsenos.
Atsižvelgiant į tai, įprasta atskirti du automatų modelius: struktūrinį ir abstraktų. Teoriškai nagrinėjant automatus naudojamas abstraktus modelis. Struktūrinis modelis naudojamas automato grandinei sukonstruoti iš loginių elementų ir trigerių ir yra skirtas valdymo funkcijai atlikti.
Abstraktus automatas- tai yra matematinis modelis skaitmeninis automatas, pateiktas šešių komponentų vektoriumi S=(A,Z,W,d,l,a 1), kur А=(a a ,…,am ) yra abstrakčiojo automato vidinių būsenų aibė; Z=)