Algoritmi-riassunto

8/16/2019 Algoritmi-riassunto

1/98

Capitolo 1 – Introduzione

• Alcuni problemi sono irrisolvibili

•

Alcuni vengono risolti solo in modo approssimato

• Soluzioni ottime: non ce ne sono di più efficienti

• Semplicità, modularità, manuntenibilità, espandibilità, sicurezza, robustezza

• Invariante: condizione sempre vera in un certo punto del programma

o Di ciclo: all’inizio del ciclo (subito dopo il for)

o Di classe: alla fine dell’esecuzione di un metodo

•

Dimosterazione correttezza

o aso base: vera all’inizio

o !asso induttivo: se la condizione " vera all’inizio di un’iterazione, lo "

anc#e alla successiva (ad esempio: min conterrà il minimo degli

elementi tra $ e i%&)

o onclusione: alla fine min conterrà il minimo tra $ e n%&

• 'isorse da poter valutare:

o empo

o Spazio (memoria)

o anda (algoritmi distribuiti)


2/98

ANALISI DI ALGORITMI

Dimensione dell’input

Criterio di costo logaritmico: la taglia dell'input è il numero di bit necessari perrappresentarlo .sempio! moltiplica"ione di numeri binari lung#i n bit

Criterio di costo uniforme: la taglia dell'input è il numero di elementi c#e locostituiscono. sempio! ricerca minimo in un arra$ di n elementi

In molti casi: possiamo assumere c#e gli %elementi& siano rappresentati da unnumero costante di bit. Le due misure coincidono a meno di una costantemoltiplicatia

Modello di calcolo: rappresentazione astratta di uncalcolatore

Astrazione: dee sempli(icare i dettagli) altrimenti è inutile

Realismo: dee ri(lettere la situa"ione reale

Potenza: dee permettere di trarre conclusioni (ormali sul costo

Binary search

*un"iona solo su ettori ordinati. +omplessit,!O-log n


3/98

aratsu!a

Sere per moltiplicare due binari con diide et impera

+omplessit,! O-n

/.01

"election sort

Ordina un ettore mettendo il minimo all2ini"io ogni olta +omplessit,!O-n3


4/98

Merge sort

Ordinare un ettore con diide et impera +omplessit,!O-nlog-n

Analisi ammortizzata

+i sono tre metodi per (are l2analisi ammorti""ata!

Metodo dell’aggregazione:

• Si calcola la complessit, O-(-n per eseguire opera"ioni in se4uen"a nelcaso pessimo

• Il costo ammorti""ato di una singola opera"ione è O-(-n5n

Metodo degli accantonamenti #consigliato$:


5/98

• Alle opera"ioni engono assegnati costi ammorti""ati c#e possono esseremaggiori 5minori del loro costo e((ettio

• 6roare c#e la somma dei costi ammorti""ati è un limite superiore al costoe((ettio

Metodo del potenziale #ignorato$

Counting sort

7asato non sui con(ronti) dipende dal range -8 dei numeri+omplessit,! O-n98


6/98

Capitolo 3 – Strutture

• Specifica, implementazione

•

Tipi:

o Lineari (presenza di una sequenza) / non lineari

o Statiche / dinamiche

o Omogenee / disomogenee

• Sequenze

o Dinamica e lineare

o

Conta lordine

o !mmette duplicati

o !ccesso diretto a primo/ultimo

o !ccesso sequenziale a tutti gli altri elementi

o ! pagina " degli appunti guella, linterfaccia # incompleta$ La %ersione

completa # a pagina & (con implementazione)

• Set

o Dati chia%e (unici)

o Dati satellite

• Dizionari

• 'mplementazioni

o Dizionario: hashtale, alero

o !lero: alero con puntatori, %ettore dei padri

o Sequenza: lined lista, arra*


7/98

STRUTTURE ELEMENTARI

Lista circolare, bidirezionale, con sentinella

È possibile realizzare le liste con i vettori, bisogna gestire però il problema delladimensione dinamica, meglio gestirla come a !ava nell"arra# list, incrementa ognivolta del doppio e dimezza $%ando l"occ%pazione & pari ad %n $%arto'


8/98

Stack

(%nziona come i piatti in pizzeria, LI()

Queue


9/98

(I()


10/98

Capitolo 5 – Alberi

• Profondità/livello: distanza dalla radice (0 per la radice)

•

Livello: nodi della stessa profondità

• Altezza: massima profondità

• Visita

o In profondità, a seconda di quando si processa il nodo rispetto ai fili:

Pre!order

In!order (a"#"a" invisita, simmetrico)

Post!order

o In ampiezza (con la coda dei nodi da visitare)

• Implementazioni

o Vettore dei fili ($parent, node $c%ild&odes')

preca spazio per i nodi con poc%i fili

o Lin#ed list dei fili ($parent, $first*%ild, $ne+tilin)

o Vettore dei padri

struct -int parentInde+, Item value.'I1

o Aleri inar2

3ree ri%t(), 3ree left()

• 4rdinamento asato sui confronti:

o equenza di confronti rappresentaile come alero inario

o 5olie: soluzioni del prolema, nodi interni: confronti

o &umero di possiili solizioni: n6

o Altezza minima dell7alero: lo n6 8 n/9 lo n/9

o Per cui oni aloritmo di ordinamento (asato sui confronti) ;(n lon)


11/98


12/98

ALBERI BINARI DI RICERCA

Alberi binari in cui il figlio sinistro è più piccolo del padre, il figlio destro più grandedel padre

Alberi binari di ricerca

Ricerca: implementazione

Cerca un valore nell’albero Coplessit!"

#$logn%


13/98

Ricerca del minimo e del massimo

Coplessit!"#$logn%


14/98

Successore-predecessore

Successore: di un nodo è il più piccolo nodo aggiore di &uel nodo

Inserimento

Nel caso pessio dobbiao scorrere tutto l’alte''a dell’alberoCoplessit!" #$logn%


15/98


16/98

Cancellazione

Bisogna se in caso odificare l’albero perc() rianga un ABR

Bilanciamento degli alberi*pesso le opera'ioni $ricerca, cancella'ione ecc% sugli ABR dipendono dall’alte''adell’albero+ Conviene &uindi cercare di tenere l’albero il più possibile bilanciato" c(enon vi sia troppa dise&uit! di profondit! fra sottoalbero destro e sottoalbero sinistro+er fare &uesto dobbiao fare ogni tanto delle rota'ioni+


17/98

Alberi Red-Black “Treee”

*ono ipleentati per prevedere la bilanciatura dell’albero+ #gni nodo pu- essererosso o nero, le foglie non contengono valori, sono nodi nil $ in trealt! ne esiste solouno, tutti puntano a &uello, per rispariare eoria%+ La radice è nera, tutte lefoglie sono nere, i figli di un nodo rosso sono abedue neri+

In pratica root e foglie sono neri, non posso avere due rossi consecutivi+ Il pat( diogni foglia contiene lo stesso nuero di nodi neri+

Altezza nera: il nuero di nodi neri lungo ogni percorso da un nodo v $escluso% aduna foglia $inclusa%+ *i indica con b$v%

Altezza nera di un albero: è l’alte''a nera della radice


18/98

RB-Tree rotazione a sinistra

RB-Tree inserimento nodo

Coe negli ABR, poi si sistea il tutto Coplessit!"#$log n%


19/98


20/98

RB-Tree cancellazione

.un'iona coe negli ABR, solo c(e poi dobbiao decidere se aggiustare o no, sideve aggiustare solo &uando il nodo cancellato è nero"

Se il nodo cancellato è rosso:

•

l’alte''a nera riane invariata• non sono stati creati nodi rossi consecutivi

• la radice resta nera

Se il nodo cancellato è nero:

• la radice pu- essere un nodo rosso

• se il padre e uno dei figli del nodo erano rossi ci troviao con due rossi di fila

• cabia l’alte''a nera

Complessit: !isitiamo "#log n$ nodi ognuno in tempo "#%$& 'uindi "#log n$


21/98


22/98

Capitolo 7 – Hashing• Dizionario: insieme dinamico con coppie chiave, valore (chiave unica)

• Se il numero di possibili chiavi è molto maggiore di quelle che verranno

effettivamente memorizzate, occorre un’hashtable, altrimenti si può usare

l’indirizzamento diretto

• (!) è una funzione che tritura la chiave ! (sempre allo stesso modo però) e

restituisce un valore dal range molto pi" limitato di !# $i possono essere

quindi delle collisioni#

• %utti i valori con lo stesso hash sono memorizzati nello stesso slot di un arra&

• 'ccorre minimizzare il numero di collisioni, e sapere gestire quelle che si

verificano

• Sarebbe necessario conoscere la distribuzione di probabilit di !, ma nella

realt non si usa questo metodo#

• unzioni di hash

o *strazione: si estraggono degli specifici bit dal valore

o +': si -orano varie estrazioni di specifici bit

o Divisione: ! mod m, dove m è dispari, meglio se primo

o .oltiplicazione: (!) / floor(m 0 (!$ 1 floor(!$))), dove $ è una

costante tra 2 e 3, e m un numero qualunque (potenze di 4 consigliate)

(questo metodo non è poi cos5 buono)

• 6valanche effect: un singolo bit della chiave modificato deve cambiare

almeno met dell’hash

• $ollisioni


23/98

o 7iste di trabocco: lin!ed list sugli slot con pi" di un elemento#

8nserimento in testa, loo!up e delete richiedono la scansione della lista:

9(3lunghezza.edia7ista;4)

o 8ndirizzamento aperto: se uno slot è gi occupato, se ne cerca uno

alternativo

esimo elemento restituito da un generatore di num

casuali da 2 a m>3

• isulta una permutazione, ma rimane il secondar&

clustering

Doppio hashing: (!, i) / ((!) i0’(!)) mod m

• ’(!) deve essere relativamente primo con m

o m / 4p, ’(!) deve restituire numeri dispari

o m primo, ’(!) deve restituire numeri minori di m

o $ancellazione: non si può mettere null, altrimenti le scansioni

successive si fermerebbero# 'ccorre uno speciale valore deleted

• $omplessit

o n chiavi, m slot

o n?m, ovvero fattore di carico @ ? 3

o 8(@): numero atteso di ispezioni in caso di insuccesso

o S(@): numero atteso di ispezioni in caso di successo


24/98

• Auando @ cresce troppo, si raddoppia la dimensione della tabella

(tipicamente 2#B)

• $osto ammortizzato costante

• =roblemi hashtable:

o Scarsa localit& reference (cache miss)

o


25/98

INSIEMI E DIZIONARI

Riepilogo complessità

Insieme: collezione di oggetti

Dizionario: insieme di associazioni chiave-valore

Insiemi realizzati con vettori booleani


26/98

Vantaggi: notevolmente semplice, efficiente verificare se n elemento appartieneall!insieme

Svantaggi: occpazione di memoria O"N#, indipendente dalla dimensionedell!insieme, operazioni inefficienti O"N#

Insiemi realizzati con liste non ordinateVantaggi: occpazione di memoriaproporzionale alla dimensione del vettore

Svantaggi: operazioni di ricerca, inserimento ecancellazione O"n#$ nione, intersezione edifferenza O"nm#

Insiemi realizzati con liste ordinate

Vantaggi: occpazione di memoriaproporzionale alla dimensione del vettore,operazioni di nione, intersezione e differenzaO"n#

Svantaggi: operazione di ricerca, inserimentoe cancellazione% O"n#

Insiemi realizzati con strutture dati complesse

Con alberi di ricerca bilanciati:

• Ricerca, inserimento, cancellazione% O"logn#

• &iene mantento l!ordinamento• Elencare ttti gli elementi% O"n#

Con tabelle hash:

• Ricerca, inserimento, cancellazione% O"'#

• &iene perso l!ordinamento

• Elencare ttti gli elementi% O"m# dove m ( la dimensione della ta)ella hash


27/98


28/98

Capitolo 9 – Grafi

• Visite

o

Ampiezza (numero di Erdos)

o Profondità (ordinamento topologico, component (fortemente)

connesse)

• Cammini minimi

o Da singola sorgente

o Fra tutte le coppie

• Tipi

o Orientato non orientato (con le freccie singole o !idirezionale)

o (u, ") incidente da u a " (u ##$ ")

o " adiacente a u se u ##$ " (%ci si pu& arri"are direttamente da')

• Definizioni

o n V, mE

o *rado (+uanti arci), grado entrante (+uanti entrano), grado uscente

(+uanti escono)

o Cammino (orientato), Catena (non orientato)- .emplice se non ci sono

nodi doppi

o Ciclo (orientato), Circuito (non orientato)- .emplice se non ci sono nodi

doppi

o Aciclico, Orientato aciclico DA*

o Completo/ ciascuno direttamente collegato a ciascunaltro

o Al!ero li!eroorientato, connesso, aciclico

o Al!ero radicato/ se +ualce "ertice 0 detto radice

o Al!ero di copertura

o Erdos/ Erdos a Erdos 1, ci a scritto un articolo con lui 2, ci a

scritto un articolo con uno di erdos 2 3 e cos4 "ia


29/98

o Vertici aperti/ "ertici i cui arci uscenti non sono ancora stati percorsi

o Vertici ciusi/ "ertici di cui arci uscenti sono stati tutti percorsi

o Componenti connesse/ si sa

o Componenti fortemente connesse/ per i grafi orientati, significa ce sipu& andare a"anti e indietro

o 5n sottografo 0 un sottoinsieme dei "ertici e un sottoinsieme dei lati

o 5n sottografo 0 massimale se non si pu& allargare mantenendolo

connesso

• 6mplementazioni

o 7atrice di adiacenza (cosa 0 collegato a cosa)

.pazio/ O(n3)

Verifica adiacenza/ O(2)

Elenco di tutti gli arci/ O(n3)

o 8iste di adiacenza

.pazio/ O(n9m)

Verifica adiacenza/ O(n)

Elenco di tutti gli arci/ O(n9m)

• Dept First .earc

o :uando si scopre un nuo"o nodo ce prima non era marcato, +uesto

"iene marcato e inserito nell;al!ero ricoprente (T)

o *li arci restanti possono essere/

All;indietro/ puntano ad un antenato (o padre)

6n a"anti/ puntano ad un discendente (o figlio)

Di attra"ersamento, negli altri casi

• 5n grafo 0 ciclico<

o 6 DA* non anno arci all;indietro, per cui +uando se ne tro"a uno si

restituisce false-


30/98

• Ordinamento topologico/ 6n ce ordine fare le cose per eseguire tutti i tas=, ad

esempio con ma=e (riciede un DA*)

o .oluzione diretta/ tro"are un nodo senza arci incidenti, stamparlo e

rimuo"ere- >ipetere per tutti gli altri

o ?asata su DF.

• .trongl@ Connected Components (scc)

o Algoritmo di osaraBu, 2 (calcola il grafo trasposto)


31/98

HEAP MFSET

Code con priorità

Le operazioni base viste fin ora (cancellazione, inserimento ecc) possono nonbastare, certe volte dobbiamo inventarne di nuove Le code di priorit! sono unastruttura dati fatta apposta per essere efficiente a fare determinate operazioni "lio##etti sono estratti dalla cosa in base alla loro priorit!

Albero binario perfetto

Tutte le fo#lie $anno la stessa altezza, tutti, tranne le fo#lie $anno due fi#li Altezza% &uindi lo# n

Albero binario completo Tutte le fo#lie $anno profondit! H o H' Tutti i nodi a livello H sono accatastati asinistra Tutti i nodi interni $anno #rado due, eccetto al pi uno

Heap

* un particolare tipo di coda di priorit! nella &uale i dati sono mantenuti in modoparzialmente ordinato

Max heap: albero binario completo in cui la radice % sempre il ma##iore (anc$enei sottoalberi, il padre % sempre il ma##iore)

Min heap: albero binario completo in cui la radice % sempre minore (anc$e neisottoalberi)

"li $eap non impon#ono nessun ordinamento fra i fi#li di un nodo (ordinamentoparziale), l+importante % c$e i padre sia ma##iore o minore rispettivamente per ilma e per il min $eap

• -#ni nodo % ma##iore o u#uale di se stesso

• Se n ./m e m./n allora n/m

• Se n./m e m./r allora n./r

L+ordinamento parziale % utile per modellare #erarc$ie complesse o per mantenere

informazioni parziali * pi semplice costruire uno $eap ordinato parzialmente c$e&ualcosa ordinato totalmente

Array heap

• A01 contiene la radice

• p(i) / 0i231 (limite inferiore) Padre


32/98

• l(i) / 3i Fi#lio sinistro

• r(i) / 3i4 Fi#lio destro

Procedure per gestire uno heap

Max heap restore

Serve per mantenere la propriet! dei ma $eap dopo un inserimento 5omplessit!6-(lo#n)

-#ni sottoalbero deve essere un ma $eap, &uindi si cerca di fare scendere fino al

posto #iusto il valore

Heap build

Serve per costruire un ma $eap da zero (dato un vettore)5omplessit!6 -(nlo#n)

Heapsort


33/98

-rdina sul posto un arra7 5omplessit!6 -(nlo#n)

Coda con priorità

8na struttura dati c$e serve a mantenere un insieme S di elementi , ciascuno con

un valore associato di priorit!


34/98


35/98

Riduzione priorità

MF!"

Servono a rappresentare de#li insiemi dis#iunti, le operazioni fondamentali sonounire pi insiemi, identificare l+insieme a cui appartiene un o##etto * una collezionedi insiemi dinamici dis#iunti (un insieme di insiemi) -#ni insieme % rappresentatoda un rappresentante univoco Le ricerc$e del rappresentate sullo stesso insiemedevono restituire sempre lo stesso o##etto Solo dopo un unione &uesto o##etto pu9cambiare Si pu9 sce#liere l+elemento pi piccolo2#rande di un insieme


36/98

Applicazione: tro#are le componenti connesse di un

grafo

Alla fine avremo l+insieme delle comonenti connesse 5omplessit!6-(n4m)


37/98

$mplementazione basata su liste

• realizzazione basata su liste: find %&'( merge %&n(

• realizzazione basata su alberi6 find -(n) mer#e -()

conviene anc$e inserire l+euristica del peso (se liste) 2 ran#o (se alberi) e la

compressione dei percorsi Euristica sul peso6 $o due liste, per unirle devo sce#liereuno dei due rappresentanti ed applicarlo all+altra lista, lo#icamente attacco la picorta alla pi lun#a, &uindi mi salvo anc$e la dimensione

:el caso delle liste6 o#ni elemento contiene un puntatore al successivo, unpuntatore al rappresentante ed un o##etto

Pu9 essere visto come un albero di altezza

L+operazione find ric$iede -(), si restituisce il rappresentante di ;

ui conviene applicare la compressione dei cammini6


38/98

>uando si cerca &ualcosa portiamo tutto in su 5os? le successive ricerc$ecosteranno -()6


39/98

Capitolo 11 – Cammini minimi grafi

• Tipi di problemi (non centra col resto del capitolo)

o Decisionali: bool IsItTrueThatInputHasASpecificProperty()

o Ricerca: IEnumerableSolution! "etPossibleSolutions()

o #ttimi$$a$ione: Solution "et%estSolution()

o Approssima$ione: Solution "et"oodEnou&hSolution()

• 'a defini$ione matematica di un problema pu su&&erirci un metodo di

risolu$ione

• Teorema di %ellman:

o on i cammini minimi* o&ni arco (u* +) dell,albero ricoprente de+e

a+ere:

Distan$a da + - Distan$a da u . peso dell,arco u*+

o Per o&ni arco del &rafo (intero sta+olta* non solo dell,albero ricoprente)

'a distan$a calcolata da noi de+e essere minore o u&uale a

/uella che si otterrebbe usando l,arco (u* +)

• Al&oritmo di Di01stra (2343)

o oda di priorit5 mediante +ettore 6 lista non ordinati

o #(n7)

o Pesi positi+i


40/98

• Al&oritmo di 8ohnson (2399)

o oda di priorit5 mediante heap binario

o #(m lo& n)

o Pesi positi+i

• Al&oritmo di redman;Tar0an (23


41/98

• Al&oritmo di %ellman;ord;=oore (234 D,Esopo (239?)

o De@ueue


42/98

o "eneralmente* superpolinomiale

o In pratica* +eloci per &rafi di reti stradali


43/98

DIVIDE ET IMPERA

Divide: dividi il problema in sotto problemi più piccoli ed indipendenti

Impera: risolvi i sotto problemi ricorsivamente

Combina: unisci le soluzioni dei sottoproblemi

Ordina un vettore sul posto, divide comlicato, nessun combina omplessit!:O"nlo#n$

Parentesizzare (decidere quale motiplicazione dimatrice fare prima)

%trassen O"n&'()$


44/98

*ino#rad O"n&,+($


45/98

Capitolo 13 – Programmazione dinamica• Divide-et-impera

o

Ricorsivao Top-down

o Vantaggioso quando i sottoproblemi sono indipendenti

• Programmazione dinamica

o Iterativa

o Bottom-up

•

Semplice spiegazione della differenza tra programmazione dinamicaiterativa!" e memoization#

o $emoization# si c%iama ricorsivamente" alla fine della funzione ci sisalva il risultato in un arra& cac%e!" e all'inizio si controlla se il risultato( gi) stato calcolato* In tal caso" lo si restituisce subito*

o Se l'arra& di cac%e %a dimensione +" significa c%e ci sono + possibiliinput per la funzione" quindi il corpo pesante della funzione verr)eseguito al massimo + volte*

o Se ci si rende conto c%e tutti gli + slot della cac%e verranno riempiti"tanto vale calcolarli tutti" iterativamente" partendo dal caso base earrivando a quello c%e ci interessa* , questo punto si pu togliere lec%iamate ricorsive e sostituirle con un fiduciosocac%e.argomento/on/ui,vrei/%iamato0a1unzioneRicorsivamente2"visto c%e lo avremo sicuramente gi) calcolato a questo punto sisceglie un nuovo nome per la variabile cac%e!

o ,ttenzione per# usando la versione iterativa si risc%ia di calcolareelementi c%e poi non ci serviranno" quindi tanto vale usarela ricorsionecon memoization" c%e ( anc%e molto pi3 naturale ed espressiva

o Se il numero di possibili c%iavi ( troppo alto" si usa un'%as%table

• Sottostruttura ottima

o 4 una definizione ricorsiva della soluzione ottima" cio( le soluzioni deisottoproblemi

• In c%e sequenza conviene moltiplicare delle matrici5


46/98

o 0'ordine non pu essere cambiato" ma i raggruppamenti s6*

o Scegliamo dove spezzare la lista di matrici per effettuare ilraggruppamento" e proseguiamo ricorsivamente sulle sottoparti

o Teorema di parentetizzazione ottima# ogni soluzione ottima contiene altuo interno le parentizzazioni ottime dei sottoproblemi

o 7n8!

• 9aino .***2

• 0ongest /ommon Subsequence

o Subsequence# cio( c%e si ottiene rimuovendo un certo numero dielementi anc%e sparsi! da una sequenza

o

/ommon subsequence# una subsequence ottenibile da due sequenzediverse

o 0ongest /ommon Subsequence# la pi3 lunga di queste


47/98

o /%e mal di testa

o 0/S viene usato nel diff per confrontare file" vedendo quali rig%e sonostate aggiunte e quali tolte le modific%e vengono viste comeaggiunta:cancellazione!

• String matc%ing approssimato

o ;n'occorrenza


48/98

Capitolo 14 – Greedy• Cerchiamo una possibile scelta ingorda

• Dimostriamo che la scelta ingorda porta alla soluzione ottima

• Scriviamo un algoritmo ricorsivo o iterativo che effettua sempre la scelta

ingorda

*sottostruttura ottima: qualcuno me la rispieghi

Teorema “Greedy choice”

Sia S[i,j] un sottoproblema non vuoto, e m lattivit! di S[i,j] con il minor tempo di fine"

allora:

• m # compresa in qualche soluzione ottima di S[i,j]

• $l sottoproblema S[i,m] # vuoto

Conseguenze:

• %on # pi& necessario analizzare tutti i possibili valori di '

o (accio una scelta )ingorda, ma sicura: seleziono lattivit! m con il minor

tempo di fine

•

%on # pi& necessario analizzare due sottoproblemi:

o +limino tutte le attivit! che non sono compatibili con la scelta ingorda

o i resta solo un sottoproblema da risolvere: S[m,j]

Insiemi indipendenti versione iterativa (greedy)

Complessit!: -.n/ se ordinata, -.nlogn/ se disordinata


49/98

Per un uon greedy!

• 0rasformare il problema di ottimizzazione in un problema di scelte successive

• Dimostrare che tale scelta rispetta il )principio della scelta ingorda

•

Dimostrare che la soluzione ottima del problema )residuo dopo la sceltaingorda pu1 essere unito a tale scelta


50/98

Tipici prolemi greedy (solu"ione sulle slide a parole# poso pseudocodice)

• 2roblema del resto

• 3lgoritmo di scheduling 4 Shortest 5ob (irst .algoritmo di oore/

• 6aino:

Complessit!: -.nlogn/ per l7ordinamento, -.n/ per la scelta dei valori

Prolema della compressione!

2roblema della compressione .codici di 8uffman, nessun codice # prefisso di altro

codice/:


51/98

Teorema! 9output dellalgoritmo 8uffman per un dato file # un codice a prefisso

ottimo

$chema della dimostra"ione!

• Sottostruttura ottima

o Dato un problema sullalfabeto , # possibile costruire un sottoproblema

con un alfabeto pi& piccolo

• 2ropriet! della scelta greed;

o Scegliere i due elementi con la frequenza pi& bassa conduce sempre ad

una soluzione ottimale

Sia• un alfabeto, f un arra; di frequenze•


52/98

• Scambiamo x con a: otteniamo T

• Scambiamo y con b: otteniamo T ?

Dimostriamo che:

• C.f,0 / = C.f, 0 / = C.f,0/

a poich> 0 # ottimo, sappiamo anche che:

• C.f,0/ = C.f,0 /

@uindi 0 # anchesso ottimo

*Sottostruttura ottima: qualcuno me la rispieghi


53/98

%lero di copertura di peso minimo

Due algoritmi greed;: Arus'al e 2rim

Per caratteri""are gli archi sicuri doiamo introdurre alcune de&ini"ioni!• Bn taglio (S,V-S) di un grafo non orientato G=(V,E) # una partizione di V in due

sottoinsiemi disgiunti• Bn arco [u,v] attraversa il taglio se u S e v V-S• Bn taglio rispetta un insieme di archi A se nessun arco di A attraversa il taglio• Bn arco che attraversa un taglio # leggero nel taglio se il suo peso # minimo fra

i pesi degli archi che attraversano un taglio

'a regola per riconoscere gli archi sicuri data dal seguente teorema!• Sia G=(V,E) un grafo non orientato e connesso• Sia w una funzione peso a valori reali definita su E•

Sia A E contenuto in un qualche albero di copertura minimo per G• Sia (S,V-S) un qualunque taglio che rispetta A• Sia [u,v] un arco leggero che attraversa il taglioE

%llora• l7arco [u,v] # sicuro per A

Corollario!• Sia G=(V,E) un grafo non orientato e connesso• Sia w una funzione peso a valori reali definita su E• Sia A E contenuto in un qualche albero di copertura minimo per G• Sia una componente connessa .un albero/ nella foresta GA=(V,A)•

Sia [u,v] un arco leggero che connette a qualche altra componente in GA%llora• l7arco [u,v] # sicuro per A


54/98


55/98

Capitolo 15 – Ricerca locale

ShellSort

• Inversioni di una sequenza: numero di coppie nell’ordine sbagliato

• Ordinamento: la permutazione che minimizza il numero di inversion

• Vantaggi della InsertionSort (pochi passi quando è quasi ordinata)

• Elimina gli svantaggi della InsertionSort (quello di spostare solo elementi

adiacenti tra loro)

• Invece di considerare elementi a distanza ! li considera prima a distanza

"#$! poi $%&! '! &"! $! & e (esempio)

• uando h ! è in pratica una insertion sort! questo garantisce la correttezza

• *er n non troppo grandi! è migliore di altri algoritmi asintoticamente migliori

• Ordinamento sul posto


56/98

• +a complessit, è piena di casi particolari

Problemi di flusso

• -ete di .lusso: (V!E!s!p!c)

o /ra.o orientato /(V!E)

o Vertice sorgente (s) e pozzo (p)

o 0unzione di capacit, c: V1V 2 3

• 0lusso: .unzione V1V2 4

o .(u! v) 5.(v! u)

o .(u! v) 6 c(u! v)

o Sommatoria di tutti i .lussi uscenti da un certo nodo " (tranne per

sorgente e pozzo)

uesto per via dei .lussi all’incontrario

• Valore di .lusso:

o Sommatoria di tutti i .lussi tra tutti i nodi (in pratica! quanto passa visto

che gli opposti si annullano)

o Si vuole trovare il massimo . possibile

• 7apacit, residua di un .lusso: .unzione che ci dice per ogni coppia di nodi!

quanto avanzerebbe per quell’arco


57/98

• -ete residua: (V! Er! s! p! r) è come l’originale! solo che la capacit, è sostituita

dalla capacit, residua e gli archi sono tutte le coppie per cui rimane una

capacit, residua

• 0lusso nullo: .lusso che restituisce " per ogni u! v

• 7ammino aumentante per .: cammino da sorgente a pozzo in -

• 7apacit, del cammino: è la pi8 piccola tra quelle degli archi del cammino

• 0lusso aumentante: (99)

• etodo delle reti residue

o Il .lusso corrente viene inizializzato a .lusso nullo

o Si ripetono i seguenti passaggi .inch; g < ."

7alcola la rete residua! sostituendo la capacit, originale con

quella residua

Si cerca un .lusso aumentante g per -

. = g


58/98

• >aglio: suddivisione in due dei nodi in modo che sorgente e pozzo rimangano

separati

• 7apacit, del taglio: la somma! per ogni coppia di nodi tra parte e parte '!

delle capacit,

• >aglio minimo: taglio con capacit, minima

• Il .lusso che attraversa un taglio è la somma! per ogni coppia di nodi tra parte

e parte '! dei .lussi

• Il valore di un .lusso che attraversa un qualsiasi taglio è uguale a quello degli

altri

• >eorema .lusso massimo ? taglio minimo: dimostrazioni equivalenti:

o . è un .lusso massimo

o 3on esistono cammini aumentanti per .

o Esiste un taglio (S!*) tale che@.@ c(S! *)

• Varianti

o 0ord50ulAerson (qualunque algoritmo di visita) O(@.B@ (m=n) )

o Edmonds5Carp (visite in ampiezza) O(nm')


59/98

o Dlgoritmo dei tre indiani O(n$)


60/98

Capitolo 16 – Backtrack

• Tipi di problem

o IEnumerable GetPossibleSolutions()

o Solution GetFirstSolution()

o int CountPossibleSolutions()

• Algoritmo di Grahm (Inviluppo onvesso ! disegnare un poligono onvesso

attorno a dei punti" pi# piolo possibile) ! $(n log n)

o Il punto on ordinata minima %a parte dell&inviluppo onvesso

• Fai 'ualosa e dis%alo se non orretto

•

Pruning lasiar perdere le solu*ioni par*iali he non porteranno a niente

• (+ regine" solite ose del %il*)

• Per le regine" la tenia migliore invee una minimum,on%lits heuristi si

muove il pe**o on il maggior numero di on%litti nella asella della stessa

olonna on minor numero di on%litti- +on per. garantita la termina*ione

sempre orretta

• Giro di avallo andare ni giro ol avallo su una sahiera %ino a rioprire

tutte le elle esattamente una volta

o S/0/0 ontiene il numero di passo in ui entro in una ella (12non

anora)

• Sudo3u" Giri di avallo appunti guella


61/98

Capitolo 17 – algoritmi probabilisticiIl calcolo delle probabilità è applicato non ai dati di input, ma ai dati di outputDue possibilità:

• Algoritmi corretti, il cui tempo di funzionamento è probabilistico•

Algoritmo la cui correttezza è probabilistica

Espressione polinomiale nulla

Data un’espressione polinomiale in n variabile, dire se è nulla o no. Non ci sono

monomi. Gli algoritmi basati su semplificazioni sono molto complessi.

• i genera una n!pla di valori v1, ..., vn• i calcola "# p(v1 , ... , vn)

o e x $ %, p non è identicamente nulloo e x # %, p potrebbe essere identicamente nullo

• e vi # random&', (d), dove d è il grado massimo del polinomio, allora laprobabilità di errore non supera '*(.

• i ripete k volte, riducendo la probabilità di errore a &'*()k

StatisticaAlgoritmi statistici sui vettori: estraggono da un vettore numerico alcune

caratteristic+e statistic+e rilevanti &media, varianza, moda, mediano).

Selezione: dato un arra di valori distinti ed un valore - compreso nel range del

vettore, trovare l’elemento c+e è maggiore di esattamente !' elementi.

/icerca del minimo, massimo:• T &n) # n!' # 0&n) confronti

1ossiamo dimostrare c+e 2uesto algoritmo è ottimale3 Idea:• scelta del minimo come un 4torneo5• 6utti gli elementi &tranne il vincitore) deve perdere almeno un 4partita5• 7uindi il problema è 8&n)

6rovare il secondo minimo dell’arra


62/98

9albero del torneo permette di trovare il secondo minimo in ;&n < log n) confronti nelcaso pessimo:

• n passi necessari per la ricerca del minimo• iano = e il minimo e il secondo minimo• icuramente cè stato un 4incontro5 fra = e , dove = +a 4vinto5•

e cos> non fosse, esisterebbe un valore ?@ c+e +a 4battuto5 assurdo dalladefinizione di 7uindi, basta cercare nei log n valori 4battuti5 direttamente da = per trovare ilsecondo minimo. 6otale: ;&n < log n)

9’albero del torneo puB essere simulato da uno +eap:

Non va bene se C# n*(. 7uesto va meglio:

eguono cenni a cose complicate.


63/98

Capitolo 18 – Teoria dell’NP-Completezza• Dominio limitato, quello delle tessere. Non c’è un algoritmo migliore della forza

bruta (si pensa che nemmeno ci sia)

•

Colorazione (carta geografica)

• Commesso viaggiatore

• rogrammazione lineare !"#$ data una matrice % di elementi interi didimensione m&n ed un vettore b di m elementi, esiste un vettore & di n elementi!"# tale che %&'b

• oddisfabilit*$ quello dell’equazione booleana e dire se si pi+ rendere vera

ono tutti problemi tanto -.

Certificato polinomiale

n algoritmo che data una presunta soluzione del problema verifica in tempopolinomiale che tale soluzione sia effettivamente una soluzione che da risposta /.

Algoritmo non deterministico

%lgoritmo che, posto di fronte alla necessit* di prendere una 0decisione1, ha la 0virtu2magica1 di scegliere sempre la strada giusta3/n termini equivalenti, è come se l’algoritmo, di fronte a pi4 alternative, le seguissetutte contemporaneamente, generando pi4 0copie1 di se stesso.Ciascuna copia procede la computazione, indipendentemente dalle altre, seguendo

una e una sola delle alternative possibili.


64/98

Istruzioni elementari O(1

• C!oic!e(c$ sceglie arbitrariamente un elemento dell’insieme finito C

• "ailure$ che blocca la computazione in uno stato di fallimento

•

#uccess$ che blocca la computazione in uno stato di successoNon determinismo

Non determinismo$ sc!ema generale


65/98

Non determinismo tramite enumerazione

Classe P

Classe di tutti i problemi decisionali risolvibili in tempo polinomiale con algoritmideterministici

Classe NP

5a classe di tutti i problemi decisionali risolvibili in tempo polinomiale con algoritmi

non deterministici

• è contenuta in N

• Non si sa se N è contenuta in

%iduci&ilit' polinomiale

iano A e B due problemi decisionali. i dice che A si riduce in tempo polinomiale a B,e si scrive A 6 B, se esiste una funzione f di trasformazione$

f $ (dati d’ingresso per A) 7 (dati d’ingresso per B)

8ale che$• f è computabile in tempo polinomiale con un algoritmo deterministico9


66/98

• x è un dato d’ingresso per cui A d* risposta : se e solo se f(x) è un datod’ingresso per cui B d* risposta :


67/98

;seguono cenni e spiegazioni poco comprensibili


68/98

Capitolo 19 – Tecniche risolutive per problemi intrattabili

• Bisogna rinunciare a qualcosa

o Generalità (algoritmi pseudo-polinomiali): per alcuni input, il problema

potrebbe essere intrattabileo Ottimalità (algoritmi approssimazione): si cercano soluzioni non troppo

distanti da quella ottima

o Efficienza (algoritmi branchbound): si pota quando non si intra!edono

soluzioni buone

o "ormalità: (algoritmi euristici): soluzioni che sembrano buone, anche

senza dimostrazione matematica

• #omma di sottoinsieme: esiste un sottoinsieme che ha una certa somma$

o #e la somma desiderata % O(nc), la complessità % polinomiale

o #e la somma desiderata à esponenziale, la complessità % esponenziale

• &lgoritmo 'ate-onotonic (iu, a*land): assegnare tempo di cpu a dei

processi periodi

• (continua+)


69/98

Misc

Ricorrenze lineari con partizione bilanciata Tn=aTn/b+cnβa≥1b≥2β≥0α=logalogb

• α≠β:Onmaxα, β• α=β:O(nmaxα, βlogn)•

• Master theorem• Tn=aTn/b+fn• a≥1

• b≥1α=logba

• ∃ ε≥0 :fn=Onα-ε⇒Tn=nα• fn=Θnα ⇒Tn=Θf(n)logn• ∃ ε≥0 :fn=!nα+ε∃ c"1 :afnb#cfn ⇒Tn=Θf(n)

• ($a %n c&'o n n *o)

• Ricorrenze lineari di ordine costante

•

• c0, β≥0• a=a

• a=1⇒Onβ+1• a≥2⇒O(nβan)

•


70/98

ANALISI DI ALGORITMI

Dimensione dell’input

Criterio di costo logaritmico: la taglia dell'input è il numero di bit necessari perrappresentarlo .sempio! moltiplica"ione di numeri binari lung#i n bit

Criterio di costo uniforme: la taglia dell'input è il numero di elementi c#e locostituiscono. sempio! ricerca minimo in un arra$ di n elementi

In molti casi: possiamo assumere c#e gli %elementi& siano rappresentati da unnumero costante di bit. Le due misure coincidono a meno di una costantemoltiplicatia

Modello di calcolo: rappresentazione astratta di uncalcolatore

Astrazione: dee sempli(icare i dettagli) altrimenti è inutile

Realismo: dee ri(lettere la situa"ione reale

Potenza: dee permettere di trarre conclusioni (ormali sul costo

Binary search

*un"iona solo su ettori ordinati. +omplessit,!O-log n


71/98

aratsu!a

Sere per moltiplicare due binari con diide et impera

+omplessit,! O-n

/.01

"election sort

Ordina un ettore mettendo il minimo all2ini"io ogni olta +omplessit,!O-n3


72/98

Merge sort

Ordinare un ettore con diide et impera +omplessit,!O-nlog-n

Analisi ammortizzata

+i sono tre metodi per (are l2analisi ammorti""ata!

Metodo dell’aggregazione:

• Si calcola la complessit, O-(-n per eseguire opera"ioni in se4uen"a nelcaso pessimo

• Il costo ammorti""ato di una singola opera"ione è O-(-n5n

Metodo degli accantonamenti #consigliato$:


73/98

• Alle opera"ioni engono assegnati costi ammorti""ati c#e possono esseremaggiori 5minori del loro costo e((ettio

• 6roare c#e la somma dei costi ammorti""ati è un limite superiore al costoe((ettio

Metodo del potenziale #ignorato$

Counting sort

7asato non sui con(ronti) dipende dal range -8 dei numeri+omplessit,! O-n98


74/98

STR:TT:R LMNTARI

%ista circolare& !idirezionale& con sentinella

; possibile reali""are le liste con i ettori) bisogna gestire per< il problema delladimensione dinamica) meglio gestirla come (a =aa nell2arra$ list) incrementa ogniolta del doppio e dime""a 4uando l2occupa"ione è pari ad un 4uarto.


75/98

"tac'

*un"iona come i piatti in pi""eria) LI*O

(ueue


76/98

*I*O

AL7RI 7INARI DI RI+R+AAlberi binari in cui il (iglio sinistro è pi> piccolo del padre) il (iglio destro pi> grande

del padreAl!eri !inari di ricerca

Ricerca: implementazione

+erca un alore nell2albero +omplessit,!O-logn


77/98

Ricerca del minimo e del massimo

+omplessit,!O-logn


78/98

"uccessore)predecessore

"uccessore: di un nodo è il pi> piccolo nodo maggiore di 4uel nodo

Inserimento

Nel caso pessimo dobbiamo scorrere tutto l2alte""a dell2albero+omplessit,! O-logn


79/98


80/98

Cancellazione

7isogna se in caso modi(icare l2albero perc#? rimanga un A7R

Bilanciamento degli al!eriSpesso le opera"ioni -ricerca) cancella"ione ecc sugli A7R dipendono dall2alte""adell2albero. +oniene 4uindi cercare di tenere l2albero il pi> possibile bilanciato! c#enon i sia troppa dise4uit, di pro(ondit, (ra sottoalbero destro e sottoalbero sinistro.6er (are 4uesto dobbiamo (are ogni tanto delle rota"ioni.


81/98

Al!eri Red)Blac' *+reee,

Sono implementati per preedere la bilanciatura dell2albero. Ogni nodo pu< essererosso o nero) le (oglie non contengono alori) sono nodi nil - in trealt, ne esiste solouno) tutti puntano a 4uello) per risparmiare memoria. La radice è nera) tutte le(oglie sono nere) i (igli di un nodo rosso sono ambedue neri.

In pratica root e (oglie sono neri) non posso aere due rossi consecutii. Il pat# diogni (oglia contiene lo stesso numero di nodi neri.

Altezza nera: il numero di nodi neri lungo ogni percorso da un nodo -escluso aduna (oglia -inclusa. Si indica con b-

Altezza nera di un al!ero: è l2alte""a nera della radice


82/98

RB)+ree rotazione a sinistra

RB)+ree inserimento nodo

+ome negli A7R) poi si sistema il tutto +omplessit,!O-log n


83/98


84/98

RB)+ree cancellazione

*un"iona come negli A7R) solo c#e poi dobbiamo decidere se aggiustare o no) sidee aggiustare solo 4uando il nodo cancellato è nero!

"e il nodo cancellato - rosso:

•

l2alte""a nera rimane inariata• non sono stati creati nodi rossi consecutii

• la radice resta nera

"e il nodo cancellato - nero:

• la radice pu< essere un nodo rosso

• se il padre e uno dei (igli del nodo erano rossi ci troiamo con due rossi di (ila

• cambia l2alte""a nera

Complessit: /isitiamo 0#log n$ nodi ognuno in tempo 0#1$& 2uindi 0#log n$


85/98


86/98

INSIMI DI@IONARI

Riepilogo complessit

Insieme: colle"ione di oggetti

Dizionario: insieme di associa"ioni c#iaealore

Insiemi realizzati con /ettori !ooleani


87/98

3antaggi: noteolmente semplice) e((iciente eri(icare se un elemento appartieneall2insieme

"/antaggi: occupa"ione di memoria O-N) indipendente dalla dimensionedell2insieme) opera"ioni ine((icienti O-N

Insiemi realizzati con liste non ordinate3antaggi: occupa"ione di memoriapropor"ionale alla dimensione del ettore

"/antaggi: opera"ioni di ricerca) inserimento ecancella"ione O-nB unione) interse"ione edi((eren"a O-nm

Insiemi realizzati con liste ordinate

3antaggi: occupa"ione di memoriapropor"ionale alla dimensione del ettore)opera"ioni di unione) interse"ione e di((eren"aO-n

"/antaggi: opera"ione di ricerca) inserimentoe cancella"ione! O-n

Insiemi realizzati con strutture dati complesse

Con al!eri di ricerca !ilanciati:

• Ricerca) inserimento) cancella"ione! O-logn

• Ciene mantenuto l2ordinamento• lencare tutti gli elementi! O-n

Con ta!elle hash:

• Ricerca) inserimento) cancella"ione! O-/

• Ciene perso l2ordinamento

• lencare tutti gli elementi! O-m doe m è la dimensione della tabella #as#


88/98


89/98

A6 M*ST

Code con priorit

Le opera"ioni base iste (in ora -cancella"ione) inserimento ecc possono nonbastare) certe olte dobbiamo inentarne di nuoe. Le code di priorit, sono unastruttura dati (atta apposta per essere e((iciente a (are determinate opera"ioni. Glioggetti sono estratti dalla cosa in base alla loro priorit,.

Al!ero !inario perfetto

Tutte le (oglie #anno la stessa alte""a) tutti) tranne le (oglie #anno due (igli. Alte""aè 4uindi log n.

Al!ero !inario completo Tutte le (oglie #anno pro(ondit, o /. Tutti i nodi a liello sono accatastati asinistra. Tutti i nodi interni #anno grado due) eccetto al pi> uno.

4eap

; un particolare tipo di coda di priorit, nella 4uale i dati sono mantenuti in modopar"ialmente ordinato.

Ma5 heap: albero binario completo in cui la radice è sempre il maggiore. -anc#enei sottoalberi) il padre è sempre il maggiore

Min heap: albero binario completo in cui la radice è sempre minore -anc#e neisottoalberi

Gli #eap non impongono nessun ordinamento (ra i (igli di un nodo -ordinamentopar"iale) l2importante è c#e i padre sia maggiore o minore rispettiamente per ilmaE e per il min #eap.

• Ogni nodo è maggiore o uguale di se stesso

• Se n Fm e mFn allora nm

• Se nFm e mFr allora nFr

L2ordinamento par"iale è utile per modellare gerarc#ie complesse o per mantenere

in(orma"ioni par"iali. ; pi> semplice costruire uno #eap ordinato par"ialmente c#e4ualcosa ordinato totalmente.

Array heap

• AH/ contiene la radice

• p-i Hi53 -limite in(eriore. 6adre


90/98

• l-i 3i. *iglio sinistro

• r-i 3i9/. *iglio destro

Procedure per gestire uno heap

Ma5 heap restore

Sere per mantenere la propriet, dei maE #eap dopo un inserimento +omplessit,!O-logn

Ogni sottoalbero dee essere un maE #eap) 4uindi si cerca di (are scendere (ino al

posto giusto il alore

4eap !uild

Sere per costruire un maE #eap da "ero -dato un ettore+omplessit,! O-nlogn

4eapsort


91/98

Ordina sul posto un arra$ +omplessit,! O-nlogn

Coda con priorit

:na struttura dati c#e sere a mantenere un insieme S di elementi E) ciascuno con

un alore associato di priorit,


92/98


93/98

Riduzione priorit

M6"7+

Serono a rappresentare degli insiemi disgiunti) le opera"ioni (ondamentali sonounire pi> insiemi) identi(icare l2insieme a cui appartiene un oggetto. ; una colle"ionedi insiemi dinamici disgiunti -un insieme di insiemi. Ogni insieme è rappresentatoda un rappresentante unioco. Le ricerc#e del rappresentate sullo stesso insiemedeono restituire sempre lo stesso oggetto. Solo dopo un unione 4uesto oggetto pu<cambiare. Si pu< scegliere l2elemento pi> piccolo5grande di un insieme


94/98

Applicazione: tro/are le componenti connesse di un

grafo

Alla (ine aremo l2insieme delle comonenti connesse. +omplessit,!O-n9m


95/98

Implementazione !asata su liste

• realizzazione !asata su liste: find 0#1$ merge 0#n$

• reali""a"ione basata su alberi! (ind O-n merge O-/

coniene anc#e inserire l2euristica del peso -se liste 5 rango -se alberi e la

compressione dei percorsi. uristica sul peso! #o due liste) per unirle deo scegliereuno dei due rappresentanti ed applicarlo all2altra lista) logicamente attacco la pi>corta alla pi> lunga) 4uindi mi salo anc#e la dimensione.

Nel caso delle liste! ogni elemento contiene un puntatore al successio) unpuntatore al rappresentante ed un oggetto

6u< essere isto come un albero di alte""a /

L2opera"ione (ind ric#iede O-/) si restituisce il rappresentante di J

Il merge-E)$ ric#iede pi> tempo) si appende la lista c#e contiene K alla lista c#econtiene J) e poi engono modi(icati tutti i puntatori) caso pessimo per n opera"ioniO-n3) costo ammorti""ato! O-n.

Implementazione !asata su al!eri

Ogni nodo #a un oggetto ed il puntatore al padre) la radice punta a se stessa ed è ilrappresentante

*ind O-n nel caso pessimo) bisogna risalire (ino a troare la radice

Merge-E)$ O-/ si appendono gli alberi

ui coniene applicare la compressione dei cammini!


96/98

uando si cerca 4ualcosa portiamo tutto in su. +os le successie ricerc#ecosteranno O-/!

DICID T IM6RA

Di/ide: diidi il problema in sotto problemi pi> piccoli ed indipendentiImpera! risoli i sotto problemi ricorsiamente

Com!ina! unisci le solu"ioni dei sottoproblemi


97/98

Ordina un ettore sul posto) diide comlicato) nessun combina +omplessit,!O-nlogn

Parentesizzare #decidere 2uale motiplicazione dimatrice fare prima$

Strassen O-n3.1/

inograd O-n3)1


98/98

TEOREMI DI ALGORITMI

----------------------------- Ricorrenze lineari con partizioni

bilanciate: Tn= aTnb+cnβn>1dn=1

ondizioni: a! b interi" a#1! b#$" c!d!β reali" c!d>% β#%

&=lo'ba

(e &>β Tn=On&

(e &=β Tn=On&lo' n

(e &)β Tn=Onβ

• Esempio quando alfa > beta

Tn=$Tn*+1 &=1$!β=% Tn=On&=On ,

• Esempio quando alfa = beta

Tn=$Tn*+n &=1$!β=1$ Tn=On&lo'n=Onlo'n ,

• Esempio quando alfa < beta

Tn=$Tn*+n &=1$!β=1 Tn=Onβ=On

--------------------------------------------------------------- Mater

t.eore/: Tn= aTnb+0n,n>1dn=1

&=lo'ba

(e 0n=On&- 2>% Tn=3n&

(e 0n=3n& Tn=3n&lo' n(e 0n=4n&+2>%! c)1! /#% 5 a0nb6c0n 7 n#/ Tn=O0n,

• Esempio fn=Onα-δ:

Tn=8Tn9+n &=lo'98=$ dobbia/o cercare n delta c.e 0accia riltare &-=eponente di n"

Eite e ;ale 1"

Algoritmi-riassunto

Documents

Transcript of Algoritmi-riassunto