Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.


 
Non ricordi la password?  ››  Iscriviti gratis
 

ALGORITMI - LE PROPRIETÀ DEGLI ALGORITMI

matematica



ALGORITMI


Un algoritmo è la descrizione della soluzione di un tipo (o classe) di problemi come sequenza di azioni elementari (pag. 72/89), in pratica la serie di passi fondamentali che servono per risolvere problemi (es. in matematica la formula risolutiva dell'equazione di 2° è un algoritmo). Per rendere la risoluzione valida per tutti i problemi che hanno le stesse caratteristiche, l'algoritmo non impiega direttamente i valori del problema, ma dei nomi simbolici che corrispondono a dei valori che possono variare durante l'esecuzione. Dal momento che il computer ha bisogno di istruzioni dall'esterno per ogni operazione che deve eseguire, quando forniamo il software alla macchina, forniamo in realtà tutta una serie di algoritmi elementari (tradotti in linguaggio di programmazione) che concorrono alla risoluzione dei problemi specifici e permettono il funzionamento del computer. Si chiama risolutore l'entità (uomo o macchina che si occupa di analizzare e definire le azioni da eseguire per giungere alla soluzione.


l'analisi del problema fatta dal risolutore per giungerne alla risoluzione attraverso l'algoritmo richiede i seguenti passi:


interpretare la traccia del problema e localizzare gli obbiettivi da raggiungere;



individuare i dati iniziali, i dati finali e un tipo di rappresentazione della realtà;

descrivere il procedimento risolutivo individuando le azioni che devono essere compiute, utilizzando il modello per elaborare i dati iniziali, sino a raggiungere i dati finali.


La risoluzione di un problema complesso richiede, inoltre, una precisa e completa conoscenza del quesito di partenza: deve essere assolutamente chiaro l'obbiettivo da raggiungere per poter fare un'analisi del problema e trovarne la 353g69d soluzione.


Il lavoro passa successivamente ad un esecutore che:


esegue in ordine le operazioni descritte dal risolutore, fino a pervenire ai risultati finali;

verifica che i risultati siano quelli previsti: se l'obiettivo non è stato raggiunto, il risolutore dovrà ripetere le tre fasi viste in precedenza e riproporre il suo lavoro all'esecutore.



LE PROPRIETÀ DEGLI ALGORITMI


Un algoritmo di risoluzione di un problema deve essere:


finito: il numero di istruzioni che lo compongono e il numero di volte che viene eseguita ogni istruzione deve essere finito;

eseguibile: la sua esecuzione da parte dell'esecutore deve essere possibile con i mezzi tecnici a sua disposizione;

deterministico: in ogni istante deve essere definita la sequenza di istruzioni che seguiranno quella in esecuzioni, in altre parole a parità di condizioni l'ordine di esecuzione delle istruzioni deve restare invariato;

non ambiguo: i comandi dati all'esecutore non devono dar alcun adito a interpretazioni diverse che dipendono dall'esecutore, solo scrivendo delle istruzioni chiare ed elementari è possibile raggiungere il risultato corretto;

generale: ogni esecutore può sfruttare lo stesso algoritmo per risolvere tutti i problemi della stessa classe.


Gli algoritmi possono essere rappresentati:

in diagrammi a blocchi;

in linguaggio di progetto o pseudocodifica (modo più moderno), metodo discorsivo basato sull'uso di un linguaggio molto sintetico dotato di un ristretto vocabolario di parole riservate (cioè non utilizzabili anche come identificatori di variabili) dette parole chiave (pag. 79).


MODELLI DI ALGORITMI


Si chiama modello una qualsiasi rappresentazione del problema che mette in evidenza solo le caratteristiche fondamentali per il raggiungimento del risultato.


1° Es. SOMMA DI DUE NUMERI (pseudocodifica)


INIZIO- Somma istruzione (in corsivo)

Leggi A, B A B ed S si dicono VARIABILI e sono posizioni di memoria

S = A + B RAM. Quando forniamo l'algoritmo, il c. predispone nella

Scrivi S RAM le posizioni A B S. Al variare delle grandezze, il numero

FINE   precedentemente inserito nelle variabili viene sostituito dalla

nuova grandezza (all'inserimento del nuovo numero il vecchio

scompare.



Variabili del problema, sono i dati i cui valori vengono a cambiare nel corso dell'esecuzione del procedimento risolutivo. All'interno della risoluzione la variabile è indicata attraverso un nome simbolico detto identificatore:


Interpretazione:  

inizio del lavoro, finalità somma;

Prima istruzione leggi i numeri A e B (il c. si ferma ed attende che i numeri siano forniti dall'esterno, l'operatore digita i due numeri);

letti i due numeri, il c. li inserisce in due posizioni di memoria RAM (dichiara le variabili)

con la seconda istruzione il c. prende il contenuto di A, lo aggiunge a B ed il risultato lo immette in S;

terza istruzione il c. scrive a video S;

fine del lavoro.


Questo è ciò che fa il programmatore, rappresenta le proprie idee per la risoluzione di un problema, traduce l'algoritmo in un linguaggio di programmazione comprensibile al c. quali Pascal, COBOL, Basic, Delphi, ecc. (che verrà poi tradotto in formato digitale), e fornisce l'algoritmo al c. L'algoritmo deve essere utile non solo in un caso specifico, ma in tutti i casi in cui si deve risolvere quel determinato problema (nel caso dell alg. visto sopra, deve funzionare per tutti i numeri e non solo per la somma di due precisi numeri). Il programmatore deve prevedere tutte le possibilità che possono presentarsi in un problema, se una possibilità non viene prevista, l'algoritmo ha un BUG (errore di programma) che può renderlo inutilizzabile e bloccare il c.


Questo elementare algoritmo utilizza una delle tre strutture fondamentali detta SEQUENZA. Questa struttura indica che tutte le istruzioni devono essere eseguite nello stesso ordine nel quale sono riportate, senza alcuna possibilità di deviazione arbitraria.


Talvolta occorre predisporre domande, prevedere decisioni. Questa struttura si chiama SELEZIONE o SCELTA che propone la selezione di una tra due sequenze di istruzioni, in base alla risposta ad una domanda. Il quesito che permette la scelta di uno dei percorsi possibili è in realtà una condizione binaria, cioè un'espressione per la quale si può affermare che è vera o falsa. Individuate le parole chiave SE, ALLORA, ALTRIMENTI, ciò che segue la parola SE è l'indicazione di un evento che può o meno essersi verificato. Le istruzioni che seguono ALLORA vengono eseguite solo nel caso in cui la condizione risulta vera, d seguito ad ALTRIMENTI sono elencate, invece, le istruzioni da considerare se la condizione è falsa. (è comunque anche presente la SEQUENZA).


2° Es. Dato un numero stabilire se è pari o dispari, con messaggio a video "numero pari" o "numero dispari"


INIZIO- Pari

Leggi NUM

R= NUM MOD 2

SE R = 0

ALLORA

Scrivi "NUMERO PARI"

ALTRIMENTI

Scrivi "NUMERO DISPARI"

FINE - SE

FINE


Il linguaggio Pascal, mette a disposizione svariate funzioni di cui una chiamata MOD che fornisce il resto di una divisione

Si inserisce tra " " tutto ciò che deve essere scritto a video

Quando scrivo qualcosa che dipende da ciò che ho scritto in precedenza (istruzioni contenute in una stessa struttura), lo scrivo spostato verso destra (INDENTAZIONE), in questo modo è possibile identificare le parti principali del programma (sposate a sinistra) e verificarne la logica complessiva di funzionamento


Interpretazione:

inizio lavoro - finalità stabilire se un numero è pari o dispari;

Prima istruzione il c. aspetta l'imputazione del numero (NUM);

divide il NUM. PER 2 e assegna (= significa assegnazione) a R il resto (crea una locazione RAM per R);

MODALITA' DI SCELTA

SE il resto R è uguale a 0 il c. ALLORA esegue l'istruzione scrivi a video numero pari;

ALTRIMENTI se il R è diverso da 0 il c. esegue l'istruzione scrivi a video numero dispari - quando è stata attuata una scelta e individuata una delle due soluzioni, si passa poi direttamente a FINE SE

FINE modalità di scelta;

FINE programma.


3° Es. Individuare il massimo fra tre numeri. Ovvero dati 3 numeri il c. deve fornire sempre e comunque in output quale è il maggiore dei tre (il metodo usato è lo stesso che si segue per determinare quale di tre oggetti è il più pesante.


INIZIO - Massimo

Leggi A, B, C

MAX = A

SE B > MAX

ALLORA

MAX = B

(ALTRIMENTI)

FINE - SE

SE C > MAX

ALLORA

MAX = C

(ALTRIMENTI)

FINE - SE

Scrivi MAX

FINE


In questo algoritmo sono presenti due scelte "in cascata" l'una indipendente dall'altra, e dipendenti solo dai SE iniziali. Viene messo tra parentesi il comando ALTRIMENTI visto che una delle due alternative è falsa e non occorre eseguire dopo questa altre istruzioni ma passare all'altra scelta.

Interpretazione

Inizio funzione individuare il massimo fra tre numeri;

Leggi (il c. aspetta l'imputazione di A, B, C);

assegna A a MAX;

1^ SCELTA

SE B è maggiore di MAX, ALLORA assegna B a MAX;

se la condizione è vera passa a FINE SE e a Scrivi MAX, ALTRIMENTI non si assegna B a MAX e si passa direttamente alla 2^ SCELTA;

SE C è maggiore di MAX, ALLORA assegna C a MAX;

se la condizione è vera passa a FINE, SE ALTRIMENTI non si assegna C a MAX e si passa direttamente a SCRIVI MAX;

FINE programma.


Esercitazione

Dati 3 numeri trovare la differenza tra il massimo ed il minimo (N.B. ciò che non è richiesto è un errore)


INIZIO - Differenza

Leggi A, B, C

MAX = A

SE B > MAX

ALLORA

MAX = B

(ALTRIMENTI)

FINE - SE

SE C > MAX

ALLORA

MAX = C

(ALTRIMENTI)

FINE - SE

MIN = A

SE B < MIN

ALLORA

MIN = B

(ALTRIMENTI)

FINE - SE

SE C < MIN

ALLORA

MIN = C

(ALTRIMENTI)

FINE - SE

DIFF = MAX - MIN

Scrivi DIFF

FINE


4° Es. Leggere l'importo della spesa fatta in un ipermercato. Trovare l'importo scontato sapendo che:

spendendo fino a L. 500.000 si usufruisce dello sconto del 5% (imp. < o = a 500.000 = sc. 5%);

spendendo da L. 500.000 a L. 1.000.000  si usufruisce dello sconto del 10 % (500.001< imp < 1.000.000 = sc. 10%);

spendendo oltre L. 1.000.000 si usufruisce dello sconto del 15% (da 1.000.001 sc. = 15%).


INIZIO - Sconti

Leggi IMP

SE IMP < = 500.000

ALLORA

RIS = IMP - IMP * 5/100

ALTRIMENTI

SE IMP < = 1.000.000

ALLORA

RIS = IMP - IMP * 10/100

ALTRIMENTI

RIS = IMP - IMP * 15/100

FINE - SE

FINE - SE

Scrivi RIS

FINE


In questo algoritmo, preso in input l'importo totale, si fornisce in output l'imp. scontato. L'alg. è strutturato, oltre che con la consueta condizione di SEQUENZA, anche con una condizione di SCELTA non a cascata, ma NIDIFICATA; qui infatti una scelta dipende dalla precedente (il secondo SE dipende dal primo) e l'ALTRIMENTI non è inserito tra ( ) in quanto non vi sono possibili scelte false ma alternative che devono essere considerate.


Interpretazione

Inizio determinare importo scontato

Leggi - imputare l'IMPORTO;

1^ SCELTA: se IMP è minore o uguale a 500.000, ALLORA il RISULTATO è uguale a IMP scontato del 5%;

ALTRIMENTI, 2^SCELTA: SE IMP è minore o uguale a 1.000.000, ALLORA il RIS è uguale a IMP scontato del 10%;

ALTRIMENTI il RIS è uguale a IMP scontato del 15% ;

FINE 2^ SCELTA;

FINE 1^SCELTA;

SCRIVI a video RIS;

FINE programma.


5° Es. Dati N numeri, trovarne la media (risultato a video).


INIZIO - Media

Leggi N

I = 0

S= 0

RIPETI

FINCHE' I < N

Leggi NUM

S = S + NUM

I = I + 1

FINE - RIPETI

M = S/N

Scrivi M

FINE


In questo algoritmo è presente anche la struttura di ripetizione o iterazione (oltre alla sequenza ed alla scelta) che consente l'esecuzione ripetuta di una sequenza di istruzioni n base al risultato di una condizione binaria, in questo caso si usa la struttura RIPETI (istruzione), FINCHE' (condizione). Ogni volta che la condizione indicata risulta falsa, viene ripetuto il blocco di istruzioni. Questa struttura presenta il blocco di verifica della condizione dopo le istruzioni da ripetere, questo vuol dire che tale sequenza di operazioni è eseguita almeno una volta anche se la condizione risulta immediatamente vera. E' anche disponibile la struttura MENTRE (condizione), ESEGUI (istruzioni), che obbliga alla ripetizione delle istruzioni contenute tra le parole chiave INIZIO e FINE ogni volta che la condizione indicata risulta vera; quando la condizione risulta essere falsa, la macchina passa ad eseguire le eventuali istruzioni che seguono la struttura iterativa, N.B. se la condizione definita risulta falsa già al primo ingresso nella struttura, allora le istruzioni della sequenza di iterazione non verranno mai eseguite.


Interpretazione

Inizio trovare la media tra N numeri;

Leggi (imputare N, ovvero il numero che indica fra quanti numeri devo eseguire la media es. 4 numeri)

assegna 0 ad I (I e il contatore, conta i "giri" che faccio);

assegna 0 a S (S è l'accumulatore, accumula man mano i numeri facendone la somma)

RIPETI (comando di struttura di iterazione)  

FINCHE'   I (il contatore) è minore di N (quando il contatore avrà contato 4 giri compreso il primo che risulta 0 la condizione non sarà più vera e si chiuderà l'iterazione)

finché l'iterazione è valida, ad ogni giro LEGGI NUM (imputare il numero da considerare);

prendi il contenuto di S, aggiungilo al NUM e inserisci il risultato in S;

prendi il contenuto di I, aggiungi 1 ed inseriscilo in I (per contare i giri fatti);

FINE rimanda a RIPETI che fa ricominciare l'iterazione FINCHÉ I < N. Al raggiungimento di I = N si passa direttamente a prendi il contenuto di S, dividilo per N e mettilo in M;

scrivi M a video;

FINE programma


Tutte le volte che uso una variabile uguale a se stesso, devo INIZIALIZZARLA, ovvero impostarla = 0 (in questo caso I e S per non aver problemi di calcolo in accumulo e in contatore, M non la pulisco in quanto si pulisce automaticamente con la funzione S/N)


Nell'algoritmo. sopradescritto se manca I = I + 1 il contatore I resta 0 e la condizione FINCHE' I < N resta vera per sempre. L'algoritmo quindi va in "    LOOP" (loop = il programma ricicla se stesso senza termine quando manca l'incremento del contatore), e continua a ripetere l'operazione. In questo caso occorre resettare il c. Se manca Leggi N o un'altra variabile, l'algoritmo non funziona.


Un algoritmo si dice strutturato se in esso sono impiegate esclusivamente le tre strutture fondamentali: sequenza, selezione, iterazione.


Date le temperature di N città alle ore 13, trovare la temperatura media (e farla apparire a video)



INIZIO - Media

Leggi N

I = 0

S= 0

RIPETI

FINCHE' I < N

Leggi NUM

S = S + NUM

I = I + 1

FINE - RIPETI

M = S/N

Scrivi M

FINE


Leggere i voti di N studenti, trovare la media e dare un'opportuna segnalazione a seconda che la media sia maggiore o minore della sufficienza.


INIZIO - Media

Leggi N

I = 0

S= 0

RIPETI

FINCHE' I < N

Leggi NUM

S = S + NUM

I = I + 1

FINE - RIPETI

M = S/N

SE M > = 6

ALLORA

Scrivi "MEDIA MAGGIORE DI 6"

ALTRIMENTI

Scrivi "MEDIA MINORE DI 6"

FINE - SE

FINE













Privacy




Articolo informazione


Hits: 2230
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2024