Post on 27-Jun-2015
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