{"id":6083,"date":"2011-03-11T15:22:44","date_gmt":"2011-03-11T14:22:44","guid":{"rendered":"http:\/\/www.devapp.it\/wordpress\/?p=6083"},"modified":"2011-10-05T12:19:17","modified_gmt":"2011-10-05T10:19:17","slug":"2-introduzione-alla-programmazione-algoritmi-e-diagrammi-di-flusso","status":"publish","type":"post","link":"https:\/\/www.devapp.it\/wordpress\/2-introduzione-alla-programmazione-algoritmi-e-diagrammi-di-flusso\/","title":{"rendered":"2. Introduzione alla programmazione: algoritmi e diagrammi di flusso"},"content":{"rendered":"

\"corso-completo-c-introduzione-alla-programmazione-00\"<\/a> Alla base della programmazione vi \u00e8 il concetto di algoritmo<\/strong>.
\nPossiamo provare a spiegare in modo non rigoroso cosa sia un algoritmo: \u00e8 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<\/em> la strada \u00e8 bloccata vai dritto, altrimenti<\/em> gira a sinistra e cammina fino a quando<\/em> vedrai il Duomo”. In questo testo ho messo in corsivo alcuni termini il cui significato \u00e8 molto importante nel mondo della programmazione, li rivedremo spesso nelle prossime lezioni.<\/p>\n

Come abbiamo detto l’informatica \u00e8 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 \u00e8 questa:<\/p>\n

\nDicesi “algoritmo”, un insieme finito di istruzioni, effettivamente eseguibili, atte alla risoluzione di un problema.\n<\/p><\/blockquote>\n

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<\/a>) e che vuol dire, in qualche modo, spezzare, dividere in parti pi\u00f9 piccole. Un algoritmo \u00e8 quindi un sistema per spezzare un problema in parti pi\u00f9 piccole.<\/p>\n

Notiamo che nella definizione non c’\u00e8 nulla di esplicitamente legato al mondo della programmazione, infatti il concetto di algoritmo \u00e8 molto pi\u00f9 generico.<\/p>\n

Descrivere un algoritmo: i diagrammi di flusso<\/h4>\n

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<\/em> o il linguaggio naturale, ma i diagrammi di flusso si prestano molto bene per via della loro chiarezza. In alcuni casi, infatti, \u00e8 facile riscontrare alcuni problemi logici di un algoritmo semplicemente guardandone il diagramma di flusso.<\/p>\n

I blocchi che costituiscono un diagramma di flusso sono:<\/p>\n


\n\"corso-completo-c-introduzione-alla-programmazione-01\"<\/a>
\n<\/center><\/p>\n

Le frecce indicano il flusso delle operazioni da eseguire.<\/p>\n

Utilizzando questo sistema potremmo descrivere l’algoritmo per preparare un t\u00e8 in questo modo:<\/p>\n


\n\"corso-completo-c-introduzione-alla-programmazione-02\"<\/a>
\n<\/center><\/p>\n

ottenendo sicuramente un risultato pi\u00f9 chiaro rispetto ad una descrizione in linguaggio naturale.<\/p>\n

A volte mi chiedo perch\u00e9 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…”<\/p>\n

Correttezza di un algoritmo<\/h4>\n

Se \u00e8 facile descrivere un algoritmo, ben pi\u00f9 grosso \u00e8 invece il problema di definirne la correttezza e verificare che rispetti tutte le propriet\u00e0 che lo definiscono.<\/p>\n

Sorvolando momentaneamente la correttezza, possiamo verificare fin da subito almeno che soddisfi le tre propriet\u00e0 dettate dalla definizione?<\/p>\n

Insieme finito di istruzioni<\/strong><\/p>\n

Un algoritmo deve avere un numero finito di istruzioni, non deve cio\u00e8 continuare indefinitamente. Ci si pu\u00f2 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<\/a>), purtroppo non \u00e8 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 \u00e8 un algoritmo.<\/p>\n

C’\u00e8 un altro modo di uscire fuori dalla definizione di algoritmo ed \u00e8 quello di generare un loop<\/em>, una sequenza di istruzioni che si ripete (spesso per errore) indefinitamente come in questa versione modificata dell’algoritmo per fare il t\u00e8:<\/p>\n


\n\"corso-completo-c-introduzione-alla-programmazione-03\"<\/a>
\n<\/center><\/p>\n

Il problema in questo esempio \u00e8 che per errore ho scritto “metti l’acqua sul fornello” senza specificare che sia acceso, quindi se il fornello \u00e8 spento continuer\u00f2 ad aspettare indefinitamente. Questo quindi tecnicamente non \u00e8 un algoritmo.<\/p>\n

Istruzioni effettivamente eseguibili<\/h4>\n

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\u00f2 essere presente l’istruzione “prendi il pi\u00f9 grande numero primo” in quanto non \u00e8 eseguibile considerando che i numeri primi sono infiniti.<\/p>\n

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\u00e0 di dettaglio che bisogna fornire all’esecutore dell’algoritmo affinch\u00e8 lo possa eseguire. Ad esempio possiamo dare l’istruzione “versa l’acqua in una tazza” ad un uomo perch\u00e8 per lui \u00e8 un’istruzione atomica, non ci sarebbe bisogno di specificare ulteriori dettagli per\u00f2 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”.<\/p>\n

Istruzioni atte alla risoluzione di un problema<\/h4>\n

L’algoritmo per fare il t\u00e8 alla fine deve fare il t\u00e8, se non lo fa non \u00e8 un algoritmo, o meglio, \u00e8 un algoritmo probabilmente per non fare il t\u00e8. Questa propriet\u00e0 non \u00e8 facilmente verificabile, perch\u00e8 l’algoritmo potrebbe sembrare che faccia il t\u00e8, mentre in realt\u00e0 non lo fa. Questo problema a questo punto ricade sulla correttezza dell’algoritmo.<\/p>\n

Correttezza di un algoritmo<\/h4>\n

Un algoritmo si dice corretto se fa quello per cui \u00e8 stato progettato. In algoritmi piuttosto complessi non \u00e8 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\u00e0 di dimostrare l’algoritmo per preparare il t\u00e8, ma se scriverete un programma per cifrare le password in un database bancario, probabilmente qualcuno vi chieder\u00e0 di dimostrare, formalmente, qual \u00e8 la probabilit\u00e0 che qualcuno riesca a decifrarlo inserendo una chiave a caso.<\/p>\n

Resta per\u00f2 il fatto che “Dimostrare la correttezza di un algoritmo \u00e8 un problema indecidibile” (link<\/a>) per\u00f2 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 \u00e8 possibile dare una risposta, ma resta valido il principio generale di indecidibilit\u00e0.<\/p>\n

Prossimamente:<\/h4>\n

Nella prossima lezione faremo una panoramica sulle caratteristiche dei linguaggi di programmazione, vedremo perch\u00e9 ne esistono cos\u00ec tanti e quali sono le loro principali differenze. Inoltre daremo un breve introduzione al linguaggio C<\/p>\n

Letture consigliate:<\/h4>\n

\"C-Corso-Completo-di-Programmazione-kernighan-ritchie-devAPP\"<\/a> Il linguaggio C. Principi di programmazione e manuale di riferimento (Accademica) <\/strong><\/a>
\nBrian W. Kernighan – Dennis M. Ritchie<\/em>
\nEditore:<\/strong> Pearson | Lingua:<\/strong> Italiano | Brossura:<\/strong> 313 pagine
\nPrezzo Listino:<\/strong> EUR 27,00<\/del>
\nPrezzo Promozione:<\/strong> EUR 22,95 con Spedizione gratuita<\/p>\n

\"C-Corso-Completo-di-Programmazione-Deitel-Deitel-devAPP\"<\/a> C. Corso completo di programmazione<\/strong><\/a>
\nPaul J. Deitel – Harvey M. Deitel<\/em>
\nEditore:<\/strong> Apogeo | Lingua:<\/strong> Italiano | Brossura:<\/strong> 640 pagine
\nPrezzo Listino:<\/strong> EUR 39,00<\/del>
\nPrezzo Promozione:<\/strong> EUR 33,15 con Spedizione gratuita<\/p>\n


\n\"\"<\/a>
\n<\/center><\/p>\n","protected":false},"excerpt":{"rendered":"

Alla base della programmazione vi \u00e8 il concetto di algoritmo. Possiamo provare a spiegare in modo non…<\/p>\n","protected":false},"author":53,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[569],"tags":[612,593,613,241,594,611,592],"class_list":["post-6083","post","type-post","status-publish","format-standard","hentry","category-corso-completo-di-c","tag-algoritmo","tag-corso-completo-di-c-2","tag-diagrammi-di-flusso","tag-ignazio-calo","tag-iniziare-a-programmare-iphone","tag-introduzione-alla-programmazione","tag-programmare-in-c"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/6083","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/users\/53"}],"replies":[{"embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/comments?post=6083"}],"version-history":[{"count":23,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/6083\/revisions"}],"predecessor-version":[{"id":7806,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/posts\/6083\/revisions\/7806"}],"wp:attachment":[{"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/media?parent=6083"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/categories?post=6083"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.devapp.it\/wordpress\/wp-json\/wp\/v2\/tags?post=6083"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}