problemi, soluzioni ed algoritmi · •per essere eseguito, l’algoritmo deve essere formulato in...
TRANSCRIPT
![Page 1: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/1.jpg)
FondamentidiInformaticaProblemi,SoluzioniedAlgoritmi
Prof. Chr i st ian Espos i toCorso d i Laurea in Ingegner ia Meccanica e Gest iona le (C lasse I )A .A . 2017/18
Problemi,SoluzioniedAlgoritmi
![Page 2: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/2.jpg)
ComeInstruire i Calcolatori aRisolvere Problemi• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisuinformazioniedati
•Macomeciòavviene?1. Abbiamobisognodicodificareopportunamenteinformazioniedati2. Abbiamobisognodiimpartirelegiusteistruzioniperrisolvere
correttamenteiproblemi
Problemi,SoluzioniedAlgoritmi 02/60
![Page 3: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/3.jpg)
RelazionetraRealtàeModello:ComeModellareunProblema
Modello
F = m × a
re tf
ft 1213
tt 1415
Costruzione modello
Ricerca dellasoluzione
Interpretazionedella soluzione
Mondo Reale
Problemi,SoluzioniedAlgoritmi 03/60
![Page 4: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/4.jpg)
RisolvereunProblema
Risolvere unProblema
1.Scegliereastrazione definendouninsiemedidatirilevantichecaratterizzanolarealtà
2.Scegliererappresentazione dei dati
3.Individuareunprocedimentoadeguato(Algoritmo epoiProgramma)
4.Scomporreeventualmenteilprocedimento insotto-procedimenti
Problemi,SoluzioniedAlgoritmi 04/60
![Page 5: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/5.jpg)
IlTermineAlgoritmo:Etimologia• DerivadalmatematicoAraboMuḥammad ibn Mūsā al-Khwārizmī (c.780-850),autoredeltestoAl-jabrw’al-muqabâla (dacuiancheiltermineAlgebra)
Problemi,SoluzioniedAlgoritmi 05/60
![Page 6: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/6.jpg)
Algoritmi:unpo’diStoria• Algoritmiditiponumericofuronostudiatidamatematicibabilonesieindianipiùdi3000annifa
• Algoritmiinusofinoatempirecentifuronostudiatidaimatematicigrecinel500a.C.• AlgoritmodiEuclide perilMassimoComunDivisore• Algoritmigeometrici(calcoloditangenti,sezionidiangoli,etc)• Etc
Problemi,SoluzioniedAlgoritmi 06/60
![Page 7: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/7.jpg)
GliAlgoritminelTrattamentodell’Informazione– 1/3• Unalgoritmoconsentedirealizzareunparticolaretrattamentodell’informazioneopiùingeneraledirisolvereunospecificoproblema• Calcolarelasommadiduenumeri• Calcolarelalunghezzadell’ipotenusadiuntriangolorettangolo• Risolvereun’equazionedisecondogrado• Maanche…
Problemi,SoluzioniedAlgoritmi 07/60
![Page 8: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/8.jpg)
GliAlgoritminelTrattamentodell’Informazione– 2/3• TrasmissionedatiinInternet• Comesigestisceinpraticailflussodidatinellarete?• RicercanelWEB• ComefaGoogleatrovareleinformazioninelWEB?• Bioinformatica• ComeilDNAdeterminalenostrecaratteristiche?• Processieconomici• Comesigestisconoleasteon-linesuEbay?• ComesieffettualacompravenditadiazionisuInternet?• Organizzazionedirisorseeservizi• Comesischedulanoivolidelleaerolinee?• Comesiassegnanolefrequenzenellecelledellereticellulari?• Etc
Problemi,SoluzioniedAlgoritmi 08/60
![Page 9: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/9.jpg)
GliAlgoritminelTrattamentodell’Informazione– 3/3• L’esperienzaquotidianasuggerisceinfinitiesempidialgoritmi
•Molteazionichesvolgiamoabitualmentepossonoesseremodellatemediantealgoritmi• Istruzionidimontaggio• Preparazionedelcaffè• Prelievobancomat• Preparazionediunricetta• Indicazioniperunlavoroamaglia• Etc
Problemi,SoluzioniedAlgoritmi 09/60
![Page 10: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/10.jpg)
Algoritmo:Definizioni• Definizione1: proceduradicalcolobendefinita,cheprendeuninsiemedivaloricomeinputeproduceuninsiemedivaloricomeoutput
• Definizione2: sequenzadiazionielementaricheconsenteditrasformareidatiinizialineirisultatifinaliattraversounnumerofinitodipassinonambigui
• Note• Insiemedidatiinizialibendefinito• Sequenzadipassipuòessereeseguitadaunesecutore(ades.calcolatore)
ALGORITMODati iniziali Dati finali (soluzione)
Problemi,SoluzioniedAlgoritmi 10/60
![Page 11: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/11.jpg)
Esempio:Algoritmoperprenderel’Automobile• Algoritmo
1. Aprirel’auto2. Aprirelaportiera3. Sedersialpostodiguida4. Allacciarelacintura5. Schiacciarelafrizione6. Avviareilmotore7. Inserirelaprimamarcia8. Togliereilfrenoamano9. Rilasciare“delicatamente”lafrizioneperpartire
Osservazione: ipassisonoeseguitiinsequenzael’ordinedelleistruzionièessenzialeperlacorrettezza
Problemi,SoluzioniedAlgoritmi 11/60
![Page 12: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/12.jpg)
Algoritmi:EsecutoreeLinguaggio– 1/3• Unalgoritmopresupponelapresenzadiqualcuno(oqualcosa)ingradodieseguirlo,chiamatoesecutore• Ininformatical’esecutoreèilcalcolatore
• L’algoritmoviene“letto”dall’esecutore• L’esecutore,partendodaidatiininput,esegue(inunbenprecisoordine)tutteleistruzionidell’algoritmostesso,ottenendoalterminedellapropriaesecuzioneidatiinoutput
• Peressereeseguito,l’algoritmodeveessereformulatoinunlinguaggiocomprensibiledall’esecutore• Unesecutorepuòeseguireunalgoritmoformulatoinunlinguaggiochenonconosce,apattochel’algoritmostessosiapreventivamentetradottoinunlinguaggiocheinvecegliènoto
Problemi,SoluzioniedAlgoritmi 12/60
![Page 13: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/13.jpg)
Algoritmi:EsecutoreeLinguaggio– 2/3• L’algoritmodeve• Prevederesoltantoistruzionicherichiedonoall’esecutoredieffettuareoperazionielementari• Operazionicheeglisacompieresenzabisognodiulteriorispecificazioni
• Essereformulato in unlinguaggiononambiguo,incuicioèogniistruzionecaratterizziunivocamenteunadelleoperazionichel’esecutoreèingradodicompiere
• Specificaresenzaambiguitàl’ordinediesecuzione delleistruzioni,cuil’esecutoredeveattenersiscrupolosamente
Problemi,SoluzioniedAlgoritmi 13/60
![Page 14: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/14.jpg)
Algoritmi:EsecutoreeLinguaggio– 3/3• L’esecuzionediunalgoritmodapartediun“esecutore”(uomoomacchina)sitraduceinunasuccessionedioperazioni chevengonoeffettuateneltempo,evocandounprocessosequenziale• Seriedieventicheoccorronounodopol’altro,ognunoconuninizioedunafinebenidentificabile
• Unalgoritmo puòrichiederel’esecuzionedialtrialgoritmiprecedentementespecificatiall’esecutore
Istruzione Istruzione Istruzione Istruzione Istruzione Istruzione
Problemi,SoluzioniedAlgoritmi 14/60
![Page 15: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/15.jpg)
Algoritmi:CaratteristichePrincipali– 1/2• L’algoritmodeveessereformulatoinunnumerofinitodiistruzionie deveterminare, fornendoidatiinoutput,inuntempofinito
• L’algoritmopuòessere• Deterministico: eseguendolostessoalgoritmopiùvoltesuglistessidatidiinput,l’esecutoredevegeneraresempreglistessidatidioutput
• Probabilistico: eseguendolostessoalgoritmopiùvoltesuglistessidatidiinput,l’esecutoredevegeneraredatidioutputsemprediversi
• Noicioccuperemosolodialgoritmideterministici
• Sepossiamospecificareunalgoritmoallorapossiamoautomatizzarelasoluzione
Problemi,SoluzioniedAlgoritmi 15/60
![Page 16: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/16.jpg)
Algoritmi:CaratteristichePrincipali– 2/2• Unalgoritmodevepossedereleseguentiproprietà• Correttezza:produrresempreunasoluzione,apattocheidatiininputsianovalidi• Determinatezza: utilizzareleistruzionidibasefornitedall’esecutore• Efficacia: risolvereilproblematramitelacombinazionediistruzionidibase• Efficienza: risolvereilproblemausandolaminorquantitàpossibiledirisorsefisiche• Tempodiesecuzione,memoria,etc
• Unalgoritmopuòessereespressoinvarieforme• Linguaggiumani,pseudo-codici,linguaggigrafici,linguaggidiprogrammazione,etc
Problemi,SoluzioniedAlgoritmi 16/60
![Page 17: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/17.jpg)
Algoritmi:FasidelProcessodiCreazione
Problemi,SoluzioniedAlgoritmi 17/60
![Page 18: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/18.jpg)
ComeRappresentareunAlgoritmo• Unasoluzionealgoritmicaadunproblema,peressereeseguitadauncalcolatore,deveessererappresentatainmanieraformale• Formale: descrizioneinterminidisequenzadioperazionielementari
• Esistononumerosistrumentiperrappresentareunasoluzioneinmodoformale,ipiùutilizzatisono• Pseudocodici(testuale)• Diagrammidiflusso(grafico)
Problemi,SoluzioniedAlgoritmi 18/60
![Page 19: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/19.jpg)
Pseudocodici• Nellarappresentazionedeglialgoritmiconvieneastrarsidallospecificolinguaggiodiprogrammazione
• Perfarequestosiusaunlinguaggiodettopseudocodice• Nellopseudocodice• Siimpieganometodiespressivipiùchiarieconcisirispettoailinguaggidiprogrammazionereali• Sipossonousarefrasiinlinguaggionaturalepersintetizzareproceduretalvoltacomplesse,manonambigue
Problemi,SoluzioniedAlgoritmi 19/60
![Page 20: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/20.jpg)
Pseudocodici:Esempio1• Rappresentazionemediantepseudocodicediunpossibilealgoritmoperlapreparazionedeltè(N.B.esecutoreumano)
INIZIOALGORITMOpreparareUnaTazzaDiTè1. Collegareilbollitoreallacorrenteelettrica2. Metterelabustinaditèinunatazza3. Metterel’acquanelbollitore4. Accendereilbollitore5. Aspettarel’ebollizionedell’acqua6. Aggiungerel’acquaallatazza7. Rimuoverelabustinaditèconilcucchiaio/forchetta8. Aggiungerelattee/ozucchero9. Servire
FINEALGORITMOpreparareUnaTazzaDiTè
Problemi,SoluzioniedAlgoritmi 20/60
![Page 21: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/21.jpg)
Pseudocodici:Esempio1• Rappresentazionemediantepseudocodicediunpossibilealgoritmoperlapreparazionedeltè(N.B.esecutoreumano)
INIZIOALGORITMOpreparareUnaTazzaDiTè1. Collegareilbollitoreallacorrenteelettrica2. Metterelabustinaditèinunatazza3. Metterel’acquanelbollitore4. Accendereilbollitore5. Aspettarel’ebollizionedell’acqua6. Aggiungerel’acquaallatazza7. Rimuoverelabustinaditèconilcucchiaio/forchetta8. Aggiungerelattee/ozucchero9. Servire
FINEALGORITMOpreparareUnaTazzaDiTè
NotazioneinCamelCase
Problemi,SoluzioniedAlgoritmi 21/60
![Page 22: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/22.jpg)
Pseudocodici:Esempio2• Problema: creareunalgoritmochetrovailpiùgrandeelementodellalistadiinputA contenente10 elementi• Input: A (unalistadi10 numeri)• Output:max (l’elementopiùgrandeinA)
• IlprimoelementodiAèrestituitodaA(1)INIZIOALGORITMOtrovaMaxmax = A(1)Per i che va da 2 a 10
Se A(i) > maxmax = A(i) //Istruzione eseguita se A(i) > max
Incrementa irestituisci maxFINEALGORITMOtrovaMax
Indicei 1 2 3 4 5 6 7 8 9 10
A 32 15 8 5 12 9 63 3 102 1
Problemi,SoluzioniedAlgoritmi 22/60
![Page 23: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/23.jpg)
DiagrammidiFlusso– 1/3• Perrealizzareunalgoritmoènecessario• Individuareidati iningresso edinuscita• Individuareunprocedimentoadeguato• Scomporreilprocedimentoinunasequenza diazionielementari enonambigue
• Permeglioaffrontarel’ultimopuntosifaspessoricorsoaidiagrammidiflusso (oflow-chart)• Strumentigrafici perrappresentare ilflussologico dioperazioni cheportanoallarisoluzione diunproblema
• Costituisconounlinguaggiomoltoutileperdescrivere glialgoritmi
Problemi,SoluzioniedAlgoritmi 23/60
![Page 24: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/24.jpg)
DiagrammidiFlusso– 2/3• Ilflusso diesecuzione puòessererappresentatograficamente conundiagrammadiflusso• Sisviluppagraficamentesuduedimensioni• Sibasasupochisimboli• Èunlinguaggiouniversale• Elimina leambiguità
Problemi,SoluzioniedAlgoritmi 24/60
![Page 25: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/25.jpg)
DiagrammidiFlusso– 3/3• Undiagrammadiflussoècompostoda• Blocchielementari• Descrivonoazioniedecisioni
• Archiorientati• Colleganoivariblocchiedescrivonolasequenzadisvolgimentodelleazioni
• Iblocchielementarisono• BloccodiInizio• BloccodiFine• BloccodiConnessione• BloccodiAzioneGenerica• BloccodiAzionediI/O• BloccodiDecisioneBinaria (dettaancheCondizionale oppureADueVie)
Problemi,SoluzioniedAlgoritmi 25/60
![Page 26: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/26.jpg)
DiagrammidiFlusso:BlocchidiInizioeFine• Unalgoritmo(ediconseguenzaunasuarappresentazionegrafica)deveavereuninizio edunafine
• Tral’inizioelafinecidevesempreesserealmenoun’istruzione
Inizio
Fine
Problemi,SoluzioniedAlgoritmi 26/60
![Page 27: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/27.jpg)
DiagrammidiFlusso:BloccodiConnessione• Larisoluzionediunproblemaconsistenell’esecuzioneordinatadiunasequenzadioperazioni• L’ordine nell’esecuzione delleistruzionièfondamentale• Neiflow-chartègarantitodall’orientamento dellefrecce checolleganoiblocchi
Problemi,SoluzioniedAlgoritmi 27/60
![Page 28: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/28.jpg)
DiagrammidiFlusso:BlocchidiAzioneGenericaedI/O
Azionegenerica
AzionediI/O
Problemi,SoluzioniedAlgoritmi 28/60
![Page 29: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/29.jpg)
DiagrammidiFlusso:BloccodiDecisioneBinaria(oCondizionale)• Possonoesserepresentiistruzionicondizionali,lacuiesecuzionedipendecioèdascelteeffettuateinbaseaidati
• Concettualmente,possiamoimmaginarecheilflussodiesecuzionesiramifichi• Inbaseadunacondizione vienedecisoseeseguireun’operazioneoppureun’altra
?
Diramazione(condizionale)
Problemi,SoluzioniedAlgoritmi 29/60
![Page 30: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/30.jpg)
EsempioStart
A>=0?
LeggiunvaloreA
Stop Stop
StampaA Stampa-A
si no
Problemi,SoluzioniedAlgoritmi 30/60
![Page 31: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/31.jpg)
RappresentazioneAlternativadeiBlocchiElementari
START
Inizio
END
Fine
I/O
Operazioni di ingresso/
usc i ta
PROCESS
Elaborazione
Predicato
Se lez ione a due vie
Sì NoSUB-PROCESS
Sottoprogramma
Problemi,SoluzioniedAlgoritmi 31/60
![Page 32: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/32.jpg)
Pseudocodicevs.DiagrammidiFlusso• Pseudocodice• Vantaggi• Immediato
• Svantaggi• Menoastratto• Interpretazionepiùcomplicata
• Diagrammidiflusso• Vantaggi• Piùintuitiviperchégrafici• Piùastratti
• Svantaggi• Richiedonoapprendimentodellafunzionedeivaritipidiblocco
Problemi,SoluzioniedAlgoritmi 32/60
![Page 33: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/33.jpg)
StrutturediControllo:Controllarel’OrdinedelleIstruzioni– 1/4
SELEZIONESEMPLICE
Problemi,SoluzioniedAlgoritmi 33/60
![Page 34: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/34.jpg)
StrutturediControllo:Controllarel’OrdinedelleIstruzioni– 2/4
SELEZIONEADUEVIE
Problemi,SoluzioniedAlgoritmi 34/60
![Page 35: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/35.jpg)
StrutturediControllo:Controllarel’OrdinedelleIstruzioni– 3/4
CICLOACONDIZIONEINIZIALE
Problemi,SoluzioniedAlgoritmi 35/60
![Page 36: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/36.jpg)
StrutturediControllo:Controllarel’OrdinedelleIstruzioni– 4/4
CICLOACONDIZIONEFINALE
Problemi,SoluzioniedAlgoritmi 36/60
![Page 37: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/37.jpg)
ALGORITMOPERLASOMMADIN NUMERI
Problemi,SoluzioniedAlgoritmi 37/60
![Page 38: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/38.jpg)
ALGORITMOPERPREPARARELAFRITTATA
Problemi,SoluzioniedAlgoritmi 38/60
![Page 39: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/39.jpg)
ALGORITMOPERLAMEDIASUN NUMERI
Problemi,SoluzioniedAlgoritmi 39/60
![Page 40: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/40.jpg)
AlgoritmoPOW:BaseBelevataall’esponenteE
b e ris = ris * b e > 02 4 1
4 > 0 (SI) 2 3 2
3 > 0 (SI)2 2 4
2 > 0 (SI)2 1 8
1 > 0 (SI)2 0 16
0 > 0 (NO)
Problemi,SoluzioniedAlgoritmi 40/60
![Page 41: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/41.jpg)
Esempio:Algoritmopercalcolareilmassimotra2numerix ey1. Leggiilvaloredix dall’esterno
2. Leggiilvalorediy dall’esterno
3. Calcolaladifferenzad frax ey(d=x-y)
4. Sedèmaggioredi0 vaialpasso6., altrimentiproseguiinsequenza
5. Stampa“ilmassimoè…”seguitodalvalorediy evaia7.
6. Stampa“ilmassimoè…”seguitodalvaloredix
7. Terminal’esecuzione
=
Problemi,SoluzioniedAlgoritmi 41/60
![Page 42: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/42.jpg)
AlgoritmieProgrammi• Algoritmo: sequenzadiazionipersvolgereilcalcolo
• Programma: algoritmoespressoinnotazioneformale(linguaggiodiprogrammazione)
• CreazioneProgramma• Fase1 =Algoritmo• Fase2 =Implementazionedell’algoritmoinundatolinguaggio(diprogrammazione)
Problemi,SoluzioniedAlgoritmi 42/60
![Page 43: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/43.jpg)
ProcessoperlaCreazionediunAlgoritmo– 1/5• Talvoltailprocessoperlarisoluzionediunproblemaèfisso• Semprelostessoadognidiversaesecuzione
• Esempio: algoritmopercalcolarel’importodiunafattura1. Cercal’aliquotaIVAsullatabella2. Moltiplical’importonettoperl’aliquotatrovata3. Sommailrisultatoall'importonetto
• Questoalgoritmoècompostodatreistruzioni• Chedevonoessereeseguiteinsequenza
Problemi,SoluzioniedAlgoritmi 43/60
![Page 44: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/44.jpg)
ProcessoperlaCreazionediunAlgoritmo– 2/5• Altrevoltelostessoalgoritmopuòportareapiùprocessisequenzialidifferenti• Asecondadellecondizioniiniziali
• Esempio: ilprecedentealgoritmo,quandoèrichiestodidoverconsiderarelapossibilitàchelamerceinesamenonsiasoggettaadIVA,diventa
• SE lamercedafatturareèsoggettaadIVA ALLORA1. CercalacorrettaaliquotaIVAsullatabella2. Moltiplical’importoperl’aliquotatrovata3. Sommailrisultatoall’importonetto• ALTRIMENTI4. Tienicontosolodell’importodipartenza
Problemi,SoluzioniedAlgoritmi 44/60
![Page 45: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/45.jpg)
ProcessoperlaCreazionediunAlgoritmo– 3/5• Osservazione: nell’esempiovistoinprecedenza,ilprocessosequenzialenonèfissomadipendedaidatidaelaborare,inparticolaredaltipodimercedafatturare• L’algoritmodescriveuninsiemecostituitodaduesequenzediesecuzionediverse
Problemi,SoluzioniedAlgoritmi 45/60
![Page 46: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/46.jpg)
ProcessoperlaCreazionediunAlgoritmo– 4/5• Esempio: algoritmopereffettuareunatelefonata
1. Sollevailricevitore2. Componiilnumero3. SE qualcunorisponde ALLORA
• Conducilaconversazione4. ALTRIMENTI
• Deponiilricevitoree• Ripetil’interoprocedimento,apartiredalpunto1.
Problemi,SoluzioniedAlgoritmi 46/60
![Page 47: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/47.jpg)
ProcessoperlaCreazionediunAlgoritmo– 5/5• Unalgoritmo puòesserevistocomeuntestoingradodidescrivere uninsiemedisequenzediesecuzione
• L’algoritmopereffettuareunatelefonatapotrebbeavereunprocessociclicochenonterminamai• L’interlocutorenonrispondemaialtelefono
Problemi,SoluzioniedAlgoritmi 47/60
![Page 48: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/48.jpg)
Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 1/5• 7 * 3 =21• 7 èdettomoltiplicando• 3 èdettomoltiplicatore
• UtilizzandoilmetododelleAddizioniSuccessive,lamoltiplicazionepuòessereespressacome• 7 + 7 + 7 =21
• L’algoritmopotrebbeesserecostituitosemplicementedalseguentetesto• “Sisommiilmoltiplicandoasestessounnumerodivolteugualealvaloredelmoltiplicatore”
Problemi,SoluzioniedAlgoritmi 48/60
![Page 49: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/49.jpg)
Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 2/5• Specifichiamoconmaggioredettaglio leoperazionirichiesteevitandoicostruttiambigui
• Adesempiopotremmoscrivere1. Sisommiilmoltiplicando asestesso,esidecrementidiunoilvaloredel
moltiplicatore2. Sisommiancorailmoltiplicando alvalore ottenutodallaprecedente
somma,esidecrementidinuovoilvalore ottenutodallaprecedentesottrazione
3. Siripetailprocedimentofinoache,perdecrementisuccessivi,ilmoltiplicatore nonraggiungailvalorezero
Problemi,SoluzioniedAlgoritmi 49/60
![Page 50: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/50.jpg)
Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 3/5
1. 7+ 0 = 7(Val.prec.somma) 3 – 1 = 2(Val.prec.sottrazione)
2. 7 + 7 = 14(Val.prec.somma) 2 – 1 = 1 (Val.prec.sottrazione)
3. 7 +14=211 – 1 = 0 (Val.prec.sottrazione)
Problemi,SoluzioniedAlgoritmi
Sequenzadioperazionieffettuatesulmoltiplicando
Sequenzadioperazionieffettuatesulmoltiplicatore
50/60
![Page 51: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/51.jpg)
Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 4/5• Osservazione: perevitareambiguitàespecificaredivoltainvoltadiqualevaloresistaparlando,sièstaticostrettiadusareleespressioni• “valoreottenutodallaprecedentesomma”• “valoreottenutodallaprecedentesottrazione”
• Perdistingueretalivalorisiricorreasimbolioidentificatori(dettivariabili)perriferirsisenzaambiguità,divoltainvolta,alvaloredesiderato
Problemi,SoluzioniedAlgoritmi 51/60
![Page 52: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/52.jpg)
Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 5/5• Algoritmo1. SiaM ilvaloredelmoltiplicando,N ilvaloredelmoltiplicatoreed
M1 ilrisultato(inizialmenteugualeazero)2. SiripetanoleseguentioperazionifinoacheilvalorediN non
diventiugualea0• SisommiilvaloredelmoltiplicandoM alvalorediM1 esichiamiilrisultatoancoraM1
• Sisottragga1dalvalorediN,esichiamiilrisultatoancoraN3. AllafineilvalorediM1 èilrisultatocercato
• IsimboliM,N eM1 sonodettiidentificatoridivariabili
•M1 èdettoaccumulatoredirisultato
Problemi,SoluzioniedAlgoritmi 52/60
![Page 53: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/53.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 1/6• Ilibrisonodispostisugliscaffali
• Laposizionediognilibroèfissaedèindividuatadaduecoordinate• Scaffale(numerodelloscaffale)• Posizionenelloscaffale
• Labibliotecaèdotatadiunoschedario(ordinatoperautore/ietitolo),doveognischedacontienenell’ordine• Cognomeenomedell’autore• Titolodellibro• Edizioneedatadipubblicazione• Numerodelloscaffaleincuisitrova• Posizioneattribuitaallibronelloscaffale
Problemi,SoluzioniedAlgoritmi 53/60
![Page 54: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/54.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 2/6
Autore: Sciuto Donatella,Buonanno Giacomo,MariLuca
Titolo: IntroduzioneaiSistemiInformatici
Edizioneedatadipubblicazione: IIIEdizione,2005
Scaffale: 42
Posizione: 81
Esempiodischeda
Problemi,SoluzioniedAlgoritmi 54/60
![Page 55: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/55.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 3/6• Primaformulazionedell’algoritmo1. Decidiillibrodarichiedere2. Prelevaillibrorichiesto
• Osservazione: seunpassononèdirettamentecomprensibileedeseguibiledall’esecutore(operazionesemplice)alloraoccorredettagliarloasuavoltamedianteunulteriorealgoritmo
Problemi,SoluzioniedAlgoritmi 55/60
![Page 56: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/56.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 4/6• AlgoritmoperilPrelievo1. Decidiillibrodarichiedere2. Cercalaschedadellibrorichiesto3. Segnatinumeroscaffaleeposizione4. Cercaloscaffaleindicato5. Accediallaposizioneindicataeprelevaillibro6. Scriviituoidatisulla“schedaprestito”
Problemi,SoluzioniedAlgoritmi 56/60
![Page 57: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/57.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 5/6• Ilsotto-algoritmodiricerca
1. Prendilaprimascheda2. Esaminasetitoloeautore/isonoquellicercati.Incasopositivolaricerca
terminaconsuccesso,altrimentipassaallaschedasuccessivaeripeti3. Seesauriscileschedealloraillibrocercatononesiste
Problemi,SoluzioniedAlgoritmi 57/60
![Page 58: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/58.jpg)
Esempio:ConsultazioneLibroinBiblioteca– 6/6• AlgoritmoperilPrelievo
1. Decidiillibrodarichiedere2. Cercalaschedadellibrorichiestocomesegue1. Prendilaprimascheda2. Esaminasetitoloeautore/isonoquellicercati.Incasopositivolaricerca
terminaconsuccesso,altrimentipassaallaschedasuccessivaeripeti3. Seesauriscileschedealloraillibrocercatononesiste
3. Segnatinumeroscaffaleeposizione4. Cercaloscaffaleindicato5. Accediallaposizioneindicataeprelevaillibro6. Scriviituoidatisulla“schedaprestito”
Problemi,SoluzioniedAlgoritmi 58/60
![Page 59: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/59.jpg)
Esercizi• Perchénell’esempioperilcalcolodelmassimoinunalistadi10elementinonèstatopostomax=0?
• Comegeneralizzarelaproceduraperlistedilunghezzan?
• Cometrovarel’elementominimoinA?
• Cometrovarelaposizionedelpiùgrandeelemento?
Problemi,SoluzioniedAlgoritmi 59/60
![Page 60: Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore •Un esecutore può eseguire un algoritmo](https://reader033.vdocumenti.com/reader033/viewer/2022052719/5f07d83f7e708231d41f09b1/html5/thumbnails/60.jpg)
Riferimenti• Libroditesto• Capitolo3• Paragrafi1,2,3,5
Problemi,SoluzioniedAlgoritmi 60/60