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