Algoritm minga deterministich

On algoritm minga deterministich a l'è on algoritm che anca cont el midemm input el pò mostrà di comportament different de esecuzion a esecuzion. A hinn tipicament doperaa per trovà l'approssimazion de 'n resultaa che 'l saria tropp oneros de trovà per intregh.

La class la comprend anca i algoritm concorrent de che l'esecuzion la depend de quella de 'n alter algoritm e i algoritm randomizaa, che veden el doperà de on numer casual.

 Esempi 
El test minga deterministich pussee famos a l'è quell de primalità, fondaa in sul teorema piscininn de Fermat:
 Fàll 30 voeult:
 Ciappa on intregh random a che 'l sia 2 ≤ a ≤ n-1.
 Se , respond compost
 Sedenò respond probabilment primm.

Se el respond compost, el numer a l'è de sigur minga primm, se inveci el respond probabilment primm a gh'è una volta possibilità che 'l numer el sia primm, ma anca ona bassa possibilità che el sia compost, donca on pseudoprimm. Anca per via de la selezion di numer random ogni esecuzion del software la sarà differenta di alter.

 Vos correlaa 
P vs NP
Informatega quantistega
Test de Fermat

Categoria:Algoritmega