Algoritmi e diagrammi di flusso

Corso di Informatica di BaseA.A. 2011/2012

Luca Tornatore

Cos’è l’informatica? Calcolatore: esecutore di ordini o automa Programma: insieme di istruzioni che possono essere

eseguite da un elaboratore elettronico Programmatore: colui che individua la sequenza di

ordini per risolvere un problema (c’è differenza tra programmatore e Informatico?!?)

Informatica: Informazione + AutomazioneSi riferisce ai processi e alle tecnologie che rendono

possibile l’immagazzinamento e l’elaborazione dell’informazione mediante macchine

Modello Semplificato(grezzo)

Dati in Ingresso Dati in Uscita

Operazioni sui dati

Abbiamo detto che… L’Informatica è la Scienza della

Rappresentazione e dell’Elaborazione dell’Informazione

Secondo la ACM (Association for Computing Machinery)…

L’Informatica è lo Studio sistematico degli algoritmi che descrivono e trasformano l’Informazione: la loro teoria, analisi, progetto, efficienza, realizzazione e applicazione.

Risoluzione di un problema: Esecuzione Automatica

L’uomo descrive l’algoritmo che la macchina deve seguire per risolvere il problema (ad esempio con i Diagrammi di flusso)

Algoritmo

Programma

Linguaggio Macchina

La descrizione viene tradotta in Linguaggio di alto livello (ad esempio il linguaggio C)

Il programma di alto livello viene tradotto in linguaggio Macchina, ovvero codice binario (ad esempio dalcompilatore)

MacchinaInput

Output

Problema

Cosa è un algoritmo? Dato un problema, un algoritmo è una procedura,

cioè una sequenza di passi, che può essere eseguita automaticamente da una macchina in modo da risolvere il problema dato. Non tutti i problemi sono risolvibili. Un problema

risolvibile con un algoritmo si dice computabile

Esempio di Algoritmo

La torta al cioccolato

1. Abbiamo gli ingredienti (uova, farina, latte, ecc..) con le giuste quantità

2. Seguiamo la ricetta

3. Serviamo la torta

L’Algoritmo della Somma

1. Sposta una pallina da sinistra a destra della prima riga e una da destra a sinistra nella terza riga

3. Sposta una pallina da sinistra a destra della seconda riga e una da destra a sinistra nella terza riga

2. Ripeti 1. fino ad esaurire la prima riga

4. Ripeti 3. fino ad esaurire la seconda riga. Il risultato è

il numero di palline a sinistra sulla terza riga

Esempio

Risoluzione di un problema

Generalmente la risoluzione di un problema consiste nel prendere alcuni dati iniziali (input) relativi al problema e nel fornire un risultato (output) che risolve quest’ultimo

EsecutoreInput Output

Algoritmo

Infatti…Problema Risolutore Algoritmo

Esecut ore

Processo di Esecuzione

… la risoluzione automatica prevedeuna notevole componente umana!!!

Definizione di algoritmo (Formale) Un algoritmo è una sequenza ordinata e finita di passi

(azioni o istruzioni) che producono un ben determinato risultato in un tempo finito

Caratteristiche di un algoritmo1. Azioni eseguibili e non ambigue

1. Non sono ammessi “un pò” e “a piacere”, che non sono termini adatti ad una macchina

2. Deterministico1. Fatto un passo, il successivo è uno ed uno solo, ben

determinato. Alternative sono possibili, ma la scelta deve essere unica

3. Numero finito di passi4. Terminazione

1. L’esecuzione prima o poi deve finire e produrre un risultato in tempo finito

2. Osservazione: la 3 non implica la 4

Esempio di non terminazione Stampare tutti i numeri successivi ad N

1. Si consideri il numero N2. Scrivere il numero successivo ad N3. Ripetere il passo precedente

Trova il più grande numero primo Non esiste un programma che riesce a dare una risposta

in tempo finito (Numero finito di passi)

Codifica dell’Algoritmo Affinchè una macchina riesca a comprendere ed

eseguire i passi specificati da un algoritmo, quest’ultimo deve essere prima codificato in un opportuno programma scritto in un linguaggio ad alto livello (che verrà successivamente compilato/interpretato)

Algoritmo Traduzione Programma

Descrizione di un algoritmo

Si descrive un algoritmo cercando di sintetizzare il più possibile la sua sequenza di passi.

La descrizione avviene mediante: Pseudo-Codice, oppure Diagramma di flusso

Diagramma di Flusso I diagrammi di flusso permettono di descrivere in

modo grafico le azioni che costituiscono un algoritmo e il loro flusso di esecuzione.

Ogni azione elementare è rappresentata da un blocco. Esistono diversi tipi di blocchi Prenderemo in esame solo 4 tipi di blocchi

Istruzioni di inizio e fine

Inizio

Fine

In degree: 0Out degree: 1

In degree: 1Out degree: 0

Operazioni di input e output

Leggi Dato Scrivi Dato

In degree: 1Out degree: 1

In degree: 1Out degree: 1

Istruzioni imperative Azioni oppure operazioni

Calcola: 10+2

In degree: arbitrarioOut degree: 1

Connettori I singoli diagrammi devono essere uniti tramite i

connettori. L’esecuzione delle istruzioni deve essere fatta

sequenzialmente, ovvero seguendo i connettori. Quando si scrive l’algoritmo bisogna fare molta

attenzione alla direzione del flusso di esecuzione.

Istruzione di Assegnamento Una variabile numerica è una entità caratterizzata da

Un nome, e Un valore (contenuto)

Può cambiare nel tempo

Una costante numerica è una entità caratterizzata da Un nome, e Un valore (contenuto)

Non può cambiare nel tempo

Istruzione di Assegnamento Un’espressione è una combinazione di operatori

aritmetici, costanti e variabili che può essere calcolata generando un singolo valore numerico ES: X, X+1 X+(Y*3)

Istruzione di assegnamento: “” VariabileEspressione ES: Z3 ZX+3

Somma di due numeri Leggo il valore di x e y Calcolo la somma e la

pongo in Z Stampo il valore

contenuto in z

Inizio

Leggi X

Leggi Y

ZX+Y

Scrivi Z

Fine

Scambio di 2 variabili Leggo il valore di x e y Copio il valore di y i una

variabile d’apoggio Copio x in y (sovrascrivo

y) Copio aux in x Stampo il valore di x e y

Inizio

Leggi X

Leggi Y

AuxY

YX

XAux

Scrivi Y

Scrivi X

Fine

Flusso di esecuzione Si possono avere casi in cui nel flusso di esecuzione si

deve scegliere tra diverse direzioni La direzione da scegliere è subordinata al verificarsi

di una condizione La condizione può assumere due stati: Vero, Falso In questi casi si parla di istruzione condizionale

Istruzioni condizionali

Condizione

Vero

Falso

In degree: arbitrarioOut degree: 2

I connettori OutSono etichettati

Massimo tra 2 numeriInizio

Leggi X

Leggi Y

X>Y

Scrivi YScrivi X

FalsoVero

Fine

Strutture di controlloWhile

Do-WhileIf-then-else

No

Si

Si No

Si No

Somma IterativaInizio

Leggi X

Leggi Y

Z Z+1X X-1

Scrivi Z

FineZ0

X=0

Z Z+1Y Y-1

No No

Si Y=0

Gli Array Gli array o vettori sono una struttura dati Gli elementi di una array sono tutti dello stesso tipo

(es. numeri) La dimensione della struttura è definita a priori A[1..10] indica un array chiamato A composto da 10

elementi. A[1], A[2], …. , A[10].

Gli Array L’elemento generico lo posso indicare con A[i]

con 1 ≤i ≤10 i indica quindi la posizione A[i] il contenuto

A[1] A[i] A[10]

Riempire un Array i=1 indica la posizione di

partenza i ≤10 indica la posizione

finale i++ indica di

incrementare la posizione di una unità

Per 1 ≤ i≤10 leggi A[i]

Start

i=1

Leggi A[i]

i≤10

i++

End Si

No

Stampare un Array i=1 indica la posizione di

partenza i ≤10 indica la posizione

finale i++ indica di

incrementare la posizione di una unità

Per 1 ≤ i≤10 leggi A[i]

Start

i=1

Scrivi A[i]

i≤10

i++

End

Si No

Stampare gli elementi di posto pari i=2 indica la posizione di

partenza (la prima posizione pari)

i ≤10 indica la posizione finale

La posizione dovrà essere incrementata di 2 unità

Per 1 ≤ i≤10 scrivi A[i]

Start

i=2

Scrivi A[i]

i≤10

i=i+2

End

Si

Stampare la 2a metà di un Array i=6 indica la posizione di

partenza i ≤10 indica la posizione

finale i++ indica di

incrementare la posizione di una unità

Per 1 ≤ i≤10 leggi A[i]

Start

i=6

Scrivi A[i]

i≤10

i++

End Si

No

Calcolare la media di un Array i=1 indica la posizione di

partenza S=0 inizializzo la somma i ≤10 indica la posizione

finale i++ indica di incrementare

la posizione di una unità Per ogni ciclo sommo A[i]

alla somma S Terminato il ciclo calcolo e

stampo la media

Start

i=1S=0

S=S+A[i]

i≤10

i++End

M=S/10

Scrivi M

No

Si

Trovare il max di un Array Assumpo che il max è

quello contenuto nella prima posizione

i=2 indica la posizione di partenza

i ≤10 indica la posizione finale

i++ indica di incrementare la posizione di una unità

Per ogni ciclo sommo A[i] Terminato il ciclo calcolo e

stampo la media

Start

Max= A[1]i=2

Max=A[i]

i≤10

i++

End

Scrivi Max

A[i]>Max

Si

Si

No

No

Array bidimensionale o Matrice Sino ad ora abbiamo trattato array o vettori

monodimensionali Potremmo lavorare con array bidimensionali Dove abbiamo righe e colonne L’elemento generico lo indicheremo con A[i,j]

con 1≤i≤max colonne e con 1≤j≤max righe Gli array bidimensionali vengono anche chiamati

matrici Le immagini sono delle matrici (una per ciascun

piano RGB)

A[1,1] A[1,2] A[1,3] A[1,maxC]

A[2,1] A[2,2]

A[i,j]

A[maxR,1] A[maxR, maxC]