Normaali algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. marraskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Normaali Markovin algoritmi (algoritmi) ( NAM , myös Markov-algoritmi ) on yksi tavallisista tavoista määritellä muodollisesti algoritmin käsite (toinen tunnettu menetelmä on Turingin kone ). Normaalialgoritmin käsitteen esitteli A. A. Markov (junior) 1940-luvun lopulla teoksissaan joidenkin assosiatiivisten laskelmien teorian ongelmien ratkaisemattomuudesta. Sanan "algori f m" perinteinen oikeinkirjoitus ja ääntäminen tässä termissä juontaa myös sen kirjoittajasta, joka opetti monien vuosien ajan matemaattisen logiikan kurssia Moskovan valtionyliopiston mekaniikka- ja matematiikan tiedekunnassa .

Normaali algoritmi kuvaa menetelmää merkkijonojen uudelleenkirjoittamiseen, samalla tavalla kuin muodolliset kieliopit . NAM on Turingin täydellinen kieli, mikä vastaa ilmaisuvoimaltaan Turingin konetta ja siten nykyaikaisia ohjelmointikieliä. Toiminnallinen ohjelmointikieli Refal luotiin NAM : n pohjalta .

Kuvaus

Normaalit algoritmit ovat verbaalisia, eli niitä on tarkoitus soveltaa eri aakkosten sanoihin.

Minkä tahansa normaalin algoritmin määritelmä koostuu kahdesta osasta: algoritmin aakkosten määrittelystä (sanoihin, joiden merkeistä algoritmia käytetään) ja sen kaavion määrittelystä . Normaalin algoritmin kaavio on äärellinen järjestys joukko niin sanottuja korvauskaavoja , joista jokainen voi olla yksinkertainen tai lopullinen . Yksinkertaiset korvauskaavat ovat muotoa , jossa ja ovat kaksi mielivaltaista sanaa algoritmin aakkosissa (jota kutsutaan vastaavasti korvauskaavan vasemmaksi ja oikeaksi puolelle). Vastaavasti lopulliset korvauskaavat ovat muotoa , jossa ja ovat kaksi mielivaltaista sanaa algoritmin aakkosissa. Oletetaan, että apukirjaimet ja eivät kuulu algoritmin aakkosiin (muuten kaksi muuta kirjainta tulisi valita toimimaan erottimena vasemman ja oikean osan välillä). $L - D$ $L$ $D$ $L\to\cdot D$ $L$ $D$ $\to$ $\tiedostoon \cdot$

Esimerkki normaalista algoritmikaaviosta viisikirjaimissa aakkosissa on malli $|*abc$

$\left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\ \|c&\&c\\ac&\&c|\\c&\\cdot \end{matrix}}\oikealle.$

Prosessi, jossa normaalia algoritmia sovelletaan mielivaltaiseen sanaan tämän algoritmin aakkosissa, on erillinen perusvaiheiden sarja, joka koostuu seuraavista. Olkoon algoritmin edellisessä vaiheessa saatu sana (tai alkuperäinen sana , jos nykyinen vaihe on ensimmäinen). Jos korvauskaavojen joukossa ei ole ketään, jonka vasen puoli olisi mukana , niin algoritmin työ katsotaan suoritetuksi ja tämän työn tuloksena on sana . Muussa tapauksessa substituutiokaavojen joukosta, joiden vasen osa on mukana , valitaan ensimmäinen. Jos tällä korvauskaavalla on muoto , niin muodon sanan kaikista mahdollisista esityksistä valitaan yksi, jolle on lyhin, minkä jälkeen algoritmin katsotaan valmistuneen tuloksella . Jos tällä korvauskaavalla on muoto , niin kaikista mahdollisista muodossa olevan sanan esityksistä valitaan se, jolle on lyhin, minkä jälkeen sanaa pidetään nykyisen vaiheen tuloksena, jota käsitellään jatkossa seuraavassa askel. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\to\cdot D$ $V'$ $RLS$ $R$ $RDS$ $L - D$ $V'$ $RLS$ $R$ $RDS$

Esimerkiksi käytettäessä algoritmia yllä esitetyllä kaaviolla sanat , , , , , , , , ja näkyvät peräkkäin sanan yhteydessä, minkä jälkeen algoritmi päättyy tulokseen . Katso lisää esimerkkejä alta. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

Mikä tahansa normaali algoritmi vastaa jotakin Turingin konetta ja päinvastoin mikä tahansa Turingin kone vastaa jotakin normaalia algoritmia. Church-Turingin teesin muunnelmaa , joka on muotoiltu suhteessa normaaleihin algoritmeihin, kutsutaan yleisesti "normalisointiperiaatteeksi".

Normaalit algoritmit ovat osoittautuneet käteväksi työkaluksi monien konstruktiivisen matematiikan haarojen rakentamiseen . Lisäksi normaalin algoritmin määritelmään kuuluvia ideoita käytetään useissa ohjelmointikielissä, jotka on suunnattu symbolisen tiedon käsittelyyn - esimerkiksi Refal- kielessä .

Esimerkkejä

Esimerkki 1

Markovin algoritmin käyttäminen merkkijonojen muunnoksissa.

Aakkoset:

{ a ... i, A ... I, "välilyönti", "piste" }

Säännöt:

A → oranssi
kg kiloon
M → kauppa
T → äänenvoimakkuus
kauppa →. pysähtyy (lopullinen kaava)
tuossa kioskissa → tuolla torilla

Lähde rivi:

Ostin kg Aovin T M:stä.

Kun algoritmi suoritetaan, merkkijonoon tehdään seuraavat muutokset:

Ostin kilon appelsiineja T M:stä.
Ostin kilon appelsiineja T.M:stä.
Ostin T-kaupasta kilon appelsiineja.
Ostin kilon appelsiineja tuosta kaupasta.
Ostin tuolta kioskilta kilon appelsiineja.

Tämä päättää algoritmin suorittamisen (koska kaava nro 5, jonka teimme lopulliseksi, saavutetaan).

Esimerkki 2

Tämä algoritmi muuntaa binääriluvut " yksiksi " (jossa ei-negatiivisen kokonaisluvun N tietue on N:n sauvan merkkijono). Esimerkiksi binääriluku 101 muunnetaan viideksi tikuksi: |||||.

Aakkoset:

{ 0, 1, | }

Säännöt:

1 → 0|
|0 → 0||
0 → "" (tyhjä merkkijono)

Lähde rivi:

101

Esitys:

0|01
0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Katso myös

Muut abstraktit toteuttajat ja muodolliset laskentajärjestelmät

Normaaliin algoritmeihin perustuvat kielet

REFAL
ti

Muut algoritmit

Operaattorin algoritmi

Linkit

Sanakirjat ja tietosanakirjat	Iso venäläinen