Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in...

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

ComeInstruire i Calcolatori aRisolvere Problemi• Glielaboratorisonostrumentiperrisolvere(oaiutarearisolvere)problemibasatisuinformazioniedati

•Macomeciòavviene?1. Abbiamobisognodicodificareopportunamenteinformazioniedati2. Abbiamobisognodiimpartirelegiusteistruzioniperrisolvere

correttamenteiproblemi

Problemi,SoluzioniedAlgoritmi 02/60

RelazionetraRealtàeModello:ComeModellareunProblema

Modello

F = m × a

re tf

ft 1213

tt 1415

Costruzione modello

Ricerca dellasoluzione

Interpretazionedella soluzione

Mondo Reale


RisolvereunProblema

Risolvere unProblema

1.Scegliereastrazione definendouninsiemedidatirilevantichecaratterizzanolarealtà

2.Scegliererappresentazione dei dati

3.Individuareunprocedimentoadeguato(Algoritmo epoiProgramma)

4.Scomporreeventualmenteilprocedimento insotto-procedimenti


IlTermineAlgoritmo:Etimologia• DerivadalmatematicoAraboMuḥammad ibn Mūsā al-Khwārizmī (c.780-850),autoredeltestoAl-jabrw’al-muqabâla (dacuiancheiltermineAlgebra)


Algoritmi:unpo’diStoria• Algoritmiditiponumericofuronostudiatidamatematicibabilonesieindianipiùdi3000annifa

• Algoritmiinusofinoatempirecentifuronostudiatidaimatematicigrecinel500a.C.• AlgoritmodiEuclide perilMassimoComunDivisore• Algoritmigeometrici(calcoloditangenti,sezionidiangoli,etc)• Etc


GliAlgoritminelTrattamentodell’Informazione– 1/3• Unalgoritmoconsentedirealizzareunparticolaretrattamentodell’informazioneopiùingeneraledirisolvereunospecificoproblema• Calcolarelasommadiduenumeri• Calcolarelalunghezzadell’ipotenusadiuntriangolorettangolo• Risolvereun’equazionedisecondogrado• Maanche…


GliAlgoritminelTrattamentodell’Informazione– 2/3• TrasmissionedatiinInternet• Comesigestisceinpraticailflussodidatinellarete?• RicercanelWEB• ComefaGoogleatrovareleinformazioninelWEB?• Bioinformatica• ComeilDNAdeterminalenostrecaratteristiche?• Processieconomici• Comesigestisconoleasteon-linesuEbay?• ComesieffettualacompravenditadiazionisuInternet?• Organizzazionedirisorseeservizi• Comesischedulanoivolidelleaerolinee?• Comesiassegnanolefrequenzenellecelledellereticellulari?• Etc


GliAlgoritminelTrattamentodell’Informazione– 3/3• L’esperienzaquotidianasuggerisceinfinitiesempidialgoritmi

•Molteazionichesvolgiamoabitualmentepossonoesseremodellatemediantealgoritmi• Istruzionidimontaggio• Preparazionedelcaffè• Prelievobancomat• Preparazionediunricetta• Indicazioniperunlavoroamaglia• Etc


Algoritmo:Definizioni• Definizione1: proceduradicalcolobendefinita,cheprendeuninsiemedivaloricomeinputeproduceuninsiemedivaloricomeoutput

• Definizione2: sequenzadiazionielementaricheconsenteditrasformareidatiinizialineirisultatifinaliattraversounnumerofinitodipassinonambigui

• Note• Insiemedidatiinizialibendefinito• Sequenzadipassipuòessereeseguitadaunesecutore(ades.calcolatore)

ALGORITMODati iniziali Dati finali (soluzione)


Esempio:Algoritmoperprenderel’Automobile• Algoritmo

1. Aprirel’auto2. Aprirelaportiera3. Sedersialpostodiguida4. Allacciarelacintura5. Schiacciarelafrizione6. Avviareilmotore7. Inserirelaprimamarcia8. Togliereilfrenoamano9. Rilasciare“delicatamente”lafrizioneperpartire

Osservazione: ipassisonoeseguitiinsequenzael’ordinedelleistruzionièessenzialeperlacorrettezza


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


Algoritmi:EsecutoreeLinguaggio– 2/3• L’algoritmodeve• Prevederesoltantoistruzionicherichiedonoall’esecutoredieffettuareoperazionielementari• Operazionicheeglisacompieresenzabisognodiulteriorispecificazioni

• Essereformulato in unlinguaggiononambiguo,incuicioèogniistruzionecaratterizziunivocamenteunadelleoperazionichel’esecutoreèingradodicompiere

• Specificaresenzaambiguitàl’ordinediesecuzione delleistruzioni,cuil’esecutoredeveattenersiscrupolosamente


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


Algoritmi:CaratteristichePrincipali– 1/2• L’algoritmodeveessereformulatoinunnumerofinitodiistruzionie deveterminare, fornendoidatiinoutput,inuntempofinito

• L’algoritmopuòessere• Deterministico: eseguendolostessoalgoritmopiùvoltesuglistessidatidiinput,l’esecutoredevegeneraresempreglistessidatidioutput

• Probabilistico: eseguendolostessoalgoritmopiùvoltesuglistessidatidiinput,l’esecutoredevegeneraredatidioutputsemprediversi

• Noicioccuperemosolodialgoritmideterministici

• Sepossiamospecificareunalgoritmoallorapossiamoautomatizzarelasoluzione


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


Algoritmi:FasidelProcessodiCreazione


ComeRappresentareunAlgoritmo• Unasoluzionealgoritmicaadunproblema,peressereeseguitadauncalcolatore,deveessererappresentatainmanieraformale• Formale: descrizioneinterminidisequenzadioperazionielementari

• Esistononumerosistrumentiperrappresentareunasoluzioneinmodoformale,ipiùutilizzatisono• Pseudocodici(testuale)• Diagrammidiflusso(grafico)


Pseudocodici• Nellarappresentazionedeglialgoritmiconvieneastrarsidallospecificolinguaggiodiprogrammazione

• Perfarequestosiusaunlinguaggiodettopseudocodice• Nellopseudocodice• Siimpieganometodiespressivipiùchiarieconcisirispettoailinguaggidiprogrammazionereali• Sipossonousarefrasiinlinguaggionaturalepersintetizzareproceduretalvoltacomplesse,manonambigue


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è


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


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


DiagrammidiFlusso– 1/3• Perrealizzareunalgoritmoènecessario• Individuareidati iningresso edinuscita• Individuareunprocedimentoadeguato• Scomporreilprocedimentoinunasequenza diazionielementari enonambigue

• Permeglioaffrontarel’ultimopuntosifaspessoricorsoaidiagrammidiflusso (oflow-chart)• Strumentigrafici perrappresentare ilflussologico dioperazioni cheportanoallarisoluzione diunproblema

• Costituisconounlinguaggiomoltoutileperdescrivere glialgoritmi


DiagrammidiFlusso– 2/3• Ilflusso diesecuzione puòessererappresentatograficamente conundiagrammadiflusso• Sisviluppagraficamentesuduedimensioni• Sibasasupochisimboli• Èunlinguaggiouniversale• Elimina leambiguità


DiagrammidiFlusso– 3/3• Undiagrammadiflussoècompostoda• Blocchielementari• Descrivonoazioniedecisioni

• Archiorientati• Colleganoivariblocchiedescrivonolasequenzadisvolgimentodelleazioni

• Iblocchielementarisono• BloccodiInizio• BloccodiFine• BloccodiConnessione• BloccodiAzioneGenerica• BloccodiAzionediI/O• BloccodiDecisioneBinaria (dettaancheCondizionale oppureADueVie)


DiagrammidiFlusso:BlocchidiInizioeFine• Unalgoritmo(ediconseguenzaunasuarappresentazionegrafica)deveavereuninizio edunafine

• Tral’inizioelafinecidevesempreesserealmenoun’istruzione

Inizio

Fine


DiagrammidiFlusso:BloccodiConnessione• Larisoluzionediunproblemaconsistenell’esecuzioneordinatadiunasequenzadioperazioni• L’ordine nell’esecuzione delleistruzionièfondamentale• Neiflow-chartègarantitodall’orientamento dellefrecce checolleganoiblocchi


DiagrammidiFlusso:BlocchidiAzioneGenericaedI/O

Azionegenerica

AzionediI/O


DiagrammidiFlusso:BloccodiDecisioneBinaria(oCondizionale)• Possonoesserepresentiistruzionicondizionali,lacuiesecuzionedipendecioèdascelteeffettuateinbaseaidati

• Concettualmente,possiamoimmaginarecheilflussodiesecuzionesiramifichi• Inbaseadunacondizione vienedecisoseeseguireun’operazioneoppureun’altra

?

Diramazione(condizionale)


EsempioStart

A>=0?

LeggiunvaloreA

Stop Stop

StampaA Stampa-A

si no


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


Pseudocodicevs.DiagrammidiFlusso• Pseudocodice• Vantaggi• Immediato

• Svantaggi• Menoastratto• Interpretazionepiùcomplicata

• Diagrammidiflusso• Vantaggi• Piùintuitiviperchégrafici• Piùastratti

• Svantaggi• Richiedonoapprendimentodellafunzionedeivaritipidiblocco


StrutturediControllo:Controllarel’OrdinedelleIstruzioni– 1/4

SELEZIONESEMPLICE



SELEZIONEADUEVIE



CICLOACONDIZIONEINIZIALE



CICLOACONDIZIONEFINALE


ALGORITMOPERLASOMMADIN NUMERI


ALGORITMOPERPREPARARELAFRITTATA


ALGORITMOPERLAMEDIASUN NUMERI


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)


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

=


AlgoritmieProgrammi• Algoritmo: sequenzadiazionipersvolgereilcalcolo

• Programma: algoritmoespressoinnotazioneformale(linguaggiodiprogrammazione)

• CreazioneProgramma• Fase1 =Algoritmo• Fase2 =Implementazionedell’algoritmoinundatolinguaggio(diprogrammazione)


ProcessoperlaCreazionediunAlgoritmo– 1/5• Talvoltailprocessoperlarisoluzionediunproblemaèfisso• Semprelostessoadognidiversaesecuzione

• Esempio: algoritmopercalcolarel’importodiunafattura1. Cercal’aliquotaIVAsullatabella2. Moltiplical’importonettoperl’aliquotatrovata3. Sommailrisultatoall'importonetto

• Questoalgoritmoècompostodatreistruzioni• Chedevonoessereeseguiteinsequenza


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


ProcessoperlaCreazionediunAlgoritmo– 3/5• Osservazione: nell’esempiovistoinprecedenza,ilprocessosequenzialenonèfissomadipendedaidatidaelaborare,inparticolaredaltipodimercedafatturare• L’algoritmodescriveuninsiemecostituitodaduesequenzediesecuzionediverse


ProcessoperlaCreazionediunAlgoritmo– 4/5• Esempio: algoritmopereffettuareunatelefonata

1. Sollevailricevitore2. Componiilnumero3. SE qualcunorisponde ALLORA

• Conducilaconversazione4. ALTRIMENTI

• Deponiilricevitoree• Ripetil’interoprocedimento,apartiredalpunto1.


ProcessoperlaCreazionediunAlgoritmo– 5/5• Unalgoritmo puòesserevistocomeuntestoingradodidescrivere uninsiemedisequenzediesecuzione

• L’algoritmopereffettuareunatelefonatapotrebbeavereunprocessociclicochenonterminamai• L’interlocutorenonrispondemaialtelefono


Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 1/5• 7 * 3 =21• 7 èdettomoltiplicando• 3 èdettomoltiplicatore

• UtilizzandoilmetododelleAddizioniSuccessive,lamoltiplicazionepuòessereespressacome• 7 + 7 + 7 =21

• L’algoritmopotrebbeesserecostituitosemplicementedalseguentetesto• “Sisommiilmoltiplicandoasestessounnumerodivolteugualealvaloredelmoltiplicatore”


Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 2/5• Specifichiamoconmaggioredettaglio leoperazionirichiesteevitandoicostruttiambigui

• Adesempiopotremmoscrivere1. Sisommiilmoltiplicando asestesso,esidecrementidiunoilvaloredel

moltiplicatore2. Sisommiancorailmoltiplicando alvalore ottenutodallaprecedente

somma,esidecrementidinuovoilvalore ottenutodallaprecedentesottrazione

3. Siripetailprocedimentofinoache,perdecrementisuccessivi,ilmoltiplicatore nonraggiungailvalorezero


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

Esempio:ProdottodidueNumerimedianteAddizioniSuccessive– 4/5• Osservazione: perevitareambiguitàespecificaredivoltainvoltadiqualevaloresistaparlando,sièstaticostrettiadusareleespressioni• “valoreottenutodallaprecedentesomma”• “valoreottenutodallaprecedentesottrazione”

• Perdistingueretalivalorisiricorreasimbolioidentificatori(dettivariabili)perriferirsisenzaambiguità,divoltainvolta,alvaloredesiderato


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


Esempio:ConsultazioneLibroinBiblioteca– 1/6• Ilibrisonodispostisugliscaffali

• Laposizionediognilibroèfissaedèindividuatadaduecoordinate• Scaffale(numerodelloscaffale)• Posizionenelloscaffale

• Labibliotecaèdotatadiunoschedario(ordinatoperautore/ietitolo),doveognischedacontienenell’ordine• Cognomeenomedell’autore• Titolodellibro• Edizioneedatadipubblicazione• Numerodelloscaffaleincuisitrova• Posizioneattribuitaallibronelloscaffale


Esempio:ConsultazioneLibroinBiblioteca– 2/6

Autore: Sciuto Donatella,Buonanno Giacomo,MariLuca

Titolo: IntroduzioneaiSistemiInformatici

Edizioneedatadipubblicazione: IIIEdizione,2005

Scaffale: 42

Posizione: 81

Esempiodischeda


Esempio:ConsultazioneLibroinBiblioteca– 3/6• Primaformulazionedell’algoritmo1. Decidiillibrodarichiedere2. Prelevaillibrorichiesto

• Osservazione: seunpassononèdirettamentecomprensibileedeseguibiledall’esecutore(operazionesemplice)alloraoccorredettagliarloasuavoltamedianteunulteriorealgoritmo


Esempio:ConsultazioneLibroinBiblioteca– 4/6• AlgoritmoperilPrelievo1. Decidiillibrodarichiedere2. Cercalaschedadellibrorichiesto3. Segnatinumeroscaffaleeposizione4. Cercaloscaffaleindicato5. Accediallaposizioneindicataeprelevaillibro6. Scriviituoidatisulla“schedaprestito”


Esempio:ConsultazioneLibroinBiblioteca– 5/6• Ilsotto-algoritmodiricerca

1. Prendilaprimascheda2. Esaminasetitoloeautore/isonoquellicercati.Incasopositivolaricerca

terminaconsuccesso,altrimentipassaallaschedasuccessivaeripeti3. Seesauriscileschedealloraillibrocercatononesiste


Esempio:ConsultazioneLibroinBiblioteca– 6/6• AlgoritmoperilPrelievo

1. Decidiillibrodarichiedere2. Cercalaschedadellibrorichiestocomesegue1. Prendilaprimascheda2. Esaminasetitoloeautore/isonoquellicercati.Incasopositivolaricerca

terminaconsuccesso,altrimentipassaallaschedasuccessivaeripeti3. Seesauriscileschedealloraillibrocercatononesiste

3. Segnatinumeroscaffaleeposizione4. Cercaloscaffaleindicato5. Accediallaposizioneindicataeprelevaillibro6. Scriviituoidatisulla“schedaprestito”


Esercizi• Perchénell’esempioperilcalcolodelmassimoinunalistadi10elementinonèstatopostomax=0?

• Comegeneralizzarelaproceduraperlistedilunghezzan?

• Cometrovarel’elementominimoinA?

• Cometrovarelaposizionedelpiùgrandeelemento?


Riferimenti• Libroditesto• Capitolo3• Paragrafi1,2,3,5


Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in...

Documents

Transcript of Problemi, Soluzioni ed Algoritmi · •Per essere eseguito, l’algoritmo deve essere formulato in...