I computer sono programmabili

Come abbiamo visto i computer sono dispositivi digitali che eseguono automaticamente operazioni complesse, come mostrare pagine web interattive, eseguire app sullo smartphone, consentire la visualizzazione del registro scolastico, eseguire videogiochi, ecc.

Tuttavia non tutti i dispositivi che svolgono operazioni complesse sono necessariamente dei computer. Una lavatrice odierna ad esempio, è sicuramente un dispositivo complesso, perché è in grado di capire quanto sono sporchi i vestiti quanto pesano, quanto l’acqua è calcarea, ecc. e comportarsi di conseguenza adeguando tempi e cicli di lavaggio. Ma la lavatrice non è un computer.

Le lavatrici smart eseguono operazioni complesse, anzi dei veri e propri programmi per computer. Ma le lavatrici ricevono la loro programmazione in fabbrica, e l’utente non può fare altro che selezionare il programma scelto e già preimpostato.

Un computer invece è un dispositivo in grado di essere programmato, ovvero può eseguire una sequenza arbitraria di istruzioni decisa dall’utente (da un utente sufficientemente esperto, ovvero un programmatore) per svolgere un compito specifico, deciso su un qualsiasi problema arbitrario. In realtà non proprio qualsiasi problema, un computer ha di norma un numero limitato di periferiche, come schermo mouse e tastiera, quindi è chiaro che non possiamo chiedergli di lavare i vestiti, perlomeno non con un normale personal computer.

Ma se venisse progettata una lavatrice programmabile in modo arbitrario dall’utente, decidendo ad esempio come gestire le informazioni di input (acqua, sporco, peso dei vestiti, ecc.) e come procedere, e per quanto tempo e con che risorse (acqua, sapone, ecc.), allora anche la lavatrice sarebbe un vero e proprio computer, anche se dedicato ad un insieme limitato di scopi (cioè lavare i vestiti).

I computer sono progettati in genere per elaborare grandi quantità di dati, per svolgere lunghe operazioni anche ripetitive senza fare errori, tramite programmi che possono essere progettati e realizzati su un computer e poi eseguiti in modo identico sullo stesso computer o su computer differenti. Sa svolgere calcoli in ambito scientifico o ingegneristico, operazioni di natura economica e finanziaria, come anche essere in grado di elaborare immagini e video, realizzare mondi virtuali (come nei videogiochi), rappresentare e memorizzare dati e comunicare con altri computer.

Il computer, di per sè, è una macchina stupida che esegue singole microistruzioni di cui non comprende il significato. I programmi per i computer sono in realtà una sequenza di queste istruzioni: è dalla loro combinazione in modo efficace che è possibile produrre operazioni anche molto complesse e che sembrano “intelligenti”.

Questa operazione viene chiamata “programmazione” ed è il frutto di una progettazione che richiede diverse fasi e dove è richiesta una capacità di astrazione e di ragionamento.

Pensiero computazionale

La programmazione richiede di ragionare su problemi, anche complessi, e scomporli in problemi più semplici e generali, per individuare poi una procedura che li possa risolvere in modo automatico, usando istruzioni basilari, che singolarmente fanno una cosa alla volta, ma che nel loro insieme producono operazioni complesse.

Il processo di ragionamento che consiste nell’affrontare un problema e produrre un programma si chiama pensiero computazionale, che prevede quattro fasi:

1. Analisi del problema: in questa fase si comprendono le caratteristiche generali del problema, eliminando quelle specifiche di casi singoli.
2. Modellizzazione: si costruisce un modello di riferimento che definisce i dati e gli obiettivi da risolvere, con eventuale scomposizione in problemi e modelli più piccoli.
3. Individuazione dell’algoritmo di risoluzione o nei problemi più complessi, scomposizione dell’algoritmo in sotto algoritmi.
4. Codifica, trasformazione degli algoritmi in istruzioni codificate per l’elaboratore.

Il pensiero computazionale (esclusa la fase 4) è qualcosa che possiamo applicare a molti ambiti scientifici e tecnici, ed anche nella vita quotidiana: possiamo usarlo per cucinare, per creare una struttura in Lego, per scrivere un tema, per risolvere problemi di matematica o fisica, ecc.

Il cuore di questa procedura consiste proprio nella definizione di algoritmi, ovvero procedure composte da un insieme di passi, che siano eseguibili in modo automatico sui dati definiti dal modello. La codifica (coding) consiste nella trasformazione di questi passi in un programma per computer, scritto di norma in un linguaggio di programmazione che utilizza tipologie di dati comprensibili dal computer.

Algoritmo

Un algoritmo è una procedura che risolve un problema tramite passi elementari, che possono anche essere condizionali (eseguiti a certe condizioni) o ripetuti.

L’algoritmo non viene creato direttamente a partire da un problema che bisogna risolvere. Il problema deve prima essere analizzato e tradotto in un “modello concettuale” che rappresenta tutti i problemi di quel tipo, e che cerca di generalizzarlo il più possibile.

Ad esempio pensiamo al semaforo. Il problema che vogliamo risolvere è attraversarlo in sicurezza. Se osserviamo il semaforo, questo ogni tot secondi, cambia colore, da verde a giallo, da giallo a rosso, e poi di nuovo verde. La regola dice di passare col verde, non cominciare l’attraversamento col giallo, e non passare col rosso. Quello che abbiamo appena esposto è un modello concettuale, che non vale solo per uno specifico semaforo, ma per tutti.

Da questo modello è possibile elaborare un algoritmo:

1. Osserviamo il semaforo.
2. Se è rosso torniamo al punto 1.
3. Se è verde attraversiamo la strada.

Come si è visto si è scomposto il problema in istruzioni elementari: osservazione, decisione ed azione. Non solo ma possiamo vedere che l’algoritmo consiste in istruzioni che elaborano dati. I dati sono proprio le osservazioni del semaforo, che può assumere infatti 3 stati possibili.

Possiamo anche affinare l’algoritmo.

1. Osserviamo il semaforo.
2. Se è rosso torniamo al punto 1.
3. Se è verde osserviamo se stanno passando auto, non tutti sono rispettosi del semaforo.
4. Se passano auto torniamo al punto 1.
5. Altrimenti attraversiamo.

Come si vede l’operazione diventa ancora più complessa, ma le istruzioni restano singolarmente semplici.

Pensiamo ora ad un algoritmo più complesso, il labirinto.

In questo caso possiamo formulare questo modello:

• il labirinto ha una entrata ed una uscita;
• è composto da corridoi e bivi;
• non c’è modo di sapere ad un bivio quale è quello giusto;
• è necessario esplorarlo per capire dove sta l’uscita.

Da qui discende questo algoritmo.

1. Avanziamo lungo il corridoio.
2. Se troviamo l’uscita usciamo.
3. Se troviamo un bivio giriamo a destra e torniamo al punto 1.
4. Se arriviamo ad un vicolo cieco, torniamo al precedente bivio e prendiamo l’uscita a sinistra, e torniamo al punto 1.

Anche qui abbiamo istruzioni semplici, camminare, osservare, scegliere dove svoltare.

In realtà è un algoritmo che potrebbe non funzionare, in molti labirinti potremmo camminare in circolo per ore. Per questa ragione lo modifichiamo:

1. Avanziamo lungo il corridoio.
2. Se troviamo l’uscita usciamo.
3. Se c’è un bivio giriamo a destra, ma prima marchiamo sul muro con un segno e torniamo al punto 1.
4. Se arriviamo ad un vicolo cieco, torniamo al precedente bivio e prendiamo la prima uscita non segnata e torniamo al punto 1.

Questo algoritmo, che potremo chiamare di “Pollicino” (in informatica viene chiamato “backtracking”) ci permette di trovare sempre una uscita.

Da questo algoritmo facciamo due importanti osservazioni:

• l’algoritmo non dipende da un particolare labirinto, perché abbiamo generalizzato il problema.
• l’algoritmo ricorda il passato, perché memorizziamo dove siamo stati.

Vediamo inoltre che qualunque algoritmo è composto sempre da un insieme di istruzioni elementari:

• osservazione o lettura dei dati, oppure anche scrittura e comunicazione all’esterno;
• elaborazione, come calcolo e scrittura dati;
• decisione;
• salto.

Queste 4 tipologie di istruzioni fondamentali sono tutte e sole le istruzioni necessarie. Vedremo poi che è possibile da queste far discendere altre istruzioni composte da queste.

Caratteristiche fondamentali degli algoritmi

Gli algoritmi, per essere definiti tali, godono di sei proprietà fondamentali:

• correttezza: deve risolvere il problema per cui è stato creato;
• finitezza: l’algoritmo può eseguire più volte la stessa istruzione, ma deve essere prevista una fine;
• non ambiguità: le istruzioni devono essere sempre chiare e non interpretabili;
• completezza: deve gestire tutte le situazioni possibili, anche quelle particolari
• generalità: deve valere per tutti i problemi dello stesso tipo;
• efficienza: deve risolvere il problema col numero minimo di passi e dati utilizzabili, forse la più complessa di tutte le proprietà.

Ad esempio l’algoritmo del labirinto deve essere valido per tutti i labirinti, deve gestire tutte le situazioni, deve essere non ambiguo sulle azioni da fare, deve portare fuori e non farci restare in eterno dentro il labirinto, nel numero di passi minore possibile.

La non ambiguità richiede di essere espliciti sulle azioni da fare. Ad esempio nella ricetta per cuocere la pasta poniamo di avere il seguente algoritmo:

1. metti dell’acqua a bollire.
2. metti un po’ di sale.
3. quando bolle butta la pasta.
4. dopo un po’ scola.

E’ ovviamente ambiguo, non si sa quanta acqua e quanta pasta mettere, non si sa quanto tempo aspettare.

La finitezza invece entra in gioco per tutti quegli algoritmi che svolgono operazioni cicliche (in realtà quasi tutti). Ipotizziamo di dover cercare un libro in una biblioteca, una sala con quattro pareti piene di scaffali.

1. Vai alla prima parete.
2. Vai al primo scaffale.
3. Cerca il libro.
4. Se lo trovi esci.
5. Se non lo trovi vai allo scaffale successivo.
6. Se è l’ultimo vai alla parete successiva.
7. Torna al punto 3.

Questo algoritmo non funziona bene, perché se il libro non si trova, continua a ripetere all’infinito la ricerca. Bisogna gestire e memorizzare anche gli scaffali e le pareti già visti, una volta finito l’algoritmo deve terminare.

L’efficienza ha a che fare col trovare una soluzione evitando istruzioni inutili. Ad esempio pensiamo ad un gioco dove ci chiedono di indovinare un numero tra 1 e 100. Ad ogni tentativo ci viene detto se il numero che diciamo è quello giusto, oppure se è più grande p più piccolo di quello da indovinare.

Un algoritmo potrebbe essere questo:

1. Diciamo un numero a caso
2. Se è indovinato, usciamo.
3. Se non lo è torniamo al punto 1.

Se siamo sfortunati potremmo anche dover ripetere 100 volte il passo 1.

Un algoritmo molto più efficiente è questo:

1. Definiamo min=1 e max=100
2. Definiamo a=min e b=max
3. Proponiamo il numero intermedio tra a e b, che chiamiamo c
4. Se è indovinato usciamo.
5. Se è più piccolo, definiamo b=c e torniamo al punto 3.
6. Se è più grande, definiamo a=c e torniamo al punto 3.

Ad esempio poniamo che il numero da indovinare sia 31.

1. min=1, max=100
2. a=1, b=100
3. Proponiamo c=50 (metà tra a e b)
4. c>31 quindi b=50
5. proponiamo c=25 (metà tra a e b)
6. c<31 quindi a=25
7. proponiamo c=37 (metà tra a e b)
8. c>31 quindi b=37
9. proponiamo c=31
10. Indovinato!

Ci sono bastati solo 4 tentativi. Ma anche nel caso peggiore ne bastano massimo 8 (provare per credere).

Come si vede ogni volta dimezziamo l’insieme dei valori possibili, ed è il sistema più veloce in assoluto. Questa tecnica si chiama “ricerca binaria” e richiede come visto un ragionamento maggiore sul modello concettuale.

L’efficienza è fondamentale perché le risorse di un computer sono limitate per quanto grandi, e spesso molti problemi computazionali richiedono algoritmi efficienti per essere efficaci.

Facciamo poi altre osservazioni importanti:

• in questo algoritmo abbiamo usato dei simboli per memorizzare dei valori, come si fa in matematica. In informatica questi simboli sono chiamati variabili.
• bisogna sempre fare attenzione a distinguere tra istruzioni di un algoritmo, e la loro esecuzione: le istruzioni effettivamente eseguite possono essere molte di più perché sono ripetute. Ma possono essere di meno quando una condizione non ci fa eseguire una istruzione.
• L’algoritmo resta generale: basta cambiare min e max per poterlo applicare anche a insiemi differenti.

Conclusioni

In questa lezione abbiamo visto che i computer sono programmabili, per risolvere problemi specifici ed arbitrari. La programmazione prevede quattro fasi: analisi del problema, definizione del modello concettuale, scrittura algoritmo e coding.

La metodologia che si applica alla programmazione si chiama pensiero computazionale e si applica anche in ambiti non informatici.

Fondamentale nel pensiero computazionale il concetto di algoritmo, una sequenza di istruzioni elementari che elaborano dati, prendono decisioni ed eventualmente si ripetono, fino a svolgere operazioni complesse.

Gli algoritmi devono soddisfare 6 proprietà: correttezza, finitezza, generalità, completezza, efficienza e non ambiguità.