Fondamenti di Informatica 4. Gli algoritmi4. Gli algoritmi

Corso di Laurea in Ingegneria Informatica e dell’Au tomazioneA.A. 2012-20132° SemestreProf. Giovanni Pascoschi

Gli algoritmi

22Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• AnalisiAnalisi ee programmazioneprogrammazione•• GliGli algoritmialgoritmi

�� ProprietàProprietà eded esempiesempi�� CostantiCostanti ee variabili,variabili, assegnazione,assegnazione, istruzioni,istruzioni, proposizioniproposizioni

ee predicatipredicati

Sommario

33

ee predicatipredicati•• GliGli strumentistrumenti perper lala formalizzazioneformalizzazione didi algoritmialgoritmi

�� DiagrammiDiagrammi aa blocchiblocchi

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Tramite un elaboratore si possono risolvere problemi di varianatura: emissione di certificati anagrafici, gestione dei c/c di unistituto di credito, prenotazioni aeree, ecc…

• Il problema deve essere formulato in modo opportuno, perché siapossibile utilizzare un elaboratore per la sua soluzione

• Per analisianalisi ee programmazioneprogrammazione si intende l’insieme delle attività

Analisi e programmazione #1

44

• Per analisianalisi ee programmazioneprogrammazione si intende l’insieme delle attivitàpreliminari atte a risolvere problemi utilizzando un elaboratore,dalla formulazione del problema fino alla predisposizionedell’elaboratore

�� ScopoScopo dell’analisidell’analisi �� definire un algoritmoalgoritmo�� ScopoScopo delladella programmazioneprogrammazione �� realizzarerealizzare unun programmaprogramma

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• AlgoritmoAlgoritmo:: elenco finito di istruzioni, che specificano leoperazioni eseguendo le quali si risolve una classe diproblemi� Un particolare problema della classe viene risolto tramite

l’apposito algoritmo sui dati che lo caratterizzanoUnUn algoritmoalgoritmo nonnon puòpuò essereessere eseguitoeseguito direttamentedirettamente

Analisi e programmazione #2

55

�� UnUn algoritmoalgoritmo nonnon puòpuò essereessere eseguitoeseguito direttamentedirettamentedall’elaboratoredall’elaboratore

•• ProgrammaProgramma:: ricetta che traduce l’algoritmo ed èdirettamente comprensibile, pertanto eseguibile, daparte di un elaboratore

•• LinguaggioLinguaggio didi programmazioneprogrammazione:: linguaggio rigoroso(piu’ vicino al linguaggio naturale) che permette laformalizzazione di un algoritmo in un programma

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• EsempioEsempio

ProblemaProblema:: Effettuare un accreditosu un c/c bancario

Programma + datiAlgoritmo + dati

ElaboratoreUomo +

Calcolatrice

Analisi e programmazione #3

66

SoluzioneSoluzione:: Utilizzare un programmache serva per predisporre ilcalcolatore all’accredito di unaqualunque cifra su un qualunquec/c; cifra da accreditare e numerodi c/c sono i dati caratteristici delproblema

AnalogieAnalogie tratra lele azioniazioni cheche devonodevonoessereessere eseguiteeseguite dada unun operatoreoperatoreumanoumano e,e, inin modomodo automatico,automatico,tramitetramite unun elaboratoreelaboratore

Calcolatrice

RisultatiRisultati

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• AlgoritmoAlgoritmo deriva dal nome del matematico arabo AlAl KhuwarizmiKhuwarizmi,vissuto nel IX secolo d.C.

• Un algoritmo è una successione di istruzioniistruzioni o passipassi chedefiniscono le operazioni da eseguire sui dati per ottenere irisultati; un algoritmo fornisce la soluzione ad una classeclasse didiproblemiproblemi

Definizione di algoritmo

77

• Lo schemaschema didi esecuzioneesecuzione di un algoritmo specifica che i passidevono essere eseguiti in sequenza, salvo diversa indicazione

• Ogni algoritmo è concepito per interagire con l’ambiente esternoper acquisire dati e comunicare messaggi o risultati; i dati su cuiopera un’istruzione sono forniti dall’esterno o sono frutto diistruzioni eseguite in precedenza

Ambiente esterno AlgoritmoRisultati o messaggi

Dati

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Sia dato un mazzo da 52 carte da ordinare inmodo che le cuori precedano le quadri, che a loro voltaprecedono fiori e picche; le carte di uno stesso seme sonoordinate dall’asso al re

Esempio : ordinamento del mazzo di carte

88

ordinate dall’asso al re•• AlgoritmoAlgoritmo::

� Si suddivida il mazzo in 4 mazzetti, ciascuno costituito datutte le carte dello stesso seme

� Si ordinino le carte di ciascun mazzetto dall’asso al re� Si prendano nell’ordine i mazzetti delle cuori, quadri, fiori

e picche

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Si vuole ricercare, all’interno di un mazzo dichiavi, quella che apre un dato lucchetto

•• AlgoritmoAlgoritmo::1) Si seleziona una chiave dal mazzo e la si marca con un

pennarello

Esempio : ricerca in un mazzo di chiavi

99

pennarello2) Si tenta di aprire il lucchetto con la chiave appena

marcata; se funziona, si va al passo 4)

3) Altrimenti, si controlla la chiave successivai. Se non è marcata, la si marca e si torna al passo 2)

ii. Viceversa, si prende atto che nel mazzo non è presentela chiave che apre il lucchetto

4) Fine della ricerca

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Calcolo delle radici reali di ax2+bx+c=0

•• AlgoritmoAlgoritmo::

1) Acquisire i coefficienti a,b,c

Esempio : radici delle equazioni di 2° grado

1010

Acquisire i coefficienti a,b,c2) Calcolare ∆ = b2−4ac3) Se ∆<0 non esistono radici reali, eseguire l’istruzione 7)4) Se ∆=0, x1=x2=−b/2a, poi eseguire l’istruzione 6)5) x1=(−b+√∆)/2a, x2=(−b−√∆)/2a6) Comunicare i valori x1, x2

7) Fine

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Affinché una ricettaricetta,, un elenco di istruzioni, possa essereconsiderato un algoritmo, devono essere soddisfatti iseguenti requisiti:

�� FinitezzaFinitezza:: ogni algoritmo deve essere finito, cioè ogni singolaistruzione deve poter essere eseguita in tempo finito ed unnumero finito di volte

GeneralitàGeneralità:: ogni algoritmo deve fornire la soluzione per una

Proprietà degli algoritmi

1111

�� GeneralitàGeneralità:: ogni algoritmo deve fornire la soluzione per unaclasse di problemi; deve pertanto essere applicabile aqualsiasi insieme di dati appartenenti all’insiemeinsieme didi definizionedefinizioneo dominiodominio dell’algoritmodell’algoritmo e deve produrre risultati cheappartengano all’insiemeinsieme didi arrivoarrivo oo codominiocodominio

�� NonNon ambiguitàambiguità:: devono essere definiti in modo univoco ipassi successivi da eseguire; devono essere evitati paradossi,contraddizioni ed ambiguità; il significato di ogni istruzionedeve essere univoco per chiunque esegua l’algoritmo

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Un algoritmo deve poter essere eseguito da chiunque, senzache l’esecutore sia stato necessariamente coinvolto nell’analisidel problema o nella descrizione dell’algoritmo

• Gli algoritmi devono essere formalizzati per mezzo di appositilinguaggi, dotati di strutture linguistiche che garantiscanoprecisione e sintesi

Algoritmi

1212

precisione e sintesi

• I linguaggi naturali non soddisfano questi requisiti, infatti...

� …sono ambiguiambigui: la stessa parola può assumere significati diversiin contesti differenti (pescapesca è un frutto o un’attività sportiva;ancora: ambiti, principi, vera, venti, avanzato, mora, amare…)

� …sono ridondantiridondanti: lo stesso concetto può essere espresso inmolti modi diversi, ad esempio “somma 2 a 3”, “calcola 2+3”,“esegui l’addizione tra 2 e 3”

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• I dati su cui opera un algoritmo sono costanticostanti evariabilivariabili

� Un dato è costante quando il suo valore non può essereaggiornato durante l’esecuzione dell’algoritmo o peresecuzioni successive

Costanti e variabili #1

1313

esecuzioni successive

� Una variabile è una coppia <nome, valore>: può essereimmaginata come una scatola sulla quale è scritto unnome e che può contenere un valore

Rappresentazione di una variabileRappresentazione di una variabile

NomeNome

ValoreValore

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Il valore di una variabile deve appartenere all’insiemeinsieme dididefinizionedefinizione, su cui si opera mediante regole opportune,specifiche dell’insieme

• Data una variabile <x,v>, x è il nomenome della variabile e v è ilsuo valorevalore attualeattuale; le variabili sono indeterminate in fase didefinizione dell’algoritmo, ma corrispondono a valori specifici

Costanti e variabili #2

1414

suo valorevalore attualeattuale; le variabili sono indeterminate in fase didefinizione dell’algoritmo, ma corrispondono a valori specificidurante ogni esecuzione

•• EsempioEsempio:: Nell’algoritmo di risoluzione delle equazioni di2°grado, a, b, c non corrispondono a nessun valore finchénon si esegue l’algoritmo per trovare le soluzioni di una dataequazione, ad esempio x2−9x−4=0; in fase di esecuzione,a=1, b=−9, c=−4; nell’istruzione ∆=b2−4ac, ∆ è la variabileche contiene il valore del discriminante

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• L’istruzione di assegnazioneassegnazione definisce il valore attuale di unavariabile, che resta inalterato fino all’assegnazione successiva

• L’assegnazione si rappresenta con il simbolo “←”:

nome_variabilenome_variabile ←←←←←←←← espressioneespressione

che si legge “assegna alla variabile nome_variabile il valore diespressione” ; l’espressione a destra di ← è costituita da

Assegnazione #1

1515

che si legge “assegna alla variabile nome_variabile il valore diespressione” ; l’espressione a destra di ← è costituita davariabili, costanti e operatori

• L’assegnazione viene così eseguita:a) si valuta l’espressione a destra di ←, sostituendo ai nomi di

variabile i loro valori attuali; il risultato deve appartenereall’insieme di definizione della variabile a sinistra di ←

b) il valore calcolato diventa il nuovo valore della variabile il cuinome appare a sinistra di ←

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• II nominomi delledelle variabilivariabili possonopossono essereessere sceltiscelti inin modomodoarbitrario,arbitrario, mama èè opportunoopportuno selezionareselezionare nominomi significativisignificativideldel contenutocontenuto delladella variabilevariabile

• È necessario rispettare la regolaregola dell’ordinamentodell’ordinamento:

Assegnazione #2

1616

• È necessario rispettare la regolaregola dell’ordinamentodell’ordinamento:

QuandoQuando unauna variabilevariabile appareappare aa destradestra didi ←← inin unaunaassegnazioneassegnazione devedeve essereessere giàgià istanziataistanziata

cioè le deve essere già stato assegnato un valore

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• EsempiEsempi

c4

a ← b+c b6

410 6

Prima dell’assegnazione

Assegnazione #3

1717

x ← x+3x

14

x17

Dopo l’assegnazione

Prima dell’assegnazione

4

ca10

b6

Dopo l’assegnazione

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Istruzioni operative, che producono risultati

• Istruzioni di controllo, che controllano il verificarsi di condizionispecificate e, in base al risultato del controllo, determinano il flussodi istruzioni da eseguire

• Istruzioni di salto, che alterano il normale flusso di esecuzionesequenziale delle istruzioni di un algoritmo, specificando quale siala successiva istruzione da eseguire

Le istruzioni #1

1818

la successiva istruzione da eseguire

� nelle istruzioni di saltosalto condizionatocondizionato, l’effettiva esecuzione del salto èlegata al verificarsi di una condizione specificata

� l’istruzione di saltosalto incondizionatoincondizionato produce sempre un salto

• Istruzioni di ingresso/uscita, che specificano come debbaessere effettuata una trasmissione di dati o messaggi fral’algoritmo e l’ambiente esterno

• Istruzioni di inizio/fine esecuzione, che indicano l’inizio/la finedell’algoritmo

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• EsempioEsempio:: CCalcoloalcolo delledelle radiciradici didi equazioniequazioni didi 22°° gradogrado

a) “acquisire i coefficienti a, b, c” è un’istruzione di lettura(ingresso)

b) “calcolare ∆=b2−4ac” è un’istruzione operativa

“se ∆=0, x =x =−b/2a” è un’istruzione di controllo: l’istruzione

Le istruzioni #2

1919

c) “se ∆=0, x1=x2=−b/2a” è un’istruzione di controllo: l’istruzionedi assegnazione x1=x2=−b/2a viene eseguita solo se ∆=0

d) “comunicare i valori x1, x2” è un’istruzione di scrittura (uscita)

e) “eseguire l’istruzione 6)” è un’istruzione di salto incondizionato

f) “se ∆<0 eseguire l’istruzione 7)” è un’istruzione di saltocondizionato, perché l’istruzione 7) è la prossima istruzione daeseguire solo se ∆<0

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Una proposizione è un costrutto linguistico del quale sipuò asserire o negare la veridicità

•• EsempiEsempi1) “Roma è la capitale della Gran Bretagna” falsafalsa2) “3 è un numero intero dispari” veravera

Proposizioni e predicati #1

2020

2) “3 è un numero intero dispari” veravera

• Il valorevalore didi veritàverità di una proposizione è il suo essere vera ofalsa

• Una proposizione è un predicatopredicato se il suo valore di veritàdipende dall’istanziazione di alcune variabili

•• EsempiEsempi1) “la variabile età è minore di 30”2) “la variabile base è maggiore della variabile altezza”

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• La valutazione di un predicato è l’operazione chepermette di determinare se il predicato è vero o falso,sostituendo alle variabili i loro valori attuali

• I valori vero e falso sono detti valori logici o booleani

Proposizioni e predicati #2

2121

• Proposizioni e predicati possono essere espressiconcisamente per mezzo degli operatori relazionali:

= (uguale) ≠ (diverso)

> (maggiore) < (minore)

≥ (maggiore o uguale) ≤ (minore o uguale)

• I predicati che contengono un solo operatore relazionalesono detti semplicisemplici

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Dato un predicato pp, il predicato notnot pp, detto opposto onegazione logica (NOT) di pp, ha i valori di verità oppostirispetto a pp

• Dati due predicati pp e qq, la congiunzione logica (AND) ppandand qq è un predicato vero solo quando pp e qq sono entrambiveri, e falso in tutti gli altri casi

• Dati due predicati pp e qq, la disgiunzione logica (OR) pp oror qq

Proposizioni e predicati #3

2222

• Dati due predicati pp e qq, la disgiunzione logica (OR) pp oror qqè un predicato falso solo quando pp e qq sono entrambi falsi, evero in tutti gli altri casi

• I predicati nei quali compare almeno un operatore logico, notnot,andand, oror, sono detti composti

• La tabella di verità di un predicato composto specifica ilvalore del predicato per ognuna delle possibili combinazioni deisuoi argomenti

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• EsempioEsempionotnot (base > altezza)

è vero solo quando il valore di base è minore o uguale del valore dialtezza

età > 30 andand età < 50

Proposizioni e predicati #4

2323

età > 30 andand età < 50

è vero solo quando il valore di età è compreso tra 30 e 50 (esclusi)

base > altezza oror base > 100

è vero quando il valore di base è maggiore del valore di altezza, oquando il valore di base è maggiore di 100, o quando entrambe lecondizioni sono verificate

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

DIAGRAMMI A BLOCCHI

Diagrammi a blocchi

2424

DIAGRAMMI A BLOCCHI

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Il linguaggio dei diagrammidiagrammi aa blocchiblocchi è un possibileformalismo per la descrizione di algoritmi

• Il diagramma a blocchi, o flowchartflowchart, è una rappresentazionegrafica dell’algoritmo

• Un diagramma a blocchi descrive il flussoflusso delle operazioni daeseguire per realizzare la trasformazione, definita

I diagrammi a blocchi #1

2525

eseguire per realizzare la trasformazione, definitanell’algoritmo, dai dati iniziali ai risultati

• Ogni istruzione dell’algoritmo viene rappresentata all’internodi un bloccoblocco elementareelementare, la cui forma grafica è determinatadal tipo di istruzione

• I blocchi sono collegati tra loro da lineelinee didi flussoflusso, munite difrecce, che indicano il susseguirsi di azioni elementari

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

Blocchi elementariBlocchi elementari

XX

leggi/scrivileggi/scrivibeginbeginAA

I diagrammi a blocchi #2

I/O

2626

endend

Blocco finaleBlocco finale

CC

Blocco di controllo

Blocco di lettura/scritturaBlocco di lettura/scritturaBlocco inizialeBlocco iniziale

Blocco azione Blocco azione

falsofalsoverovero

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Un diagrammadiagramma aa blocchiblocchi è un insieme di blocchielementari composto da:

a) un blocco iniziale

b) un blocco finale

I diagrammi a blocchi #3

2727

b) un blocco finale

c) un numero finito n (n≥1) di blocchi di azione e/o diblocchi di lettura/scrittura

d) un numero finito m (m≥0) di blocchi di controllo

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• I programmatori inesperti tendono ad “aggrovigliare” ilprogramma introducendo numerosi salti privi di regole(spaghettispaghetti programmingprogramming)

• L’analisianalisi strutturatastrutturata favorisce, viceversa, la descrizione dialgoritmi facilmente documentabili e comprensibili

• I blocchi di un diagramma a blocchi strutturato sono collegati

Analisi strutturata #1

2828

• I blocchi di un diagramma a blocchi strutturato sono collegatisecondo i seguenti schemi di flusso:�� SchemaSchema didi sequenzasequenza – più schemi di flusso sono eseguiti in

sequenza�� SchemaSchema didi selezioneselezione – un blocco di controllo subordina

l’esecuzione di due possibili schemi di flusso al verificarsi di unacondizione

�� SchemaSchema didi iterazioneiterazione – si itera l’esecuzione di un dato schemadi flusso

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Ovvero: un diagrammadiagramma aa blocchiblocchi strutturatostrutturato è undiagramma a blocchi nel quale gli schemi di flusso sonostrutturatistrutturati

• Uno schema di flusso è strutturato quando soddisfa unadelle seguenti proprietà…

1) …è uno schema elementare o uno schema di sequenza

Analisi strutturata #2

2929

…è uno schema elementare o uno schema di sequenza

S1, S2,…, Sn schemidi flusso strutturati

end

A

begin

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

2) …è uno schema di selezione

Analisi strutturata #3

3030

� Nel primo caso, lo schema S viene eseguito solo se lacondizione C è vera; se C è falsa, non viene eseguitaalcuna azione (ad una via)

� Nel secondo caso, viene eseguito solo uno dei due schemiSv o Sf, in dipendenza del valore di verità della condizione

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

3) …è uno schema di iterazione

Analisi strutturata #4

pre-condizionale post-condizionale

3131

� Nel primo caso, S può non venire mai eseguito, se la condizione Cè subito falsa; nel secondo caso, S viene eseguito almeno una volta

� Quando lo schema S viene eseguito finché la condizione C simantiene vera si parla di iterazioneiterazione perper verovero; si ha un’iterazioneiterazioneperper falsofalso quando S viene eseguito finché C è falsa

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

pre-condizionale post-condizionale

•• OgniOgni diagrammadiagramma aa blocchiblocchi nonnon strutturatostrutturato èètrasformabiletrasformabile inin unun diagrammadiagramma aa blocchiblocchi strutturatostrutturatoequivalenteequivalente

• Due diagrammi a blocchi sono equivalentiequivalenti se, operandosugli stessi dati, producono gli stessi risultati

• L’uso dell’analisi strutturata garantisce:

Analisi strutturata #5

3232

• L’uso dell’analisi strutturata garantisce:� facilità di comprensione e modifica dei diagrammi a

blocchi� maggiore uniformità nella descrizione degli algoritmi

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Inoltre...

� È stato dimostrato (teorema fondamentale dellaprogrammazione di Bohm−−−−Jacopini, 1966) che ogniprogramma può essere codificato riferendosi esclusivamentead un algoritmo strutturato e quindi attenendosi alle trestrutture fondamentali:

Analisi strutturata #6

3333

SequenzialeSequenziale IterativaIterativa CondizionaleCondizionale

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Il teorema di Bohm−−−−Jacopini ha un interesse soprattuttoteorico, in quanto i linguaggi di programmazione tendono adotarsi di più tipi di istruzioni, non sempre “rispettose” delteorema, ma utili per la realizzazione di programmi di facilescrittura e comprensione

Analisi strutturata #7

3434

scrittura e comprensione

• Il suo valore consiste nella capacità di fornire indicazionigenerali per le attività di progettazione di nuovi linguaggi estrategie di programmazione

• In effetti, esso ha contribuito alla critica dell’usosconsiderato delle istruzioni gogo toto e alla definizione dellelinee guida della programmazione strutturata, sviluppatenegli anni `70

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

� In un diagramma strutturato non apparirà mai una istruzionedi salto incondizionato: i tre schemi fondamentali possonoessere concatenaticoncatenati, uno di seguito all’altro, o nidificatinidificati, unodentro l’altro; non possono in nessun caso essere “intrecciati”o “accavallati”

Analisi strutturata #8

3535

CorrettoCorretto

SbagliatoSbagliato

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Diagramma a blocchi per laselezione, in un mazzo dichiavi, di quella che apre unlucchetto

Esempio

3636Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• NoteNote::

•• ProblemaProblema:: Calcolare la somma ditre interi consecutivi

Gli algoritmi iterativi #1

3737

•• NoteNote::

� La variabile sommasomma(totalizzatore) è uncontenitore di somme parziali,finché non si ottiene la sommatotale richiesta

� La soluzione del problema vieneraggiunta eseguendo azionisimili per un numero opportunodi volte

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Il ciclo o loop è uno schema di flusso per descrivere, in modoconciso, situazioni in cui un gruppo di operazioni deve essere ripetutopiù volte

• La condizione di fine cicloviene verificata ogni volta che siesegue il ciclo; se la condizioneassume valore vero (falso), leistruzioni vengono reiterate,

Gli algoritmi iterativi #2

3838

istruzioni vengono reiterate,altrimenti si esceesce daldal ciclociclo

• La condizione di fine ciclo puòessere verificata prima o dopol’esecuzione dell’iterazione

• Le istruzioni diinizializzazione assegnanovalori iniziali ad alcune variabili(almeno a quella che controlla lacondizione di fine ciclo)

Ciclo con controllo in codaCiclo con controllo in codaCiclo con controllo in testaCiclo con controllo in testa

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Calcolare la somma ditre interi consecutivi

Gli algoritmi iterativi #3

3939

•• NoteNote::

� La fase di inizializzazione riguardala somma e l’indice del ciclo

� Il controllo di fine ciclo vieneeffettuato in coda (iterazione perfalso)

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Un ciclo è definitodefinito quando è noto a priori quante volte deveessere eseguito; un ciclo definito è detto ancheenumerativoenumerativo (ciclo for)

• Un contatorecontatore deldel ciclociclo tiene memoria di quante iterazionisono state effettuate; può essere utilizzato in due modi:

Gli algoritmi iterativi #4

4040

sono state effettuate; può essere utilizzato in due modi:

�� incrementoincremento deldel contatorecontatore:: il contatore viene inizializzato ad unvalore minimo (ad es. 0 o 1) e incrementato ad ogniesecuzione del ciclo; si esce dal ciclo quando il valore delcontatore eguaglia il numero di iterazioni richieste

�� decrementodecremento deldel contatorecontatore:: il contatore viene inizializzato alnumero di iterazioni richiesto e decrementato di uno ad ogniiterazione; si esce dal ciclo quando il valore del contatoreraggiunge 0 (o 1)

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

• Il ciclo for puo’ essere rappresentato anche con un unicoblocco� esempio :

i=0 a NPasso 1

Gli algoritmi iterativi #5

Passo 1

4141Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

……

• Un ciclo è indefinitoindefinito quando non è possibile conoscerea priori quante volte verrà eseguito

• La condizione di fine ciclo controlla il valore di una opiù variabili modificate da istruzioni che fanno parte

Gli algoritmi iterativi #5

4242

più variabili modificate da istruzioni che fanno partedell’iterazione

• Comunque, un ciclo deve essere eseguito un numerofinito di volte, cioè si deve sempre verificare laterminazioneterminazione dell’esecuzione del ciclo

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Calcolo della mediadi un insieme di numeri; nonè noto a priori quanti sono inumeri di cui deve esserecalcolata la media

Gli algoritmi iterativi #6

4343

calcolata la media� I numeri vengono letti uno

alla volta fino a che non siincontra un x=0, che segnalala fine dell’insieme

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

•• ProblemaProblema:: Somma di unasequenza di numeri� Indicando con ai il generico

elemento da sommare, la formulagenerale è

Ancora esempi ...

4444

generale èS = a1+ a2 +…+ an

� La variabile n conta quante voltesi ripete l’iterazione: n vienedecrementata di 1 ad ogniiterazione ed il ciclo terminaquando n vale 0

� La variabile A è usata per l’inputdegli ai, S per le somme parziali etotale

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

Gli algoritmi

�Analisi e programmazione�Costanti e variabili�Diagrammi a blocchi

Sommario della lezione

4545

�Algoritmi strutturati (Bohm Jacopini)

Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni

�Domande?

Fine della lezione

4646Fondamenti di Informatica – A.A. 2012-2013 a cura di Pascoschi Giovanni