Click to edit Master title styleAlgoritmo

• algoritmo: un insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in un tempo finito

• in termini informali: un algoritmo è una sequenza ordinata di operazioni che risolve un problema specifico

Click to edit Master title styleProprietà

• un algoritmo deve essere:

• non ambiguo (i risultati non devono variare in funzione della macchina o persona che esegue l'algoritmo)

• corretto (deve risolvere un dato problema)

• realizzabile (deve essere eseguibile con le risorse a disposizione)

• finito (deve essere composto da un numero finito di passi elementari; le operazioni sono eseguite un numero finito di volte)

• efficiente (deve avere un costo accettabile, se non ottimo, in termini di risorse consumate: tempo di CPU richiesto per completare, quantità di memoria utilizzata, quantità di bit trasferiti)

Click to edit Master title styleEfficienza

• efficienza è il termine usato per descrivere l’uso attento delle risorse da parte di un algoritmo

• come si misurano il tempo e lo spazio consumati da un algoritmo, in modo da determinare se è efficiente?

– efficienza rispetto allo spazio: si può giudicare in base alla quantità di informazioni che l’algoritmo deve registrare nella memoria del computer per svolgere il proprio compito, oltre ai dati iniziali sui quali opera

– efficienza rispetto al tempo: è un’indicazione della quantità di “lavoro” richiesto dall’algoritmo stesso; è una misura dell’efficienza implicita del metodo, indipendente dalla velocità della macchina su cui è eseguito, dai valori dei dati di ingresso elaborati ma non dalla loro quantità

Click to edit Master title styleComplessità

• descrive l'efficienza dell'algoritmo– numero di operazioni svolte dall'algoritmo relativamente alla

misura dell'informazione su cui opera l'algoritmo

• esempio: per mettere in ordine una lista di N numeri interi un algoritmo può eseguire N*N operazioni oppure logN operazioni

• complessità tipiche degli algoritmi, in ordine crescente:– logN, N, NlogN, N2, 2N

Click to edit Master title styleDescrizione di un algoritmo

• un algoritmo è descritto in linguaggio

• il linguaggio di descrizione di un algoritmo deve essere adeguato alle caratteristiche del suo esecutore

• esecutore umano:

– linguaggio naturale

– linguaggio grafico (ad esempio i diagrammi di flusso)

• esecutore automatico (computer):

– linguaggio di programmazione

Click to edit Master title styleEsecuzione

• l'esecuzione delle azioni nell'ordine specificato

dall'algoritmo consente di ottenere, a partire dai dati

di ingresso, i risultati che risolvono il problema

ESECUTORE

una macchina astratta

capace di eseguire le

azioni specificate dallo

algoritmo.

EsecutoreDATI RISULTATI

Metodo

Risolutivo

(algoritmo)

Click to edit Master title styleEsempio

• scrivere un algoritmo per decidere se l'assicurazione della macchina è scaduta– anno corrente < anno scadenza polizza? non è scaduta, fine

– anno corrente > anno scadenza polizza? è scaduta, fine

– mese corrente < mese scadenza polizza? non è scaduta, fine

– mese corrente > mese scadenza polizza? è scaduta, fine

– giorno corrente < giorno scadenza polizza? non è scaduta, fine

– giorno corrente > giorno scadenza polizza? è scaduta, fine

– non è scaduta ma lo sarà tra 24 ore

Click to edit Master title styleVariabili

• una variabile rappresenta una zona di memoria RAM che può essere usata per memorizzare un valore

• analogia con una scatola di scarpe etichettata in uno scaffale (che rappresenta la RAM):– la scatola ha un nome

– una posizione nello scaffale

– un valore (le scarpe che si trovano dentro la scatola)

– [un tipo (forma della scatola)]*

(* vedremo più avanti cos'è e a che serve il tipo di una variabile)

Click to edit Master title styleVariabili

• A = Valore oppure A ← Valore significa che "Valore" viene memorizzato nella zona di memoria RAM etichettata con l'etichetta "A":

Valore

A

Click to edit Master title styleVariabili

• B = A oppure B ← A significa che "Valore", precedentemente memorizzato nella zona di memoria etichettata con "A" viene copiato nella zona di memoria etichettata con "B":

Valore

A B

Click to edit Master title styleDiagrammi di flusso

• un diagramma di flusso (flow chart) è la definizione grafica delle operazioni che costituiscono un algoritmo

• è uno strumento efficace per la descrizione degli algoritmi

• i diagrammi di flusso usano forme geometriche diverse per rappresentare:– trasferimento di informazioni (lettura dati, scrittura risultati,

visualizzazione dati intermedi)

– esecuzione di calcoli

– assunzione di decisioni

– esecuzione di iterazioni (ripetizione di sequenze di operazioni)

Click to edit Master title styleDiagrammi di flusso

– elaborazione – i blocchi rettangolari rappresentano istruzioni di assegnazione di valori o una modifica dello stato globale della computazione

– input/output - i blocchi a forma di parallelogramma corrispondono a operazioni di input/output dei dati (lettura da tastiera, visualizzazione su video)

– decisione – i blocchi a forma di rombo vengono utilizzati per rappresentare istruzioni di salto condizionato

– inizio/fine – i blocchi ovali vengono utilizzati per rappresentare l’inizio e la fine dell’algoritmo

v E

condition

start

stop

operation

yes no

Click to edit Master title styleCalcolo dell’area di un rettangolo

• leggi da input l’altezza (H)

• leggi da input la base (B)

• calcola l’area H*B

• dai in output il risultato

Click to edit Master title styleCalcola l’area di un rettangolo

Area = Base*Altezza

START

Leggi Altezza

Leggi Base

Stampa Area

STOP

Click to edit Master title styleConversione lire in euro

• leggi da input l’importo in lire

• calcola il corrispettivo in Euro

• dai in output il risultato

Click to edit Master title styleConversione lire in Euro

Euro = Lire/1936,27

START

Leggi Lire

Stampa Euro

STOP

Click to edit Master title styleIF-THEN-ELSE

• selezione tra due istruzioni sulla base di una condizione

I

O

Then Else

Click to edit Master title styleMassimo tra due numeri

• leggi X

• leggi Y

• se X > Y– stampa X

altrimenti– stampa Y

Click to edit Master title styleMassimo tra due numeri

Click to edit Master title stylePari o dispari

• leggi N

• dividi N per 2

• se resto = 0– scrivi “N è pari”

altrimenti– scrivi “N è dispari”

Click to edit Master title stylePari o dispari

Click to edit Master title styleWHILE-DO

I

O

Click to edit Master title styleESEMPIO

• CALCOLO DEL FATTORIALE

• N!=N*(N-1)*(N-2)*…*2

F=F*N

START

Leggi N

Stampa F

STOP

N>1?

yes

no

F = N

N=N-1

Click to edit Master title styleREPEAT-UNTIL

I

O

Click to edit Master title styleESEMPIO

• CALCOLO DEL FATTORIALE

• N!=N*(N-1)*(N-2)*…*2

Click to edit Master title styleScambio dei valori di due variabili

• Leggi valore prima variabile X

• Leggi valore seconda variabile Y

• Conserva X in una variabile temporanea Aux

• Assegna il valore di Y ad X

• Assegna il valore di Aux a Y

• Scrivi X

• Scrivi Y

Click to edit Master title styleScambio dei valori di due variabili

Click to edit Master title styleEsercizi

• dati 2 numeri in input trovare e stampare in output il max

• dati 3 numeri in input trovare e stampare in output il max

• dati 3 numeri in input stamparli in ordine crescente

• dati 2 numeri in input stampare in output la somma

• sul prezzo di un prodotto viene praticato lo sconto del 3% se costa meno di 1.000.000 e del 5% se costa di più; dato in input il prezzo P, calcolare il prezzo da pagare secondo la regola sopra descritta

• sul prezzo di un biglietto di un treno viene applicato un supplemento del 7% se il treno è di tipo "a", del 12% se è di tipo "b" e del 18% se è di tipo "c"; per gli altri treni non c'è supplemento; calcolare il prezzo totale del biglietto, a seconda del tipo di treno e comunicare il tipo di treno con il prezzo calcolato

Click to edit Master title styleEsercizi

• dati in input i min, ore e sec stampare in output il totale dei secondi

• data in input una data verificare se è giusta

• dato in input 100 valori stampare in output la somma dei numeri positivi e la somma dei negativi

• dato in input una parola stampare in output se è una palindrome o no

• dato in input una parola stampare in output il numero delle vocali

Click to edit Master title styleAlgoritmo e programma

• ogni computer è una macchina in grado di

eseguire azioni elementari su dati

• l'esecuzione delle azioni elementari viene

attivata tramite sequenze di istruzioni

• le istruzioni sono espresse attraverso frasi di

un opportuno linguaggio di

programmazione

• un programma non è altro che la formula-

zione testuale di un algoritmo in un

linguaggio di programmazione

Click to edit Master title styleAlgoritmo e programma

un programma è la formulazione testuale, in un

certo linguaggio di programmazione, di un

algoritmo che risolve un dato problema.

problema algoritmo programma

metodo

risolutivo

linguaggio

di

programmazione