Informatica interattiva · Sezione 4

Gli algoritmi

Un computer non "capisce": esegue. Esegue una ricetta, passo dopo passo, senza saltarne nemmeno uno. Quella ricetta si chiama algoritmo, e la sua qualità cambia tutto.

Hai visto che dentro al computer ci sono solo numeri. Ma i numeri da soli non fanno niente: qualcuno deve dire cosa farci, e in che ordine. Un algoritmo è proprio questo — una sequenza di passi precisi che, eseguiti uno dietro l'altro, risolvono un problema. Due cose, qui, contano più di tutte: l'ordine dei passi e la loro efficienza. Tocchiamole con mano.

01Cos'è un algoritmo

Pensa a preparare un tè. I passi, da soli, non bastano: vanno messi in ordine. Se versi l'acqua prima di farla bollire, qualcosa non torna. Qui sotto i passi sono in disordine: sistemali con le frecce e guarda quando la ricetta inizia ad avere senso.

    Un algoritmo è una sequenza ordinata di passi. Gli stessi passi, in ordine diverso, danno un risultato diverso — o nessun risultato.

    02Ordinare

    Mettere delle cose in ordine è uno dei problemi più classici dell'informatica. Il computer non vede tutto in un colpo: può solo confrontare due elementi per volta e, se serve, scambiarli. Ripetendo questo gesto semplice, l'ordine emerge. Qui sotto vedi un bubble sort: a ogni passo confronta due barre vicine (in rosso) e mette la più bassa a sinistra. Le barre già sistemate diventano verdi.

    confronti: 0
    da ordinare in confronto al posto giusto

    Confronta e scambia, confronta e scambia. È lento a dirsi, ma il computer lo fa milioni di volte al secondo. Esistono poi algoritmi di ordinamento molto più furbi di questo.

    03Cercare

    Cercare un numero in una lista già ordinata può essere lentissimo o quasi istantaneo: dipende dall'algoritmo. Il modo ingenuo è guardare una cella alla volta da sinistra (scansione lineare): fino a tutte le celle, nel caso peggiore. Il modo furbo è la ricerca binaria: guarda quella in mezzo, e visto che la lista è ordinata butta via metà delle celle in un colpo solo. Scegli un numero e cercalo.

    Dividere a metà ogni volta è potentissimo: raddoppia le celle e serve un solo passo in più. È il motivo per cui cercare in un elenco enorme può restare immediato.

    04E con Leo?

    In Leo non devi scrivere il bubble sort a mano: ordinare e cercare sono gesti già pronti. Tu dici cosa vuoi, l'algoritmo giusto gira sotto. Prova questo nell'editor:

    # una lista di voti in disordine
    variabile voti = [7, 4, 9, 5, 8, 6]
    
    # chiedi a Leo di metterli in ordine
    voti.ordina()
    stampa(voti)
    
    # ora che è ordinata, cerca un valore
    stampa(voti.contiene(8))
    
    # oppure scorri i passi uno a uno
    per ogni voto in voti fai
        stampa(voto)
    fine
    ▶ Provalo in Leo Websi apre il playground con questo codice

    provalo e guarda cosa stampa: la lista passa dal disordine all'ordine, e la ricerca ti risponde sì o no. Lo stesso ordinare e cercare che hai mosso qui sopra — ora in codice vero.

    ★ Metti alla prova

    Informatica interattiva — un libro di Rosario Zappalà leoitalia.com