Appunti Algoritmi E Strutture Dati

Criteri costo e notazione asintotica

Sabato 14 marzo 2020 19:19

Criterio costo uniforme

Questo criterio consiste nel considerare ogni operazione come un singolo passo, quindi il costo di ogni operazione sarà 1 indipendentemente dalla grandezza del dato.

Criterio costo logaritmico

Questo criterio assume che il costo di esecuzione dipenda dalla dimensione degli operandi.

Dimostrazione algoritmo ordinamento con dimezzamento

m =

Caso Base: Banalmente corretto.

Ipotesi Induttiva: Supponiamo sia corretto per ogni n' < n.

Passo Induttivo: Dimostro veridicità per n'.

Possiamo avere 3 casi:

• 1) Elemento cercato è quello centrale.
• 2) Elemento cercato a sinistra: Avremo che l'algoritmo viene eseguito su metà dei valori quindi n/2 = n' che è minore di n.
• 3) Elemento cercato a destra: Avremo che l'algoritmo viene eseguito su metà dei valori quindi n/2 = n' che è minore di n.

Esempio

X <-- 1

For i = 1 to n ∙ do x <-- x 2

Per il criterio del costo uniforme eseguiamo n volte la moltiplicazione, e incrementiamo n volte il contatore quindi il costo totale è 2n n poiché devo sommare tutti i costi. La serie avrà valore = i.

∑ ≈ ∑

Per il criterio del costo logaritmico, a ogni passo il valore di x raddoppia quindi costo sarà log 2 = i,2 ∑ incrementeremo il contatore i volte quindi il costo sarà log i. Di conseguenza il costo totale sarà i2 + log i.

∑ ≤ ∑ ≤ ∑ ∑ i + log i ≤ 2 ∑ i + log

Possiamo scrivere che n i + log i 2n ---> --->2 2i ≤ n quindi possiamo dire che il costo è compreso tra e n.

Modello di calcolo

Il modello di calcolo è la rappresentazione di un calcolatore, e deve avere delle caratteristiche:

• Astrazione Deve poter nascondere i dettagli.
• Realismo Deve riflettere la situazione reale.
• Potenza Matematica Deve consentire di trovare conclusioni formali circa il costo degli algoritmi.

Un esempio di modello di calcolo è la Macchina di Turing. Consiste, idealmente, in un dispositivo di controllo che accede a un nastro infinito bidirezionale (la memoria) diviso in celle, dove in ogni cella può contenere un simbolo di un alfabeto finito. L'accesso al nastro è eseguito da una testina che può spostarsi a destra o sinistra di una posizione per volta. Un'operazione può consistere nello scrivere una cella, leggere una cella, spostare la testina o cambiare lo stato di controllo. Ma questa macchina è troppo di basso livello e non consente un'accurata analisi degli algoritmi.

Un altro esempio è la Macchina a Registri ispirata all'architettura di Von Neumann. Consiste in un programma finito, un nastro in input e un nastro in output, ed una memoria strutturata ad array di n parole, con indirizzi da 1 a n. Un registro detto accumulatore, contiene gli operandi che agiscono sull'istruzione corrente, un altro registro detto contatore delle istruzioni, contiene l'indirizzo della successiva operazione Criteri Costo E Notazione Asintotica Pagina 1 successiva operazione.

Notazione asintotica

Questo tipo di notazione serve per ignorare i dettagli non influenti come le costanti moltiplicative e i termini di ordine inferiore.

Data una funzione f(n) definiamo ≥ ≤ ≥ O(f(n)) quell'insieme di funzioni g(n) tali che ∃ c > 0 e n 0 | g(n) c f(n) per ogni n n0 0.

Se riconosciamo che il costo computazionale h(n) dell'algoritmo è in questo insieme, possiamo dire che h(n) = O(f(n)) ≥.

Quindi g(n) è upper bound, cioè che dopo un certo n 0 f(n) cresce al più come g(n).0

La funzione g(n) mi esprime l'ordine di f(n).

Data una funzione f(n) definiamo ≥ ≥ ≥ Ω(f(n)) quell'insieme di funzioni g(n) tali che ∃ c > 0 e n 0 | g(n) c f(n) per ogni n n0 0.

Se riconosciamo che il costo computazionale h(n) dell'algoritmo è in questo insieme, possiamo dire che h(n) = Ω(f(n)) ≥.

Quindi g(n) è lower bound, cioè che dopo un certo n 0 f(n) vale almeno g(n).0

Data una funzione f(n) definiamo ≥ ≤ ≤ θ(f(n)) quell'insieme di funzioni g(n) tali che ∃ c > 0 c > 0 e n 0 | c f(n) g(n) c f(n) per ogni 1 2 0 1 2 ≥ n n0.

Cioè f(n) cresce tra c f(n) e c f(n) e quindi f(n) si comporta come g(n) perché a differenza di costanti 1 2 di molteplicità f(n) si comporta come g(n).

Se riconosciamo che il costo computazionale h(n) dell'algoritmo è in questo insieme, possiamo dire che h(n) = θ(f(n)).

Una funzione per essere θ(f(n)) deve essere sia lower bound che upper bound.

Se f(n) = θ(g(n)) <---> f(n) = O(g(n)) Λ f(n) = Ω(g(n)).

f(n) = O(g(n)) Λ g(n) = O(h(n)) ---> f(n) = O(h(n)).

Un algoritmo A ha costo di esecuzione O(f(n)) su istanze di dimensione n e rispetto ad una certa risorsa di calcolo, se la quantità r di risorsa sufficiente per eseguire A su istanze di dimensione n è r(n) = O(f(n)).

Un problema P ha complessità o(f(n)) rispetto ad una certa risorsa di calcolo, se esiste un algoritmo A che risolve P il cui costo di esecuzione è o(f(n)).

Ottimalità

Dato un problema P con complessità Ω(f(n)) rispetto a una certa risorsa, un algoritmo A che risolve P è ottimo se ha costo di esecuzione O(f(n)) rispetto a quella risorsa A è θ(f(n)). P non lo è perché ci possono essere algoritmi con upper bound più alto.

Criteri Costo E Notazione Asintotica Pagina 2

Caso peggiore, migliore e medio

Sabato 21 marzo 2020 22:00

Data un'istanza I di dimensione n, indichiamo con t(I) il tempo di esecuzione dell'algoritmo su quella istanza.

Worst Case: Il tempo per eseguire l'algoritmo sarà il massimo dell'insieme di tutti i tempi di esecuzione T = max { t(I) } worst istanze I di ordine n.

Worst Case: Il tempo per eseguire l'algoritmo sarà il minimo dell'insieme di tutti i tempi di esecuzione T = min { t(I) } best istanze I di ordine n.

Average Case: Il tempo medio per eseguire l'algoritmo, cioè per eseguire un'istanza tipica T = avg.

Il caso medio è la somma dei prodotti della proprietà che il caso si verifichi per il tempo, sempre su istanze di dimensione n.

Ovviamente

E quindi

Quindi il tempo medio è:

¬in; ∙ n + p( v ∈ ∙ 1 + p( v ∈ ∙ 2 + … + p( v ∈ T = p(v S) S Λ S[1] = v) S Λ S[2] = v) S Λ S[n] = avg ∙ nv) ¬in;

Per sapere la probabilità che v non appartiene a S, ci vuole un esperto. Supponiamo che p(v S) = 0,5. Se invece è presente v stessa probabilità di essere in qualsiasi posto quindi ∈ p( v S Λ S[n] = v) = .

Il tempo medio di conseguenza è: T = dove: avg probabilità per ogni caso qualsiasi posizioni si trovi.

i sono i confronti che faccio per ogni probabilità (se è al primo posto 1, se al 37° allora 37).

Facendo delle manipolazioni algebriche su T : avg

La serie varia in i quindi possiamo portare fuori il primo termine, otteniamo:

T = avg

Che possiamo scrivere come: ≈ ≈ n T = avg

Quindi tempo medio = tempo peggiore.

Nel binary search il e log n poiché il caso peggiore è che v non c'è e quindi iterando iterando2 entro nel caso base, quindi faccio log n2.

Caso Peggiore, Migliore E Medio Pagina 3

Analisi algoritmi ricorsivi

Venerdì 27 marzo 2020 12:29

Analisi algoritmo ricorsivo

Un algoritmo ricorsivo è diviso in

Caso Base: Uscita dalla ricorsione.

Corpo: Insieme di istruzioni che sicuro eseguo a ogni chiamata. Possiamo avere una o più chiamate.

Normalmente il caso base si conta come una sola operazione. Il corpo un certo numero di operazioni che devo contare in funzione della dimensione in input, in più ci sono anche le chiamate in un insieme più piccolo.

Il costo di un algoritmo ricorsivo è uguale al costo di esecuzione del corpo + il costo di esecuzione delle n chiamate ricorsive. Quindi:

f(n) operazioni che servono per eseguire il corpo + il numero (k) delle chiamate ricorsive in insiemi più piccoli. In formule è: T(n) = f(n) + k T(n' )k.

Binary search

f(n) = 1

K T(n' ) = 1 T(k

K = 1 poiché c'è una sola chiamata ricorsiva. Anche se ce ne fossero di più ne viene eseguita una soltanto.

In totale T(n) = 1 + k T(n/2).

Il costo del corpo è uno perché esegue . solo m = più n chiamate ricorsive eseguite su un input di elementi poiché a seconda della chiamata ricorsiva in cui entra vado a sinistra o a destra.

Metodo dell'iterazione

Il modo più intuitivo per risolvere una relazione di ricorrenza consiste nello "srotolare" la ricorsione, riducendola ad una sommatoria dipendente solo dalla dimensione n.

Sappiamo che la relazione di ricorrenza del binary search è:

Assumendo per semplicità che k sia una potenza di 2, avremo:

Da cui per sostituzioni successive otteniamo

Prima di raggiungere il passo base dobbiamo iterare questo procedimento finché non è uguale a 1, ovvero per i = log n. Ponendo i = log n, possiamo concludere che2 2

T(n) = c log n + T(1) = O(log n)2 2

Metodo sostituzione

Questo metodo consiste nell'intuire la soluzione di una determinata relazione di ricorrenza ed usare l'induzione per dimostrare che la soluzione è effettivamente quella che si è intuita.

Supponiamo di avere

Assumiamo che la soluzione sia O(n). Tramite l'induzione cercheremo di dimostrare che ≤ ∙ T(n) c n per c > 0.

≤ ∙ ≥ Passo Base: T(1) = 1 --> 1 c 1 ---> c 1

≤ ∙ ≤ ∙ Passo Induttivo: Suppongo che T( ) c . Quindi T(n) = n + T( ) n + c . Posso riscriverlo come:

≤ ≤ n + T( ) n(1 + ). Affinché l'ipotesi sia verificata è necessario che 1 + c, che è verificata per c ≥ 2 Analisi Algoritmi Ricorsivi Pagina 4 ≥ 2 ≥ Quindi, l'algoritmo ha costo O(n) per c 2.

Il teorema fondamentale delle ricorrenze

Una tecnica molto potente e generale per la progettazione di algoritmi è la tecnica divide et impera. L'idea consiste nel dividere i dati in ingresso in sottoinsiemi, risolvere ricorsivamente il problema sui sottoinsiemi e ricombinare infine la soluzione dei sottoproblemi per ottenere infine la soluzione globale. Supponiamo che un problema di dimensione n venga diviso in k sottoproblemi, e che combinare le soluzioni richieda tempo f(n). La relazione di ricorrenza corrispondente a questo scenario è quindi ∙ T(n) = k T( ) + f(n).

Le chiamate ricorsive possono essere rappresentate tramite l'albero della ricorsione: la radice corrisponde alla prima chiamata, ed i figli di ogni nodo corrispondono alle chiamate ricorsive effettuate dal nodo stesso.

Per semplicità assumiamo che n sia una potenza di b, e che la ricorsione si fermi quando n = 1.

La dimensione del problema viene divisa per b ad ogni chiamata.

• I sottoproblemi al livello i dell'albero della ricorsione hanno dimensione.
• Il contributo di un nodo a livello i al tempo di esecuzione (escludendo il tempo impiegato per le chiamate) è f( ) i.

Il fatto che i sottoproblemi nell'ultimo livello hanno dimensione implica che n = b e quindi i = log n. Questo ci dice che: b

• Il numero di livelli dell'albero è log nb.

Ciascun nodo ha esattamente k figli, abbiamo quindi che: i

• Il numero di nodi al livello i dell'albero della ricorsione è k.

Possiamo scrivere la ricorrenza come: T(n) =

La soluzione è data dal teorema fondamentale delle ricorrenze o anche teorema master, che si può dimostrare con alcune semplice manipolazioni algebriche.

Teorema fondamentale delle ricorrenze (Teorema Master) Foglio 1

Analisi algoritmo randomizzato

Algoritmo randomizzato: Un algoritmo è un algoritmo che non dipende solo dall'input ma anche da numeri casuali.

Algoritmo deterministico: Un algoritmo è un algoritmo che dipende solo dall'input.

Per gli algoritmo randomizzati, si calcola il valore atteso del tempo di esecuzione, che è il tempo richiesto da una certa istanza e per una data sequenza di numeri casuali. Per una certa istanza I, il tempo atteso è la media calcolata sulle diverse sequenze di numeri casuali.

Il tempo atteso dell'algoritmo nel caso peggiore su istanze di lunghezza n è quindi calcolato combinando questa formula con quella del calcolo del tempo di esecuzione nel caso peggiore.

Algoritmo di ricerca randomizzata

Analisi Algoritmi Ricorsivi Pagina 5

Questo algoritmo prima di eseguire la ricerca, calcola una permutazione casuale della lista L, in modo che l'elemento x appaia in una posizione casuale nella permutazione. La permutazione può essere effettuata in tempo O(n), dove n è la lunghezza di L, semplicemente scorrendo uno alla volta ogni elemento di L e scambiandolo con un altro preso a caso da L stesso. Questo rallenta leggermente l'algoritmo, perché si spende del tempo per calcolare la permutazione, ma potrebbe rendere più veloce la ricerca. Potrebbe convenire usare questo tipo di ricerca quando confrontare gli elementi costa di più che cambiarli di posto.

Analizziamo il tempo di attesa

Dove:

La lista L contiene n elementi.

π(L) è la lista permutata secondo π.

P{π} è la probabilità della permutazione π.

T(x,π(L)) è il numero di confronti per trovare x in π(L).

Partizionando le permutazioni L in base alla posizione che occupa l'elemento x possiamo scrivere la sommatoria come segue:

Dove:

Pos(x) è la posizione di x.

Poiché ci sono n! permutazioni, P{π} = . Inoltre, tra tutte le permutazioni, esattamente (n-1)! Hanno x in una determinata posizione p, e per queste permutazioni T(x,π(L)) = p.

Con ulteriori manipolazioni algebriche possiamo arrivare a:

Da cui T (n) = (n+1)/2.exp

Il numero di confronti è quindi esattamente lo stesso dell'analisi nel caso medio, indipendentemente dalla distribuzione delle istanze di ingresso.

Analisi Algoritmi Ricorsivi Pagina 6

Strutture dati

Venerdì 17 aprile 2020 16:40

Il termine struttura dati si riferisce a una particolare organizzazione delle informazioni che permette di supportare in modo efficiente le operazioni su un tipo di dato.

Un esempio di dato è l'insieme dinamico che rappresenta un insieme di elementi. Un'istanza del tipo Dizionario è una collezione di elementi a cui sono associate delle chiavi appartenenti a un dominio ordinato. Operazioni tipiche di un dizionario sono delete e insert e search. I dizionari sono strumenti di fondamentale importanza nella soluzione di molti problemi pratici.

Possiamo avere rappresentazioni indicizzate e rappresentazioni collegate. Entrambe hanno pro e contro.

Rappresentazioni indicizzate: I dati sono contenuti in array. L'accesso avviene tramite indici, e quindi il tempo di esecuzione è costante. Però hanno dimensione fissa, cioè che se aggiungo o tolgo elementi, devo riallocare la struttura, e questo richiede tempo.

Rappresentazioni collegate: I dati sono contenuti in record collegati tra di loro tramite puntatori. La dimensione può essere variabile, non richiedono posizioni di memoria contigue, poiché non serve calcolare automaticamente l'indirizzo. Di conseguenza, l'accesso ai dati avviene in maniera sequenziale, cioè se devo fare un'operazione su un determinato elemento devo scorrerli tutti.

Array

Un array è una struttura indicizzata costituita da una collezione di celle numerate contigue che possono contenere solo elementi di un determinato tipo. In un array di h celle gli indici vanno da 0 a h-1. Le proprietà basilari degli array sono:

• Gli indici delle celle di un array sono numeri consecutivi.
• Non è possibile aggiungere nuove celle.

La seconda proprietà implica che il ridimensionamento di un array è possibile solamente tramite la riallocazione, creando un nuovo array con la dimensione voluta, e copiandone i valori dalle celle del vecchio array. Il tempo di esecuzione di questa operazione è proporzionale al minimo tra le dimensioni dei due array.

Come implementiamo un dizionario? Strutture Dati Pagina 7

Tecnica raddoppio-dimezzamento

Questa tecnica consente di mantenere in un array una collezione non ordinata di n elementi, soggetti a inserimento e cancellazione. La tecnica consiste nel mantenere un array di dimensione h, ≤ dove per ogni n > 0 abbiamo che 0 h < 4n.

L'idea principale è quella di non effettuare la riallocazione ad ogni operazione, ma solo ad ogni Ω(n). La condizione ≤ 0 h < 4n viene mantenuta mediante riallocazioni definite nel seguente modo:

• Quando n = 0, poniamo h = 1.
• Quando n > h, l'array viene allocato raddoppiandone la dimensione ( h --> 2h).
• ≤ Quando n, l'array viene allocato dimezzandone la dimensione ( h --> ).

≤ ≤ In pratica per ogni n > 0, avremo sempre che n < h, che è la stessa cosa di 0 h < 4n. In termini di memoria avremo che il costo sarà θ(h) = θ(n). ≥

In questo modo, h è sempre una potenza di 2, e quindi e sono sempre interi per h 4.

L'inserimento viene realizzato, previa riallocazione, inserendo l'elemento nella cella di indice n e si incrementa n di uno.

La cancellazione, avviene sovrascrivendo l'elemento in posizione i, con l'elemento in posizione i+1.

Strutture Dati Pagina 8

Strutture collegate: record e puntatori

I record sono numerati e contengono i dati della collezione. Mentre la numerazione degli array è locale al singolo array, i numeri associati ai record sono i loro indirizzi. Vengono cancellati e inseriti in maniera dinamica. Gli indirizzi dei record non sono necessariamente consecutivi. Per mantenere in relazione i vari r