Deterministisk algoritm

En deterministisk algoritm  är en algoritmisk process som ger ett unikt och förutbestämt resultat för givna indata.

Icke-deterministisk algoritm

Inom datavetenskap är en " icke-deterministisk algoritm " en algoritm som specificerar flera vägar för bearbetning av samma indata , utan någon specifikation av vilken som kommer att väljas .

Användning

Algoritmteori

I teorin om algoritmer betyder termen " algoritm " vanligtvis en " deterministisk " algoritm. " Non-deterministic " - skiljer sig från sin mer välkända "double" i möjligheten att erhålla ett resultat på olika sätt (" deterministic " - följer den enda vägen: från data till resultat , - medan vissa sätt att exekvera " icke- deterministisk " kan leda till samma resultat, och vissa - till andra resultat). Dessa egenskaper beskrivs matematiskt: i en "icke-deterministisk" beräkningsmodell , känd som en " icke- deterministisk automat " .

Utveckling av algoritmer

I algoritmdesign används ofta " icke- deterministiska " algoritmer när problemet som löses av algoritmen - i sig - gör att många utgångar kan hittas (eller - när det finns en utgång med många vägar genom vilka den kan hittas , och alla är "lika bra"). "). Det är viktigt att varje utdata från den " icke- deterministiska " algoritmen är sann ; - oavsett de vägar " valda " av algoritmen vid körning.

Exempel

"Inköpslista"

Föreställ dig en " inköpslista ": en lista över föremål att köpa - som kan ses på två sätt: som en instruktion för att köpa alla dessa föremål...

  • ...i valfri ordning (" icke- deterministisk " algoritm);
  • ...i den givna ordningen (en " deterministisk " algoritm).

"Sammanfoga sortering"

Antag att - det finns en uppsättning " entiteter " (säg - 300 studenter), som måste "beställas" (säg efter "antal" studenter). En algoritm för detta är " slå samman sortering ":

  • Dela upp setet i två ungefär lika stora grupper ;
  • Sortera båda grupperna efter den givna sorteringen (d.v.s. " rekursivt ");
  • Slå samman resultat (" slå samman "; se metodnamn).

Element kan sorteras " unikt " om sorteringskriteriet alltid definierar en " full " ordning (dvs. elevens "nummer" är " unika ": upprepa inte sinsemellan). Men annars (om du t.ex. sorterar tentor efter elevernas efternamn utan att ta hänsyn till namne ), är sorteringsresultatet inte definierat: det är inte känt vilken ordning som anses vara korrekt ; — d.v.s. Algoritmen är " icke- deterministisk ".

Enkelhetstestet

Uppgift : ett naturligt tal större än ett ges; avgöra om det är enkelt .

Lösning : Den "icke-deterministiska" algoritmen är följande:

  1. Ta vilket heltal som helst " k" så att 2 ≤ k ≤ √( n );
  2. Om " k" är en divisor av " n" - sluta med svaret " nej " ; annars sluta med svaret " okänt ".

Det kan ses att algoritmen inte alltid ger ett " användbart " svar, men aldrig ger ett fel svar.

Denna algoritm är " icke- deterministisk ": den producerar inte alltid en " användbar " lösning - men den kan, givet en viss kombination av val. Detta är ett exempel på en " sökning " typ av "icke-deterministisk" algoritm.

Se även