Definiția laxă a algoritmului
Algoritmul - este definit cu precizie secventa (unic) de operații simple (elementare), oferind o soluție la orice problemă într-o anumită clasă.
Această definiție nu poate fi acceptată ca o definiție riguroasă, așa cum a folosit alte --- concepte nedeterminate lipsite de ambiguitate și alte elementare.
Conceptul poate fi rafinat prin specificarea unei liste de proprietăți comune. care harakuterny pentru algoritmi. Printre acestea se numără:
1. Rezoluție - algoritm este împărțit în etape separate, performanța următorul pas este posibilă numai după finalizarea tuturor operațiunilor în etapa anterioară;
2. Determinancy - un set de valori intermediare la orice pas este unic determinat de sistemul de valori care au existat în etapa anterioară;
3. Etapele elementare # 8209; lege obținerea valorilor ulterioare din sistemul anterior ar trebui să fie simplu și local;
4. Orientare # 8209; În cazul în care o metodă de obținere a valorilor ulterioare din orice sursă nu conduce la un rezultat, trebuie subliniat faptul că ar trebui să fie luate în considerare rezultatul algoritmului;
5. Masa - sistem valori inițiale pot fi selectate dintr-un set.
Conceptul algoritmului definit de proprietățile de listare a 1 - 5, nu pot fi considerate la fel de stricte ca și în formulările proprietăților utilizate termenii „valoare“, „metodă“, „simplu“, însemnând „local“ precis al cărui nu este setat. Prin urmare, se numește non-strict conceptul (intuitiv) a algoritmului.
Clarificarea conceptului algoritmului realizat în cadrul modelelor algoritmice.
Unul dintre domeniile de construcție a definiției stricte a algoritmului asociat cu luarea în considerare a algoritmilor pentru a calcula valoarea funcțiilor numerice care depind de valorile întregi de argumente - astfel de funcții sunt numite calculabil. Noțiunea de o funcție calculabil nu este strictă, deoarece conceptul de algoritm. Cu toate acestea, în lucrările Bisericii. K. Gödel. Kleene a fost fundamentată clasa de identitate de pretutindeni sunt definite funcțiile calculabile din clasa de funcții recursive parțiale. care este determinată strict. Este posibil de a reduce problema solvabilitatii algoritmică a dovezii de posibilitatea (sau imposibilitatea) de a construi o funcție recursivă care rezolvă problema.
Să presupunem că există două seturi de X și Y.
În cazul în care unele elemente ale X cartografiat elementele definite în mod unic de Y, atunci spunem că o funcție parțială de la X la Y.
Setul de elemente de X, care au elemente corespunzătoare în Y, numit domeniul functiei. o multitudine de elemente Y, care corespund X este setul de valori ale funcției.
Dacă domeniul funcției unui X Y X coincide cu setul, funcția este numit definită peste tot.
Ideea de a construi o definiție precisă a algoritmului, bazat pe noțiunea unei funcții recursive
Orice date digitale pot codifica numerele naturale într-un sistem numeric.
Apoi, fiecare din conversie va fi redusă la o secvență de operații de calcul și un rezultat de procesare va fi un număr întreg.
Orice algoritm pentru această singură funcție numerică, calculează valoarea sa, iar etapele sale de bază sunt obișnuite operații aritmetice și logice. Aceste funcții sunt numite calculabil.
Să presupunem că avem o clasă de funcții de tip y (x1, x2. ..., xn). caracteristică este faptul că toate argumentele la x1 funcție, x2. ..., xn sunt întregi, iar valoarea lui y este exprimată ca un întreg.
Funktsiyay (x1, x2. ..., xn), se spune că în mod eficient calculabil. în cazul în care există un algoritm pentru a calcula valoarea sa din valorile cunoscute ale argumentelor.
Deoarece conceptul de algoritm în această definiție este luată într-un sens intuitiv, și conceptul de funcții în mod eficient calculabil este intuitiv.
Cu toate acestea, setul de funcții de calcul, care îndeplinesc proprietățile enumerate mai sus, algoritmul a fost aceeași și, în plus, este ușor de descris în termeni matematici convenționale. Acest set este descris cu precizie de funcții numerice, care coincide cu mulțimea tuturor funcțiilor calculabile cu cea mai largă încă o anumită înțelegere a algoritmului se numește funcții recursive împreună.
Orice model algoritmică implică identificarea etapelor elementare ale algoritmului și cum să construiască succesiunea lor de transformări, oferind secvența de prelucrare a datelor necesare.
Recursivă „pași elementari“ modelul este un simplu funcții numerice:
· S 1 (x) = x + 1 este o funcție directă de o singură repetiție;
Aceste funcții sunt definite peste tot și intuitiv calculabil. Deasupra lor sunt determinate de exploatare (operatori), a căror utilizare dă naștere unor noi funcții de calcul cunoscute în sens intuitiv. Funcții parțiale care pot fi obținute cu ajutorul acestor operatori de cele mai simple se numește recursiv partiala.
Ipoteza este că Biserica clasa construită astfel funcții recursive parțiale identice cu clasa funcțiilor care admit calcule algoritmice.
Suprapunerea funcțiilor parțiale
Să funcții locale m-
substituit în funcția n -place g (x1, ..., xn). Rezultatul este un n - funcția ary
Se spune că funcția h obținută din funcțiile g. f1, ..., fnsuperpozitsiey (substituție).
în cazul în care SuperScript reprezintă numărul de funcții, inline ca argumente.
Dacă suntem capabili să calculeze funcțiile g, f 1, ......, f n, functia h poate fi calculată.
În cazul în care funcțiile g, f 1, ......, f n, definită peste tot, atunci funcția h așa cum este definit pretutindeni.
Să presupunem că orice funcții numerice parțiale: n - g locală (x1, ..., xn) și (n + 2) - local. h (x1, ..., xn, y, k). Se spune că (n + 1) -place funcție parțială f este formată din funcțiile g și h prin recursie primitiv dacă pentru toate valorile pozitive ale x1, ..., xn, y este adevărată:
Deoarece domeniul funcțiilor este mulțimea tuturor numerelor naturale, funcția parțială f. care îndeplinește condițiile de (1) există pentru toate funcțiile g și parțiale h, iar această funcție va fi singura.
Condiția (1) este setat ca secvența pentru determinarea valorilor etape f recursie diferite:
Pentru recursie primitiv folosim notația
În această înregistrare R este privit ca un simbol al unei operațiuni parțiale de două loc definit pe un set de toate funcțiile parțiale. Dacă g și h sunt definiți peste tot, atunci f este definită peste tot. Ceea ce este important este faptul că, dacă suntem capabili de a găsi valorile g și h funcții. valoarea funcției f (a1, ..., an, m + 1), se poate calcula "mecanic" folosind ecuația (2).
Parțial functia f (x1, ..., xn) se numește primitivă recursiv în cazul în care poate fi obținut printr-un număr finit și superpoziție recursie primitiv, pe simpla funktsiyS1. 0niInm.
Toate funcțiile recursive primitive sunt definite peste tot.
Dovedi că funcția dublă f (x, y) = x + y este un recursiv primitiv
Găsiți valoarea funcției f (3,2). în cazul în care este dată de următoarele relații:
Lăsați o anumită funcție f (x, y). Reparăm valoarea lui x și de a determina la ce valoare y f (x, y) = 0. Mai dificil este problema de a găsi cea mai mică dintre valorile lui y. pentru care f (x, y) = 0.
Ca rezultat al soluției acestei probleme depinde de x. chiar și cea mai mică y este o funcție de x.
În mod similar, definim o funcție de mai multe variabile
Pentru a calcula funcția j se poate utiliza următoarea procedură:
Funcția f (x, y) = x-y poate fi obținută prin minimizarea operator:
Parțial functia f (x1, ..., xn) este numit recursiv partiala. dacă puteți obține un număr finit de operații superpoziției, recurențe primitivă și minimizarea, bazată doar pe cea mai simplă funktsiyS1. 0niInm.
Clasa de funcții recursive parțiale mai largi decât clasa de funcții recursive primitive, de exemplu. A. Toate funcțiile recursive primitive sunt definite peste tot, iar printre funcțiile recursive parțiale să nu funcționeze găsit peste tot definit, și definit nicăieri.
Conceptul unei functii recursive partiala este una dintre principalele concepte ale teoriei algoritmilor. Importanța sa este după cum urmează.
Pe de o parte, fiecare specificat parțial funcția recursivă standard de calculabil printr-un procedeu mecanic caracter corespunde noțiunii intuitive de algoritmi.
Pe de altă parte, indiferent de modul în care nu au fost construite clase de algoritmi strict delimitate, în toate cazurile, invariabil, care sunt calculabile de funcțiile lor numerice sunt recursiv parțiale.
Prin urmare, este în general acceptată ipoteza științifică, formulată ca o Biserică teză.
Clasa funcții numerice parțiale algoritmic (sau mașină) calculabile identice cu clasa de funcții recursive parțiale.