Automatų teorija. Paskaitos apie automatų teoriją - failų automatų teorija.doc Probleminės grupės abstrakčių automatų teorijoje

automatų teorija
Automatų teorija- diskrečiosios matematikos skyrius, nagrinėjantis abstrakčius automatus - kompiuterius, pateiktus matematinių modelių pavidalu - ir užduotis, kurias jie gali išspręsti.

Automatų teorija glaudžiausiai susijusi su algoritmų teorija: automatas paverčia diskrečią informaciją žingsneliais į atskirus laiko momentus, o rezultatą generuoja tam tikro algoritmo žingsneliais.

1 Terminija
2 Taikymas
- 2.1 Tipinės užduotys
3 Taip pat žr
4 Literatūra
5 Nuorodos

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.

Automatas

Automatai gali būti deterministiniai arba nedeterministiniai.

Deterministinis baigtinis automatas (DFA)

yra tokia perėjimo funkcija
- pradinė būsena

Nedeterministinis baigtinis automatas (NFA)- penkių elementų seka (kortelė), kur:

- automato būsenų rinkinys
- kalbos, kurią supranta automatas, abėcėlė
yra pereinamasis santykis, kur yra tuščias žodis. Tai reiškia, kad NFA gali pereiti iš būsenos q į būseną p, skirtingai nei DFA, per tuščią žodį, taip pat pereiti iš q į kelias būsenas (kas vėlgi neįmanoma DFA).
- pradinių būsenų rinkinys
- galutinių būsenų rinkinys.

Žodis automatas skaito baigtinę simbolių eilutę a1,a2,…., an , kur ai ∈ Σ, kuri vadinama įvesties žodžiu.Visų žodžių aibė rašoma kaip Σ*. Gautas žodis Žodį w ∈ Σ* priima automatas, jei qn ∈ F.

Laikoma, kad kalba L skaitoma (priimama) automato M, jei ji susideda iš žodžių w pagal abėcėlę taip, kad jei šie žodžiai įvedami į M, apdorojimo pabaigoje ji 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. Yra automatų, kurie gali pereiti į naują būseną neskaitydami simbolio. Perėjimo funkcija neskaitant simbolio vadinama -jump (epsilon-jump).

Taikymas

Automatų teorija yra visų skaitmeninių technologijų ir programinė įranga, taigi, pavyzdžiui, kompiuteris yra ypatingas baigtinių būsenų mašinos praktinio įgyvendinimo atvejis.

Dalis automatų teorijos matematinio aparato yra tiesiogiai 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ė- duotų „elementarių automatų“, lygiaverčių tam tikram automatui, sistemos sukūrimas. Toks automatas vadinamas struktūriniu. Jis naudojamas, pavyzdžiui, skaitmeninio sintezėje elektros grandinės ant tam tikro elemento pagrindo.

taip pat žr

Siurblys Lemma
Abstraktus automatas
Žaidimas "Gyvenimas"
Minimali automato forma
Šenono-Lupanovo teorema

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

Automatų teorijos taikymas

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. Skirtingas objektuose vykstančių fizinių procesų pobūdis, kompleksas
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 vaizdavimas, 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ą. Didelė dalis automatų teorijos
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ą.<><><>Yra žinoma daug
į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 tekti 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 didelis skaičius perėjimai, sąlygos 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.
Kadangi mobiliosios programos turi 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žduotys. 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 srityse.
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
įgytos patirties panaudojimas pilnai praktiškai nėra. 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ų interneto paieškos sistemų naudoja
speciali programa- paieškos robotas, kuris yra automatas.
Interneto ir skaitmeninių bibliotekų su nuolatine prieiga amžiuje įprasta
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. Kuriame 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

Teorinės kibernetikos skyrius, tiriantis realiai egzistuojančių (techninių, biologinių ir kt.) matematinius modelius (vadinamus automatais, mašinomis) arba iš esmės galimus įrenginius, kurie apdoroja diskrečią informaciją diskretiškais laiko žingsniais. Ir. t. iškilo hl. taip, veikiant skaitmeninių kompiuterių ir valdymo mašinų technologijos reikalavimams, taip pat vidiniams algoritmų teorijos ir matematinės logikos poreikiams. „Automato“ sąvoka labai skiriasi priklausomai nuo šių prietaisų pobūdžio, nuo priimto abstrakcijos lygio ir atitinkamo bendrumo laipsnio (automatai yra baigtiniai, begaliniai, augantys, tikimybiniai, deterministiniai, autonominiai ir kt.).

Klausimas yra apie tokios koncepcijos "automatą" sukūrimą, kuris turėtų maks. Bendrumo laipsnio ir tuo pačiu galėtų būti pagrindu nustatant ir sprendžiant pakankamai esmines problemas, dar negali būti laikomos visiškai išspręstomis. Kartu tai gali būti laikoma specialiu bendrosios valdymo sistemos sampratos atveju.

Sąvoka „A. t." pradėta naudoti XX amžiaus šeštajame dešimtmetyje, nors atitinkamos problemos didele dalimi pradėjo formuotis dar 30-aisiais algoritmų teorijos ir relių įtaisų teorijos rėmuose. Tada teorijos algoritmuose buvo suformuluotos gana bendros skaičiavimo sąvokos. automatas (žr. Tiuringo mašiną) ir (netiesiogiai) baigtinio automato samprata (tiūringo mašinos galvutė). Nustatyta, kad norint

visokios efektyvios informacijos transformacijos, visai nebūtina kiekvieną kartą kurti specializuotų automatų; iš esmės visa tai galima padaryti vienoje universalioje mašinoje su tinkama programa ir tinkamu kodu. Ši teorija. rezultatas vėliau gavo inžinerinį įsikūnijimą modernių universalių kompiuterių pavidalu. mašinos. Tačiau išsamus įvairių rūšių automatuose vykstančių procesų ir jiems taikomų bendrųjų dėsnių tyrimas vėliau prasidėjo tik A. T. Formuluotės skirtumai tarp algoritmų teorijos problemų ir A. T. ką. mašinos gali tai padaryti ir kaip jos tai daro. Kadangi kitų tipų automatų (išskyrus Tiuringo mašinas) įtraukimas tikrai neišplečia skaičiuojamų informacijos transformacijų atsargų, tai algoritmų teorijai toks įtraukimas yra tik epizodinis ir siejamas tik su taikoma įrodinėjimo technika. Kita vertus, A. t. toks svarstymas tampa savitiksliu. Theor. ir taikomosios automatizavimo, skaičiavimo problemos. technologija ir programavimas, biol modeliavimas. elgesys ir tt toliau skatina A. t.. Tačiau kartu su tuo A. t. jau vystosi savo vidines problemas. Algebros teorijoje plačiai naudojamas algebros, matematinės logikos, kombinatorinės analizės (įskaitant grafų teoriją) ir tikimybių teorijos aparatas.

Automatų teorijoje kai kurios jo kryptys išryškėja gana aiškiai, nulemtas tiriamų automatų tipų (baigtinių, tikimybinių ir kt.) pasirinkimo, priimto abstrakcijos lygio (žr. Abstrakčių automatų teorija, Struktūrinė automatų teorija). ), arba pagal taikomosios matematikos specifiką. metodai (žr. Algebrinių automatų teoriją). Kartu su tuo susijusios problemos ir metodai intensyviai plėtojami relinių įrenginių teorijoje, skaitmeninių kompiuterių teorijoje ir programavimo teorijoje, todėl dažnai sunku atskirti šių teorijų veikimo sritis nuo A. t.

Elgesys ir struktūra. A. t. centre yra tikslūs kilimėliai. sąvokos, kurios formalizuoja intuityvias idėjas apie automato veikimą ir elgesį, taip pat apie jo struktūrą (vidinę struktūrą). Automatai savo elgsenos požiūriu dažniausiai laikomi žodyno informacijos konverteriais, t.y. raidžių sekų keitėjais į raidžių sekas. Įgyvendinama transformacija paprastai interpretuojama kaip tam tikros funkcijos (operatoriaus) reikšmių apskaičiavimas pateiktomis argumentų reikšmėmis arba kaip tam tikro tipo problemų sąlygų įrašų pavertimas į įrašus atitinkamus sprendimus. Visų pirma, vadinamieji. atpažindami automatus, suvokdami įvesties informaciją, į ją reaguoja taip, kad vienas įvesties signalų sekas priimtų, o kitas atmestų. Šia prasme jie atpažįsta arba, kaip sakoma, atstovauja daugybei įvesties sekų. Galiausiai generacinis automatas funkcionuoja kaip autonominė sistema, nesusijusi su įvesties informacija, jo elgesį lemia tai, kokias išvesties sekas jis sugeba generuoti. Aukščiau pateikta klasifikacija transformacijos, atpažinimo ir generavimo požiūriu priklauso nuo automato veikimo taisyklių, t. y. nuo jo vidinių būsenų sąveikos su įvestimi (ateinančia iš išorinės aplinkos) ir išvesties (pagaminta į automatą) programos. išorinės aplinkos) signalus. Tegu Q, X, Y yra atitinkamai automato įėjimo ir išėjimo signalų vidinių būsenų rinkinys. Jei tai deterministinis automatas, jo programa formalizuojama perėjimo f-ts ir išvesties f-ts požiūriu, kiekvienam įvesties signalui x ir kiekvienai būsenai nurodant būseną, į kurią pereina automatas, ir jo generuojamą išėjimo signalą.

Abstraktioji automatinė teorija pasižymi aukštesniu abstrakcijos lygiu: joje automato sąvoka tapatinama su automato programos sąvoka, tai yra su penkiais (), visiškai abstrakcija nuo jos struktūros. Automato struktūra atspindi būdą, kaip jis yra organizuotas iš paprastesnių tarpusavyje sąveikaujančių komponentų (elementarių automatų arba tiesiog elementų), tinkamai sujungtų į vieną sistemą. Pavyzdžiui, skaičiavimas mašina sudaryta iš elementarių elementų, tokių kaip trigeriai, keitikliai ir kt.; Nervų sistema susideda iš neuronų. Struktūrinę automatų klasifikaciją nulemia leidžiamų jungčių pobūdis (jungtys gali būti standžios arba keisti eksploatacijos eigoje, taikomos tam tikros geom. apribojimai), taip pat naudojamų elementų veikimo ir sąveikos specifika ( pavyzdžiui, elementai gali tik keistis informacija arba gali generuoti naujus elementus, sukurdami struktūrą). Struktūrinių sąvokų formalizavimas atliekamas pagal įvairių tipų schemas (žr. Loginis tinklas). A. N. Kolmogorovas apibūdino požiūrį, kuris paskatino suformuluoti labai bendrą, bet vis dar konstruktyvią automato struktūros koncepciją (žr. Augantys automatai), kuri, matyt, apima visus žinomus automatų struktūrų tipus ir visus tuos, kuriuos galima numatyti šiuolaikinio lygio mokslas. Visiškai akivaizdu, kad tarp automato struktūros ir jo elgesio yra glaudus ryšys. Tačiau atskiras kiekvieno iš šių dviejų aspektų tyrimas su reikšmingu abstrakcija nuo kito yra ne tik įmanomas, bet dažnai naudingas keliant ir sprendžiant daug svarbių problemų. Toks tyrimas atliekamas atitinkamai abstrakčioje (elgesio) ir struktūrinėje automatų teorijoje.

Mašinų tipai. Labiausiai paplitęs yra automatų ir ko-resp. skyriai A. t., skirti įvairiems

mašinų tipų, atsižvelgiant į šias savybes.

1) Atminties kiekis. Baigtiniai ir begaliniai automatai apibūdinami pagal. atminties kiekio (vidinių būsenų skaičiaus) baigtinumą ir begalybę. Baigtiniai automatai yra atskiri šiuolaikinio skaičiavimo blokai. mašinos ir net visa mašina. Smegenys taip pat gali būti vertinamos kaip baigtinės būsenos mašina. Begaliniai automatai yra natūralus kilimėlis. idealizacija, išauganti iš idėjos apie automatą su baigtiniu, bet be galo daug būsenų. Tai reiškia tik potencialią atminties begalybę, kuri pasireiškia tuo, kad atmintis, nors ir išlieka baigtinė kiekvienu laiko momentu, gali augti neribotai. Toks idealizavimas pirmą kartą atsirado algoritmų teorijos rėmuose, tobulinant intuityvią algoritmo idėją. Struktūriškai augantis automatas vaizduojamas kaip elementų, galinčių daugintis ir augti, derinys. Šiuolaikinius kompiuterius galima laikyti augančiais (o kartu ir potencialiai begaliniais) automatais tokia prasme: kad skaičiavimai būtų atlikti visais atvejais, reikia pripažinti neriboto išorinės (juostinės) atminties augimo galimybę.

2) Atsitiktinės atrankos mechanizmas. Deterministiniuose automatuose elgesį ir struktūrą kiekvienu laiko momentu vienareikšmiškai lemia dabartinė įvesties informacija ir automato būsena, kuri susiformavo prieš pat momentą. Tikimybiniuose (stochastiniuose) automatuose jie taip pat priklauso nuo kažkokio atsitiktinio pasirinkimo. Stochastiniai automatai neturėtų būti painiojami su nedeterministiniais automatais, kuriuose taip pat pažeidžiama unikalumo sąlyga (tačiau nedalyvaujant c.l. atsitiktinės atrankos mechanizmui).

Problemos ir metodai. Pagrindinės automatinės teorijos problemos apima analizės, ty automato elgesio aprašymo pagal jo pateiktą programą ar struktūrą, ir sintezės, ty automatų projektavimo, kurių elgesys atitiktų iš anksto nustatytus reikalavimus, problemas. Su šiomis problemomis glaudžiai susijusios ir daugelis kitų intensyviai tiriamų problemų (išsamumas ir universalumas, minimizavimas, kalbos, asimptotiniai įverčiai ir kt.). Labiausiai analizė ir sintezė buvo tiriama baigtinių deterministinių automatų teorijoje, o abstrakčiai ir struktūrinėje automatų teorijoje jie interpretuojami skirtingai. Taigi, pavyzdžiui, struktūrų teorijoje sintezė (žr. Struktūrinių automatų sintezę) reiškia grandinės sukūrimą iš tam tikro elementų asortimento, kuris būtų optimalus. (arba artimas optimaliam) tam tikro grandinių sudėtingumo kriterijaus prasme. Čia vyrauja kombinatoriniai-informaciniai metodai ir asimptotiniai įverčiai (K. Shannon, S. V. Yablonskii, O. B. Lupanov ir kt.). Abstrakčioje automatų teorijoje pasitenkinama automato veikimo programos sukūrimu (žr. Abstrakti automatų sintezė), pavyzdžiui, baigtinio automato perėjimo ir išėjimo funkcijų forma, kuri dažniausiai yra pradinė. medžiaga tolesnei struktūrinės sintezės plėtrai. Čia vyrauja algebrinė (S. K. Klini, V. M. Gluškovas ir kt.), matematinė ir loginė. (B. A. Trakhtenbrot, R. Buchi ir kt.) ir žaidimo (R. McNotop) metodai ir sąvokos. Relinių įtaisų teorijoje svarbią vietą užima ir baigtinių deterministinių automatų analizės ir sintezės problema.

Eksperimentų su automatais teorijoje (E. Moore) kuriami metodai, leidžiantys naudojant informaciją, gautą iš išorės stebėjimo automato elgseną, atkurti jo veikimo programą ar bent kai kurias jo savybes. Šiuos metodus galima vertinti kaip savotišką abstrakčią automatų sintezę ir dekodavimą (Ya. M. Barzdin). K. Shannon, M. Rabin ir kitų darbai pasitarnavo kaip postūmis plėtoti tikimybinių automatų teoriją šiomis kryptimis: 1) kiek deterministinių automatų teorijos sąvokos ir metodai perkeliami į stochastinius automatus. ; 2) kokie skaičiavimo supaprastinimai. procesai pasiekiami paliekant siauresnę deterministinių automatų klasę į platesnę tikimybinių automatų klasę. Augimo automatų tyrimas daugiausia orientuotas į šias problemas: 1) augančių automatų modelių kūrimas ir atskirų jų klasių tyrimas (iteratyvūs automatai - F. Henny, registro automatai - V. M. Gluškovas, savaime atkuriantys automatai - J. von Neumann, apibendrintas auginimo automatas - A. N. Kolmogorovas, Ya. M. Barzdinas); 2) įvertinimas skaičiuojamas auginimo automatų (Ya. M. Barzdin, B. A. Trakhtenbrot, Yu. Khartmanis, G. S. Tseitin, M. Rabin ir kt.) skaičiavimo galimybė ir sudėtingumas.

Ryšys su kitomis mokslo sritimis.

Algoritmų teorijos ir relinių įtaisų teorijos reikšmė automatinei technologijai jau buvo paaiškinta aukščiau. Taip pat turėtume atkreipti dėmesį į A. t. abipusiškumą, kurio metodai leido išspręsti daugybę matematikos problemų. logika ir algoritmų teorija (R. Buchi). Augančių automatų teorijoje iškylanti problema (pavyzdžiui, skaičiavimo sudėtingumas) iš esmės glūdi algoritmų teorijos ir asimptotinių automatų struktūrinės sintezės dėsningumų sankirtoje. Stiprus abipusis matematinės lingvistikos ir matematinės kalbotyros, kurios viena iš svarbių sąvokų yra generacinė gramatika, skverbtis yra objektas, labai artimas generatyviniam automatui. Todėl tam tikrus gana svarbius gramatikų teorijos teiginius iš esmės galima priskirti automatinei teorijai Abstrakčioje automatų teorijoje mat. mokymosi, taip pat vieno individo ar komandos tikslingo elgesio klausimai buvo išaiškinti ir tiriami žaidimo automatų požiūriu (M. L. Tsetlin). Naudinga

taip pat buvo ryšys tarp baigtinių automatų teorijos ir kompiuterių projektavimo bei programavimo teorijos (V. M. Gluškovas, A. A. Letichevskis).

Lit .: Gavrilov M A. Relių-kontaktinių grandinių teorija. M. - L., 1950 [bibliogr. Su. 298-299]; „Matematikos instituto darbai. V. A. Steklovo SSRS mokslų akademija, 1958, t. 51; Gluškovas V. M. Skaitmeninių automatų sintezė. M., 1962 [bibliogr. Su. 464–469]; Kobrinsky N. E., Trakhtenbrot B. A. Įvadas į baigtinių automatų teoriją. M., 1962 [bibliogr. Su. 399-402]; Tsetlin ML Automatų teorijos ir biologinių sistemų modeliavimo tyrimai. M., 1969 [bibliogr. Su. 306-316]; Trakhtenbrot B. A., Barzdin Ya. M. Baigtiniai automatai (Elgesys ir sintezė). M., 1970 [bibliogr. Su. 389-395]; Automatas. Per. iš anglų kalbos. M., 1956. B. A., Trakhtenbrotas.

Kiekvienas klausimas dedamas į vieną atskirą puslapį (išskyrus vieną – „KA algebrinė ir struktūrinė teorija“, kuris užima du puslapius). Cheat lapo formatas: doc.

Klausimai apie lovelę

Automatų teorijos dalykas
Automatų klasifikacija
Automatų teorijos taikymai
dvejetainis dauginimas
Daugyba atvirkštiniais kodais
Padalinys
Padalijimas atvirkštiniais kodais. Ypatumai
Operacijų atlikimo slankiojo kablelio formatu ypatybės
Dvejetainiai dešimtainiai kodai. Papildymas DDC
Diskretus keitiklis Gluškovo modelis
Mikroprogramavimas
Veikiančių mašinų konstrukcijos
Procedūrinio tipo veikiančio automato (OA) sintezė
OA struktūrinio tipo sintezė
Automatinės kalbos. Oficialus automato pavedimas
„Mealy“ ir „Moore“ modeliai
Baigtinių automatų (FA) ekvivalentiškumas. Moore'o teorema
Baigtinių automatų sumažinimas
Mealy ir Moore mašinų lygiavertiškumas
Valdymo mašinų tipai (UA)
UA blokinės diagramos. Miles ir Moura
Valdymo automato su standžiąja logika (UAZhL) sintezės etapai
UAHL sintezės pavyzdžiai
Lenktynės ir kaip su jomis elgtis
UA su programuojama logika (PLL)
KA algebrinė ir struktūrinė teorija
Kelių UA sujungimas į vieną
KA programinė įranga. Įgyvendinimo parinktys. Šablono būsena
VHDL tikslas ir trumpas aprašymas
UA diegimas VHDL
Suprasti UML modeliavimo kalbą
Kalbų samprata ir formalioji gramatika
Kalbos klasifikacija
Siurblys Lemma
NKI samprata. DCA gavimas per NCA
Reguliarūs posakiai. Sintaksinės diagramos. Kleene teorema
RV taikymas. Įvairūs RW žymėjimai
COP-gramatikos ir nuspaudimo automatai
Tiuringo mašinos
MT naudojimas algoritmams analizuoti

Apgaulingo lapo klausimo pavyzdys

Automatų teorijos dalykas

Automatas yra objektas (idealas, medžiaga arba, tiksliau, įrenginys), kuris apdoroja informaciją.

Informacijos transformavimo metodų tyrimas yra automatų teorijos dalykas plačiąja prasme.

Automatų teorija yra kibernetikos dalis, kaip mokslas apie tai, kaip informacija saugoma, suvokiama, perduodama ir apdorojama mašinose ir gyvuose organizmuose.

Automatų teorija naudoja įvairius matematinius modelius. Bendriausius iš jų tiria abstrakčioji automatų teorija ir algebrinė TA.

Abstrakčiosios TA požiūriu automatas yra rinkinių ir atvaizdų rinkinys. Pavyzdžiui, automatas gali būti apibrėžtas kaip šešių objektų: A = , kur:

X yra automato įvesties simbolių rinkinys
Y yra automato išvesties simbolių rinkinys
Q yra automato būsenų rinkinys
q0 yra pradinės automato būsenos
A – perėjimo funkcija: Q x X -> Q
B yra išvesties funkcija: Q x X -> Y

Automato transformacijos: automato išvesties žodžiai priklauso ne tik nuo būsenų išvesties žodžių, bet ir nuo ankstesnės būsenos žodžių reikšmių.

Matematinis automatas kartais laikomas algebra ir išskiriamas automato būsenų ir operacijų rinkinys šioje aibėje.

Techninis automatas yra fizinis įrenginys, kuriam svarbus ne tik elgesys ar veikimo dėsnis, bet ir jo vidinė struktūra, gaudama šią struktūrą, todėl technikoje jie laiko automato konstrukcijos teoriją, kurios tema yra automato sandaros tyrimas, automato grandinių su nurodytomis savybėmis analizė ir sintezė.

Galima išskirti šiuos automatų teorijų tipus:

Santrauka TA (matematinė);
Struktūrinė TA (techninė);
Bendroji TA;
Taikomoji TA;

PTCA – diskretinis automatas – įrenginys, konvertuojantis skaitmeninę informaciją pagal nurodytą algoritmą.

TT automatas – įrenginys, atliekantis įvesties žodžių (teksto) transformaciją (atpažinimą).

Siųsti savo gerą darbą žinių bazėje yra paprasta. Naudokite žemiau esančią formą

Studentai, magistrantai, jaunieji mokslininkai, kurie naudojasi žinių baze savo studijose ir darbe, bus jums labai dėkingi.

Priglobta adresu http://www.allbest.ru/

Rusijos Federacijos švietimo ministerija

Valstybinė švietimo įstaiga

aukštasis profesinis išsilavinimas

Sibiro valstybinis aviacijos universitetas

pavadintas akademiko M.F. Rešetnevas

Sisteminės analizės katedra

abstrakčiai disciplinoje „Sistemų teorija“ tema:

" Tteorijakulkosvaidis"

Užbaigė: Larionovas A.Yu.

Patikrinta: Ikonnikovas O.A.

Krasnojarskas 2013 m

Įvadas

1. Bendra informacija apie automatų teoriją

1.1 Atpažintojai

1.2 Automatų klasifikacija

1.2.1 Abstraktus automatas

1.2.2 Automatų tipai ir porūšiai

2. Skaitmeninės mašinos. Bendra informacija

2.1 Loginiai elementai

2.2 Baigtinių skaitmeninių automatų su atmintimi teorija

2.3 Daliniai automatai

2.4 T formos gaidukas

2.5 D gaidukas

2.6 RS šlepetas

2.7 JK šlepetės

2.8 Universalus gaidukas

Išvada

Naudotų šaltinių sąrašas

Įvadas

Automatų teorija yra diskrečiosios matematikos šaka, tirianti abstrakčius automatus – kompiuterius, vaizduojamus kaip matematinius modelius – ir problemas, kurias jie gali išspręsti.

Automatų teorija yra šiuolaikinių skaitmeninių sistemų gamybos pagrindas: elektroniniai kompiuteriai, informaciniai ir valdymo kompleksai pramonės, gynybos ir kosmoso reikmėms.

Santraukos tikslas – įvairiais kampais aprašyti automatų teorijos ypatybes. Žvilgsnis į automatų teoriją bus tiek iš diskrečiosios matematikos, tiek iš elektronikos ir schemų pusės.

1. Bendra informacija apie automatų teoriją

Automatų teorija skirstoma į abstrakčiąją ir struktūrinę.

Abstraktioji automatų teorija svarsto struktūrą neatsižvelgdama į techninio įgyvendinimo priemones. Abstraktaus svarstymo rezultatas yra viena ar kita perėjimo funkcijos ir išvesties funkcijos išraiška. Taigi abstrakčiosios teorijos lygmeniu „automato veikimo“ sąvoka suprantama kaip įvesties informacijos pavertimas išvesties informacija.

Struktūrinė automatų teorija tiria bendruosius konstravimo metodus blokinės schemos automatai, pagrįsti elementariais automatais.

1.1 Atpažintojai

Automato veikimą lemia atpažintojo veikimas. Yra gramatikų klasė, kuri turi savo atpažinimo klasę, kuri apibrėžia tą pačią kalbų klasę:

Kalba L yra dešinioji tada ir tik tada, kai ją apibrėžia vienpusis deterministinis baigtinis automatas;

Kalba L yra be konteksto tada ir tik tada, kai ją apibrėžia vienpusis nedeterministinis nuspaudimo automatas;

Kalba L yra jautri kontekstui tada ir tik tada, kai ją apibrėžia dvipusis nedeterministinis nuspaudimo automatas;

Kalba L yra rekursyviai suskaičiuojama tada ir tik tada, kai ją apibrėžia Tiuringo mašina (šios rūšies matematiniai objektai aptariami kurse „Matematinė logika ir algoritmų teorija“).

3 tipo gramatikos yra automatai, nes yra ryšys tarp šių gramatikų ir baigtinių automatų, neturinčių išvesties ar skyriklių. Toks atpažintuvas apima įvesties juostą, skaitymo galvutę ir valdymo įtaisą, kaip parodyta 1 paveiksle.

1 paveikslas – atpažinimo priemonė

Atpažintojo darbas atliekamas taip:

Įvesties žodis įrašomas į begalinę juostą, apribotą kairėje pusėje. Kiekviename juostos langelyje yra vienas įvesties eilutės simbolis, pradedant nuo kairiojo langelio;

Tušti langeliai (įvesties eilutės pabaigoje) užpildomi specialiu simboliu, žyminčiu eilutės pabaigą. Paprastai atitinka tuščią kalbos eilutę e (žr. 1 pav.);

Įvesties abėcėlės simbolius nuskaito skaitymo galvutė, kuri perskaičius simbolį pasislenka viena padėtimi į dešinę. Tokiu būdu perskaitytas simbolis tiekiamas į valdymo įrenginio įvestį, kuris gali pakeisti savo būseną.

A – atpažinėjas – matematinis objektas. P yra atpažintojo įvesties abėcėlė, kurią sudaro į įvesties juostą įrašyti simboliai. S yra atpažinimo būsenų rinkinys, kur s0 yra pradinė būsena, o ši būsena yra atitinkamai iš aibės S. ts – perėjimo funkcija.

Teigiama, kad įvesties žodis (eilutė) yra leistinas atpažintojui A, jei, nuosekliai nuskaitęs simbolius iš įvesties juostos, atpažintuvas pereina iš pradinės konfigūracijos į vieną iš galutinių.

1.2 Automatų klasifikacija

Yra bendresnė matematinių objektų klasė. Pagrindinė sprendiklio užduotis yra nustatyti, ar duota eilutė priklauso atpažintoją atitinkančiai kalbai. Kartu iškyla užduoties dalis ne atpažinti eilutę, o paversti ją kita forma.

Ypatingas atvejis yra eilutės atpažinimas, kurį galima įsivaizduoti kaip savavališko simbolio pavertimą dviem simboliais „taip“ ir „ne“, kur simbolis „taip“ reiškia, kad eilutė priklauso nurodytai kalbai.

Tipiškas konvertavimo pavyzdys yra programos vertimas iš aukšto lygio kalbos į mašininio kodo kalbą ir matematinių išraiškų konvertavimo užduotis.

1.2.1 Abstraktus automatas

Abstraktus automatas yra matematinis objektas, kuris yra elementų rinkinys: A=(S,X,Y,d,l), kur S yra baigtinė automato būsenų aibė; X,Y - atitinkamai galutinės įvesties ir išvesties abėcėlės, iš kurių formuojamos eilutės, kurias nuskaito ir išduoda aparatas; d:SxY->S - perėjimo santykis (perėjimo funkcija); l - išvesties funkcija.

Abstraktus automatas turi tokią funkcinę diagramą, kaip parodyta 2 pav.

2 pav. Abstrakčiojo automato funkcinė diagrama

kur si yra nauja automato būsena; xi - srovės įvesties simbolis; yi yra dabartinės išvesties simbolis.

Abstrakčiojo automato veikimo tvarka yra tokia:

Kai ateina kitas simbolis į automato įvestį, perėjimo funkcija y, remdamasi įeinančiu simboliu xi ir esama būsena si, nustato naują automato būseną Si+1;

Išvesties funkcija, remiantis esama automato si būsena ir srovės įvesties simboliu xi, nustato esamą išėjimo simbolį.

Abstraktaus automato atminties talpa yra jo vidinių būsenų skaičius.

Pažymėtina, kad automatų nurodymo būdai yra panašūs į atpažintojų nurodymo būdus – tai perėjimo lentelė ir perėjimo diagrama. matematikos diskretusis automatas

Abstrakčiojo automato sąvoka yra pati bendriausia. Ir iš tikrųjų dauguma automatų rūšių yra ypatingas abstraktaus automato atvejis. Apskritai automatų hierarchiją galima pavaizduoti pagal 3 pav.

3 pav. Automatų hierarchija

1.2.2 Automatų tipai ir porūšiai

Pradiniai automatai – reiškia atskirą klasę – tai abstraktūs automatai su išskirtine pradine būsena. Taigi pradinių automatų aibė aprašoma vienu abstrakčiu automatu.

Pagal diskretinio laiko skaičiavimo pobūdį automatai skirstomi į sinchroninius ir asinchroninius. Sinchroninės būsenos mašinose laikas, kuriuo aparatas nuskaito įvesties signalus, turi būti nustatytas pagal laikrodžio signalus. Po kito sinchronizavimo signalo, atsižvelgiant į skaitymo signalą ir pagal automato veikimo ryšius, įvyksta perėjimas į naują būseną ir išėjime išduodamas signalas, po kurio automatas gali suvokti kitą vertęįvesties signalas. Asinchroninis baigtinis automatas nuolat skaito įvesties signalą ir, reaguodamas į pakankamai ilgą pastovios reikšmės X įvesties signalą, gali, kaip matyti iš automato funkcionavimo ryšių, keletą kartų keisti savo būseną, išduodamas atitinkamą skaičių. išėjimo signalų, kol jis pereis į stabilią būseną, kurios šis įvesties signalas nebegali pakeisti.

Deterministiniai ir nedeterministiniai automatai skiriasi būsenų, kuriose automatas gali būti vienu metu, skaičiumi. Deterministinis automatas yra vienoje būsenoje bet kuriuo laiko momentu, o nedeterministinis automatas gali būti keliose būsenose vienu metu bet kuriuo metu.

Ypatingas nedeterministinio automato atvejis yra tikimybinis automatas. Jei perėjimo funkcija ir (arba) išvesties funkcija yra atsitiktinės, tada automatas vadinamas tikimybiniu. Kitaip tariant, tikimybinis automatas yra sistema, apibūdinama baigtiniais įėjimo signalų rinkiniais X=(x1, x2,..., xn), būsenomis S=(s1, s2,..., sn), išėjimo signalais Y= (y1, y2,...,yn). Taip pat pateikta sąlyginių tikimybių aibė, kad tikimybinis automatas, būdamas aj būsenoje ir gavęs įvesties signalą x, eis į būseną ai ir išduos signalą y.

Tikimybinis automatas yra labai patogus kaip modelis, nes jis tinkamai atspindi mūsų žinių apie kai kurias, pavyzdžiui, socialines sistemas, neišsamumą ir leidžia padidinti šio modelio tikslumą, kai gauname naujų žinių apie modeliuojamą sistemą. Tikimybinio automato veikimas lengvai imituojamas kompiuteryje. Tokį svarbų aspektą gyvų sistemų tyrimams kaip savarankiško mokymosi procesas parodo tikimybinis automatas per teisingų reakcijų tikimybių pasikeitimą.

Pagal papildomos atminties buvimą išskiriami automatai su „push-pull“ atmintimi. Skirtingai nuo abstrakčių automatų, atminties kiekis, kurį lemia būsenų skaičius, tokiuose automatuose yra papildomas elementas, vadinamas kamino. Stackas įgyvendina LIFO (Last In - First Out) atminties modelį ir yra naudojamas tarpiniams darbo rezultatams saugoti.

Reikėtų atsižvelgti į tai, kad klasifikacija pagal sinchronizmo / asinchronijos, determinizmo / nedeterminizmo požymius, papildomos atminties buvimą, automato būsenų skaičių yra nepriklausomi, t. y. pilnas automato aprašymas turėtų apimti visų šių ženklų aprašymas, pavyzdžiui: baigtinis sinchroninis deterministinis automatas su stumiamąja atmintimi.

Todėl galima pastebėti, kad sujungus abstrakčių automatų tipus, galima gauti kitus automatus su skirtingu funkcionalumu.

2. Skaitmeninės mašinos. Bendra informacija

Kompiuteris apdoroja skaitinę informaciją, pateiktą dvejetainėje sistemoje, t.y. informacija pateikiama kaip nulių ir vienetų derinys. Todėl bet kurios kompiuterio grandinės veikimas gali būti laikomas funkciniu keitikliu su daugybe įėjimų ir išėjimų. Šiuo atveju tam tikros įvesties signalų sekos, susidedančios iš nulių ir vienetų, įvesties, išvestiese atsiranda tiksliai apibrėžta išėjimo signalų seka, taip pat susidedanti iš nulių ir vienetų.

Visas kompiuterių grandines galima suskirstyti į dvi dideles klases:

Loginių arba kombinuotų grandinių (CS) klasė.

Baigtinių automatų klasė.

Loginėse (kombinuotose) grandinėse išėjimo signalų vertė momentu t yra vienareikšmiškai nustatoma pagal įvesties signalų reikšmes momentu t1 t.

Išėjimo signalus antros klasės grandinėse lemia ne tik įvesties signalų reikšmės tam tikru momentu, bet ir grandinės būsenos, kurios savo ruožtu priklauso nuo taikomų signalų vertės. į jo įvestis visais ankstesniais laiko momentais. Šiose grandinėse būtinai yra atminties elementų, kurie naudojami kaip įvairių tipų trigeriai.

Techniniai kombinuotųjų grandinių sintezės klausimai sprendžiami naudojant matematinės logikos aparatą. Tam naudojama paprasčiausia matematinės logikos dalis, būtent logikos algebra arba Būlio algebra. Pagrindinė logikos algebros sąvoka, kuria remiasi jos taikymas CS sintezei, yra Būlio arba perjungimo funkcijos (SF) sąvoka.

2.1 galvosūkiselementai

Tarp pramonės gaminamų elementų sistemų labiausiai paplitę yra loginiai elementai, kurie įgyvendina operacijas: AND-NOT, OR-NOT, AND-OR-NOT, taip pat Būlio pagrindo elementai.

Ši elementų sistema apima ir universalaus pagrindo elementus: AND-NOT, OR-NOT, ir Būlio bazinių operacijų derinius: AND-OR-NOT.

2.2 Baigtinių skaitmeninių automatų su atmintimi teorija

Kompiuterinėje technologijoje daugiausia naudojamos dvi grandinių klasės: kombinacinės grandinės ir skaitmeniniai automatai. Išskirtinis bruožas Kombinuotosios grandinės yra standus funkcinis ryšys tarp išėjimo signalo ir įvesties:

y(t) = f(x(t) ) .

Be to, nesant įvesties signalų, išėjimo signalų taip pat nėra, nes tokios grandinės neturi atminties. Skirtingai nuo kombinuotųjų grandinių, antros klasės grandinėse yra atminties elementų (atminties elementų). Šios grandinės vadinamos skaitmeniniais automatais (DA) arba tiesiog automatais. DA išėjimo signalai tam tikru laiko momentu priklauso ne tik nuo įvesties signalų vertės tuo pačiu momentu, bet ir nuo grandinės būsenos, kurią, savo ruožtu, lemia reikšmės. įvesties signalų, gautų ankstesniais laiko momentais. Leiskite mums pristatyti pagrindines sąvokas ir apibrėžimus.

Automatas – tai diskrečios informacijos keitiklis, galintis priimti įvairias būsenas, perjungti įvesties signalų įtakoje iš vienos būsenos į kitą ir generuoti išėjimo signalus. Jeigu automato būsenų aibė, taip pat įėjimo ir išėjimo signalų aibės yra baigtinės, tai automatas vadinamas baigtiniu automatu.

Būsenos sąvoka buvo įvesta dėl to, kad dažnai tampa būtina apibūdinti sistemų, kurių išėjimo signalai priklauso ne tik nuo įėjimų būsenos tam tikru metu, bet ir nuo tam tikros priešistorės, tai yra nuo signalų, elgesį. kurie atėjo į sistemos įvestis anksčiau. Būsenos tiesiog atitinka tam tikrą praeities atmintį, leidžiančią eliminuoti laiką kaip aiškų kintamąjį ir išvesties signalus išreikšti kaip būsenų ir įėjimų funkciją tam tikru metu.

Įprasta informaciją, gautą į automato įvestį, taip pat išvesties informaciją koduoti baigtiniu simbolių rinkiniu. Šis rinkinys vadinamas abėcėle, atskiri simboliai, sudarantys abėcėlę, vadinami raidėmis, o visos tam tikros abėcėlės raidžių sekos yra vadinamos šios abėcėlės žodžiais.

Pavyzdžiui: abėcėlėje X = (x1, x2), susidedančioje iš dviejų raidžių, žodžiai bus: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1 ir kt.

Kartu su žodžiais, susidedančiais iš bent vienos raidės, pristatome žodį, kuriame nėra nė vienos raidės, kurį pažymėsime simboliu e ir pavadinsime tuščią žodį arba tuščią raidę.

Realios baigtinių būsenų mašinos matematinis modelis yra abstrakti mašina, turinti vieną įvesties kanalą ir vieną išvesties kanalą.

Automatas veikia atskirais laiko momentais, tarp kurių T vadinamas taktu. Tuo pačiu metu kiekvienu atskiru laiko momentu į automato įvestį patenka viena įvesties abėcėlės raidė, automatas pereina iš vienos būsenos į kitą ir išvedama viena išvesties abėcėlės raidė. Priklausomai nuo to, kaip nustatyta ciklo T trukmė, yra sinchroninio veiksmo (T=const) ir asinchroninio veiksmo (Tconst) automatai. Daugiausia nagrinėsime sinchroninius automatus, veikiančius diskrečiu laiku, kurie gali būti pažymėti sveikaisiais neneigiamais natūraliaisiais skaičiais, t=0,1,2,3,…., turinčiais ciklo skaičiaus reikšmę.

Norint nurodyti baigtinį automatą S, reikia nurodyti penkių objektų aibę: S(A, X, Y,), kur A = (a0,a1,a2,...,an) yra vidinių būsenų rinkinys. automato, X = (x1, x2 ,…, xm) - įvesties signalų rinkinys (įvesties abėcėlė), xi - įvesties abėcėlės raidė, Y = (y1, y2,…, yk) - išėjimo signalų rinkinys ( išvesties abėcėlė),

Perėjimo funkcija, kuri nustato automato būseną a(t+1), kurioje automatas bus momentu (t+1), priklausomai nuo automato būsenos a(t) ir įvesties signalo x(t) momentu t, ty a(t+1) = ,

Išėjimo funkcija, kuri nustato išėjimo signalo y(t) reikšmę priklausomai nuo automato a(t) būsenos ir įėjimo signalo x(t) momentu t, t.y. y(t) = .

Automatas veikia taip: kiekvienu laiko momentu t yra tam tikroje būsenoje a(t) iš galimų būsenų aibės A. Be to, pradiniu momentu t = 0, jis visada yra būsenoje a(t = 0) = a0. Laike t automatas gauna įėjimo signalą x(t), duoda išėjimo signalą y(t) = ir pereina į kitą būseną a(t+1)=. Kitaip tariant, abstraktus automatas kiekvienai simbolių porai a(t) ir x(t) priskiria vieną su vienu atitikimą simbolių porai a(t+1) ir y(t). Tokie automatai vadinami deterministiniais. Informacijos transformavimui deterministiniuose automatuose keliamos sąlygos.

Informacijos transformacijos deterministiniuose automatuose sąlygos:

1) bet koks įvesties žodis, ilgas l raidžių, konvertuojamas į tokio pat ilgio išvesties žodį.

2) jei kiekvieną kartą prieš duodant įvesties signalus, automatas yra toje pačioje būsenoje, tada, jei pirmieji du įvesties žodžiai sutampa, l 1 raidė, pirmoji išvesties žodžiuose l Taip pat tiks 1 raidė.

Be deterministinių automatų, yra tikimybiniai arba stochastiniai automatai, kuriuose perėjimas iš vienos būsenos į kitą atsitiktinių arba deterministinių įvesties signalų įtakoje vyksta atsitiktinai. Tokių automatų veikimas jau aprašytas perėjimo matrica, kurios elementai yra perėjimų iš vienos būsenos į kitą tikimybės. Daugiausia nagrinėsime deterministinius automatus .

Praktikoje naudojami automatai paprastai skirstomi į dvi klases – tai Mealy automatai ir Moore automatai, pavadinti pirmųjų juos tirti pradėjusių amerikiečių mokslininkų vardu. Automatų veikimas griežtai paklūsta tam tikriems dėsniams (automatų veikimo dėsniams). Automatų veikimo dėsniai aprašomi lygčių sistemomis:

Miles mašina:

a(t + 1) =
y(t) =

Moore mašina:

a(t + 1) =

Išskirtinis Mealy automatų bruožas yra tas, kad jų išėjimo signalai priklauso ir nuo automato būsenos, ir nuo įvesties signalo vertės. Moore mašinose išvesties signalai y(t) kiekvienu atskiru laiku t yra vienareikšmiškai nustatomos pagal automato būseną tuo pačiu metu ir nepriklauso nuo įvesties signalo vertės.

Taikant lentelių nustatymo metodą, Mealy automatas aprašomas dviem lentelėmis: perėjimo lentele ir išvesties lentele.

Šokinėjimo stalas

Šių lentelių eilutės atitinka įvesties signalus x(t), o stulpeliai yra būsenos. Stulpelio ai ir eilutės sankirtoje x j pereinamojoje lentelėje nustatoma būsena a s = [ a aš, x j] į kurį automatas pereis iš būsenos a i veikiamas signalo x j; o išėjimų lentelėje – šį perėjimą atitinkantis išėjimo signalas y g = [ a aš, x j]. Kartais Mealy automatui pateikiama kombinuota perėjimų ir išėjimų lentelė, kai kuriais atvejais tai yra patogiau.

Kombinuota „Mealy“ mašinos perėjimų ir išėjimų lentelė:

Nurodant perėjimo ir išvesties lenteles visiškai aprašomas baigtinio automato veikimas, nes nurodomos ne tik pačios perėjimo ir išvesties funkcijos, bet ir visos trys abėcėlės: įvesties, išvesties ir būsenos abėcėlė. Kadangi Moore mašinoje išėjimo signalą vienareikšmiškai lemia mašinos būsena, jam nurodyti reikia tik vienos lentelės, kuri vadinama Moore mašinos pažymėta pereinamojo laikotarpio lentele.

Pažymėta Moore mašinos perėjimo lentelė:

Šioje lentelėje kiekvienas stulpelis yra priskirtas, išskyrus būseną a i, taip pat išvesties signalas y(t) = (a(t)), atitinkantis šią būseną. Moore mašinos perėjimo lentelė vadinama pažymėta, nes kiekviena būsena yra pažymėta išvesties signalu.

Taikant grafinį metodą, automatas apibrėžiamas naudojant grafiką. Šis metodas pagrįstas nukreiptų sujungtų grafikų naudojimu. Grafų viršūnės atitinka automato būsenas, o lankai – perėjimus tarp jų. Dvi grafiko viršūnės a aš ir a s yra sujungti lanku, nukreiptu iš a aš į a s jei automatas turi perėjimą iš a aš įeinu a s, tai yra a s = ( a aš, x j). Mealy mašinoje lankas pažymėtas įvesties signalu x j, kuris sukėlė perėjimą ir išvesties signalą y g, kuris vyksta pereinant. Apskritimo viduje, žyminčio grafiko viršų, parašyta būsena.

„Mealy“ mašinos grafikas:

Moore automato grafikas

2.3 Daliniai automatai

Inžinerinėje praktikoje dažnai susiduriama su automatais, kurių įėjimais niekada netaikomos kai kurios signalų sekos. Tokios sekos bus vadinamos uždraustais tam tikro automato įvesties žodžiais, o pats automatas – daliniu automatu. Daliniam automatui perėjimo ir išvesties funkcijos apibrėžtos ne visose porose ai, xj. Vietoje neapibrėžtų būsenų ir išvesties signalų dedamas brūkšnys. Sintezės metu dalinis automatas dažniausiai apibrėžiamas iš naujo, kad jo grandinės įgyvendinimas būtų kuo paprastesnis.

Dalinės „Mealy“ mašinos perėjimo ir išvesties lentelės pavyzdys

Iš šuolių stalo matyti, kad T-flip-flop turi pilna sistema perėjimai ir išėjimai, nes kiekvienai būsenų porai (0-0, 0-1, 1-0,

1-1) yra įvesties signalas, užtikrinantis perėjimą iš vienos būsenos į kitą. Be to, kiekviena automato būsena pažymėta skirtingu išėjimo signalu. Praktikoje vietoje pažymėtų perėjimų lentelių patogiau naudoti vadinamąsias elementariųjų automatų pereinamąsias matricas.

Perėjimo matrica:

Perėjimo matrica nustato signalų reikšmes elementaraus automato įėjimais, pateikdama kiekvieną iš keturių galimų perėjimų. Čia Q(t) ir Q(t+1) yra automato būsenos atitinkamai momentais t ir t+1. Kadangi T flip-flop turi vieną įvestį, o galimų perėjimų skaičius yra keturi, perėjimų matrica turi keturias eilutes.

Norėdami analitine forma užrašyti T trigerio veikimo dėsnį, naudodami perėjimo matricą sudarysime Veitch diagramą:

Iš diagramos turime:


=> (T(t) + Q(t) ) 2 modas

Kadangi ši formulė sutampa su perjungimo funkcijos modulo du analitiniu žymėjimu, T-flip-flop dažnai vadinamas apvertimu su skaičiavimo įėjimu T, o įvesties signalas T įėjime yra skaičiavimo signalas. Praktikoje be asinchroninio T-flip-flop, kurio veikimą nagrinėjome, naudojamas ir sinchroninis T-flip-flop, kuris, skirtingai nei asinchroninis, keičia savo būsenas tik esant T = 1 ir C. = 1. Jei bent vienas iš šių signalų yra lygus nuliui, trigeris išsaugo savo būseną. Įvestis C vadinama laikrodžio įvestimi.

Kombinuota grandinė, paaiškinanti sinchroninės sistemos veikimą ir paskirtį

T-flip-flop pavaizduoti paveikslėlyje:

2.5 D gaidukas

D trigeris (delsinimo trigeris) yra elementarus Moore automatas, turintis dvi stabilias būsenas ir vieną įvestį D, kad Q(t+1) = D(t). Pavadinimas D-trigeris kilęs iš Angliškas žodis„delay“ – delsimas. Iš apibrėžimo išplaukia, kad trigerio būsena momentu t+1 pakartoja įėjimo signalo D(t) reikšmę momentu t (taigi ir vėlavimo trigerio pavadinimas).

D-flip-flop perėjimo matrica:

Asinchroninių ir sinchroninių D-flip-flopų pavadinimai:

Sinchroniniame D trigeryje su C=0 trigeris savo būsenos nekeičia, o esant C=1 veikia taip pat kaip ir asinchroninis, t.

Q(t+1)=D(t)C(t) v Q(t)

Asinchroninis D flip-flop praktinė vertė neturi.

D-trigerio grafikas

2.6 RS šlepetas

RS šleifas yra bistabili Moore mašina, turinti du įėjimus R ir S, kad kai S = 1 ir R = 0, apverstas įgauna 1 būseną, o kai R = 1 ir S = 0 - 0. būsena, priimta flip-flop, įėjimas S vadinamas vienu įėjimu, o įėjimas R vadinamas nuliu.

RS flip-flop perėjimo matrica:

Signalų R=1 ir S=1 derinys yra draudžiamas, todėl perėjimas flip-flop su tokiomis įvesties signalų reikšmėmis nėra apibrėžtas. Trigerio perėjimas nuo 0 iki 0 galimas dviem įvesties signalų kombinacijomis: R=0, S=0 ir R=1, S=0. Todėl stulpelio R flip-flop perėjimo matricos RS pirmoje eilutėje nustatomas kintamasis b1, kuris gali turėti dvi reikšmes 0 v 1. Panašiai perėjimas iš būsenos 1 į 1 galimas ir su dvi įvesties signalų kombinacijos: R=0, S=0 ir R= 0, S=1. Kadangi tokio perėjimo metu signalo reikšmė įėjime S yra abejinga, kintamasis b2 rašomas apatinėje perėjimo matricos eilutėje S stulpelyje. Perėjimo matrica gali būti naudojama RS trigerio grafikui sudaryti.

Automatai, kurie gali pereiti iš vienos būsenos į kitą veikiant kelioms įvesties signalų kombinacijoms, vadinami automatais su pertekline perėjimo sistema. Atleidimas gali būti naudojamas sintezės procese, siekiant supaprastinti grandinę, suteikiant kintamiesiems b1 ir b2 tokias reikšmes, kurios leidžia sumažinti elementų skaičių. Todėl, jei dviejų elementarių automatų grandinės yra lygiavertės sudėtingumo, tada pirmenybė teikiama automatui su dideliu perėjimo sistemos pertekliumi.

Analitine forma užrašykime RS flip-flop veikimo dėsnį, kuriam pagal perėjimo matricą sudarome Veitch diagramą:

2.7 JK šlepetės

JK apverstas yra Moore'o automatas su dviem stabiliomis būsenomis ir dviem įėjimais J ir K, kuris, esant sąlygai J * K = 1, apverčia ankstesnę būseną (t. y. kai J*K=1, Q(t+1) ) = Q( t)), o kitais atvejais jie veikia pagal trigerio tiesos lentelę RS, o įvestis J yra lygiavertė įėjimui S, o įvestis K lygiavertė įėjimui R. Šis trigeris Nr. ilgiau turi draudžiamą įvesties signalų derinį ir jo tiesos lentelę, tai yra, priklausomybė Q (t+1) = f turi tokią formą:

JK flip-flop tiesos lentelė:

Iš šios lentelės galite sukurti Veitch diagramą Q(t + 1), kuri gali būti naudojama sumažinimui, ir perėjimo matricą:

JK flip-flop perėjimo matrica:

Integrinėje grandinėje naudojami tik laikrodžio (sinchroniniai) trigeriniai JK, kurie, kai C=0, išlaiko savo būseną, o kai C=1 veikia kaip asinchroniniai trigeriniai JK.

2.8 Universalus gaidukas

JK šlepetės priklauso universalių šlepečių kategorijai, nes jos pagrindu, paprastu išoriniu perjungimu, galima sukurti RS-, D- ir T-flip-flop. RS flip-flop gaunamas iš JK šlepetės tiesiog apribojant įvesties signalų derinį J=K=1, nes šis derinys draudžiamas RS šlepetei.

Skaičiavimo šleifas, pagrįstas JK šlepetėmis, gaunamas sujungus įvestis J ir K.

Uždelsimo flip-flop (D-flip-flop) sukuriamas keitiklį prijungus prie įvesties K, kuri tiekiama tuo pačiu signalu kaip į įėjimą J. Šiuo atveju įėjimas J veikia kaip įėjimas D, o visas įrenginys įgyvendina D. -flip-flop perėjimo lentelė.

Išvada

Šiame darbe buvo aprašyti pagrindiniai automatų veikimo principai. Tuo pačiu metu automatai buvo suskirstyti į abstrakčius ir automatus, naudojamus mikroschemoje. Taip pat automatų teorija yra glaudžiai susijusi su algoritmų teorija.

Dėl to abstrakčių automatų tyrimas paskatino aktyvų vystymąsi informatika ir mikroschemų inžinerija, atitinkamai.

Naudotų šaltinių sąrašas

1. Diskretioji matematika. Pamoka. Sayapin A.V., Slivina T.A. SibGAU redakcinis ir leidybos skyrius. Krasnojarskas 2010 163s.

2. Skaitmeninių automatų teorijos paskaitos [ Elektroninis šaltinis]. Paskaitos [Svetainė]. URL: http://www.twirpx.com/file/455856/

Priglobta Allbest.ru

...

Panašūs dokumentai

Aproksimacijos teorija kaip matematikos šaka, nagrinėjanti matematinių objektų apytikslio atvaizdavimo galimybę. Interpoliacijos daugianario konstravimas. Aproksimacija dalimis daugianario funkcijomis. Programos algoritmas ir jo įgyvendinimas.

Kursinis darbas, pridėtas 2015-10-18

Abstrakčių, struktūrinių ir dalinių baigtinių automatų aprašymas. Sinchroninių baigtinių automatų, turinčių įvairių tipų trigerius, veikimas, jų žadinimo signalų apibrėžimas. Kanoninio struktūrinės sintezės metodo pavyzdys. Durų spynos schema.

pamoka, pridėta 2009-06-07

Tikimybių teorija – matematikos šaka, tirianti atsitiktinių reiškinių dėsningumus: atsitiktinius įvykius, atsitiktinius dydžius, jų savybes ir operacijas su jais. Tikimybių teorijos uždavinių sprendimo metodai, matematinių lūkesčių ir dispersijos apibrėžimas.

testas, pridėtas 2012-02-04

Žaidimų teorija – matematikos šaka, kurios objektas – matematinių modelių, leidžiančių priimti optimalius sprendimus konflikte, tyrimas. Iteracinis Brown-Robinson metodas. Monotoninis iteracinis algoritmas sprendžiant matricinius žaidimus.

baigiamasis darbas, pridėtas 2007-08-08

Grafų teorija kaip diskrečiosios matematikos šaka, tirianti baigtinių aibių savybes su nurodytais ryšiais tarp jų elementų. Pagrindinės grafų teorijos sąvokos. Gretimo ir dažnumo matricos ir jų praktinis naudojimas analizuojant sprendimus.

santrauka, pridėta 2011-06-13

Kompiuterinių technologijų tema – problemos, kurias gali išspręsti mašinos. Užduoties sudėtingumo matavimas. Sujungti rūšiavimo algoritmą. Polinominės ir nepolinominės problemos. Nedeterministinio algoritmo samprata. Grafinis vaizdavimas klasifikacija.

pristatymas, pridėtas 2013-10-22

Diskrečiosios Furjė transformacijos savybės, pateiktos matematinių formulių pavidalu, labiausiai atitinkančios skaitmeninę informacijos apdorojimo technologiją. Greitojo Furjė transformacijos (FFT) algoritmas, jo svarba programavimui.

pamoka, pridėta 2014-11-02

santrauka, pridėta 2011-01-13

Tam tikros diskrečiosios matematikos dalies tyrimas. 5 užduočių nagrinėjama tema sprendimas su metodiniu aprašymu. Kompiliavimo ir įgyvendinimo metodas tiriamos temos algoritmo programos forma. Programinės įrangos sąsajos kūrimo procedūra ir nurodymai.

Kursinis darbas, pridėtas 2011-04-27

Geometrija kaip matematikos šaka, tirianti erdvinius santykius ir formas, taip pat kitus santykius ir formas, savo struktūra panašius į erdvinius. Pagrindiniai šio mokslo formavimosi ir raidos etapai, šiuolaikiniai pasiekimai ir perspektyvos.