Theory and Algorithms

In che modo i computer o gli esseri umani risolvono i problemi? Come possono farlo velocemente, nonostante il numero di dati sempre crescente? Una sequenza ben definita di passi che mirano a risolvere un problema è chiamata algoritmo e lo studio sistematico degli algoritmi è una dei temi principali dell'informatica.

Immaginiamo di avere un terrazzo rettangolare e di essere alla ricerca della piastrella quadrata più grande che ti permetta di ricoprire esattamente la superficie disponibile con il minore scarto: qual è il modo migliore e più veloce per farlo? La risposta la diede Euclide più di 2000 ani fa ed il suo metodo è uno dei più antichi algoritmi conosciuti. Nella vita di tutti i giorni, come può il nostro GPS calcolare il percorso migliore per portarci a destinazione? Un moderno algoritmo chiamato 'cammino minimo' potrebbe essere silenziosamente al lavoro. In poche parole un algoritmo è ciò che si trova dietro a tutto ciò che un computer può fare.

La ricerca nel campo degli algoritmi cerca di trovare il modo migliore e più veloce per risolvere un problema. Potrebbe anche occuparsi della ricerca di problemi per i quali non esiste un metodo veloce di risoluzione. Quest'ultimi ci permettono di elaborare schemi di cifratura difficili da decifrare, consentendone la crittografia. La suddivisione dei problemi in categorie a seconda della loro difficoltà computazionale (durezza) è un argomento centrale nella teoria della computazione.