1

Unità Didattica 1

Algoritmi

2

Analisi e Programmazione

• Insieme delle attività necessarie per la risoluzione dei problemi per mezzo di un elaboratore: dalla formulazione del problema alla predisposizione dell’elaboratore.

• Scopo dell’analisi è definire un algoritmo: elenco finito di istruzioni necessarie per risolvere una classe di problemi; in generale non può essere eseguito da un elaboratore;

• Scopo della programmazione è definire un programma. Un programma è la descrizione comprensibile ed eseguibile di un algoritmo da parte di un elaboratore

Problema

Analisi e Programmazione

Risultati

3

Algoritmi e ProgrammiProblema

Algoritmo

Programma

Risultati

Analisi

Diagramma a blocchi

Programmazione

Linguaggioprogrammativo

4

Algoritmi

• Un elenco di istruzioni è un algoritmo se sono soddisfatte le seguenti proprietà:

1. Finitezza: ogni istruzione deve essere eseguita in un tempo finito e un numero finito di volte;

2. Generalità: ogni algoritmo deve fornire la soluzione per i problemi appartenenti ad una determinata classe.

3. Non ambiguità: devono essere definiti in modo univoco tutti i passi; devono essere evitati paradossi, contraddizioni ed ambiguità.

5

Descrizione degli Algoritmi

• Uso di un linguaggio generalizzato costituito da strutture linguistiche prive di ambiguità e ridondanze;

• Uso di proposizioni (espressioni) composte da due parti:

1. Descrizioni delle operazioni (istruzioni);

2. Descrizione dei dati su cui eseguire le istruzioni.

6

Dati e Istruzioni• Dati:

– Costanti (valore invariabile all’interno dell’algoritmo);– Variabili scalari: <nome, valore> – Variabili vettoriali: <nome, insieme di valori>

(il valore delle variabili è indeterminato all’inizio di un algoritmo).

• Istruzioni:1. Istruzioni operative (producono risultati se eseguite);

2. Istruzioni di controllo (in funzione del verificarsi di condizioni determinano l’esecuzione

di alcune istruzioni piuttosto che di altre);

3. Istruzioni di salto (alterano l’ordine di esecuzione delle istruzioni);

4. Istruzioni di inizio e fine;5. Istruzioni di I/O (trasmissione dati o messaggi fra

l’ambiente esterno e l’algoritmo).

7

Proposizioni e predicati

• Come sono espresse le condizioni nelle istruzioni di controllo?– Le istruzioni di controllo verificano se una condizione è vera o falsa.– Il controllo viene espresso per mezzo di predicati.

• Proposizione:Costrutto del quale si può dire se è vero o falso.

• Predicato:Una proposizione è un predicato se in essa appaiono delle

variabili e il valore di verità delle variabili determina il valore di verità della proposizione.

I predicati si esprimono con operatori logici e relazionali.- Predicati Semplici: predicati di un solo operatore (NOT) e una sola

variabile;- Predicati Composti: predicati con operatori logici (AND, OR, NOT).

8

Tavole di Verità

• Tavole di Verità:– descrivono i valori di verità dei predicati in funzione dei valori di

verità delle singole parti.

– Esprimono le modalità con cui operano gli operatori relazionali.

• Esempi:

A B A and B

0 0 0

0 1 0

1 0 0

1 1 1

A B A or B

0 0 0

0 1 1

1 0 1

1 1 1

A not A

0 1

1 0

9

Diagrammi a Blocchi

• Esempio di un linguaggio generalizzato per la descrizione degli algoritmi;

• I blocchi contengono istruzioni elementari, la forma del blocco indica il tipo di istruzioni;

Inizio

Fine

LetturaScrittura Azioni Controllo

V F

10

Analisi Strutturata• Procedimento che permette di ottenere descrizioni di algoritmi

che siano facilmente documentabili e comprensibili;• Schemi di flusso:

– Schema di sequenza;

– Schema di selezione;

– Schema di iterazione:

Condizione di fine ciclo

Inizializzazione

F

Iterazione

VIterazione per falsocon controllo in coda

Condizione di fine ciclo

Inizializzazione

Iterazione

V

F

Iterazione per verocon controllo in testa

11

Diagramma a Blocchi Strutturati

• Uno schema di flusso è strutturato se i suoi blocchi sono collegati con gli schemi di flusso precedenti;

• Un diagramma a blocco è strutturato se sono strutturati tutti gli schemi di flusso che lo compongono;

• In un diagramma a blocchi strutturato non compare mai alcuna istruzione di salto;

12

Principio di Induzione

• Sia Pn una proposizione di cui si può dire se è vera o falsa

Hp) Sia P0 vera;

Supponendo Pn-1 vera, si dimostra che Pn è vera;

Ts) Pn è vera n.

13

Algoritmi Ricorsivi

• Un algoritmo si dice ricorsivo quando è definito nei termini di se stesso;

• È costituito da due parti:1. Passo base

(stabilisce il risultato per valori precisi dei dati iniziali);

2. Passo di induzione(risultato per n in funzione del risultato per n-1).

14

Esempi di algoritmi ricorsivi

• Potenza (definizione iterativa):

0

011 baa

ba

bb

volteb

........ aaaab

• Potenza (definizione ricorsiva):

15

Esempi di algoritmi ricorsivi

• Fattoriale (definizione iterativa):

11 ...)(! nnn

• Fattoriale (definizione ricorsiva):

01

01

nnn

nn

)!(!

16

Diagramma di Flusso del Fattoriale Ricorsivo

V F

Inizio

1fatt

0n

)!( 1 nnfatt

Fine

17

Sviluppo del Fattoriale Ricorsivo

!! 233

!! 122

!! 011

10 !Passo base

111011 !!

212122 !!

623233 !!

!! 344 2464344 !!