CorsoInformaticadiBase

FlowChart

AbbiamodettoChe..• INFORMATICA:scienzaetecnicachetrattal'elaborazioneautomaticadeidatiedeiprocedimentidicalcolo

• CALCOLATOREOELABORATORE ELETTRONICO:macchinaelettronicaingradodimanipolareautomaticamenteinformazioni,eseguendooperazionisudatifornitiiningresso(input),perotteneredeirisultatiemessicomedatiinuscita(output)

• PROGRAMMA: insiemediistruzionichepossonoessereeseguitedaunelaboratoreelettronico.

• PROGRAMMATORE: Sioccupadirealizzareoperativamenteleapplicazioni,scrivendoleistruzionisottoformadilineedicodicebasatesuspecificilinguaggidiprogrammazione.

ModellodiComputer(semplificato)

Dati In Ingresso

Elaborazione dei Dati

Dati in Uscita

Informatica

SecondolaACM(AssociationforComputingMachinery)…L’InformaticaèloStudiosistematicodeglialgoritmi chedescrivonoetrasformanol’Informazione:laloroteoria,analisi,progetto,efficienza,realizzazioneeapplicazione.

RisoluzionediunProblema

Problema

Algoritmo

Programma

Linguaggio Macchina

Input Macchina Output

L’uomo descrive l’algoritmo che lamacchina deve seguire per risolvere ilproblema (ad esempio con i Diagrammidi flusso)

La descrizione viene tradotta inLinguaggio di alto livello (adesempio il linguaggio C)

Il programma di alto livelloviene tradotto in linguaggioMacchina, ovvero codice binario(ad esempio dalcompilatore)

EsempidiAlgoritmi

Ricettapercucinareglispaghetti

➔Mettil’acquanellapentola➔ Faibollirel’acqua➔Mettilapastanell’acqua➔ Aggiungiunpo’ disale➔ Attendi6minuti➔ Scolalapasta

EsempidiAlgoritmi

Verificaseunnumeroèpariodispari➔ Prendiilnumero➔ Calcolailrestodelladivisioneinteradelnumeroper2➔ Seilrestoèzero

– Allorailnumeroèpari– Altrimentiilnumeroèdispari

AlgoritmiConilterminealgoritmo siintende,ingenere,unmetodoperlarisoluzionediproblemiutilizzandounnumerofinitodipassi.

Daquestadefinizionesievinconolequattroproprietàfondamentalidell'algoritmo:

• lasequenzadiistruzionideveesserefinita(finitezza);• essadeveportareadunrisultato(effettività);• leistruzionidevonoessereeseguibilimaterialmente(realizzabilità);

• leistruzionidevonoessereespresseinmodononambiguo(nonambiguità).

Caratteristichediunalgoritmo• Azionieseguibilienonambigue

– Nonsonoammessi“unpò” e“apiacere”,chenonsonotermini adattiadunamacchina

• Deterministico– Fattounpasso,ilsuccessivoèunoedunosolo,bendeterminato.Alternativesonopossibili,malasceltadeveessereunica

• Numerofinitodipassi• Terminazione

– L’esecuzioneprimaopoidevefinireeprodurreunrisultatointempofinito

– Osservazione:la3nonimplicala4

Esempiodinonterminazione

SiconsideriilnumeroN• ScrivereN• ScrivereilnumerosuccessivoadN• Ripetereilpassoprecedente

Esempiodinonterminazione

Trovailpiùgrandenumeroprimo.

Nonesisteunprogrammacheriesceadareunarispostaintempofinito(Numerofinitodipassi)

Tuttiiproblemisonorisolvibili???

No..

Unproblemarisolvibileconunalgoritmosidicecomputabile

Risoluzionediunproblema

Generalmentelarisoluzionediunproblemaconsistenelprenderealcunidatiiniziali(input)relativialproblemaenelfornireunrisultato(output)cherisolvequest’ultimo.

Input Esecutore Output

Algoritmo

NonècosìFacilePerscriverelagiusta“sequenzadipassi”bisognaessereunbravocuoco!

PrepararegliSpaghetti:• Ingredienti(acqua,Sale,Spaghetti)• Eseguirelaricetta• ServiregliSpaghetti

Codificadell’AlgoritmoAffinchèunamacchinariescaacomprendereedeseguireipassispecificatidaunalgoritmo,quest’ultimodeveessereprimacodificatoinunopportunoprogramma scrittoinunlinguaggioadaltolivello (cheverràsuccessivamentecompilato/interpretato)

Algoritmo Traduzione Programma

Rappresentazionedeglialgoritmi

E’ necessariofarriferimentoadeiformalismiche:• nonintroducanoambiguità• sianouniversalmentericonosciutiedinterpretatiallostessomododaungenericoesecutore

• permettanodirappresentareinmodoefficaceunalgoritmo

• Costituiscanounutilestrumentoperpoipoterpassareallafasedicodificainunlinguaggiodiprogrammazione

Rappresentazionedeglialgoritmi

1. Rappresentazionegrafica– Diagrammiablocchi/FlowChart

2. Rappresentazionetestuale– NotazioneLineareStrutturata/PseudoCodice

Algoritmi:operazionibase

Leoperazioniprimariesono:• Trasferimentodiinformazioni(istruzionidiI/O)

• letturadati,scritturarisultati,visualizzazionedatiintermedi

• Esecuzionedicalcoli(valutazioneespressioni)• Istruzionidiassegnamento• Strutturedicontrollo(chemodificanoilflussosequenzialediesecuzionedelleoperazioni)

DiagrammidiFlusso

Idiagrammiablocchi (dettianchediagrammidiflusso)sonounlinguaggiodimodellazionegraficoperrappresentarealgoritmi(insensolato).

Essoconsentedidescrivereledifferentioperazionisottoformadiunoschemaincuilediversefasidelprocessoeledifferenticondizionichedevonoessererispettatevengonorappresentatidasimboligraficidettiblocchielementari.Iblocchisonocollegatitralorotramitefreccecheindicanolacronologia.

DiagrammidiFlussoOgniazioneelementareèrappresentatadaunblocco.Esistono5tipidiblocchielementari:

Blocco iniziale Blocco finale

Blocco I/O

Blocco ControlloBlocco Elaborazione

IstruzionidiI/O

• letturadidatiininput• scritturadeirisultatiinoutput

Connettori

Isingolidiagrammidevonoessereunititramiteiconnettori.

L’esecuzionedelleistruzionideveesserefattasequenzialmente,ovveroseguendoiconnettori.

Quandosiscrivel’algoritmobisognafaremoltaattenzionealladirezionedelflussodiesecuzione.

IstruzionediAssegnamento

Concettodivariabile• Identificatadaun’etichetta/identificatoresimbolico

• Puòesserecomodopensareallavariabilecomeaduncontenitoreincuipossiamomemorizzareoreperiredeidatiutilizzatiduranteilcalcolo

• L’istruzionediassegnamentopermettediassegnareunvaloreadunavariabile

IstruzionediAssegnamento

Unavariabilenumerica èunaentitàcaratterizzatada• Unnome• Unvalore(contenuto)• PuòcambiareneltempoUnacostantenumerica èunaentitàcaratterizzatada• Unnome• Unvalore(contenuto)• Nonpuòcambiareneltempo

IstruzionediAssegnamento

A = 5Alla Variabile Aassegno il valore 5

Espressione

Un’espressione èunacombinazionedioperatoriaritmetici,costantievariabilichepuòesserecalcolatagenerandounsingolovalorenumerico

Es:X+1X+(Y*5)

IstruzionediAssegnamento

• Istruzionediassegnamento:“ ”

• VariabileEspressioneX5YX+4

AssegnoallaVariabilexilvalore5LaVariabileYconterràilvaloredellasommatrailnumero4edilvaloreassegnatoallavariabileX

X = 5 Y=X+4

Esempio

Descriveremediantediagrammidiflusso,unalgoritmochecalcolilasommadiduenumerilettiininput

Diagrammadiflusso:Somma

Inizio

Leggi Y

Leggi X

Z X + Y

Scrivi Z

Fine

Esempio2

Descrivere,mediantediagrammidiflusso,unalgoritmochescambiivalorididuevariabililetteininput.

Diagrammadiflusso:Scambio

Inizio

Leggi X

Leggi Y

Aux Y

Y X

X Aux

Scrivi Y

Scrivi X

Fine

Flussodiesecuzione

Sipossonoaverecasiincuinelflussodiesecuzionesidevesceglieretradiversedirezioni

Ladirezionedascegliereèsubordinataalverificarsidiunacondizione

Lacondizionepuòassumereduestati:– Vero– Falso

Inquesticasisiparladiistruzionecondizionale

StrutturedicontrolloTuttiglialgoritmidevonoadattarsiadunaclassediproblemiperessereapplicatialmondorealeeleoperazionidaeffettuareperraggiungerelasoluzionespessodifferisconoasecondadeicasichesipresentano.

Perquestoesistonodelleparticolaristrutturedellinguaggiochepermettonodicontrollareilflussodiesecuzione(quindidelleoperazioni),ovverodieseguireunacertaseriediistruzionianchepiu'voltenelmomentoincuisiverificadiunaseriedicondizioni.

Questestrutturesonoassolutamenteindispensabili,infattinonesisteunlinguaggiodiprogrammazioneincuinone'possibilecontrollareilflussodelprocesso.

StrutturedicontrolloQuasilatotalitàdeiprogrammihalanecessitàdisvolgerealcuneistruzioniocompieredeterminateoperazioni(oppureevitaredicompierealcuneoperazioni)asecondadeidatidipartenza.

Peresempiounprogrammacheesegueunadivisionetraduenumeria/bdovràevitaredicompierel'effettivaoperazionearitmeticaseildatob=0.

Perquestointuttiilinguaggidiprogrammazioneesistonodeiparticolaricostruttichegeneralmentepermettonodi:- Scegliereseeseguireomenounacertaporzionedicodice,oppure- Eseguirepiùvolteunacertapartedicodice.

Strutturedicontrollo

IstruzioniCondizionaliLa selezione (o scelta) permette a un programma di proseguire secondo uno tra due (o più) flussi di istruzioni alternative, a seconda del risultato di un test o del verificarsi di una condizione.

L’iterazione (o ciclo, o loop) consiste nella ripetizione di una o più istruzioni, e si può ottenere collegando il flusso in uscita da un blocco con il flusso in entrata nel blocco stesso o in uno precedente.In tal modo si possono eseguire compiti ripetitivi senza specificare uno per uno un gran numero di singoli passi, ma scrivendo per esempio un’istruzione del tipo: “esegui il prossimo passo 1.000 volte”.

IstruzioniCondizionaliSelezionebinaria.Nellaselezioneiltestolacondizionesonotipicamentecostituitidaunavariabilelogica,scrittadentroilsimbolodidecisione,(bloccocontrollo)dalqualeesconoduefrecce.Questeindicanolepossibiliazionidacompiersiasecondadelvaloredellavariabile,comemostralafigura.

IstruzioniCondizionali

Sipuòanchevolerecompiereunacertaazioneseiltestolacondizionehannounvalorevero,enessunaazionenelcasocontrario.

Esempio

Descriveremediantediagrammadiflusso,unalgoritmochedeterminiilmassimotraduenumerilettiininput

DiagrammadiFlusso:Max

Inizi

Leggi X

Leggi Y

X>Y Scrivi X

Scrivi Y

Vero

Falso

Fine

StrutturaIF-ELSEL’istruzionecondizionaleif-else ècostruitapersceglierel’esecuzionediun’istruzioneinalternativaaun’altraasecondadelvaloreassuntodaunadatacondizione.

if(condizione){operazione}L'operazionepuòanchenonessereracchiusatraparentesigraffe.

Vediamounsempliceesempio.if($a==5) {echo"Lavariabileavale5";}Inquestocasoverràstampatalastringa"Lavariabileavale5"soloquando$asaràugualea5.

StrutturaIF-ELSEAbbiamointrodottoilcontrolloreelse:aggiungelapossibilitàdi

eseguireun'istruzionealternativanelcasolacondizionenonsiavera.

if(condizione){operazione1}else{operazione2}

Vediamooradiapplicaretuttiicasifinoravisti,utilizzandol'annidamentodipiùif:l'importanteèricordarsidichiuderesempreunacondizionechesièaperta.

if($a>$b){echo"aèmaggioredib";}else{if($a<$b){echo"aèminoredib";}else{if($a==$b){echo"aèugualedib";}}}

StrutturediControlloIterattiveLestrutturedicontrollo"iterative"consentonodispecificarecheunadataistruzioneoundatobloccodiistruzionidevonoessereeseguitiripetutamente.Essevengonoanchedettecicli.

Ognistrutturadicontrollodiquestotipodeveconsentiredispecificaresottoqualicondizionil'iterazione(ripetizione)ditaliistruzionidebbaterminare,ovverolacondizionediterminazionedelciclo oppure,equivalentemente,lacondizionedipermanenzanelciclo.

StrutturaWhileIlciclowhile (mentre,ofintantoché)èindicatoquandolacondizionedipermanenzainuncicloèunagenericacondizionebooleana,indipendentedalnumerodiiterazionieseguite.Leformetradizionalidiciclowhilepossonoessereparafrasatecome"ripeti(ilcodicecontrollato)fintantochérestaveralacondizioneC".Unesempiotipicoèlaletturadidatidaunfiledicuinonsiconoscaaprioriladimensione;essopotrebbeassumerelaforma"leggiilprossimodatofinchénonincontrilafinedelfile".

StrutturaWhile

Vediamounsempliceesempio:$i=1;while($i<=10){echo$i;$i++;

}Questociclocontinuaadincrementarelavariabile$ifinoaquandononsaràugualea10edognivoltastampailsuovalore.Inpraticaverràstampatalastringa"12345678910".

StrutturaDo-WhileUnmodoalternativopereseguirelastessacosasaràricorrerealciclo

do..while.L'unicadifferenzaècheilvaloredellacondizionevienecontrollatoallafinedelcicloenonall'inizio.Inpraticalaprimaoperazionevienesempreeseguita,siachelacondizionesiaveraofalsa.do{operazione}while(condizione)

Vediamol'esempio:$i=1;do{echo$i;$i++;

}while($i<=10)

StruttureDatiUnastrutturadati èun'entitàusataperorganizzareuninsiemedidatiall'internodellamemoriadelcomputer,edeventualmentepermemorizzarliinunamemoriadimassa.Lasceltadellestrutturedatidautilizzareèstrettamentelegataaquelladeglialgoritmi.

La strutturadatièunmetododiorganizzazionedeidati,quindiprescindedaidatieffettivamentecontenuti.

Ciascunlinguaggiodiprogrammazioneoffrestrumenti,piùomenosofisticati,perdefinirestrutturedati,ovveroaggregaredatiditipoomogeneooeterogeneo.

GliArrayUnarrayèunastrutturadatiomogenea,checontieneunnumerofinitodielementidellostessotipo,adesempiounvettoredi10interi.Questielementisonoindividuatiattraversounindicenumerico,chetipicamentevada0alnumeromassimodielementimenouno.Ladimensionedelvettoredeveesseredichiarataalmomentodellasuacreazione.Vettorididimensionediversacostituisconotipididatidiversi.

Glielementidell'array(levariabilichelocostituiscono)sonoidentificatedallostessonomedell'arrayedaunoopiùindici,cheindicanolaposizionedell'elementoall'interodelvettoreodellamatrice.

GliArrayArraymonodimensionale:Unarrayadunadimensioneècostituitodauninsiemefinitodielementiomogeneiincorrispondenzabiunivocaconuninsiemediindici.

Arraybidimensionale puòessereconsideratounarraydiarraymonodimensionalicioèognicomponentedell’arrayèessostessounarray

L’accessoadognicomponentediunarraybidimensionalesihatramiteunacoppiadiindici(i,j)

Ilprimoindicesiriferisceallarigaedilsecondoallacolonna

GliArray

X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7]

Array Monodimensionale

X

A[0][0] A[0][1] A[0][2] A[0][3] A[0][4]A[1][0] A[1][1] A[1][2] A[1][3] A[1][4]A[2][0] A[2][1] A[2][2] A[2][3]

Array Bidimensionale

A

COLONNE

R

I

G

H

E

GliArray

Essigodonodelleseguentiproprietà:• Gliarraysonounodeitipididatostrutturato• Sonocompostidaelementiomogenei• Ognielementoèidentificatoall’internodelvettore

daunnumerod’ordinedettoancheindicedell’elemento

• E’ possibileriempireoleggereunasolaposizionepervolta

• Ilnumerodeglielementièdettodimensione olunghezza delvettore

GliArray

Adesempio,pensiamodivolermemorizzareinomideigiornidellasettimanaall'internodell'arrayditipostringachiamatogiorno;avremolaseguentestruttura:

$giorno[0]="lunedi'"$giorno[1]="martedi'"$giorno[2]="mercoledi'"$giorno[3]="giovedi'"$giorno[4]="venerdi'"$giorno[5]="sabato"$giorno[6]="domenica"

Array

Esercizisugliarray