Cunoaște Intuit, de curs, algoritmi normale de Markov

Rezumat: Determinarea algoritmului normale Markov și punerea sa în aplicare. Oportunități normale Markov și algoritmi Markov tezei. Metode de dezvoltare a algoritmilor normali Markov.

Determinarea algoritmului normal și punerea sa în aplicare

La mijlocul secolului trecut, un proeminent AA matematician român Markov a introdus conceptul unui algoritm normal (algoritm) pentru a clarifica conceptul de „algoritm“ care ne permite să rezolve problema determinării problemelor algoritmic de nerezolvat. Mai târziu, acest concept a fost numit algoritmul normal de Markov (SUA). Limba SUA. Pe de o parte, în mod deliberat săraci, este necesar în scopul introducerii conceptului „algoritm“. Cu toate acestea, pe de altă parte, avem idei ca bază pentru un grup mare de limbaje de programare, cunoscut sub numele de limbaje de programare logică. care fac obiectul acestui manual.

Pentru a determina SUA a introdus alfabet arbitrar - un set finit nevidă de simboluri, care descrie algoritmul și a datelor. Alfabetul este inclus, de asemenea, un caracter nul. care va fi notată cu litera grecească. Cuvântul se referă la orice secvență nevidă de caractere alfanumerice sau un caracter martor, ceea ce denotă cuvântul gol.

Fiecare SUA este determinat să se încheie un set ordonat de perechi de cuvinte în alfabet, numit permutări. Într-o pereche de cuvinte wildcard din stânga (primul) cuvânt care nu este gol și dreapta (a doua), cuvântul poate fi un caracter nul. Pentru claritate, în stânga și cuvântul dreapta sunt separate printr-o săgeată. De exemplu,

Taken orice șir care nu este gol de caractere ca un algoritm de date. Munca noastră constă într-o serie de pași foarte similare. Pasul Algoritmul poate fi descris după cum urmează:

1. Într-o secvență ordonată de substituții sunt în căutarea pentru prima substituție, a lăsat un cuvânt, care face parte dintr-un rând de date.
2. Linia de date în căutarea pentru prima (stânga) cuvintele de intrare găsite prin substituirea stânga.
3. Această intrare în șirul de date se înlocuiește cu cuvântul potrivit de substituție găsit (conversie de date).

Etapa a algoritmului se repetă atâta timp cât

• sau nu va avea o situație în care un pas nu poate fi realizată datorită faptului că nu substituție nu este adecvată (cuvânt din stânga a oricărei substituție nu este inclusă în șirul de date) - oprire regula;
• sau se stabilește că procesul de permutare nu se poate opri.

În primul caz, șirul de date. când oprirea algoritmului rezultat este output (rezultat) și se aplică datelor de intrare. iar în al doilea caz, algoritmul nu se aplică datelor de intrare.

Deci, așa cum este definit mai sus în exemplul unui algoritm normal de Markov traduce cuvânt cu cuvânt, după cum urmează (mai sus de conversie săgeată vom scrie numărul utilizat ca substituție în șir subliniază stânga utilizat schimbarea cuvântul.)

și atunci când convertirea cuvintelor abbc același algoritm va rula pe termen nelimitat, deoarece există o repetare ciclică a datelor:

Astfel, orice algoritm Markov normale definește o funcție, pe care o numim normală (sau computable Markov). care poate fi parțială, și în care definiția cuvântul de intrare atribuie cuvântul de ieșire.

Posibilitatea de algoritmi normale și teza Markov

În primul rând, să ia în considerare posibilitatea de a implementa operații aritmetice folosind algoritmi Markov normale. În primul rând, să acorde o atenție la o împrejurare în legătură cu activitatea de orice SUA. este necesar fie să se introducă reguli suplimentare de oprire a algoritmului normal (altfel în exemplul 1, pentru a crește numărul de algoritmul va continua să funcționeze și va crește din nou rezultatul de 1, și deci un număr nelimitat de ori), sau adăugat la șirul de intrare specială înainte de funcționare normală a algoritmului de caractere. diferit de celelalte personaje din șirul, care sunt contabilizate de permutări ale algoritmului de la începutul activității sale, și care sunt eliminate la sfârșitul algoritmului. Vom adera la cea de a doua metodă, ca una dintre cele mai de succes implementări de algoritmi Markov normale într-un limbaj de programare Refal. Pe măsură ce ia simbolul „@“ ca personaj adăugat.

Exemplul 1. Se consideră o operație simplă de a crește numărul de zecimale 1. În acest caz, este aproape întotdeauna necesară pentru a crește ultima cifră este 1, iar ultima cifră este diferită în faptul că acesta vine după simbolul „@“. De aceea, primele substituții ar trebui să fie de tip substituție

Dar dacă e numărul 9, atunci acesta trebuie să fie înlocuit cu 0 și creșterea cu 1 pentru a trece la cifra anterioară. Aceasta corespunde cu substituția

În cele din urmă, în cazul în care numărul începe cu 9, iar înainte de această cifră aveți nevoie pentru a pune 1, atunci acesta va fi responsabil de substituție

și dacă nu, atunci, la sfârșitul simbolurilor @ pentru a șterge algoritm care realizează substituirea

Astfel, vom obține următoarele SUA pentru a crește numărul de zecimale 1:

Aici locuri de muncă construite algoritm pentru numerele 79 și 99:

In mod similar dezvoltat normal de algoritm Markov pentru a reduce numărul de 1 (a se vedea. Exercitiul 1.3.1).

Am demonstrat algoritmul pentru numărul 10:

Pentru a construi adăugarea a două numere ale algoritmului se poate folosi ideea de a reduce numărul de unul, urmat de o altă creștere a numărului de 1 și repetarea acestui atâta timp cât numărul Descăzut dispare după ce devine egal cu 0. Dar este posibil să se utilizeze mai complex plus idee bitwise 1 cu cifra de transfer din stânga. Construcția acestor algoritmi, și algoritmi de scădere. înmulțirea și împărțirea alocată pentru funcționarea independentă în exerciții de 2 - (. vezi 1.3) 9.

Aceste exemple arată, de asemenea, posibilitățile ale dispozitivului Markov algoritmii normali pentru organizarea ramificarea și procesele ciclice de calcul. Acest lucru arată că orice algoritm poate fi normalizat, astfel. E. Setați la algoritmul normal de Markov. Aceasta este teza Markov. care ar trebui înțeles ca definiția algoritmului.

Cu toate acestea, în algoritmul de construcție din urmă exemplul de mai sus sugerează următoarea dezvoltare tehnica din SUA:

Rezolvarea problemelor de realizare a fiecărei părți. În acest exemplu, următoarele aspecte:

1. stocarea copiei descărcării - nivelul 1 este stocat ca un simbol „a“, iar descărcarea 0 - ca simbol „b“;
2. spațiu de stocare de descărcare copiat - marca nu a fost încă copiat simbol simbol suplimentar „!“ cu înlocuirea acestuia cu o „?“ atunci când se deplasează descărcarea de copiere, și invers, după mișcarea de înlocuire.

Dacă o parte a implementării este complex, este de asemenea supus descompunerii.

Asamblarea punerea în aplicare a unui algoritm.

exerciții

1. Se determină algoritmul normal. care reduce numărul de unul.
2. Definirea algoritm normal adăugarea a două numere binare printr-o reducere a numărului 1 și creșterea celuilalt numărul 1, atâta timp cât numărul Descăzut devine egal cu 0.
3. Definirea plus logică algoritmul normale a două numere binare.
4. Se determină algoritmul de multiplicare logică normală a două numere binare.
5. Se determină algoritmul normal de modulo-2 adăugarea a două numere binare.
6. Se determină algoritmul normală este adăugarea la nivel de bit a două numere binare.
7. Se determină algoritmul normal pentru scăderea numerelor binare.
8. Se determină algoritmul normal pentru înmulțirea cu două coloane binare de numere.
9. Se determină algoritmul normal pentru împărțirea celor două numere binare cu definiția coeficientului și restul.
10. Definirea algoritm normal pentru calcul cel mai mare divizor comun a două numere binare.
11. Definirea algoritm normal pentru calcularea cel mai mic multiplu comun a două numere binare.