|
La guida è disponibile in versione zip per una consultazione non in linea.Download now. concetti fondamentali sugli algoritmi - tipi di istruzioni - le strutture di controllo - accumulatori e contatori Concetti fondamentali sugli Algoritmi Per molto tempo si pensò che il termine algoritmo derivasse da una storpiatura del termine logaritmo. Lopinione attualmente diffusa è invece che il termine derivi da al-Khuwarizmi, nome derivante a sua volta dal luogo di origine di un matematico arabo, autore di un libro di aritmetica e di uno di algebra: nel libro di aritmetica si parla della cosiddetta numerazione araba (quella attualmente usata) e si descrivono i procedimenti per lesecuzione delle operazioni dellaritmetica elementare. Questi procedimenti vennero in seguito chiamati algoritmi e il termine passò ad indicare genericamente qualunque procedimento di calcolo. Lalgoritmo esprime le azioni da svolgere su determinati oggetti al fine di produrre gli effetti attesi. Una azione che produce un determinato effetto è chiamata istruzione e gli oggetti su cui agiscono le istruzioni possono essere costanti (valori che restano sempre uguali nelle diverse esecuzioni dellalgoritmo) e variabili (contenitori di valori che variano ad ogni esecuzione dellalgoritmo). Si potrà dire brevemente che un algoritmo è una elaborazione di dati: i dati, cioè linsieme delle informazioni che devono essere elaborate, sono manipolati, secondo le modalità descritte dalle istruzioni, per produrre altri dati. Ciò porta lalgoritmo ad essere una funzione di trasformazione dei dati di un insieme A (dati di input) in dati di un insieme B (dati di output). In questi appunti, dato che ci si pone il fine di una introduzione alla programmazione, più che una definizione rigorosa di algoritmo se ne fornirà una definizione intuitiva. In questo senso si può definire lalgoritmo come ".. un insieme di istruzioni che definiscono una sequenza di operazioni mediante le quali si risolvono tutti i problemi di una determinata classe". Per chiarire meglio il concetto di algoritmo è bene fare riferimento ad alcune proprietà che un insieme di istruzioni deve possedere affinché possa chiamarsi algoritmo:
Per quanto osservato nellultima proprietà espressa, gli algoritmi operano principalmente su variabili che conterranno i dati sui quali si vuole svolgere una determinata elaborazione. I valori da elaborare devono essere assegnati alle variabili prima di effettuare lelaborazione. Si pensi infatti ad una variabile come ad un contenitore. Le istruzioni operano sui valori contenuti: se questi non ci sono non ci si può attendere alcuna elaborazione. Ogni variabile è identificata da un nome che permette di distinguerla dalle altre.
Esaminiamo adesso due versioni di un algoritmo per il calcolo dellarea di un rettangolo (i nomi delle variabili sono scritti in maiuscolo):
Nellalgoritmo A si assegnano alle variabili BASE ed ALTEZZA dei valori costanti, lalgoritmo calcola larea di un rettangolo particolare e se si vuole applicare lalgoritmo ad un diverso rettangolo è necessario modificare le due istruzioni di assegnamento a BASE e ALTEZZA: lalgoritmo ha perso la sua caratteristica di generalità. Questo esempio non deve portare a concludere che non ha senso parlare di costanti in un algoritmo perché, per esempio, se si fosse trattato di un triangolo il calcolo dellarea avrebbe assunto laspetto: Assegna a AREA valore BASE*ALTEZZA/2. La costante 2 prescinde dai valori diversi che possono essere assegnati a BASE e ALTEZZA, essendo parte della formula del calcolo dellarea di un triangolo qualsiasi. Nellalgoritmo B i valori da assegnare a BASE e ALTEZZA provengono da una unità di input. Lalgoritmo ad ogni esecuzione si fermerà in attesa di tali valori e il calcolo verrà eseguito su tali valori: lelaborazione è sempre la stessa (larea di un rettangolo si calcola sempre allo stesso modo) ma i dati saranno di volta in volta diversi (i rettangoli hanno dimensioni diverse). Gli algoritmi, a causa della loro generalità, lavorano utilizzando variabili. Non si conoscono, al momento della stesura dellalgoritmo stesso, i valori che possono assumere le variabili. Ciò se permette di scrivere algoritmi generali può comportare problemi per alcune istruzioni: si pensi al problema apparentemente banale del calcolo del quoziente di due numeri: Ricevi DIVIDENDO Ricevi DIVISORE Assegna a QUOZIENTE valore DIVIDENDO/DIVISORE Comunica QUOZIENTE Il quoziente può essere calcolato se DIVISORE contiene un valore diverso da 0, evento questo non noto in questo momento dipendendo tale valore dal numero proveniente da input. Inoltre è chiaro che, in questa eventualità, sarebbe priva di senso anche listruzione di output del valore di QUOZIENTE non essendoci nella variabile alcun valore. È necessario introdurre, oltre alle istruzioni, degli strumenti che permettano di controllare lesecuzione dellalgoritmo: le strutture di controllo. La programmazione strutturata (disciplina nata alla fine degli anni 60 per stabilire le regole per la scrittura di buoni algoritmi) impone luso di tre sole regole di composizione degli algoritmi: la sequenza È lunica struttura di composizione che si è utilizzata finora. In poche parole questa struttura permette di specificare lordine con cui le istruzioni si susseguono: ogni istruzione produce un risultato perché inserita in un contesto che è quello determinato dalle istruzioni che la precedono. Nellesempio di prima il calcolo di QUOZIENTE, per poter contenere il valore atteso, deve essere eseguito dopo gli input. la selezione Questa struttura permette di scegliere tra due alternative la sequenza di esecuzione. È la struttura che ci permette, per esempio, di risolvere in modo completo il problema del calcolo del quoziente fra due numeri: Ricevi DIVIDENDO Ricevi DIVISORE Se DIVISORE ¹ 0 Assegna a QUOZIENTE valore DIVIDENDO/DIVISORE Comunica QUOZIENTE Altrimenti Comunica Operazione senza senso Fine-se La condizione espressa nella struttura Se permette di scegliere, in relazione al valore di verità o falsità, quale elaborazione svolgere. La sequenza contenuta nella parte Altrimenti potrebbe mancare se si volesse soltanto un risultato laddove possibile: in tale caso se la condizione DIVISORE ¹ 0 risultasse non verificata, non si effettuerebbe alcuna elaborazione. literazione La struttura iterativa permette di ripetere più volte la stessa sequenza di istruzioni finché non si verifica una determinata condizione. Si voglia, a titolo di esempio, scrivere un algoritmo che calcoli e visualizzi i quadrati di una serie di numeri positivi. Si tratta in altri termini di effettuare la stessa elaborazione (calcolo e visualizzazione del quadrato di un numero) effettuata su numeri diversi (quelli che arriveranno dallinput): Ricevi NUMERO Mentre NUMERO > 0 Assegna a QUADRATO valore NUMERO*NUMERO Comunica QUADRATO Ricevi NUMERO Fine-mentre Dentro la struttura iterativa (la parte compresa fra le parole Mentre e Fine-mentre) sono specificate le istruzioni per il calcolo del quadrato di un numero: literazione permette di ripetere tale calcolo per tutti i numeri che verranno acquisiti tramite listruzione di input inserita nelliterazione stessa. La condizione NUMERO>0 viene chiamata condizione di controllo del ciclo e specifica quando deve terminare lelaborazione (il valore introdotto da input è non positivo): si ricorda che lalgoritmo deve essere finito e non si può iterare allinfinito. Il primo input fuori ciclo ha lo scopo di permettere limpostazione della condizione di controllo sul ciclo stesso e stabilire, quindi, quando terminare le iterazioni. In generale si può dire che la struttura di una elaborazione ciclica, controllata dal verificarsi di una condizione, assume il seguente aspetto: Considera primo elemento Mentre elementi non finiti Elabora elemento Considera prossimo elemento Fine mentre Le strutture di controllo devono essere pensate come schemi di composizione: una sequenza può contenere una iterazione che, a sua volta, contiene una selezione ecc.. Rappresentano in pratica i mattoncini elementari di una scatola di montaggio le cui diverse combinazioni permettono la costruzione di architetture di varia complessità. Lelaborazione ciclica è spesso utilizzata per laggiornamento di totalizzatori o contatori. Per chiarire meglio il concetto di totalizzatore, si pensi alle azioni eseguite dal cassiere di un supermercato quando si presenta un cliente con il proprio carrello pieno di merce. Il cassiere effettua una elaborazione ciclica sulla merce acquistata: ogni oggetto viene esaminato per acquisirne il prezzo. Lo scopo della elaborazione è quello di cumulare i prezzi dei prodotti acquistati per stabilire il totale che il cliente dovrà corrispondere. Dal punto di vista informatico si tratta di utilizzare una variabile (nellesempio potrebbe essere rappresentata dal totalizzatore di cassa) che viene aggiornata per ogni prezzo acquisito: ogni nuovo prezzo acquisito non deve sostituire il precedente ma aggiungersi ai prezzi già acquisiti precedentemente. Tale variabile:
La variabile di cui si parla nellesempio è quella che, nel linguaggio della programmazione, viene definita un totalizzatore o accumulatore: cioè una variabile nella quale ogni nuovo valore non sostituisce ma si accumula a quelli già presenti in precedenza. Se la variabile si aggiorna sempre di una quantità costante (per esempio viene sempre aggiunta lunità) viene chiamata contatore. In generale si può dire che luso di un totalizzatore prevede i seguenti passi: Inizializzazione totalizzatore Inizio ciclo aggiornamento totalizzatore
Aggiornamento totalizzatore Fine ciclo Uso del totalizzatore Linizializzazione serve sia a dare senso allistruzione di aggiornamento (cosa significherebbe la frase: aggiorna il valore esistente con il nuovo valore se non ci fosse un valore esistente ?), sia a fare in modo che laccumulatore stesso contenga un valore coerente con lelaborazione da svolgere (nellesempio di prima il nuovo cliente non può pagare prodotti acquistati dal cliente precedente: il totalizzatore deve essere azzerato, prima di cominciare lelaborazione, affinché contenga un valore che rispecchi esattamente tutto ciò che è stato acquistato dal cliente esaminato). Laggiornamento viene effettuato allinterno di un ciclo. Se infatti si riflette sulla definizione stessa di totalizzatore, è facile prendere atto che avrebbe poco significato fuori da un ciclo: come si può cumulare valori se non si hanno una serie di valori ? Quando i valori da esaminare terminano, il totalizzatore conterrà il valore cercato. Nellesempio di prima tutto ciò si tradurrebbe: finito lesame dei prodotti acquistati, si potrà presentare al cliente il totale da corrispondere. Si voglia, a titolo di esempio di utilizzo di un accumulatore, risolvere il seguente problema: data una sequenza di numeri positivi, se ne vuole calcolare la somma. Inizializza SOMMA con valore 0 Ricevi NUMERO Mentre NUMERO > 0 Aggiorna SOMMA sommando NUMERO Ricevi NUMERO Fine-mentre Comunica SOMMA Il totalizzatore SOMMA è inizializzato, prima del ciclo, al valore nullo poiché deve rispecchiare la somma dei numeri introdotti da input e, quindi, non essendo ancora stata effettuata alcuna elaborazione su alcun numero tale situazione viene espressa assegnando il valore neutro della somma. Loutput di SOMMA alla fine del ciclo indica il fatto che si può utilizzare (in questo caso per la conoscenza del valore contenuto) il totalizzatore quando il suo contenuto è coerente con il motivo della sua esistenza: SOMMA deve accumulare tutti i valori e ciò avverrà quando tutti i numeri da considerare saranno stati elaborati, cioè in uscita dal ciclo.
|
|