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 ed 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

1. 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) ed 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 d'istitutive 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

Sequenzabeginend

Selezioneif condizione then istruzione1else(istruzione2)

IterazioneWhile condizione do(istruzione)for ind ← inf to sup do(istruzione)Foreach elemento ε insieme doistruzione

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'è
   • 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)