Algoritm minga deterministich

Quest articol chì l'è scrivuu in lombard, grafia milanesa.

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.

Differenza in tra i algoritm deterministich e quej minga determinalistich

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:

1. Fàll 30 voeult:
   1. Ciappa on intregh random a che 'l sia 2 ≤ a ≤ n-1.
   2. Se $a^{n-1}\neq 1{\pmod {n}}$, respond compost
2. 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