Детерминистички алгоритам
У компјутерској науци, детерминистички алгоритам је алгоритам који, дат као посебан улаз, увек ће произвести исти излаз, уз основну машину увек пролази кроз исти низ стања. Детерминистички алгоритми су далеко највише проучавана и позната врста алгоритма, као и један од најпрактичнијих, јер они могу бити покренути на стварним машинама ефикасно.
Формално, детерминистички алгоритам израчунава математичку функцију; функција има јединствену вредност за сваки улаз у свом домену, и алгоритам је процес који производи ову конкретну вредност као излаз.
Формална дефиниција уреди
Детерминистички алгоритми се могу дефинисати у смислу машине стања: стање описује оно што машина ради у одређеном тренутку у времену. Машине стања пролазе на дискретан начин из једног стања у други. Одмах након што улазимо у улаз, машина је у првобитно стању или у стартном стању. Ако је машина детерминистички, то значи да од тог тренутка па надаље, његово тренутно стање одређује шта његово следеће стање ће бити; њен ток кроз скуп стања је предодређен. Имајте на уму да једна машина може бити детерминистичка и даље да не заустави или заврши обраду, а самим тим не донесе резултат.
примери појединих апстрактним машина које су детерминистичке укључују детерминистичку Тјурингову Машину и детерминистички коначни аутомат.
Шта прави алгоритме не-детерминистичким? уреди
Различити фактори могу изазвати алгоритам да се понаша на начин који није детерминистички, или не-детерминистички:
- Ако користи спољашње стање осим улаза, као што су кориснични улаз, глобалне променљиве, а хардвер вредност тајмера, случајних вредности, или сачуваних података диска.
- Ако ради на начин који је тајминг осетљив, на пример, ако више процесора пишу истим подацима у исто време. У овом случају, прецизан редослед у којем сваки процесор пише његове податке ће утицати на резултат.
- Ако хардверска грешка изазива његово стање да се промени на неочекиван начин.
Иако прави програми су ретко чисто детерминистички, то је лакше за људе, као и други програми за разлог о програмима који су. Из тог разлога, већина програмских језика и нарочито функционални програмски језици направе напор да спрече горенаведене догађаје да се дешавају осим под контролисаним условима.
Распрострањеност мулти-кор процесора је резултирала великим порастом интересовања за детерминизам у паралелном програмирању и изазове не-детерминизам за добро документовани.[1][2]Велики број алата за помоћ договора са предложеним су изазови[3][4][5][6][7] да се баве застојима и тркама услова.
Недостаци Детерминизма уреди
То је предност, у неким случајевима, за програм да излаже недетерминистичко понашање. Понашање програма картица мешањем се користи у игри ајнс, на пример, не би требало да буде предвидива играчима - чак и ако је изворни код програма видљив. Употреба псеудослучајних броја генератор често није довољан да осигура да играчи нису у стању да предвиди исход мешања. Памеран коцкар може да погоди тачно бројеве које ће генератор изабрати и тако одредити комплетан садржај палуби испред времена, омогућавајући му да превари; на пример, софтвер безбедност група на поуздан софтвер технологија је у стању да уради ово за имплементацију Текас Холдем Покера који се дистрибуира преко АСФ Софтвара, Инц, омогућавајући им да доследно предвиде исход рукама испред времена.[8]Ови проблеми се могу избећи, делимично, кроз употребу криптографских сигурних псеудо-случајних бројева генератора, али и даље је неопходно за непредвидљиво случајно семе да се користи да покрене генератор. У ту сврху је потребан извор нодетерминистички, као што је обезбеђен од стране хардвера случајних бројева генератора.
Имајте на уму да је негативан одговор на P =NP проблем не би указивао да програми са недетерминистичким излазима су теоретски моћнији од оних са детерминистичким излазима. Класа Комплексности NP (сложеност) може дефинисати без помињања недетерминистичких коришћења дефиниције верификатора-основе.
Категорије детерминизма у језицима уреди
Меркур уреди
Овај логички-функционални програмски језик успостављa различите категорије детерминизма за предикатни режим као што је објашњено у реф.[9][10]
Хаскел уреди
Хаскел обезбеђује неколико механизама:
- не-детерминизам или појам неизвршења
- Можда и било типови су појам успеха у резултату.
- не метод класе Монад, може се користити за сигнализирање пропасти као изузетак.
- Можда монад и Можда Т монад трансформатор обезбеђују пропало израчунавање (зауставити израчунавања редослед и вратити Ништа)
[11]
- детерминизам и не-детерминизам са више решења
- можете преузети све могуће исходе обрачуна вишеструког резултата, уметнути своју врсту резултата у МонадПлус монаду. (његов метод мзеро чини исход и Мплус прикупља успешне резултате).
[12]
МЛ породица и изведени језици уреди
Као што се види у Стандардном МЛ,ОКАМЛ и Скали
- Тип опција укључује појам успеха.
Јава уреди
- Нулта референтна вредност може се представљати неуспешно (ван домена) резултата.
Референце уреди
- ^ Lee, Edward A. „The Problem with Threads” (PDF). Приступљено 29. 05. 2009.
- ^ Reinders, James. „Parallel terminology definitions”. Архивирано из оригинала 24. 02. 2012. г. Приступљено 29. 05. 2009.
- ^ „Intel Parallel Inspector Thread Checker”. Приступљено 29. 05. 2009.
- ^ Lin, Yuan. „Data Race and Deadlock Detection with Sun Studio Thread Analyzer” (PDF). Приступљено 29. 05. 2009.
- ^ Intel. „Intel Parallel Inspector”. Приступљено 29. 05. 2009.
- ^ Worthington, David. „Intel addresses development life cycle with Parallel Studio”. Архивирано из оригинала 28. 05. 2009. г. Приступљено 26. 05. 2009.
- ^ Parallel Studio
- ^ Gary McGraw and John Viega.
- ^ „Determinism categories in the Mercury programming language”. Архивирано из оригинала 03. 07. 2012. г. Приступљено 27. 11. 2015.
- ^ „Mercury predicate modes”. Архивирано из оригинала 03. 07. 2012. г. Приступљено 27. 11. 2015.
- ^ Representing failure using the Maybe monad
- ^ The class MonadPlus