Da Vinci Sapri 3^A Da Vinci Sapri 3^A AFMAFM

Problema: dati i voti di tutti gli studenti di una classe determinare il voto medio della classe.

1) Comprendere il problema2) Stabilire quali sono le azioni da eseguire per

risolverlo3) Stabilire la sequenza di queste azioni (per

ricavare la media devo prima sommare gli n voti)una sequenza finita di azioni che conduce alla

soluzione di un problema si definisce ALGORITMO

2

3

Definizione: Procedimento di calcolo che permette di risolvere un problema, partendo da dei dati iniziali ed eseguendo un numero finito di operazioni o istruzioniIl termine algoritmo si fa derivare dal nome del matematico persiano Al-Khwarizmi, vissuto nel IX secolo, ed è quindi un concetto che è sempre stato utilizzato nella matematica e nella logica come sinonimo di metodo per la risoluzione di un problema generale.

Esempi di algoritmi per la soluzione di problemi di vita quotidiana sono:

le istruzioni per l’uso di un elettrodomestico la realizzazione di una ricetta di cucina

4

1) dati iniziali e finali: sono gli elementi che vengono elaborati dall’algoritmo (dati iniziali o di input) e i risultati prodotti dall’algoritmo (dati finali o di output). Es. nell’algoritmo dell’addizione, i dati iniziali sono gli addendi, il dato finale è la somma.

2) sequenza di azioni (istruzioni o passi elementari): un’azione è un’istruzione (operazione elementare) che deve essere eseguita sui dati in ingresso per ottenere i dati in uscita.

3) esecutore: è il soggetto che compie le azioni, cioè legge le istruzioni, le interpreta e le esegue.Le istruzioni quindi devono essere scritte in modo che l’esecutore possa comprenderle ed eseguirle correttamente.

ALGORITMO +ESECUTORE

DATI DI INPUT

DATI DI OUTPUT

5

FINITO: un algoritmo deve essere composto da un numero finito di passi e deve presentare un punto di inizio e uno di fine, raggiunto il quale si interrompe l’esecuzione delle operazioni.

DETERMINISTICO: l’algoritmo a fronte degli stessi dati di input deve produrre gli stessi risultati (es. l’istruzione “moltiplica 2x5” produce sempre il medesimo risultato, mentre l’istruzione “tira una freccia contro il bersaglio” può avere risultati diversi anche se è rivolta al medesimo arciere munito del suo solito arco).

NON AMBIGUO: i passi che compongono l’algoritmo devono essere interpretati in modo chiaro dall’esecutore, senza lasciar dubbi (es. “se il numero è abbastanza grande allora dividilo per 3 istruzione ambigua!)

L'algoritmo può essere rappresentato in:

◦ PSEUDOCODIFICA: PSEUDOCODIFICA: descrizione di un algoritmo utilizzando termini del linguaggio comune. Non si tratta di un vero e proprio linguaggio di programmazione (non è direttamente interpretabile dal computer), ma di un linguaggio sintetico che descrive la soluzione logica del problema.

◦ DIAGRAMMI A BLOCCHI: DIAGRAMMI A BLOCCHI: linguaggio formale di tipo grafico per rappresentare l’ordine di esecuzione delle istruzioni negli algoritmi.

6

Utilizzando la pseudocodifica, il programmatore esprime le proprie idee attraverso frasi elementari della lingua italiana (o inglese).

Le regole generali della pseudocodifica sono:

Le parole chiave che aprono e chiudono il testo di un algoritmo sono: INIZIO e FINE  (BEGIN e END)Le istruzioni LEGGI e SCRIVI (READ e WRITE) vengono utilizzate per descrivere le operazioni input ed output dei dati. Ogni istruzione è indicata con una frase del linguaggio corrente e può essere un‘operazione oppure può indicare una decisione da prendere

7

8

Problema:Problema: Calcola la media di 3 numeri interi

Analisi del problema:Analisi del problema:Dati di INPUT: 3 numeri inseriti da tastiera.Dati di OUTPUT: La media mostrata su monitor.

Pseudocodifica:Pseudocodifica:INIZIOLEGGI (n1, n2, n3);somma (n1+n2+n3);media (somma/3) ;SCRIVI (media);FINE

Un algoritmo può essere rappresentato anche attraverso un diagramma a blocchi (o flow chart) : Un particolare simbolo grafico detto blocco elementare è associato a ciascun tipo di istruzione dell’algoritmo.

I blocchi sono collegati fra loro tramite frecce che indicano il susseguirsi delle istruzioni.

9

10

INIZIO

FINEquesti simboli indicano il punto di partenza e di terminazione dell’algoritmo

è il simbolo dell’elaborazione e contiene l’istruzione da eseguire

è il simbolo per le operazioni di Input / Output

condizioneVF

è il simbolo di decisione ed è usato per stabilire se una proposizione è vera (V) o falsa (F)

11

INIZIOLEGGI (n1, n2, n3);somma (n1+n2+n3);media (somma/3) ;SCRIVI (media);FINE

Pseudocodifica:Pseudocodifica:INIZIOINIZIO

FINEFINE

Leggi(n1, n2, n3)Leggi(n1, n2, n3)

Scrivi(media)Scrivi(media)

somma=(n1+n2+nsomma=(n1+n2+n3)3)

media=(somma/3)media=(somma/3)

Problema:Problema: Calcola la media di 3 numeri interi

Analisi del problema:Analisi del problema:Dati di INPUT: 3 numeri inseriti da tastiera.Dati di OUTPUT: La media mostrata su monitor.

Diagramma a blocchiDiagramma a blocchi

Un diagramma a blocchi descrive un algoritmo se:

ha un blocco iniziale e uno finale;

è costituito da un numero finito di blocchi azione e/o blocchi lettura/scrittura e/o blocchi di controllo;

Vediamo un esempio di diagramma a blocchi per un semplice problema di geometria…

 12

Pseudocodifica: Diagramma a blocchi:

13

INIZIOINIZIO

FINEFINE

Leggi(base, Leggi(base, altezza)altezza)

Scrivi(area)Scrivi(area)

area=base*altezzarea=base*altezzaa

14

INIZIO

FINE

area = raggio * raggio * π

raggioI

areaO

INIZIO

FINE

area = raggio * raggio * π

raggioI

areaO

raggio = 0VF

area = 0

Cosa calcola questo algoritmo?

PROBLEMA PROBLEMA ALGORITMO PROGRAMMAALGORITMO PROGRAMMA

 1. 1. Analisi del problema e identificazione di

una soluzione;2. 2. Stesura dell’algoritmo risolutivo;3. 3. Programmazione, cioè scrittura

dell’algoritmo in un linguaggio adatto al computer;

4. 4. Esecuzione del programma sul computer e verifica del suo funzionamento

Attenzione: l’algoritmo è indipendente dal linguaggio di programmazione!

15

11 22 33 44

I computer usano il sistema binario costitutito dai simboli (0,1) e di conseguenza non possono interpretare e comprendere il nostro linguaggio. Il linguaggio del computer, basato sui simboli binari (bit) si chiama LINGUAGGIO MACCHINA (codice macchina o linguaggio di basso livello) ed è costituito da una serie di istruzioni direttamente eseguibili per il computer.

Per permettere la comunicazione tra “uomo” e “macchina” sono stati creati i LINGUAGGI DI PROGRAMMAZIONE (linguaggi ad alto livello o procedurali).

16

I LINGUAGGI DI PROGRAMMAZIONE permettono di scrivere i programmi, cioè di “tradurre” un algoritmo in un linguaggio più comprensibile al computer, ma non direttamente eseguibile.Il programma scritto in linguaggio di programmazione si chiama programma sorgente e per essere eseguito da una macchina deve essere compilato, cioè trasformato in LINGUAGGIO MACCHINA. Questa trasformazione viene fatta da un programma che si chiama COMPILATORE. 17

Linguaggio naturale

Linguaggio macchina

Linguaggio di programmazione

COMPILATORE

PROGRAMMA SORGENTE

18

19

20

Una proposizione di un linguaggio è un’affermazione che può avere valore vero o falso.Esempio: Gli alunni studiano

Un connettivo logico, o operatore logico, è un’operazione che stabilisce una relazione fra due proposizioni e che restituisce un valore vero o falso.Esempio:

Oggi prima studio E poi esco con gli amiciNON è vero che stavo parlandoPer andare a scuola prendo il treno O prendo l’autobus

21

Anche i dati del computer sono messi in relazione dai connettivi logici, i più importanti dei quali sono AND, OR e NOTNOT=negazione (es: Bocciato= NOTPromosso)AND=congiunzione, il risultato è vero se entrambe le affermazioni sono vere. (es: l’alunno sarà promosso se studia AND si comporta bene)OR= disgiunzione, il risultato è vero se almeno una delle due proposizioni è vera (l’alunno è giustificato dal padre OR dalla madre)

22