Algoritmi

Definizione

E’ un insieme ordinato di istruzioni che risolvono un

problema

Da al- Khwarizmi:

importante matematico Arabonato nel 780 circa a Baghdad

Proprietà di un algoritmo

Ha un unico punto di inizioL’istruzione successiva deve essere univoca

Ogni istruzione ha una durata limitataLe istruzioni devono essere non ambigueLe istruzioni devono essere elementari

Può avere più punti di fine

Esempi di algoritmi

Istruzioni di montaggio (mobili IKEA)Preparazione del caffèPrelievo bancomatPreparazione di una ricettaCalcolo del massimo comun divisore tra due interi

Problemi non risolvibili

Ci sono problemi non risolvibili da nessun modellodi calcolo reale o astratto

predire il valore delle azioni Alitalia nel 2012.predire chi vincerà il campionato di calcioCalcolare tutte le cifre decimali di π

Come si fa una tortaRiscalda il forno alla

temperatura prescelta

Procura tutti gli ingredienti

Mescola tutti gli ingredienti

Versa il composto nella teglia

Cuoci per 50 minuti

Algoritmo Approssimato !!!

Il problema dei secchi

Determinare le operazioni necessarie per far si che il primo secchio (da 3 litri) sia riempito con 2 litri.

Possiamo agire sui due secchi attraverso le seguenti operazioni : - riempire completamente un secchio- svuotarlo completamente- travasare una certa quantità di liquido da un secchio all’altro

Sono presenti due secchi

3 Litri 4 Litri

Soluzione

Riempi il secchio da tre litriTravasa nel secchio da quattroRiempi il secchio da tre litriTravasa fino a riempire completamente quello da quattro

Il problema del contadinoUn contadino deve trasportare al di là di un fiume il suo lupo, la sua

capra e una cesta di cavoli.Ha a disposizione una barca poco capiente che può trasportare:

solo lui in compagnia di uno dei due animali

solo lui insieme alla sola cesta di cavoli.

Istruzioni per il contadino:

TraghettaRitorna

Prendi CapraPrendi LupoPrendi Cavoli

Deposita CapraDeposita LupoDeposita Cavoli

SoluzionePrendi la capraTrasportala e posalaTornaPrendi il lupoTrasportalo e posaloPrendi la capraRitorna Trasportala posalaPrendi i cavoliTrasportali posaliTornaPrendi la capraTrasportala e posala

Un programmaUn algoritmo

scritto per un esecutore computerin un linguaggio ad esso comprensibile

Il computer non è intelligenteBisogna:

Fornirgli tutte le istruzioniDargliele nell’ordine giusto

Esempio: Algoritmo per fare una frittata

Prendi la padella Prendi l’olio Prendi le uova

Quante mani deve avere?

Che tipo di problema?

Dato un elenco di nomi e numeri di telefono, trovare il numero di una data persona,

…. ordinare l’elenco ….

Esempi di applicazioni informatiche:

Risolvere problemi matematici

Creare, modificare e alterare suoni o immagini

Pilotare l’elettronica esterna

Supportare operazioni di commercio elettronico

CodificaFase di scrittura di un programma attraverso un insieme ordinato di “frasi” (istruzioni) scritte in un linguaggio di programmazione

Per ogni linguaggio esiste l’opportuno ambiente che consente la:

1- Scrittura (codifica)

2- Esecuzione

del programma

Flow Chart

�Una notazione grafica per descrivere

un algoritmo è fornita dai diagrammi di

flusso

�Un diagramma di flusso consente di

descrivere le istruzioni da eseguire e il

loro ordine

Primitive grafiche

Connettore: inizio/fine,

Connettore: punti di collegamento

Elaborazione: operazione/istruzione

Decisione: confronto/test di una espressione

Direzione flusso di controllo

Lettura dati / Scrittura dati

Regole per il disegno

� Ciascun blocco deve potere essere

raggiunto dal blocco iniziale

� Il blocco finale deve essere raggiungibile

da qualsiasi altro blocco

� Ciascuna freccia entra in un blocco o si

innesta in un’altra freccia

I SottoproblemiIndica la presenza di un blocco di istruzioni che si occupano della risoluzione di un sottoproblema

Esempi di sottoproblemi:

• Prendi i dati

• Fai i calcoli

• Visualizza i risultati

• Componi il numero di telefono

La Sequenza

A è una istruzione elementare

S1 ed S2 sono due sottoproblemi

Ovviamente sono possibili combinazioni miste.

Esempio di sequenzaSpegni la svegliaAlzatiLavatiVestitiFai ColazioneAscolta la radioEsci di casa

Alcune sono istruzioni elementari, altri sono sottoproblemi

!??!

Discutibile...

Esempio di sequenza

Acquisisci il valore di nAcquisisci il valore di mMoltiplica n per mComunica il risultato

Se:

n vale 4

m vale 8Il risultato (area del rettangolo) vale 32

Il flow dell’area del rettangoloArea Rettangolo

Richiesta base e altezzaI

Calcola Area

Comunica valore AreaO

Fine

Il computer si mette in contatto con l’utente per acquisire da Tastiera i due valori necessariIn questo punto il programma acquisisce

informazioni I = Input = entrano i dati

Il computer si mette in contatto con l’utente per visualizzare il risultato

In questo punto il programma invia informazioniO= Output = escono i dati

Il computer esegue il calcolo

Non si vede niente all’esterno

La deviazione dalla sequenzaLa selezione o scelta:

C’è una condizione logica C da sottoporre a test

Vero

Il risultato del test

Falso

Viene eseguito il blocco S1 o il blocco S2 in funzione della risposta

Le istruzioni sono in alternativa

Si riprende la normale sequenza

Esempio di scelta

CONTROLLA LA TEMPERATURA

FA FREDDO?

NOSI

INDOSSA IL CAPPOTTO

INDOSSA LA GIACCA

Ci sono gruppi di istruzioni da eseguire in alternativa

a seconda della risposta

La scelta non è sempre completa

HAI FAME?SI

NOFAI COLAZIONE

Non sempre c’e’ una alternativa.

L’algoritmo:

prosegue in sequenza se si risponde NO

devia dalla sequenza se si risponde SI

Attenzione ai controlli!

Piove ?

NO

SI

GUARDA FUORI DALLA FINESTRA

PRENDI L’OMBRELLO

Minacciapioggia ?

NO

SI

GUARDA FUORI DALLA FINESTRA

PRENDI L’OMBRELLO