Dario Bianchi - 2003Fond. Informatica - Ing. Civile Fondamenti di Informatica Algoritmi Corso di...

Dario Bianchi - 2003 Fond. Informatica - Ing. Civile

Fondamenti di InformaticaAlgoritmi

Corso di Laurea in

Ingegneria Civile

Prof. Dario Bianchi


Elaborazione dell’Informazione

Risolvere un problema comporta:

• Avere dei dati in ingresso

• Elaborare questi dati

• Produrre dei dati in uscita

Bisogna quindi:

• Descrivere i dati

• Specificare come trattarli


Processi

• Un processo trasforma un insieme di dati iniziali nei risultati finali mediante una successione di azioni elementari.

• Per descrivere un processo e’ necessario utilizzare un linguaggio. Il linguaggio deve far corrispondere a una frase ben precisa o istruzione ad ogni azione elementare e deve indicare come le aziono elementari si succedono nel processo.


Programma, esecutore, algoritmo• L’insieme delle istruzioni che descrivono

un processo espresse in un qualche linguaggio prende il nome di programma.

• Il programma e’ espresso in termini di azioni elementari che un esecutore, uomo o macchina, deve essere in grado di mettere in atto.

• La descrizione rigorosamente definita di un processo (eseguibile in un tempo finito) e’ un algoritmo.


Requisiti degli algoritmi• Ogni istruzione deve essere ben definita

nei suoi effetti (rigorosamente e senza ambiguita`).

• Ogni istruzione rappresenta una azione elementare che che l’esecutore puo` portare a termine in un tempo finito.

• Il processo dall’algoritmo deve terminare dopo un numero finito di passi. ( un passo = esecuzione di una azione elementare)


Algoritmo di Euclide

• Calcola il massimo comun divisore fra due interi positivi m ed n (supponiamo che n ≥ m, altrimenti li possiamo scambiare).

• L’ algoritmo si compone di 3 passi ripetuti ciclicamente fino ad una condizione di arresto:


Algoritmo di Euclide

• Passo E1 {ricerca del resto} : Sia m ≥ n. Si divide m per n. Sia r il resto. Allora 0 ≤ r < n.

• Passo E2 {r = 0?} : Se r = 0 l’ algoritmo e’ terminato e n e’ la risposta finale.

• Passo E3 {scambio} : Se r ≠ 0 si operano gli scambi m ← n e n ← r. Si torni al passo E1.


Algoritmo di Euclide: esempio

m n r

45 30 15

30 15 0

Si voglia l’ MCD fra 30 e 45 (I due numeri vanno scambiati)

Poiche’ il resto r = o, l’ultimo valore per n e’ l’ MCD


Algoritmo di Euclide: finitezza• Poiche’ al passo E1 {ricerca del resto} si

ha senpre 0 ≤ r < n, ad ogni scambio il valore di n decresce.

• Dopo un numero finito di passi si raggiungera` la condizione r = 0, e la terminazione dell’ algoritmo.


Algoritmo di Euclide: correttezza• Ad ogni passo abbiamo che m = q n + r

(con q intero).• Se r ≠0 ogni divisore di m,n divide anche

r=m-qn. D’altra parte anche ogni divisore di n,r divide m=qn+r.

• In pratica la coppia m,n primo e dopo lo scambio m ← n e n ← r hanno lo stesso MCD.

• Se r=0 l’ algoritmo termina e n e’ l’MCD.


Il crivello di Eratostene• Si vogliono trovare tutti i numeri primi

compresi fra 2 e n (In modo efficiente).1) Si costruisca una sequenza ordinata dei numeri

fra 2 e n.

2) Si estragga il primo numero dalla sequenza. E’ necessariamente un numero primo.

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

4) se la sequenza non e’ vuota si torna la passo 2) altrimenti si termina.


Il crivello di Eratostene: esempio

• Sequenza iniziale (da 2 a 20):2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,202 e’ primo lo elimino con tutti i suoi multipli:3,5,7,9,11,13,15,17,193 e’ primo lo elimino con tutti i suoi multipli: 5,7,11,13,17,195 e’ primo lo elimino con tutti i suoi multipli: …19 e’ primo, la sequenza e’ vuota, termino.


Diagrammi di flusso

• Sono un linguaggio grafico per la rappresentazione di algoritmi

• Le operazioni su cui si basa un diagramma di flusso– Ingresso/Uscita dati– Trasferimento di informazione (Assegnamenti)– Calcolo di espressioni aritmetiche e logiche – Assunzione di decisioni– Esecuzione di iterazioni (Cicli)– Possono contenere costanti e variabili


Simboli

Start

Stop

Fine diagramma

ElaborazioneAssegnamenro

Inizio diagramma Lettura dati

Scrittura dati

Var

Var

Var = Expr

Si NoCondizione

Decisione

CondizioniExpr1 = Expr2 Expr1 ≠ Expr2Expr1 < Expr2 Expr1 > Expr2Expr1 ≤ Expr2 Expr1 ≥ Expr2

Linea di flusso


Programmazione Strutturata

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

• Ogni diagramma ha esattamente un ingresso ed una uscita.

• Ogni azione puo essere – una azione semplice– una azione composta da altri diagrammi

strutturati


Somma di tre numeriStart

X1

X2

X3

Somma←X1+X2+X3

Somma

Fine


Somma di N numeri

Somma

Fine

Start

N

X3Somma=0

I=0

I < N

Somma←Soma+XI=I+1

Si

X

N


Strutture per il controllo di flusso

• Sequenza

I

O

I

O



• Decisione If then

I

O

I

O

Vero

Falso

Cond

Azione



• Decisione If Then Else

I

O

I

O

Vero FalsoCond

Azione1 Azione2



• Ciclo While-Do

I

O

I

O

Cond

Vero

Falso

Azione



• Ciclo Repeat Until

I

O

I

O

Azione

Cond

Falso

Vero


Tecniche di programmazione

• Programmazione top-down:– scomposizione iterativa del problema in

sottoproblemi– i sottoproblemi devono essere indipendenti ed

avere interfacce ben definite– visibilità dei dettagli di ogni sottoproblema

solo all’interno del sottoproblema stesso

Dario Bianchi - 2003Fond. Informatica - Ing. Civile Fondamenti di Informatica Algoritmi Corso di...

Documents

Transcript of Dario Bianchi - 2003Fond. Informatica - Ing. Civile Fondamenti di Informatica Algoritmi Corso di...