Algoritmi primari. Să presupunem că ne sunt date unele L1 limbaj formal. care propuneri sunt datele inițiale pentru transformare, așa cum este definit mai jos. L2 va fi numită limba operanzi de intrare. Să presupunem că avem un set finit de operații, dintre care unele pot fi aplicate la unele dintre propuneri (desene de caractere) limbă L1. Operațiunile vor fi împărțite în acțiuni și condiții. Executarea acțiunii este ca operandul se înlocuiește cu structura de proiectare a acestei operanzi obținute prin efectuarea operației; ceea ce se întâmplă în viitor, este considerat operand. În cazul în care operațiunea a operandului sursă nu se aplică, atunci nici un rezultat se obține și nici o informație cu privire la absența acestuia nu se produce. această condiție este de a testa, fie că este vorba de un operand sau nu valid. În primul caz, rezultatul de verificare este o valoare logică adevărată, în al doilea - o minciună. Operand rămâne neschimbat. Condițiile sunt predicate.
Construim un context limbaj liber L2. care va fi numit algoritmică. Pentru aceasta folosim notația Backus. propunere limba L2 va fi notată metacaractere (intrare algoritm primar):
<запись первичного алгоритма>:: = <безусловный приказ> ï <условный приказ>
<безусловный приказ>:: = <метка> <разделитель I> <знак действия> <разделитель II> <отсылка> <разделитель III>
<условный приказ>:: = <метка> <разделитель IV> <знак условия> <разделитель V> <отсылка> <разделитель VI> <отсылка> <разделитель III>
<отсылка>:: = <метка> ï <стоп>
Pentru L2 a fost complet definită, trebuie să specificați valoarea folosind metacaractere metaformul:
<метка> <разделитель IV>
<стоп> <разделитель V>
<разделитель I> <разделитель VI>
<разделитель II> <знак действия>
<разделитель III> <знак условия>
Noi nu vom face acest lucru, definind astfel, mai mult de o limbă, o clasă de limbă. Ca L2 pot fi adoptate oricare dintre limbajul specific acestei clase. Remarcăm doar că separatoarele trebuie să fie alese astfel încât să fie în mod clar separate pe ordinele părților relevante, iar separatorul III, trebuie să fie deosebită de separatorul VI, precum și din orice referințe și etichete.
Pentru a da un sentiment de înregistrare a algoritmului primar, definim următoarea regulă.
EXEMPLU și l și efectuarea algoritmului primar.
1) înregistrarea de vizualizare primar de la începutul algoritmului, pentru a găsi primul ordin; mergeți la pasul 2.
2) În cazul în care ordinea de raportare este salt necondiționat revendicării 3 sau revendicării 5.
3) Se aplică operație corespunzătoare semnul acțiunii acestui ordin, la operand; găsi trimiterea în această ordine; mergeți la pasul 4.
4) Dacă referința selectată are forma <стоп>, atunci procesul este terminat; în caz contrar, se uită la înregistrarea algoritmului de la început, pentru a găsi o comandă, eticheta este aceeași cu o referință, și treceți la pasul 2.
5) În cazul în care satisface operanzilor corespunzătoare semnați termenii acestui ordin, atunci du-te la revendicarea 6, sau - pentru revendicarea 7.
6) Găsiți prima trimiterea acestui ordin; mergeți la pasul 4.
7) Găsiți a doua trimiterea acestui ordin; mergeți la pasul 4.
Rețineți că executarea regulii depinde de L2 de limbă și de la un set preselectat de operațiuni. Această regulă este un algoritm într-un sens intuitiv al cuvântului, dar formulat atât de precis încât atunci când se execută nu poate avea nici un ambiguități.
Înregistrarea algoritmului primar, considerat împreună cu statul de implementare a acesteia, numit algoritmul principal.
Aplicarea normelor algoritm pentru a efectua agregat primar format dintr-un algoritm de înregistrare primară și scrierea operanzi, generează un proces numit algoritmică. Acest proces poate fi întrerupt, fie atunci când regulile din revendicarea 2, și apoi operandul rezultată se numește rezultatul dorit, sau rupe din cauza impracticabilitate oricărui alt paragraf al regulilor (în zadar să oprească) sau să continue la nesfârșit (nu opri).
În primul caz, spunem că algoritmul principal este aplicabil acestui operand, iar al doilea și al treilea cazuri - care nu este aplicabilă.
Trebuie remarcat faptul că un proces de algoritmică este un set de înregistrări algoritm de co-transformare și operanzi. caracteristică particulară a acestei transformări este desenul personajelor invarianta care algoritmul de înregistrare.
Algoritmi naturale. Algoritmul natural se numește algoritmi primare pentru punerea în aplicare a ceea ce impune numai cunoașterea operațiilor naturale și, probabil, liniarizarea și delinearization. Aici este una dintre familiile naturale ale algoritmilor.
Să operanzi limbajul L2 are ca sugestii cuvânt numai în alfabetul A. Presupunem că sarcina alfabetului este definită clasa gramaticale <буква в А>. Presupunem că, în plus față de L2 de locuri de muncă necesită doar formula Backus <операнд>:: =<буква в А> ï <операнд> <буква в А>
Limba L1 algoritmică precizam după cum urmează:
<метка>. = <цифра>ï<метка> <цифра>
Pentru a construi gramaticile limbilor L1 și L2 este suficientă înlănțuire de cunoștințe. Astfel, am construit clasa primară algoritmi (pozitive) folosind doar naturale de operare, liniarizare și delinearization definite matematic destul de strict.
definiție formală pe scară largă a unui algoritm. Știm deja că clasa primară de algoritmi specificat, în cazul dat două limbi: L1 și L2. în care prima dintre aceste propuneri declarate înregistrează algoritmi și oferă al doilea - Înregistrări operanzi și dacă regula se efectuează algoritmi primare aplicabile: perechile de înregistrare de înregistrare operanzi algoritm.
Primul paragraf din definiția generală a algoritmului va avea următorul cuprins:
1) Algoritmi primari - sunt algoritmi.
Dar conceptul general al algoritmului este mult mai largă. al doilea paragraf al acestuia prevede:
2) În cazul în care doi L1 și L2 de limbă. în care teză a primului anunțat înregistrează algoritmi și oferă al doilea - Înregistrări operanzi și în cazul dat un W algoritm, care sunt operanzi de proiectare obținute prin legarea fiecare propoziție de L1 cu n L2 Exemple de limbă folosind conexiunea bine definită de rang n + 1, apoi dat-o familie algoritmi n-ary.
În cele din urmă, al treilea punct al unei definiții comune va avea următorul cuprins:
3) n locale algoritm - același algoritm.
Astfel, fiecare algoritm într-un sens formal larg, dacă nu primar, are propriul algoritm de executie. În cazul în care nu au fost identificate algoritmi primar, ar fi imposibil să se dea o definiție strictă și alți algoritmi, cum ar fi imposibil să se specifice un singur algoritm de execuție. Dar, odată ce a construit cel puțin o implementare a algoritmului, este posibil să se construiască multe altele, nu mai atrage algoritmi primari.
Single numitul algoritm n-local pentru care n = 1. algoritmi primare vor fi, de asemenea, numit singur.
într-un sens larg algoritm oficial numit aplicabil operandul special (set operanzi), în cazul în care algoritmul este aplicabil pentru a realiza structura simbol corespunzător combinarea algoritmului de înregistrare și operand (operand). În caz contrar, spun că algoritmul în sens larg aplicabile formale și acest operand (set operand).
Doi algoritmi sunt numite echivalente funcțional. dacă operanzilor limbile lor coincid una cu cealaltă, iar dacă întotdeauna una și aceeași sursă sau ambilor algoritmi produce același rezultat, sau ambele nu sunt aplicabile la acestea.
Teorema Teorema. Pentru fiecare algoritmi primar de familie (definită prin două limbi L1 și L2 și efectuarea regula) există un algoritm într-un sens formal larg, care este echivalentă cu regula performanței și care are o intrare grafic identic cu regula de înregistrare.
Un astfel de algoritm este numit în mod natural algoritmul pentru realizarea acestei familii algoritmi primari. Această teoremă, deși nu permite determinarea conceptului de algoritm pentru a renunța la definirea algoritmilor primare, dar „egalizează drepturile“ algoritmi primare non-primare.
De multe ori este necesar să se aplice unor algoritmi pentru înregistrările altora. Pentru a putea să se bucure de aceeași formulă utilizată în alte discipline matematice, trebuie să urmați măsuri de precauție speciale. De obicei, algoritmi sunt notate cu litere latine; denota înregistrarea lor prin aceleași litere cu un capac (liniuță), la partea de sus; funcțiile definite de acestea desemnate prin aceleași litere cu partea de sus val. De exemplu, în cazul în care g - algoritmul, apoi - recordul său, precum și - generată de funcția (afișare operație) lor.
Sub rezerva precauțiile menționate mai sus, după cum urmează pentru a descrie legătura dintre algoritmul care corespunde unei limbi și a algoritmului.
Să L2 =<> - Limba algoritmică, L1 =<> - operanzi de limbă, Z - Feedback (n + 1) lea rang și W - efectuarea algoritmului. Denote o structură obținută prin legarea n L1 și L2 Exemple lingvistice ale limbii. Apoi, egalitatea înseamnă că t este un algoritm și că. În același timp - a înregistra rezultatul dorit.
Pentru fiecare familie de algoritmi definite de un algoritm care efectuează W, L3 = set de toate posibile se înregistrează rezultatele dorite este un limbaj formal. Astfel, fiecare familie de algoritmi întâlnește o altă limbă oficială: limba rezultatelor dorite. Într-un caz particular, acesta poate fi un subset al limbajului operanzi.
Luați în considerare două familii de algoritmi care au algoritmi de performanță echivalente. Este clar că aceste familii au aceleași limbi operanzi, rezultatele dorite și algoritmică. Ia doi algoritmi aparținând familii diferite, dar cu aceeași înregistrare. Astfel de algoritmi sunt echivalente, dar atunci când se efectuează genera procese diferite.
O p e n d e n e. Doi algoritmi care au aceeași înregistrare și echivalente, sunt unul și același algoritm (sau instanțe ale aceluiași algoritm).
Acum este ușor să se clarifice definiția generală a algoritmului de mai sus (sau, mai degrabă, să-l completeze).
Algoritm- o colecție de înregistrări ale algoritmului și cartografiere, a indus algoritmul său de execuție.