Algoritme determinista

En ciències de la computació, un algoritme determinista és un algoritme que, en térmens informals, és completament predictiu si es coneixen els seus entradas. Dit d'una atra forma, si es coneixen les entrades de l'algoritme sempre produirà la mateixa eixida, i la màquina interna passarà per la mateixa seqüència d'estats. Este tipo d'algoritmes ha segut el més estudiat durant l'història i per lo tant resulta ser el tipo més familiar dels algoritmes, aixina com el més pràctic ya que pot eixecutar-se en les màquines eficientemente.

Un model simple d'algoritme determinista és la funció matemàtica, puix esta extrau sempre la mateixa eixida per a una entrada donada. No obstant un algoritme descriu explícitament cóm l'eixida s'obté de l'entrada, mentres que les funcions definixen implícitament la seua eixida.

Definició formal

Formalment els algoritmes determinista es poden definir en térmens d'una màquina d'estat; un «estat» descriu qué està fent la màquina en un instant particular de temps. Just quan es produïx l'entrada, la màquina comença en el seu «estat inicial» i, posteriorment, si la màquina és determinista, començarà l'eixecució de la seqüència d'estats predeterminats. Una màquina pot ser determinista i no tindre llímit temporal per a l'eixecució o quedar-se en un bucle d'estats cíclicos eternament.

Eixemples de màquines abstractes determinista són les màquines de Turing determinista i els autómates finitos determinista.

Modo pel qual els algoritme deterministicos pot tornar-se no determinista

Per diversos motius un algoritme determinista pot comportar-se d'una forma no determinista:

• Si ampra en l'eixecució de la seqüència d'estats atre estat «extern» com a entrada del procés; per eixemple: una entrada d'un usuari, una variable objectiu, un valor d'un temporisador de hardware, un valor aleatori, etc.
• Si en operar es troba en concurrència d'estats; per eixemple, si té múltiples processadors escrivint al mateix temps en un ficher. En este cas l'orde precís en el que cada processador escriu la senya pot afectar a l'eixida.
• Si un error (l'orige del qual pot deure's al hardware o al software) causa un inesperat canvi en la seqüència d'eixecució d'estats.

Encara que els programes reals rara volta són purament determinista, és convenient considerar que sí ho són ya que és més fàcil raonar sobre estos. Per este motiu, la majoria dels llenguages de programació i especialment aquells que entren dins de la categoria de la programació funcional són llenguages que fan un esforç en previndre events que s'eixecuten sense control. Este tipo de restriccions forcen el caràcter determinista i per això als algoritmes determinista se'ls sol denominar purament funcionals.

La prevalença dels processadors de varis núcleus ha alçat l'interés pel determinisme en la programació en paralel i s'han documentat be els problemes del no determinisme. Numeroses ferramentes útils en estos problemes s'han propost per a tractar en els bloquejos mutus i les condiciones de carrera.

Vore també

• Algoritme no determinista