Esercizi: Algoritmi e pensiero computazionale

Scrivi l'algoritmo, come elenco di passi numerati, per preparare un panino al formaggio, in modo che una persona che non ne ha mai fatto uno possa seguirlo senza dubbi. Rivedi il tuo elenco e verifica che non manchino passi che davi per scontati.

Questi passi dell'algoritmo «andare a scuola» sono in disordine: (a) entrare in classe, (b) alzarsi, (c) fare colazione, (d) uscire di casa, (e) vestirsi, (f) camminare fino a scuola. Mettili nell'ordine corretto e aggiungi all'algoritmo una decisione: che cosa fare se piove quando esci di casa.

La figura mostra, con blocchi incastrati, l'algoritmo di una lampada da lettura automatica che deve accendersi solo quando c'è poca luce, ma manca un blocco.

Indica quale blocco metteresti nello spazio vuoto e spiega con parole tue come funziona l'algoritmo completo, passo dopo passo.

Molti apparecchi di uso quotidiano seguono algoritmi. Scegline due da questo elenco —lavatrice, forno a microonde, semaforo— e descrivi per ciascuno quali dati riceve (ingresso), che cosa decide o ripete (elaborazione) e che cosa fa alla fine (uscita).

Scrivi l'algoritmo per preparare un bicchiere di latte al cacao in sei o otto passi, così precisi che potrebbe seguirli un robot: quantità, ordine dei passi e come verificare che il cacao si sia sciolto prima di finire.

Leggi questo algoritmo: (1) prendi il mazzo di carte, (2) finché ci sono carte in mano, dai una carta a ciascun giocatore partendo dalla tua sinistra, (3) quando non ci sono più carte, annuncia «distribuite». Spiega con una frase che cosa fa l'algoritmo e indica quale parte è la ripetizione e quando termina.

Nella ricetta «friggere un uovo» individua l'ingresso (gli ingredienti e gli utensili), l'elaborazione (i passi con il fuoco e la padella) e l'uscita (il risultato). Spiega perché ragionare così aiuta a scrivere algoritmi chiari.

Una ricetta dice «mescola la salsa finché si addensa». Spiega perché un algoritmo deve sempre terminare e che cosa potrebbe succedere se la salsa non si addensasse mai. Riscrivi quel passo in modo che il cuoco non resti a mescolare per sempre.

Scomponi il problema «organizzare la festa di fine anno» in quattro sottoproblemi più piccoli e scrivi due passi concreti per risolvere ciascuno. Spiega quale vantaggio ha dividere così un problema grande.

Per ordinare un mazzo di carte esistono diversi algoritmi, e alcuni sono più rapidi di altri. Spiega con un esempio della vita quotidiana che uno stesso problema può avere più algoritmi che lo risolvono e che cosa significa che uno sia «migliore» di un altro.

Una ricetta dice: «aggiungi sale e lascia cuocere un po' a fuoco medio». Spiega perché un computer non potrebbe seguire quell'istruzione e riscrivila come un passo di algoritmo preciso, indicando quantità, tempi e come verificare che il passo sia terminato.

Riconoscere gli schemi significa trovare la regola che si ripete. Scopri lo schema di queste tre sequenze ed esprimilo come regola chiara: (a) 5, 10, 15, 20, …, (b) 100, 90, 80, 70, …, (c) lunedì: 1 flessione, martedì: 2, mercoledì: 4, giovedì: 8, … Indica quale valore verrebbe dopo in ciascuna.

La mappa della metropolitana non disegna la città reale: elimina distanze, curve e strade, e tiene solo stazioni e collegamenti. Spiega che cos'è l'astrazione usando questo esempio e applicala poi alla pianta della tua scuola: quali tre cose includeresti e quali tre cose elimineresti.

Puoi farlo su carta e inviare una foto con la tua risposta.

Fai la traccia di esecuzione di questo algoritmo con $n = 7$: (1) parti dal valore $n$, (2) ripeti tre volte: aggiungi 2, (3) sottrai 5, (4) scrivi il risultato. Annota il valore dopo ogni passo, dai il risultato finale e spiega che cos'è una traccia di esecuzione e a che cosa serve farla a mano.

Questo algoritmo per «fare il bucato» ha un errore: (1) mettere tutti i vestiti in lavatrice, bianchi e colorati insieme, (2) aggiungere il detersivo, (3) scegliere il programma lungo ad acqua calda, (4) stendere. Trova due passi problematici, spiega che cosa può andare storto in ciascuno e riscrivi l'algoritmo corretto con un passo di selezione preliminare.

Scrivi l'algoritmo per contare quante persone entrano dalla porta dell'aula usando solo una variabile «contatore» che parte da 0: che cosa fai ogni volta che entra qualcuno, come sai quando smettere di contare e quale valore avrà il contatore alla fine.

Progetta l'algoritmo completo, con passi numerati che comprendano decisioni e ripetizioni, di un semaforo pedonale a pulsante: che cosa accade da quando qualcuno preme il pulsante fino a quando il semaforo torna allo stato iniziale, compresi i tempi di ciascuna luce.

Pensa a un programma che gioca a tris. Descrivi la strategia che seguirebbe a ogni turno: quali dati della griglia deve osservare, in quale ordine e quali regole useresti per decidere dove collocare il segno. Non serve scrivere codice: bastano le regole in linguaggio naturale.

L'algoritmo di una mensa distribuisce un panino a ciascun partecipante, ma non funziona quando i partecipanti sono più dei panini. Spiega che cos'è un «caso limite» in un algoritmo, proponi come dovrebbe comportarsi la distribuzione in quella situazione e riscrivi il passaggio problematico in modo che l'algoritmo non fallisca.

La figura mostra, con blocchi incastrati, lo scheletro di un gioco in cui si deve indovinare un numero segreto, ma all'interno del ciclo manca un pezzo affinché il gioco dia indizi al giocatore.

Descrivi quale blocco (o quali blocchi) inseriresti nello spazio vuoto affinché il gioco dica al giocatore se il suo numero è maggiore o minore di quello segreto, e spiega il funzionamento completo dell'algoritmo: che cosa si ripete, quando termina e che cosa succede se il giocatore indovina al primo tentativo.

Cerchi la parola «pipistrello» in un dizionario di 500 pagine. Confronta questi due algoritmi: aprire dalla prima pagina e avanzare una pagina alla volta, oppure aprire a metà e scartare via via la metà che non interessa. Spiega quale è più efficiente, perché funziona solo se le pagine sono ordinate e stima quante «aperture» richiede ciascun metodo.

Due persone preparano insieme la colazione per quattro ospiti: bisogna fare il caffè, tostare il pane, spremere il succo e apparecchiare la tavola. Distribuisci i compiti tra i due rispettando le dipendenze (non si può servire il caffè prima di averlo fatto) e spiega quali compiti possono essere svolti contemporaneamente e quali no, indicandone l'ordine.

Uno sportello bancomat ha solo banconote da $20\ \text{€}$ e il suo algoritmo distribuisce l'importo richiesto in banconote. Spiega che cosa succede quando qualcuno richiede $75\ \text{€}$, perché è un caso limite e riscrivi le regole del bancomat in modo che risponda sempre qualcosa di ragionevole.

Per la raccolta differenziata della classe si propongono due algoritmi: (a) ogni giorno, la persona responsabile separa tutti i rifiuti del giorno nei tre contenitori, e (b) ogni settimana, a turno, una coppia classifica quanto accumulato. Valuta entrambi con criteri di tempo totale, errori di classificazione e ripartizione dello sforzo, e scegline uno giustificando la scelta.