Valtion koneiden ymmärtäminen

Johdatus tietojenkäsittelytieteen käsitteisiin

Tietojenkäsittelytieteen avulla voimme ohjelmoida, mutta on mahdollista tehdä paljon ohjelmointia ymmärtämättä taustalla olevia tietojenkäsittelytieteen käsitteitä.

Tämä ei ole aina huono asia. Kun ohjelmoimme, työskentelemme paljon korkeammalla abstraktiotasolla.

Kun ajamme autoa, huolehdimme vain kahdesta tai kolmesta polkimesta, vaihdekytkimestä ja ohjauspyörästä. Voit käyttää autoa turvallisesti ilman selkeää käsitystä sen toiminnasta.

Jos kuitenkin haluat käyttää autoa sen kyvykkyyden rajoissa, sinun on tiedettävä paljon enemmän autoista kuin vain kolmesta polkimesta, vaihteistosta ja ohjauspyörästä.

Sama pätee ohjelmointiin. Paljon jokapäiväistä työtä voidaan suorittaa vain vähän tai ei lainkaan tietämystä tietojenkäsittelystä. Sinun ei tarvitse ymmärtää laskennallista teoriaa rakentaaksesi "Ota yhteyttä" -lomakkeen PHP: hen.

Jos kuitenkin aiot kirjoittaa koodia, joka vaatii vakavaa laskentaa, sinun on ymmärrettävä hieman enemmän siitä, miten laskenta toimii konepellin alla.

Tämän artikkelin tarkoituksena on antaa tietyt perustiedot laskennalle. Jos on kiinnostusta, voin seurata joitain edistyneempiä aiheita, mutta haluan nyt tarkastella yhden yksinkertaisimman abstraktin laskennallisen laitteen - äärellisen tilakoneen - logiikkaa .

Äärelliset tilakoneet

Äärellinen tilakone on matemaattinen abstraktio, jota käytetään algoritmien suunnitteluun.

Yksinkertaisemmin sanottuna tilakone lukee syötesarjan. Kun se lukee syötteen, se vaihtaa toiseen tilaan. Kukin tila määrittää, mihin tilaan tietyt tulot vaihdetaan. Tämä kuulostaa monimutkaiselta, mutta se on todella yksinkertaista.

Kuvittele laite, joka lukee pitkän paperin. Jokaista tuumaa paperia kohti siihen on painettu yksi kirjain - joko kirjain "a" tai "b".

Kun tilakone lukee jokaisen kirjaimen, se muuttaa tilaa. Tässä on hyvin yksinkertainen tilakone:

Ympyrät ovat ” tiloja ”, joissa kone voi olla. Nuolet ovat siirtymiä . Joten jos olet tilassa s ja luet a: n, siirryt tilaan q . Jos luet b: n, pysyt tilassa s .

Joten jos aloitamme s: llä ja luemme paperinauhan vasemmalta oikealle, luemme 'a': n ja siirrymme tilaan q .

Sitten luemme 'b' ja siirrymme takaisin tilaan s .

Toinen 'b' pitää meidät s: ssä , jota seuraa 'a' - joka siirtää meidät takaisin q- tilaan. Tarpeeksi yksinkertainen, mutta mitä järkeä siinä on?

On käynyt ilmi, että voit ajaa nauhan tilakoneen läpi ja kertoa jotain kirjainsekvenssistä tutkimalla tilaa, johon päädyt.

Edellä olevassa yksinkertaisessa tilakoneessamme, jos päätämme tilaan s , nauhan on lopputtava b-kirjain. Jos loppumme tilaan q , nauha päättyy a-kirjaimella.

Tämä saattaa kuulostaa turhalta, mutta tämäntyyppisellä lähestymistavalla voidaan ratkaista todella paljon ongelmia. Hyvin yksinkertainen esimerkki olisi määrittää, sisältääkö HTML-sivu nämä tunnisteet tässä järjestyksessä:

Tilakone voi siirtyä tilaan, joka osoittaa, että se on lukenut html-tunnisteen, silmukan, kunnes se pääsee päätunnisteeseen, silmukka, kunnes pääsee päähän -tunnisteeseen, jne.

Jos se onnistuu lopulliseen tilaansa, sinulla on kyseiset tunnisteet oikeassa järjestyksessä.

Rajoitettujen tilojen koneita voidaan käyttää myös monien muiden järjestelmien edustamiseen - kuten pysäköintimittarin mekaniikka, pop-kone, automaattinen kaasupumppu ja kaikenlainen muu.

Deterministiset äärellisen tilan koneet

Tähän mennessä tarkastelemamme tilakoneet ovat kaikki deterministisiä tilakoneita. Mistä tahansa tilasta sallitulle syötteelle on vain yksi siirtymä. Toisin sanoen, ei voi olla kahta polkua, jotka johtavat tilasta, kun luet a-kirjainta. Aluksi tämä kuulostaa typerältä jopa tehdä tämä ero.

Mitä hyötyä on joukosta päätöksiä, jos sama panos voi johtaa siirtymiseen useampaan kuin yhteen tilaan? Et voi kertoa tietokoneelle, if x == truesitten suorittaa doSomethingBigtai suorittaa doSomethingSmall, vai mitä?

No, sinä voit tavallaan valtion koneella.

Tilakoneen tulos on sen lopullinen tila. Se käy läpi kaiken prosessoinnin ja sitten lukee lopullisen tilan ja sitten tehdään toiminto. Valtion kone ei tee mitään, kun se siirtyy tilasta toiseen.

Se prosessoi, ja kun se pääsee loppuun, tila luetaan ja jokin ulkoinen laukaisee halutun toiminnan (esimerkiksi soodakannun annostelu). Tämä on tärkeä käsite, kun on kyse ei-deterministisistä rajallisista tilakoneista.

Ei-deterministiset äärellisen tilan koneet

Ei-deterministiset rajallisen tilan koneet ovat rajallisia tilakoneita, joissa annettu syöttö tietystä tilasta voi johtaa useampaan kuin yhteen eri tilaan.

Oletetaan esimerkiksi, että haluamme rakentaa rajallisen tilakoneen, joka tunnistaa kirjainmerkkijonot, jotka:

  • Aloita a-kirjaimella
  • ja niitä seuraa sitten nolla tai useampi b-kirjaimen esiintyminen
  • tai nolla tai useampi c-kirjaimen esiintyminen
  • aakkoset seuraavan kirjaimen kanssa.

Kelvolliset merkkijonot olisivat:

  • abbbbbbbbbc
  • abbbc
  • acccd
  • acccccd
  • ac (b: n nolla esiintymää)
  • ad (nolla esiintymää c)

Joten se tunnistaa kirjaimen "a", jota seuraa nolla tai enemmän samaa "b" tai "c" kirjainta, jota seuraa seuraava aakkoset.

Hyvin yksinkertainen tapa esittää tämä on tilakoneella, joka näyttää alla olevalta, jossa t- tilan lopullinen tila tarkoittaa, että merkkijono on hyväksytty ja vastaa mallia.

Näetkö ongelman? Aloituskohdasta s emme tiedä kumpa polkua. Jos luemme a-kirjaimen, emme tiedä, menisikö tilaan q vai r.

On olemassa muutama tapa ratkaista tämä ongelma. Yksi on palata takaisin. Kävelet yksinkertaisesti kaikki mahdolliset polut ja jätät huomiotta tai poistu niistä, joihin juutut.

Pohjimmiltaan suurin osa shakkipeleistä toimii. He tarkastelevat kaikkia mahdollisuuksia - ja kaikkia näiden mahdollisuuksien mahdollisuuksia - ja valitsevat polun, joka antaa heille eniten etuja vastustajaansa nähden.

Toinen vaihtoehto on muuntaa ei-deterministinen kone deterministiseksi koneeksi.

Yksi ei-deterministisen koneen mielenkiintoisista ominaisuuksista on se, että on olemassa algoritmi minkä tahansa ei-deterministisen koneen muuttamiseksi deterministiseksi. Se on kuitenkin usein paljon monimutkaisempi.

Meille onneksi yllä oleva esimerkki on vain hieman monimutkaisempi. Itse asiassa tämä on tarpeeksi yksinkertainen, jotta voimme muuttaa sen päämme deterministiseksi koneeksi ilman muodollisen algoritmin apua.

Alla oleva kone on deterministinen versio yllä olevasta ei-deterministisestä koneesta. Alla olevassa koneessa lopullinen tila t tai v saavutetaan millä tahansa merkkijonolla, jonka kone hyväksyy.

Ei-deterministisessä mallissa on neljä tilaa ja kuusi siirtymää. Deterministisessä mallissa on kuusi tilaa, kymmenen siirtymää ja kaksi mahdollista lopputilaa.

Se ei ole niin paljon enemmän, mutta monimutkaisuus kasvaa yleensä eksponentiaalisesti. Kohtalaisen kokoinen ei-deterministinen kone voi tuottaa ehdottoman suuren deterministisen koneen.

Säännölliset lausekkeet

Jos olet tehnyt minkä tahansa tyyppisen ohjelmoinnin, olet todennäköisesti kohdannut säännöllisiä lausekkeita. Säännölliset lausekkeet ja rajalliset tilakoneet ovat toiminnallisesti vastaavia. Kaikki, mitä voit hyväksyä tai sovittaa säännölliseen lausekkeeseen, voidaan hyväksyä tai sovittaa tilakoneeseen.

Esimerkiksi edellä kuvattu malli voidaan sovittaa säännöllisen lausekkeen kanssa: a(b*c|c*d)

Säännöllisillä lausekkeilla ja rajallisilla tilakoneilla on myös samat rajoitukset. Erityisesti molemmat voivat sovittaa tai hyväksyä vain malleja, joita voidaan käsitellä rajallisella muistilla.

Joten minkä tyyppisiä malleja ne eivät voi sovittaa yhteen? Oletetaan, että haluat sovittaa vain merkkijonot 'a' ja 'b', joissa on useita a: ta ja yhtä monta b: tä. Tai n 'a: n jälkeen n ' b: n, jossa n on jokin luku.

Esimerkkejä ovat:

  • ab
  • aabb
  • aaaaaabbbbbb
  • aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

Aluksi tämä näyttää helpolta työltä rajalliselle tilakoneelle. Ongelmana on, että tilat loppuvat nopeasti, tai joudut olettamaan rajattoman määrän tiloja - missä vaiheessa se ei ole enää äärellinen tilakone.

Oletetaan, että luot äärellisen tilakoneen, joka voi hyväksyä jopa 20 'a: n ja sen jälkeen 20' b: n. Se toimii hyvin, kunnes saat 21 'a: n merkkijonon ja sen jälkeen 21' b: n - jolloin sinun on kirjoitettava kone uudelleen käsittelemään pidempää merkkijonoa.

Kaikille tunnistamillesi merkkijonoille on vain vähän pidempi, jota koneesi ei tunnista, koska muisti loppuu.

Tämä tunnetaan nimellä Pumping Lemma, joka sanoo periaatteessa: "Jos kuviossasi on osa, joka voidaan toistaa (kuten yksi) yllä, kuvio ei ole säännöllinen".

Toisin sanoen, ei säännöllinen lauseke eikä äärellinen kone voidaan rakentaa joka tunnistaa kaikki jouset, jotka eivät vastaa mallia.

Jos katsot tarkkaan, huomaat, että tämän tyyppinen kuvio, jossa jokaisella a: lla on vastaava b, näyttää hyvin samanlaiselta kuin HTML. Missä tahansa tunnisteparissa voi olla mikä tahansa määrä muita vastaavia tunnisteita.

Joten, vaikka saatat pystyä käyttämään säännöllistä lauseketta tai äärellisen tilakoneen tunnistamaan, onko HTML-sivulla yksi ; ja elementit oikeassa järjestyksessä, et voi käyttää säännöllistä lauseketta kertoaksesi, onko koko HTML-sivu kelvollinen vai ei - koska HTML ei ole säännöllinen kuvio. ml >, ead>

Turingin koneet

Joten miten tunnistat epäsäännölliset mallit ?

On olemassa teoreettinen laite, joka on samanlainen kuin tilakone, nimeltään Turingin kone. Se on samanlainen kuin äärellisen tilan kone, koska siinä on paperiliuska, jonka se lukee. Mutta Turingin kone voi poistaa ja kirjoittaa paperinauhalle.

Turingin koneen selittäminen vie enemmän tilaa kuin meillä on, mutta rajallisten tilakoneiden ja säännöllisten lausekkeiden keskustelussa on muutamia tärkeitä seikkoja.

Turingin koneet ovat laskennallisesti täydellisiä - mikä tarkoittaa mitä tahansa, mikä voidaan laskea, voidaan laskea Turingin koneella.

Koska Turingin kone voi kirjoittaa sekä lukea paperinauhalta, se ei rajoitu rajalliseen määrään tiloja. Paperinauhan voidaan olettaa olevan äärettömän pitkä. Tietysti todellisissa tietokoneissa ei ole loputon määrä muistia. Mutta ne sisältävät yleensä tarpeeksi muistia, joten et saavuta rajaa niiden käsittelemien ongelmien tyypille.

Turing Machines antaa meille kuvitteellisen mekaanisen laitteen, jonka avulla voimme visualisoida ja ymmärtää kuinka laskennallinen prosessi toimii. Se on erityisen hyödyllinen laskennan rajojen ymmärtämisessä. Jos on kiinnostusta, teen tulevaisuudessa toisen artikkelin Turing Machinesista.

Miksi tällä on merkitystä?

Joten, mikä järkeä? Kuinka tämä auttaa sinua luomaan seuraavan PHP-lomakkeen?

Rajoituksista riippumatta tilakoneet ovat erittäin keskeinen käsite laskennassa. Erityisesti on merkityksellistä, että kaikilla ei-deterministisillä tilakoneilla, jotka voit suunnitella, on olemassa deterministinen tilakone, joka tekee saman.

Tämä on avainasemassa, koska se tarkoittaa, että voit suunnitella algoritmin sillä tavalla, mikä on helpoin ajatella. Kun sinulla on toimiva algoritmi, voit muuntaa sen mihin tahansa tehokkaimpaan muotoon.

Ymmärtäminen, että rajalliset tilakoneet ja säännölliset lausekkeet ovat toiminnallisesti samanarvoisia, avaa uskomattoman mielenkiintoisia käyttötarkoituksia säännöllisten lausekemoottoreiden suhteen - etenkin kun on kyse sellaisten liiketoimintasääntöjen luomisesta, joita voidaan muuttaa ilman järjestelmän uudelleen kokoamista.

Tietojenkäsittelytieteen säätiön avulla voit ottaa ongelman, jota et osaa ratkaista, ja perustella: ”En tiedä miten ratkaista X, mutta tiedän kuinka ratkaista Y. Ja tiedän kuinka muuntaa ratkaisu Y: stä ratkaisuksi X: lle. Siksi tiedän nyt, kuinka X voidaan ratkaista. "

Jos pidät tästä artikkelista, saatat nauttia YouTube-kanavastani, jossa luon satunnaisen videon tai sarjakuvan ohjelmiston luomisen osasta. Minulla on myös postituslista ihmisille, jotka haluavat satunnaisen sähköpostin, kun tuotan jotain uutta.

Alun perin julkaistu osoitteessa blog.markshead.com 11. helmikuuta 2018.