• Non ci sono risultati.

Laboratorio di Programmazione

N/A
N/A
Protected

Academic year: 2022

Condividi "Laboratorio di Programmazione"

Copied!
29
0
0

Testo completo

(1)

Laboratorio di Programmazione

Laurea in Ingegneria Civile e Ambientale

Algoritmi e Programmazione

Stefano Cagnoni

Dipartimento di Ingegneria dell’Informazione

Università degli Studi di Parma

(2)

Il problema di fondo

Descrizione di un problema

individuazione di una soluzione

Quale è il giusto punto di partenza? Cioè, di quali dati abbiamo bisogno ?

Quali metodologie o tecniche utilizzare?

In quale ordine eseguire le operazioni consentite da tali tecniche ?

(3)

Variabili (richiamo)

Costituiscono un’astrazione della memoria, cioè

tramite una variabile si fa riferimento ad una specifica area della memoria centrale.

Una variabile è caratterizzata da:

Un nome che la identifica

Un valore modificabile che viene associato al nome

Il risultato di un'espressione contenente variabili si ottiene sostituendo ad ogni variabile il suo valore.

L'operazione di assegnazione ( var = expr )

consente di assegnare il valore dell'espressione expr alla variabile var, quindi di modificare il valore di var

(4)

Risoluzione di problemi

Un ambiente di programmazione (come MATLAB) o applicazione di calcolo (come Excel) fornisce una serie di operatori di base e di funzioni per programmare il

computer a calcolare la soluzione, se esiste, di un problema.

Due casi

Foglio di calcolo (Excel): ogni soluzione è basata su funzioni definibili come singole formule a partire dagli operatori e dalle funzioni fornite dall’applicazione

Linguaggio di programmazione (MATLAB): definizione di una procedura (algoritmo) traducibile in un

programma utilizzando la sintassi del linguaggio.

(5)

Risoluzione di problemi

Esempio di soluzione diretta mediante calcolo di una singola espressione (può essere anche molto complessa):

Calcolo dell’area di un rettangolo:

Data la base B e l’altezza H l’area A si calcola con la formula A = B * H

Ho a disposizione l’operatore * (moltiplicazione) e lo uso per definire una funzione area(B, H) come prodotto delle due variabili B e H in cui inserisco i valori che descrivono il rettangolo che mi

interessa.

(6)

Risoluzione di problemi

Esempio di soluzione mediante algoritmo:

Calcolo del massimo M fra tre numeri C, D, E:

se C > D

se C > E M = C altrimenti M = E altrimenti (cioè se D >= C)

se D > E M = D altrimenti M = E

(7)

Algoritmo

Dall'arabo al-Khuwarizmi, e dal greco arithmós

Un algoritmo è un metodo generale che risolve

in un tempo finito e con una sequenza finita di

passi qualsiasi istanza di un dato problema.

(8)

Algoritmo: esempio

Problema generale: Calcolare la somma di un numero arbitrario N di numeri.

Se sono in grado di fare la somma fra 2 numeri risolvo il problema per qualsiasi valore di N con una stessa

sequenza di operazioni:

Poni totale=0;

Per N volte: somma un nuovo addendo a totale.

Infatti, sommare un nuovo numero alla somma dei precedenti è ancora una somma fra due numeri!

Ad ogni valore di N corrisponde una diversa istanza del problema generale, ma tutte le istanze possono essere risolte mediante lo stesso algoritmo

(9)

Algoritmo

E’ possibile definire algoritmi anche per la risoluzione di problemi non informatici

Esempi:

Descrivere come raggiungere una destinazione

Istruzioni per il montaggio di un mobile

Istruzioni per la realizzazione di una torta

Non sempre la soluzione di un problema può essere descritta tramite un algoritmo.

Il calcolo di p non è un algoritmo (non ha fine)

Il calcolo di p fino alla decima cifra decimale è un algoritmo

(10)

Codifica di un algoritmo

Fase di descrizione (scrittura) di un algoritmo

attraverso un insieme ordinato (sequenza) di codici (istruzioni, ciascuno dei quali rappresenta

un’operazione), appartenenti a un qualche

linguaggio di programmazione, che specificano le azioni da compiere e l’ordine in cui devono essere eseguite

Il prodotto della codifica è un programma

(11)

Programma

Testo scritto in accordo alla sintassi (insieme di regole sulla formazione delle espressioni in un

linguaggio) e alla semantica (insieme di regole che consentono l’interpretazione del significato del testo) di un linguaggio di programmazione

Un programma rappresenta l’insieme delle istruzioni che descrivono un processo computazionale,

espresse in un qualche linguaggio

Un processo trasforma un insieme di dati iniziali nei risultati finali mediante una successione di azioni elementari (operazioni)

(12)

Programma

Un programma può non descrivere un algoritmo (basta che la sequenza di operazioni non sia

finita, cioè che il programma non termini) …

... tuttavia può essere ugualmente molto utile Es. gestione di un semaforo: non ha fine poiché

ripete indefinitamente la stessa sequenza

(13)

Esecuzione

L’esecuzione delle azioni nell’ordine specificato dall’algoritmo consente di ottenere i risultati che risolvono il problema a partire dai dati in

ingresso

 algoritmo  programma

Metodo risolutivo

Codifica del metodo in un linguaggio di programmazione

(14)

Algoritmo

Un algoritmo deve avere le seguenti proprietà:

Finitezza: deve essere composto da un numero finito di passi elementari.

Non ambiguità (determinismo): i risultati non variano in funzione della macchina/persona che esegue

l'algoritmo.

Realizzabilità: deve essere eseguibile con le risorse a disposizione.

Efficienza (auspicabile): deve eseguire il minimo numero possibile di operazioni

(15)

Algoritmo

Per definire un algoritmo è necessario:

Condurre un'attenta analisi del problema ed eventualmente suddividere il problema in sottoproblemi più piccoli.

Individuare le informazioni disponibili in ingresso (input) e precisare le informazioni che devono essere prodotte dall’elaborazione (output), cioè definire i dati di input e di output.

Definire completamente e dettagliatamente la sequenza dei passi che portano alla soluzione.

(16)

Il crivello di Eratostene

Si vogliono trovare tutti i numeri primi compresi fra 2 e n (in modo efficiente).

1. Si costruisce una sequenza ordinata dei numeri fra 2 e n.

2. Si estrae il primo numero dalla sequenza. E’

necessariamente un numero primo.

3. Si eliminano dalla sequenza tutti i multipli del numero estratto al passo 2.

4. Se la sequenza non è vuota si torna al passo 2, altrimenti si termina.

(17)

Il crivello di Eratostene

Esempio :

trovare i numeri primi compresi fra 2 a 20

Sequenza iniziale:

2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20

2 è primo; lo elimino con tutti i suoi multipli:

3,5,7,9,11,13,15,17,19

3 è primo; lo elimino con tutti i suoi multipli:

5,7,11,13,17,19

5 è primo; lo elimino con tutti i suoi multipli:

…7 … 11 … 13 … 17 … (li estraggo allo stesso modo)

19 è primo, la sequenza è vuota, termino.

(18)

Diagrammi di flusso (Flow Chart)

I diagrammi di flusso sono un formalismo grafico per descrivere gli algoritmi.

I diagrammi di flusso visualizzano graficamente i passi da cui sono formati gli algoritmi e l’ordine in cui devono essere eseguiti.

Un diagramma di flusso è una descrizione formale, (cioè rispetta una precisa sintassi), più efficace e meno ambigua di una descrizione a parole.

(19)

Diagrammi di flusso

Operazioni rappresentabili in un diagramma di flusso:

Ingresso/Uscita dati (rappresentate come schede)

Operazioni sui dati (rappresentate come rettangoli)

Trasferimento di informazione (assegnazioni)

Calcolo di espressioni aritmetiche e logiche

Verifica di condizioni (rappresentate come rombi)

Assunzione di decisioni o cicli (combinazioni di rettangoli e rombi)

Se… allora …

Ripeti per N volte

Ripeti finché ….

Possono utilizzare costanti e variabili

(20)

Diagrammi di flusso

Un diagramma di flusso è costituito da due tipi di entità:

Nodi

rappresentano le operazioni e gli stati di inizio e fine dell’algoritmo

Archi orientati (di solito in realtà sono segmenti di retta orientati secondo la direzione di una freccia)

Collegano fra loro i nodi, rappresentando con frecce il

‘flusso’ dei dati, cioè la sequenza delle operazioni:

l’istruzione contenuta in un nodo è seguita

dall’esecuzione dell’operazione contenuta nel nodo a cui punta l’arco uscente da esso

Una struttura di questo tipo è detta grafo (orientato)

(21)

Tipi di Nodi

Inizio

Scrittura dati (output)

Var1

Lettura dati (input)

Var1

Elaborazione / Assegnazione

Var1  Espr1

Decisione

No

Espr1 = Espr2 Espr1  Espr2 Espr1 > Espr2 Espr1  Espr2 Espr1 < Espr2 Espr1  Espr2

Start

Fine

Stop

(22)

Esempio

Var1 Var1

Start

Stop

Inizio

Leggi un valore (ad es. 10) che sarà assegnato alla variabile Var1

Stampa il contenuto di Var1 (stampa 10)

Fine

(23)

Esempio 2

Var1 Var1

Var1  Var1 + 1

Start

Stop

Inizio

Leggi un valore (ad es. 10) e inseriscilo nella locazione di memoria

corrispondente alla variabile Var1 Aggiungi 1 a quel valore

Stampa il nuovo valore (stampa il contenuto di Var1 cioè 11) Fine

(24)

Esempio 3

Var1 Var1

Var1  Var1 + 1

No

Start

Stop

Var1 > 10 Se Var1 > 10

stampa Var1 Altrimenti

incrementa di 1 Var1 e poi stampa Var1

Inizio

Leggi Var1

Fine

(25)

Strutture di Controllo

Ciclo While Ciclo For

No

Ripete una stessa operazione (o

sequenza) O finché la condizione C

resta vera

C

O

Ciclo Repeat - Until

No

O C

Ripete una stessa operazione (o

sequenza) O finché la condizione C non diventa vera

If - Then - Else

No

O2 O1

C

Se C è vera esegue l’operazione (o

sequenza) O1, altrimenti esegue O2

(26)

Programmazione Strutturata

Si compone di sequenze di azioni, decisioni (if then, if then else) e cicli (do-while, repeat until).

Ogni diagramma ha esattamente un ingresso ed una uscita

Ogni azione può essere

Un’operazione semplice

Un’ azione composta da altri diagrammi strutturati

(27)

Esempio: Somma di due Numeri

Start

Var1

Var2

Somma  Var1 +Var2

Somma

Stop

(28)

Esempio: Somma di N Numeri

Start

N Somma  Somma + Var

Somma

Stop I  0

Somma  0

No I < N Var

I  I + 1

(29)

Esercizi

Sulla base di quanto visto per la somma di N numeri

Definire un algoritmo per il calcolo del prodotto di N numeri

Descriverlo attraverso un opportuno diagramma di flusso

Descrivere il diagramma di flusso di un algoritmo che calcola l’area di triangoli o rettangoli:

Inizialmente il programma deve chiedere quanti lati ha la figura di cui si vuole calcolare l’area

Poi chiede base e altezza e calcola l’area mediante la giusta formula per la figura considerata.

Riferimenti

Documenti correlati

Al pari delle altre tipologie di sistemi di risose ad accesso aperto (valli da pesca, foreste, informazione, conoscenza) il tema cruciale è spesso la scala di

[r]

Nascono i sistemi a chiave asimmetrica, composti da una chiave pubblica, nota a tutti ed usata per la cifratura, e da una chiave privata,.. nota ad una sola persona ed usata per

Perch´ e la complessit` a delle operazioni su Tabelle Hash viene studiata al caso medio e non al

Irroratela quindi con un quarto di litro di vino e con altrettanto fumetto di pesce, poi passatela nel forno a 150 gradi per 45 minuti circa, unendo, a metà cottura, i

 Se nessuna variabile artificiale è ancora in base, ho una base fatta da sole colonne del problema originario e posso partire con Fase 2 su esso.  Se ho ancora variabili

Definito (non--ambiguo) ambiguo), , ogni istruzione deve essere elementare e deve consentire un’interpretazione.. elementare e deve consentire un’interpretazione

Poiché la stam- pa della soluzione finale sul file di testo dovrà riportare il costo totale della soluzione, gli indici delle colonne selezionate ed i relativi costi, oltre al