Categories
fantascienza informatica matematica programmazione

Algoritmi e curve temporali

Come programmatore sono sempre stato affascinato dagli algoritmi, specialmente se compatti ed eleganti

Ci sono, però, dei problemi per la cui soluzione non esistono algoritmi efficienti; di contro, per gli stessi problemi, se viene presentata una soluzione, questa è immediatamente e facilmente verificabile come corretta. Prendete, per esempio, una mappa con un sacco di isole e ponti: non esiste un algoritmo efficiente che tracci un percorso per visitare tutte le isole una sola volta, ma se vi viene presentata una soluzione, è facile capire se sia corretta. Un altro problema da un lato più teorico, ma con tremende ripercussioni pratiche è, dato un numero, capire se sia il prodotto di due numeri primi e di quali. Se quest’ultimo problema è semplice con numeri piccoli, non lo è, fortunatamente, per numeri molto grossi. Perché «fortunatamente»? Perché la gran parte di transazioni informatiche crittografate si basa su questo assunto. Se leggete che qualcuno ha trovato un algoritmo per fattorizzare rapidamente numeri di grandi dimensioni, iniziate a preoccuparvi davvero.