Bevezetés a számítástechnikai koncepciókba
A számítástechnika lehetővé teszi számunkra a programozást, de nagyon sok programozásra van lehetőség anélkül, hogy megértsük a mögöttes informatikai fogalmakat.
Ez nem mindig rossz dolog. Amikor programozunk, sokkal magasabb absztrakciós szinten dolgozunk.
Amikor autót vezetünk, csak két vagy három pedállal, sebességváltóval és kormánykerékkel foglalkozunk. Biztonságosan üzemeltethet egy autót anélkül, hogy világos elképzelése lenne a működéséről.
Ha azonban egy autót a képességeinek legszélesebb körében akar üzemeltetni, akkor sokkal többet kell tudnia az autókról, nemcsak a három pedálon, a sebességváltón és a kormánykeréken.
Ugyanez vonatkozik a programozásra is. Sok mindennapi munkát el lehet végezni a számítástechnika alig vagy egyáltalán nem értésével. A „Kapcsolatfelvétel” űrlap létrehozásához a PHP-ben nem kell értenie a számítási elméletet.
Ha azonban komoly számítást igénylő kódot tervez írni, akkor egy kicsit többet kell megértenie a számítás működéséről a motorháztető alatt.
A cikk célja néhány alapvető háttér biztosítása a számításhoz. Ha van érdeklődés, követhetem néhány fejlettebb témát, de most meg akarom nézni az egyik legegyszerűbb elvont számítási eszköz - egy véges állapotgép - logikáját .
Véges állapotú gépek
A véges állapotú gép egy matematikai absztrakció, amelyet algoritmusok tervezésére használnak.
Egyszerűbben kifejezve: egy állapotgép beolvassa a bemenetek sorozatát. Amikor beolvas egy bemenetet, más állapotba kapcsol. Minden állapot meghatározza, hogy melyik állapotra váltson át egy adott bemenetre. Ez bonyolultnak hangzik, de valóban nagyon egyszerű.
Képzeljünk el egy eszközt, amely hosszú papírdarabot olvas. Minden hüvelyk papírra egyetlen betű van nyomtatva - vagy az 'a', vagy a 'b' betű.
Amint az államgép minden betűt olvas, megváltoztatja az állapotot. Itt van egy nagyon egyszerű állapotgép:
A körök olyan állapotok, amelyekben a gép tartózkodhat. A nyilak az átmenetek . Tehát, ha s állapotban van, és egy 'a' betűt olvas, akkor áttér a q állapotra . Ha elolvasod a „b”, akkor marad az állami s .
Tehát, ha elindulunk az s-n, és balról jobbra olvassuk a fenti papírszalagot, elolvassuk az 'a'-t és a q állapotba lépünk .
Ezután elolvassuk a 'b' szót, és visszatérünk az s állapotba .
Egy másik 'b' tart minket az s-en , majd egy 'a' következik - ami visszavezet minket a q állapotba. Elég egyszerű, de mi értelme van?
Nos, kiderült, hogy végigvezethet egy szalagot az államgépen, és elmondhat valamit a betűk sorrendjéről.
A fenti egyszerű állapotgépünkben, ha s állapotra végzünk, akkor a szalagnak 'b' betűvel kell végződnie. Ha q állapotra végzünk , akkor a szalag az „a” betűvel végződik.
Lehet, hogy ez értelmetlenül hangzik, de nagyon sok probléma megoldható ilyen típusú megközelítéssel. Nagyon egyszerű példa lehet annak meghatározása, hogy egy HTML-oldal tartalmazza-e ezeket a címkéket ebben a sorrendben:
Az állapotgép elmozdulhat egy olyan állapotba, amely megmutatja, hogy elolvasta a html címkét, a ciklust, amíg el nem jut a head címkéig, a ciklust, amíg a fej bezárásához el nem jut, és így tovább.
Ha sikeresen eljut a végső állapotba, akkor az adott címkék a megfelelő sorrendben vannak.
A véges állapotú gépek sok más rendszer képviseletére is használhatók - ilyen például a parkolóóra, a popgép, az automatizált gázszivattyú és minden más dolog mechanikája.
Determinisztikus végesállapotú gépek
Az eddig vizsgált állapotgépek mind determinisztikus állapotgépek. Bármely állapotból csak egy átmenet létezik minden megengedett bemenethez. Más szavakkal, az „a” betű elolvasásakor nem lehet két út az államból. Eleinte ez butaságnak tűnik, ha ezt a különbséget is meg akarjuk tenni.
Mire jó a döntések halmaza, ha ugyanaz a bemenet több állapotba kerülhet? Ugye, nem mondhatja el a számítógépnek, hogy if x == trueaztán végrehajtja doSomethingBigvagy végrehajtja doSomethingSmall?
Nos, ön egy állami géppel képes.
Az állapotgép kimenete a végső állapota. Minden feldolgozásán átesik, majd a végső állapotot kiolvassák, majd intézkednek. Az államgép nem tesz semmit, amikor állapotról államra halad.
Feldolgozza, és amikor a végére ér, leolvassa az állapotot, és valami külső kiváltja a kívánt műveletet (például szódabikarbóna kiadása). Ez egy fontos fogalom, ha nem determinisztikus végesállományú gépekről van szó.
Nem determinisztikus végesállapotú gépek
A nem determinisztikus végesállapotú gépek olyan végesállapotú gépek, amelyekben egy adott állapotból származó adott bemenet egynél több különböző állapothoz vezethet .
Tegyük fel például, hogy egy olyan véges állapotú gépet akarunk felépíteni, amely képes felismerni olyan betűsorokat, amelyek:
- Kezdje az 'a' betűvel
- majd ezt követi a „b” betű nulla vagy több előfordulása
- vagy a „c” betű nulla vagy több előfordulása
- az ábécé következő betűjével zárulnak.
Érvényes karakterláncok lennének:
- abbbbbbbbbc
- abbbc
- acccd
- acccccd
- ac (a b nulla előfordulása)
- ad (a c nulla előfordulása)
Tehát felismeri az „a” betűt, amelyet nulla vagy annál több követ a „b” vagy „c” betű, majd az ábécé következő betűje.
Ennek ábrázolásának nagyon egyszerű módja egy olyan állapotgép, amely úgy néz ki, mint az alábbi, ahol a t végső állapot azt jelenti, hogy a karakterlánc elfogadásra került, és megfelel a mintának.
Látja a problémát? Az s kiinduló ponttól nem tudjuk, melyik utat választjuk. Ha elolvassuk az „a” betűt, nem tudjuk, hogy a q vagy r állapotba kell-e menni .
Ennek a problémának a megoldására néhány mód van. Az egyik a visszalépés. Egyszerűen az összes lehetséges utat bejárja, és figyelmen kívül hagyja vagy visszalép azoktól, ahol elakad.
Alapvetően így működik a legtöbb sakkozó számítógép. Megvizsgálják az összes lehetőséget - és e lehetőségek összes lehetőségét -, és azt az utat választják, amely a legtöbb előnyt biztosítja számukra ellenfelükkel szemben.
A másik lehetőség a nem determinisztikus gép átalakítása determinista géppé.
A nem determinisztikus gép egyik érdekes tulajdonsága, hogy létezik olyan algoritmus, amely bármely nem-determinista gépet determinisztává varázsolja. Ez azonban gyakran sokkal bonyolultabb.
Szerencsénkre a fenti példa csak kissé bonyolultabb. Valójában ez elég egyszerű ahhoz, hogy a formális algoritmus segítsége nélkül a fejünkben determinisztikus géppé alakítsuk.
Az alábbi gép a fenti nem-determinisztikus gép determinisztikus változata. Az alábbi gépben a t vagy v végállapotot bármely olyan húr eléri, amelyet a gép elfogad.
A nem determinisztikus modellnek négy állapota és hat átmenete van. A determinisztikus modellnek hat állapota, tíz átmenete és két lehetséges végállapota van.
Ez nem sokkal több, de a komplexitás általában ugrásszerűen növekszik. Egy közepes méretű, nem determinisztikus gép abszolút hatalmas determinisztikus gépet képes előállítani .
Reguláris kifejezések
Ha bármilyen programozást végzett, valószínűleg rendszeres kifejezésekkel találkozott. A reguláris kifejezések és a véges állapotú gépek funkcionálisan egyenértékűek. Bármi, amit elfogadhat, vagy egy szabályos kifejezéssel egyeztethet, elfogadható vagy illeszthető egy állami géphez.
Például a fent leírt minta illeszthető a reguláris kifejezéshez: a(b*c|c*d)
A reguláris kifejezéseknek és a véges állapotú gépeknek is ugyanazok a korlátai. Különösen mindkettő csak a véges memóriával kezelhető mintákat illesztheti vagy fogadhatja el.
Tehát milyen típusú minták nem felelnek meg? Tegyük fel, hogy csak az „a” és a „b” karakterláncokat szeretné egyeztetni, ahol számos „a” van, amelyet azonos számú „b” követ. Vagy n 'a, majd n ' b, ahol n valamilyen szám.
Példák:
- ab
- aabb
- aaaaaabbbbbb
- aaaaaaaaaaaaaaaaaaaababbbbbbbbbbbbbbbbbb
Eleinte ez könnyű feladatnak tűnik egy véges állapotú gép számára. A probléma az, hogy gyorsan elfogynak az állapotok, vagy végtelen számú állapotot kell feltételezned - ekkor már nem egy véges állapotú gép.
Tegyük fel, hogy létrehoz egy véges állapotú gépet, amely képes elfogadni akár 20 'a-t, majd 20' b-t. Ez jól működik, amíg meg nem kap egy 21 'a-os karakterláncot, amelyet a 21' b-s követ - ekkor át kell írnia a gépet, hogy kezelje egy hosszabb karakterláncot.
Bármely felismerhető karaktersorozathoz van egy kicsit hosszabb, amelyet a gépe nem ismer fel, mert elfogy a memóriája.
Ez a Pumping Lemma néven ismert, amely alapvetően azt mondja: "Ha a mintádnak van egy szakasza, amely megismételhető (mint a fenti), akkor a minta nem szabályos".
Más szóval, nem egy reguláris kifejezés, sem a véges állapotú gép lehet kialakítani, amelyek elismerik a szálakat, hogy ne a minta illeszkedik.
Ha alaposan megnézi, akkor észreveszi, hogy ez a fajta minta, ahol minden „a” -nak megegyezik a „b” betűvel, nagyon hasonlít a HTML-hez. Bármely címkepáron belül tetszőleges számú más megfelelő címkepár lehet.
Tehát, bár képes lehet használni egy reguláris kifejezést vagy véges állapotú gépet annak felismerésére, hogy egy HTML-oldal rendelkezik-e a ; és az elemek a megfelelő sorrendben, nem használhat reguláris kifejezést annak megállapítására, hogy egy teljes HTML-oldal érvényes-e vagy sem - mert a HTML nem szabályos minta.
>,
Turing gépek
Tehát hogyan ismeri fel a nem szabályos mintákat ?
Van egy elméleti eszköz, amely hasonlít egy állapotgéphez, az úgynevezett Turing-gép. Hasonlít egy véges állapotú géphez, mivel van egy papírcsíkja, amelyet leolvas. De egy Turing gép törölheti és ráírhatja a papírszalagra.
A Turing-gép elmagyarázása több helyet foglal el, mint amennyi itt van, de a véges állapotú gépekről és a reguláris kifejezésekről folytatott megbeszélésünk szempontjából fontos néhány szempont.
A Turing-gépek számítási szempontból teljesek - vagyis bármi, ami kiszámítható, egy Turing-gépen is kiszámítható.
Mivel egy Turing-gép képes írni és olvasni a papírszalagról, ez nem korlátozódik egy véges számú állapotra. Feltételezhető, hogy a papírszalag végtelen hosszú. Természetesen a tényleges számítógépeken nincs végtelen mennyiségű memória. De általában elegendő memóriát tartalmaznak, így nem éri el az általuk feldolgozott problémák típusának korlátját.
A Turing Machines egy képzeletbeli mechanikus eszközt ad nekünk, amely lehetővé teszi számunkra a számítási folyamat működésének vizualizálását és megértését. Különösen hasznos a számítás határainak megértésében. Ha van érdeklődés, a jövőben még egy cikket készítek a Turing Machines-ról.
Miért számít ez?
Szóval, mi értelme van? Hogyan segít ez létrehozni a következő PHP űrlapot?
Korlátozottságuktól függetlenül az állapotgépek nagyon központi fogalmat jelentenek a számítástechnika szempontjából. Különösen lényeges, hogy bármely nem determinisztikus állapotgép számára, amelyet megtervezhet, létezik egy determinisztikus állapotgép, amely ugyanazt csinálja.
Ez kulcsfontosságú, mert ez azt jelenti, hogy megtervezheti az algoritmust, amelyikre a legkönnyebb gondolni. Ha van működő algoritmusa, akkor azt a leghatékonyabb formára konvertálhatja.
Annak megértése, hogy a véges állapotú gépek és a reguláris kifejezések funkcionálisan egyenértékűek, hihetetlenül érdekes felhasználási lehetőségeket nyit meg a reguláris kifejezés-motorok számára - különösen akkor, ha olyan üzleti szabályokat kell létrehozni, amelyek megváltoztathatók a rendszer újrafordítása nélkül.
A számítástechnika egyik alapja lehetővé teszi egy olyan probléma megoldását, amelyet nem tudsz megoldani, és okold meg: „Nem tudom, hogyan kell megoldani az X-et, de tudom, hogyan kell megoldani az Y-t. És tudom, hogyan kell megoldást konvertálni az Y megoldást az X-hez. Ezért most már tudom, hogyan lehet X-et megoldani. "
Ha tetszik ez a cikk, élvezheti a YouTube-csatornámat, ahol alkalmi videót vagy rajzfilmet készítek a szoftveralkotás bizonyos aspektusairól. Van egy levelezőlistám azok számára, akik alkalmi e-mailt szeretnének, ha valami újat készítek.
Eredetileg a blog.markshead.com címen jelent meg 2018. február 11-én.