Dispensa II.1

(1)

Dispensa II.1 versione 1.0 mail: lamonica@associatesonline.it Pagina 1 di 8

ALGORITMI

La dispensa di seguito proposta si pone come tutorial per poter porre le basi per la realizzazione di algoritmi che poi potranno eventualmente essere sviluppati in moduli software con metodologia di programmazione strutturata .

Il concetto di algoritmo

Il calcolatore elettronico per risolvere un problema utilizza un algoritmo, cioè un insieme di azioni (o istruzioni) che, eseguite secondo un ordine prestabilito, permettono di trovare il risultato cercato sulla base dei dati in ingresso.

Il concetto di algoritmo è uno dei concetti di base dell'intera matematica: i più semplici ed antichi algoritmi sono le regole per eseguire le operazioni dell'aritmetica elementare, formulate dal matematico arabo medioevale Al-Khuwarizmi, da cui deriva appunto il nome di algoritmo.

Nel secolo scorso il concetto di algoritmo venne formalizzato per risolvere il problema matematico della "decisione" (Entscheidungsproblem) posto da David Hilbert nel 1928.

Successive modifiche avvennero a seguito della definizione delle funzioni ricorsive Gödel–

Herbrand–Kleene del 1930, 1934 e 1935 e della Macchina di Alan Turing del 1936–7 e 1939.

Nonostante questi tentativi, la definizione formale del concetto di algoritmo è tuttora una sfida aperta. Tuttavia, si può definire intuitivamente un algoritmo come una sequenza ordinata e finita di passi (operazioni o istruzioni) elementari che conduce ad un ben determinato risultato in un tempo finito.

(2)

Il diagramma di flusso (flow chart)

Il diagramma di flusso (in inglese detti anche flow chart) è un linguaggio di modellazione grafico per rappresentare il flusso di controllo di algoritmi, procedure, istruzioni operative (in senso lato).

Esso consente di descrivere in modo schematico:

• le operazioni da compiere, rappresentate mediante sagome convenzionali (come

rettangoli, rombi, esagoni, parallelogrammi, rettangoli smussati...) all'interno delle quali un'indicazione testuale descrive l'attività da svolgere

• la sequenza nella quale devono essere compiute, rappresentate con frecce di collegamento.

I diagrammi di flusso trovano la loro applicazione in vari ambiti, ma quello in cui storicamente si sono maggiormente affermati è stato quello informatico dove, solo in tempi più recenti, sono stati affiancati da altri strumenti metodologici quali lo pseudocodice e l'UML.

Blocchi elementari

Esistono varie notazioni per la rappresentazione con diagrammi di flusso. Tutte le notazioni sottendono a un meta-modello molto semplice, caratterizzato da una lettura sequenziale:

• si parte dal blocco iniziale

• si segue la freccia in uscita

• si giunge al blocco successivo e si effettua l'operazione descritta nel blocco

• si procede iterando i passi 2 e 3 fino a giungere al blocco finale.

(3)

Dispensa II.1 versione 1.0 mail: lamonica@associatesonline.it Pagina 3 di 8 Tra le operazioni si distingue tra:

• azione, che comportano una attività o un'elaborazione

• test, che indicano due o più direzioni in base a un fattore di decisione

• ingresso/uscita, che comportano l'immissione di informazioni dall'esterno oppure l'invio di

informazioni verso l'esterno.

La notazione più semplice e più frequentemente utilizzata prevede dunque 5 tipi di blocchi elementari:

blocco iniziale blocco finale

blocco di I/O blocco di Elaborazione

blocco di controllo

(4)

Dispensa II.1 versione 1.0 mail: lamonica@associatesonline.it Pagina 4 di 8 Struttura sequenza

Quando due o più azioni vengono eseguite l’una di seguito all’altra si parla di sequenza.

Struttura selezione

Quando avviene che dopo una azione può essere eseguita o una o un’altra azione si parla di selezione.

Tramite la struttura Selezione è possibile arrivati a un certo punto del programma, di scegliere che strada seguire in base alla verità o falsità di un’affermazione.

Successivamente il flusso di esecuzione dell’algoritmo prosegue per affrontare altri passi.

(5)

Dispensa II.1 versione 1.0 mail: lamonica@associatesonline.it Pagina 5 di 8 Struttura Iterazione

Quando avviene che un’azione o insieme di azioni venga ripetuto un certo numero di volte prestabilito oppure venga ripetuto ﬁnché non si veriﬁchi una certa condizione si parla di iterazione.

Individuamo in particolare

• la iterazione in cui è possibile che una azione venga ripetuta un numero di volte ma anche

mai eseguita ( da 0 ad n volte) in cui la azione di controllo avviene prima del blocco di azioni da ripetere

• la iterazione in cui è possibile che una azione venga ripetuta un numero di volte ma almeno una volta ( da 1 ad n volte) in cui la azione di controllo avviene dopo del blocco di azioni da ripetere.

(6)

(7)

Teorema di Böhm-Jacopini

Il teorema di Böhm-Jacopini, enunciato nel 1966 dagli informatici Corrado Böhm e Giuseppe Jacopini, afferma che qualunque algoritmo può essere implementato utilizzando tre sole strutture, la sequenza, la selezione ed il ciclo (iterazione).

(8)

Esecuzione di un algoritmo su un Computer

Algoritmo: Procedura di trasformazione di un insieme di dati iniziali in un insieme di risultati finali mediante una sequenza di istruzioni.

linguaggio di programmazione: Linguaggio (insieme di simboli e regole) per rappresentare le istruzioni di un algoritmo e la loro concatenazione.

Programma: Algoritmo scritto in un linguaggio di programmazione al fine di comunicare al calcolatore elettronico le azioni da eseguire.

Processo: Programma in esecuzione sul computer.