Post on 01-May-2015
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