Algoritmul determinist

Un algoritm determinist  este un proces algoritmic care produce un rezultat unic și predeterminat pentru intrări date.

Algoritm nedeterminist

În informatică , un „ algoritm nedeterminist ” este un algoritm care specifică mai multe căi pentru procesarea aceleiași intrări , fără nicio specificație a cărora va fi aleasă .

Utilizare

Teoria algoritmilor

În teoria algoritmilor , termenul „ algoritm ” înseamnă de obicei un algoritm „ determinist ”. „ Nedeterminist ” – diferă de cel mai cunoscut „dublu” al său prin posibilitatea de a obține un rezultat în moduri diferite („ determinist ” - urmează singura cale: de la date la rezultat , - în timp ce unele modalități de a executa „ non- determinist " poate duce la același rezultat, iar unele - la alte rezultate). Aceste proprietăți sunt descrise matematic: într-un model de calcul „nedeterminist” , cunoscut sub numele de „ automat nedeterminist ” .

Dezvoltarea algoritmilor

În proiectarea algoritmului, algoritmii „ nedeterminiști ” sunt adesea utilizați atunci când problema care este rezolvată de algoritm - în mod inerent - permite găsirea mai multor ieșiri (sau - când există o singură ieșire cu mai multe căi prin care poate fi găsită și toate sunt "la fel de bune"). "). Este important ca fiecare ieșire a algoritmului „ nedeterminist ” să fie adevărată ; - indiferent de căile „ alese ” de algoritm în timpul rulării.

Exemple

„Lista de cumpărături”

Imaginați-vă o „ listă de cumpărături ”: o listă de articole de cumpărat - care poate fi gândită în două moduri: ca o instrucțiune pentru a cumpăra toate aceste articole...

  • ...în orice ordine ( "algoritm nedeterminist ");
  • ...în ordinea dată (un algoritm " determinist ").

„Imbinare sortare”

Să presupunem că există un set de „ entități ” (să zicem – 300 de studenți), care trebuie „ordonate” (să zicem, după „numărul” de studenți). Un algoritm pentru aceasta este „ sortare de îmbinare ”:

  • Împărțiți setul în două grupuri aproximativ egale ;
  • Sortați ambele grupuri după sortarea dată (adică „ recursiv ”);
  • Rezultatele îmbinării (" îmbinați împreună "; vedeți numele metodei).

Elementele pot fi sortate „ unic ” dacă criteriul de sortare definește întotdeauna o ordine „ completă ” (adică, „numerele” elevilor sunt „ unice ”: nu se repetă între ele). Dar altfel (de exemplu, dacă sortați examenele după numele studenților fără a lua în considerare omonimi ), rezultatul sortării nu este definit: nu se știe care ordine este considerată corectă ; — adică algoritmul este „ nedeterminist ”.

Testul de simplitate

Sarcină : este dat un număr natural mai mare decât unu; stabiliți dacă este simplu .

Soluție : Algoritmul „nedeterminist” este următorul:

  1. Luați orice număr întreg „ k” astfel încât 2 ≤ k ≤ √( n );
  2. Dacă „ k” este un divizor al lui „ n” - opriți-vă cu răspunsul „ nu ” ; în caz contrar, opriți-vă cu răspunsul „ necunoscut ”.

Se poate observa că algoritmul nu oferă întotdeauna un răspuns „ util ”, dar nu dă niciodată un răspuns greșit .

Acest algoritm este „ nedeterminist ”: nu produce întotdeauna o soluție „ utilă ” - dar poate, având în vedere o anumită combinație de opțiuni. Acesta este un exemplu de algoritm „nedeterminist” de tip „ căutare ” .

Vezi și