Deterministički algoritam
U kompjuterskoj nauci, deterministički algoritam je algoritam koji, dat kao poseban ulaz, uvek će proizvesti isti izlaz, uz osnovnu mašinu uvek prolazi kroz isti niz stanja. Deterministički algoritmi su daleko najviše proučavana i poznata vrsta algoritma, kao i jedan od najpraktičnijih, jer oni mogu biti pokrenuti na stvarnim mašinama efikasno.
Formalno, deterministički algoritam izračunava matematičku funkciju; funkcija ima jedinstvenu vrednost za svaki ulaz u svom domenu, i algoritam je proces koji proizvodi ovu konkretnu vrednost kao izlaz.
Formalna definicija[uredi | uredi izvor]
Deterministički algoritmi se mogu definisati u smislu mašine stanja: stanje opisuje ono što mašina radi u određenom trenutku u vremenu. Mašine stanja prolaze na diskretan način iz jednog stanja u drugi. Odmah nakon što ulazimo u ulaz, mašina je u prvobitno stanju ili u startnom stanju. Ako je mašina deterministički, to znači da od tog trenutka pa nadalje, njegovo trenutno stanje određuje šta njegovo sledeće stanje će biti; njen tok kroz skup stanja je predodređen. Imajte na umu da jedna mašina može biti deterministička i dalje da ne zaustavi ili završi obradu, a samim tim ne donese rezultat.
primeri pojedinih apstraktnim mašina koje su determinističke uključuju determinističku Tjuringovu Mašinu i deterministički konačni automat.
Šta pravi algoritme ne-determinističkim?[uredi | uredi izvor]
Različiti faktori mogu izazvati algoritam da se ponaša na način koji nije deterministički, ili ne-deterministički:
- Ako koristi spoljašnje stanje osim ulaza, kao što su korisnični ulaz, globalne promenljive, a hardver vrednost tajmera, slučajnih vrednosti, ili sačuvanih podataka diska.
- Ako radi na način koji je tajming osetljiv, na primer, ako više procesora pišu istim podacima u isto vreme. U ovom slučaju, precizan redosled u kojem svaki procesor piše njegove podatke će uticati na rezultat.
- Ako hardverska greška izaziva njegovo stanje da se promeni na neočekivan način.
Iako pravi programi su retko čisto deterministički, to je lakše za ljude, kao i drugi programi za razlog o programima koji su. Iz tog razloga, većina programskih jezika i naročito funkcionalni programski jezici naprave napor da spreče gorenavedene događaje da se dešavaju osim pod kontrolisanim uslovima.
Rasprostranjenost multi-kor procesora je rezultirala velikim porastom interesovanja za determinizam u paralelnom programiranju i izazove ne-determinizam za dobro dokumentovani.[1][2]Veliki broj alata za pomoć dogovora sa predloženim su izazovi[3][4][5][6][7] da se bave zastojima i trkama uslova.
Nedostaci Determinizma[uredi | uredi izvor]
To je prednost, u nekim slučajevima, za program da izlaže nedeterminističko ponašanje. Ponašanje programa kartica mešanjem se koristi u igri ajns, na primer, ne bi trebalo da bude predvidiva igračima - čak i ako je izvorni kod programa vidljiv. Upotreba pseudoslučajnih broja generator često nije dovoljan da osigura da igrači nisu u stanju da predvidi ishod mešanja. Pameran kockar može da pogodi tačno brojeve koje će generator izabrati i tako odrediti kompletan sadržaj palubi ispred vremena, omogućavajući mu da prevari; na primer, softver bezbednost grupa na pouzdan softver tehnologija je u stanju da uradi ovo za implementaciju Tekas Holdem Pokera koji se distribuira preko ASF Softvara, Inc, omogućavajući im da dosledno predvide ishod rukama ispred vremena.[8]Ovi problemi se mogu izbeći, delimično, kroz upotrebu kriptografskih sigurnih pseudo-slučajnih brojeva generatora, ali i dalje je neophodno za nepredvidljivo slučajno seme da se koristi da pokrene generator. U tu svrhu je potreban izvor nodeterministički, kao što je obezbeđen od strane hardvera slučajnih brojeva generatora.
Imajte na umu da je negativan odgovor na P =NP problem ne bi ukazivao da programi sa nedeterminističkim izlazima su teoretski moćniji od onih sa determinističkim izlazima. Klasa Kompleksnosti NP (složenost) može definisati bez pominjanja nedeterminističkih korišćenja definicije verifikatora-osnove.
Kategorije determinizma u jezicima[uredi | uredi izvor]
Merkur[uredi | uredi izvor]
Ovaj logički-funkcionalni programski jezik uspostavlja različite kategorije determinizma za predikatni režim kao što je objašnjeno u ref.[9][10]
Haskel[uredi | uredi izvor]
Haskel obezbeđuje nekoliko mehanizama:
- ne-determinizam ili pojam neizvršenja
- Možda i bilo tipovi su pojam uspeha u rezultatu.
- ne metod klase Monad, može se koristiti za signaliziranje propasti kao izuzetak.
- Možda monad i Možda T monad transformator obezbeđuju propalo izračunavanje (zaustaviti izračunavanja redosled i vratiti Ništa)
[11]
- determinizam i ne-determinizam sa više rešenja
- možete preuzeti sve moguće ishode obračuna višestrukog rezultata, umetnuti svoju vrstu rezultata u MonadPlus monadu. (njegov metod mzero čini ishod i Mplus prikuplja uspešne rezultate).
[12]
ML porodica i izvedeni jezici[uredi | uredi izvor]
Kao što se vidi u Standardnom ML,OKAML i Skali
- Tip opcija uključuje pojam uspeha.
Java[uredi | uredi izvor]
- Nulta referentna vrednost može se predstavljati neuspešno (van domena) rezultata.
Reference[uredi | uredi izvor]
- ^ Lee, Edward A. „The Problem with Threads” (PDF). Pristupljeno 29. 05. 2009.
- ^ Reinders, James. „Parallel terminology definitions”. Arhivirano iz originala 24. 02. 2012. g. Pristupljeno 29. 05. 2009.
- ^ „Intel Parallel Inspector Thread Checker”. Pristupljeno 29. 05. 2009.
- ^ Lin, Yuan. „Data Race and Deadlock Detection with Sun Studio Thread Analyzer” (PDF). Pristupljeno 29. 05. 2009.
- ^ Intel. „Intel Parallel Inspector”. Pristupljeno 29. 05. 2009.
- ^ Worthington, David. „Intel addresses development life cycle with Parallel Studio”. Arhivirano iz originala 28. 05. 2009. g. Pristupljeno 26. 05. 2009.
- ^ Parallel Studio
- ^ Gary McGraw and John Viega.
- ^ „Determinism categories in the Mercury programming language”. Arhivirano iz originala 03. 07. 2012. g. Pristupljeno 27. 11. 2015.
- ^ „Mercury predicate modes”. Arhivirano iz originala 03. 07. 2012. g. Pristupljeno 27. 11. 2015.
- ^ Representing failure using the Maybe monad
- ^ The class MonadPlus