Informatica II

Algoritmi

Algoritmo = procedura computazionale ben definita che, dato un input, produce un output attraverso una serie finita di azioni.

L'algoritmo e i dati sono strettamente legati.

L'algoritmo deve dare in tempo limitato un risultato certo, unico e ripetibile quindi deve essere non ambiguo, finito e infine devono essere eseguibili e descritte con il livello di dettaglio che dipende dall'esecutore (linguaggio di programmazione universale tradotto da un compilatore in codice macchina).

Linguaggi per la descrizione di algoritmi

• Grafi di flusso (flow-charts)

È uno pseudo linguaggio che utilizza simboli grafici per descrivere istruzioni e l'ordine di esecuzione tra esse che riprendono le schede perforate su cui nel 1960 era scritto il programma.

Istruzione di lettura: leggere un nuovo dato (esempio: 5) e assegnare il suo valore alla variabile "nome".

Istruzione di scrittura: (scrivere in uscita il valore della variabile denominata "nome").

Istruzione di assegnazione: (calcola il valore della espr. arith. assegna il valore risultato alla variabile "nome").

Istruzione di test: (calcola il valore della espr. booleana se la risposta è vera, segui il ramo V altrimenti il ramo F).

Istruzione di stop (fermarsi).

La lettura e l'assegnazione sono variabili di istruzioni o di azione, le altre sono di controllo poiché definiscono solo l'ordine.

Ci sono 3 strutture di controllo.

Sequenza: definisce l'ordine sequenziale.

Selezione: scelta tra 2 alternative.

Algoritmi

Algoritmo = procedura computazionale ben definita che dato un input produce un output attraverso una serie finita di azioni.

L'algoritmo e i dati sono strettamente legati.

L'algoritmo deve dare in tempo limitato un risultato certo, unico e ripetibile, quindi deve essere non ambiguo, finito e le azioni devono essere eseguibili e descritte con un livello di dettaglio che dipende dall'esecutore (linguaggio di programmazione universale tradotto da un compilatore in codice macchina).

Linguaggi per la descrizione di algoritmi

Grafi di flusso (Flow-charts).

È uno pseudo linguaggio che utilizza simboli grafici per descrivere istruzioni e ordine di esecuzione tra esse e che riprendendo le schede perforate su cui negli anni '60 era scritto il programma.

Istruzione di lettura: leggere univocamente un dato (inserito nel bus) assegnandolo al valore di una variabile "nome".

Istruzione di scrittura: scrivere in uscita il valore della variabile denominata "nome".

Istruzione di assegnazione (calcola il valore della espr. arith. assegnandolo al valore risultato nella variabile "nome").

Istruzione di test (calcola il valore della espr. booleana); se la risposta è vera segui il ramo V, altrimenti il ramo F.

Istruzione di stop (fermarsi).

La lettura e l'assegnazione sono variabili di istruzioni e di azione, le altre sono di controllo poiché definiscono solo l'ordine. Ci sono 3 strutture di controllo.

Sequenza.

Selezione: scelta tra 2 alternative.

Iterazione.

Il loop è una sequenza ciclica di istruzioni contenente almeno una istruzione che modifichi la condizione del ciclo necessaria per evitare un loop infinito.

Pseudocodifica

È un linguaggio naturale e più formale che utilizza uno pseudocodice, cioè un linguaggio di programmazione fittizio per rappresentare l'algoritmo senza scendere in dettaglio su un particolare linguaggio di programmazione.

temp ← a (Il contenuto di a è assegnato a temp).

Assegnazione.

Sequenza.

begin.

end.

Selezione.

if condizione then istruzione1.

else.

(istruzione2).

Iterazione.

While condizione do.

(istruzione).

for ind ← inf to sup do.

(istruzione).

Foreach elemento ε insieme do.

istruzione.

Problema

Dato A insieme di N elementi generare un nuovo insieme A con elementi originali diminuiti del massimo di A.

Algoritmo

1. Cerca il massimo di A.
2. Costruisci il nuovo insieme A.

Per rendere l'algoritmo maggiormente leggibile lo scomponiamo in moduli.

Ora il problema consiste nella risoluzione dei due moduli.

1. Scegli un elemento come massimo provvisorio.
2. Per ogni elemento c'è.
3. Se > massimo provvisorio — scegli come massimo provvisorio.

1.a. si per ogni elemento ∈ A sostituisci con i-il valore massimo.

Manca la rappresentazione dei nostri dati! Considerato A con un array una posizione di memoria.

A[1] ha come valore x₁ etc.

Così all'inizio scelgo il primo elemento togliendo ogni ambiguità ora posso risolvere il primo modulo.

xmax (X: A, integer m).