Algoritmi, Dati e Programmi - disi.unige.it · Tali strutture sono dette strutture di ... tutte le...

Walter Cazzola Algoritmi, Dati e Programmi 1

Walter Walter CazzolaCazzolaDipartimentoDipartimento didi InformaticaInformatica e e ComunicazioneComunicazioneUniversitUniversità degli Studi di Milano.à degli Studi di Milano.

ee--mail: mail: [email protected]@dico.unimi.it

Laboratorio di Informatica (Chimica)Laboratorio di Informatica (Chimica)

AlgoritmiAlgoritmi, , DatiDati e e ProgrammiProgrammi..


Algoritmi, Dati e Programmi Algoritmi, Dati e Programmi

Introduzione ai concetti di:Introduzione ai concetti di:–– Algoritmo;Algoritmo;–– Programma;Programma;–– Dato; Dato; –– Diagramma di flusso;Diagramma di flusso;–– Linguaggio di programmazione.Linguaggio di programmazione.


Algoritmi, Dati e Programmi: Nozioni Algoritmi, Dati e Programmi: Nozioni

AlgoritmoAlgoritmo = Successione di operazioni elementari che = Successione di operazioni elementari che possono essere eseguite da un calcolatore.possono essere eseguite da un calcolatore.

DatoDato = informazione da elaborare rappresentata in un = informazione da elaborare rappresentata in un formato che consenta al programma di operare su di essa.formato che consenta al programma di operare su di essa.ProgrammaProgramma = algoritmo in un linguaggio “comprensibile” dal = algoritmo in un linguaggio “comprensibile” dal computer.computer.

Linguaggio macchinaLinguaggio macchina = Basato sul set di istruzioni della = Basato sul set di istruzioni della macchina, rappresentato da sequenze di 0 e 1.macchina, rappresentato da sequenze di 0 e 1.

Linguaggio ad alto livelloLinguaggio ad alto livello = Linguaggio più vicino al linguaggio = Linguaggio più vicino al linguaggio naturale, rigoroso e non ambiguo.naturale, rigoroso e non ambiguo.


Elaborazione dell’InformazioneElaborazione dell’Informazione

Ogni problema legato all’elaborazione di informazioni Ogni problema legato all’elaborazione di informazioni è caratterizzato da:è caratterizzato da:–– un insieme di dati di partenza, edun insieme di dati di partenza, ed–– un risultato cercato.un risultato cercato.

Ogni sua soluzione è:Ogni sua soluzione è:–– una procedura che genera il risultato cercato a una procedura che genera il risultato cercato a

partire dall’insieme dei dati di partenza partire dall’insieme dei dati di partenza specificati.specificati.



Distinguiamo tra:Distinguiamo tra:–– conoscenza di come si risolve un problema:conoscenza di come si risolve un problema:

analisi del problema;analisi del problema;identificazione di una soluzione; eidentificazione di una soluzione; edescrizione della soluzionedescrizione della soluzione

–– ed effettiva capacità di risolvere un problema:ed effettiva capacità di risolvere un problema:interpretazione della soluzione; einterpretazione della soluzione; eattuazione della soluzioneattuazione della soluzione

La conoscenza di come si risolve un problema è ciò La conoscenza di come si risolve un problema è ciò che ci permette di sviluppare un programma.che ci permette di sviluppare un programma.



Il programma sarà poi interpretato ed eseguito da un Il programma sarà poi interpretato ed eseguito da un esecutore (es. calcolatore).esecutore (es. calcolatore).

Un esecutore è caratterizzato da:Un esecutore è caratterizzato da:–– il linguaggio che è in grado di interpretare;il linguaggio che è in grado di interpretare;–– l’insieme di azioni che è in grado di compiere; el’insieme di azioni che è in grado di compiere; e–– l’insieme delle regole che ad ogni costrutto linguistico l’insieme delle regole che ad ogni costrutto linguistico

sintatticamente corretto associano le relative azioni da sintatticamente corretto associano le relative azioni da compiere.compiere.



Per la descrizione della soluzione si utilizza:Per la descrizione della soluzione si utilizza:–– linguaggio naturale (ad es. italiano, inglese, …): ambiguo;linguaggio naturale (ad es. italiano, inglese, …): ambiguo;–– linguaggio formale (non ambiguo):linguaggio formale (non ambiguo):

formalismo matematico;formalismo matematico;pseudopseudo--codicecodice;;diagramma di flusso; ediagramma di flusso; elinguaggio di programmazione.linguaggio di programmazione.

La descrizione rigorosa di un metodo che consente di La descrizione rigorosa di un metodo che consente di ottenere un risultato attraverso passi elementari si ottenere un risultato attraverso passi elementari si chiama chiama algoritmo.algoritmo.


Processo di sviluppo di un programma:Processo di sviluppo di un programma:–– analisianalisi del problema e del problema e identificazioneidentificazione di una di una

soluzione;soluzione;–– formalizzazioneformalizzazione della soluzione e definizione della soluzione e definizione

dell’dell’algoritmoalgoritmo risolutivo;risolutivo;–– programmazioneprogrammazione in un linguaggio di programmazione in un linguaggio di programmazione

“ad alto livello”; e“ad alto livello”; e–– traduzionetraduzione in linguaggio macchinain linguaggio macchina



AlgoritmoAlgoritmo

Un Un algoritmoalgoritmo è un insieme finito ed ordinato di passi che è un insieme finito ed ordinato di passi che determinano un procedimento atto a risolvere in un determinano un procedimento atto a risolvere in un tempo finito un problema utilizzando i dati iniziali ed tempo finito un problema utilizzando i dati iniziali ed ottenendo dei risultati.ottenendo dei risultati.

Esempi:Esempi:Algoritmi per eseguire le 4 operazioni che ci sono stati Algoritmi per eseguire le 4 operazioni che ci sono stati

insegnati alle elementariinsegnati alle elementari–– Espressi in un linguaggio adatto ai bambiniEspressi in un linguaggio adatto ai bambini

Ricette di cucinaRicette di cucina–– Espresse nel linguaggio dei libri di cucinaEspresse nel linguaggio dei libri di cucina


Algoritmo: EsempioAlgoritmo: Esempio

1.1. Accendere lo schermo se è spento;Accendere lo schermo se è spento;2.2. Scrivere il proprio <Scrivere il proprio <usernameusername> nella riga in cui compare la > nella riga in cui compare la

scritta scritta loginlogin::3.3. Scrivere la propria <password> nella riga in cui compare la Scrivere la propria <password> nella riga in cui compare la

scritta password;scritta password;4.4. Se il sistema risponde con la frase: «utente non abilitato» Se il sistema risponde con la frase: «utente non abilitato»

ritornare al punto 2. e riprovare;ritornare al punto 2. e riprovare;5.5. Se il sistema continua a rispondere con la frase: «utente Se il sistema continua a rispondere con la frase: «utente

non abilitato» allora chiamare il non abilitato» allora chiamare il tutortutor..

Esempio:Esempio: Algoritmo per accedere al proprio account sul Algoritmo per accedere al proprio account sul computer del laboratorio: computer del laboratorio:


Algoritmi e Programmi: SviluppoAlgoritmi e Programmi: Sviluppo

Per costruire un programma conviene procedere con Per costruire un programma conviene procedere con metodo:metodo:–– passando da passando da un’analisi del problemaun’analisi del problema da risolvere, da risolvere, –– all’algoritmo della soluzioneall’algoritmo della soluzione rappresentato in un rappresentato in un

“linguaggio” adatto all’uomo“linguaggio” adatto all’uomo ma non troppo lontano dai ma non troppo lontano dai linguaggi di programmazione,linguaggi di programmazione,

–– ed ed infine al programmainfine al programma scritto nel linguaggio di scritto nel linguaggio di programmazione prescelto.programmazione prescelto.


Algoritmi e Programmi: SviluppoAlgoritmi e Programmi: Sviluppo

Introdurremo la nozione di:Introdurremo la nozione di:–– contenitore di daticontenitore di dati (variabile)(variabile)–– come astrazione dalla nozione di come astrazione dalla nozione di zona della zona della

memoriamemoria utilizzata da un computer per i datiutilizzata da un computer per i datiDescriveremo gli algoritmi mediante:Descriveremo gli algoritmi mediante:

–– diagrammi di flussodiagrammi di flusso; e; e–– un linguaggio di programmazione didattico (LP)un linguaggio di programmazione didattico (LP)


Processo di SviluppoProcesso di Sviluppo

A.A. Diamo un nome al problema e partiamo Diamo un nome al problema e partiamo dall’analisi del dall’analisi del problema;problema;

B.B. Scriviamo la Scriviamo la specifica funzionalespecifica funzionale;;C.C. OutlineOutline dell’algoritmodell’algoritmo, ,

1.1. Si introducono i contenitori di dati necessari e le Si introducono i contenitori di dati necessari e le relative operazioni elementari;relative operazioni elementari;

2.2. Si disegna un diagramma di flusso che indica in modo Si disegna un diagramma di flusso che indica in modo preciso e non ambiguo la successione di operazioni da preciso e non ambiguo la successione di operazioni da eseguire;eseguire;

D.D. Traduciamo il diagramma di flusso in un programma.Traduciamo il diagramma di flusso in un programma.


A. Problema e Analisi del ProblemaA. Problema e Analisi del Problema

L’analisi del problema è il primo passo e deve L’analisi del problema è il primo passo e deve fornire: fornire: –– un un nomenome e una e una breve descrizionebreve descrizione di cosa si vuol di cosa si vuol

fare; fare; –– un elenco di un elenco di requisitirequisiti: richieste che il programma : richieste che il programma

deve soddisfare. deve soddisfare.


Esempio di Analisi del ProblemaEsempio di Analisi del Problema

Problema:Problema: RADICIRADICIDescrizione:Descrizione: vogliamo trovare le soluzioni reali di vogliamo trovare le soluzioni reali di

un’equazione di secondo grado.un’equazione di secondo grado.Requisiti:Requisiti: l’equazione può non avere soluzioni, avere due l’equazione può non avere soluzioni, avere due

soluzioni coincidenti o due soluzioni distinte; a seconda soluzioni coincidenti o due soluzioni distinte; a seconda dei casi, si vuole il messaggio:dei casi, si vuole il messaggio:–– ““nessuna radice xnessuna radice x”;”;–– ““radici coincidenti = rradici coincidenti = r” dove r è il valore reale delle ” dove r è il valore reale delle

radici;radici;–– ““due radici distinte r1, r2due radici distinte r1, r2” dove r1 e r2 sono i ” dove r1 e r2 sono i

valori reali delle due radici.valori reali delle due radici.


B. Specifica FunzionaleB. Specifica Funzionale

La specifica funzionale indica: La specifica funzionale indica: –– quali sono i quali sono i dati inizialidati iniziali, cioè quelli da elaborare, , cioè quelli da elaborare,

detti anche detti anche ingressi ingressi all’algoritmo; eall’algoritmo; e–– Qual è il Qual è il risultatorisultato atteso, atteso, in funzione degli in funzione degli

ingressi, ingressi, detto anche detto anche uscitauscita dell’algoritmo.dell’algoritmo.


Esempio di Specifica FunzionaleEsempio di Specifica Funzionale

RADICI:RADICI: specifica funzionalespecifica funzionaleArgomenti Argomenti oo ingressi:ingressi:

–– a,b,ca,b,c: numeri reali, coefficienti dell’equazione da : numeri reali, coefficienti dell’equazione da elaborareelaborare

Risultati Risultati o o uscite:uscite:–– ““nessuna radicenessuna radice” ” –– ““x1 = x2 = rx1 = x2 = r” se l’equazione ” se l’equazione aa..xx22+b+b..x+cx+c ha radici ha radici

coincidenti = coincidenti = rr–– ““x1 = r1, x2 = r2x1 = r1, x2 = r2” se l’equazione ” se l’equazione aa..xx22+b+b..x+cx+c ha ha

radici distinte = radici distinte = r1, r2r1, r2


C. C. OutlineOutline dell’Algoritmodell’Algoritmo

Descrivere brevemente l’idea dell’algoritmoDescrivere brevemente l’idea dell’algoritmo–– cioè i passi da eseguire per giungere alla cioè i passi da eseguire per giungere alla

soluzione a partire dagli ingressi.soluzione a partire dagli ingressi.

Il primo Il primo outlineoutline non deve necessariamente essere non deve necessariamente essere molto dettagliato: si procede per raffinamenti molto dettagliato: si procede per raffinamenti successivi.successivi.


Esempio di Esempio di OutlineOutline dell’Algoritmodell’Algoritmo

RADICI:RADICI: OutlineOutline dell’Algoritmo.dell’Algoritmo.–– Risolvo il problema calcolando il discriminante Risolvo il problema calcolando il discriminante deltadelta

dell’equazione; dell’equazione; –– Analizzo i vari casi di delta: Analizzo i vari casi di delta:

< 0 < 0 = 0= 0> 0> 0

–– Caso per caso costruisco il messaggio da inviare in Caso per caso costruisco il messaggio da inviare in uscita.uscita.

Successivamente definisco le variabili coinvolte e Successivamente definisco le variabili coinvolte e dettaglio l’algoritmo grazie ad un diagramma di flusso.dettaglio l’algoritmo grazie ad un diagramma di flusso.


CC.1..1. Contenitori di DatiContenitori di Dati

Un algoritmo deve tener traccia degli ingressi, dei risultati Un algoritmo deve tener traccia degli ingressi, dei risultati e dei valori intermedi che e dei valori intermedi che prodiceprodice durante il calcolo.durante il calcolo.

Allo scopo, usa dei Allo scopo, usa dei contenitori di daticontenitori di dati..

Un contenitore dati, detto anche variabile, è un’astrazione Un contenitore dati, detto anche variabile, è un’astrazione della nozione di area di memoria contenente dei dati.della nozione di area di memoria contenente dei dati.

I dati contenuti hanno un I dati contenuti hanno un tipotipo, che caratterizza un insieme , che caratterizza un insieme di elementi e le operazioni possibili su di essi.di elementi e le operazioni possibili su di essi.


Tipo dei Contenitori.Tipo dei Contenitori.

TIPO di DATOTIPO di DATO = insieme di elementi rappresentabili in = insieme di elementi rappresentabili in modo finito, dotato di operazioni primitive su di esso.modo finito, dotato di operazioni primitive su di esso.

ESEMPIO:ESEMPIO: il tipo degli interiil tipo degli interi–– è l’insieme degli interi, è l’insieme degli interi, sono successioni finite di cifre con sono successioni finite di cifre con

eventuale segno;eventuale segno;–– dotato delle seguenti operazioni primitive (e calcolabili): +, dotato delle seguenti operazioni primitive (e calcolabili): +, --, ,

*, divisione intera, resto.*, divisione intera, resto.

CC.1..1. Contenitori di Dati (Segue)Contenitori di Dati (Segue)

NomeNome contenitore e contenitore e tipotipo

Contenuto = Contenuto = datodato appartenete al appartenete al tipo di dati tipo di dati associato al nomeassociato al nome

pippopippo: intero: intero

5454


I contenitori di dati utilizzati per i risultati intermedi I contenitori di dati utilizzati per i risultati intermedi dipendono dall’algoritmo:dipendono dall’algoritmo:–– quindi, a meno di casi assai elementari, è quindi, a meno di casi assai elementari, è

necessario avere già un’idea ben delineata necessario avere già un’idea ben delineata dell’algoritmo per determinarlidell’algoritmo per determinarli

–– difficilmente sono TUTTI prevedibili sin dall’inizio; difficilmente sono TUTTI prevedibili sin dall’inizio; man mano che l’algoritmo prende forma, si possono man mano che l’algoritmo prende forma, si possono aggiungere al volo nuovi contenitoriaggiungere al volo nuovi contenitori

CC.1..1. Contenitori di Dati (Segue)Contenitori di Dati (Segue)


Esempio di Contenitori di DatiEsempio di Contenitori di Dati

Contenitori di dati usati da RADICI.Contenitori di dati usati da RADICI.

Di quali contenitori abbiamo bisogno per RADICI?Di quali contenitori abbiamo bisogno per RADICI?–– Sicuramente di quelli per contenere i dati di Sicuramente di quelli per contenere i dati di

ingresso ed il risultato: 3 contenitori per a,b,c ingresso ed il risultato: 3 contenitori per a,b,c (ingressi) e r1, r2.(ingressi) e r1, r2.

–– Eventuali contenitori per i risultati intermedi (ad Eventuali contenitori per i risultati intermedi (ad es. delta) ed eventualmente quello finale.es. delta) ed eventualmente quello finale.

Tutti i contenitori saranno di tipo Tutti i contenitori saranno di tipo floatfloat..


CC.2.2 Diagrammi di FlussoDiagrammi di Flusso

Diagramma di Flusso:Diagramma di Flusso: è un formalismo visuale per è un formalismo visuale per rappresentare in modo semplice ed intuitivo un algoritmo.rappresentare in modo semplice ed intuitivo un algoritmo.

Un algoritmo compie due tipi fondamentali di operazioni:Un algoritmo compie due tipi fondamentali di operazioni:–– calcoli primitivi: ottenibili mediante le operazioni calcoli primitivi: ottenibili mediante le operazioni

primitive dei tipi di dati (sostanzialmente, valutando primitive dei tipi di dati (sostanzialmente, valutando espressioni);espressioni);

–– azioni: consistono nel modificare il contenuto dei azioni: consistono nel modificare il contenuto dei contenitori di memoria, eventualmente eseguendo calcoli contenitori di memoria, eventualmente eseguendo calcoli primitivi.primitivi.


Calcoli PrimitiviCalcoli Primitivi

Valutazione di espressioni in cui compaiono i nomi dei Valutazione di espressioni in cui compaiono i nomi dei contenitori di dati utilizzati e solo operazioni primitive contenitori di dati utilizzati e solo operazioni primitive disponibili sui relativi tipi di dati; disponibili sui relativi tipi di dati;

il valore dell’espressione è riferito allo il valore dell’espressione è riferito allo STATO di STATO di memoriamemoria dell’algoritmo, cioè al contenuto attuale dei dell’algoritmo, cioè al contenuto attuale dei suoi contenitori dati.suoi contenitori dati.

Esempio:Esempio: a : a : floatfloat

22

b b . . b b -- 4 4 .. a a .. c = 0c = 0

È un’espressione valutabile perché contiene operazioni È un’espressione valutabile perché contiene operazioni primitive disponibili nel tipo primitive disponibili nel tipo floatfloat..

StatoStato delladella MemoriaMemoriac : c : floatfloat

22b : b : floatfloat

44


Calcoli Primitivi: Espressioni Calcoli Primitivi: Espressioni BooleaneBooleane

Fra le espressioni valutabili assumono particolare importanza Fra le espressioni valutabili assumono particolare importanza quelle di tipo quelle di tipo booleanobooleano..

Il tipo Il tipo booleanobooleano contiene due valori:contiene due valori:–– vero, falso.vero, falso.

Esempi di espressioni Esempi di espressioni booleanebooleane disponibili nei tipi numerici:disponibili nei tipi numerici:–– x x << yy–– (x + 5) (x + 5) == yy–– ecc.ecc.


AzioniAzioni

Modificano lo stato di memoria, cioè i valori dei Modificano lo stato di memoria, cioè i valori dei contenitori dati.contenitori dati.

Le azioni più semplici sono gli assegnamenti, della forma:Le azioni più semplici sono gli assegnamenti, della forma:–– metti ESPRESSIONE in CONTENITOREmetti ESPRESSIONE in CONTENITORE–– si valuta ESPRESSIONE e si mette il risultato in si valuta ESPRESSIONE e si mette il risultato in

CONTENITORE, sostituendone il valore precedente.CONTENITORE, sostituendone il valore precedente.Esempi di altre azioni: leggi da input, scrivi su output.Esempi di altre azioni: leggi da input, scrivi su output.Esempio:Esempio:

a : a : floatfloat

22

MettiMetti b b . . b b -- 4 4 .. a a .. c c inin deltadelta..

StatoStato delladella MemoriaMemoria

delta: delta: floatfloatb : b : floatfloat

44c : c : floatfloat

22 00


Diagrammi di FlussoDiagrammi di Flusso

Contengono sequenze di Contengono sequenze di azioni.azioni.

metti metti x+yx+y in y;in y;metti xmetti x--1 in x;1 in x;

Contengono una condizione Contengono una condizione booleanabooleana::

–– se vera, si segue la freccia se vera, si segue la freccia etichettata “vero”;etichettata “vero”;

–– se falsa si segue la freccia se falsa si segue la freccia etichettata “falso”etichettata “falso”

x = 0x = 0verovero falsofalso

–– Blocchi Decisionali.Blocchi Decisionali.–– Blocchi Blocchi ComputazionaliComputazionali..


Strutture di Controllo ModulariStrutture di Controllo Modulari

Un diagramma di flusso si ottiene collegando le frecce Un diagramma di flusso si ottiene collegando le frecce uscenti dai blocchi di elaborazione e decisionali.uscenti dai blocchi di elaborazione e decisionali.

Una buona norma è attenersi a diagrammi con strutture Una buona norma è attenersi a diagrammi con strutture predefinite, con una sola freccia entrante ed una sola predefinite, con una sola freccia entrante ed una sola uscente.uscente.

Tali strutture sono dette Tali strutture sono dette strutture di controllostrutture di controllo e sono e sono alla base della alla base della programmazione strutturata.programmazione strutturata.

Ciò consente di Ciò consente di modularizzaremodularizzare (cioè dividere in parti o (cioè dividere in parti o moduli) il diagramma; è utile poiché spesso i moduli moduli) il diagramma; è utile poiché spesso i moduli corrispondono a sottoproblemicorrispondono a sottoproblemi


Strutture di Controllo PrincipaliStrutture di Controllo Principali–– Sequenza.Sequenza. –– Iterazione.Iterazione.

verovero

falsofalso

verovero falsofalso

–– Selezione.Selezione.


Assegna ad a,b,c i Assegna ad a,b,c i valori d’ingressovalori d’ingresso

Metti il valore di Metti il valore di bb22--4ac in delta4ac in delta

delta<0?delta<0?

MESSAGGIO:MESSAGGIO:‘radici coincidenti=’ ‘radici coincidenti=’

--b/2ab/2a

MESSAGGIO:MESSAGGIO:‘radici distinte=’ ‘radici distinte=’

((--bb--radiceradice(delta))/2a(delta))/2a((--b+radice(delta))/2ab+radice(delta))/2a

MESSAGGIO:MESSAGGIO:‘nessuna ‘nessuna soluzione’soluzione’

falsofalso

verovero

falsofalso

verovero

delta=0?delta=0?

a:a:floatfloat b:b:floatfloat c:c:floatfloat

delta:delta:floatfloat

StatoStato delladella MemoriaMemoria

RADICIRADICI: : DiagrammaDiagramma didi FlussoFlusso

EsempioEsempio DiagrammaDiagramma didi FlussoFlusso

Assegna ad a,b,c i Assegna ad a,b,c i valori d’ingressovalori d’ingresso 22 1111

Assegna ad a,b,c i Assegna ad a,b,c i valori d’ingressovalori d’ingresso

Metti il valore di Metti il valore di bb22--4ac in delta4ac in delta 00

Ingresso: 1, 2, 1Ingresso: 1, 2, 1

delta<0?delta<0? falsofalso

Metti il valore di Metti il valore di bb22--4ac in delta4ac in delta

verovero

delta=0?delta=0?delta<0?delta<0? falsofalso


--b/2ab/2a

verovero

delta=0?delta=0?

MESSAGGIO:MESSAGGIO:radici coincidenti = radici coincidenti = --11


--b/2ab/2a


D. Il D. Il ProgrammaProgramma

DisegnatoDisegnato ilil diagrammadiagramma didi flussoflusso e e quindiquindi delineatodelineato in in tuttetutte le sue le sue partiparti l’algoritmol’algoritmo non non restaresta cheche tradurlotradurlo in in un un programmaprogramma cheche ilil calcolatorecalcolatore saràsarà in in gradogrado didieseguireeseguire..

Il Il programmaprogramma verràverrà scrittoscritto usandousando un un linguaggiolinguaggio didiprogrammazioneprogrammazione (ad (ad eses. C, Java, . C, Java, MatlabMatlab etc.).etc.).

NoiNoi cominceremocominceremo con un con un linguaggiolinguaggio didatticodidattico per per prendereprenderedimestichezzadimestichezza coicoi varivari concetticoncetti. .


Linguaggi di ProgrammazioneLinguaggi di Programmazione

Un linguaggio di programmazione è costituito da:Un linguaggio di programmazione è costituito da:–– un un vocabolario vocabolario –– un insieme di un insieme di regole sintatticheregole sintattiche che specificano come che specificano come

comporre istruzioni ben formatecomporre istruzioni ben formate–– una una semanticasemantica che associa un “significato” alle istruzioni che associa un “significato” alle istruzioni

ben formate, cioè l’azione denotata da ciascuna ben formate, cioè l’azione denotata da ciascuna istruzione.istruzione.

Rispetto ad una qualsiasi lingua parlata da esseri umani, Rispetto ad una qualsiasi lingua parlata da esseri umani, un linguaggio di programmazione è molto più semplice, un linguaggio di programmazione è molto più semplice, perché la sua sintassi è molto semplice.perché la sua sintassi è molto semplice.



Linguaggi di Basso Livello.Linguaggi di Basso Livello.Sono linguaggi di programmazione caratterizzati da Sono linguaggi di programmazione caratterizzati da

istruzioni molto elementari (ad es. l’istruzioni molto elementari (ad es. l’AssemblyAssembly). ). Richiedono uno sforzo di codifica maggiore da parte Richiedono uno sforzo di codifica maggiore da parte del programmatore.del programmatore.

Linguaggi di Alto Livello.Linguaggi di Alto Livello.Sono linguaggi di programmazione in cui ad ogni Sono linguaggi di programmazione in cui ad ogni

istruzione corrisponde un insieme di azioni più istruzione corrisponde un insieme di azioni più articolato. Richiedono uno sforzo di codifica articolato. Richiedono uno sforzo di codifica inferiore.inferiore.


EsempioEsempio

Il linguaggio L1 mette a disposizione i Il linguaggio L1 mette a disposizione i comadicomadi::–– Aggiungi_una_unità_al_dato_AAggiungi_una_unità_al_dato_A–– Leggi_dato_ALeggi_dato_A–– Leggi_dato_BLeggi_dato_B–– Esegui_perEsegui_per <numero di volte><numero di volte>

Il linguaggio L2 mette a disposizione i Il linguaggio L2 mette a disposizione i comadicomadi::–– Leggi_dato_ALeggi_dato_A–– Leggi_dato_BLeggi_dato_B–– Somma <addendo1, addendo2>Somma <addendo1, addendo2>


Esempio (Segue)Esempio (Segue)

Vogliamo scrivere un programma per la somma di due Vogliamo scrivere un programma per la somma di due numeri memorizzati rispettivamente nei registro A e B.numeri memorizzati rispettivamente nei registro A e B.

In In L1L1::Leggi_dato_ALeggi_dato_ALeggi_dato_BLeggi_dato_BEsegui_perEsegui_per B volte:B volte:Aggiungi _una_unità_al_dato_AAggiungi _una_unità_al_dato_A

In In L2L2::Leggi_dato_ALeggi_dato_ALeggi_dato_BLeggi_dato_BSomma (A, B)Somma (A, B)

L2 è un linguaggio di livello più alto rispetto a L1, L2 è un linguaggio di livello più alto rispetto a L1, perché offre al programmatore la possibilità di usare perché offre al programmatore la possibilità di usare istruzioni che sono meno “vicine” al modo in cui lavora il istruzioni che sono meno “vicine” al modo in cui lavora il processore.processore.


Il Linguaggio MacchinaIl Linguaggio Macchina

Il processore è in grado di riconoscere (e quindi di Il processore è in grado di riconoscere (e quindi di eseguire) solo programmi scritti in un proprio linguaggio eseguire) solo programmi scritti in un proprio linguaggio di basso livello (di basso livello (linguaggio macchinalinguaggio macchina).).

Ogni modello di processore (Ogni modello di processore (eses: : IntelIntel, , PentiumPentium, , MotorolaMotorola, , PowerPCPowerPC) ha un proprio linguaggio macchina diverso da ) ha un proprio linguaggio macchina diverso da quello degli altri processori.quello degli altri processori.

Un programma scritto in un linguaggio diverso dal linguaggio Un programma scritto in un linguaggio diverso dal linguaggio macchina deve essere quindi tradotto nel linguaggio che macchina deve essere quindi tradotto nel linguaggio che il processore sa interpretare.il processore sa interpretare.



Invece di codificare algoritmi in linguaggi macchina si Invece di codificare algoritmi in linguaggi macchina si utilizzano linguaggi ad alto livello.utilizzano linguaggi ad alto livello.

Le istruzione dei linguaggi ad alto livello sono facilmente Le istruzione dei linguaggi ad alto livello sono facilmente comprensibili ai programmatori. comprensibili ai programmatori.

CompilatoreCompilatore: (programma che) traduce automaticamente : (programma che) traduce automaticamente un programma ad alto livello in linguaggio macchina.un programma ad alto livello in linguaggio macchina.

Affronteremo la programmazione tramite un linguaggio Affronteremo la programmazione tramite un linguaggio semplificato che chiameremo LP (riepilogo sintassi sul semplificato che chiameremo LP (riepilogo sintassi sul sito del corso).sito del corso).


Nozione di VariabileNozione di Variabile

Come si indirizzano le Come si indirizzano le celle di memoriacelle di memoria??

Invece di usare gli indirizzi fisici si usano dei nomi Invece di usare gli indirizzi fisici si usano dei nomi simbolicisimbolici ((eses., ., xx, , yy, , nomenome,...) che vengono ,...) che vengono mappatimappati in in indirizzi fisici attraverso la fase di compilazione.indirizzi fisici attraverso la fase di compilazione.

Le variabili vanno Le variabili vanno dichiaratedichiarate all’inizio del programma all’inizio del programma (celle diverse, nomi diversi).(celle diverse, nomi diversi).

ValoreValore di una variabile = di una variabile = contenutocontenuto corrente della corrente della cellacella di di memoria associata alla variabile.memoria associata alla variabile.


Nozione di CostanteNozione di Costante

Per esprimere direttamente valori prefissati (cioè che Per esprimere direttamente valori prefissati (cioè che non devono essere modificati dal programma) si non devono essere modificati dal programma) si utilizzano leutilizzano le costanticostanti

Una Una costantecostante è una rappresentazione è una rappresentazione simbolicasimbolica di un di un numero, stringa, ecc.numero, stringa, ecc.

Ad esempio, Ad esempio, 11, , ‘‘ciao’ciao’, , 3.143.14, ecc., ecc.Il set di costanti disponibile dipende dal linguaggio di Il set di costanti disponibile dipende dal linguaggio di

programmazione.programmazione.


EspressioniEspressioni

Le espressioni servono per rappresentare calcoli a livello Le espressioni servono per rappresentare calcoli a livello simbolico.simbolico.

Un’espressione può coinvolgere nomi di variabili, costanti, Un’espressione può coinvolgere nomi di variabili, costanti, operatori operatori aritmeticoaritmetico--logicilogici, ecc., ecc.

EsEs: : 3+4, 3+4, x+yx+y--11 (dove x è una variabile),(dove x è una variabile),x>0 and y>1x>0 and y>1


Programma LPProgramma LP

La sintassi di un programma LP consiste di due blocchi.La sintassi di un programma LP consiste di due blocchi.

Dichiarazione di variabili e costanti:Dichiarazione di variabili e costanti:constconst pi = 3.14, nome = “Walter”;pi = 3.14, nome = “Walter”;varvar x: x: intint, y: , y: stringstring, z: , z: floatfloat;;

Sono liste di dichiarazioni introdotte rispettivamente Sono liste di dichiarazioni introdotte rispettivamente dalla dalla keywordkeyword constconst e e var.var.

Sequenza di istruzioni racchiusa tra le parole chiave Sequenza di istruzioni racchiusa tra le parole chiave beginbegin …… endend e separate dal punto e virgola ‘e separate dal punto e virgola ‘;;’’


Esecuzione di un ProgrammaEsecuzione di un Programma

Qual è significato (semantica) di un programma?Qual è significato (semantica) di un programma?

Trasformazione da Input iniziale a Output finale!Trasformazione da Input iniziale a Output finale!

Un programma deve essere eseguito per poter calcolare Un programma deve essere eseguito per poter calcolare la trasformazione la trasformazione InputInput OutputOutput. .

L’esecuzione modifica lo stato del programma:L’esecuzione modifica lo stato del programma:stato iniziale, corrente, e finale.stato iniziale, corrente, e finale.

L’esecuzione dipende dalla semantica dei singoli costrutti.L’esecuzione dipende dalla semantica dei singoli costrutti.


Lettura e ScritturaLettura e Scrittura

Le operazioni di lettura e scrittura servono per ottenere Le operazioni di lettura e scrittura servono per ottenere valori in input (es. tastiera) o fornire valori in output valori in input (es. tastiera) o fornire valori in output (es. Video). (es. Video).

Assumiamo che input e output siano sequenze di valori:Assumiamo che input e output siano sequenze di valori:–– writewrite(Variabile)(Variabile): aggiunge il valore corrente di : aggiunge il valore corrente di VariabileVariabile

all’output;all’output;–– readread(Variabile)(Variabile): toglie il primo valore della lista input e lo : toglie il primo valore della lista input e lo

assegna a assegna a VariabileVariabile. .


AssegnamentoAssegnamento

Si utilizza per assegnare il valore Si utilizza per assegnare il valore correntecorrente di di un’espressione ad una variabile. L’un’espressione ad una variabile. L’assegnamentoassegnamento cambia cambia il valore della variabile.il valore della variabile.

Variabile := Espressione;Variabile := Espressione;

se nello stato corrente se nello stato corrente EspressioneEspressione si valuta in si valuta in val val allora allora VariabileVariabile varrà varrà valval dopo l’esecuzione dell’assegnamento.dopo l’esecuzione dell’assegnamento.

EsEs.. x:=x+1x:=x+1L’espressione x+1 va valutata nello stato corrente.L’espressione x+1 va valutata nello stato corrente.Il risultato dell’espressione è assegnato nuovamente ad x.Il risultato dell’espressione è assegnato nuovamente ad x.


Istruzione CondizionaleIstruzione Condizionale

Sintassi:Sintassi:ifif CondizioneCondizione thenthen Lista IstruzioniLista Istruzioni11elseelse Lista IstruzioniLista Istruzioni22endifendif

CondizioneCondizione = Espressione Booleana.= Espressione Booleana.Se la condizione si valuta in Se la condizione si valuta in verovero si si

esegue ramo esegue ramo thenthen, altrimenti si esegue , altrimenti si esegue il ramo elseil ramo else verovero falsofalso

Lista IstruzioniLista Istruzioni11

CondizioneCondizione

Lista IstruzioniLista Istruzioni22


EsempiEsempi

Lettura da tastiera e Lettura da tastiera e scrittura su video:scrittura su video:

varvar s: s: stringstringbeginbegin

readread(s);(s);writewrite(s);(s);

endend..

Leggere due numeri, sommarli Leggere due numeri, sommarli e stampare il risultato:e stampare il risultato:

varvar x,y,somma: x,y,somma: intint;;beginbegin

readread(x);(x);readread(y);(y);sommasomma:=:=x+y;x+y;writewrite(somma);(somma);

end.end.

Calcolare il Calcolare il massimomassimo tra 2 tra 2 valori letti in input:valori letti in input:

varvar x,y: x,y: intint;;beginbegin

readread(x);(x);readread(y);(y);ifif x>y x>y thenthen

writewrite(x)(x)else else writewrite(y);(y);endifendif

end.end.


Istruzione CiclicaIstruzione Ciclica

Sintassi:Sintassi:whilewhile CondizioneCondizione dodo

Lista IstruzioniLista Istruzioniendwendw

Lista IstruzioniLista Istruzioni viene eseguita viene eseguita fintantochèfintantochèCondizione si valuta in Condizione si valuta in vero.vero.

Quando Quando CondizioneCondizione si valuta in si valuta in falsofalso si si passa all’istruzione seguente nel passa all’istruzione seguente nel programmaprogramma

verovero

falsofalsoCondizioneCondizione

Lista IstruzioniLista Istruzioni


Esempio: Somma di K NumeriEsempio: Somma di K Numeri

ProblemaProblema: leggere K, e quindi calcolare la somma di K valori : leggere K, e quindi calcolare la somma di K valori letti dall’input.letti dall’input.

Devo memorizzare K, la somma, e i valori letti Devo memorizzare K, la somma, e i valori letti V1,V2,…,VKV1,V2,…,VK–– PoichePoiche uso ogni uso ogni ViVi una sola volta, bastano 3 variabili: una sola volta, bastano 3 variabili: K, x ed S;K, x ed S;–– xx manterrà il valore manterrà il valore ViVi corrente, S la somma progressiva;corrente, S la somma progressiva;

varvar K, x, S: K, x, S: intint;;beginbegin

readread(K); S:=0;(K); S:=0;whilewhile K>0 K>0 do do

readread(x);(x);S:=S+x; K:=KS:=S+x; K:=K--1;1;

endwendw;;writewrite(somma);(somma);

end.end.


Esecuzione del Esecuzione del whilewhile

Inizialmente: Inizialmente: valval(x),(x),valval(K)(K)=indefiniti=indefiniti,,valval(somma)=0.(somma)=0.Leggo il valore 3: Leggo il valore 3: valval(K)=3(K)=3Poiché Poiché valval(K)>0, entro nel ciclo.(K)>0, entro nel ciclo.Leggo il primo valore in input Leggo il primo valore in input V1V1 su cui fare la somma e su cui fare la somma e

lo memorizzo in x.lo memorizzo in x.Calcolo somma=somma+x, e decremento K.Calcolo somma=somma+x, e decremento K.Cioè dopo l’esecuzione delle istruzioni dentro il cicloCioè dopo l’esecuzione delle istruzioni dentro il ciclo

valval(x)=3, (x)=3, valval(somma)=3, (somma)=3, valval(K)=2(K)=2Proseguo con il ciclo Proseguo con il ciclo fino a chefino a che valval(K)=0.(K)=0.A tal punto esco dal ciclo e scrivo il valore finale di A tal punto esco dal ciclo e scrivo il valore finale di

sommasomma


Esempio: Calcolo MCDEsempio: Calcolo MCD

Calcolare il massimo Calcolare il massimo comuncomun divisore tra due numeri interi divisore tra due numeri interi letti da input, utilizzando l’algoritmo di letti da input, utilizzando l’algoritmo di EuclideEuclide::–– mcdmcd(m,n)=m=n se (m,n)=m=n se n=Mn=M–– mcdmcd(m,n)(m,n)=mcd=mcd(m(m--n,n) se m>nn,n) se m>n–– mcdmcd(m,n)(m,n)=mcd=mcd(m,n(m,n--m) se n>mm) se n>m


Algoritmo di Algoritmo di EuclideEuclide

Leggo m and nLeggo m and n(*) Fino a che m diverso da n, (*) Fino a che m diverso da n,

–– se m>n allora sottraggo n ad mse m>n allora sottraggo n ad m–– se n>m sottraggo m ad nse n>m sottraggo m ad n–– torno a (*)torno a (*)

Quando Quando m=nm=n stampo, ad stampo, ad eses, n, n


Es.Es. Calcolo MCDCalcolo MCD

varvar m,n: m,n: intint;;beginbegin

readread(m);(m);readread(n);(n);whilewhile notnot((m=nm=n) ) do do

ifif m>n m>n thenthen m:=mm:=m--n n elseelse n:=nn:=n--m;m;endifendif

endwendw;;writewrite(n); (n); (Nota: a questo punto (Nota: a questo punto n=mn=m!)!)

endend


Strutture Dati ComplesseStrutture Dati Complesse

Oltre a variabili di tipo Oltre a variabili di tipo intero,intero, stringastringa, ecc può essere , ecc può essere molto utile utilizzare dati strutturati (ad es. molto utile utilizzare dati strutturati (ad es. listeliste, , insiemiinsiemi, ecc), ecc)

Molti linguaggi di programmazione forniscono vari tipi di Molti linguaggi di programmazione forniscono vari tipi di dato quali dato quali –– arrayarray, , –– recordrecord,,–– listlist

Nel linguaggio LP abbiamo solo Nel linguaggio LP abbiamo solo arrayarray e record.e record.


ArrayArray

Un Un arrayarray rappresenta una sequenza di celle consecutive rappresenta una sequenza di celle consecutive contenenti dati contenenti dati omogeneiomogenei (es. (es. interi).interi).

Una variabile Una variabile V V di tipo di tipo arrayarray denota la sequenza di celledenota la sequenza di cellePer accedere direttamente alla cella Per accedere direttamente alla cella ii--esima si utilizza il esima si utilizza il

suo indice suo indice i i come segue: come segue: V[i].V[i].Sintassi dichiarazione:Sintassi dichiarazione:

–– NomeVarArrayNomeVarArray: : arrayarray 1..N 1..N ofof Tipo; (N costante)Tipo; (N costante)Nelle espressioni, assegnamenti, ecc si utilizza poiNelle espressioni, assegnamenti, ecc si utilizza poi

–– NomeVarArrayNomeVarArray[Exp] dove [Exp] dove ExpExp è un espressione che è un espressione che si valuta in un valore da 1…Nsi valuta in un valore da 1…N


varvar A : A : arrayarray 1..10 1..10 of intof int; ; i,K : i,K : intint;;

beginbeginreadread(K);(K);i := 1;i := 1;whilewhile i=i=<K <K dodo

readread(A[i]);(A[i]);i:=i+1;i:=i+1;

endwendw;;i:i:=K=K;;whilewhile i>0 i>0 dodo

writewrite(A[i]);(A[i]);i:=ii:=i--1;1;

endwendw;;end.end.

Esempio: Esempio: ArrayArray

Leggere Leggere K=K=<10 valori e stamparli <10 valori e stamparli in ordine inverso:in ordine inverso:–– Dobbiamo leggere V1,…,VK, Dobbiamo leggere V1,…,VK,

memorizzarli e poi stamparli in memorizzarli e poi stamparli in ordine VK,…,V1.ordine VK,…,V1.

–– Usiamo un Usiamo un arrayarray A di N>K A di N>K posizioni per memorizzare i posizioni per memorizzare i dati in input.dati in input.

–– Dopo aver memorizzato i dati, Dopo aver memorizzato i dati, li scriviamo scorrendo l’li scriviamo scorrendo l’arrayarraydall’indice K all’indice 1.dall’indice K all’indice 1.


RecordRecord

Tipo di dato per gestire dati strutturati di tipo Tipo di dato per gestire dati strutturati di tipo eterogeneo; ogni dato viene chiamato campo del eterogeneo; ogni dato viene chiamato campo del record.record.

SintassiSintassi::Variabile: Variabile: recordrecord

CampoCampo--1:Tipo1;1:Tipo1;……CampoCampo--N:N:TipoNTipoN;;

endendPer accedere ai campi di un record si utilizza:Per accedere ai campi di un record si utilizza:

Variabile.CampoVariabile.Campo--ii (rappresenta l’i(rappresenta l’i--esimo campo)esimo campo)


Esempio di RecordEsempio di Record

Coordinate:Coordinate:varvar Punto:Punto:recordrecord x,y:x,y:intint endend;;

z:z:intint;;

Punto.x=3;Punto.x=3;Punto.y=2;Punto.y=2;z:=Punto.x*Punto.y;z:=Punto.x*Punto.y;


Compilatore e Compilatore e LoaderLoader

Un Un compilatorecompilatore è un programma che traduce un è un programma che traduce un programma scritto in linguaggio ad alto livello in un programma scritto in linguaggio ad alto livello in un programma scritto in linguaggio macchina:programma scritto in linguaggio macchina:–– Un compilatore produce quindi un programma Un compilatore produce quindi un programma

eseguibile (eseguibile (.exe.exe in Windows)in Windows)Il Il loaderloader è il programma che carica un programma in è il programma che carica un programma in

linguaggio macchina in memoria principale (e quindi linguaggio macchina in memoria principale (e quindi mappa indirizzi logici in indirizzi fisici)mappa indirizzi logici in indirizzi fisici)


Come Funziona la CompilazioneCome Funziona la Compilazione

Un compilatore (che abbia anche la funzione di Un compilatore (che abbia anche la funzione di loaderloader) ) deve deve –– riconoscere la sintassi del linguaggio ad alto livello; riconoscere la sintassi del linguaggio ad alto livello; –– associare uno spazio in memoria associare uno spazio in memoria principareprincipare per per

poter gestire le variabili dichiarate nel programma;poter gestire le variabili dichiarate nel programma;–– tradurre i costrutti di alto livello in sequenze di tradurre i costrutti di alto livello in sequenze di

istruzioni in linguaggio macchina.istruzioni in linguaggio macchina.

Date post:	15-Feb-2019
Category:	Documents
Upload:	dokhue
View:	223 times
Download:	0 times

Algoritmi, Dati e Programmi - disi.unige.it · Tali strutture sono dette strutture di ... tutte le...

Documents