θ O o Ω ω  
Insertion-sort
pess O(n²)
medio O(n²)
ottimo O(n)

20n + 36 nlogn è o(n²)
n²+n/3+nlogn è O(n²)
n(n-1)/2 è O(n²)
20n +36nlogn è Ω(n)
n²+n/3+nlogn è Ω(n²)
n(n-1)/2 è Ω(n²)
20logn +36n²logn è Ω(n²log(n))
se lim n->inf di f(n)/g(n)=0 => f(n) è o(g(n))
se F(n) é O(g(n)) => il lim per n --> inf di f(n)/g(n) è finito

Merge-sort stabile non in place - pess O(nlog(n))
Heap-sort non stabile in place-pess O(nlog(n))
Quick-sort non stabile in place- **pess O(n²) **med θ(nlog(n))
Partititon θ(n)
Insertion sort stabile in place
Bucket stabile non in place **med O(n)
Counting stabile non in place **pess O(n+k)
Radix stabile non in place θ(nd+dk)

Il probl di ordinare i n numeri ha compl. Ω(nlog(n))

Metodi per equaz ricors: Albero ricors, Master Method, sostituz

T(n)=T(n/2)+1 ==> T(n)=θ(log(n))
T(n)=T(n/2)+n ==> T(n)=θ(nlog(n))
Dato x=logBa la soluz T(n)=aT(n/b)+θ(n^x) é T(n)=θ(n^x)

PQ struttura dati astratta, operaz EstrMax, Inserim
Ricercare max in PQ dipende da implementaz
Ric & Estr max in PQ implement con vet non ordinat è θ(n) 
Ric & Estr max in PQ implement con vet ordinat è θ(1)
Ric & Estr max in PQ implement con heap è θ(log(n))
Ins x in PQ implement con vet non ordinat è θ(1)
Ins x in PQ implement con vet ordinat è θ(n)
Ins x in PQ implement con heap è θ(log(n))

Build-heap O(n)
Heapify O(lgn)
Alb binario altezza h ==> foglie 2^h
Ric Ins Canc x da alb bin con n nodi e altez h O(log(n)) O(h)
RedBlackTree ogni nodo è rosso o nero e tuute foglie nere
			 ogni rosso ha figli neri
			 black height è il num di nodi neri(senza x)nel camm da x a una foglia ed è la stessa...
			 n nodi ==> altez <= 2log(n+1)											>
			 n nodi interni non inferiore a 2^(bh(x))-1
			 rotazione cost comp costante
			 Canc Ins nodo O(log(n))

Pila LIFO
Coda FIFO
Delete x in DoublyLinkList O(1)
Ricerc x in "			" O(n)
Inserir x in "			" O(1)
Ricerc x in "			" ordinata O(n)
Delete x in SinglyLinkList O(1)
Ricerc x in "			" O(n)

Hash costo comput costante
chiave i memorizzata in h(i)
iniettiva si
biettiva non ho collis ma tab troppo grande
generare pos che dipend da tutti i bit dela chiave
assomigliare random
usando chaining un atab con m pos puo cont + di m elem
Load factor rapport tra num elementi e dimens tabella
Ricerca Hash con chaining **med θ(1+loadfactor) ma solo SUH
						  **pes θ(n elementi in tab)
Hash Open Add il LoadFactor mai >1, lung media di probe 1/(1-loadFactor)

Programm Dinamica passi: caratterizza della strutt di una soluz ottima
						 def ricors del valore di una sol ottima
						 costruz di una soluz ottima 
						
B TREE
ad ogni nodo num chiavi, chiavi, flag 
tutte foglie hanno stessa profondità O(logn)
gardo minimo t indica il min num di chiavi memorizzate
caso particolare di BST
se grado min t>=2 ==> h<=logT((n+1)/2)							>
num accessi a HD per un dato O(logTn)
Tempo CPU per un dato O(tlogTn)
operaz creaz di new tree,ricerc inser e canc di chiavi
BTreeSearch permett di trov un achiave k in un sottoalb di rad x
BtreeCreate Accessi HD e Temp CPU O(1)
nodo pieno quandocontiene 2t-1 chiavi
BTreeSplitChild param:nodo padre, indice in padre, nodo da spezza θ(t)
Ins elemento num accessi HD O(h), Tempo CPU O(th)
Canc effettuata ricorsivam da radice verso foglie
	 si scende ad un new liv dell'alb se il nodo contienemeno di t elementi
	 gestisce tre casi: k in un foglia, k in un nodo intern, k probabilmente in un nodo inf
	 cancellaz e fusion quando ci e tutti i fratelli hanno t-1 elementi
	 Tempo CPU O(th)=O(tlogTn)
	 può richiedere di risalire il BTree verso radice
	 Accessi disco O(h)
	 
HEAP BINOMIALE
insieme di alberi binomiali
i nodi di un alb bin Bk sono 2^k
altezza con 2^k nodi è k
i nodi a profondità i sono Esattamente(k su i)
Bk con altezzak radice ha grado k
campi: p,key,deg,child,sibling

complessità più alta θ(logn) nell inserimento

HEAP FIBO
insieme di alberi , non necessar binomiali, con ordinamento parziale a heap, non sono ordinati
sono meno vincolate risp a heap binom, permettono di differirne la riorg.
i nodi marcati hanno perso un figlio dall'ultima volta in cui erano diventati loro stessi figli
	di un'altro nodo
campi: p,key,data,deg,child,left,right
Insert inserisc nodo x nell H fibo inserendola nelle radici
Estraz del nodo min complicata richiede ristrutturaz
Decrease richiama Cut che toglie x dalla list dei figl di y e lo agg nelle radic, fa uso
	di Cascading-Cut
tempo ammort di ExtractMin è O(lgn)
n di nodi cresce esponenzialm in deg(x)
deg(y1)>=0 e deg(y-i)>=i-2 i=2,3,...,k
F0=0, F1=1, Fk=F(k-1)+F(k-2)
F(k+2)=1+Σi=0...k Fi per ogni k>=0
size(x)>=F(k+2)>=Φ^k, con Φ^k=(1+rad(5))/2
grado max di D(n) è O(lgn)

INSIEMI DISGIUNTI
insieme partiz in sottoinsiemi
operaz: Make-Set,Unin,Find-Set
UP TREE
possono rappr ins disg assoc un uptree ad ogni ins disg
la rad cont il rappresent che è padre di se stesso, ogni elem ha campo chiave e un punt a padre, ogni
	elem punta solo al padre
unione: si fa punt dalla radic dell'alb che ha meno nodi la radice dell'alb che ha più nodi
compressione di camm: serve nel corso dell FindSet, fa puntare dirett alla radic ogni nodo del camm d'accesso...
rank= limite sup all'altez di x, lim sup al num di archi del cammin più lung fra x e una foja discend
modificano rank:MakeSet e Link
La funz F(0)=1 e F(i)=2^(F(i-1)) è tale per cui gia F(5)...
se i=log*(n) ==> i + picc intero | F(i)>=n, i + picc intero | log log...log(n)<=1 ripet i volte >
la funz log* cresce molto molto lentam, tale per cui log*(n)<=5 per ogni... >
Ackerman A(i,j) definita: A(i,j)=2^j per j>=1, A(i,1)=A(i-1,2)per i>1, A(i,j)=A(i-1,A8i,j-1)) per i,j>1
inversa α(m,n)=i se i è il + picc int | A(i,mVn|)>log(n)
per tutte le radici x di alberi, size(x)>=2^rank(x)
Data una foresta...0(mlog*n)

GRAFI
coppia di insiemi V e E
somma gradi = doppi del num archi in E
spazio necessario per rappres le list di adiac θ(m+n)
"					" contenere la matrice di adiac θ(n²), O(n²)

RIC AMPIEZZA BFS
percorre componente connessa di G e ne def un albero di..
Tempo CPU O(V+E) lineare(con list di adiacenz)
Il sottografo G'=(V',E') dei predec... ...è un albero contenente tutti i vertici raggiungibili da s...

DFS
inizializzaz e fase di esploraz ricors
si appoggia a DFS-Visit(u) che ad ogni invocaz..., effettua il backtracking nella ric...
tempo CPU θ(V+E)
il sottografo...forma una foresta di sottoalb DF
In una DFS di un grafo nn orientato G ogni arco è: unarco dell'alb opp un arco di backtrack, 
	un arco all'indietro
	
DAG
grafo diretto che nn contiene cicli diretti
ordinamento lineare dei vertici
TopologicalSort identifica un ordinamento topologicodi un DAG G calcolando...,introduce gli archi transitivi...
Grafo diretto G aciclico sse 1 ricercaDFS su G nn produce archi all'indietro
Tempo CPU O(V+E)
dimostraz correttezza se(u,v)appartiene E ==> f[u]>f[v]
Nel caso di un DAG è possibile calc i cam min sfruttand un ordinam topol dei vert di G
Compless DAG-shortest-path O(V+E)

COMPONENTI FORT CONNESSE
StronglyConnectedComponents trova In tempo O(V+E) le comp...
	correttezza per induzione
nessun cammino fra loro esce dalla CFC
Un avo(u)... è il vertice w:più lontano, che massimizza f[w]

ALBERI DI COPERTURA MINIMI
albero T=(V,E')...
Kruskal utilizza MakeSet, FindSet, Union
	trova albero copertura minimo del grafo G
	costruisce un MST scegliendo sempre l'arco di cost minimo fra quelli nn ins che nn chiuda un anello
	mantiene archi ordinati per costo nn decrescente
	provare correttezza(V,E' U e), e arco di costo min che unisce G1 e G2, è un sottograf di qualc MST
	compless O(ElogE)
Prim utilizza Extract-Min
	trova albero di cop min
	costruisce un MST scegliendo sempre l'arco di cost minimo fra i nn ins che nn chiuda un anello e che sia conn...
	non necessita di particolari ordinam delegand alla ExtractMin la gest dei costi degli archi di G
	compless O(E+VlogV)
	
CAMMINI MIN CON SORG SING
per ogni vertic v app V il cammino di peso minim da s a v
analoga a BFS
viene mantenuto un predecessore π(v)
Dijkstra mantiene un insieme S di vertici v per cui il costo...
	correttezza si prova dimostrand che al termine dell'esec si ha d[u]=δ(s,u)...
	compless O(V²)
Bellman-Ford perm di indv camm minanche in un graf con archi neg, restituisc false se esist cicli di costo
	neg...,"restituisce un identificativo di "nessuna soluzione"...."
	compless O(V E)

CAMMINI MIN FRA TUTTE LE COPPIE
La matrice dei predec Π={πuv}calcolata...: πuv è NIL se u=v o se nn c'è... ...cammino minimo da u
La riga i-esima della matrice...: un albero dei cammini minimi con radice in i
Floyd-Warshall risolve il prob dei cammini min fra tutte le coppiedi ...
	alg di program dinamica
	accetta archi di peso neg ma nn cicli negativi
	passo ricorsiv Dst(k)=min(Dst(k-1),Dsk(k-1)+Dkt(k-1)) (se k>0)
	realizzato con tre cicli for innestati
	compless θ(V³)
	
PROBLEMI DECISIONALI
Classe di prob ...:scegliere una di due risp possibili "si" o "no"
La classe delle funzioni corrispond...: coputabili del tipo f:N->{0,1}
Il problema del sottografo completo richiede: Dati un grafo G e un intero n, stabilire...
Il problema del cammino hamiltoniano...:stabilire se esiste un cammino che tocchi tutti i vertici di G una e una sola volta
Il prob del cammino eureliano...: stabilire se esiste un cammino che percorra tutti i vertici di G una e una sola volta
Il prob SAT richiede: Data una CNF f stabilire se F è soddisf, cioè se esiste (finisce con 1)
una k-CNF è:una CNF in cui ogni congiunto ha k termini
Un prob di ottimizzazione richiede: di trovare il max e il min di una funzione
Dato un prob di ottimizzazione PO e il corrisp...:PO e PD hanno stessa complessità, è possibile ricondurre PO a PD tramite...
Una istanza di un prob: è un suo caso particolare...
Per codifica di un prob si intende: la corrispondenza fra l'insieme delle istanze...
Un problema decision PD è nella classe P: se esiste un algoritm che risolve qualsiasi...in tempo polinomiale
Una funzione f:{0,1}*-->...: se esiste un algoritm polinomiale che, dato in input un qualsiasi...come output f(x)
Un prob decis PD è nella classe NP: se nn esiste un alg oritmoche risolve..., se esiste un algoritm non-deterministico...
Un algoritmo non-deterministico è...: che può anche contenere istruzioni del tipo goto..., che può dare risultati diversi...
Per realizzazione di un algoritmo non deterministico...:ciascuna delle possibili devierse esecuzioni di A
Un algoritmo non-deterministico A calcola...:per ogni a...=1 esiste una realizzazione..., per ogni a...=0 tutte le realizzazioni...
Per il problema del ciclo euleriano...: polinomiale
Si sa che: P C= NP
f:N->{0,1} è riducibile...: esiste una funzione h, calcolabile... ...x:f(x)=g(h(x))
f:N->{0,1} è NP-completo...: f appartiene NP, per ogni g appartiene NP...
Per dimostrare la NP completezza di una funzione f dalla definizione...:che la funzione è in NP, dimostrare che qualunque altra...
Per dimostrare la NP completezza di una funzione f è necessario: mostrare che la funzione f è in NP, mostrare che gMINp f...     
La prova di NP completezza...: riducendo SAT a CSP
Un algoritmo approssimato A...: il costo C della soluz prodotta da A si discosta per un fatt r(n)... ...soluz ottima max(C/C*,C*/C)...
L'errore relativo ε...: |C-C*|/C*
L'algoritmo A ha un errore relat...: |C-C*|/C*<=ε(n)       >
Uno schema di approssimazione (SdA)...: un algoritmo approssimato A...
Uno schema di approssimazione polinomiale è...: per qualsiasi ε>0 dato richiede...
Uno SdA pienamente polinomiale (fully...: il cui tempo di esecuzione è polinomiale sia per 1/ε
Il problema vertex cover, dato...: trovare un sottoinsieme S di dimensione minima...
Un algoritmo approssimato per vetrex...: scegliere un arco a caso...
L'algoritmo approssimato presentato a lezione per il vertex...: 2
Il prob del commesso viaggiatore(TSP)...: trovare un ciclo hamiltoniano su G...
L'ipotesi della disugualianza triangolare...: è sempre più economico andare direttamente...
Un algoritmo di approssimazione per il TSP per un grafo G: è basato su un albero di copertura minimo per G
L'algoritmo approx-TSP-tour...: 2
Un generico algoritmo euristico: non garantisce niente sulla qualità delle soluzioni trovate
Un algoritmo euristico costruttivo per un prob...: costruisce una buona soluzione migliorando successiv...
L'insieme di vicinanza di una soluzione data: è definito sulla base di una funzione...
Un algoritmo euristico di ricerca locale: parte da una soluzione ammissibile e passa successivamente...
Semplici ricerche locali per il prob del TSP sono: 2-opt, 3-opt