Algoritmi

2

Algoritmo

• Un metodo preciso e sistematico per ottenere uno specifico risultato

• Ne abbiamo già incontrati diversi:– riconoscimento del clic di un pulsante

– la tecnica del segnaposto

– conversione esadecimale/binario e viceversa

3

Algoritmi nella vita quotidiana

• alcuni li abbiamo imparati a scuola – per esempio le operazioni aritmetiche

• alcuni li abbiamo ricostruiti da soli – come la ricerca di un numero telefonico

• altri hanno istruzioni scritte – le ricette di cucina, le istruzioni di assemblaggio dei mobili, le mappe stradali...

4

Le cinque proprietà essenziali degli algoritmi

1. Input specificato– i dati che saranno trasformati attraverso i calcoli

per produrre l’output

– devono specificare il tipo, la quantità e la forma che dovranno avere i dati

2. Output specificato– il risultato della computazione

– talvolta è possibile non avere alcun output

5

Le cinque proprietà essenziali degli algoritmi (cont.)

3. Determinatezza– la sequenza degli eventi dev’essere specificata

– ogni passo dev’essere descritto in ogni suo aspetto, inclusa la gestione degli errori

4. Efficacia– le operazioni devono essere effettivamente

eseguibili da parte dell’agente

5. Terminazione– l’elaborazione deve giungere al termine in un

tempo finito

6

Algoritmi e linguaggi

• Linguaggio naturale– utilizzato dalle persone: noi usiamo un

linguaggio naturale come l’italiano

– l’ambiguità è comune nei linguaggi naturali

• Linguaggi di programmazione– linguaggi formali progettati per esprimere

algoritmi

– hanno una definizione precisa; non ci sono ambiguità

7

Programmi e algoritmi

• Un programma è un algoritmo concepito per operare in un determinato insieme di circostanze ed espresso in un particolare linguaggio

8

Un algoritmo: Ordina CD

• Immaginate dei CD disposti in modo disordinato su uno scaffale

• Volete ordinarli alfabeticamente in base al nome del gruppo, del cantante o del compositore

• Come risolvere questo problema?

9

Ordina CD (cont.)

• Input: una sequenza non ordinata di CD che riempie una scaffalatura

• Output: gli stessi CD nella stessa scaffalatura, ordinati alfabeticamente

• Istruzioni:1. Usiamo il termine Artista per riferirci al nome del gruppo,

del cantante o del compositore di un CD

2. Decidete quale estremo della rastrelliera corrisponde all’inizio della sequenza alfabetica e chiamate Alfa la prima posizione di quell’estremo

3. Chiamate Beta la posizione immediatamente adiacente ad Alfa

10

Ordina CD (cont.)

4. Se l’Artista del CD nella posizione Beta precede alfabeticamente l’Artista del CD nella posizione Alfa scambiate i due CD; in caso contrario continuate.

5. Se c’è ancora almeno un posto dopo Beta, consideratela la nuova posizione Beta e tornate all’istruzione 4; in caso contrario continuate.

6. Se ci sono due o più posti dopo Alfa, considerate quello immediatamente successivo come nuova posizione Alfa e quello ancora dopo come nuova posizione Beta e saltate all’istruzione 4; in caso contrario l’esecuzione è terminata.

11

Istruzione 1

• Usiamo il termine Artista per riferirci al nome del gruppo, del cantante o del compositore di un CD

• Questo passo assegna un nome all’operazione utilizzata per determinare il nome in base a cui sarà effettuato per l’ordinamento

12

13

Istruzione 2

• Decidete quale estremo della rastrelliera corrisponde all’inizio della sequenza alfabetica e chiamate Alfa la prima posizione di quell’estremo

• Dà un punto di partenza al processo e definisce Alfa. All’inizio, Alfa si riferisce alla prima posizione nella sequenza alfabetica; man mano che l’esecuzione prosegue, il nome fa riferimento a posizioni successive

14

15

Istruzione 3

• Chiamate Beta la posizione immediatamente adiacente ad Alfa

• Dà un significato iniziale a Beta. Alfa e Beta non hanno un significato intrinseco; sono i termini scelti per indicare due posizioni sullo scaffale

16

17

Istruzione 4

● Se l’Artista del CD nella posizione Beta precede alfabeticamente l’Artista del CD nella posizione Alfa scambiate i due CD; in caso contrario continuate.

• Questa è l’istruzione che svolge la gran parte del lavoro. L’istruzione confronta i nomi degli artisti che caratterizzano i CD in Alfa e Beta e, se necessario, li scambia in modo che siano nell’ordine corretto

18

19

Istruzione 5

● Se c’è ancora almeno un posto dopo Beta, consideratela la nuova posizione Beta e tornate all’istruzione 4; in caso contrario continuate.

• Ridefinisce Beta in modo che il nome si riferisca alla posizione successiva nella sequenza, se esiste.Con questa nuova definizione di Beta è possibile eseguire nuovamente l’Istruzione 4, confrontando una diversa coppia di CD

20

21

Istruzione 6

● Se ci sono due o più posti dopo Alfa, considerate quello immediatamente successivo come nuova posizione Alfa e quello ancora dopo come nuova posizione Beta e saltate all’istruzione 4; in caso contrario l’esecuzione è terminata.

• Quando arriviamo a quest’istruzione, il CD che precede tutti gli altri si trova in Alfa. Possiamo far avanzare Alfa di un posto e percorrere ancora tutti i CD, localizzando il CD che precede alfabeticamente tutti gli altri. Quando non ci sono più due posti per definire le posizioni Alfa e Beta, l’intera scaffalatura è stata ordinata e l’algoritmo termina

22

Analisi dell’algoritmo Ordina CD

• Illustra le cinque caratteristiche base degli algoritmi

– Gli input e gli output sono specificati

– Ogni istruzione è definita in modo preciso (determinatezza)

– Le operazioni sono efficaci perché semplici e meccanicamente eseguibili

– L’ordinamento alfabetico è meccanico, così il nostro algoritmo è efficace

– Il requisito di terminazione è soddisfatto: dato che con un numero finito di posti esiste un numero finito di coppie distinte, le istruzioni 4, 5 e 6 non possono essere ripetute all’infinito

23

Un’analisi più approfondita

• Caratteristiche strutturali– due istruzioni, 5 e 6, in cui l’agente deve ripetere

azioni già eseguite. In questi casi si dice che l’algoritmo presenta un ciclo

– Cicli e test• Un ciclo deve includere un test per determinare se le

istruzioni devono essere ripetute ancora una volta

– Ipotesi di partenza• Ipotizziamo che

– lo scaffale sia pieno di CD (senza spazi vuoti)– la parola "dopo" significa lo slot più lontano dal punto iniziale

24

25

L’algoritmo di ordinamento per scambio

• L’esempio Ordina CD illustra un algoritmo standard chiamato ordinamento per scambio

– confronta coppie di oggetti scelti in modo particolare, li scambia se non sono ordinati e prosegue considerandoli tutti uno dopo l’altro

– possiamo usare lo stesso algoritmo con un diverso criterio di ordinamento

26

L’astrazione nel pensiero algoritmico

• Possiamo considerare alcune parti del comportamento di un algoritmo come unità funzionali piuttosto che come singole istruzioni

27

Astrazione della scansione Beta

• Le istruzioni 4 e 5 illustrano l’idea di un’unità computazionale, che chiameremo scansione Beta – l’operazione consiste nello scandire nell’ordine tutti

i CD che seguono una specifica posizione Alfa

– mentre Alfa rimane in una posizione fissa per tutta la scansione, Beta visita ogni posizione successiva ad Alfa, confrontando i CD e scambiandoli quando necessario

– il suo effetto è trovare il CD successivo nell’ordinamento e di spostarlo nella posizione Alfa

28

29

Astrazione della scansione Alfa

• Alfa percorre lo scaffale a partire dalla posizione in cui comincia l’ordinamento e occupa tutte le posizioni (tranne l’ultima) eseguendo a ogni iterazione le istruzioni della scansione Beta

30

31

32

Proprietà della scansione Alfa

1. Esaustiva. Prende in considerazione tutti i CD dalla prima posizione all’ultima (esclusa)

2. Non ridondante. Nessun posto è assegnato ad Alfa più di una volta. Ne consegue che il processo termina se la scansione Beta termina

3. Progressiva. Alla fine di ogni scansione Beta, il CD che segue immediatamente nell’ordinamento tutti quelli già ordinati si trova nella posizione Alfa

4. Completa. Quando l’ultima scansione Beta è completata, il CD nell’ultima posizione segue quello nella penultima

5. Risolutiva. Il CD che precede alfabeticamente tutti gli altri si trova nel primo posto dello scaffale, in virtù della proprietà 4 e del fatto che sono stati presi in considerazione tutti i CD. Per ogni nuova posizione di Alfa, Beta assegna il CD immediatamente successivo nell’ordinamento. Ne segue che il programma esegue correttamente un ordinamento alfabetico.

33

Astrazioni per altri algoritmi e programmi

• Le astrazioni delle scansioni Alfa e Beta si applicano specificatamente all’algoritmo di ordinamento di scambio e ai programmi da esso derivati

• Altri algoritmi e programmi si comportano diversamente e richiedono astrazioni differenti, con altre caratteristiche

• Ogni situazione è diversa, ma l’approccio – astrazione del comportamento e analisi delle proprietà – è sempre lo stesso