Fondamenti di Informatica 1

Ripetizioni di segmenti di codice

• Spesso è necessario ripetere più volte uno stesso segmento dell'algoritmo (e.g. I/O, elaborazioni dati)

• Esistono due possibilità:– Macro– Procedure

Fondamenti di Informatica 2

Le macro

• Una macro è definita come un insieme di istruzioni (o blocco)

• Queste vengono sostituite all'interno del codice

• Servono per rendere più leggibile il codice e per facilitarne la modifica coerente

• #define MAX(a,b) (a>b ? a : b)

Fondamenti di Informatica 3

Le procedure

• Una procedura è definita come un insieme di istruzioni (o blocco)

• Il controllo del flusso passa alla procedura ogni volta che viene invocata

• E' necessario un meccanismo per ritornare al punto chiamante

• Utilizzo dello stack (Stack Pointer)

Fondamenti di Informatica 4

Procedure e funzioni

• La ripetizione di un segmento di codice può avere due obiettivi:– ripetere la stessa sequenza di operazioni– calcolare diversi valori, partendo da

parametri diversi

• La differenza principale è:– la procedura non ritorna nessun valore– la funzione ritorna un valore (ad es void)

Fondamenti di Informatica 5

Passaggio dei parametri

• Ogni procedura/funzione generalmente richiede un insieme di dati

• I dati devono essere accessibili:– in variabili globali– oppure sotto forma di parametri

• I parametri sono dati che vengono utilizzati dalla procedura; ad ogni chiamata possono assumere valori diversi

Fondamenti di Informatica 6

Passaggio dei parametri

• I parametri possono essere passati in modi diversi:– per valore

vengono effettuate delle copie dei valori; le copie sono usate dalla procedura che può anche modificarne il valore

– per riferimentosi passa il puntatore alle variabili; i valori possono essere modificati dalla procedura

Fondamenti di Informatica 7

Side effects

• Se il passaggio dei parametri avviene per valore, l'effetto della procedura è limitato al valore che ritorna

• Se i parametri sono passati per riferimento, la procedura può avere effetti collaterali (side effects)– è un modo per far in modo che la

procedura ritorni più di un valore

Fondamenti di Informatica 8

Le procedure

• Annidamento: in una procedura può essere contenuta un'altra chiamata a procedura

• Limite sulla dimensione dello stack

Fondamenti di Informatica 9

Le procedure

• Ricorsione:all'interno di una procedura avviene una chiamata alla procedura stessa

• Limite sulla dimensione dello stack• Molti algoritmi sono basati sulla

ricorsione

Fondamenti di Informatica 10

La ricorsione

• Esempi:– somma di N dati– calcolo del fattoriale– calcolo dei primi N numeri primi– visita di un albero

Fondamenti di Informatica 11

Algoritmi di ordinamento

• Basilare in molteplici applicazioni• Esempio importante di algoritmi

diversi per risolvere lo stesso problema

• Metodi di ordinamento interni: i dati risiedono nella memoria centrale (in un vettore; campo chiave)

• Confronto basato sull'efficienza

Fondamenti di Informatica 12

Selectionsort

• Ordinamento per selezione• Si sceglie il minimo del vettore e lo

si scambia con la posizione corretta• Complessità: O(n2)• I due cicli vengono sempre eseguiti,

indipendentemente dalla configurazione dei dati

Fondamenti di Informatica 13

Bubblesort

• Basato sulla considerazione che: ei ei+1

• Confronta coppie adiacenti e eventualmente le scambia

• Dopo una scansione completa l'elemento minore è nella posizione corretta

• Termina quando sono terminati gli scambi (se è già ordinato serve solo un passo per la verifica)

• Complessità: O(n2)

Fondamenti di Informatica 14

Mergesort

• Basato sulla fusione (merge) di due vettori ordinati:– la fusione ha complessità O(n)

• E' intrisecamente ricorsivo• Vettore iterativamente diviso in 2

parti:– ordinamento e fusione

• Complessità O(n log2 n)

Fondamenti di Informatica 15

Mergesort

• Indipendente dalla configurazione in ingersso

• La ricorsione incrementa la complessità della gestione:– è consigliabile usare un programma non-

ricorsivo

• Per ogni programma ricorsivo esiste un programma non-ricorsivo più efficiente

Fondamenti di Informatica 16

Quicksort

• Si sceglie un elemento pivot e si suddivide il vettore in due: uno con el. minori, l'altro con el. maggiori o uguali del pivot

• Si procede iterativamente fino a vettori di 1 solo elemento

• La suddivisione ha complessità O(n)• La complessità della parte ricorsiva

dipende dalla scelta del pivot

Fondamenti di Informatica 17

Quicksort

• Scegliendo come pivot l'elemento min o max, la complessità diventa O(n2)

• Scegliendo come pivot l'elemento centrale, la complessità è O(n log2 n)

• Il caso peggiore succede raramente• E' più probabile il caso migliore• E' usato per la semplicità e l'efficienza

Fondamenti di Informatica 18

Limite inferiore della complessità

• Si considerano algoritmi la cui operazione fondamentale è il confronto tra elementi

• Problema:– è ricondotto alla ricerca di una specifica

permutazione di n oggetti– esistono n! permutazioni diverse– tutte le permutazioni sono candidate– ogni passo dell'algoritmo serve per eliminare

dei candidati

Fondamenti di Informatica 19

Esempio

• La ricerca è rappresentabile graficamente con un albero binario:– la radice rappresenta tutte le

permutazioni– ogni confronto suddivide le permutazioni

• La profondità dell'albero determina il numero massimo di confronti nel caso peggiore

Fondamenti di Informatica 20

Esempio

• Ordinare {a1, a2, a3}

• Albero di risoluzione– 3! = 6 permutazioni (6 foglie)– albero con profondità 3

• Programma in C

Fondamenti di Informatica 21

• L'albero deve avere n! foglie• In generale un albero binario con

profondità i ha al più 2i foglie• Quindi per avere n! foglie, l'albero deve

avere profondità p = log(n!)

p = log(n!) ~ log(n/e)n =n log(n) - n log(e) = O(n log(n))

• Il limite inferiore alla complessità è O(n log(n))

Limite inferiore della complessità

Fondamenti di Informatica 22

Binsort

• Fin'ora gli algoritmi erano basati su operazioni di confronto

• Il binsort utilizza operazioni di indirizzamento con indici

• Sfrutta la conoscenza dell'intervallo di variabilità delle chiavi

Fondamenti di Informatica 23

Binsort

• Si suppone che gli n elementi del vettore abbiano chiavi [1..n]

• Si scandisce un vettore e si spostano gli elementi in un altro

• Ha complessità O(n)

Fondamenti di Informatica 24

Binsort

• Caso di più chiavi uguali:– utilizzo di una lista– al termine le liste vengono

concatenate

• Complessità:– inserimento O(n)– concatenazione O(n)– totale O(n)

Fondamenti di Informatica 25

Binsort

• E' il più efficiente se:– si utilizzano chiavi numeriche– l'intervallo di variabilità delle chiavi è

noto– è possibile effettuare indirizzamenti

con indici

Fondamenti di Informatica 26

Considerazionisulla scelta di un algoritmo• Le caratteristiche di un algoritmo sono:

– semplice, per facilitarne la comprensione, programmazione, e correzione

– efficiente, cioè richiede una quantità limitata di risorse per l'esecuzione

• Le due caratteristiche si riferiscono a:– costo umano– costo di esecuzione

Fondamenti di Informatica 27

Considerazionisulla scelta di un algoritmo• Non esistono regole per la scelta

ottima• Generalmente però:

– si sceglie la prima regola quando si deve eseguire poche volte su insiemi ridotti di dati

– si sceglie la seconda se il programma viene eseguito un grande numero di volte su insiemi estesi di dati

Fondamenti di Informatica 28

Considerazioni

• Implementazione efficiente dell'algoritmo– sono state considerate solo le complessità – sono state eliminate le costanti moltiplicative

• Per scegliere l'implementazione migliore è necessario considerare tutto– ad esempio, gli algoritmi ricorsivi sono

generalmente molto pesanti