Gli algoritmi

Materie:	Appunti
Categoria:	Informatica
Download:	203
Data:	23.04.2001
Numero di pagine:	6
Formato di file:	.doc (Microsoft Word)

Attività di programmazione: il computer è un sistema di elaborazione in grado di trasformare le informazioni che riceve in ingresso (che si chiamano dati di input) nei risultati che l’utente si aspetta (che si chiamano dati di output).

GLI ALGORITMI

Un algoritmo è una sequenza di passi o istruzioni elementari che devono essere eseguiti secondo un ordine prefissato per raggiungere il risultato voluto.

Caratteristiche o requisiti di un algoritmo, l’algoritmo deve essere:

1. FINITO, ovvero deve essere composto da un numero finito di passi che devono essere eseguiti un numero finito di volte.
(LOOP ( ciclo che viene eseguito all’infinito )

2. DETERMINISTICO, ovvero a fronte degli stessi dati di input, cioè a parità di condizioni di partenza, deve produrre gli stessi risultati.

3. NON AMBIGUO, ovvero i passi che compongono l’algoritmo devono essere interpretabili in modo univoco dall’esecutore. Deve essere sempre interpretato allo stesso modo.

4. GENERALE, ovvero deve fornire la soluzione per tutti i problemi appartenenti a una certa classe , cioè deve essere applicabile a qualunque valore dei dati di input appartenenti alla stessa classe.

Le componenti di un algoritmo

Le componenti di un algoritmo sono i dati, cioè gli oggetti su cui operare e le istruzioni, cioè i passi elementari che devono essere eseguiti.

I Dati
I dati si possono classificare sia in base al tipo che in base all’uso.
A ogni dato è associato un nome che lo identifica in modo univoco ed è sempre buona norma dare ai dati nomi significativi che permettono immediatamente di comprenderne il significato.

La classificazione dei dati è stabilita secondo il modo con cui essi interagiscono con l’elaboratore:
• INPUT : sono i dati forniti dall’esterno dell’elaboratore necessari all’elaboratore e devono essere noti al momento dell’esecuzione;
• OUTPUT : sono i risultati calcolati dall’elaboratore e comunicati all’esterno;
• INTERNI : sono i dati utilizzati nella trasformazione compiuta dall’algoritmo ma trasparenti all’utente. Si tratta di dati di lavoro che non vengono forniti in output.
•
I dati a seconda degli oggetti che rappresentano possono essere:
• NUMERICI :sono di dati che contengono numeri, sui quali è possibile effettuare le operazioni aritmetiche (somma, sottrazione, divisione, moltiplicazione). Possono ancora essere ulteriormente suddivisi in:
1- INTERI : dati numerici che non prevedono cifre decimali
2- REALI : dati numerici che prevedono cifre decimali
• ALFANUMERICI : (detti anche stringhe) sono i dati che contengono caratteri alfabetici, caratteri speciali e cifre sulle quali non sono possibili operazioni aritmetiche.
La classificazione è stabilita sulla possibilità di cambiare o meno il valore del dato durante l’esecuzione dell’algoritmo:
• COSTANTI : il valore del dato rimane immutato nel tempo
• VARIABILI: il valore del dato può cambiare nel tempo

Istruzioni

I passi elementari che compongono l’algoritmo sono le istruzioni che permettono di dare comandi all’esecutore che nel nostro caso è il computer.

1. Istruzione di lettura (LEGGI) : permette di assegnare a una variabile un valore tramite la sua digitazione sulla tastiera del computer.
In questa istruzione deve essere sempre specificato il nome della variabile che deve contenere il valore inserito da tastiera.
2. Istruzione di scrittura (SCRIVI) : permette di visualizzare sul video o sulla stampante un
messaggio o il valore di una variabile
3. Istruzione di assegnazione : permette di assegnare in diversi modi un valore a una variabile
( () simbolo

• NOME VARIABILE N VALORE IMMEDIATO
Se il valore che deve essere assegnato è di tipo alfanumerico, esso deve essere racchiuso tra gli apici.
• NOME VARIABILE N NOME VARIABILE
A A B
• NOME VARIABILE N ESPRESSIONE
A A (K + 3) /2

L’istruzione A L A +1 serve per INCREMENTARE di un’unità il valore della variabile A
L’istruzione A L A – 1 serve per DECREMENTARE di un’unità il valore della variabile A

Le variabili che non vengono inizializzate con operazioni di lettura o di assegnazione non hanno un valore definito (le variabili numeriche non contengono il valore zero)

La rappresentazione degli algoritmi

Diagrammi a blocchi (Flow-Chart)

Un metodo molto usato è il diagramma a blocchi o flow-chart, dove a ogni simbolo corrisponde un preciso tipo di operazione. Si tratta di un metodo molto diffuso perché semplice da imparare e in grado di offrire una percezione grafica del flusso di esecuzione delle istruzioni, anche se, poiché arriva a una descrizione molto dettagliata dei passi operativi, può risultare in alcuni casi alquanto complesso.

Ogni algoritmo deve iniziare con il simbolo

E deve concludersi con il simbolo

Il simbolo indica un’operazione di assegnazione
Il simbolo indica un’operazione di lettura (input)
Il simbolo indica un’operazione di scrittura (output)
Il simbolo indica un’istruzione di confronto (operazioni logiche)

Pseudocodifica

Un altro modo per rappresentare gli algoritmi è quello di utilizzare un linguaggio speciale che descrive le istruzioni con frasi rigorose anziché con simboli grafici. Ogni frase di questo linguaggio contiene parole chiave, scritte con lettere maiuscole, operatori e nomi di variabili.

La programmazione strutturata

Gli schemi o strutture che sono presenti in un algoritmo sono:
• Struttura di SEQUENZA
• Struttura di SELEZIONE
• Struttura di ITERAZIONE
Quando nella programmazione si fa uso sistematico di queste strutture, allora la programmazione si dice strutturata.

Le tecniche della programmazione strutturata nascono a metà degli anni 70, quando al crescere della attività di progettazione del software, si sentì la necessità di fornire regole nella progettazione in modo che i lavori prodotti fossero non solo più leggibili, ma anche più facilmente modificabili nel tempo. A questo riguardo il riferimento classico è il teorema di Bohm-Jacopini che afferma:
qualsiasi algoritmo può essere definito usando le strutture di sequenza, di selezione e di iterazione.

La struttura di sequenza
Si parla di struttura di sequenza quando le operazioni descritte vanno eseguite una dopo l’altra, secondo l’ordine con cui sono state definite.
Es.pag 101

La struttura di selezione
La struttura di selezione o di controllo permette di impostare nell’algoritmo percorsi diversi in base a condizioni che possono essere o meno verificate nel corso dell’esecuzione stessa.
Se la condizione è vera si compie un’azione, se invece la condizione è falsa si compie un’azione diversa.
Es.pag 101-102

I simboli =, =, ,, ….. sono detti operatori logici. Un operatore logico deve essere sempre presente nell’istruzione di controllo. Il simbolo = in questo caso equivale all’uguaglianza matematica, non all’istruzione di assegnazione.
Analizzando il formato dell’istruzione di controllo si osserva che il valore della variabile che si trova a sinistra dell’operatore logico può essere con:

1. valore immediato (A ( 5)
2. nome variabile il contenuto della variabile che si trova a sinistra dell’operatore logico è confrontato con il contenuto della variabile che si trova a destra ( A = B )
3. espressione viene prima calcolato il valore dell’espressione e successivamente è confrontato il valore della variabile che si trova a sinistra dell’operatore logico con il valore dell’espressione appena calcolato. A = (K * 5)/B

La struttura di selezione può essere a due vie se sono presenti istruzioni in entrambi i rami; si parla invece di selezione a una via quando sono presenti istruzioni solo su un ramo. Es . pag. 104
Le istruzioni presenti nei blocchi inseriti nei due rami non devono necessariamente essere elementari ma possono essere formate da più istruzioni (strutture di sequenza) o a loro volta strutture di selezione. In quest’ultimo caso si parla di strutture di selezione annidate. Es.105

Si parla invece di strutture di selezione in cascata quando due o più selezioni devono essere eseguite una dopo l’altra Es. 106

Struttura iterativa
Prima sono eseguite le istruzioni formanti il corpo dell’iterazione e dopo è eseguito il controllo per stabilire se ripetere il corpo dell’iterazione. Se la condizione di uscita del ciclo non è verificata (è falsa) allora il ciclo viene ripetuto altrimenti l’esecuzione prosegue con la prima istruzione che si trova sul ramo del vero. Il corpo dell’iterazione viene eseguito almeno una volta.