Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымдағы алгоритм түрі. Компьютерлік ғылымда детерминистік алгоритм – нақты бір кіріс мәліметі берілгенде, әрқашан бірдей нәтижені беретін, ал негізгі машина әрқашан бірдей күйлер тізбесінен өтетін алгоритм. Детерминистік алгоритмдер – ең көп зерттелген, жақсы таныс және практикалық қолданысы кең алгоритмдердің бірі, себебі оларды нақты машиналарда тиімді жүргізуге болады. Формальды түрде айтқанда, детерминистік алгоритм математикалық функцияны есептейді; функцияның әрбір кіріс мәні үшін бір ғана мәні болады, ал алгоритм – осы нақты мәнді нәтиже ретінде шығаратын процесс.
Type of algorithm in computer science
In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by far the most studied and familiar kind of algorithm, as well as one of the most practical, since they can be run on real machines efficiently. Formally, a deterministic algorithm computes a mathematical function; a function has a unique value for any input in its domain, and the algorithm is a process that produces this particular value as output.
Ресми анықтама
Детерминистік алгоритмдерді күй машинасы түрінде анықтауға болады: күй машинаның нақты бір уақыт сәтінде не істеп жатқанын көрсетеді. Күй машиналары дискретті түрде бір күйден екінші күйге өтеді. Енгізілген деректерден кейін машина бастапқы күйге немесе іске қосылу күйіне енеді. Егер машина детерминистік болса, онда осы сәттен бастап оның ағымдағы күйі келесі күйін анықтайды; күйлер жиынтығы арқылы өту жолы алдын ала белгіленген. Машина детерминистік бола тұра тоқтамай немесе аяқтамай, нәтиже бермей қалуы мүмкін екенін ескеру қажет. Детерминистік абстрактілі машиналардың мысалдарына детерминистік Тьюринг машинасы және детерминистік шекті автомат жатады.
Deterministic algorithms can be defined in terms of a state machine: a state describes what a machine is doing at a particular instant in time. State machines pass in a discrete manner from one state to another. Just after we enter the input, the machine is in its initial state or start state. If the machine is deterministic, this means that from this point onwards, its current state determines what its next state will be; its course through the set of states is predetermined. Note that a machine can be deterministic and still never stop or finish, and therefore fail to deliver a result. Examples of particular abstract machines which are deterministic include the deterministic Turing machine and deterministic finite automaton.
Детерминизмнің кемшіліктері
Кейбір жағдайларда бағдарламаның детерминистік емес мінез-құлық көрсетуі тиімді болуы мүмкін. Мысалы, блэкджек ойынында қолданылатын карталарды шайқау бағдарламасының мінез-құлқы ойыншыларға болжауға мүмкіндік бермеуі керек, тіпті бағдарламаның бастапқы коды көрінетін болса да. Псевдокездейсоқ сан генераторын пайдалану, ойыншылардың шайқау нәтижесін болжау мүмкіндігін толыққанды қамтамасыз ету үшін жеткіліксіз болуы мүмкін. Ақылды ойыншы генератор таңдайтын сандарды дәл болжап, колоданың құрамын алдын ала анықтап, алдауға мүмкіндік алады. Мысалы, Reliable Software Technologies компаниясының бағдарламалық қауіпсіздік тобы, ASF Software, Inc. компаниясы таратқан Texas Hold 'em Poker іске асырылымында мұны жасап, қолдардың нәтижесін алдын ала болжауға қол жеткізді. Бұл мәселелерді криптографиялық тұрғыдан қамтамасыз етілген псевдокездейсоқ сан генераторын пайдалану арқылы ішінара болдыруға болады, бірақ генераторды бастау үшін әлі де болжауға келмейтін кездейсоқ бастама қажет. Осы мақсатта, аппараттық кездейсоқ сан генераторы сияқты детерминистік емес көз қажет. P=NP мәселесіне теріс жауап, детерминистік емес шығысы бар бағдарламалардың, детерминистік шығысы бар бағдарламалардан теориялық тұрғыдан күштірек екенін білдірмейді. NP күрделілік класын (көптігін) тексеруге негізделген анықтаманы қолдана отырып, детерминистік емес элементтерге сілтеме жасамай анықтауға болады.
It is advantageous, in some cases, for a program to exhibit nondeterministic behavior. The behavior of a card shuffling program used in a game of blackjack, for example, should not be predictable by players — even if the source code of the program is visible. The use of a pseudorandom number generator is often not sufficient to ensure that players are unable to predict the outcome of a shuffle. A clever gambler might guess precisely the numbers the generator will choose and so determine the entire contents of the deck ahead of time, allowing him to cheat; for example, the Software Security Group at Reliable Software Technologies was able to do this for an implementation of Texas Hold 'em Poker that is distributed by ASF Software, Inc, allowing them to consistently predict the outcome of hands ahead of time. These problems can be avoided, in part, through the use of a cryptographically secure pseudo random number generator, but it is still necessary for an unpredictable random seed to be used to initialize the generator. For this purpose, a source of nondeterminism is required, such as that provided by a hardware random number generator. Note that a negative answer to the P=NP problem would not imply that programs with nondeterministic output are theoretically more powerful than those with deterministic output. The complexity class NP (complexity) can be defined without any reference to nondeterminism using the verifier based definition.
Жиде
Меркурийлік логикалық функционалдық бағдарламалау тілі анықтамада көрсетілгендей, предикат режимдері үшін әртүрлі детерминизм санаттарын орнатады.
The mercury logic functional programming language establishes different determinism categories for predicate modes as explained in the reference.
Жава
Java-да нөлдік сілтеме мәні сәтсіз (қалыптан тыс) нәтижені көрсете алады.
In Java, the null reference value may represent an unsuccessful (out of domain) result.