Teoria algoritmilor
În teoria algoritmilor - termenul „algoritmul“ este de obicei înțeles ca algoritmul „determinist“. „Nedeterminista“ - diferă de la ei mai faimos „dublu“, capacitatea de a obține rezultatul în diferite moduri ( „deterministe“ - ar trebui să fie singura cale :. Din datele - rezultatul - în timp ce unele modalități de a efectua „non-deterministă“ poate duce la același rezultat, și unele - rezultate diferite). Aceste proprietăți - descrise matematic: în modelul de calcul „nedeterminat“. Este cunoscut sub numele de „automaton non-determinist“.
Dezvoltarea de algoritmi
Dezvoltarea algoritmilor - „nedeterministe“ algoritmi sunt utilizate adesea atunci când sarcina. rezolvată prin algoritmul - în esență - vă permite să găsiți mai multe puncte de vânzare (sau -., atunci când există o cale de ieșire din mai multe moduri prin care poate fi găsit tot „la fel de bune“). Este important ca fiecare ieșire algoritm „nedeterminist“ - credincioși; - indiferent de căile, „selectat“ algoritm în timpul rulării.
„Lista de cumpărături“
Noi reprezentăm „lista de cumparaturi“: o listă de produse pentru a cumpăra - care poate fi înțeleasă în două moduri: ca o indicație de a cumpăra toate aceste mărfuri.
- . în orice ordine ( „non-deterministă“ algoritm);
- . în această ordine (algoritmul „determinist“).
„Merge sortare“
Să presupunem că - un set de „entități“ (de exemplu, - 300 de elevi), care au nevoie pentru a „armoniza“ (să spunem - pe „numărul“ de elevi). Unul dintre algoritmi pentru aceasta - „îmbinare sortare“:
- Împărțiți setat pe dvepriblizitelno ravnyegruppy;
- Se filtrează obegruppy această sortare (adică „recursiv“);
- Se combină rezultatele ( „îmbinare“, a se vedea numele metodei.).
Elementele pot fi „unic“ sortate, atunci când sortarea criteriu definește întotdeauna comanda „complet“ (adică „numărul“ de studenți „unic“: nu se mai repeta reciproc). Dar, în caz contrar (de exemplu - dacă sortează după ultimele nume de examene ale elevilor cu excepția namesakes) - Sortarea rezultatul nu este definit: Nu se cunoaște ce fel de ordonare a considerat credincios; - și anume, algoritm "non-deterministă."
„Simplitate Test“
Sarcină. Având în vedere un număr întreg pozitiv mai mare decât unu; determina dacă este simplu.
Decizie. Algoritmul „nedeterminista“ - după cum urmează:
- Mark orice întreg «k» - astfel încât 2 ≤ k ≤ √ (n);
- Dacă „k“ este un factor de „n“ - a opri cu răspunsul „nu“; în caz contrar - să rămână cu răspunsul „necunoscut“.
Se poate observa că algoritmul nu produce întotdeauna un răspuns „util“, dar niciodată nu dă un răspuns greșit.
Acest algoritm - „non-deterministă“: ea nu întotdeauna produce o soluție „util“ - dar poate, în anumite combinații de opțiuni. Acesta este - un exemplu de „motor de căutare“ de tip algoritm „nedeterminist“.