Automaattiteoria, äärelliset automaatit
Erilaisten koneiden rakenne, suunnittelu ja toimintaperiaate määräytyvät suurelta osin sen toiminnallisen tarkoituksen perusteella. Erottele teknologian, liikenteen, tietojenkäsittelyn, sotilaalliset ja muut koneet. Kokonaisia automaattisia komplekseja, jotka on suunniteltu suorittamaan monimutkaisia teknologisia prosesseja, otetaan laajalti käyttöön eri aloilla. Automaatteja suunnitellaan ja rakennetaan suorittamaan erilaisia loogisia toimintoja (loogisia koneita).
Automaattien teoria — kybernetiikkaosasto, joka syntyi digitaalisten tietokoneiden ja ohjauskoneiden tekniikan vaatimusten vaikutuksesta. Automaattiteoriassa tutkitut diskreetit automaatit ovat abstrakteja malleja todellisista järjestelmistä (sekä teknisistä että biologisista), jotka käsittelevät diskreettiä (digitaalista) informaatiota diskreetissä aikavaiheessa.
Automaattiteoria perustuu tarkkoihin matemaattisiin käsitteisiin, jotka formalisoivat intuitiivisia ajatuksia automaatin toiminnasta (käyttäytymisestä) ja sen rakenteesta (sisäinen rakenne).
Tässä tapauksessa informaatiomuunnos ymmärretään aina operaatioksi, joka muuntaa syöteaakkoston kirjaimista koostuvat syöttösekvenssit lähtöaakkoston kirjaimista koostuviksi lähtösarjoiksi.
Matemaattisen logiikan, algebran, todennäköisyysteorian, kombinatoriikan ja graafiteorian laitteistoa käytetään laajalti.
Automaattiteorian eräissä osissa ongelma (automaattien rakenneteoria) kasvoi rele-koskettimien teoriasta, joka alkoi muotoutua 1930-luvun lopulla. mukaan lukien loogisen algebran menetelmät.
Automaattien rakenneteoriassa tutkitaan erilaisia kaavioita, jotka on suunniteltu kuvaamaan kuinka monimutkainen automaatio luodaan yksinkertaisemmista komponenteista (elementeistä), jotka on yhdistetty oikein järjestelmään.
Toinen suunta, jota kutsutaan abstraktiksi automaatiteoriaksi, tutkii automaattien käyttäytymistä (eli niiden suorittaman tiedon muuntamisen luonnetta), samalla kun se irtaantuu niiden sisäisen rakenteen erityispiirteistä, ja syntyi 1950-luvulla.
Automaattien abstraktin teorian puitteissa käsitteiden "automaatti" ja "kone" sisältö on oleellisesti umpeutunut automaatin suorittaman tiedon muuntamisen standardikuvaukseen. Tällainen muunnos voi olla deterministinen, mutta se voi myös olla luonteeltaan todennäköisyys.
Eniten tutkittuja ovat deterministiset koneet (automaatit), joihin kuuluvat äärelliset automaatit – automaatioteorian pääasiallinen tutkimuskohde.
Äärillisen tilan koneelle on tunnusomaista rajallinen määrä muistia (sisäisten tilojen määrä) ja se määritellään siirtymäfunktiolla.Tietyllä järkevällä idealisoinnilla kaikkia nykyaikaisia matemaattisia koneita ja jopa aivoja voidaan pitää niiden toiminnan kannalta äärellisinä automaateina.
Termejä "peräkkäinen kone", "Milly-automaatti", "Mooren automaatti" käytetään kirjallisuudessa (eikä kaikki kirjoittajat yhtenäisesti) synonyymeinä termille "äärellinen automaatti" tai korostamaan tiettyjä piirteitä äärellisen siirtymäfunktioissa. automaatti.
Automaatti, jolla on rajoittamaton muisti, on Turingin kone, joka pystyy suorittamaan (mahdollisesti) minkä tahansa tehokkaan tiedon muunnoksen. Käsite "Turingin kone" syntyi aikaisemmin kuin "äärellisen tilan koneen" käsite, ja sitä tutkitaan pääasiassa algoritmien teoriassa.
Abstrakti automaattiteoria liittyy läheisesti tunnettuihin algebrallisiin teorioihin, esimerkiksi puoliryhmäteoriaan. Sovelletusta näkökulmasta kiinnostavat tulokset, jotka kuvaavat automaatissa tapahtuvaa tiedon muuntamista muistin koon suhteen.
Näin on esimerkiksi automaatikokeiluongelmissa (E.F. Mooren teokset jne.), joissa yhtä tai toista tietoa automaatin siirtymäfunktioista tai sen muistin kapasiteetista saadaan automaatin tuloksista. kokeiluja.
Toinen tehtävä on laskea lähtösekvenssien jaksot käytettävissä olevan tiedon perusteella automaatin muistin koosta ja syöttöjaksojen jaksoista.
Erittäin tärkeää on menetelmien kehittäminen äärellistilakoneiden muistin minimoimiseksi ja niiden käyttäytymisen tutkimiseksi satunnaisissa ympäristöissä.
Abstraktissa automaattiteoriassa synteesiongelma on seuraava.Jollakin selvästi formalisoidulla kielellä ehdot on kirjoitettu suunnitellun automaatin käyttäytymiselle (automaatissa esitetylle tapahtumalle). Tässä tapauksessa on tarpeen kehittää menetelmiä, jotka kunkin kirjallisen ehdon mukaan:
1) selvittää, onko olemassa sellaista tilakonetta, jonka muuntama tieto täyttää tämän ehdon;
2) jos kyllä, niin tällaisen äärellisen tilakoneen siirtymäfunktiot konstruoidaan tai sen muistin koko arvioidaan.
Synteesitehtävän ratkaisu tällaisessa formulaatiossa edellyttää alustavasti sopivan kielen luomista automaatin toimintaolosuhteiden tallentamiseksi kätevillä algoritmeilla siirtymiseen tallentamisesta transitiivisiin toimintoihin.
Automaattien rakenneteoriassa synteesiongelma koostuu tietyn tyyppisten elementtien ketjun rakentamisesta, joka toteuttaa siirtymäfunktioidensa antaman äärellisen automaatin. Tässä tapauksessa he yleensä ilmoittavat jonkin optimaalisuuskriteerin (esimerkiksi elementtien vähimmäismäärän) ja pyrkivät saamaan optimaalisen kaavion.
Kuten myöhemmin kävi ilmi, tämä tarkoittaa, että osa aiemmin kehitetyistä menetelmistä ja käsitteistä liittyen rele-kosketinpiireihin soveltuu myös toisen tyyppisiin piireihin.
Sähkötekniikan kehityksen yhteydessä yleisimpiä ovat suunnitelmat toiminnallisista elementeistä (loogiset verkot). Logiikkaverkkojen erikoistapaus ovat abstraktit hermoverkot, joiden elementtejä kutsutaan neuroneiksi.
Monia synteesimenetelmiä on kehitetty riippuen piirien tyypistä ja tiedon muuntamisesta, jolle ne on tarkoitettu (Relelaitteiden synteesi).
Katso -Yhdistelmäpiirien minimointi, Carnot-kartat, piirisynteesi
Äärimmäisen tilan kone — matemaattinen malli ohjausjärjestelmästä, jonka muistikoko on kiinteä (joka ei voi kasvaa käytön aikana).
Äärillisen tilan koneen käsite on matemaattinen abstraktio, joka luonnehtii ohjausjärjestelmien joukon yleisiä ominaisuuksia (esimerkiksi monisilmukkarelelaite). Kaikilla tällaisilla järjestelmillä on yhteisiä piirteitä, jotka on luonnollista hyväksyä äärellisen automaatin määritelmäksi.
Jokaisessa valmiissa automaatissa on sisäänkäynti, joka on alttiina ulkoisille vaikutuksille ja sisäisille elementeille. Sekä syötteille että sisäisille elementeille on olemassa kiinteä määrä erillisiä tiloja, jotka ne voivat ottaa.
Tulon ja sisäisten elementtien tilojen muutos tapahtuu diskreeteillä ajanhetkillä, joiden välisiä aikavälejä kutsutaan tikkeiksi. Nauhan lopussa oleva sisätila (sisäosien tila) määräytyy kokonaan sisäisen tilan ja nauhan alussa olevan tulon tilan mukaan.
Kaikki muut äärellisen automaatin määritelmät voidaan lyhentää tähän ominaisuuteen, erityisesti määritelmät, joissa oletetaan, että äärellisellä automaatilla on lähtö, joka riippuu automaatin sisäisestä tilasta tietyllä hetkellä.
Tällaisen ominaisuuden kannalta sen tulojen ja sisäisten tilojen luonteella ei ole merkitystä täydellisen automaatin kuvauksen kannalta. Syötteiden ja tilojen sijaan voit katsoa niiden numeroita satunnaisessa numeroinnissa.
Tilakone asetetaan, jos sen sisäisen tilanumeron riippuvuus edellisestä sisäisestä tilanumerosta ja edellisestä syötetyn tilanumerosta on määritetty. Tällainen tehtävä voi olla finaalipöydän muodossa.
Toinen yleinen tapa määritellä täydellinen automaatti on rakentaa ns siirtymäkaaviot. Syöttötiloja kutsutaan usein yksinkertaisesti syötteiksi ja sisäiset tilat ovat yksinkertaisesti tiloja.
Äärillinen kone voi olla sekä teknisten laitteiden että joidenkin biologisten järjestelmien malli. Ensimmäisen tyyppisiä automaatteja ovat esimerkiksi relelaitteet ja erilaiset elektroniset tietokoneet, mm. ohjelmoitavat logiikkaohjaimet.
Relelaitteen tapauksessa tulotilojen roolia ovat relelaitteen herkkien elementtien tilojen yhdistelmillä (jokainen tällaisten tilojen yhdistelmä on "kompleksitila", jolle on tunnusomaista kaikkien herkkien elementtien ilmaisu). nämä erilliset tilat, jotka heillä on tietyllä hetkellä). Vastaavasti relelaitteen välielementtien tilojen yhdistelmät toimivat sisäisinä tiloina.
Ohjelmoitava logiikkaohjain (PLC) on esimerkki reletoimintolaitteesta, jota voidaan kutsua itsenäiseksi tilakoneeksi.
Itse asiassa, kun ohjelma on syötetty PLC:hen ja säädin on alkanut laskea, se ei ole alttiina ulkoisille vaikutuksille ja jokainen seuraava tila määräytyy täysin sen edellisen tilan mukaan. Voidaan olettaa, että tulolla on sama tila joka kellojaksolla.
Sitä vastoin mitä tahansa äärellisen tilan konetta, jolla on ainoa mahdollinen tulotila, kutsutaan luonnollisesti autonomiseksi, koska tässä tapauksessa ulkoinen ympäristö ei sisällä informaatiota, joka ohjaa sen käyttäytymistä.
Katso myös:
Mikroprosessorijärjestelmien käyttö sähkötekniikassa PLC:n käytön esimerkkinä