9 : Analisi degli Algoritmi Vers . 2.0 – Aprile 2022
PROBLEMI INTRATTABILI
E ’ necessario guardare con molta diffidenza agli algoritmi dotati di complessità computazionale esponenziale poiché necessitano di tempi di esecuzione proibitive anche per valori non molto grandi di N . Purtroppo esistono molti problemi , anche di interesse pratico , per i quali non si conoscono algoritmi non esponenziali . Chiameremo intrattabili tali problemi .
A volte è una fortuna che un problema sia intrattabile ; basti pensare ai sistemi di crittografia che garantiscono una elevata sicurezza perché gli algoritmi di decrittografia ( che cercano di decifrare un messaggio senza conoscere la parola chiave ) sono di complessità esponenziale .
CONSIDERAZIONI FINALI
Ciò che è stato detto finora permette di affrontare un qualsiasi algoritmo sotto una nuova ottica , diversa da quella precedente che possiamo riassumere come l ’ ottenimento dei risultati voluti . Questi infatti potrebbero arrivare subito o anche non arrivare mai o addirittura arrivare dopo secoli di tempo di elaborazione per dimensione del problema maggiore .
Quindi è indispensabile per un buon analista alla ricerca di un algoritmo che risolva un problema valutare attentamente l ’ ordine di complessità di quello trovato non accontentandosi del primo trovato soprattutto se tale ordine di complessità risultasse troppo elevato o addirittura esponenziale ( intrattabile ).
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 14