Algoritmi

Question 1

Algoritmo

Answer 1

Un algoritmo è un procedimento effettivo che consente di risolvere un problema eseguendo, in un determinato ordine, una sequenza finita e completa di operazioni elementari (passi semplici, azioni, istruzioni), scelte tra un insieme (solitamente finito) di possibili azioni. Le operazioni in cui viene scomposto il processo risolutivo del problema devono essere comprensibili ed eseguibili dall’entità (uomo, computer, robot, . . .) cui l’algoritmo ` e destinato, entità che può anche non essere il computer.

Question 2

Algoritmo: input e output

Answer 2

Spesso un algoritmo ha degli input e degli output. L’input è l’insieme degli elementi in ingresso, mentre l’output è l’insieme degli elementi in uscita. Ad esempio, in una ricetta di cucina gli input sono gli ingredienti della ricetta e l’output il piatto finale realizzato.

Question 3

Proprietà di un algoritmo

Answer 3

• finito
• non ambiguo
• generale
• effettivo
• efficienza
  Un procedimento che viola una di queste proprietà non è ritenuto un algoritmo valido per il problema da risolvere.

Question 4

Algoritmo: finito

Answer 4

Finito: L’algoritmo

• deve essere composto da un numero finito (anche elevato) di azioni (passi semplici, istruzioni);
• richiedere una quantità finita di dati in input;
• l’esecuzione deve aver termine dopo un tempo finito.

Question 5

Algoritmo: non ambiguo

Answer 5

• Non ambiguo: Ogni azione (passo semplice, istruzione) deve essere interpretata in modo univoco dall’esecutore (computer, robot, . . .). Le operazioni che compongono un algoritmo possono essere anche complesse, purché sia stato previsto ogni aspetto che il problema può assumere durante la fa-se risolutiva e che ogni espressione sia interpretabile in maniera univoca senza ambiguità.

Question 6

Algoritmo: generale

Answer 6

Generale: L’algoritmo deve essere il più generale possibile in modo da applicarlo a tutta la classe di problemi simili. Inoltre, deve poter gesti-re correttamente qualsiasi insieme di dati di input per quel particolare problema.

Question 7

Algoritmo: effettivo

Answer 7

Effettivo: L’algoritmo deve avere un punto di partenza ed ogni operazione deve produrre un ben determinato risultato ogni volta che si presentano le stesse condizioni. Ovviamente un procedimento che sbaglia ` e inutile in quanto non calcola effettivamente la funzione per cui ` e stato ideato.

Question 8

Algoritmo: efficienza

Answer 8

Una ulteriore importante proprietà, ma non obbligatoria, ` e l’efficienza: l’algoritmo deve pervenire alla soluzione del problema usando la minor quantità possibile di risorse di calcolo (tempo di esecuzione, spazio in memoria, . . .).
L’efficienza di un algoritmo richiede di verificare
- se ` e corretto, ossia produce il risultato atteso;
- se ` e veloce (in termini di tempo impiegato per produrre il risultato);
- se ` e parsimonioso (in termini di risorse allocate per produrre il risultato).

Question 9

Progettazione algoritmo

Answer 9

Nel progettare un algoritmo è necessario analizzare il problema e decidere le azioni da compiere e la loro sequenza temporale. Le fasi della progettazione di un algoritmo possono essere così schematizzate:

• analisi del problema;
• definizione dei dati di ingresso;
• definizione dei risultati che si desiderano ottenere;
• individuazione dei possibili metodi risolutivi;
• determinazione della necessità e della disponibilità di risorse (di calcolo e di memorizzazione);
• generalizzazione del problema (definizione di una classe di problemi simili da risolvere);
• descrizione informale dell’algoritmo (o degli algoritmi) necessari a risolvere la procedura.

Question 10

Implementazione algoritmo

Answer 10

Una volta delineato un algoritmo, il passaggio successivo è l’implementazione, ovvero la traduzione in un programma. Un programma è un algoritmo scritto in un linguaggio comprensibile dal computer che consenta di svolgere un prefissato compito. La programmazione deve tenere in considerazione alcuni criteri di ottimizzazione, quali i tempi di calcolo e l’occupazione di memoria, e si concretizza nei seguenti passi:

• definizione dell’algoritmo, spesso in forma grafica tramite un diagramma a blocchi (diagramma di flusso, flow chart) oppure in pseudocodice (linguaggio di programmazione testuale, affine alla lingua parlata);
• stesura del programma nel linguaggio di programmazione prescelto (C, Java, R, Python, . . .);
• esecuzione del programma nel linguaggio di programmazione prescelto.

Question 11

Variabili

Answer 11

Ogni linguaggio di programmazione prevede l’uso di variabili, che possono considerarsi come contenitori di dati. Esse vengono usate nei programmi, per memorizzare i valori, che possono essere relativi ai dati in ingresso, ai risultati finali o a risultati intermedi dell’elaborazione. Una variabile deve avere: - un nome univoco; - un tipo che indica il genere di informazione che contiene; - un valore tra quelli possibili per il tipo, che pu` o ovviamente essere modificato nel corso delle elaborazioni; - una dimensione, in termini di celle di memoria occupate.

Question 12

Nome della variabile

Answer 12

Il nome di una variabile viene scelto dal programmatore e si utilizza il nome identificatore. Il nome dovrebbe essere significativo nel senso che dovrebbe riflettere il ruolo che la variabile assume all’interno del programma. Comunque, la scelta di un particolare nome non ha influenza sull’esecuzione del programma. Occorre osservare che le parole riservate non possono essere usate per i nomi delle variabili (ad esempio, TRUE o FALSE).

Question 13

Tipo di variabile

Answer 13

Il tipo determina i valori che la variabile pu` o assumere e determina lo spazio in memoria necessario: - numeri booleani {0,1}; - numeri interi (rappresentati tramite il complemento a due); - numeri reali (rappresentati in virgola fissa o in virgola mobile); - caratteri (rappresentati in ASCII o UNICODE) . Le variabili che servono a contenere informazioni testuali, sono dette di tipo stringa. Per memorizzare un testo occorre assegnarlo ad una variabile di tipo stringa ed inoltre delimitarlo con doppi apici (che non vengono memorizzati, ma servono a delimitare il testo da memorizzare).

Question 14

Variabile globale e locale

Answer 14

Una variabile globale può essere vista e utilizzata da ogni funzione del programma e in ogni istruzione del programma. Una variabile ` e detta locale quando ` e definita all’interno di una funzione o come parte di un ciclo, essa ` e visibile e può essere utilizzato solo all’interno della funzione in cui ` e stata dichiara

Question 15

Dichiarazione e inizializzazione della variabile

Answer 15

Tutte le variabili, prima di essere utilizzate, devono essere dichiarate, ossia deve essere stabilito il tipo della variabile ed il suo nome. La posizione in cui viene dichiarata la variabile determina la sua visibilità all’interno del pro-gramma e la capacità, da parte di alcune parti del programma, di utilizzarla. La variabile deve essere anche inizializzata, ossia le deve essere assegnato un valore, operazione che generalmente viene fatta contemporaneamente alla dichiarazione. Una variabile, dopo essere stata inizializzata, pu` o cambiare il suo valore nell’esecuzione del programma.

Question 16

Costanti

Answer 16

Il contenuto della locazione di memoria, che il sistema riserver a per la memorizzazione del dato dichiarato come costante, non potr a essere modificato durante il corso del programma: soltanto inizialmente sar a possibile memorizzare il valore deside-rato. Le costanti consentono di dichiarare un valore un’unica volta e di fare poi riferimento a questo valore nel corso del programma. Una costante deve avere: - un nome univoco; - un tipo che indica il genere di informazione che contiene; - un valore tra quelli possibili per il tipo, che non pu o essere modificato nel corso delle elaborazioni; - una dimensione, in termini di celle di memoria occupate.

Question 17

Costanti/variabili - contenitore

Answer 17

La dichiarazione di una costante/variabile indica al sistema di riservare un apposito spazio in memoria per memorizzare un dato, ossia una zona di memoria viene allocata (riservata) per la memorizzazione di una particolare informazione. Le costanti o le variabili possono essere quindi pensate come dei contenitori, ognuno con il proprio nome (deciso dal programmatore), in grado di contenere dei valori numerici, alfanumerici o logici, a seconda del tipo con cui sono state dichiarate.

Question 18

Espressione

Answer 18

Oltre alle variabili e alle costanti, all’interno di un programma un’informazione può essere anche organizzata in espressioni. Un’espressione` e una sequenza di operandi, operatori (di calcolo, logici e relazionali) e parentesi, dove gli operandi possono essere variabili o costanti. Il tipo dell’espressione complessiva dipende dai tipi degli operandi coinvolti nell’espressione.

Question 19

Diagrammi di flusso

Answer 19

I diagrammi di flusso (flow chart) costituiscono uno dei più diffusi formalismi grafici per rappresentare il flusso dell’esecuzione di un algoritmo. Un diagramma di flusso (o diagramma a blocchi) ` e un grafo orientato, ovvero ` e costituito da un insieme finito di blocchi (nodi) e da un insieme di frecce che collegano i blocchi (nodi) tra di loro. Ogni freccia rappresenta la scelta della prossima istruzione o blocco da eseguire.

Question 20

Blocchi dei diagrammi di flusso

Answer 20

I blocchi sono di quattro tipi:
- Ellisse: inizio e fine del diagramma di flusso;
- Parallelogramma: istruzioni di input o di output;
- Rettangolo: istruzioni di calcolo;
- Rombo: condizioni di controllo del flusso; al rombo sono associate delle biforcazioni rappresentate da due frecce uscenti etichettate rispettivamente con true/false (si/no).
Ogni blocco del diagramma, ad eccezione dei rombi e del nodo finale, ha un’unica freccia uscente che lo collega al blocco che lo segue nell’ordine di esecuzione. Il blocco finale non ha frecce uscenti, mentre il blocco iniziale non ha frecce entranti. I blocchi rombo hanno due frecce uscenti etichettate con true/false oppure si/no.

Question 21

Esecuzione di un diagramma di flusso

Answer 21

L’esecuzione di un diagramma di flusso parte con il nodo Start e sono eseguite le istruzioni che si incontrano durante il percorso, passando da un blocco a quello successivo seguendo le frecce. Arrivando ad un nodo rombo, il percorso prosegue percorrendo l’arco etichettato con True se la condizione contenuta nel rombo ` e vera, quello con False se la condizione ` e falsa.
Le istruzioni di ingresso (contrassegnate dalla parolaRead) consentono all’e-secutore di ricevere dei dati dall’esterno, mentre quelle di uscita (contrassegna-te dalla parola Write) indicano all’esecutore di fornire all’esterno dei risultati. L’esecuzione termina quando si arriva al blocco End.

Question 22

Lettura diagramma di flusso

Answer 22

La lettura di un diagramma di flusso procede in maniera sequenziale:
(a) si parte dal blocco iniziale; (b) si segue la freccia in uscita; (c) si giunge al blocco successivo e si effettua l’operazione descritta nel blocco; (d) si procede iterando (b) e (c) fino a raggiungere il blocco finale.

Question 23

Pseudocodice

Answer 23

Mentre ` e facile seguire l’esecuzione di un algoritmo tramite un diagramma di flusso, ` e spesso non facile comprendere qual ` e il suo scopo, soprattutto quando il flow chart ` e molto complesso. Si preferisce spesso scrivere l’algoritmo in pseudocodice (ossia utilizzare una pseudocodifica). Lo pseudocodice ` e un linguaggio informale che i programmatori adotta-no per sviluppare un algoritmo senza doversi preoccupare dei dettagli sintattici del linguaggio di programmazione. Lo pseudocodice ` e una forma di linguaggio naturale: ` e semplice e facilmente comprensibile, ma non ` e un vero linguaggio di programmazione. I programmi scritti in pseudocodice, infatti, non sono destinati ai computer, ma agli uomini, e sono uno strumento valido per esaminare un algoritmo prima di scriverlo in un vero linguaggio di programma-zione. In un programma in pseudocodice devono essere incluse soltanto le istruzioni eseguibili(ovvero le azioni effettivamente svolte quando il programmatore converte lo pseudocodice in un programma da eseguire utilizzando un vero linguaggio di programmazione). Tali azioni possono rappresentare istruzioni di input o di output, istruzioni di controllo oppure istruzioni di calcolo. Di conseguenza, nei programmi in pseudocodice non sono presenti dichiarazioni di variabili, poichè una dichiarazione non corrisponde a un’a-zione quando il programma viene eseguito; quindi, le dichiarazioni, non essendo istruzioni eseguibili, vanno tralasciate.

Question 24

Algoritmo di Euclide delle differenze successive

Answer 24

L’algoritmo per il calcolo del MCD di due interi positivi, nella sua versione pi u semplice delle differenze successive, si basa sulla seguente propriet a: “Se due numeri interi positivi m, n sono divisibili per un terzo numero x, allora anche la loro differenza ` e divisibile per x”. Consideriamo dunque due numeri m, n interi positivi e il loro massimo comune divisore d = M CD(m, n). Applicando la proprietà, poiché è divisore sia di m sia di n, divide anche la loro differenza p, che ` e minore di almeno uno dei due numeri m e n. Allora la ricerca di d = M CD(m, n) coincide con la ricerca, più semplice come calcoli, del MCD tra p e il minore dei due numeri m e n. Si ripete tale operazione finché non si ottiene una differenza nulla: il MCD(m, n) ` e l’ultima differenza non nulla determinata. Questo metodo, detto delle differenze successive, ha sicuramente termine in un numero finito di passaggi. ` E dunque un esempio interessante di algoritmo di calcolo e può essere facilmente implementato sul computer

Question 25

Algoritmo di Euclide delle divisioni successive

Answer 25

Dati due numeri interi positivi m e n, con m > n, denotiamo con q il quoziente e r il resto. Si ha quindi: m = n q +r .
Possiamo sfruttare la seguente proprietà: “Supposto m > n, se m e n hanno un divisore d comune, d ` e divisore anche di r, dove r ` e il resto della divisione intera di m per n”. Quindi, m e n hanno gli stessi divisori comuni di r e n e quindi anche lo stesso massimo comune divisore. Possiamo pertanto applicare questa proprietà più volte per determinare mediante divisioni successive il massimo comune divisore di due numeri. Se r = 0, significa che m ` e divisibile per n e quindi MCD(m, n) = n. Se r > 0 dalla relazione precedente otteniamo m− n q = r e applicando la proprietà, si può dedurre che il MCD(m, n) deve dividere anche r. Ci riconduciamo a calcolare il MCD(n, r), essendo n più piccolo di m. Operiamo la divisione tra n e r e analizziamo di nuovo il resto di questa seconda divisione: se ` e zero abbiamo terminato, se non ` e zero continuiamo con lo stesso procedimento. Il MCD(m, n) ` e l’ultimo resto non nullo nella sequenza di divisioni successive.