Algoritmiper Svogliati
Per chi non ne sa niente: cos'è un algoritmo, perché uno è veloce e un altro no, come si mette in ordine un milione di cose, come fa il navigatore a trovare la strada, e perché certi problemi non li risolve nessuno. Con le barre da riordinare e guardare.
"Il mio programma è lento, compro un server più grosso." — "Che algoritmo usi?" — "Boh, due cicli for." — "Ecco."
Cos'è un algoritmo
Una ricetta. Passi precisi, in ordine, che partono da qualcosa e arrivano a un risultato. Il computer non c'entra: sapevi già farne tanti.
"Metti l'acqua, quando bolle butta la pasta, intanto rosola il guanciale…". È un algoritmo: ingredienti in ingresso, passi in ordine, un piatto in uscita. Ma per un computer "quando bolle" e "un po' di pecorino" non bastano: ogni passo deve essere preciso, e la ricetta deve finire. Un computer che segue "mescola finché è buono" mescola per sempre.
Ingressi
Da cosa parte: una lista di nomi, una mappa, un numero.
Passi precisi
Ognuno senza ambiguità, che chiunque, anche una macchina, eseguirebbe allo stesso modo.
Una fine
Prima o poi si ferma, con un risultato. Se non si ferma, non è un algoritmo: è un guaio.
Il punto interessante non è che gli algoritmi esistano, ma che per lo stesso problema ce ne sono di buoni e di pessimi. Con mille elementi non te ne accorgi. Con un miliardo, uno finisce in un secondo e l'altro tra qualche secolo. Questa guida parla di questa differenza.
Un po' di storia
Gli algoritmi sono più vecchi dei computer di un paio di millenni.
Euclide
Negli Elementi c'è il modo per trovare il massimo comune divisore di due numeri: togli il più piccolo dal più grande, ripeti. È considerato uno dei più antichi algoritmi ancora in uso, ed è dentro la crittografia di oggi.
al-Khwarizmi
Il matematico persiano di Baghdad scrive i libri che portano in Europa i numeri indiani e i metodi per fare i conti passo passo. Dal suo nome latinizzato, Algoritmi, viene la parola "algoritmo"; da un suo titolo, "algebra".
Ada Lovelace
Nelle note sulla macchina analitica di Babbage, mai costruita, descrive passo per passo come calcolare i numeri di Bernoulli. È considerato il primo programma della storia, scritto per un computer che non esisteva.
Turing
Alan Turing definisce cosa vuol dire "calcolabile" con una macchina immaginaria fatta di un nastro e di poche regole. E dimostra che ci sono domande a cui nessun algoritmo potrà mai rispondere.
Dijkstra e Hoare
Edsger Dijkstra trova il percorso più breve in un grafo, pensandoci in una ventina di minuti seduto al tavolino di un caffè ad Amsterdam, così raccontava. Tony Hoare inventa il quicksort, l'ordinamento che ancora oggi sta dentro mezzo mondo.
PageRank
Due studenti di Stanford, Larry Page e Sergey Brin, ordinano le pagine web contando chi le linka e quanto conta chi le linka. Da quell'algoritmo nasce Google.
Veloce o lento: la "O grande" senza matematica
Non conta quanti secondi ci mette oggi. Conta come cresce il lavoro quando i dati diventano dieci, cento, mille volte di più.
| Si scrive | Si legge | Esempio | Con 1.000 elementi | Con 1 milione |
|---|---|---|---|---|
O(1) | Costante: non dipende da quanti sono | Prendere il terzo elemento di una lista | 1 passo | 1 passo |
O(log n) | Logaritmica: quasi gratis | Cercare in un elenco ordinato | ~10 passi | ~20 passi |
O(n) | Lineare: tanti dati, tanto lavoro | Leggerli tutti una volta | 1.000 | 1 milione |
O(n log n) | Poco più che lineare | Gli ordinamenti buoni | ~10.000 | ~20 milioni |
O(n²) | Quadratica: esplode | Gli ordinamenti alla buona, due cicli uno dentro l'altro | 1 milione | 1.000 miliardi |
O(n²). Va benissimo per cento elementi, è un disastro per un milione. Se il tuo script rallenta molto più di quanto crescono i dati, cerca i cicli annidati.
Cercare: uno per uno, o a metà
Il primo algoritmo veloce che tutti usano senza saperlo: quello dell'elenco del telefono.
🐢 Ricerca lineare
Guardi il primo, poi il secondo, poi il terzo… finché lo trovi. Funziona sempre, anche se i dati sono in disordine. Ma con un milione di elementi, nel caso peggiore, li guardi tutti.
🐇 Ricerca binaria
Solo su dati ordinati. Apri a metà: se cerchi una parola che viene dopo, butti via la prima metà. Ripeti sulla metà rimasta. Con un milione di elementi bastano una ventina di tentativi.
def cerca(lista, cosa):
sx, dx = 0, len(lista) - 1
while sx <= dx:
meta = (sx + dx) // 2
if lista[meta] == cosa: return meta
if lista[meta] < cosa: sx = meta + 1 # sta a destra
else: dx = meta - 1 # sta a sinistra
return None
Ecco perché si ordina: ordinare costa, ma una volta fatto ogni ricerca diventa quasi gratis. È lo stesso motivo per cui i database hanno gli indici.
Ordinare, alla buona
Tre modi che ti verrebbero in mente da solo, con un mazzo di carte in mano. Funzionano. Sono lenti.
Bubble sort
Confronti due vicini e li scambi se sono al contrario. Ripeti finché non serve più nessuno scambio. I più grandi "salgono" in fondo come bolle.
Inserimento
Come le carte in mano: prendi la prossima e la fai scivolare a sinistra finché non trova il suo posto. Velocissimo se i dati sono già quasi in ordine.
Selezione
Cerchi il più piccolo di tutti e lo metti primo. Poi il più piccolo dei rimasti, e così via. Pochi scambi, tanti confronti.
def ordina(a):
for i in range(1, len(a)):
j = i
while j > 0 and a[j - 1] > a[j]: # la carta va più a sinistra
a[j - 1], a[j] = a[j], a[j - 1]
j -= 1
return a
Tutti e tre sono O(n²): con il doppio dei dati, il quadruplo del lavoro. Per una ventina di elementi vanno benissimo, e infatti gli ordinamenti "seri" passano all'inserimento quando il pezzo da ordinare è piccolo.
Dividi e conquista: merge sort e quicksort
Il trucco che porta da O(n²) a O(n log n): un problema grande è difficile, due problemi piccoli no.
🔀 Merge sort
Dividi la lista a metà, poi ogni metà a metà, finché restano pezzi da un elemento solo, già ordinati per forza. Poi fondi i pezzi a due a due: fondere due liste ordinate è facile, guardi solo le due teste. Sempre veloce, anche nel caso peggiore, ma usa memoria in più.
⚡ Quicksort
Scegli un elemento, il "perno". Metti a sinistra i più piccoli e a destra i più grandi: il perno è già al suo posto. Ripeti sulle due parti. In media è il più veloce di tutti; con un perno scelto male, su dati già ordinati, diventa lento come gli altri.
sorted(lista) e hai finito. Gli algoritmi si studiano per capire, non per riscriverli.
Provalo: guarda come ordinano
Scegli un algoritmo e premi avvia. Guarda i contatori: è lì che si vede la differenza fra O(n²) e O(n log n).
Hai chiesto al sistema di ridurre le animazioni: qui niente movimento automatico, usa Passo o Completa.
Ricorsione: la funzione che chiama se stessa
Merge e quick sono ricorsivi: per ordinare una lista, ordinano due liste più piccole nello stesso modo.
Per sapere quante bambole ci sono: apri la prima, e conti quelle che ci sono dentro, con lo stesso metodo. Quando ne trovi una che non si apre, ti fermi. Due ingredienti: il caso base (la bambola piena, ci si ferma) e il passo (apri e ripeti sul pezzo più piccolo). Dimentica il caso base e le matrioske non finiscono mai.
def mcd(a, b):
if b == 0: # caso base: ci si ferma
return a
return mcd(b, a % b) # stesso problema, più piccolo
mcd(48, 18) # 6
Strutture dati: dove metti le cose
Un algoritmo veloce su una struttura sbagliata è lento lo stesso. È come cercare un libro: dipende se la libreria è in ordine o un mucchio sul pavimento.
| Struttura | Com'è | Veloce per | Lenta per |
|---|---|---|---|
| Array / lista | Caselle in fila, numerate | Prendere la casella numero 500 | Inserire in mezzo: devi spostare tutte quelle dopo |
| Lista concatenata | Ogni elemento sa dov'è il prossimo, come una caccia al tesoro | Inserire e togliere in mezzo | Arrivare al numero 500: devi passare da tutti |
Tabella hash (il dict di Python) | Una funzione trasforma la chiave nel numero della casella | "Dammi il telefono di Mario" in un colpo solo | Tenere le cose in ordine |
| Albero | Ogni nodo ha figli: i più piccoli a sinistra, i più grandi a destra | Cercare e inserire tenendo tutto in ordine | Se si sbilancia diventa una lista |
| Coda e pila | La fila alla posta, e la pila di piatti | Il primo arrivato, o l'ultimo appoggiato | Tutto il resto |
Il consiglio più utile della guida, se scrivi script: per controllare se una cosa c'è, usa un set o un dict, non una lista. if x in lista la scorre tutta; if x in insieme va diretto. In un ciclo su centomila elementi è la differenza fra un secondo e un'ora.
Grafi: il navigatore è un algoritmo del 1956
Città unite da strade, persone unite da amicizie, router uniti da cavi: sono tutti grafi. Punti e collegamenti, con un costo.
🧭 Dijkstra
Parti da casa. Guardi le città raggiungibili e segni quanto costa arrivarci. Poi ti sposti sempre in quella più vicina non ancora visitata, e aggiorni i costi delle sue vicine. Quando arrivi a destinazione, hai la strada più corta, garantito.
⭐ A*
Dijkstra più un'intuizione: preferisce le città che vanno nella direzione giusta, stimando la distanza in linea d'aria dalla meta. Esplora molto meno. I navigatori usano parenti stretti di questi due, con tante scorciatoie precalcolate.
Dove sei lo dice il GPS (c'è la guida GPS e Satelliti); la strada la trova un algoritmo come questo. E anche i router di internet usano lo stesso principio per scegliere dove mandare i pacchetti.
Goloso o furbo: il problema del resto
Dare il resto con meno monete possibile. Sembra banale. Non sempre lo è.
Il modo che usa ogni cassiere è goloso (greedy): prendi sempre la moneta più grande che ci sta, poi ripeti con quello che manca. Con gli euro funziona sempre. Ma prova con un paese immaginario che ha monete da 1, 3 e 4:
🍰 Algoritmo goloso
Fa la scelta che sembra migliore adesso, e non torna mai indietro. Veloce e semplice, a volte sbaglia. Va bene quando si può dimostrare che il meglio di adesso porta al meglio alla fine, come con gli euro.
🧩 Programmazione dinamica
Risolve prima i problemi piccoli e si segna le risposte: il resto migliore per 1, per 2, per 3… fino a 6. Ogni risposta si costruisce dalle precedenti, senza rifare i conti. Più lenta, ma trova sempre l'ottimo.
def resto(totale, monete=(1, 3, 4)):
meglio = [0] + [float("inf")] * totale # meglio[x] = monete minime per x
for x in range(1, totale + 1):
for m in monete:
if m <= x:
meglio[x] = min(meglio[x], meglio[x - m] + 1)
return meglio[totale]
resto(6) # 2 (3 + 3), il goloso ne usa 3 (4 + 1 + 1)
Comprimere e riassumere: Huffman e gli hash
Due algoritmi che usi cento volte al giorno: uno rimpicciolisce i file, l'altro ne fa un'impronta digitale.
🗜️ Huffman
In italiano la "e" compare tantissimo, la "q" quasi mai. Allora perché usare lo stesso numero di bit per tutte? Huffman, nel 1952, da studente, dà codici corti alle lettere frequenti e lunghi alle rare. È lo stesso trucco del codice Morse, dove la "e" è un punto solo. Sta dentro zip, gzip, PNG e JPEG, insieme ad altri trucchi.
🧾 Hash
Un algoritmo che da qualunque file, anche enorme, tira fuori un'impronta corta e sempre uguale per lo stesso contenuto. Cambi una virgola e l'impronta cambia tutta. Serve per controllare che un download non sia rovinato, per le password, per le tabelle hash e per le firme digitali: c'è la guida Crittografia.
Problemi impossibili: P, NP e il commesso viaggiatore
Ci sono problemi facili da controllare e, per quanto ne sappiamo, difficilissimi da risolvere. Su questa differenza c'è un premio da un milione di dollari.
Un rappresentante deve passare da 20 città e tornare a casa facendo meno strada possibile. Provare tutti i giri? Sono più di sessanta milioni di miliardi. Con 70 città i giri sono più degli atomi dell'universo osservabile. Se però qualcuno ti dà un giro e dice "è sotto i 1.000 km", controllarlo è facilissimo: basta sommare.
| Classe | Vuol dire | Esempi |
|---|---|---|
| P | Si risolve in un tempo ragionevole | Ordinare, la strada più corta, cercare |
| NP | Una soluzione si controlla in un tempo ragionevole | Il sudoku, il commesso viaggiatore, gli orari di una scuola |
| P = NP? | Tutto ciò che si controlla in fretta si può anche risolvere in fretta? | Nessuno lo sa. È uno dei sette Problemi del Millennio del Clay Institute |
Quasi tutti pensano che la risposta sia no. Ed è una fortuna: la crittografia si regge proprio su problemi facili da controllare e difficili da risolvere. Nella pratica, per i problemi difficili si usano euristiche: algoritmi che non garantiscono la soluzione perfetta, ma ne trovano una ottima in fretta. È così che si organizzano i giri dei corrieri.
Gli algoritmi intorno a te
Quando qualcuno dice "l'algoritmo", di solito intende uno di questi.
| Dove | Cosa fa l'algoritmo |
|---|---|
| Il feed dei social | Ordina i post per quanto pensa che ti terranno incollato. Non è un ordinamento come il quicksort: è un punteggio calcolato da un modello addestrato sul comportamento di miliardi di persone |
| Il navigatore | Dijkstra, A* e parenti, con il traffico in tempo reale come costo delle strade |
| I motori di ricerca | Indici invertiti per trovare le pagine in millisecondi, poi centinaia di segnali per ordinarle. PageRank è stato solo l'inizio |
| Zip, foto, video | Compressione: Huffman e trucchi simili, più quelli che buttano via ciò che l'occhio non nota |
| Le IA come ChatGPT o Claude | Una rete neurale che sceglie la parola successiva più probabile, una alla volta. Algoritmi di addestramento enormi, ma nessuna "regola" scritta a mano: c'è la guida Come Funziona un LLM |
Glossario
Le parole della guida in una riga.
| Parola | Vuol dire |
|---|---|
| Algoritmo | Ricetta precisa che finisce |
| O grande | Come cresce il lavoro quando crescono i dati |
| Ricerca binaria | Cercare a metà, su dati ordinati |
| Dividi e conquista | Spezzare il problema in problemi più piccoli dello stesso tipo |
| Ricorsione | Una funzione che chiama se stessa su un pezzo più piccolo |
| Tabella hash | Trovare un valore dalla chiave in un colpo solo |
| Grafo | Punti uniti da collegamenti, con un costo |
| Goloso | Scegliere il meglio di adesso, senza ripensamenti |
| Programmazione dinamica | Risolvere i pezzi piccoli e ricordarsi le risposte |
| Euristica | Una scorciatoia che dà una buona risposta, non per forza la migliore |
| P e NP | Facile da risolvere, e facile da controllare |
sorted()."