Ripetizioni di segmenti di codice

(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

(2)

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)

(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)

(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)

(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

(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 riferimento

si passa il puntatore alle variabili; i valori possono essere modificati dalla procedura

(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

(8)

Le procedure

• Annidamento:

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

• Limite sulla dimensione dello stack

(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

(10)

La ricorsione

• Esempi:

– somma di N dati

– calcolo del fattoriale

– calcolo dei primi N numeri primi – visita di un albero

(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

(12)

Selectionsort

• Ordinamento per selezione

• Si sceglie il minimo del vettore e lo si scambia con la posizione corretta

• Complessità: O(n²)

• I due cicli vengono sempre eseguiti,

indipendentemente dalla configurazione dei dati

(13)

Bubblesort

• Basato sulla considerazione che:

e_i  e_i+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(n )

(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 log₂ n)

(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

(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

(17)

Quicksort

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

• Scegliendo come pivot l'elemento

centrale, la complessità è O(n log₂ n)

• Il caso peggiore succede raramente

• E' più probabile il caso migliore

• E' usato per la semplicità e l'efficienza

(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

(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

(20)

Esempio

• Ordinare {a1, a2, a3}

• Albero di risoluzione

– 3! = 6 permutazioni (6 foglie) – albero con profondità 3

• Programma in C

(21)

• L'albero deve avere n! foglie

• In generale un albero binario con profondità i ha al più 2ⁱ foglie

• Quindi per avere n! foglie, l'albero deve avere profondità p = log(n!)

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

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

Limite inferiore della complessità

(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

(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)

(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)

(25)

Binsort

• E' il più efficiente se:

– si utilizzano chiavi numeriche

– l'intervallo di variabilità delle chiavi è noto – è possibile effettuare indirizzamenti con

indici

(26)

Considerazioni

sulla 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

(27)

Considerazioni

sulla 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

(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