Computer, algoritmi e linguaggi - Capitolo 1homes.di.unimi.it/~cesabian/prog/c01-basi.pdf · Esami...

Capitolo 1

Computer, algoritmi elinguaggi

Informazioni sul corso

Sito del corso: pighizzini.di.unimi.it/programmazione/

Laboratorio: Prof. Carlo Mereghetti, inizio 16 ottobre

Esame: scritto + laboratorio + orale

Compitini: novembre, gennaio

Appelli: gennaio-febbraio, giugno-luglio, settembre

Esami – 1

Struttura dell’esame1 L’esame di Programmazione consiste di una prova scritta, di una

prova di laboratorio e di un colloquio.

2 Nella prova scritta viene richiesta la soluzione di alcuni esercizi (sullostile di quelli presenti nel libro di testo e proposti nei compitini).

3 Nella prova di laboratorio viene richiesta la scrittura di codice chesoddisfi specifiche assegnate. Per partecipare alla prova di laboratorioe necessario disporre di un account presso il SiLab.

4 Il colloquio vertera sui contenuti del corso. Oltre alla padronanzadegli argomenti, nella prova orale si verifichera la capacita diesprimere correttamente e con termini appropriati i concetti appresi.

Esami – 2

Vincoli sull’ordine di svolgimento delle prove

1 La prova scritta e la prova di laboratorio possono essere sostenute inun ordine qualsiasi e in appelli differenti. Tuttavia, visto che le dueprove riguardano, anche se da punti di vista diversi, gli stessicontenuti, si suggerisce fortemente di sostenere le prove nello stessoappello.

2 Si accede al colloquio dopo avere superato sia la prova scritta sia laprova di laboratorio. Al termine del colloquio verra formulata everbalizzata la valutazione finale dell’esame. Il colloquio puo esseresostenuto nello stesso appello delle altre prove, o in un appellosuccessivo, purche entro il limite massimo indicato sotto.

Esami – 3

Validita delle prove

1 L’esame deve essere completato entro l’ultimo appello previso perl’anno accademico, cioe quello di settembre 2012. Dopo tale appelloeventuali parti d’esame superate saranno inderogabilmente annullate.

2 La partecipazione a una prova scritta annulla un’eventuale provascritta gia superata (inclusa la prova superata mediante compitini).

3 La partecipazione a una prova di laboratorio annulla un’eventualeprova di laboratorio gia superata.

4 Il mancato superamento del colloquio implica l’annullamento dellaprova scritta e dunque rende necessaria la sua ripetizione.

Esami – 4

Compitini

1 Sulla base dei risultati ottenuti nei compitini lo studente puo essereesonerato dalla prova scritta ed eventualmente dalla prova orale.

2 In caso di esonero dalla prova orale, il voto finale proposto saracomunicato dopo il superamento della prova di laboratorio.

3 E necessario che lo studente si presenti alla prova orale per laverbalizzazione del risultato.

4 Lo studente ha comunque la facolta di sostenere la prova orale.

Introduzione

1 Computer, algoritmi e programmiComputer, algoritmi e programmiEvoluzione della programmazioneFinalita del corsoRappresentazione dell’informazione

2 Dal linguaggio macchina ai linguaggi ad alto livelloLa macchina di Von NeumannComponenti principali di un computerI linguaggi ad alto livelloJava Virtual Machine (JVM)Strumenti per la stesura dei programmi

3 La programmazione strutturataLe strutture di controllo fondamentaliVariabili e assegnamenti

4 Sintassi e semanticaGrammaticheLessico del linguaggio Java

Sommario: Computer, algoritmi e linguaggi

Computer e programmi

Programmazione

Codifica del procedimento risolutivo di un problema (algoritmo) in uninsieme di istruzioni (programma) destinate ad un esecutore (macchina)

Problema dell’ordinamento (sorting)

Ordinare una sequenza di interi in modo crescente

21 5 9 10 13 2 6

Possiamo risolvere il problema usando diversi algoritmi: mergesort,bubblesort, quicksort

Possiamo codificare l’algoritmo usando diversi linguaggi: c, visualbasic, java

Possiamo eseguire il programma su diversi processori: intel, amd,motorola

Programmazione

21 5 9 10 13 2 6

Programmazione

21 5 9 10 13 2 6

Programmazione

21 5 9 10 13 2 6

Programmazione

21 5 9 10 13 2 6

Algoritmi

Algoritmo

Insieme ordinato di passi eseguibili (non manipolo oggetti infiniti) e nonambigui che definiscono un processo terminante (no cicli infiniti).

La nozione di algoritmo precede quella di programmazione

Algoritmo di Euclide per calcolare il massimo comun divisore (300 AC)

Crivello di Eratostene per enumerare i numeri primi (250 AC)

Algoritmi per la moltiplicazione, divisione, estrazione di radicequadrata. . .

Algoritmi

Algoritmo

Insieme ordinato di passi eseguibili (non manipolo oggetti infiniti) e nonambigui che definiscono un processo terminante (no cicli infiniti).

La nozione di algoritmo precede quella di programmazione

Algoritmo di Euclide per calcolare il massimo comun divisore (300 AC)

Crivello di Eratostene per enumerare i numeri primi (250 AC)

Algoritmi per la moltiplicazione, divisione, estrazione di radicequadrata. . .

L’algoritmo di Euclide

Calcola il massimo comun divisore (MCD) fra due numeri interi x e y(x ≥ y > 0)

1. Calcola il resto della divisione di x per y

2. Se il resto e diverso da zero,ricomincia dal passo 1 utilizzando come x il valore attuale di y ,e come y il valore del resto,

altrimentiprosegui con il passo successivo

3. Il massimo comun divisore e uguale al valore attuale di y

L’ intelligenza necessaria per trovare la soluzione del problema e tuttacodificata nell’algoritmo

Chiunque sappia comprendere ed eseguire le operazioni checostituiscono l’algoritmo di Euclide, puo calcolare l’MCD

Un esempio negativo

1. Crea un elenco di tutti i numeri primi

2. Ordina l’elenco in modo decrescente

3. Preleva il primo elemento dall’elenco risultante

E un algoritmo?

Non lo e

La prima e la seconda istruzione non sono effettivamente eseguibili inquanto richiedono la manipolazione di infiniti elementi

Un esempio negativo

1. Crea un elenco di tutti i numeri primi

2. Ordina l’elenco in modo decrescente

3. Preleva il primo elemento dall’elenco risultante

E un algoritmo?

Non lo e

La prima e la seconda istruzione non sono effettivamente eseguibili inquanto richiedono la manipolazione di infiniti elementi

Algoritmi e programmi

Programma

E la codifica di un algoritmo in un linguaggio che un esecutore e in gradodi eseguire su una data macchina senza bisogno di ulteriori spiegazioni

LOAD R1, 101 LOAD R1, 102

LOAD R2, 102 JZERO R2, end

start DIV R1, R2 STORE R1, 101

MUL R1, R2 STORE R2, 102

LOAD R2, 101 JUMP start

SUB R2, R1 end LOAD R1, 102

STORE R1, 103

Evoluzione della programmazione

anni ’40-’50 Programmi scritti direttamente nel linguaggio del processore(linguaggio macchina). Difficili da scrivere e da modificare.

1954 Nascita dei linguaggi ad alto livello e dei compilatori.fortran (IBM)

1958 Nascita dei linguaggi “multipiattaforma”. algol

1970 Programmazione strutturata (Dijkstra). Blocchi, top-down,no goto. Strutture di controllo: sequenza, selezione e ciclo.Struttura → correttezza, manutebilita. pascal, ada

1972 Programmazione ad oggetti. smalltalk

1991 java (Sun, acquistata da Oracle).

Evoluzione della programmazione (cont.)

Tendenza generale

Il linguaggio si astrae dalle caratteristiche della macchina

Programmazione strutturata → struttura nel codice

Programmazione ad oggetti → struttura nei dati

Programmazione ad oggetti

Idea di fondo: disegno il software attorno agli oggetti manipolatipiuttosto che attorno alle azioni eseguite sugli oggetti

Approccio giustificato perche si parte dal problema (dato) e non dallasoluzione (algoritmo)

La rappresentazione dei dati (oggetto) e piu stabile rispetto al codiceche implementa le operazioni su di esso

Posso usare oggetti semplici per costruire oggetti piu complessi (riusodel software)

Evoluzione della programmazione (cont.)

Tendenza generale

Il linguaggio si astrae dalle caratteristiche della macchina

Programmazione strutturata → struttura nel codice

Programmazione ad oggetti → struttura nei dati

Programmazione ad oggetti

Idea di fondo: disegno il software attorno agli oggetti manipolatipiuttosto che attorno alle azioni eseguite sugli oggetti

Approccio giustificato perche si parte dal problema (dato) e non dallasoluzione (algoritmo)

La rappresentazione dei dati (oggetto) e piu stabile rispetto al codiceche implementa le operazioni su di esso

Posso usare oggetti semplici per costruire oggetti piu complessi (riusodel software)

Finalita del corso

Acquisire le abilita necessarie per programmare usando linguaggi adoggetti

Non e un corso di Java: il linguaggio e uno strumento peresemplificare i concetti

Organizzazione del corso

Parte I: Combinazione di oggetti gia esistenti (quali servono, come licombino)

Parte II: Costruzione di classi di oggetti → costruire classi chepossono essere riusate per affrontare problemi diversi

Finalita del corso

Acquisire le abilita necessarie per programmare usando linguaggi adoggetti

Non e un corso di Java: il linguaggio e uno strumento peresemplificare i concetti

Organizzazione del corso

Parte I: Combinazione di oggetti gia esistenti (quali servono, come licombino)

Parte II: Costruzione di classi di oggetti → costruire classi chepossono essere riusate per affrontare problemi diversi

Rappresentazione dell’informazione

Nel computer, qualsiasi informazione deve esssere rappresentata informa digitale binaria come sequenza di bit

Bit (binary digit): una quantita astratta che puo assumere soltantodue valori distinti

Digitalizzazione: processo che traduce informazione in formato binario(immagini, audio, video, testi, programmi)

In alcuni casi il processo di digitalizzazione comporta perdita diinformazione (data entry rispetto a campionamento)

Rappresentazione di numeri e caratteri

Con n bit posso rappresentare al piu 2n interi distinti

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Alcuni tipi di codifiche

Caratteri alfanumerici ASCII: 8 bit per ogni carattere(28 = 256 caratteri)

Caratteri alfanumerici Unicode: 16 bit per ogni carattere(216 = 65536 caratteri)

Codifica tipica numeri interi: 32 bit per ogni intero.Rappresento il range {−231, . . . , 0, . . . , 231 − 1}Codifica tipica numeri decimali: 64 bit per ogni numero

x = m × 10e 53 bit per m e 11 bit per e

Esempio: 0,000012 = 12× 10−6

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Esempio: 0,000012 = 12× 10−6

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Esempio: 0,000012 = 12× 10−6

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Esempio: 0,000012 = 12× 10−6

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Codifica tipica numeri interi: 32 bit per ogni intero.Rappresento il range {−231, . . . , 0, . . . , 231 − 1}

Codifica tipica numeri decimali: 64 bit per ogni numero

Esempio: 0,000012 = 12× 10−6

n = 3 → 23 = 8

000 001 010 011 100 101 110 111

Esempio: 0,000012 = 12× 10−6

I multipli del bit

1 byte = 8 bit

Kilobyte 210 (circa 103) byte. Una pagina web statica

Megabyte 220 (circa 106) byte. Una fotografia digitale

Gigabyte 230 (circa 109) byte. Un banco di memoria RAM

Terabyte 240 (circa 1012) byte. Un disco fisso esterno

Petabyte 250 (circa 1015) byte. Un datacenter

Exabyte 260 (circa 1018) byte. Traffico mobile dati nel mondo al mese

Zettabyte 270 (circa 1021) byte. Tutto il web

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

I multipli del bit

1 byte = 8 bit

Il Computer

Computer: macchina elettronica programmabile (lavatrice?)

Il computer e una macchina universale, ovvero puo eseguire qualsiasialgoritmo

Negli anni Trenta ilmatematico inglese AlanTuring caratterizza cio chepuo essere calcolato da unalgoritmo

Negli anni Quaranta ilmatematico ungherese Johnvon Neumann definiscel’architettura base di uncalcolatore universale(stored-program computer)

Il Computer

La macchina di Von Neumann (1946)

I componenti fondamentali dell’hardware di un elaboratore sono:

MemoriaContiene il programma da eseguire e i dati da esso utilizzati.

ProcessoreE l’esecutore del programma e opera ripetendo il ciclo

FetchDecode

Execute

1 Fetch: preleva la prossima istruzione

2 Decode: scomponi l’istruzione inoperatore e operandi

3 Execute: applica l’operatore aglioperandi

FetchDecode

Execute

FetchDecode

Execute

Hardware

La parte fisica del computer

Processore o unita centrale (CPU)Il dispositivo che esegue effettivamente l’operazione

Memoria centraleSuddivisa in celle della stessa dimensione (p.es., 4 byte)

Ogni cella identificata da un indirizzoTempo di accesso costante (circa 10 nanosecondi = 10−8 secondi)RAM: memoria volatile di lettura/scrittura; contiene i programmi inesecuzione e parte dei loro datiROM: memoria permanente di sola lettura; contiene informazioninecessarie all’avvio del computer (BIOS)

Hardware

Hardware (cont.)

Memoria di massa: Hard-disk, CD, DVD, chiavi USB

Tempo di accesso non costante (tranne per chiavi USB), tempo mediodi accesso di molto superiore a RAMInformazione organizzata in files all’interno di un file-system

PerifericheVideo, tastiera, mouse, scheda rete, stampante, . . .

Permettono la comunicazione fra computer e mondo esterno

Bus: Circuiti di connessione fra componenti

Hardware (cont.)

Software

L’insieme di tutti i programmi utilizzabili dal computer

Sistema operativoMette a disposizione e amministra le risorse del computer

Esecuzione comandi tramite shell o desktopAccesso alle risorse (CPU, memoria e periferiche)Condivisione ottimale delle risorse fra piu processi utilizzatori

Utility e SW di baseConsentono all’utente di effettuare delle attivita di gestione

Copiatura e compressione file, sicurezza, sviluppo codice

Programmi applicativi

Software

Linguaggio macchina e assembler

Ogni processore ha un proprio linguaggio macchina con un proprioformato delle istruzioni

Le istruzioni sono sequenze di bit che codificano:

l’operazione da eseguiregli operandi su cui tale operazione deve essere eseguita

Gli operandi sono:

indirizzi di memoria RAMregistri del processorecostanti (p.es., 5)

Nota: Tutte le operazioni aritmetico-logiche vengono effettuatesoltanto su operandi contenuti in registri del processore

Il linguaggio assembler di un processore e la versione simbolica dellinguaggio macchina

Gli operandi sono:

Un assembler “giocattolo”

Istruzioni di trasferimento :

LOAD R, x STORE R, y ...

Istruzioni aritmetico-logiche

ADD R1, R2 MUL R1, R2 ...

Istruzioni di controllo e di salto

salto incondizionato

JUMP alfa

alfa:...

salto condizionato

JZERO R1, alfa

alfa:...

JUMP alfa

alfa:...

salto condizionato

JZERO R1, alfa

alfa:...

JUMP alfa

alfa:...

salto condizionato

JZERO R1, alfa

alfa:...

Calcola il massimo comun divisore (MCD) fra due numeri x e y(x ≥ y > 0)

Correttezza dell’algoritmo di Euclide

L’algoritmo di Euclide puo essere riscritto comeSe x%y = 0 allora MCD(x,y) = y

altrimenti MCD(x,y) = MCD(y,x%y)

La parte “se . . . allora” e chiaramente corretta. Verifichiamo lacorrettezza della parte “altrimenti”

Dato che x > y possiamo scrivere x = yk + q dove k e q sono dueinteri positivi con q < y

Sia g = MCD(x , y). Allora q divide g , infatti

yk + q

Dato che (yk)/g e (yk)/g + q/g sono entrambi interi, anche q/g eintero

Quindi g e anche il massimo comun divisore fra y e q = x%y

yk + q

L’algoritmo di Euclide in assembler

LOAD R1, 101 R1 <- 101 (input x)

LOAD R2, 102 R2 <- 102 (input y)

start DIV R1, R2 R1 <- R1/R2 (divisione intera)

MUL R1, R2 R1 <- R1*R2 (moltiplicazione)

LOAD R2, 101 R2 <- 101

SUB R2, R1 R2 <- R2-R1 (R2 = resto div.)

JZERO R2, end IF R2=0 GOTO end

LOAD R1, 102 R1 <- 102

STORE R1, 101 101 <- R1

STORE R2, 102 102 <- R2

JUMP start GOTO start

end LOAD R1, 102 R1 <- 102

STORE R1, 103 103 <- R1

x%y = x − bx/ycy Esempio: 8%3 = 8− b8/3c3

Svantaggi del linguaggio macchina

E necessario conoscere i dettagli dell’architettura del processoreutilizzato e il relativo linguaggio

Risulta impossibile trasportare i programmi da una macchina ad unadifferente

Il programmatore si specializza nell’uso di “trucchi” legati allecaratteristiche specifiche della macchina

I programmi risultano difficili da comprendere e da modificare.

La struttura logica del programma e nascosta

Difficile comprendere il programma e correggerlo in presenza di errori

Richiamo

L’esecutore di un programma opera ripetendo il ciclo

FetchDecode

Execute

I linguaggi ad alto livello

Linguaggi di programmazioneInsiemi di regole per costruire sequenze di istruzioni (cioe programmi)che possono essere direttamente eseguite da una macchina

Macchina fisicaE il processore, cioe l’esecutore dei programmi in linguaggio macchina

Macchina virtuale (per un dato linguaggio L)E un programma (detto interprete) che svolge il ruolo di esecutore peri programmi nel linguaggio L

Linguaggi ad alto livelloLinguaggi le cui istruzioni sono eseguibili da una macchina virtuale ingrado di effettuare operazioni piu complesse rispetto alle operazionielementari dei processori reali

Compilatori e interpreti

Compilatore E un programma che traduce un programma del linguaggio Lin un programma equivalente nel linguaggio macchina

Interprete E una macchina virtuale per un dato linguaggio. Operaripetendo il ciclo

1 Fetch: legge la prossima istruzione del programma2 Decode: traduce l’istruzione in corrispondenti istruzioni

del linguaggio macchina3 Execute: esegue le istruzioni del linguaggio macchina

Un compilatore puo anche tradurre un programma in un programmaequivalente in un linguaggio diverso dal linguaggio macchina

Interpreti

L’interprete “espande” ogni istruzione del linguaggio in una sequenza diistruzioni in linguaggio macchina

y <- x - (x/y)*y

LOAD R1 x

LOAD R2 y

DIV R1 R2

MUL R1 R2

LOAD R2 x

SUB R2 R1

STO R2 y

Interpreti

L’interprete “espande” ogni istruzione del linguaggio in una sequenza diistruzioni in linguaggio macchina

y <- x - (x/y)*y

LOAD R1 x

LOAD R2 y

DIV R1 R2

MUL R1 R2

LOAD R2 x

SUB R2 R1

STO R2 y

Compilatori

program Saluti;__________________________________________

Compilatore Pascal per X

Saluti.exe0110010...________________________________________

0110010...

Saluti

Programma Pascal

Macchina X

Portabilita del sorgente

Compilatore per Windows

Compilatoreper Linux

Compilatoreper MacOs

program p (input,output);var x:integer; ...

Programma Pascal

Eseguibile Eseguibile Eseguibile

Indipendente dalla

piattaforma

Dipendente dalla

piattaforma

Windows Linux MacOS

Java Virtual Machine (JVM)

Saluti.java__________________________________________

Compilatore(javac)

Saluti.class________________________________________

Interprete(java)

Saluti

0110010...

Il compilatore Java traduce il sorgente in un programma per illinguaggio bytecode

La Java Virtual Machine e un interprete per il bytecode

Vantaggi: portabilita del bytecode

class Saluti{...}

Programma Java

Compilatore

bytecode

Interpreteper Windows

Interpreteper Linux

Interpreteper MacOs

Linux MacOS

Indipendente dalla

piattaforma

Windows

Dipendente dalla

piattaforma

Vantaggi: leggerezza del bytecode

Saluti.java__________________________________________

Compilatore(javac)

Saluti.class________________________________________

Interprete(java)

0110010...

Saluti

Network

Strumenti per la stesura dei programmi

programmasorgente

compilatore

errori di compilazione

programmaoggetto

linkererrori

del linker librerie

eseguibile

esecutore

output ederrori diesecuzione

output

modifiche

Programmazione strutturata

Metodologia di programmazione introdotta agli inizi degli anni settanta.

La sequenza di esecuzione delle istruzioni (flusso di esecuzione) econtrollata da tre strutture di controllo fondamentali:

Sequenza permette di eseguire le istruzioni secondo l’ordine in cui sonoscritte

Selezione permette di scegliere l’esecuzione di un blocco di istruzionitra due possibili in base al valore di una condizione

Iterazione permette di ripetere l’esecuzione di una o piu istruzioni inbase al valore di una condizione

L’impiego di queste strutture migliora la leggibilita dei programmi

Ogni struttura di controllo ha un solo punto di ingresso e un solopunto d’uscita

Il flusso di esecuzione e evidente dalla struttura del codice

Teorema di Jacopini-Bohm (1966)

Le tre strutture di controllo fondamentali (sequenza, iterazione eselezione) sono sufficienti per implementare qualunque algoritmo.

Quindi una macchina virtuale per un linguaggio che comprende le trestrutture di controllo fondamentali e un computer universale.

Descriviamo le strutture di controllo utilizzando uno pseudo-codice

Sequenza

Le istruzioni sono eseguite nello stesso ordine in cui compaiono nelprogramma, cioe secondo la sequenza in cui sono scritte.

Example: Somma di due numeri

leggi i numeri a, bcalcola a + bscrivi il risultato

Selezione

Sintassi

SE condizioneALLORA

blocco1ALTRIMENTI

blocco2FINESE

Esecuzione

(1) Viene valutata condizione

se e vera vengono eseguite le istruzioni del blocco1

se e falsa vengono eseguite quelle del blocco2

(2) L’esecuzione procede con l’istruzione che segue immediatamente lafine del costrutto di selezione (FINESE)

Selezione

Sintassi

SE condizioneALLORA

blocco1ALTRIMENTI

blocco2FINESE

Esecuzione

Selezione

Sintassi

SE condizioneALLORA

blocco1ALTRIMENTI

blocco2FINESE

Esecuzione

Selezione

Sintassi

SE condizioneALLORA

blocco1ALTRIMENTI

blocco2FINESE

Esecuzione

Selezione

Sintassi

SE condizioneALLORA

blocco1ALTRIMENTI

blocco2FINESE

Esecuzione

Selezione (senza ALTRIMENTI)

Sintassi

SE condizioneALLORA

blocco1FINESE

Esecuzione

Viene valutata condizione:

quindi l’esecuzione riprende dalla prima istruzione che segueil costrutto di selezione

se e falsa l’esecuzione prosegue direttamente dalla prima istruzioneche segue il costrutto di selezione

Sintassi

SE condizioneALLORA

blocco1FINESE

Esecuzione

Sintassi

SE condizioneALLORA

blocco1FINESE

Esecuzione

Sintassi

SE condizioneALLORA

blocco1FINESE

Esecuzione

Esempio

Calcolo della divisione tra due numeri controllando che il divisore siadiverso da zero:

leggi il dividendo e il divisoreSE il divisore e diverso da zeroALLORA

calcola dividendo/divisorescrivi il risultato

ALTRIMENTI

scrivi “errore: divisione per zero”FINESE

Le strutture di controllo possono essere innestate

Esempio

Calcolo della divisione tra due numeri controllando che il divisore siadiverso da zero:

leggi il dividendo e il divisoreSE il divisore e diverso da zeroALLORA

calcola dividendo/divisorescrivi il risultato

ALTRIMENTI

scrivi “errore: divisione per zero”FINESE

Le strutture di controllo possono essere innestate

Esempio: calcolo delle radici di ax2 + bx + c = 0

leggi i valori dei parametri a, b, ccalcola il discriminante ∆ = b2 − 4acSE il discriminante e minore di zeroALLORA

scrivi “nessuna soluzione reale”ALTRIMENTI

SE il discriminante e uguale a zeroALLORA

calcola −b2ascrivi “Due soluzioni coincidenti: ”, il risultato

ALTRIMENTI

scrivi “Due soluzioni: ”,

calcola −b−√

∆2a e scrivi il risultato

calcola −b+√

∆2a e scrivi il risultato

FINESE

Iterazione (schema 1)

Sintassi

ESEGUI

bloccoQUANDO condizione

Esecuzione

(1) Viene eseguito blocco

(2) Viene valutata condizione:

se e vera si ritorna al punto (1)

se e falsa si prosegue con la prima istruzione scritta dopo ilcostrutto iterativo

il blocco e eseguito almeno una volta

termina quando la condizione diventa falsa

Sintassi

ESEGUI

Esecuzione

Sintassi

ESEGUI

Esecuzione

Sintassi

ESEGUI

Esecuzione

Sintassi

ESEGUI

Esecuzione

Sintassi

ESEGUI

Esecuzione

Esempio: somma dei primi 100 numeri interi

Calcolo iterativo, senza utilizzare la formula di Gauss (∑n

i=1 i = n(n+1)2 ).

poni il valore della somma a zeroinizia a considerare il numero 1ESEGUI

aggiungi alla somma il numero che stai considerandoconsidera il numero successivo

QUANDO il numero che stai considerando non supera 100scrivi la somma

Sintassi

QUANDO condizione ESEGUI

bloccoRIPETI

Esecuzione

(1) Viene valutata la condizione:

se e vera, viene eseguito bloccoquindi si torna al punto (1)

se e falsa, l’esecuzione riprende dalla prima l’istruzione che segue ilcostrutto iterativo

il blocco puo essere eseguito anche zero volte

Sintassi

bloccoRIPETI

Esecuzione

Sintassi

bloccoRIPETI

Esecuzione

Sintassi

bloccoRIPETI

Esecuzione

Sintassi

bloccoRIPETI

Esecuzione

Simulazione

Il comportamento dello schema QUANDO...RIPETI puo essere simulatocombinando ESEGUI...QUANDO... e selezione:

SE condizioneALLORA

ESEGUI

FINESE

Variabili e assegnamenti

Una variabile e un area di memoria che contiene un datoIl nome di una variabile e detto identificatore

Istruzione di assegnamento

variabile ← espressione

Esecuzione

(1) Viene calcolato il valore dell’espressione scritta a destra del simbolo ←

(2) Il risultato ottenuto e assegnato alla variabile (ovvero salvato nell’areadi memoria corrispondente) il cui nome e scritto a sinistra del simbolo←, eliminando l’eventuale valore precedentemente contenuto.

OsservazioneMolti linguaggi, tra cui anche Java, utilizzano per l’assegnamento ilsimbolo =, usato comunemente per indicare l’uguaglianza.

Esecuzione

Esempio

x ← y + z

1 si valuta l’espressione y+z, recuperando i valori presenti in y e z efacendone la somma

2 si pone il risultato nel contenitore di cui x e il nome dopo avereeliminato il valore precedentemente presente

Esempio

x ← y + z

Esempio

x ← y + z

Esempio

k ← k + 1

1 si valuta l’espressione k+1, recuperando il valore di k (3) esommandogli 1

2 si pone il risultato nel contenitore di cui k e il nome dopo avereeliminato il valore precedentemente presente

Esempio

k ← k + 1

Esempio

k ← k + 1

Esempio

k ← k + 1

Il tipo di una variabile specifica

la classe di valori che questa puo assumere

l’insieme delle operazioni che possono essere effettuate su di essa.

Ad esempio una variabile x di tipo intero

puo assumere come valori solo numeri interi

su di essa possono essere effettuate soltanto le operazioni consentiteper i numeri interi

Il tipo e utile per

allocare spazio sufficiente a memorizzare il valore di una variabile

verificare in fase di compilazione la correttezza di un programma

Il tipo e utile per

Astrazioni

Variabili

Il concetto di variabile e un’astrazione del concetto di locazione dimemoria

L’assegnamento di un valore a una variabile e un’astrazionedell’istruzione STORE

Sebbene tutte le variabili siano rappresentate nella memoria comesequenze di bit, tali sequenze possono essere interpretatediversamente in base ai tipi

La nozione di tipo fornisce un’astrazione rispetto allarappresentazione effettiva dei dati

Il programmatore puo utilizzare variabili di tipi differenti, senzanecessita di conoscerne l’effettiva rappresentazione

Astrazioni

Variabili

Il concetto di variabile e un’astrazione del concetto di locazione dimemoria

L’assegnamento di un valore a una variabile e un’astrazionedell’istruzione STORE

Sebbene tutte le variabili siano rappresentate nella memoria comesequenze di bit, tali sequenze possono essere interpretatediversamente in base ai tipi

La nozione di tipo fornisce un’astrazione rispetto allarappresentazione effettiva dei dati

Il programmatore puo utilizzare variabili di tipi differenti, senzanecessita di conoscerne l’effettiva rappresentazione

Dichiarazione delle variabili

Molti linguaggi richiedono di dichiarare le variabili utilizzate nelprogramma indicandone il tipo.

Vantaggi:

accresce la leggibilita dei programmi

diminuisce la possibilita di errori

facilita la realizzazione di compilatori efficienti

Dichiarazione delle variabili

Molti linguaggi richiedono di dichiarare le variabili utilizzate nelprogramma indicandone il tipo.

Vantaggi:

accresce la leggibilita dei programmi

diminuisce la possibilita di errori

facilita la realizzazione di compilatori efficienti

Esempio: calcolo delle radici di ax2 + bx + c = 0

variabili a, b, c, D, x, x1, x2: numeri reali

leggi a, b, c

D ← b2 - 4 * a * c

SE D < 0

ALLORA

scrivi “nessuna soluzione reale”ALTRIMENTI

SE D == 0

ALLORA

x ← - b / (2 * a)

scrivi “Due soluzioni coincidenti: ”, xALTRIMENTI

x1 ← (- b -√D) / (2 * a)

x2 ← (- b +√D) / (2 * a)

scrivi “Due soluzioni: ”, x1, x2FINESE

FINESE

Linguaggi di programmazione

Sintassi

Fornisce delle regole per la scrittura di programmi

Esistono vari formalismi per descrivere la sintassi di un linguaggio(forme di Backus-Naur, carte sintattiche, . . . )

Semantica

Determina il significato di un programma

Ovvero, le operazioni attuate dalla macchina che esegue il programma(semantica operazionale)

Solo i programmi sintatticamente corretti hanno una semantica, cioepossono essere eseguiti

Quando il compilatore (o l’interprete) incontra un errore di sintassi nelcodice si arresta segnalando il problema

Sintassi

Semantica

Sintassi

Semantica

Sintassi

Semantica

Programmi e algoritmi

ALGORITMI

PROGRAMMI

PROGRAMMI CORRETTI

PROGRAMMI TERMINANTI

Per codificare tutti gli algoritmi e necessario utilizzare i cicli

La presenza dei cicli rende possibile scrivere programmi non terminanti(contenenti cicli infiniti), che quindi non codificano nessun algoritmo

Sintassi e semantica

In astratto, la sintassi e definita da una grammatica

La grammatica e un modello generativo di tutti e soli i programmisintatticamente corretti

Sintassi dei numeri reali (ad esempio 3.14...)

<sequenza_cifre> ::= <cifra> | <cifra> <sequenza_cifre>

<cifra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Grammatica

G = (T ,N,P,S)

T insieme finito dei simboli terminali, cioe dei simboli checostituiranno i programmi

N insieme finito dei simboli non terminali, o metasimboli,utilizzati nella costruzione dei programmi

P insieme finito delle regole di produzione

S simbolo iniziale, S ∈ N ed e il punto di partenza nellacostruzione dei programmi

Linguaggio generato da G

L’insieme di tutte le sequenze di simboli terminali ottenibili applicando leregole di produzione dell’insieme P, a partire dal simbolo iniziale S .

Grammatica

G = (T ,N,P,S)

Grammatica

G = (T ,N,P,S)

Grammatica

G = (T ,N,P,S)

Grammatica

G = (T ,N,P,S)

Grammatica

G = (T ,N,P,S)

Esempio

(1) T = {il, lo, la, cane, mela, gatto, mangia, graffia, ,}

(2) N = {frase, soggetto, verbo, complemento, articolo, nome}

(3) P, regole espresse in BNF (forma di Backus-Naur):

(4) S = frase.

Esempio

(4) S = frase.

Esempio

(4) S = frase.

Esempio

(4) S = frase.

Esempio di produzione

��

articolo nome articolo nome complemento

articolo nome

soggetto verbo complemento

lo mela

graffia

lo gatto

il cane

Linguaggio Java: il lessico

AlfabetoL’alfabeto utilizzato per scrivere i programmi si chiama Unicode, ed eun insieme di caratteri rappresentati su 16 bit.

Parole riservate (o parole chiave)Sono parole che nel linguaggio hanno un significato predeterminato.Non possono essere utilizzate diversamente e non possono essereridefinite.

abstract assert boolean break byte case

catch char class const continue default

do double else enum extends final

finally float for goto if implements

import instanceof int interface long native

new package private protected public return

short static strictfp super switch synchronized

this throw throws transient try void

volatile while

Linguaggio Java: il lessico (2)

IdentificatoriSono nomi impiegati all’interno del programma per indicare variabili,classi, riferimenti a oggetti, e cosı via.Un identificatore e costituito da una sequenza di lettere e cifre cheinizia con una lettera

SeparatoriSono caratteri che permettono di separare o raggruppare parti dicodice.( ) { } [ ] ; , .

OperatoriSono simboli o sequenze di simboli che denotano alcune operazioni.= > < ! ~ ? :

== <= >= != && || ++ --

+ - * / & | ^ % << >> >>>

+= -= *= /= &= |= ^= %= <<= >>= >>>=

== <= >= != && || ++ --

+ - * / & | ^ % << >> >>>

+= -= *= /= &= |= ^= %= <<= >>= >>>=

== <= >= != && || ++ --

+ - * / & | ^ % << >> >>>

+= -= *= /= &= |= ^= %= <<= >>= >>>=

LetteraliSequenze di caratteri utilizzate all’interno dei programmi perrappresentare valori di tipi primitivi e stringhe.

Commenti

/*. . . */

il compilatore ignora tutto il testo compreso tra questi caratteri;possono estendersi per piu righe

/**. . . */

il compilatore ignora tutto il testo compreso tra questi caratteri;possono estendersi per piu righe. Sono chiamati commenti didocumentazione, vengono interpretati da javadoc

commenti a fine riga

si aprono con la coppia di caratteri // e si chiudono alla fine della riga;il compilatore ignora il testo che inizia dai caratteri // fino alla finedella riga.

Commenti

/*. . . */

/**. . . */

Commenti

/*. . . */

/**. . . */

Commenti

/*. . . */

/**. . . */

Il primo programma Java

/* Il nostro primo programma */

class BuonInizio {

// il metodo main

public static void main(String[] args) {

System.out.println("Ti auguro una buona giornata!");

In Java, ogni istruzione deve trovarsi all’interno di una classeIn ogni programma Java deve essere definito un metodo main (e non piudi uno) che indica alla JVM dove iniziare la computazione

BuonInizio.java

Computer, algoritmi e linguaggi - Capitolo 1homes.di.unimi.it/~cesabian/prog/c01-basi.pdf · Esami...

Documents

Transcript of Computer, algoritmi e linguaggi - Capitolo 1homes.di.unimi.it/~cesabian/prog/c01-basi.pdf · Esami...