Alla base della programmazione vi è il concetto di algoritmo.
Possiamo provare a spiegare in modo non rigoroso cosa sia un algoritmo: è un insieme di istruzioni per fare qualcosa. Se per strada vi chiedono delle informazioni per raggiungere la spiaggia, probabilmente voi fornirete un algoritmo per raggiungerla, qualcosa come: “Vai dritto, gira a sinistra, poi se la strada è bloccata vai dritto, altrimenti gira a sinistra e cammina fino a quando vedrai il Duomo”. In questo testo ho messo in corsivo alcuni termini il cui significato è molto importante nel mondo della programmazione, li rivedremo spesso nelle prossime lezioni.
Come abbiamo detto l’informatica è una scienza e non una materia approssimativa, non possiamo quindi accettare definizioni approssimative di algoritmo, ce ne serve una formale. Esistono diverse definizioni formali della parola algoritmo, quella che piaceva tanto al mio professore universitario è questa:
Dicesi “algoritmo”, un insieme finito di istruzioni, effettivamente eseguibili, atte alla risoluzione di un problema.
A me piace inoltre ricordare che algoritmo ha la stessa radice ed etimologica di algebra, una parola che a sua volta deriva dal nome del grande matematico arabo Musa al-Khwarizmi (link) e che vuol dire, in qualche modo, spezzare, dividere in parti più piccole. Un algoritmo è quindi un sistema per spezzare un problema in parti più piccole.
Notiamo che nella definizione non c’è nulla di esplicitamente legato al mondo della programmazione, infatti il concetto di algoritmo è molto più generico.
Descrivere un algoritmo: i diagrammi di flusso
I diagrammi di flusso o a diagrammi a blocchi sono un metodo grafico per rappresentare un algoritmo. Esistono anche altri metodi per descrivere un algoritmo, come lo pseudocodice o il linguaggio naturale, ma i diagrammi di flusso si prestano molto bene per via della loro chiarezza. In alcuni casi, infatti, è facile riscontrare alcuni problemi logici di un algoritmo semplicemente guardandone il diagramma di flusso.
I blocchi che costituiscono un diagramma di flusso sono:
Le frecce indicano il flusso delle operazioni da eseguire.
Utilizzando questo sistema potremmo descrivere l’algoritmo per preparare un tè in questo modo:
ottenendo sicuramente un risultato più chiaro rispetto ad una descrizione in linguaggio naturale.
A volte mi chiedo perché nei libri di cucina non utilizzino i diagrammi di flusso! si eviterebbero frasi come “porre nella casseruola nella quale avevamo tagliato le verdure che erano state sbucciate…”
Correttezza di un algoritmo
Se è facile descrivere un algoritmo, ben più grosso è invece il problema di definirne la correttezza e verificare che rispetti tutte le proprietà che lo definiscono.
Sorvolando momentaneamente la correttezza, possiamo verificare fin da subito almeno che soddisfi le tre proprietà dettate dalla definizione?
Insieme finito di istruzioni
Un algoritmo deve avere un numero finito di istruzioni, non deve cioè continuare indefinitamente. Ci si può chiedere che senso abbia cercare di risolvere un problema con un algoritmo che non finisce mai, e in effetti in generale ha davvero poco senso tranne che in casi davvero particolari. Supponiamo infatti di voler ricercare un numero perfetto dispari (link), purtroppo non è noto se un tale numero esista realmente, quindi possiamo solo scorrere tutti i numeri fin quando non ne troviamo uno oppure…oppure proseguiremo ad infinito. Quindi quello che stiamo facendo, tecnicamente non è un algoritmo.
C’è un altro modo di uscire fuori dalla definizione di algoritmo ed è quello di generare un loop, una sequenza di istruzioni che si ripete (spesso per errore) indefinitamente come in questa versione modificata dell’algoritmo per fare il tè:
Il problema in questo esempio è che per errore ho scritto “metti l’acqua sul fornello” senza specificare che sia acceso, quindi se il fornello è spento continuerò ad aspettare indefinitamente. Questo quindi tecnicamente non è un algoritmo.
Istruzioni effettivamente eseguibili
Questa parte della definizione significa che le istruzioni devono essere eseguibili, se non lo sono non si tratta di un algoritmo. Per esempio in un algoritmo non può essere presente l’istruzione “prendi il più grande numero primo” in quanto non è eseguibile considerando che i numeri primi sono infiniti.
Alcune volte viene richiesto anche che le istruzioni siano “atomiche”, nel senso di indivisibili, elementari. (quando hanno scoperto le particelle subatomiche avrebbero dovuto cambiare nome all’atomo!). Questa caratteristica ha influenza solo sulla quantità di dettaglio che bisogna fornire all’esecutore dell’algoritmo affinchè lo possa eseguire. Ad esempio possiamo dare l’istruzione “versa l’acqua in una tazza” ad un uomo perchè per lui è un’istruzione atomica, non ci sarebbe bisogno di specificare ulteriori dettagli però se il destinatario delle nostre istruzioni fosse un robot meccanico allora bisognerebbe certamente fornire istruzioni come “afferra la tazza, sollevala, ruotala intorno al suo asse etc etc”.
Istruzioni atte alla risoluzione di un problema
L’algoritmo per fare il tè alla fine deve fare il tè, se non lo fa non è un algoritmo, o meglio, è un algoritmo probabilmente per non fare il tè. Questa proprietà non è facilmente verificabile, perchè l’algoritmo potrebbe sembrare che faccia il tè, mentre in realtà non lo fa. Questo problema a questo punto ricade sulla correttezza dell’algoritmo.
Correttezza di un algoritmo
Un algoritmo si dice corretto se fa quello per cui è stato progettato. In algoritmi piuttosto complessi non è facile seguire il filo del procedimento, quindi viene richiesta una verifica formale del loro funzionamento. Una vera e propria dimostrazione con tanto di teoremi, ipotesi e regole di derivazione. Certo nessuno vi chiederà di dimostrare l’algoritmo per preparare il tè, ma se scriverete un programma per cifrare le password in un database bancario, probabilmente qualcuno vi chiederà di dimostrare, formalmente, qual è la probabilità che qualcuno riesca a decifrarlo inserendo una chiave a caso.
Resta però il fatto che “Dimostrare la correttezza di un algoritmo è un problema indecidibile” (link) però questa frase oltre a giustificarvi con il vostro cliente che vi chiede come mai il vostro programma non funziona, ci informa anche che non esiste una procedura automatica per cui, dato un algoritmo si riesca a decidere se sia corretto o meno. Ci sono tantissimi casi particolari in cui è possibile dare una risposta, ma resta valido il principio generale di indecidibilità.
Prossimamente:
Nella prossima lezione faremo una panoramica sulle caratteristiche dei linguaggi di programmazione, vedremo perché ne esistono così tanti e quali sono le loro principali differenze. Inoltre daremo un breve introduzione al linguaggio C
Letture consigliate:
Il linguaggio C. Principi di programmazione e manuale di riferimento (Accademica)
Brian W. Kernighan – Dennis M. Ritchie
Editore: Pearson | Lingua: Italiano | Brossura: 313 pagine
Prezzo Listino: EUR 27,00
Prezzo Promozione: EUR 22,95 con Spedizione gratuita
C. Corso completo di programmazione
Paul J. Deitel – Harvey M. Deitel
Editore: Apogeo | Lingua: Italiano | Brossura: 640 pagine
Prezzo Listino: EUR 39,00
Prezzo Promozione: EUR 33,15 con Spedizione gratuita
22 Responses to “2. Introduzione alla programmazione: algoritmi e diagrammi di flusso”
12 Marzo 2011
Enrico6 semplicemente mitico! È talmente ben spiegato che mi viene da pensare ad algoritmi adessoXD
Grazie, aspetto con ansia le prossime illuminanti lezioni!
12 Marzo 2011
cristianoGrazie !!
12 Marzo 2011
ByterosA me hanno insegnato così:
Dicesi “algoritmo” un insieme finito di istruzioni CHE RISOLVONO IN TEMPO FINITO una classe di problemi.
Complimenti, un buon palazzo ha buone fondamenta.
12 Marzo 2011
SyleGrandi ….. Finalmente capisco qualcosa anch’io 😉 mitici.. ormai vi amo… 😉 ogni volta che entro clicco su un banner di google . ;)….. Non so perché ma sento che stavolta ci riuscirò… Alla prossima…
13 Marzo 2011
LinkatmeComplimenti, attendo con trepidazione gli altri capitoli!
14 Marzo 2011
Alexgrazie professo’! Ancora non ho potuto leggere nulla ma sto salvando questo corso perché promette bene. In settimana studio e riferirò!
14 Marzo 2011
ALBERTOGrazie mille!!
Neofita al 100% e mo’ vediamo se riesco a concludere qualcosa!!
Comunque complimenti per la chiarezza e semplicità del testo!
14 Marzo 2011
iCharrlesComplimenti. Continuate così.
15 Marzo 2011
GiacomoMolto interessante, mi sono letto tutto in un’ora e ho ancora molta fame!;)
15 Marzo 2011
LapoGrazie davvero perchè mi state facendo riappassionare alla programmazione che ho abbandonato anni fa pentendomene sempre! 🙂
complimenti.
17 Marzo 2011
gdevilGrazieeeee, grandissimo! 😀
18 Marzo 2011
VjoeComplimenti aspetto con ansia la prossima lezione!
18 Marzo 2011
Andreabene grazie.
aspetto con ansia le altre lezioni…..
18 Marzo 2011
Corso di programmazione in C - Panoramica sui linguaggi di programmazione | devAPP[…] esegue il suo compito ed infine giunge al termine, come nell’algoritmo per fare il tè della precedente lezione, mentre in un programma event-driven il programma si avvia e resta in un loop molto stretto (in […]
21 Marzo 2011
NelloVeramente complimenti di tutto cuore
21 Marzo 2011
Matteowow !! e davvero scritto in modo semplice e chiaro che persino io avendo 3 in matematica a scuola sono riuscito a capire cosè un algoritmo !!! incredibile sei un grande nello spiegrare !continua così che seguo le sue lezioni ! grazie !
21 Marzo 2011
maurizioTutti questi concetti sono spiegati benissimo!
(li capisco pure io che ho 15 anni)
21 Marzo 2011
Pasquale VassalluzzoSono un neofita, ma pare proprio che riesco a seguire questo corso che promette bene davvero!
Complimenti
27 Marzo 2011
WuberoneBel lavoro, ci sono ottime premesse… vediamo il resto adesso…
Complimenti!
15 Aprile 2011
Corso di programmazione in C - Costrutti decisionali | devAPP[…] l’algoritmo per preparare il tè visto nella seconda lezione? Quel rombo al centro è proprio il simbolo del costrutto decisionale, se è vera una data […]
17 Maggio 2011
AndreaCiao ragazzi,
semplicemente stupefacente, ho voglia di imparare, i miei professori sarebbero invidiosi di voi 🙂
26 Giugno 2012
DevtechSto iniziando a seguire questo corso. Lo trovo molto utile e soprattutto chi l’ha scritta sa spiegare veramente bene, al contrario di professori che credo di sapere insegnare e alla fine non hanno un metodo buono per fare imprimere queste nozioni agli studenti. Complimenti!