Algorisme determinista
En informàtica, un algorisme determinista és un algorisme que, donada una entrada particular, sempre produirà la mateixa sortida, amb la màquina subjacent passant sempre per la mateixa seqüència d'estats. Els algorismes deterministes són, amb diferència, el tipus d'algorisme més estudiat i familiar, així com un dels més pràctics, ja que es poden executar en màquines reals de manera eficient.[1]
Formalment, un algorisme determinista calcula una funció matemàtica; una funció té un valor únic per a qualsevol entrada del seu domini, i l'algorisme és un procés que produeix aquest valor particular com a sortida.
Definició formal
[modifica]Els algorismes deterministes es poden definir en termes d'una màquina d'estats: un estat descriu el que fa una màquina en un instant concret. Les màquines d'estats passen de manera discreta d'un estat a un altre. Just després d'introduir l'entrada, la màquina es troba en el seu estat inicial o estat d'inici. Si la màquina és determinista, això vol dir que a partir d'aquest punt, el seu estat actual determina quin serà el seu següent estat; el seu curs a través del conjunt d'estats està predeterminat. Cal tenir en compte que una màquina pot ser determinista i, tot i així, no aturar-se ni acabar mai, i per tant no aconsegueix oferir un resultat.
Exemples de màquines abstractes particulars que són deterministes inclouen la màquina de Turing determinista i l'autòmat finit determinista.
algorismes no deterministes
[modifica]Diversos factors poden fer que un algorisme es comporti d'una manera que no sigui determinista o no determinista:
- Si utilitza un estat extern diferent de l'entrada, com ara l'entrada de l'usuari, una variable global, un valor de temporitzador de maquinari, un valor aleatori o dades de disc emmagatzemades.
- Si funciona d'una manera sensible al temps, per exemple, si té diversos processadors que escriuen a les mateixes dades alhora. En aquest cas, l'ordre precís en què cada processador escriu les seves dades afectarà el resultat.
- Si un error de maquinari fa que el seu estat canviï de manera inesperada.
Tot i que els programes reals rarament són purament deterministes, és més fàcil per als humans, així com per a altres programes, raonar sobre programes que sí que ho són. Per aquest motiu, la majoria de llenguatges de programació, i especialment els llenguatges de programació funcional, fan un esforç per evitar que els esdeveniments anteriors passin, excepte en condicions controlades.
La prevalença dels processadors multinucli ha provocat un augment de l'interès pel determinisme en la programació paral·lela i els reptes del no determinisme han estat ben documentats.[2][3] S'han proposat diverses eines per ajudar a afrontar els reptes[4][5][6][7] per fer front als interbloquejos i les condicions de carrera .
Desavantatges del determinisme
[modifica]En alguns casos, és avantatjós que un programa mostri un comportament no determinista. El comportament d'un programa de barreja de cartes utilitzat en un joc de blackjack, per exemple, no hauria de ser predictible pels jugadors, fins i tot si el codi font del programa és visible. L'ús d'un generador de nombres pseudoaleatoris sovint no és suficient per garantir que els jugadors no puguin predir el resultat d'una barreja. Un jugador intel·ligent podria endevinar amb precisió els nombres que triarà el generador i així determinar tot el contingut de la baralla amb antelació, cosa que li permetria fer trampa; per exemple, el Grup de Seguretat de Programari de Reliable Software Technologies va poder fer-ho per a una implementació de Texas Hold 'em Poker distribuïda per ASF Software, Inc, cosa que els va permetre predir de manera consistent el resultat de les mans amb antelació.[8] Aquests problemes es poden evitar, en part, mitjançant l'ús d'un generador de nombres pseudoaleatoris criptogràficament segur, però encara és necessari que s'utilitzi una llavor aleatòria impredictible per inicialitzar el generador. Per a aquest propòsit, es requereix una font de no determinisme, com la que proporciona un generador de nombres aleatoris de maquinari.
Cal tenir en compte que una resposta negativa al problema P=NP no implicaria que els programes amb sortida no determinista siguin teòricament més potents que els que tenen una sortida determinista. La classe de complexitat NP (complexitat) es pot definir sense cap referència al no determinisme utilitzant la definició basada en verificadors.
Referències
[modifica]- ↑ «Difference between Deterministic and Non-deterministic Algorithms» (en anglès), 11-09-2018. [Consulta: 15 novembre 2025].
- ↑ Edward A. Lee. «The Problem with Threads» (en anglès). [Consulta: 29 maig 2009].
- ↑ Bocchino Jr.. "Parallel Programming Must Be Deterministic by Default" a USENIX Workshop on Hot Topics in Parallelism.
- ↑ «Intel Parallel Inspector Thread Checker» (en anglès). [Consulta: 29 maig 2009].
- ↑ Yuan Lin. «Data Race and Deadlock Detection with Sun Studio Thread Analyzer» (en anglès). [Consulta: 29 maig 2009].
- ↑ Intel. «Intel Parallel Inspector» (en anglès). [Consulta: 29 maig 2009].
- ↑ David Worthington. «Intel addresses development life cycle with Parallel Studio» (en anglès). Arxivat de l'original el 2009-05-28. [Consulta: 26 maig 2009].
- ↑ McGraw, Gary. «Make your software behave: Playing the numbers: How to cheat in online gambling.» (en anglès). IBM. Arxivat de l'original el 2008-03-13. [Consulta: 2 juliol 2007].
