1. Corso C - Gli Algoritmi

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”.

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, ad esempio questa:

Dicesi “algoritmo”, un insieme finito di istruzioni, effettivamente eseguibili, atte alla risoluzione di un problema.

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:

 


corso-completo-c-introduzione-alla-programmazione-01

 

Le frecce indicano il flusso delle operazioni da eseguire.

Utilizzando questo sistema potremmo descrivere l’algoritmo per preparare un tè in questo modo:

 


corso-completo-c-introduzione-alla-programmazione-02

 

ottenendo sicuramente un risultato più chiaro rispetto ad una descrizione in linguaggio naturale.

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è:

 


corso-completo-c-introduzione-alla-programmazione-03

 

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à.

 

tratto da: http://www.devapp.it/wordpress/corso-completo-di-programmazione-in-c

video giochi
Flag Counter
motori di ricerca