Svogliati
🧮

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."

↓
01 / 15

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.

💡 La ricetta della carbonara

"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.

02 / 15

Un po' di storia

Gli algoritmi sono più vecchi dei computer di un paio di millenni.

~300 a.C.

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.

IX secolo

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".

1843

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.

1936

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.

1956–61

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.

1998

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.

03 / 15

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ù.

Come cresce il lavoro
quanti dati (n)lavoron²: alla buona, esce dal graficon²: alla buona, esce dal graficon log n: merge, quickn log n: merge, quickn: leggere tutton: leggere tuttolog n: ricerca binarialog n: ricerca binaria
Si scriveSi leggeEsempioCon 1.000 elementiCon 1 milione
O(1)Costante: non dipende da quanti sonoPrendere il terzo elemento di una lista1 passo1 passo
O(log n)Logaritmica: quasi gratisCercare in un elenco ordinato~10 passi~20 passi
O(n)Lineare: tanti dati, tanto lavoroLeggerli tutti una volta1.0001 milione
O(n log n)Poco più che lineareGli ordinamenti buoni~10.000~20 milioni
O(n²)Quadratica: esplodeGli ordinamenti alla buona, due cicli uno dentro l'altro1 milione1.000 miliardi
🧠 La regola praticaUn ciclo dentro un altro ciclo, sugli stessi dati, è quasi sempre 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.
04 / 15

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.

Cercare il 72 fra 16 numeri: 4 giri
25812162338425661727781909599giro 1guardo il 42: troppo piccolo, tengo la destra25812162338425661727781909599giro 2guardo il 77: troppo grande, tengo la sinistra25812162338425661727781909599giro 3guardo il 61: troppo piccolo25812162338425661727781909599giro 4guardo il 72: trovato!
python · ricerca binaria
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.

05 / 15

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.

python · ordinamento per inserimento
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.

06 / 15

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.

🐍 Nella vita vera non li scriviPython usa Timsort, scritto da Tim Peters nel 2002: un ibrido fra merge sort e inserimento, bravissimo con i dati reali, che spesso sono già un po' in ordine. sorted(lista) e hai finito. Gli algoritmi si studiano per capire, non per riscriverli.
07 / 15

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).

▲ confronto⇅ scambio o scrittura✓ ordinato
Confronti 0 Scambi o scritture 0 Pronto

🔬 Cosa guardareCon le stesse barre, il bubble sort fa centinaia di confronti, merge e quick molti meno. Prova anche "Mescola" più volte: il quicksort cambia molto da un giro all'altro, il merge sort quasi mai. Per vedere il colpo di fortuna dell'inserimento, completa un ordinamento e poi rilancia l'inserimento sulle barre già ordinate.
08 / 15

Ricorsione: la funzione che chiama se stessa

Merge e quick sono ricorsivi: per ordinare una lista, ordinano due liste più piccole nello stesso modo.

💡 Le matrioske

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.

python · ricorsione: Euclide
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
📚 Stack overflow, quello veroOgni chiamata ricorsiva occupa un po' di memoria finché non torna. Senza caso base, o con troppi livelli, la memoria finisce e il programma si ferma con "stack overflow". Il famoso sito di domande si chiama così per questo.
09 / 15

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.

StrutturaCom'èVeloce perLenta per
Array / listaCaselle in fila, numeratePrendere la casella numero 500Inserire in mezzo: devi spostare tutte quelle dopo
Lista concatenataOgni elemento sa dov'è il prossimo, come una caccia al tesoroInserire e togliere in mezzoArrivare 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 soloTenere le cose in ordine
AlberoOgni nodo ha figli: i più piccoli a sinistra, i più grandi a destraCercare e inserire tenendo tutto in ordineSe si sbilancia diventa una lista
Coda e pilaLa fila alla posta, e la pila di piattiIl primo arrivato, o l'ultimo appoggiatoTutto 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.

10 / 15

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.

Una mappa come grafo: il percorso più corto
425183210CasaABCDMetaPercorso più corto: Casa → B → A → C → Meta = 2 + 1 + 5 + 3 = 11La strada che sembra diretta, Casa → A, costa già 4: passare da B è meglio

🧭 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.

11 / 15

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:

Quando il goloso sbaglia
Resto di 6, con monete da 1, 3 e 4Golosoprende sempre la più grande4113 moneteProgrammazione dinamicaprova tutte le strade, con memoria332 monete ✓

🍰 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.

python · resto con la programmazione dinamica
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)
12 / 15

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.

🎲 Comprimere il caso non si puòLa compressione funziona perché i dati veri sono ripetitivi: parole che tornano, pixel dello stesso colore. Un file già compresso, o dati casuali, non si rimpiccioliscono più: zippare uno zip non serve a niente.
13 / 15

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.

💡 Il commesso viaggiatore

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.

ClasseVuol direEsempi
PSi risolve in un tempo ragionevoleOrdinare, la strada più corta, cercare
NPUna soluzione si controlla in un tempo ragionevoleIl 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.

14 / 15

Gli algoritmi intorno a te

Quando qualcuno dice "l'algoritmo", di solito intende uno di questi.

DoveCosa fa l'algoritmo
Il feed dei socialOrdina 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 navigatoreDijkstra, A* e parenti, con il traffico in tempo reale come costo delle strade
I motori di ricercaIndici invertiti per trovare le pagine in millisecondi, poi centinaia di segnali per ordinarle. PageRank è stato solo l'inizio
Zip, foto, videoCompressione: Huffman e trucchi simili, più quelli che buttano via ciò che l'occhio non nota
Le IA come ChatGPT o ClaudeUna 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
⚖️ "L'ha deciso l'algoritmo"non è mai una spiegazione. Un algoritmo fa quello per cui è stato scritto o addestrato, con i dati che gli sono stati dati. Se un mutuo viene rifiutato o un curriculum scartato da un sistema automatico, qualcuno ha scelto quei criteri. Per le decisioni automatiche importanti, in Europa il GDPR dà il diritto di chiedere l'intervento di una persona.
15 / 15

Glossario

Le parole della guida in una riga.

ParolaVuol dire
AlgoritmoRicetta precisa che finisce
O grandeCome cresce il lavoro quando crescono i dati
Ricerca binariaCercare a metà, su dati ordinati
Dividi e conquistaSpezzare il problema in problemi più piccoli dello stesso tipo
RicorsioneUna funzione che chiama se stessa su un pezzo più piccolo
Tabella hashTrovare un valore dalla chiave in un colpo solo
GrafoPunti uniti da collegamenti, con un costo
GolosoScegliere il meglio di adesso, senza ripensamenti
Programmazione dinamicaRisolvere i pezzi piccoli e ricordarsi le risposte
EuristicaUna scorciatoia che dà una buona risposta, non per forza la migliore
P e NPFacile da risolvere, e facile da controllare
🧭 La risposta per il collega"Un algoritmo è una ricetta. Per lo stesso problema ce ne sono di veloci e di lenti, e la differenza si vede quando i dati crescono: due cicli annidati su un milione di righe non finiscono più. Ordina e cerca a metà, usa un set invece di una lista per controllare se una cosa c'è, e non riscrivere il quicksort: c'è già sorted()."