appunti di fondamenti di informatica e programmazione I

Appunti di Raffaele Ventriglia

decrementata la porzione e ne verrà considerata una nuova in cui dovrà essere trovato di nuovo l'elemento minimo e il suo indice per poterlo inserire nella prima posizione, che però questa volta è la posizione 2 in quanto è stato già trovato il primo elemento. Bisogna considerare che l'algoritmo ordina fino a size - 1 in quanto l'ultimo elemento di logica sarà già nella posizione corretta essendo l'unico elemento e quindi il più piccolo tra "gli elementi". In C quest'algoritmo viene implementato attraverso un ciclo for che itera tutti gli elementi dell'array, ma ad ogni iterazione considererà una porzione sempre minore di dati: all'interno di questo for avremo una prima chiamata alla function min_val_ind che permette di trovare l'elemento minore e il suo indice, dopo di che abbiamo una chiamata alla function swap che scambierà l'elemento.

minore con l'elemento che si trova alla prima posizione della porzione considerata. La complessità di spazio, poiché lavora in place, è n; per la complessità di tempo invece bisogna prendere in considerazione le operazioni di confronto e di scambio: le operazioni di confronto vengono fatte all'interno della function min_val_ind, ed è costante in quanto viene chiamata n - 1 volte, ma il size della porzione su cui agisce non è costante perché diminuisce di 1 ad ogni iterazione, quindi bisogna fare la somma dei primi n numeri naturali (formula di Gauss); per quanto riguarda invece le operazioni di scambio vengono effettuate una volta per ogni iterazione del ciclo for, quindi si tratta di una complessità assoluta che è uguale a size - 1.

Algoritmo di Ordinamento per Selezione di Massimo

L'algoritmo di ordinamento per selezione di massimo permette di ordinare un array in ordine crescente, che può contenere dati di tipo intero,

il testo fornito utilizzando tag html:

carattere o stringhe di caratteri. Ha come dati di input un array, il suo size e come unico dato di output lo stesso array ordinato; questa tecnica è chiamata anche "in place" in quanto permette di ordinare un array senza l'utilizzo di ulteriori strutture dati. Questo algoritmo fa un numero di iterazioni che è uguale a size - 1, e ad ogni passo risolve il sotto problema di trovare l'elemento massimo e il suo indice all'interno della porzione data; una volta trovato l'elemento, viene posto all'ultimo posto della porzione dell'array; dopo di che verrà decrementata la porzione e ne verrà considerata una nuova in cui dovrà essere trovato di nuovo l'elemento massimo e il suo indice per poterlo inserire nell'ultima posizione della nuova porzione. In C quest'algoritmo viene implementato attraverso un ciclo for che itera tutti gli elementi dell'array, ma ad ogni iterazione

considererà unaporzione sempre minore di dati: all'interno di questo for avremo una prima chiamata alla function max_val_ind che permette di trovare l'elemento massimo e il suo indice, dopo di che abbiamo una chiamata alla function swap che scambierà l'elemento massimo con l'elemento che si trova all'ultima posizione della porzione considerata. La complessità di spazio, poiché lavora in place, è n; per la complessità di tempo invece bisogna prendere in considerazione le operazioni di confronto e di scambio: le operazioni di confronto vengono fatte all'interno della function max_val_ind, in maniera costante, size - 1 volte, ma poiché viene considerata una porzione di array sempre diminuita di 1 allora utilizziamo la formula di Gauss per sommare i primi n numeri naturali; per quanto riguarda invece le operazioni di scambio vengono effettuate una volta per ogni iterazione del ciclo for, quindi si tratta di una

complessità assoluta che è uguale a size - 1.

Algoritmo di Fusione

L'algoritmo di fusione permette la fusione di due array di dati già ordinati all'interno di un terzo array ordinato in ordine crescente, detto anche problema di "merging". Questo algoritmo ha come dati di input i due array ordinati e i rispettivi size, e come unico dato di output un terzo array che avrà size uguale all'addizione tra i due size degli array in input. Dopo aver creato due indici che puntano agli elementi del primo e del secondo array, il meccanismo è molto semplice, in quanto si possono delineare tre scenari possibili: il primo dove entrambi gli array contengono ancora elementi che devono essere inseriti all'interno del terzo, e in questo caso bisogna confrontare gli elementi del primo e del secondo array per poter trovare l'elemento minore che deve essere inserito; per quanto riguarda il secondo e il terzo scenario bisogna dire che

verrà eseguito solo uno dei due, in quanto vengono attivati solo nel momento in cui uno dei due array è terminato, e bisogna quindi inserire gli elementi che rimangono nell'array. L'implementazione in C di questo algoritmo prevede l'utilizzo di tre while che rappresentano i tre scenari: con il primo si controlla se in entrambi gli array sono ancora presenti degli elementi, il secondo invece rappresenta lo scenario nel quale il secondo array è terminato, mentre il terzo il caso in cui il primo array è terminato, e quindi bisogna inserire gli elementi che sono rimasti. La complessità di spazio, chiamando n = n_a + n_b, è uguale a 2n in quanto costruisce un terzo array di size n; per la complessità di tempo invece bisogna considerare le operazioni dominanti, che sono solo le operazioni di confronto che vengono effettuate solo nel primo scenario: per questo viene calcolato un caso peggiore, ovvero il caso.

In cui entrambi gli array hanno size n e devono essere confrontati tutti gli elementi, la complessità sarà quindi n = n_a + n_b.

Algoritmo di String Matching

L'algoritmo di String Matching permette di risolvere il problema del "searching", ovvero cercare per esempio il numero di occorrenze di una stringa chiave all'interno di una stringa testo; infatti, ha come dati di input la stringa chiave e la stringa testo, mentre come output il numero di occorrenze. Il meccanismo è quello di far eseguire l'algoritmo un numero di volte uguale alla lunghezza della stringa testo meno la lunghezza della chiave più 1 per poter evitare inutili confronti, risolvendo ad ogni passo il problema di controllare l'uguaglianza tra la stringa chiave e la sottostringa della stringa testo che ha come inizio il passo e come lunghezza la lunghezza della stringa chiave. L'implementazione C prevede due variabili fondamentali, che dovranno contenere, utilizzando

la complessità di tempo di questa operazione dipende dalla lunghezza della sottostringa. Quindi, se la lunghezza della sottostringa è m, la complessità di tempo sarà O(m).poiché è innestata nel forche itera m – n + 1 volte, allora la complessità di tempo è uguale proprio a m – n + 1, che è quindi la complessità di caso peggiore. Algoritmo di Ricerca Binaria (iterativo) L'algoritmo di ricerca binaria versione iterativa permette di cercare una chiave all'interno di un array ordinato di dati, ed è molto efficiente in quanto la sua complessità di tempo è logaritmica. L'algoritmo prevede come input la chiave, l'array e il suo size, e come output, se la chiave è presente nell'array, l'indice d'inizio dell'occorrenza, altrimenti -1 se non è presente. Questo algoritmo utilizza un approccio divide et impera, ovvero durante l'esecuzione viene trovato l'elemento mediano dell'array che viene confrontato con la chiave, dopo di che abbiamo tre scenari possibili: il primo in cui i due elementi sono uguali, e quindi il

Il programma restituisce il valore 1; negli altri due casi invece si controlla se la chiave è maggiore o minore dell'elemento mediano: se l'elemento è maggiore allora viene presa in considerazione la porzione di destra, ovvero con inizio uguale a mediano + 1, e fine uguale a size - 1; mentre se l'elemento è minore allora viene considerata la porzione di sinistra, con inizio che è il primo elemento della porzione, e fine uguale a mediano - 1.

L'implementazione in C prevede un singolo while che controlla che ci siano ancora elementi all'interno dell'array; all'interno del while viene fatto il controllo a tre vie di cui abbiamo appena parlato. La complessità di spazio è uguale a n in quanto l'algoritmo lavora in-place, ovvero non fa uso di ulteriori strutture dati; per quanto riguarda invece la complessità di tempo bisogna prendere in considerazione i confronti fatti all'interno del while,

e per poterla calcolare al meglio bisogna esaminare l'albero binario delle decisioni. Questo ha come nodi gli elementi che costituiscono l'array, e i livelli che sono i passi d'esecuzione dell'algoritmo; la radice è il primo elemento mediano che viene confrontato con la chiave: se questo risulta diverso, allora si genererà il primo livello, che è diviso nell'elemento mediano della porzione di sinistra e l'elemento mediano della porzione di destra e così via fino ad arrivare alle foglie, ovvero l'elemento ultimo che non può generare altre decisioni binarie. Per poter calcolare la complessità di tempo bisogna quindi prendere in considerazione la profondità (numero di livelli) dell'albero; se l'albero fosse completo, allora la profondità sarebbe log (n + 1), ma poiché l'albero di un algoritmo di ricerca binaria non è sempre completo, la complessità di tempo può variare.