Conclusion del Curso
2
Jérémy Barbay 18 Nov 201018/11/10 a las 14:06 hrs.2010-11-18 14:06:18
CONCLUSION del curso
====================
Author: Jérémy Barbay
Date: 2010-11-18 18:04:09 XXX
* Unidades:
1. Conceptos basicos
2. Memoria Secundaria
3. Tecnicas Avanzadas
4. Extensiones
* Temas
- Implementacion y Experimentacion.
- cotas inferiores
- lemma del ave
- mínimo y m{\'a}ximo de un arreglo
- búsqueda en un arreglo con distintas probabilidades de acceso
- lemma del minimax (para aleatorizacion)
- theorema de Yao-von Neuman
- analisis
- en promedio
- de algoritmos deterministicos
- de algoritmos aleatorizados
- "adaptativa" para
- torre de Hanoi y "Disk Pile" problema
- busqueda ordenada (y codificacion de enteros)
- problemas en linea
- en Memoria Externa
- Diccionarios
- Colas de Prioridades
- Ordenamiento
- en dominio discreto y finito (afuera del modelo de comparacion)
- inter/extra polacion
- skiplists
- hash
- radix sort
- de algoritmos en linea ("online")
- "competitive analysis"
- de esquemas de aproximacion
- "bin packing"
- "Vertex Cover"
- "Traveling Salesman"
- "Backpack"
- amortizada
- enumeracion de enteros en binario
- min max
- en el modelo PRAM
- max
- ranking en listas
- prefijos
====================
Author: Jérémy Barbay
Date: 2010-11-18 18:04:09 XXX
* Unidades:
1. Conceptos basicos
2. Memoria Secundaria
3. Tecnicas Avanzadas
4. Extensiones
* Temas
- Implementacion y Experimentacion.
- cotas inferiores
- lemma del ave
- mínimo y m{\'a}ximo de un arreglo
- búsqueda en un arreglo con distintas probabilidades de acceso
- lemma del minimax (para aleatorizacion)
- theorema de Yao-von Neuman
- analisis
- en promedio
- de algoritmos deterministicos
- de algoritmos aleatorizados
- "adaptativa" para
- torre de Hanoi y "Disk Pile" problema
- busqueda ordenada (y codificacion de enteros)
- problemas en linea
- en Memoria Externa
- Diccionarios
- Colas de Prioridades
- Ordenamiento
- en dominio discreto y finito (afuera del modelo de comparacion)
- inter/extra polacion
- skiplists
- hash
- radix sort
- de algoritmos en linea ("online")
- "competitive analysis"
- de esquemas de aproximacion
- "bin packing"
- "Vertex Cover"
- "Traveling Salesman"
- "Backpack"
- amortizada
- enumeracion de enteros en binario
- min max
- en el modelo PRAM
- max
- ranking en listas
- prefijos
Algoritmos paralelos y distribuidos [2010-11-09 Tue]--[2010-11-18 Thu]
Jérémy Barbay 9 Nov 201009/11/10 a las 11:33 hrs.2010-11-09 11:33:09
Algoritmos paralelos y distribuidos (2 semanas = 4 charlas)
===========================================================
[2010-11-09 Tue]--[2010-11-18 Thu]
- Medidas de complejidad
- Técnicas de diseño
REFERENCIA: Chap 12 of "Introduction to Algorithms, A Creative Approach",
Udi Manber, p. 375
REFERENCIA: [www.catonmat.net/ ... ithms-part-thirteen/]
Table of Contents
=================
1 Modelos de paralelismo
2 Modelo PRAM
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
4 PROBLEMA: Calcular Max(A[1,...,N])
5 LEMA de Brent
6 DEFINICIÓN "Trabajo"
7 COROLARIO
8 EJEMPLO
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
10 PROBLEMA: Ranking en listas
1 Modelos de paralelismo
~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Instrucciones
- SIMD: Single Instrucción, Múltiple Data
- MIMD: Múltiple Instrucción, Múltiple Data
* Memoria
- compartida
- distribuida
* 2*2 combinaciones posibles:
Memoria compartida Memoria distribuida
------+--------------------+-----------------------------------------------------
SIMD PRAM redes de interconexión (weak computer units)
(hipercubos, meshes, etc...)
------+--------------------+-----------------------------------------------------
MIMD Threads procesamiento distribuido (strong computer units),
Bulk Synchronous Process, etc...
* En este curso consideramos en particular el modelo PRAM
2 Modelo PRAM
~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Mucha unidad de CPU, una sola memoria RAM
cada procesador tiene un identificador único, y puede utilizarlo
en el programa
* Ejemplo:
+ if p mod 2 = 0 then
+ A[p] += A[p-1]
+ else
+ A[p] += A[p+1]
+ b <- A[p];
+ A[p]<- b;
* Problema: el resultado no es bien definido, puede tener
*conflictos* si los procesadores están asinchronos. Las soluciones a
este problemas dan varios submodelos del modelo PRAM:
1. EREW Exclusive Read. Exclusive Write
2. CREW Concurrent Read, Exclusive Write
3. CRCW Concurrent Read, Concurent Write
En este caso hay variantes también:
- todos deben escribir lo mismo
- arbitrario resultado
- priorizado
- alguna f() de lo que se escribe
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* DEFINICIÓN:
- $T^*(n)$ es el *Tiempo secuencial* del mejor algoritmo no
paralelo en una entrada de tamaño $n$ (i.e. usando $1$
procesador).
- $T_A(n,p)$ es el *Tiempo paralelo* del algoritmo paralelo
$A$ en una entrada de tamaño $n$ usando $p$ procesadores.
- El *Speedup* del algoritmo $A$ es definido por
$S_A(n,p) = \frac{ T^*(n) }{ T_A(n,p) } \leq p$
Un algoritmo es mas efectivo cuando $S(p)=p$, que se llama
*speedup perfecto*.
- La *Eficiencia* del algoritmo $A$ es definida por
$E_A(n,p) = \frac{ S_A(n,p) }{ p }=\frac{T^*(n)}{pT_A(n,p)}$
El caso óptima es cuando $E_A(n,p)=1$, cuando el algoritmo
paralelo hace la misma cantidad de trabajo que el algoritmo
secuencial. El objetivo es de *maximizar la eficiencia*.
(Nota estas definiciones en la pisara, vamos a usarlas después.)
4 PROBLEMA: Calcular Max(A[1,...,N])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
1. Solucion Secuencial
* Algoritmo:
- $m \leftarrow 1$
- for $i\leftarrow 2$ to $n$
- if $A[i]>A[m]$ then $m\leftarrow i$
- return $A[m]$
* Se puede ver como un arbol de evaluación con una sola rama
de largo $n$ y $n$ hojas.
* Complejidad:
- tiempo $O(n)$, con $1$ procesador, entonces:
- $T^*(n)=n$.
2. Solucion Parallela con $n$ procesadores
* Algoritmo:
- $M[p] \leftarrow A[p]$
- for $l\leftarrow 0$ to $\lceil \lg p \rceil -1$
- if $p \mod 2^{l+1}=0$ y $ p+2^l
Si un algoritmo consigue un tiempo T(n,p)=C,
entonces consigue tiempo T(n,p/s)= sC \forall s>1
(bajo algunas condiciones)
6 DEFINICIÓN "Trabajo"
~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Usando el Lema de Brent, podemos exprimir el rendimiento de
los algoritmos paralelos con dos medidas:
- $T(n)$, el tiempo del algoritmo paralelo usando cualquier
cantidad de procesadores que quiere.
Nota la diferencia con
+ $T^*(n)$, el tiempo del mejor algoritmo secuencial, y
+ $T_A(n,n)$, el tiempo del algoritmo con $n$ procesadores.
- $W(n)$, la suma del total trabajo ejecutado por todo los
procesadores.
7 COROLARIO
~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Con el lema de Brent podemos obtener:
- $$T(n,p) = T(n) + \frac{ W(n) }{ p }$$
- $$E(n,p) = \frac{ T^*(n) }{ pT(n) + W(n) }$$
8 EJEMPLO
~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
* Para el calculo del máximo:
- $T(n) = \lg n$
- $W(n) = n$
* Entonces
- se puede obtener
- $T_B(n,p) = \lg n + {n \over p}$
- $$E(n,p) = \frac{ n }{ p\lg n + n }$$
* (Nota que eso es solamente una cota superior, nuestro
algoritmo da un mejor tiempo.)
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
* DEFINICIÓN: Problema "Prefijo en Paralelo"
Dado $x_1,\ldots, x_n$ y un operador asociativo \times
calcular
- $y_1 = x_1$
- $y_2 = x_1\times x_2$
- $y_2 = x_1\times x_2 \times x_3$
- ...
- $y_n = x_1\times \ldots \times x_n$
* Solucion Secuencial
Hay una solucionó obvio en tiempo O(n).
* Solucion paralela 1
* Concepto:
- Hipótesis: sabemos solucionarlo con $n/2$ elementos
- Caso de base: $n=1$ es simple.
- Inducción:
1. recursivamente calculamos en paralelo:
- todos los prefijos de $\{x_1,\ldots,x_{n/2}\}$ con
$n/2$ procesadores.
- todos los prefijos de $\{x_{n/2},\ldots,x_n\}$ con
$n/2$ procesadores.
2. en paralelo agregamos $x_{n/2}$ a los prefijos de
$\{x_{n/2},\ldots,x_n\}$
* ParallelPrefix1(i,j)
- if $i_p=j_p$
- return x_{i_p}
- $m_p \leftarrow \lfloor \frac{i_p + j_p}{2} \rfloor$;
- if $p\leq m$ then
- algo( i_p, m_p )
- else
- algo(m+1, j_p)
- y_p \leftarrow y_m . y_p
* Otra forma del algoritmo (de p. 384 de "Introduction to
Algorithms, A Creative Approach", Udi Manber):
+ ParallelPrefix1(left,right)
- if (right-left) = 1
- x[right] <- x[left] . x[right]
- else
- middle <- (left+right-1)/2
- do in paralel
- ParallelPrefix1(left,middle) {assigned to {P_1 to P_{n/2}}}
- ParallelPrefix1(middle+1,right) {assigned to {P_{n/2+1} to P_n}}
- for i <- middle+1 to right do in paralel
- x[i] <- x[middle] . x[i]
* Notas:
- este solucion *no* es EREW (Exclusive Read&Write), porque
los procesadores pueden leer $y_m$ al mismo tiempo.
- este solucionó es CREW (Concurrent Read, Exclusive Write).
- Complejidad:
- $T_{A_1}(n,n) = 1+ T(n/2,n/2) = \lg n$
(El mejor tiempo en paralelo con cualquier cantidad de
procesadores.)
- $W_{A_1}(n) = n + 2 W_{A_1}(n/2) - n\lg n$
- $T_{A_1}(n,p) = T(n) + W_{A_1}(n)/p = \lg n + (n\lg n)/p$
- Calculamos $p^*$, la cantidad óptima de procesadores
para minimizar el tiempo:
- $T(n) = W_{A_1}(n) /p^*$
- $p^* = \frac{ W(n) }{ T(n) } = n$
- Calculamos la eficiencia
- $E_{A_1}(n,p^*)
= \frac{ T^*(n) }{ p^* T(n)+W(n) }
= \frac{ n }{ n\lg n }
= {1 \over \lg n}$
- es poco eficiente =(
- PodrÃ-amos tener un algoritmo con
- la eficiencia del algoritmo secuencial
- el tiempo del algoritmo paralelo?
* Solucion paralela 2: mismo tiempo, mejor eficiencia
- Idea:
El concepto es de dividir de manera diferente: par y impar
(en vez de largo o pequeño).
- Concepto:
1. Calcular en paralelo $x_{2i-1}.x_{2i}$ en $x_{2i}$
para $\forall i, 1\leq i \leq n/2$.
2. Recursivamente, calcular todos los prefijos de
$E=\{ x_2,x_4,\ldots, x_{2i},\ldots, x_n \}$
3. Calcular en paralelo los prefijos en posiciones impares,
multiplicando los prefijos de $E$ por una sola valor.
- algo2(i,j)
- for $d\leftarrow 1$ to $(\lg n)-1$
- if $p=0 \mod 2^{d+1}$
- if $p+2^d0$
- $x_{p-2^d} \leftarrow x_{p-2^d}.x_p$
- visualización
0.
1. [0,1]
2.
3. [2,3] [0,3]
4.
5. [4,5]
6.
7. [6,7] [4,7] [0,7]
8.
9. [8,9]
10.
11. [10,11] [8,11]
12.
13. [12,13]
14.
15. [14,15] [12,15] [8,15] [0,15]
- Notas:
- Este algoritmo es EREW
- Análisis
- $T_2(n) = 2\lg n$
- $W(n) = n + W(n.2) = n$
- $T_2(n,p) = T(n) + W(n)/p = 2\lg n + \frac{n}{p}$
- Calculamos la cantidad óptima de procesadores para obtener
el tiempo óptima:
- $T_2(n) = W(n) / p^*$ entonces
- $p^* = {W(n) \over T(n)} = {n\over\lg n}$
- $E_2(n,p^*) = { T^*(n) \over p^* T(n)+ W(n)} = n/n \in O(1)$
10 PROBLEMA: Ranking en listas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
1. DEFINICIÓN
- dado una lista, calcula el rango para cada elemento.
- En el caso de una lista tradicional, no se puede hacer
mucho mejor que lineal.
- Consideramos una lista en un arreglo $A$,
- donde cada elemento $A[i]$ tiene un puntero al siguiente
elemento, $N[i]$, y
- calculamos su rango $R[i]$ en un arreglo $R$.
2. DoublingRank()
- $R[p] \leftarrow 0$
- if $N[p] = null$
- R[p] \leftarrow 1
- for $d\leftarrow 1$ to $\lceil\lg n\rceil$
- if $N[p]\neq NULL$
- if $R[N[p]]>0$
- $R[p] \leftarrow R[N[p]]+2^d$
- $N[p] \leftarrow N[N[p]]$
3. Análisis
- T(n) = \lg n
- W(n) = n + W(n/2) = O(n)
- T(n,p) = T(n) + W(n)/p = \lg n + n/p
- p^*
T(n) = W(n) / p^*
p n/\lg n
- E(n,p^*) = \frac{T^*(n)}{ p^* T(n) + W(n) }
= \frac{ n }{ n/\lg n \lg n +n}
= \Theta(1)
4. El algoritmo es EREW o CREW?
- es EREW si los procesadores están sincronizados, com en RAM
aquÃ-.
===========================================================
[2010-11-09 Tue]--[2010-11-18 Thu]
- Medidas de complejidad
- Técnicas de diseño
REFERENCIA: Chap 12 of "Introduction to Algorithms, A Creative Approach",
Udi Manber, p. 375
REFERENCIA: [www.catonmat.net/ ... ithms-part-thirteen/]
Table of Contents
=================
1 Modelos de paralelismo
2 Modelo PRAM
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
4 PROBLEMA: Calcular Max(A[1,...,N])
5 LEMA de Brent
6 DEFINICIÓN "Trabajo"
7 COROLARIO
8 EJEMPLO
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
10 PROBLEMA: Ranking en listas
1 Modelos de paralelismo
~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Instrucciones
- SIMD: Single Instrucción, Múltiple Data
- MIMD: Múltiple Instrucción, Múltiple Data
* Memoria
- compartida
- distribuida
* 2*2 combinaciones posibles:
Memoria compartida Memoria distribuida
------+--------------------+-----------------------------------------------------
SIMD PRAM redes de interconexión (weak computer units)
(hipercubos, meshes, etc...)
------+--------------------+-----------------------------------------------------
MIMD Threads procesamiento distribuido (strong computer units),
Bulk Synchronous Process, etc...
* En este curso consideramos en particular el modelo PRAM
2 Modelo PRAM
~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Mucha unidad de CPU, una sola memoria RAM
cada procesador tiene un identificador único, y puede utilizarlo
en el programa
* Ejemplo:
+ if p mod 2 = 0 then
+ A[p] += A[p-1]
+ else
+ A[p] += A[p+1]
+ b <- A[p];
+ A[p]<- b;
* Problema: el resultado no es bien definido, puede tener
*conflictos* si los procesadores están asinchronos. Las soluciones a
este problemas dan varios submodelos del modelo PRAM:
1. EREW Exclusive Read. Exclusive Write
2. CREW Concurrent Read, Exclusive Write
3. CRCW Concurrent Read, Concurent Write
En este caso hay variantes también:
- todos deben escribir lo mismo
- arbitrario resultado
- priorizado
- alguna f() de lo que se escribe
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* DEFINICIÓN:
- $T^*(n)$ es el *Tiempo secuencial* del mejor algoritmo no
paralelo en una entrada de tamaño $n$ (i.e. usando $1$
procesador).
- $T_A(n,p)$ es el *Tiempo paralelo* del algoritmo paralelo
$A$ en una entrada de tamaño $n$ usando $p$ procesadores.
- El *Speedup* del algoritmo $A$ es definido por
$S_A(n,p) = \frac{ T^*(n) }{ T_A(n,p) } \leq p$
Un algoritmo es mas efectivo cuando $S(p)=p$, que se llama
*speedup perfecto*.
- La *Eficiencia* del algoritmo $A$ es definida por
$E_A(n,p) = \frac{ S_A(n,p) }{ p }=\frac{T^*(n)}{pT_A(n,p)}$
El caso óptima es cuando $E_A(n,p)=1$, cuando el algoritmo
paralelo hace la misma cantidad de trabajo que el algoritmo
secuencial. El objetivo es de *maximizar la eficiencia*.
(Nota estas definiciones en la pisara, vamos a usarlas después.)
4 PROBLEMA: Calcular Max(A[1,...,N])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
1. Solucion Secuencial
* Algoritmo:
- $m \leftarrow 1$
- for $i\leftarrow 2$ to $n$
- if $A[i]>A[m]$ then $m\leftarrow i$
- return $A[m]$
* Se puede ver como un arbol de evaluación con una sola rama
de largo $n$ y $n$ hojas.
* Complejidad:
- tiempo $O(n)$, con $1$ procesador, entonces:
- $T^*(n)=n$.
2. Solucion Parallela con $n$ procesadores
* Algoritmo:
- $M[p] \leftarrow A[p]$
- for $l\leftarrow 0$ to $\lceil \lg p \rceil -1$
- if $p \mod 2^{l+1}=0$ y $ p+2^l
Si un algoritmo consigue un tiempo T(n,p)=C,
entonces consigue tiempo T(n,p/s)= sC \forall s>1
(bajo algunas condiciones)
6 DEFINICIÓN "Trabajo"
~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Usando el Lema de Brent, podemos exprimir el rendimiento de
los algoritmos paralelos con dos medidas:
- $T(n)$, el tiempo del algoritmo paralelo usando cualquier
cantidad de procesadores que quiere.
Nota la diferencia con
+ $T^*(n)$, el tiempo del mejor algoritmo secuencial, y
+ $T_A(n,n)$, el tiempo del algoritmo con $n$ procesadores.
- $W(n)$, la suma del total trabajo ejecutado por todo los
procesadores.
7 COROLARIO
~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Con el lema de Brent podemos obtener:
- $$T(n,p) = T(n) + \frac{ W(n) }{ p }$$
- $$E(n,p) = \frac{ T^*(n) }{ pT(n) + W(n) }$$
8 EJEMPLO
~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
* Para el calculo del máximo:
- $T(n) = \lg n$
- $W(n) = n$
* Entonces
- se puede obtener
- $T_B(n,p) = \lg n + {n \over p}$
- $$E(n,p) = \frac{ n }{ p\lg n + n }$$
* (Nota que eso es solamente una cota superior, nuestro
algoritmo da un mejor tiempo.)
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
* DEFINICIÓN: Problema "Prefijo en Paralelo"
Dado $x_1,\ldots, x_n$ y un operador asociativo \times
calcular
- $y_1 = x_1$
- $y_2 = x_1\times x_2$
- $y_2 = x_1\times x_2 \times x_3$
- ...
- $y_n = x_1\times \ldots \times x_n$
* Solucion Secuencial
Hay una solucionó obvio en tiempo O(n).
* Solucion paralela 1
* Concepto:
- Hipótesis: sabemos solucionarlo con $n/2$ elementos
- Caso de base: $n=1$ es simple.
- Inducción:
1. recursivamente calculamos en paralelo:
- todos los prefijos de $\{x_1,\ldots,x_{n/2}\}$ con
$n/2$ procesadores.
- todos los prefijos de $\{x_{n/2},\ldots,x_n\}$ con
$n/2$ procesadores.
2. en paralelo agregamos $x_{n/2}$ a los prefijos de
$\{x_{n/2},\ldots,x_n\}$
* ParallelPrefix1(i,j)
- if $i_p=j_p$
- return x_{i_p}
- $m_p \leftarrow \lfloor \frac{i_p + j_p}{2} \rfloor$;
- if $p\leq m$ then
- algo( i_p, m_p )
- else
- algo(m+1, j_p)
- y_p \leftarrow y_m . y_p
* Otra forma del algoritmo (de p. 384 de "Introduction to
Algorithms, A Creative Approach", Udi Manber):
+ ParallelPrefix1(left,right)
- if (right-left) = 1
- x[right] <- x[left] . x[right]
- else
- middle <- (left+right-1)/2
- do in paralel
- ParallelPrefix1(left,middle) {assigned to {P_1 to P_{n/2}}}
- ParallelPrefix1(middle+1,right) {assigned to {P_{n/2+1} to P_n}}
- for i <- middle+1 to right do in paralel
- x[i] <- x[middle] . x[i]
* Notas:
- este solucion *no* es EREW (Exclusive Read&Write), porque
los procesadores pueden leer $y_m$ al mismo tiempo.
- este solucionó es CREW (Concurrent Read, Exclusive Write).
- Complejidad:
- $T_{A_1}(n,n) = 1+ T(n/2,n/2) = \lg n$
(El mejor tiempo en paralelo con cualquier cantidad de
procesadores.)
- $W_{A_1}(n) = n + 2 W_{A_1}(n/2) - n\lg n$
- $T_{A_1}(n,p) = T(n) + W_{A_1}(n)/p = \lg n + (n\lg n)/p$
- Calculamos $p^*$, la cantidad óptima de procesadores
para minimizar el tiempo:
- $T(n) = W_{A_1}(n) /p^*$
- $p^* = \frac{ W(n) }{ T(n) } = n$
- Calculamos la eficiencia
- $E_{A_1}(n,p^*)
= \frac{ T^*(n) }{ p^* T(n)+W(n) }
= \frac{ n }{ n\lg n }
= {1 \over \lg n}$
- es poco eficiente =(
- PodrÃ-amos tener un algoritmo con
- la eficiencia del algoritmo secuencial
- el tiempo del algoritmo paralelo?
* Solucion paralela 2: mismo tiempo, mejor eficiencia
- Idea:
El concepto es de dividir de manera diferente: par y impar
(en vez de largo o pequeño).
- Concepto:
1. Calcular en paralelo $x_{2i-1}.x_{2i}$ en $x_{2i}$
para $\forall i, 1\leq i \leq n/2$.
2. Recursivamente, calcular todos los prefijos de
$E=\{ x_2,x_4,\ldots, x_{2i},\ldots, x_n \}$
3. Calcular en paralelo los prefijos en posiciones impares,
multiplicando los prefijos de $E$ por una sola valor.
- algo2(i,j)
- for $d\leftarrow 1$ to $(\lg n)-1$
- if $p=0 \mod 2^{d+1}$
- if $p+2^d0$
- $x_{p-2^d} \leftarrow x_{p-2^d}.x_p$
- visualización
0.
1. [0,1]
2.
3. [2,3] [0,3]
4.
5. [4,5]
6.
7. [6,7] [4,7] [0,7]
8.
9. [8,9]
10.
11. [10,11] [8,11]
12.
13. [12,13]
14.
15. [14,15] [12,15] [8,15] [0,15]
- Notas:
- Este algoritmo es EREW
- Análisis
- $T_2(n) = 2\lg n$
- $W(n) = n + W(n.2) = n$
- $T_2(n,p) = T(n) + W(n)/p = 2\lg n + \frac{n}{p}$
- Calculamos la cantidad óptima de procesadores para obtener
el tiempo óptima:
- $T_2(n) = W(n) / p^*$ entonces
- $p^* = {W(n) \over T(n)} = {n\over\lg n}$
- $E_2(n,p^*) = { T^*(n) \over p^* T(n)+ W(n)} = n/n \in O(1)$
10 PROBLEMA: Ranking en listas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
1. DEFINICIÓN
- dado una lista, calcula el rango para cada elemento.
- En el caso de una lista tradicional, no se puede hacer
mucho mejor que lineal.
- Consideramos una lista en un arreglo $A$,
- donde cada elemento $A[i]$ tiene un puntero al siguiente
elemento, $N[i]$, y
- calculamos su rango $R[i]$ en un arreglo $R$.
2. DoublingRank()
- $R[p] \leftarrow 0$
- if $N[p] = null$
- R[p] \leftarrow 1
- for $d\leftarrow 1$ to $\lceil\lg n\rceil$
- if $N[p]\neq NULL$
- if $R[N[p]]>0$
- $R[p] \leftarrow R[N[p]]+2^d$
- $N[p] \leftarrow N[N[p]]$
3. Análisis
- T(n) = \lg n
- W(n) = n + W(n/2) = O(n)
- T(n,p) = T(n) + W(n)/p = \lg n + n/p
- p^*
T(n) = W(n) / p^*
p n/\lg n
- E(n,p^*) = \frac{T^*(n)}{ p^* T(n) + W(n) }
= \frac{ n }{ n/\lg n \lg n +n}
= \Theta(1)
4. El algoritmo es EREW o CREW?
- es EREW si los procesadores están sincronizados, com en RAM
aquÃ-.
Nociones de aproximabilidad [2010-10-26 Tue]--[2010-11-04 Thu]
4
Jérémy Barbay 9 Nov 201009/11/10 a las 11:32 hrs.2010-11-09 11:32:09
Nociones de aproximabilidad (2 semanas = 4 charlas)
===================================================
Author: Jérémy Barbay
[2010-10-26 Tue]--[2010-11-04 Thu]
- problemas que son o no aproximables
Table of Contents
=================
1 Intro: Aproximación de problemas de optimización NP-dificiles
2 *$p(n)$-aproximación*: Definición
3 Ejemplo: Bin Packing (un problema que es 2-aproximable)
4 Ejemplo: Recubrimiento de Vertices (Vertex Cover)
5 Ejemplo: Vendedor viajero (Traveling Salesman)
6 Ejemplo: Vertex Cover con pesos
7 PTAS y FPTAS: Definiciones
8 Ejemplo: Problema de la mochila
1 DONE Intro: Aproximación de problemas de optimización NP-dificiles
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- Que problemas NP dificiles conocen?
- colorisacion de grafos
- ciclo hamiltonian
- Recubrimiento de Vertices (Vertex Cover)
- Bin Packing
- Problema de la Muchila
- Vendedor viajero (Traveling Salesman)
- Que hacer cuando se necessita una solucion en tiempo
polinomial?
- Consideramos los problemas NP completos de decisión,
generalmente de optimización. Si se necesita una solucionó
en tiempo polinomial, se puede considerar una aproximación.
2 DONE *$p(n)$-aproximación*: Definición
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
* Dado un problema de minimización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_A(x) }{ C_{OPT}(x) } \leq p(n)$
* Dado un problema de maximización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_{OPT}(x) }{ C_A(x) } \leq p(n)$
- Notas:
1) AquÃ- consideramos la cualidad de la solución, NO la
complejidad del algoritmo. Usualmente el problema es
NP-difÃ-cil, y el algoritmo de aproximación es de
complejidad polinomial.
2) Las razones estas \geq 1 (elijamos las definiciones para
eso)
3) A veces consideramos también C_A(x)-C_{OPT}(x)
(minimización) y C_{OPT}(x)-C_A(x): eso se llama un
"esquema de aproximación polinomial" y vamos a verlo mas
tarde.
3 DONE Ejemplo: Bin Packing (un problema que es 2-aproximable)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- DEFINICIÓN
Dado $n$ valores $x_1, \ldots, x_n$, $0\leq x_i\leq 1/2$,
cual es la menor cantidad de cajas de tamaño 1 necesarias
para empaquetarlas?
- Algoritmo "Greedy"
- Considerando los $x_i$ en orden,
- llenar la caja actual todo lo posible,
- pasar ala siguiente caja.
- Análisis
- Este algoritmo tiene complejidad lineal O(n).
- Greedy da una 2-aproximación.
- (se puede mostrar facilamente en las instancias donde el
algoritmo óptima llene completamente todas las cajas.)
- Además, hay mejores aproximaciones,
1. Best-fit tiene performance ratio de 1.7 en el peor caso
2. [Best-Fit Bin-Packing with Random Order (1997), Kenyon]
Best-fit is the best known algorithm for on-line
binpacking, in the sense that no algorithm is known to
behave better both in the worst case (when Best-fit has
performance ratio 1.7) and in the average uniform case,
with items drawn uniformly in the interval [0; 1] (then
Best-fit has expected wasted space O(n 1=2 (log n) 3=4
)). In practical applications, Best-fit appears to perform
within a few percent of optimal. In this paper, in the
spirit of previous work in computational geometry, we study
the expected performance ratio, taking the worst-case
multiset of items L, and assuming that the elements of L
are inserted in random order, with all permutations equally
likely. We show a lower bound of 1:08 : : : and an upper
bound of 1:5 on the random order performance ratio of
Best-fit. The upper bound contrasts with the result that in
the worst case, any (deterministic or randomized) on-line
bin-packing algorithm has performance ratio at least
1:54 : : :. 1
3. Un otro paper donde particionan los $x_i$ en tres classes,
placeando los x_i mas grande primero, buscando el
placamiento optimal de los $x_i$ promedio, y usando un
algoritmo greedy para los $x_i$ pequenos. [Karpinski?]
4. la distribucion de los tamaños de las cajas hacen la
instancia dificil o facil.
4 DONE Ejemplo: Recubrimiento de Vertices (Vertex Cover)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado un grafo $G=(V,E)$, cual es el menor $V'\subseteq V$ tal
que $V'$ sea un vertex cover de $G$.
(o sea $V'$ mas pequeño tq $\forall e=(u,v)\in E, u\in V'o v\in V')
- Algoritmo de aproximación:
- V'<- \emptyset
- while E\neq \emptyset
- sea (u,v) \in E
- V'\leftarrow V'\cup {u,v}
- E <- E \ {(x,y), x=u o x=v o y=u o y=v }
- return V
- Discusión: es una 2-aproximación o no?
- LEMA: El algoritmo es una 2-aproximación.
- PRUEBA:
+ Cada par $u,v$ que la aproximación elige esta conectada,
entonces u o v estas en cualquier solucionó óptima de
Vertex Cover.
+ Como se eliminan las aristas incidentes en u y v, los
siguientes pares que se eligen no tienen intersección con
el actual, entonces cada 2 nodos que el algoritmo elige,
uno pertenece a la solución óptima.
+ quod erat demonstrandum, (QED).
5 DONE Ejemplo: Vendedor viajero (Traveling Salesman)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado $G=(V,E)$ dirigido y $C:E\rightarrow R^+$ una función de
costos, encontrar un recorrido que toque cada ciudad una vez, y
minimice la suma de los costos de las aristas recorridas.
- LEMA: Si $c$ satisface la desigualdad triangular
$\forall x,y,z c(x,y)+x(y,z) \geq c(x,z)$,
hay una 2-aproximación.
- PROOF:
- Algoritmo de Aproximación (con desigualdad triangular)
- construir un arbol cobertor mÃ-nimo (MST)
- se puede hacer en tiempo polinomial, con programación lineal.
- C_{MST} \leq C_{OPT}
- producimos un recorrido en profundidad DFS del MST:
- C_{DFS} = 2C_{MST} \leq 2 C_{OPT}
- (factor dos porque el camino de vuelta puede ser al
máximo de tamaño igual al tamaño del camino de ida)
- eliminamos los nodos repetidos del camino, que no crece
el costo
- $C_A\leq 2 C_{OPT}$
- quod erat demonstradndum, QED.
- LEMA: Si $c$ no satisface la desigualdad triangular, el
problema de vendedor viajero no es aproximables en tiempo
polinomial (a menos que P=NP$).
- PROOF:
- Supongamos que existe una p(n)-aproximación de tiempo
polinomial.
- Dado un grafo G=(V,E)
- Construimos un grafo G'=(V,E') tal que
- E'=V^2 (grafo completo), y
- c(u,v) = 1 si (u,v)\in E
n p(n) sino
- Si no hay un Ciclo Hamiltonian en E,
- todas las soluciones usan al menos una arista que no es
en E
- entonces todas las soluciones tienen costo mas que
$np(n)$
- Si hay un Ciclo Hamiltonian en E
- tenemos una aproximación de una solucionó de costo menos
que $(n-1)p(n)$ QED
6 DONE Ejemplo: Vertex Cover con pesos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-02 Tue 12:00-13:30>
- DEFINICIÓN
Dado G=(V,E) y c:V->R^+, se quiere un V^*\subseteq V que cubra
E y que minimice \sum_{v\in V^*} c(v).
- Este problema es NP Completo.
- LEMA: Vertex Cover con pesos es 2-aproximable
- PROOF:
1. Sea variables x(v)\in {0,1}, \forall v\in V
- el costo de V^* sera \sum x(v) c(v)
- objetivo: \min \sum_{v\in V} x(v) c(v)
donde 0\leq x(v) \leq 1 \forall v\in V
- x(u)+x(v)\geq 1 \forall u,v \in E
2. x(v) \in Z seré programación entera, que es NP Completa
x(v) \in R seré programación lineal, que es polinomial
el valor \sum x(v) c(v) que produce el programo lineal
es inferior a la mejor solución al problema de VC.
3. Algoritmo
- resolver el problema de programación lineal
- nos da x(v_1),\ldots x(v_n)
- V^* <Â \emptyset
- for v\in V
- si x(v)\geq 1/2
- V^* <- V^* \cup {v}
- return V^*
4. Propiedades
- V^* es un vertex cover:
- si \forall(u,v)\in E, x(u)+x(v)\geq 1
- entonces, x(u)\geq 1/2 o x(v)/geq 1/2
- entonces, u\in V^* o v\in V^*
- V^* es una 2-aproximación:
- c(V^*) = \sum_v y(v) c(v)
donde y(v) = 1 si x(v) \geq 1/2
0 sino
- entonces y(v) \leq 2 x(v)
- \sum y(v) c(v) \leq \sum 2 x(v) c(v) \leq 2 OPT
- C(V^*) \leq 2 OPT
5. QED
7 DONE PTAS y FPTAS: Definiciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Esquema de aproximacion poliniomial *PTAS*
Un *esquema de aproximación polinomial* para un problema es un
algoritmo $A$ que recibe como input una instancia del problema
y un para-metro $\varepsilon>0$ y produce una $(1+\varepsilon)$
aproximación. Para todo $\varepsilon$ fijo, el tiempo de $A$
debe ser polinomial en $n$, el tamaño de la instancia.
* Ejemplos de complejidades: Cuales tienen sentidos?
- [ ] $O(n^{2/3})$
- [ ] $O(\frac{1}{\varepsilon^2} n^2)$
- [ ] $O(2^\varepsilon n)$
- [ ] $O(2^{1/\varepsilon} n)$
* Esquema de aproximación completamente polinomial *FPTAS*
Un *esquema de aproximación completamente polinomial* es un
PTAS donde el tiempo del algoritmo es polinomial en $n$ *y en
$1/\varepsilon$*.
8 DONE Ejemplo: Problema de la mochila
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Definición:
Dado
- los elementos $S={1,\ldots,n}$ con pesos $X_1,\ldots,X_N\geq 0$,
- un tamaño máximo $t$
Quiero encontrar $S'\subset S$
- tal que $\sum(S')\leq t y$
- que maximice $\sum(S')=\sum_{i\in S'} x_i$
* Solucion exacta, exponencial
- Dado $L=\{y_1,,\ldots y_m\}$, definimos $L+x=\{y_1+x,\ldots,y_m+x\}$
- Algoritmo:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow$ merge $(L,L+x_i)$
- prune$(L,t)$ (remudando las valores $> t$)
- return $\max(L)$
* Solucion aproximada (inspirada del algoritmo exacto)
- Definimos la operación de *recorte* de una lista L con
parámetro $\delta$:
- Dado $y,z \in L$, $z$ *represente* a $y$ si
- $y /(1+\delta) \leq z \leq y$
- vamos a eliminar de $L$ todos los $y$ que sean representados
por alguno $z$ no eliminado de $L$.
- Recortar$(L,\delta)$
- Sea $L=\{y_1,\ldots,y_m\}$
- $L'\leftarrow \{y_1\}$
- $\mathit{Last} \leftarrow y_1$
- for $i\leftarrow 2$ to $m$
- si $y_i > \mathit{Last}(1+\delta)$
- $L \leftarrow L'.\{y_i\}$
- $\mathit{Last}\leftarrow y_i$
- return $L'$
- Algoritmo de Aproximación:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow \mathit{merge} (L,L+x_i)$
- $\mathit{prune}(L,t)$ (remudando las valores $> t$)
- *$L \leftarrow \mathit{recortar}(L,\epsilon/2n)$*
- return max(L)
- El resultado es una $(1+\epsilon)$-aproximación:
1. retorne una solución valida, tal que
- $\sum(S')\leq t$ para algún $S'\subset S$
2. en el paso $i$, para todo $z\in L_{OPT}$,
existe un $y\in L_A$ tal que $z$ representa a $y$.
- Luego de los $n$ pasos, el $z^*$ óptimo en $L_{OPT}$
tiene un representante $y^*\in L_A$ tal que
$z^*/(1+\epsilon/2n)^n \leq y^* \leq z^*
3. Para mostrar que el algoritmo es una $(1+\epsilon)$
aproximación,
- hay que mostrar que
- $z^*/(1+\epsilon) \leq y^*$
- entonces, debemos mostrar que
- $(1+\epsilon/2n)^n \leq 1+\epsilon$
- Eso se muestra con puro calculo:
- $(1+\epsilon/2n)^n \leq? 1+\epsilon$
- $e^{n\lg(1+\epsilon/2n) }$
- $\leq e^{ n \epsilon /2n }$
- $= e^{ \epsilon/2 }$
- $\leq? e^{\ln(1+\epsilon)}$
- eso es equivalente a elegir \epsilon tal
que $\epsilon/2 \leq \ln(1+\epsilon)$
- i.e. cualquier tal que $0<\epsilon\leq 1$
4. El algoritmo es polinomial (en todos los parámetros)
- despues de recortar dedos $y_i,y_{i+1}\in L$
se cumple $y_{i+1}>y_i(1+\delta)$
y el ultimo elemento es $\leq t$
- entonces, la lista contiene $0,1$
y luego a lo mas $\lfloor \log_{(1+\delta)} t \rfloor$
- entonces el largo de L en cada iteracion no supera
$2+ \frac{ \log t }{ \log( 1+\varepsilon/2n) }$
- Nota que $\ln(1+x) $
- $= - \ln (1/(1+x))$
- $= - \ln ( (1+x-x)/(1+x) )$
- $= - \ln ( 1 - x/(1+x) )$
- $= - \ln (1+y) \geq -y$
- $\geq - (-x/(1+x)) = x/(1+x)$
- Entonces
- $2+ \frac{ \ln t }{ \ln 1 + \epsilon/2n }$
- $\leq 2 + ((1+\epsilon/2n) 2n \ln t )/\epsilon$
- $= ( 2n\ln t )/ \epsilon + \ln t + 2$
- $= O(n \lg t /\epsilon)$
- Entonces cada iteracion toma $O(n \lg t /\epsilon)$ operaciones
- Las $n$ iteraciones en total toman
- $O(n^2 \lg t /\epsilon)$ operaciones
===================================================
Author: Jérémy Barbay
[2010-10-26 Tue]--[2010-11-04 Thu]
- problemas que son o no aproximables
Table of Contents
=================
1 Intro: Aproximación de problemas de optimización NP-dificiles
2 *$p(n)$-aproximación*: Definición
3 Ejemplo: Bin Packing (un problema que es 2-aproximable)
4 Ejemplo: Recubrimiento de Vertices (Vertex Cover)
5 Ejemplo: Vendedor viajero (Traveling Salesman)
6 Ejemplo: Vertex Cover con pesos
7 PTAS y FPTAS: Definiciones
8 Ejemplo: Problema de la mochila
1 DONE Intro: Aproximación de problemas de optimización NP-dificiles
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- Que problemas NP dificiles conocen?
- colorisacion de grafos
- ciclo hamiltonian
- Recubrimiento de Vertices (Vertex Cover)
- Bin Packing
- Problema de la Muchila
- Vendedor viajero (Traveling Salesman)
- Que hacer cuando se necessita una solucion en tiempo
polinomial?
- Consideramos los problemas NP completos de decisión,
generalmente de optimización. Si se necesita una solucionó
en tiempo polinomial, se puede considerar una aproximación.
2 DONE *$p(n)$-aproximación*: Definición
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
* Dado un problema de minimización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_A(x) }{ C_{OPT}(x) } \leq p(n)$
* Dado un problema de maximización, un algoritmo $A$ es un
*$p(n)$-aproximación* si
$\forall n \max \frac{ C_{OPT}(x) }{ C_A(x) } \leq p(n)$
- Notas:
1) AquÃ- consideramos la cualidad de la solución, NO la
complejidad del algoritmo. Usualmente el problema es
NP-difÃ-cil, y el algoritmo de aproximación es de
complejidad polinomial.
2) Las razones estas \geq 1 (elijamos las definiciones para
eso)
3) A veces consideramos también C_A(x)-C_{OPT}(x)
(minimización) y C_{OPT}(x)-C_A(x): eso se llama un
"esquema de aproximación polinomial" y vamos a verlo mas
tarde.
3 DONE Ejemplo: Bin Packing (un problema que es 2-aproximable)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-26 Tue 12:00-13:30>
- DEFINICIÓN
Dado $n$ valores $x_1, \ldots, x_n$, $0\leq x_i\leq 1/2$,
cual es la menor cantidad de cajas de tamaño 1 necesarias
para empaquetarlas?
- Algoritmo "Greedy"
- Considerando los $x_i$ en orden,
- llenar la caja actual todo lo posible,
- pasar ala siguiente caja.
- Análisis
- Este algoritmo tiene complejidad lineal O(n).
- Greedy da una 2-aproximación.
- (se puede mostrar facilamente en las instancias donde el
algoritmo óptima llene completamente todas las cajas.)
- Además, hay mejores aproximaciones,
1. Best-fit tiene performance ratio de 1.7 en el peor caso
2. [Best-Fit Bin-Packing with Random Order (1997), Kenyon]
Best-fit is the best known algorithm for on-line
binpacking, in the sense that no algorithm is known to
behave better both in the worst case (when Best-fit has
performance ratio 1.7) and in the average uniform case,
with items drawn uniformly in the interval [0; 1] (then
Best-fit has expected wasted space O(n 1=2 (log n) 3=4
)). In practical applications, Best-fit appears to perform
within a few percent of optimal. In this paper, in the
spirit of previous work in computational geometry, we study
the expected performance ratio, taking the worst-case
multiset of items L, and assuming that the elements of L
are inserted in random order, with all permutations equally
likely. We show a lower bound of 1:08 : : : and an upper
bound of 1:5 on the random order performance ratio of
Best-fit. The upper bound contrasts with the result that in
the worst case, any (deterministic or randomized) on-line
bin-packing algorithm has performance ratio at least
1:54 : : :. 1
3. Un otro paper donde particionan los $x_i$ en tres classes,
placeando los x_i mas grande primero, buscando el
placamiento optimal de los $x_i$ promedio, y usando un
algoritmo greedy para los $x_i$ pequenos. [Karpinski?]
4. la distribucion de los tamaños de las cajas hacen la
instancia dificil o facil.
4 DONE Ejemplo: Recubrimiento de Vertices (Vertex Cover)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado un grafo $G=(V,E)$, cual es el menor $V'\subseteq V$ tal
que $V'$ sea un vertex cover de $G$.
(o sea $V'$ mas pequeño tq $\forall e=(u,v)\in E, u\in V'o v\in V')
- Algoritmo de aproximación:
- V'<- \emptyset
- while E\neq \emptyset
- sea (u,v) \in E
- V'\leftarrow V'\cup {u,v}
- E <- E \ {(x,y), x=u o x=v o y=u o y=v }
- return V
- Discusión: es una 2-aproximación o no?
- LEMA: El algoritmo es una 2-aproximación.
- PRUEBA:
+ Cada par $u,v$ que la aproximación elige esta conectada,
entonces u o v estas en cualquier solucionó óptima de
Vertex Cover.
+ Como se eliminan las aristas incidentes en u y v, los
siguientes pares que se eligen no tienen intersección con
el actual, entonces cada 2 nodos que el algoritmo elige,
uno pertenece a la solución óptima.
+ quod erat demonstrandum, (QED).
5 DONE Ejemplo: Vendedor viajero (Traveling Salesman)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-28 Thu 12:00-13:30>
- DEFINICIÓN:
Dado $G=(V,E)$ dirigido y $C:E\rightarrow R^+$ una función de
costos, encontrar un recorrido que toque cada ciudad una vez, y
minimice la suma de los costos de las aristas recorridas.
- LEMA: Si $c$ satisface la desigualdad triangular
$\forall x,y,z c(x,y)+x(y,z) \geq c(x,z)$,
hay una 2-aproximación.
- PROOF:
- Algoritmo de Aproximación (con desigualdad triangular)
- construir un arbol cobertor mÃ-nimo (MST)
- se puede hacer en tiempo polinomial, con programación lineal.
- C_{MST} \leq C_{OPT}
- producimos un recorrido en profundidad DFS del MST:
- C_{DFS} = 2C_{MST} \leq 2 C_{OPT}
- (factor dos porque el camino de vuelta puede ser al
máximo de tamaño igual al tamaño del camino de ida)
- eliminamos los nodos repetidos del camino, que no crece
el costo
- $C_A\leq 2 C_{OPT}$
- quod erat demonstradndum, QED.
- LEMA: Si $c$ no satisface la desigualdad triangular, el
problema de vendedor viajero no es aproximables en tiempo
polinomial (a menos que P=NP$).
- PROOF:
- Supongamos que existe una p(n)-aproximación de tiempo
polinomial.
- Dado un grafo G=(V,E)
- Construimos un grafo G'=(V,E') tal que
- E'=V^2 (grafo completo), y
- c(u,v) = 1 si (u,v)\in E
n p(n) sino
- Si no hay un Ciclo Hamiltonian en E,
- todas las soluciones usan al menos una arista que no es
en E
- entonces todas las soluciones tienen costo mas que
$np(n)$
- Si hay un Ciclo Hamiltonian en E
- tenemos una aproximación de una solucionó de costo menos
que $(n-1)p(n)$ QED
6 DONE Ejemplo: Vertex Cover con pesos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-02 Tue 12:00-13:30>
- DEFINICIÓN
Dado G=(V,E) y c:V->R^+, se quiere un V^*\subseteq V que cubra
E y que minimice \sum_{v\in V^*} c(v).
- Este problema es NP Completo.
- LEMA: Vertex Cover con pesos es 2-aproximable
- PROOF:
1. Sea variables x(v)\in {0,1}, \forall v\in V
- el costo de V^* sera \sum x(v) c(v)
- objetivo: \min \sum_{v\in V} x(v) c(v)
donde 0\leq x(v) \leq 1 \forall v\in V
- x(u)+x(v)\geq 1 \forall u,v \in E
2. x(v) \in Z seré programación entera, que es NP Completa
x(v) \in R seré programación lineal, que es polinomial
el valor \sum x(v) c(v) que produce el programo lineal
es inferior a la mejor solución al problema de VC.
3. Algoritmo
- resolver el problema de programación lineal
- nos da x(v_1),\ldots x(v_n)
- V^* <Â \emptyset
- for v\in V
- si x(v)\geq 1/2
- V^* <- V^* \cup {v}
- return V^*
4. Propiedades
- V^* es un vertex cover:
- si \forall(u,v)\in E, x(u)+x(v)\geq 1
- entonces, x(u)\geq 1/2 o x(v)/geq 1/2
- entonces, u\in V^* o v\in V^*
- V^* es una 2-aproximación:
- c(V^*) = \sum_v y(v) c(v)
donde y(v) = 1 si x(v) \geq 1/2
0 sino
- entonces y(v) \leq 2 x(v)
- \sum y(v) c(v) \leq \sum 2 x(v) c(v) \leq 2 OPT
- C(V^*) \leq 2 OPT
5. QED
7 DONE PTAS y FPTAS: Definiciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Esquema de aproximacion poliniomial *PTAS*
Un *esquema de aproximación polinomial* para un problema es un
algoritmo $A$ que recibe como input una instancia del problema
y un para-metro $\varepsilon>0$ y produce una $(1+\varepsilon)$
aproximación. Para todo $\varepsilon$ fijo, el tiempo de $A$
debe ser polinomial en $n$, el tamaño de la instancia.
* Ejemplos de complejidades: Cuales tienen sentidos?
- [ ] $O(n^{2/3})$
- [ ] $O(\frac{1}{\varepsilon^2} n^2)$
- [ ] $O(2^\varepsilon n)$
- [ ] $O(2^{1/\varepsilon} n)$
* Esquema de aproximación completamente polinomial *FPTAS*
Un *esquema de aproximación completamente polinomial* es un
PTAS donde el tiempo del algoritmo es polinomial en $n$ *y en
$1/\varepsilon$*.
8 DONE Ejemplo: Problema de la mochila
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-04 Thu 12:00-13:30>
* Definición:
Dado
- los elementos $S={1,\ldots,n}$ con pesos $X_1,\ldots,X_N\geq 0$,
- un tamaño máximo $t$
Quiero encontrar $S'\subset S$
- tal que $\sum(S')\leq t y$
- que maximice $\sum(S')=\sum_{i\in S'} x_i$
* Solucion exacta, exponencial
- Dado $L=\{y_1,,\ldots y_m\}$, definimos $L+x=\{y_1+x,\ldots,y_m+x\}$
- Algoritmo:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow$ merge $(L,L+x_i)$
- prune$(L,t)$ (remudando las valores $> t$)
- return $\max(L)$
* Solucion aproximada (inspirada del algoritmo exacto)
- Definimos la operación de *recorte* de una lista L con
parámetro $\delta$:
- Dado $y,z \in L$, $z$ *represente* a $y$ si
- $y /(1+\delta) \leq z \leq y$
- vamos a eliminar de $L$ todos los $y$ que sean representados
por alguno $z$ no eliminado de $L$.
- Recortar$(L,\delta)$
- Sea $L=\{y_1,\ldots,y_m\}$
- $L'\leftarrow \{y_1\}$
- $\mathit{Last} \leftarrow y_1$
- for $i\leftarrow 2$ to $m$
- si $y_i > \mathit{Last}(1+\delta)$
- $L \leftarrow L'.\{y_i\}$
- $\mathit{Last}\leftarrow y_i$
- return $L'$
- Algoritmo de Aproximación:
- $L \leftarrow \{\emptyset\}$
- for $i\leftarrow 1$ to $n$
- $L \leftarrow \mathit{merge} (L,L+x_i)$
- $\mathit{prune}(L,t)$ (remudando las valores $> t$)
- *$L \leftarrow \mathit{recortar}(L,\epsilon/2n)$*
- return max(L)
- El resultado es una $(1+\epsilon)$-aproximación:
1. retorne una solución valida, tal que
- $\sum(S')\leq t$ para algún $S'\subset S$
2. en el paso $i$, para todo $z\in L_{OPT}$,
existe un $y\in L_A$ tal que $z$ representa a $y$.
- Luego de los $n$ pasos, el $z^*$ óptimo en $L_{OPT}$
tiene un representante $y^*\in L_A$ tal que
$z^*/(1+\epsilon/2n)^n \leq y^* \leq z^*
3. Para mostrar que el algoritmo es una $(1+\epsilon)$
aproximación,
- hay que mostrar que
- $z^*/(1+\epsilon) \leq y^*$
- entonces, debemos mostrar que
- $(1+\epsilon/2n)^n \leq 1+\epsilon$
- Eso se muestra con puro calculo:
- $(1+\epsilon/2n)^n \leq? 1+\epsilon$
- $e^{n\lg(1+\epsilon/2n) }$
- $\leq e^{ n \epsilon /2n }$
- $= e^{ \epsilon/2 }$
- $\leq? e^{\ln(1+\epsilon)}$
- eso es equivalente a elegir \epsilon tal
que $\epsilon/2 \leq \ln(1+\epsilon)$
- i.e. cualquier tal que $0<\epsilon\leq 1$
4. El algoritmo es polinomial (en todos los parámetros)
- despues de recortar dedos $y_i,y_{i+1}\in L$
se cumple $y_{i+1}>y_i(1+\delta)$
y el ultimo elemento es $\leq t$
- entonces, la lista contiene $0,1$
y luego a lo mas $\lfloor \log_{(1+\delta)} t \rfloor$
- entonces el largo de L en cada iteracion no supera
$2+ \frac{ \log t }{ \log( 1+\varepsilon/2n) }$
- Nota que $\ln(1+x) $
- $= - \ln (1/(1+x))$
- $= - \ln ( (1+x-x)/(1+x) )$
- $= - \ln ( 1 - x/(1+x) )$
- $= - \ln (1+y) \geq -y$
- $\geq - (-x/(1+x)) = x/(1+x)$
- Entonces
- $2+ \frac{ \ln t }{ \ln 1 + \epsilon/2n }$
- $\leq 2 + ((1+\epsilon/2n) 2n \ln t )/\epsilon$
- $= ( 2n\ln t )/ \epsilon + \ln t + 2$
- $= O(n \lg t /\epsilon)$
- Entonces cada iteracion toma $O(n \lg t /\epsilon)$ operaciones
- Las $n$ iteraciones en total toman
- $O(n^2 \lg t /\epsilon)$ operaciones
Aleatorizacion [2010-10-14 Thu]--[2010-10-19 Tue]
Jérémy Barbay 9 Nov 201009/11/10 a las 11:30 hrs.2010-11-09 11:30:09
Aleatorizacion (1 semana = 2 charlas)
=====================================
Author: Jérémy Barbay
Date: 2010-11-09 11:28:36 CLST
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
Table of Contents
=================
1 Definiciones
2 El poder de un algoritmo aleatorizado
3 Aleatorizacion de la entrada
3.1 SkipLists
3.1.1 Paginamiento al Azar
3.1.2 Arboles Binarios de Busqueda aleatorizados
3.1.3 Complejidad Probabilistica: cotas inferiores
4 *Relacion con Problemas NP-Dificiles*
5 Complejidad de un algoritmo aleatorizado
6 Tecnicas de cotas inferiores de la complejidad aleatorizada
7 Algoritmos tipo Monte Carlo y Las Vegas
8 Primalidad
9 Clases de complejidad aleatorizada
9.1 RP
9.2 ZPP
9.3 PP
9.4 BPP
1 DONE Definiciones
~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- *Algoritmos deterministico*
- algoritmo que usa solamente instrucciones
*deterministicas*.
- algoritmo de cual la ejecucion (y, entonces, el
rendimiento) depende solamente del input.
- *Algoritmos aleatorizados*
- algoritmo que usa una instruccion *aleatorizada*
(potentialemente muchas veces)
- una distribucion de probabilidades sobre una familia de
algoritmos deterministicos.
- *Análisis probabilistica*
- analysis del rendimiento de un algoritmo, en promedio
sobre
- el aleatorio de la entrada, o
- el aleatorio del algoritmo, o
- los dos.
- veamos que son nociones equivalentes.
2 DONE El poder de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- Nota: Trae los juguetes/cajas de colores, con un tesoro a esconder a dentro.
Ejemplos de algoritmos o estructuras de datos aleatorizados
1. *hidden coin*
- Decidir si un elemento pertenece en un lista
desordenada de tamaño k, o si hay una moneda a dentro
de una de las $k$ caja.
- cual son las complejidades determinisitica y
aleatorizada del problema de encontrar *una* moneda,
con $c$ la cantidad de monedas,
- si $c=1$?
- si $c=n-1$?
- si $c=n/2$?
- Respuestas:
- Si una sola instancia de la valor buscada
- k en el peor caso deterministico
- k/2 en (promedio y en) el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
- Si r instancias de la valor buscada
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
3. Decidir si un elemento pertenece en una lista ordenadas
de tamaño n
* \Theta(\lg n) comparaciones en ambos casos,
deterministico y probabilÃ-stico.
4. *problema de union*
* Decidir si un elemento pertenece en una de las k listas
ordenadas de tamaño n
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n)/2 comparaciones
* Si r
* Independencia de la distribucion de la entrada
- Si el input sigue una distribucion non-conocida, el input
perturbado tiene una distribucion conocida (para una
perturbacion bien elegida)
- Ejemplo:
- flip $b$ de una bit con probabilidad $p$ que puede ser
distinta de $1/2$.
- suma-lo modulo 1 con un otro bit aleatorizado, con
probabilidad $1/2$ de ser uno.
- la suma es igual a uno con probabilidad $1/2$.
* Estructuras de datos aleatorizadas
- *funciones de hash*:
- estructura de datos aleatorizada,
- donde (a,b) son elegidos al azar.
- *skiplists*
- estructura de datos aleatorizada,
- que simula en promedio un arbol binario
3.1 DONE SkipLists
===================
1) Estructuras de datos para diccionarios
- [X] Arreglo ordenado
- [ ] "Move To Front" list (did they see it already?)
- [X] Arboles binarios
- [X] Arboles binarios aleatorizados
- [X] Arboles 2-3 ( they saw it already?)
- [X] Red-Black Trees ( they saw it already?)
- [X] AVL
- [X] Skip List
- [ ] Splay trees
2) Skip Lists
1. Motivación
- un arbol binario con entradas aleatorizadas tienen una
altura O(lg n), pero eso supone un orden de input
aleatorizados.
- El objetivo de las "skip lists" es de poner el aleatorio
a dentro de la estructura.
- también, es el equivalente de una búsqueda binaria en
listas via un resumen de resumen de resumen...
2. Definición
- una skip-list de altura $h$ para un diccionario $D$ de
$n$ elementos es una familia de lists $S_0,\ldots,S_h$ y
un puntero al primero elemento de $S_h$, tal que
- $S_0$ contiene $D$;
- cada $S_i$ contiene un subconjunto aleatorio de $S_{i-1}$
(en promedio la mitad)
- se puede navegar de la izquierda a la derecha, y de la
cima hasta abajo.
- se puede ver como $n$ torres de altura aleatorizadas,
conectadas horizontalmente con punteros de la
izquierda a la derecha.
- la información del diccionario están solamente en S_0 (no
se duplica)
3. Ejemplo
4 X - - - - - - -> X
3 X - -> X - - - -> X
2 X - -> X X -> X -> X
1 X X -> X X -> X -> X
0 X X X X X X X X X
---+---------+----+----+----+----+----+----+----+--------
-\infty 10 20 30 40 50 60 70 \infty
4. Operaciones
* Search(x):
- Start a the first element of $S_h$
- while not in $S_0$
- go down one level
- go right till finding a key larger than x
* Insert(x)
- Search(x)
- create a tower of random height (p=1/2 to increase
height, typically)
- insert it in all the lists it cuts.
* Delete(x)
- Search(x)
- remove tower from all lists.
5. Ejemplos
* Insert(55) con secuencia aleatora (1,0)
4 X - - - - - - - -> X
3 X - -> X - - - - -> X
2 X - -> X X - -> X -> X
1 X X -> X X *->* *X* X -> X
0 X X X X X X *X* X X X
---+---------+----+----+----+----+------+------+----+----+--------
-\infty 10 20 30 40 50 *55* 60 70 \infty
* Insert(25) con (1,1,1,1,0)
5 *X* - - - - - - - - *->* *X*
4 X - *->* *X* - - - - - -> X
3 X - *->* *X* X - - - - -> X
2 X - *->* *X* X X - -> X -> X
1 X X *->* *X* X X -> X X -> X
0 X X X *X* X X X X X X X
---+---------+----+------+------+----+----+----+----+----+------+--------
-\infty 10 20 *25* 30 40 50 55 60 70 \infty
* Delete(60)
5 X - - - - - - - -> X
4 X - -> X - - - - -> X
3 X - -> X X - - - -> X
2 X - -> X X X - - *->* X
1 X X -> X X X -> X -> X
0 X X X X X X X X X X
---+---------+----+----+----+----+----+----+----+------+--------
-\infty 10 20 25 30 40 50 55 70 \infty
6. Analisis
* Espacio: Cuanto nodos en promedio?
- cuanto nodos en lista S_i?
- $n/2^i$ en promedio
- Summa sobre todos los niveles
- $n \sum 1/2^i < 2n$
* Tiempo:
- altura promedio es O(\lg n)
- tiempo promedio es O(\lg n)
3.1.1 DONE Paginamiento al Azar :OPTIONAL:
------------------------------------------
- REFERENCIA:
- Capitulo 3 en "Online Computation and Competitive Analysis", de
Allan Borodin y Ran El-Yaniv
- Capitulo 13 en "Randomized Algorithms", de Rajeev Motwani and
Prabhakar Raghavan, p. 368
1) Tipos de Adversarios (cf p372 [Motwani Raghavan]
* Veamos en el caso deterministico un tipo de adversario
offline, como medida de dificultad para las instancias online.
Para el problema de paginamiento con k paginas, el ratio
óptima entre un algoritmo online y offline es de $k$
(e.g. entre LRU y LFD).
* DEFINICIÓN:
En el caso aleatorizado, se puede considerar mas tipos de
adversarios, cada uno definiendo una medida de dificultad y
un modelo de complejidad.
1. Adversario "Oblivious" ("Oblivious Adversary")
El adversario conoce $A$ pero no $R$: el elija su instancia
completamente al inicial, antes de la ejecución online del
algoritmo.
2. Adversario Offline adaptativo
Para este definición, es mas fácil de pensar a un
adversario como un agente distinto del algoritmo offline
con quien se compara el algoritmo online.
El adversario conoce $A$ en total, pero $R$ online, y le
utiliza para generar una instancia peor $I$. Este instancia
$I$ es utilizada de nuevo para ejecutar el algoritmo
offline (quien conoce el futuro) y producir las
complejidades (a cada instante online) con cual comparar la
complejidad del algoritmo online.
3. Adversario Online adaptativo
En este definición, el algoritmo conoce $A$ en total,
construir la instancia $I$ online como en el caso
precedente, pero tiene de tiene de resolverla online también
(de una manera, no se ve en el futuro).
* Comparación de los Tipos de adversarios.
- Por las definiciones, es claro que
- el adversario offline adaptativo
- es mas poderoso que
- el adversario online adaptativo
- es mas poderoso que
- el adversario oblivious
* Competitiva Ratios
* Para un algoritmo online $A$
- Para cada tipo de adversario se define un competitivo ratio:
- C_A^{obl}: competitivo ratio con adversario oblivious
- C_A^{aon}: competitivo ratio con adversario adaptativo online
- C_A^{aof}: competitivo ratio con adversario adaptativo offline
- Es obvio que, para $A$ fijada, considerando un adversario
mas poderoso va aumentar el competitivo ratio:
C_A^{obl} \leq C_A^{aon} \leq C_A^{aof}
* Para un problema
- el competitivo ratio de un problema es el competitivo
ratio mÃ-nima sobre todos los algoritmos correctos para
este problema.
C^{obl} \leq C^{aon} \leq C^{aof} \leq C^{det}
- donde C^{det} es el competitivo ratio de un algoritmo
online deterministico.
3.1.2 DONE Arboles Binarios de Busqueda aleatorizados
------------------------------------------------------
- Conrado MartÃ-nez. Randomized binary search trees. Algorithms
Seminar. Universitat Politecnica de Catalunya, Spain, 1996.
- Conrado MartÃ-nez and Salvador Roura. Randomized binary search
trees. J. ACM, 45(2):288–323, 1998.
- [en.wikipedia.org/ ... d_binary_search_tree]
3.1.3 DONE Complejidad Probabilistica: cotas inferiores
--------------------------------------------------------
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teorÃ-a de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teorÃ-a de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teorÃ-a de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que M_{a,b}
es el costo del algoritmo $a$ sobre la instancia $b$.
Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mÃ-nima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ TodavÃ-a falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe
una instan ca tan mal que la pero distribución de
instancias.
5) PrÃ-ncipe de Yao
* Del leima de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Ejemplos de Problemas NP-Dificiles
1. *Maxcut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
*maximiza* la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
- se aproxima con un factor de dos con un algoritmo
aleatorizado en tiempo polinomial.
2. *mincut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
minimiza la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
* Relacion con la nocion de NP:
- El arbol representando la ejecucion de un algoritmo
non-deterministico en tiempo polynomial (i.e. NP) se
decomposa en dos partes, de altura polynomial $p(n)$:
- una parte de *decisiones* non-deterministica (fan-out)
- una parte de *verificacion* deterministica (straight)
- Si una solamente de las $2^{p(n))$ soluciones corresponde a
una solucion valida del problema, la aleatorizacion no
ayuda, pero si una proporcion constante
(e.g. 1/2,1/3,1/4,...) de las ramas corresponden a una
solucion correcta, existe un algoritmo aleatorizado que
resuelve el problema NP-dificil en tiempo polynomial *en
promedio*.
5 DONE Complejidad de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
* Considera algoritmos con comparaciones
- algoritmos deterministicos se pueden ver como arboles de
decisión.
- algoritmos aleatorios se pueden ver (de manera
intercambiable) como
- una distribución sobre los arboles de decisión,
- un arbol de decisión con algunos nodos "aleatorios".
- La complejidad en una instancia de un algoritmo aleatorio
es el promedio de la complejidad (en este instancia) de
los algoritmos deterministicos que le compasan:
C((A_r)_r,I) = E_r( C(A_r,I) )
- La complejidad en el peor caso de un algoritmo aleatorio
es el peor caso del promedio de la complejidad de los
algoritmos deterministicos que le composan:
C((A_r)_r) = \max_I C((A_r)_r,I) = \max_I E_r( C(A_r,I) )
6 DONE Tecnicas de cotas inferiores de la complejidad aleatorizada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
REFERENCIA: Capitulo 2, "Randomized Complexity" en "Concepts of
Combinatorial Optimization", pages 21--38, 2010.
[www.cs.uwaterloo.ca/ ... RandomizedComplexity]
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teoría de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teoría de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teoría de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que
$M_{a,b}$ es el costo del algoritmo $a$ sobre la instancia
$b$. Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mínima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ Todavía falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe una
instancia tan mal que la peor distribución de
instancias.
5) Príncipe de Yao
* Del lema de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Formalización
Algoritmos clásicos Non clásicos
------------------------+---------------
Siempre hacen lo mismo aleatorizados
Nunca se equivocan Monte Carlo
Siempre terminan Las Vegas
* Clasificación de los algoritmos *de decisión* aleatorizados
1. ProbabilÃ-stico: Monte Carlo
- P(error) < épsilon
- Ejemplo:
- detección de cliquas
- Se puede considerar también variantes mas fines:
- two-sided error ( => clase de complejidad BPP)
- P(accept | negative) < \epsilon
- P(refuse | negative) > 1-\epsilon
- P(accept | positive) > 1-\epsilon
- P(refuse | positive) < epsilon
- One-sided error
- P(accept | negative) < epsilon
- P(refuse | negative) > 1 -\epsilon
- P(accept | positive) = 1
- P(refuse | positive) = 0
2. ProbabilÃ-stico: Las Vegas
- Tiempo es una variable aleatoria
- Ejemplos:
- determinar primalidad [Miller Robin]
- búsqueda en arreglo desordenado
- intersección de arreglos ordenados
- etc...
* Relación
- Si se puede verificar el resultado en tiempo razonable,
Monte Carlos iterado hasta correcto => Las Vegas
8 CANC Primalidad
~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
REFERENCIAS:
- Primalidad: Capitulo 14.6 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
- [en.wikipedia.org/ ... lity_test#Complexity]
* Algoritmo "Random Walks" para SAT
1. eliga cualquieras valores $x_1,\ldots,x_n$
2. si todas las clausilas son satisfechas,
- accepta
3. sino
- eliga una clausula non satisfecha (deterministicamente
o no)
- eliga una de las variables de esta closula.
4. Repite es $r$ veces.
* PRIMES is in coNP
si $x\in coNP$, eliga non-deterministicamente una
decomposicion de $x$ y verificalo.
* PRIMES is in NP (hence in NP\cap coNP)
In 1975, Vaughan Pratt showed that there existed a
certificate for primality that was checkable in polynomial
time, and thus that PRIMES was in NP, and therefore in NP Á
coNP.
* PRIMES in coRP
The subsequent discovery of the Solovay-Strassen and
Miller-Rabin algorithms put PRIMES in coRP.
* PRIMES in ZPP = RP \cap coRP
In 1992, the Adleman-Huang algorithm reduced the complexity
to ZPP = RP Á coRP, which superseded Pratt's result.
* PRIMES in QP
The cyclotomy test of Adleman, Pomerance, and Rumely from
1983 put PRIMES in QP (quasi-polynomial time), which is not
known to be comparable with the classes mentioned above.
* PRIMES in P
Because of its tractability in practice, polynomial-time
algorithms assuming the Riemann hypothesis, and other
similar evidence, it was long suspected but not proven that
primality could be solved in polynomial time. The existence
of the AKS primality test finally settled this long-standing
question and placed PRIMES in P.
* PRIMES \in NC? PRIMES \in L?
PRIMES is not known to be P-complete, and it is not known
whether it lies in classes lying inside P such as NC or L.
9 CANC Clases de complejidad aleatorizada :BONUS:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
9.1 RP
=======
- "A *precise* polynomial-time bounded nondeterministic Turing
Machine", aka "maquina de Turing non-deterministica acotadada
polinomialemente *precisa*", es una maquina tal que su
ejecucion sobre las entradas de tamaño n toman tiempo p(n)
*todas*.
- "A *polynomial Monte-Carlo Turing machine*", aka una
"*maquina de Turing de Monte-Carlo* polynomial" para el
idioma $L$, es una tal maquina tal que
- si $x\in L$, al menos la mitad de los $2^{p(|x|)}$ caminos
acceptan $x$
- si $x\not\in L$, *todas* los caminos rechazan $x$.
- La definicion corresponde exactamente a la definicion de
algoritmos de Monte-Carlo. La classe de idiomas reconocidos
por una *maquina de Turing de Monte-Carlo* polynomial es
$RP$.
- $P \subset BP \subset NP$:
- un algoritmo en $P$ accepta con todos sus caminos cuando
una palabra $x$ es en $L$, que es "al menos" la mitad.
- un algoritmo en $NP$ accepta con al menos un camino: un
algoritmo en $RP$ accepta con al menos la mitad de sus
caminos.
9.2 ZPP
========
- ZPP = RP \cap coRP
- Primes \in ZPP
9.3 PP
=======
- Maquina que, si $x\in L$, accepta en la mayoridad de sus
entradas.
- PP probablemente no en NP
- PP probablemente no en RP
9.4 BPP
========
- BPP = { L, \forall x,
- x\in L \implies 3/4 de los caminos acceptan x
- x\not\in L \implies 3/4 de los caminos rechazan x
- RP \subset BPP \subset PP
- BPP = coBPP
=====================================
Author: Jérémy Barbay
Date: 2010-11-09 11:28:36 CLST
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
Table of Contents
=================
1 Definiciones
2 El poder de un algoritmo aleatorizado
3 Aleatorizacion de la entrada
3.1 SkipLists
3.1.1 Paginamiento al Azar
3.1.2 Arboles Binarios de Busqueda aleatorizados
3.1.3 Complejidad Probabilistica: cotas inferiores
4 *Relacion con Problemas NP-Dificiles*
5 Complejidad de un algoritmo aleatorizado
6 Tecnicas de cotas inferiores de la complejidad aleatorizada
7 Algoritmos tipo Monte Carlo y Las Vegas
8 Primalidad
9 Clases de complejidad aleatorizada
9.1 RP
9.2 ZPP
9.3 PP
9.4 BPP
1 DONE Definiciones
~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- *Algoritmos deterministico*
- algoritmo que usa solamente instrucciones
*deterministicas*.
- algoritmo de cual la ejecucion (y, entonces, el
rendimiento) depende solamente del input.
- *Algoritmos aleatorizados*
- algoritmo que usa una instruccion *aleatorizada*
(potentialemente muchas veces)
- una distribucion de probabilidades sobre una familia de
algoritmos deterministicos.
- *Análisis probabilistica*
- analysis del rendimiento de un algoritmo, en promedio
sobre
- el aleatorio de la entrada, o
- el aleatorio del algoritmo, o
- los dos.
- veamos que son nociones equivalentes.
2 DONE El poder de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-14 Thu 12:00-13:30>
- Nota: Trae los juguetes/cajas de colores, con un tesoro a esconder a dentro.
Ejemplos de algoritmos o estructuras de datos aleatorizados
1. *hidden coin*
- Decidir si un elemento pertenece en un lista
desordenada de tamaño k, o si hay una moneda a dentro
de una de las $k$ caja.
- cual son las complejidades determinisitica y
aleatorizada del problema de encontrar *una* moneda,
con $c$ la cantidad de monedas,
- si $c=1$?
- si $c=n-1$?
- si $c=n/2$?
- Respuestas:
- Si una sola instancia de la valor buscada
- k en el peor caso deterministico
- k/2 en (promedio y en) el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
- Si r instancias de la valor buscada
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
3. Decidir si un elemento pertenece en una lista ordenadas
de tamaño n
* \Theta(\lg n) comparaciones en ambos casos,
deterministico y probabilÃ-stico.
4. *problema de union*
* Decidir si un elemento pertenece en una de las k listas
ordenadas de tamaño n
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n)/2 comparaciones
* Si r
* Independencia de la distribucion de la entrada
- Si el input sigue una distribucion non-conocida, el input
perturbado tiene una distribucion conocida (para una
perturbacion bien elegida)
- Ejemplo:
- flip $b$ de una bit con probabilidad $p$ que puede ser
distinta de $1/2$.
- suma-lo modulo 1 con un otro bit aleatorizado, con
probabilidad $1/2$ de ser uno.
- la suma es igual a uno con probabilidad $1/2$.
* Estructuras de datos aleatorizadas
- *funciones de hash*:
- estructura de datos aleatorizada,
- donde (a,b) son elegidos al azar.
- *skiplists*
- estructura de datos aleatorizada,
- que simula en promedio un arbol binario
3.1 DONE SkipLists
===================
1) Estructuras de datos para diccionarios
- [X] Arreglo ordenado
- [ ] "Move To Front" list (did they see it already?)
- [X] Arboles binarios
- [X] Arboles binarios aleatorizados
- [X] Arboles 2-3 ( they saw it already?)
- [X] Red-Black Trees ( they saw it already?)
- [X] AVL
- [X] Skip List
- [ ] Splay trees
2) Skip Lists
1. Motivación
- un arbol binario con entradas aleatorizadas tienen una
altura O(lg n), pero eso supone un orden de input
aleatorizados.
- El objetivo de las "skip lists" es de poner el aleatorio
a dentro de la estructura.
- también, es el equivalente de una búsqueda binaria en
listas via un resumen de resumen de resumen...
2. Definición
- una skip-list de altura $h$ para un diccionario $D$ de
$n$ elementos es una familia de lists $S_0,\ldots,S_h$ y
un puntero al primero elemento de $S_h$, tal que
- $S_0$ contiene $D$;
- cada $S_i$ contiene un subconjunto aleatorio de $S_{i-1}$
(en promedio la mitad)
- se puede navegar de la izquierda a la derecha, y de la
cima hasta abajo.
- se puede ver como $n$ torres de altura aleatorizadas,
conectadas horizontalmente con punteros de la
izquierda a la derecha.
- la información del diccionario están solamente en S_0 (no
se duplica)
3. Ejemplo
4 X - - - - - - -> X
3 X - -> X - - - -> X
2 X - -> X X -> X -> X
1 X X -> X X -> X -> X
0 X X X X X X X X X
---+---------+----+----+----+----+----+----+----+--------
-\infty 10 20 30 40 50 60 70 \infty
4. Operaciones
* Search(x):
- Start a the first element of $S_h$
- while not in $S_0$
- go down one level
- go right till finding a key larger than x
* Insert(x)
- Search(x)
- create a tower of random height (p=1/2 to increase
height, typically)
- insert it in all the lists it cuts.
* Delete(x)
- Search(x)
- remove tower from all lists.
5. Ejemplos
* Insert(55) con secuencia aleatora (1,0)
4 X - - - - - - - -> X
3 X - -> X - - - - -> X
2 X - -> X X - -> X -> X
1 X X -> X X *->* *X* X -> X
0 X X X X X X *X* X X X
---+---------+----+----+----+----+------+------+----+----+--------
-\infty 10 20 30 40 50 *55* 60 70 \infty
* Insert(25) con (1,1,1,1,0)
5 *X* - - - - - - - - *->* *X*
4 X - *->* *X* - - - - - -> X
3 X - *->* *X* X - - - - -> X
2 X - *->* *X* X X - -> X -> X
1 X X *->* *X* X X -> X X -> X
0 X X X *X* X X X X X X X
---+---------+----+------+------+----+----+----+----+----+------+--------
-\infty 10 20 *25* 30 40 50 55 60 70 \infty
* Delete(60)
5 X - - - - - - - -> X
4 X - -> X - - - - -> X
3 X - -> X X - - - -> X
2 X - -> X X X - - *->* X
1 X X -> X X X -> X -> X
0 X X X X X X X X X X
---+---------+----+----+----+----+----+----+----+------+--------
-\infty 10 20 25 30 40 50 55 70 \infty
6. Analisis
* Espacio: Cuanto nodos en promedio?
- cuanto nodos en lista S_i?
- $n/2^i$ en promedio
- Summa sobre todos los niveles
- $n \sum 1/2^i < 2n$
* Tiempo:
- altura promedio es O(\lg n)
- tiempo promedio es O(\lg n)
3.1.1 DONE Paginamiento al Azar :OPTIONAL:
------------------------------------------
- REFERENCIA:
- Capitulo 3 en "Online Computation and Competitive Analysis", de
Allan Borodin y Ran El-Yaniv
- Capitulo 13 en "Randomized Algorithms", de Rajeev Motwani and
Prabhakar Raghavan, p. 368
1) Tipos de Adversarios (cf p372 [Motwani Raghavan]
* Veamos en el caso deterministico un tipo de adversario
offline, como medida de dificultad para las instancias online.
Para el problema de paginamiento con k paginas, el ratio
óptima entre un algoritmo online y offline es de $k$
(e.g. entre LRU y LFD).
* DEFINICIÓN:
En el caso aleatorizado, se puede considerar mas tipos de
adversarios, cada uno definiendo una medida de dificultad y
un modelo de complejidad.
1. Adversario "Oblivious" ("Oblivious Adversary")
El adversario conoce $A$ pero no $R$: el elija su instancia
completamente al inicial, antes de la ejecución online del
algoritmo.
2. Adversario Offline adaptativo
Para este definición, es mas fácil de pensar a un
adversario como un agente distinto del algoritmo offline
con quien se compara el algoritmo online.
El adversario conoce $A$ en total, pero $R$ online, y le
utiliza para generar una instancia peor $I$. Este instancia
$I$ es utilizada de nuevo para ejecutar el algoritmo
offline (quien conoce el futuro) y producir las
complejidades (a cada instante online) con cual comparar la
complejidad del algoritmo online.
3. Adversario Online adaptativo
En este definición, el algoritmo conoce $A$ en total,
construir la instancia $I$ online como en el caso
precedente, pero tiene de tiene de resolverla online también
(de una manera, no se ve en el futuro).
* Comparación de los Tipos de adversarios.
- Por las definiciones, es claro que
- el adversario offline adaptativo
- es mas poderoso que
- el adversario online adaptativo
- es mas poderoso que
- el adversario oblivious
* Competitiva Ratios
* Para un algoritmo online $A$
- Para cada tipo de adversario se define un competitivo ratio:
- C_A^{obl}: competitivo ratio con adversario oblivious
- C_A^{aon}: competitivo ratio con adversario adaptativo online
- C_A^{aof}: competitivo ratio con adversario adaptativo offline
- Es obvio que, para $A$ fijada, considerando un adversario
mas poderoso va aumentar el competitivo ratio:
C_A^{obl} \leq C_A^{aon} \leq C_A^{aof}
* Para un problema
- el competitivo ratio de un problema es el competitivo
ratio mÃ-nima sobre todos los algoritmos correctos para
este problema.
C^{obl} \leq C^{aon} \leq C^{aof} \leq C^{det}
- donde C^{det} es el competitivo ratio de un algoritmo
online deterministico.
3.1.2 DONE Arboles Binarios de Busqueda aleatorizados
------------------------------------------------------
- Conrado MartÃ-nez. Randomized binary search trees. Algorithms
Seminar. Universitat Politecnica de Catalunya, Spain, 1996.
- Conrado MartÃ-nez and Salvador Roura. Randomized binary search
trees. J. ACM, 45(2):288–323, 1998.
- [en.wikipedia.org/ ... d_binary_search_tree]
3.1.3 DONE Complejidad Probabilistica: cotas inferiores
--------------------------------------------------------
* REFERENCIA:
- Capitulo 1 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teorÃ-a de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teorÃ-a de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teorÃ-a de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que M_{a,b}
es el costo del algoritmo $a$ sobre la instancia $b$.
Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mÃ-nima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ TodavÃ-a falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe
una instan ca tan mal que la pero distribución de
instancias.
5) PrÃ-ncipe de Yao
* Del leima de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Ejemplos de Problemas NP-Dificiles
1. *Maxcut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
*maximiza* la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
- se aproxima con un factor de dos con un algoritmo
aleatorizado en tiempo polinomial.
2. *mincut*
- dado un grafe $G=(V,E)$
- encontrar una partition $(L,R)$ tq $L\cup R=V$ y que
minimiza la cantidad de aristas entre $L$ y $R$
- el problema es NP dificil
* Relacion con la nocion de NP:
- El arbol representando la ejecucion de un algoritmo
non-deterministico en tiempo polynomial (i.e. NP) se
decomposa en dos partes, de altura polynomial $p(n)$:
- una parte de *decisiones* non-deterministica (fan-out)
- una parte de *verificacion* deterministica (straight)
- Si una solamente de las $2^{p(n))$ soluciones corresponde a
una solucion valida del problema, la aleatorizacion no
ayuda, pero si una proporcion constante
(e.g. 1/2,1/3,1/4,...) de las ramas corresponden a una
solucion correcta, existe un algoritmo aleatorizado que
resuelve el problema NP-dificil en tiempo polynomial *en
promedio*.
5 DONE Complejidad de un algoritmo aleatorizado
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
* Considera algoritmos con comparaciones
- algoritmos deterministicos se pueden ver como arboles de
decisión.
- algoritmos aleatorios se pueden ver (de manera
intercambiable) como
- una distribución sobre los arboles de decisión,
- un arbol de decisión con algunos nodos "aleatorios".
- La complejidad en una instancia de un algoritmo aleatorio
es el promedio de la complejidad (en este instancia) de
los algoritmos deterministicos que le compasan:
C((A_r)_r,I) = E_r( C(A_r,I) )
- La complejidad en el peor caso de un algoritmo aleatorio
es el peor caso del promedio de la complejidad de los
algoritmos deterministicos que le composan:
C((A_r)_r) = \max_I C((A_r)_r,I) = \max_I E_r( C(A_r,I) )
6 DONE Tecnicas de cotas inferiores de la complejidad aleatorizada
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-19 Tue 12:00-13:30>
REFERENCIA: Capitulo 2, "Randomized Complexity" en "Concepts of
Combinatorial Optimization", pages 21--38, 2010.
[www.cs.uwaterloo.ca/ ... RandomizedComplexity]
* Notes:
1) Problema
- Strategia de adversario no funciona
- En algunos casos, teoría de códigos es suficiente
- e.g. búsqueda en arreglo ordenado
- eso es una cota inferior sobre el tamaño del
certificado
- En otros caso, teoría de códigos no es suficiente
- en particular, cuando el precio para verificar un
certificado es mas pequeño que de encontrarlo.
- En estos casos, utilizamos otras técnicas:
- teoría de juegos (que vamos a ver) y equilibro de Nash
- cotas sobre la comunicación en un sistema de
"Interactive Proof"
2) Algunas Notaciones Algebraicas
Sea:
- A una familia de $n_a$ algoritmos deterministicos
- $a$ un vector (0,...,0,1,0,...,0) de dimensión $n_a$
- $\alpha$ una distribución de probabilidad de dimensión $n_a$
- B una familia de $n_n$ instancias
- $b$ un vector (0,...,0,1,0,...,0) de dimensión $n_b$
- $\beta$ una distribución de probabilidad de dimensión $n_b$
- M una matriz de dimensión $n_a\times n_b$ tal que
$M_{a,b}$ es el costo del algoritmo $a$ sobre la instancia
$b$. Por definición,
- a^t M b = M_{a,b}
- \alpha^t M b es la complejidad en promedio (sobre el
aleatorio del algoritmo \alpha) de \alpha sobre b
- a^t M \beta es la complejidad en promedio (sobre la
distribución de instancias \beta) de a sobre \beta
- \alpha^t M \beta es la complejidad en promedio del
algoritmo aleatorizados \alpha sobre la distribución de
instancia \beta.
3) von Neuman's theorem: infsup = supinf = minmax = maxmin
1. OPCIONAL Existencia de $\tilde{\alpha}$ et $\tilde{\beta}$
Dado $\phi$ y $\psi$ definidas sobre $\mathbb{R}^m$ y $\mathbb{R}^n$ por
$$\phi(\alpha) = \sup_\beta \alpha ^T M \beta
\,\mbox{ y }\,
\psi(\beta) = \inf_\alpha \alpha ^T M \beta$$
Entonces:
- $\phi(\alpha) = \max_\beta \alpha ^T M \beta$
- $\psi(\beta) = \min_\alpha \alpha ^T M \beta$
- hay estrategias mixtas
- $\tilde{\alpha}$ por \A\
- $\tilde{\beta}$ por \B\
- tal que
- $\phi$ es a su mínima en $\tilde{\alpha}$ y
- $\psi$ es a su máxima en $\tilde{\beta}$.
2. Resultado de von Neuman:
Dado un juego $\Gamma$ definido por la matrica $M$~:
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
3. Interpretación:
+ Este resultado significa que si consideramos ambos
distribuciones sobre algoritmos y instancias, no
importa el orden del max o min:
- podemos elegir el mejor algoritmo (i.e. minimizar
sobre los algoritmos aleatorizados) y después
elegir la peor distribución de instancias para el
(i.e. maximizar sobre las distribuciones de
instancias), o al reves
- podemos elegir la peor distribución de instancias
(i.e. maximizar sobre las distribuciones de
instancias), y considerar el mejor algoritmo
(i.e. minimizar sobre los algoritmos
aleatorizados) para este distribución.
+ ATENCIÓN!!!! Veamos que
- El promedio (sobre las instancias) de las
complejidades (de los algoritmos) en el peor caso
- no es igual
- al peor caso (sobre las instancias) de la complejidad
en promedio (sobre el aleatorio del algoritmo)
- donde el segundo termo es realmente la complejidad de
un algoritmo aleatorizados.
+ Todavía falta la relación con la complejidad en el
peor caso $b$ de un algoritmo aleatorizados $\alpha$:
$\max_b \min_\alpha \alpha ^T M b$
4) Lema de Loomis
* Dado una estrategia aleatoria $\alpha$, emite una instancia
$b$ tal que $\alpha$ es tan mal en $b$ que en el
peor $\beta$.
$$
\forall \alpha \exists b,
\max_\beta \alpha^T M \beta = \alpha^T M b
$$
* Dado una distribución de instancias $\beta$, existe un
algoritmo deterministico $a$ tal que $a$ es tan
bien que el mejor algoritmo aleatorizados $\alpha$ sobre
la distribución de instancias $\beta$:
$$
\forall \beta \exists a,
\min_\alpha \alpha^T M \beta = a^T M \beta
$$
* Interpretación:
+ En frente a una distribución de instancias especifica,
siempre existe un algoritmo deterministico óptima en
comparación con los algoritmos aleatorizados (que
incluen los deterministicos).
+ En frente a un algoritmo aleatorizados, siempre existe una
instancia tan mal que la peor distribución de
instancias.
5) Príncipe de Yao
* Del lema de Loomis podemos concluir que
$$
\max_\beta \alpha^T M \beta = \max_b \alpha^T M b
$$
$$
\min_\alpha \alpha^T M \beta = \min_a a^T M \beta
$$
* Del resultado de von Neuman sabemos que maxmin=minmax
(sobre \alpha y \beta):
$$
\min_\alpha \max_\beta \alpha ^T M \beta
=
\max_\beta \min_\alpha \alpha ^T M \beta
$$
* Entonces
$$
\min_alpha \max_b \alpha^T M b
= (Loomis)
\min_\alpha \max_\beta \alpha ^T M \beta
= (von Neuman)
\max_\beta \min_\alpha \alpha ^T M \beta
= (Loomis)
\max_\beta \min_a a^T M \beta
$$
* Interpretación
\min_\alpha \max_b \alpha^T M b
\_______ La complejidad
\______ _______ ________ del mejor algoritmo aleatorizado
\___ ___________ en el peor caso
es igual a
\max_\beta \min_a \alpha^T M b
\_______ La complejidad
\___ ___________ del mejor algoritmo deterministico
\______ _______ ________ sobre la peor distribución de instancias
"El peor caso del mejor algoritmo aleatorizado
corresponde a
la peor distribución para el mejor algoritmo deterministico."
* Ejemplos de cotas inferiores:
1. Decidir si un elemento pertenece en una lista ordenadas de tamaño n
- Cual es el peor caso $b$ de un algoritmo aleatorizado $\alpha$?
- Buscamos una distribución $\beta_0$ que es mala para todos
los algoritmos deterministicos $a$ (del modelo de comparaciones)
- Consideramos la distribución uniforma.
- Cada algoritmo deterministico se puede representar como un
arbol de decisión (binario) con $2n+1$ hojas.
- Ya utilizamos para la cota inferior deterministica que la
altura de un tal arbol es al menos $\lg(2n+1)\in\Omega(\lg
n)$. Esta propiedad se muestra por recurrencia.
- De manera similar, se puede mostrar por recurrencia que la
altura en promedio de un tal arbol binario es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, la complejidad promedio de cada algoritmo
deterministico $a$ sobre $\beta_0$ es al menos
$\lg(2n+1)\in\Omega(\lg n)$.
- Entonces, utilizando el principie de Yao, la complejidad en
el peor caso de un algoritmo aleatorizado en el modelo de
comparaciones es al menos $\lg(2n+1)\in\Omega(\lg n)$.
- El corolario interesante, es que el algoritmo
deterministico de búsqueda binaria es *oprima* a dentro de
la clase mas general de algoritmos aleatorizados.
2. Decidir si un elemento pertenece en un lista desordenada de tamaño k
* Si una sola instancia de la valor buscada ($r=1$)
* Cotas superiores
- k en el peor caso deterministico
- (k+1)/2 en el peor caso aleatorio
- con una dirección al azar
- con lg(k!) bits aleatorios
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición, y que
consideran todas las posiciones en el peor caso:
entonces cada algoritmo puede ser representado por una
permutación sobre $k$.
- Dado un algoritmo deterministico $a$, para cada
$i\in[1,k]$, hay una instancia sobre cual el performe
$i$ comparaciones. Entonces, su complejidad en promedio
en este instancia es $\sum_i i/k$, que es $k(k+1)/2k =
(k+1)/2$. Como eso es verdad para todos los algoritmos
deterministicos, es verdad para el mejor de ellos
también.
- Entonces, utilizando el principio de Yao, la complejidad
en el peor caso de un algoritmo aleatorizado en el
modelo de comparaciones es al menos $(k+1)/2$.
* Si r instancias de la valor buscada
* Cotas superiores
- k-r en el peor caso deterministico
- O(k/r) en (promedio y en) el peor caso aleatorio
* Cota inferior
- Buscamos una distribución $\beta_0$ que es mala para
todos los algoritmos deterministicos $a$ (en el modelo de
comparaciones).
- Consideramos la distribución uniforma (cada algoritmo
reordena la instancia a su gusto, de toda manera,
entonces solamente la distribución uniforma tiene
sentido): cada posición es elegida con probabilidad $1/k$
- Se puede considerar solamente los algoritmos que no
consideran mas que una ves cada posición.
- De verdad, no algoritmo tiene de considerar mas
posiciones que $k-r+1$, entonces hay menos algoritmos
que de permutaciones sobre $k$ elementos. Para
simplificar la prueba, podemos exigir que los algoritmos
especifican una permutación entera, pero no vamos a
contar las comparaciones después que un de las $r$
valores fue encontrada.
3. Decidir si un elemento pertenece en k listas ordenadas de tamaño n/k
* Cotas superiores
* Si una sola lista contiene la valor buscada
- k búsquedas en el peor caso deterministico, que da
k\lg(n/k) comparaciones
- k/2 búsquedas en (promedio y en) el peor caso
aleatorio, que da k\lg(n/k)/2 comparaciones
* Si r
* Formalización
Algoritmos clásicos Non clásicos
------------------------+---------------
Siempre hacen lo mismo aleatorizados
Nunca se equivocan Monte Carlo
Siempre terminan Las Vegas
* Clasificación de los algoritmos *de decisión* aleatorizados
1. ProbabilÃ-stico: Monte Carlo
- P(error) < épsilon
- Ejemplo:
- detección de cliquas
- Se puede considerar también variantes mas fines:
- two-sided error ( => clase de complejidad BPP)
- P(accept | negative) < \epsilon
- P(refuse | negative) > 1-\epsilon
- P(accept | positive) > 1-\epsilon
- P(refuse | positive) < epsilon
- One-sided error
- P(accept | negative) < epsilon
- P(refuse | negative) > 1 -\epsilon
- P(accept | positive) = 1
- P(refuse | positive) = 0
2. ProbabilÃ-stico: Las Vegas
- Tiempo es una variable aleatoria
- Ejemplos:
- determinar primalidad [Miller Robin]
- búsqueda en arreglo desordenado
- intersección de arreglos ordenados
- etc...
* Relación
- Si se puede verificar el resultado en tiempo razonable,
Monte Carlos iterado hasta correcto => Las Vegas
8 CANC Primalidad
~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
REFERENCIAS:
- Primalidad: Capitulo 14.6 en "Randomized Algorithms", de Rajeev Motwani and Prabhakar Raghavan.
- [en.wikipedia.org/ ... lity_test#Complexity]
* Algoritmo "Random Walks" para SAT
1. eliga cualquieras valores $x_1,\ldots,x_n$
2. si todas las clausilas son satisfechas,
- accepta
3. sino
- eliga una clausula non satisfecha (deterministicamente
o no)
- eliga una de las variables de esta closula.
4. Repite es $r$ veces.
* PRIMES is in coNP
si $x\in coNP$, eliga non-deterministicamente una
decomposicion de $x$ y verificalo.
* PRIMES is in NP (hence in NP\cap coNP)
In 1975, Vaughan Pratt showed that there existed a
certificate for primality that was checkable in polynomial
time, and thus that PRIMES was in NP, and therefore in NP Á
coNP.
* PRIMES in coRP
The subsequent discovery of the Solovay-Strassen and
Miller-Rabin algorithms put PRIMES in coRP.
* PRIMES in ZPP = RP \cap coRP
In 1992, the Adleman-Huang algorithm reduced the complexity
to ZPP = RP Á coRP, which superseded Pratt's result.
* PRIMES in QP
The cyclotomy test of Adleman, Pomerance, and Rumely from
1983 put PRIMES in QP (quasi-polynomial time), which is not
known to be comparable with the classes mentioned above.
* PRIMES in P
Because of its tractability in practice, polynomial-time
algorithms assuming the Riemann hypothesis, and other
similar evidence, it was long suspected but not proven that
primality could be solved in polynomial time. The existence
of the AKS primality test finally settled this long-standing
question and placed PRIMES in P.
* PRIMES \in NC? PRIMES \in L?
PRIMES is not known to be P-complete, and it is not known
whether it lies in classes lying inside P such as NC or L.
9 CANC Clases de complejidad aleatorizada :BONUS:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-10-21 Thu 12:00-13:30>
9.1 RP
=======
- "A *precise* polynomial-time bounded nondeterministic Turing
Machine", aka "maquina de Turing non-deterministica acotadada
polinomialemente *precisa*", es una maquina tal que su
ejecucion sobre las entradas de tamaño n toman tiempo p(n)
*todas*.
- "A *polynomial Monte-Carlo Turing machine*", aka una
"*maquina de Turing de Monte-Carlo* polynomial" para el
idioma $L$, es una tal maquina tal que
- si $x\in L$, al menos la mitad de los $2^{p(|x|)}$ caminos
acceptan $x$
- si $x\not\in L$, *todas* los caminos rechazan $x$.
- La definicion corresponde exactamente a la definicion de
algoritmos de Monte-Carlo. La classe de idiomas reconocidos
por una *maquina de Turing de Monte-Carlo* polynomial es
$RP$.
- $P \subset BP \subset NP$:
- un algoritmo en $P$ accepta con todos sus caminos cuando
una palabra $x$ es en $L$, que es "al menos" la mitad.
- un algoritmo en $NP$ accepta con al menos un camino: un
algoritmo en $RP$ accepta con al menos la mitad de sus
caminos.
9.2 ZPP
========
- ZPP = RP \cap coRP
- Primes \in ZPP
9.3 PP
=======
- Maquina que, si $x\in L$, accepta en la mayoridad de sus
entradas.
- PP probablemente no en NP
- PP probablemente no en RP
9.4 BPP
========
- BPP = { L, \forall x,
- x\in L \implies 3/4 de los caminos acceptan x
- x\not\in L \implies 3/4 de los caminos rechazan x
- RP \subset BPP \subset PP
- BPP = coBPP
*Algoritmos en línea*. Competividad. Adaptividad.
8
Jérémy Barbay 12 Oct 201012/10/10 a las 14:08 hrs.2010-10-12 14:08:12
+ *Algoritmos en línea*. Competividad. Adaptividad.
- List Accessing
REFERENCIA: Capitulo 1 en "Online Computation and Competitive
Analysis", de Allan Borodin y Ran El-Yaniv
1) "List Accessing"
- Considera la secuencia de búsqueda de tamaño $n$, en un
diccionario de tamaño $\sigma$:
"1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,..."
- Cual es el rendimiento de una estructura de diccionario
*estática* (tal que AVL) en este secuencia?
- $n\lg\sigma$
- Se puede mejorar?
- si, utilizando la *localidad* de las consultas, en
*estructuras de datos dinámicas*.
2) Soluciones
1. MTF ("Move To Front"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada en frente
2. TRANS ("Transpose"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada de una posición mas cerca del frente
3. FC ("Frequency Count"):
- mantiene un contador para la frecuencia de cada elemento
- mantiene la lista ordenada para frecuencia decreciente.
4. Splay Trees (y otras estructuras con propiedades de localidad)
([www.dcc.uchile.cl/ ... tes/Diccionario/#8b])
3) Estos son "Algoritmos en Linea"
- algoritmo de optimización
- que conoce solamente una parte de la entrada al tiempo t.
- se compara a la competitividad con el algoritmo offline que
conoce toda la instancia.
- Como se puede medir su complejidad?
- cada algoritmo ejecuta O(n) comparaciones para cada
búsqueda en el peor caso!!!!
- tiene de considerar instancies "fáciles" y "difíciles"
- una medida de dificultad
- e.g. el rendimiento del *mejor algoritmo "offline"*
4) Competitive Analysis: instancias "difíciles" o "fáciles"
- Las estructuras de datos dinámicas pueden aprovechar de
secuencias "fáciles" de consultas: eso se llama "online".
- pero para muchos problemas online, todas las heurísticas se
comportan de la misma manera en el peor caso.
- Por eso se identifica una medida de dificultad de las
instancias, y se comparan los rendimientos de los
algoritmos sobre instancias que tienen una valor fijada de
este medida de dificultad.
- Tradicionalmente, esta medida de dificultad es el
rendimiento del mejor algoritmo "offline": eso se llama
*competitive analysis*, resultando en el *competitive
ratio*, el ratio entre la complejidad del algoritmo ONLINE
y la complejidad del mejor algoritmo OFFLINE.
- por ejemplo, veamos que MTF tiene un competitive ratio de
2
- Pero todavía hay algoritmos con performancia practicas muy
distintas que tienen el mismo competitive ratio. Por eso se
introduce otras medidas de dificultadas mas sofisticadas, y
mas especialidades en cada problema.
5) Competitividad
* Optimización/aproximación
- A es *k(n) competitiva* para un problema de *minimización* si
- \exist b, \forall n,x |x|=n
- C_A(x) - k(n) C_{OPT}(x) \leq b
- A es *k(n) competitiva* para un problema de *maximización* si
- \exist b, \forall n,x |x|=n
- C_{OPT}(x) - k(n) C_{A}(x) \leq b
* Competitiva Ratio
- an algoritmo en linea es *c-competitiva* si
- \exists \alpha, \forall I
- ALG(I) \leq c OPT(I) + \alpha
- an algoritmo en linea es *estrictamente c-competitiva* si
- \forall I
- ALG(I) \leq c OPT(I)
6) Sleator-Tarjan sobre MTF
- costo de una búsqueda negativa (la llave NO esta en el
diccionario)
- $\sigma$
- costo de una búsqueda positiva (la llave esta en el
diccionario)
- la posición de la llave, no mas que $\sigma$
- en promedio para una distribución de probabilidad fijada:
- $MTF \leq 2 OPT$,
- Prueba: (from my notes in my CS240 slides)
How does MTF compare to the optimal ordering?
- Assume that:
- the keys $k_1,\ldots,k_n$ have probabilities
$p_1 \ge p_2 \ge \ldots \ge p_n \ge 0$
- the list is used sufficiently to reach a steady state.
- Then:
$$C_{MTF} < 2\cdot C_{OPT}$$
- Proof:
\begin{eqnarray*}
C_{OPT} & = & \sum_{j=1}^{n} jp_j
C_{MTF} & = & \sum_{j=1}^{n} p_j(\mbox{cost of finding $k_j$})
& = & \sum_{j=1}^{n} p_j(1+\alert{\mbox{number of keys before } k_j})
\end{eqnarray*}
- To compute the average number of keys before $k_j$:
\begin{eqnarray*}
\Pr[\mbox{ $k_i$ before $k_j$}] &=& \frac{p_i}{p_i+p_j}
E(\mbox{ \alert{number of keys before $k_j$}}) &=&
\sum_{i\neq j} \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- $k_i$ is before $k_j$ if and only if
$k_i$ was accessed more recently than $k_j$.
- Consider the last time either $k_i$ or $k_j$ was looked up. What is the probability that it was $k_i$?
\begin{eqnarray*}
P(k_i \textrm{ before } k_j) &=
%& P(k_i \textrm{ chosen }|\ k_i \textrm{ or }k_j\textrm{ chosen }) \\ &=
& \frac{P(k_i \textrm{ chosen })}{P(k_i \textrm{ or } k_j \textrm{ chosen })}
&=& \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- Therefore,
\begin{eqnarray*}
C_{MTF} & = & \sum_{j=1}^{n} p_j (1+\sum_{i\not = j} \frac{p_i}{p_i+p_j})
\mbox{\hspace{.5cm} (Joining both previous formulas.)}
& = & 1 + 2 \sum_{j=1}^n \sum_{i0 y S=
p_1^l,p_2^l,\ldots,p_{k-1}^l,(p_k,p_{k+1})^{l-1}
- Después de las (k-1)l primeras consultas, LFU va a tener
un miss cada consulta, cuando LFD solamente dos.
5. Que tal de FWF?
- MRU=LIFO es un poco estúpido, su mala rendimiento no es
una sorpresa.
- FWF es un algoritmo muy ingenuo también, pero vamos a
ver que no tiene un rendimiento tan mal "en teoría".
5) BONUS: Competive Analysis: Algoritmos a Marcas
1. $k$-fases particiones
Para cada secuencia $S$, partitionala en secuencias
$S_1,\ldots,S_\delta$ tal que
- $S_0 = \emptyset$
- $S_i$ es la secuencia Maxima después de $S_{i-1}$ que
contiene al máximum $k$ consultas distintas.
- Llamamos "fase $i$" el tiempo que el algoritmo considera
elementos de la subsecuencia $S_i$.
- Nota que eso es independiente del algoritmo considerado.
2. Algoritmo con marcas
- agrega a cada pagina de memoria lenta un bit de marca.
- al inicio de cada fase, remuda las marcas de cada
pagina en memoria.
- a dentro de una fase, marca una pagina la primera vez
que es consultada.
- un algoritmo a marca ("marking algorithm") es un
algoritmo que nunca remuda una pagina marcada de su
cache.
3. Un algoritmo con marcas es $k$-competitiva
- En cada fase,
- un algoritmo ONLINE con marcas performa al máximum $k$ miss.
- Un algoritmo OFFLINE (e.g. LFD) performa al mínimum
$1$ miss.
- QED
4. LRU, CLOCK y FWF son algoritmos con marcas
5. LRU, CLOCK y FWF tienen un ratio competitivo ÓPTIMO
6) Mas resultados:
1. La análisis se puede generalizar al caso donde el
algoritmo offline tiene h paginas, y el algoritmo online
tiene $k\geq h$ paginas.
- Cada algoritmo *con marcas* es
$\frac{k}{k-h+1}$-competitiva.
2. Definición de algoritmos (conservadores) da resultado
similar para FIFO (que no es con marcas pero es
conservador).
4. En practica, sabemos que LRU es mucho mejor que FWF (for
instancia). Había mucha investigación para intentar de
mejorar la análisis por 20 anos, ahora parece que hay una
análisis que explica la mejor rendimiento de LRU sobre
FWF, y de variantes de LRU que pueden saber $x$ pasos en
el futuro (Reza Dorrigiv y Alex Lopez-Ortiz).
+ Conclusion Unidad 3
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
* Resultados de Aprendisajes de la Unidad
- Comprender las tecnicas de algoritmos de
- costo amortizado,
- uso de finitud, y
- algorimos competitivos
- Ser capaz de diseñar y analzar algoritmos y estructuras de
datos basados en estos principios.
- conocer algunos casos de estudio relevantes
* Principales casos de estudio:
- estructuras para union-find,
- colas binomiales
- splay trees,
- búsqueda por interpolacíon
- radix sort
- árboles de van Emde Boas
- árboles de sufijos
- técnica de los cuatro rusos,
- paginamiento
- búsqueda no acotada (unbounded search, doubling search)
- List Accessing
REFERENCIA: Capitulo 1 en "Online Computation and Competitive
Analysis", de Allan Borodin y Ran El-Yaniv
1) "List Accessing"
- Considera la secuencia de búsqueda de tamaño $n$, en un
diccionario de tamaño $\sigma$:
"1,1,1,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,..."
- Cual es el rendimiento de una estructura de diccionario
*estática* (tal que AVL) en este secuencia?
- $n\lg\sigma$
- Se puede mejorar?
- si, utilizando la *localidad* de las consultas, en
*estructuras de datos dinámicas*.
2) Soluciones
1. MTF ("Move To Front"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada en frente
2. TRANS ("Transpose"):
- pone las llaves en un arreglo desordenado
- buscas secuencialmente en el arreglo
- muda la llave encontrada de una posición mas cerca del frente
3. FC ("Frequency Count"):
- mantiene un contador para la frecuencia de cada elemento
- mantiene la lista ordenada para frecuencia decreciente.
4. Splay Trees (y otras estructuras con propiedades de localidad)
([www.dcc.uchile.cl/ ... tes/Diccionario/#8b])
3) Estos son "Algoritmos en Linea"
- algoritmo de optimización
- que conoce solamente una parte de la entrada al tiempo t.
- se compara a la competitividad con el algoritmo offline que
conoce toda la instancia.
- Como se puede medir su complejidad?
- cada algoritmo ejecuta O(n) comparaciones para cada
búsqueda en el peor caso!!!!
- tiene de considerar instancies "fáciles" y "difíciles"
- una medida de dificultad
- e.g. el rendimiento del *mejor algoritmo "offline"*
4) Competitive Analysis: instancias "difíciles" o "fáciles"
- Las estructuras de datos dinámicas pueden aprovechar de
secuencias "fáciles" de consultas: eso se llama "online".
- pero para muchos problemas online, todas las heurísticas se
comportan de la misma manera en el peor caso.
- Por eso se identifica una medida de dificultad de las
instancias, y se comparan los rendimientos de los
algoritmos sobre instancias que tienen una valor fijada de
este medida de dificultad.
- Tradicionalmente, esta medida de dificultad es el
rendimiento del mejor algoritmo "offline": eso se llama
*competitive analysis*, resultando en el *competitive
ratio*, el ratio entre la complejidad del algoritmo ONLINE
y la complejidad del mejor algoritmo OFFLINE.
- por ejemplo, veamos que MTF tiene un competitive ratio de
2
- Pero todavía hay algoritmos con performancia practicas muy
distintas que tienen el mismo competitive ratio. Por eso se
introduce otras medidas de dificultadas mas sofisticadas, y
mas especialidades en cada problema.
5) Competitividad
* Optimización/aproximación
- A es *k(n) competitiva* para un problema de *minimización* si
- \exist b, \forall n,x |x|=n
- C_A(x) - k(n) C_{OPT}(x) \leq b
- A es *k(n) competitiva* para un problema de *maximización* si
- \exist b, \forall n,x |x|=n
- C_{OPT}(x) - k(n) C_{A}(x) \leq b
* Competitiva Ratio
- an algoritmo en linea es *c-competitiva* si
- \exists \alpha, \forall I
- ALG(I) \leq c OPT(I) + \alpha
- an algoritmo en linea es *estrictamente c-competitiva* si
- \forall I
- ALG(I) \leq c OPT(I)
6) Sleator-Tarjan sobre MTF
- costo de una búsqueda negativa (la llave NO esta en el
diccionario)
- $\sigma$
- costo de una búsqueda positiva (la llave esta en el
diccionario)
- la posición de la llave, no mas que $\sigma$
- en promedio para una distribución de probabilidad fijada:
- $MTF \leq 2 OPT$,
- Prueba: (from my notes in my CS240 slides)
How does MTF compare to the optimal ordering?
- Assume that:
- the keys $k_1,\ldots,k_n$ have probabilities
$p_1 \ge p_2 \ge \ldots \ge p_n \ge 0$
- the list is used sufficiently to reach a steady state.
- Then:
$$C_{MTF} < 2\cdot C_{OPT}$$
- Proof:
\begin{eqnarray*}
C_{OPT} & = & \sum_{j=1}^{n} jp_j
C_{MTF} & = & \sum_{j=1}^{n} p_j(\mbox{cost of finding $k_j$})
& = & \sum_{j=1}^{n} p_j(1+\alert{\mbox{number of keys before } k_j})
\end{eqnarray*}
- To compute the average number of keys before $k_j$:
\begin{eqnarray*}
\Pr[\mbox{ $k_i$ before $k_j$}] &=& \frac{p_i}{p_i+p_j}
E(\mbox{ \alert{number of keys before $k_j$}}) &=&
\sum_{i\neq j} \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- $k_i$ is before $k_j$ if and only if
$k_i$ was accessed more recently than $k_j$.
- Consider the last time either $k_i$ or $k_j$ was looked up. What is the probability that it was $k_i$?
\begin{eqnarray*}
P(k_i \textrm{ before } k_j) &=
%& P(k_i \textrm{ chosen }|\ k_i \textrm{ or }k_j\textrm{ chosen }) \\ &=
& \frac{P(k_i \textrm{ chosen })}{P(k_i \textrm{ or } k_j \textrm{ chosen })}
&=& \frac{p_i}{p_i+p_j}
\end{eqnarray*}
- Therefore,
\begin{eqnarray*}
C_{MTF} & = & \sum_{j=1}^{n} p_j (1+\sum_{i\not = j} \frac{p_i}{p_i+p_j})
\mbox{\hspace{.5cm} (Joining both previous formulas.)}
& = & 1 + 2 \sum_{j=1}^n \sum_{i0 y S=
p_1^l,p_2^l,\ldots,p_{k-1}^l,(p_k,p_{k+1})^{l-1}
- Después de las (k-1)l primeras consultas, LFU va a tener
un miss cada consulta, cuando LFD solamente dos.
5. Que tal de FWF?
- MRU=LIFO es un poco estúpido, su mala rendimiento no es
una sorpresa.
- FWF es un algoritmo muy ingenuo también, pero vamos a
ver que no tiene un rendimiento tan mal "en teoría".
5) BONUS: Competive Analysis: Algoritmos a Marcas
1. $k$-fases particiones
Para cada secuencia $S$, partitionala en secuencias
$S_1,\ldots,S_\delta$ tal que
- $S_0 = \emptyset$
- $S_i$ es la secuencia Maxima después de $S_{i-1}$ que
contiene al máximum $k$ consultas distintas.
- Llamamos "fase $i$" el tiempo que el algoritmo considera
elementos de la subsecuencia $S_i$.
- Nota que eso es independiente del algoritmo considerado.
2. Algoritmo con marcas
- agrega a cada pagina de memoria lenta un bit de marca.
- al inicio de cada fase, remuda las marcas de cada
pagina en memoria.
- a dentro de una fase, marca una pagina la primera vez
que es consultada.
- un algoritmo a marca ("marking algorithm") es un
algoritmo que nunca remuda una pagina marcada de su
cache.
3. Un algoritmo con marcas es $k$-competitiva
- En cada fase,
- un algoritmo ONLINE con marcas performa al máximum $k$ miss.
- Un algoritmo OFFLINE (e.g. LFD) performa al mínimum
$1$ miss.
- QED
4. LRU, CLOCK y FWF son algoritmos con marcas
5. LRU, CLOCK y FWF tienen un ratio competitivo ÓPTIMO
6) Mas resultados:
1. La análisis se puede generalizar al caso donde el
algoritmo offline tiene h paginas, y el algoritmo online
tiene $k\geq h$ paginas.
- Cada algoritmo *con marcas* es
$\frac{k}{k-h+1}$-competitiva.
2. Definición de algoritmos (conservadores) da resultado
similar para FIFO (que no es con marcas pero es
conservador).
4. En practica, sabemos que LRU es mucho mejor que FWF (for
instancia). Había mucha investigación para intentar de
mejorar la análisis por 20 anos, ahora parece que hay una
análisis que explica la mejor rendimiento de LRU sobre
FWF, y de variantes de LRU que pueden saber $x$ pasos en
el futuro (Reza Dorrigiv y Alex Lopez-Ortiz).
+ Conclusion Unidad 3
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
* Resultados de Aprendisajes de la Unidad
- Comprender las tecnicas de algoritmos de
- costo amortizado,
- uso de finitud, y
- algorimos competitivos
- Ser capaz de diseñar y analzar algoritmos y estructuras de
datos basados en estos principios.
- conocer algunos casos de estudio relevantes
* Principales casos de estudio:
- estructuras para union-find,
- colas binomiales
- splay trees,
- búsqueda por interpolacíon
- radix sort
- árboles de van Emde Boas
- árboles de sufijos
- técnica de los cuatro rusos,
- paginamiento
- búsqueda no acotada (unbounded search, doubling search)
*Análisi amortizado* de algoritmos y estructuras de datos
2
Jérémy Barbay 7 Oct 201007/10/10 a las 13:38 hrs.2010-10-07 13:38:07
*Análisi amortizado* de algoritmos y estructuras de datos
=========================================================
Author: Jérémy Barbay
Date: 2010-10-07 17:36:41 XXX
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
Table of Contents
=================
1 Análisis amortizada
2 Colas de Prioridades
1 Análisis amortizada
~~~~~~~~~~~~~~~~~~~~~~
* Costo Amortizado:
- Se tiene una secuencia de n operaciones con costos
c1,c2,...,cn. Se quiere determinar C=\sum c_i.
- Se puede tomar el peor caso de ci\leq t para tener una
cota superior de C\leq t n.
- Un mejor análisis puede analizar el costo amortizado,
con varias técnicas:
- análisis agragada
- contabilidad de costos
- función potencial.
* Ejemplo simple: Incremento binario
- Incrementar n veces un numero binario de k bits,
- e.g. desde cero hasta 2^k-1, con n=2^k.
- costo \leq k n (brute force)
- costo \leq n + n/2 + ... \leq 2n (costo amortizado)
- La técnica usada aquí es la contabilidad de costos:
- un flip de 0 a 1 cuesta 2
- un flip de 1 a 0 cuesta 0
- cada incremento cuesta 2.
* Función Potencial para contar el costo
- \phi_0 = 0
- \phi_i es el tamaño de la bolsa luego de ejecutar c_1,\ldots,c_i
- \Delta \phi_i = \phi_i - \phi_{i-1}
- costo amortizado = \overline{c_i} = c_i + \Delta\phi_i
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0 \geq \sum c_i
- Ejemplo : la analisis del algoritmo para min y max al mismo tiempo.
* En el ejemplo de Incrementacion binaria:
- \phi = cantidad de unos en el numero
- \phi_0 = 0
- c_i = l+1 cuando hay l unos
- \Delta \phi_i = -l+1
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0
\geq 2
* Ejemplo: realocación amortizada
- considera el tipo "Vector" en Java.
- de tamaño fijo n
- cuando accede a n+1, crea un otro arreglo de tamaño 2n, y
copia todo.
- cual es el costo amortizado si agregando elementos uno a
uno?
2 Colas de Prioridades
~~~~~~~~~~~~~~~~~~~~~~~
* REFERENCIA: [www.leekillough.com/heaps/]
* Problema: Dado un conjunto (dinámica) de $n$ tareas con
valores, elegir y remudar la tarea de valor máxima.
* operaciones básicas:
- M.build({e1,e2,...,2n})
- M.insert(e)
- M.min
- M.deleteMin
* operaciones adicionales ("Addressable priority queues")
- M.insert(e), volviendo un puntero h ("handle") al elemento insertado
- M.remove(h), remudando el elemento especificado para h
- M.decreaseKey(h,k), reduciendo la llave del elemento especificado para h
- M.merge(Q), agregando el heap Q al heap M.
* Soluciones (conocidas o no):
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
1) Colas de prioridades binarias ("Binary Heaps")
* La solución tradicional
- un arreglo de n elementos
- hijos del nodo i en posiciones 2i y 2i+1
- la valor de cada nodo es mas pequeña que las valores de su hijos.
* Complejidad: Espacio n+O(1), y
Operación Tiempo
-------------------------+----------
M.build({e1,e2,...,2n}) O(n)
M.insert(e) O(\lg n)
M.min O(1)
M.deleteMin O(\lg n)
* Detalles de implementacion (mejorando las constantes)
- Cuidado de no implementar M.build({e1,e2,...,2n}) con n
inserciones (sift up -> O(n\lg n)), pero con n/2
sift-down (-> O(n)).
- En M.deleteMin(), algunas variantes de implementación
(después de cambiar el min con A[n]):
1. dos comparaciones en cada nivel hasta encontrar la
posición final de A[n]
- 2\lg n comparaciones en el peor caso
- \lg n copias
2. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda binaria para encontrar
la posición final
- \lg n + O(\lg \lg n) comparaciones en el peor caso
- \lg n copias en el peor caso
3. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda *secuencial* up para encontrar
la posición final
- 2\lg n comparaciones en el peor caso
- \lg n copias en el peor caso
- pero en practica y promedio mucho mejor.
* Flexibilidad de estructuras
+ Porque la complejidad es mejor con un heap que con un
arreglo ordenado?
- Para cada conjunto, hay solamente un arreglo ordenado
que puede representarlo, pero muchos heaps posibles:
eso da mas flexibilidad para la mantención dinámica de
la estructura de datos.
+ Colas de prioridades con punteros ("Addressable priority queues")
- Algún que mas flexible que los arreglos ordenados, las
colas de prioridades binarias todavía son de estructura
muy estricta, por ejemplo para la union de
filas. Estructuras mas flexibles consideran un "bosque"
de arboles. Además, estas estructuras de arboles son
implementadas con puntadores (en ves de implementarlos
en arreglos).
- Hay diferentes variantes. Todas tienen en común los
puntos siguientes:
- un puntero *minPtr* indica el nodo de valor mínima
en el bosque, raíz de alguno arbol.
- *insert* agregas un nuevo arbol al bosque en tiempo O(1)
- *deleteMin* remudas el nodo indicado par minPtr,
dividiendo su arbol en dos nuevos arboles. Buscamos
para el nuevo min y fusionamos algunos arboles (los
detalles diferencian las variantes)
- *decreaseKey(h,k)* es implementado cortando el arbol
al nodo indicado por h, y rebalanceando el arbol
cortado.
- *delete()* es reducido a *decreaseKey(h,0)* y
*deleteMin*
2) "Pairing Heaps"
- Malo rendimiento en el peor caso, pero bastante buena en
practica.
- rebalancea los arboles solamente en deleteMin, y solamente
con pares de raises (i.e. la cantidad de arboles es
reducida por dos a cada deleteMin).
Operación Amortizado
------------------+--------------------------
Insert(C,x) O(1)
Merge O(1)
ExtractMin O(lg n)
decreaseKey(h,k) \Omega(n \lg n \lg\lg n)
3) Colas de prioridades binomiales ("Binomial Heaps")
[en.wikipedia.org/wiki/Binomial_heap]
o p136 de Melhorn y Sanders
* Definición
- Un *arbol binomial* (de orden k) tiene exactamente $k$
hijos de orden distintos k-1,k-2,..., 0. [Un arbol
binomial de orden 0 tiene 0 hijos.]
- Un *bosque binomial* es un conjunto de arboles binomiales
de orden *distintas* (i.e. hay cero o uno arboles de cada
orden).
* Propiedades
- Para cada arbol T
- h(T) \leq lg |T|
- |T| \geq 2^{h(T)}
- Para el bosque
- \forall n hay solamente uno bosque binomial con n nodos.
- al máxima tiene $\lfloor \lg (n+1) \rfloor$ arboles.
- la descomposición del bosque en arboles de orden k
corresponde a la descomposición de n en base de dos.
* Definición
- una *cola binomial* es un bosque binomial donde cada nodo
almacena una clave, y siempre la clave de un padre es
inferior o igual a la clave de un hijo.
* Operaciones
Operación Peor Caso
------------------+-----------
Merge O(lg n)
FindMin O(lg n)
ExtractMin O(lg n)
Insert(C,x) O(lg n)
Heapify O(n)
------------------+-----------
remove(h) O(lg n)
decreaseKey(h,k) O(lg n)
merge(Q) O(lg n)
* Union
- Union de dos arboles binomiales de mismo orden:
- agrega T_2 a T_1 si T_1 tiene la raíz mas pequeña.
- Union de dos bosques binomiales:
- si hay uno arbol de orden k, es lo de la union
- si hay dos arboles de orden k, calcula la union en un arbol de orden k+1
- la propagación es similar a la suma de enteros en binario.
- Complejidad
- O(lg n) en el peor caso
* Insert
- agrega un arbol de orden 0 y hace la union si necesitado
- Complejidad O(log n) en el peor caso
- Puede ser O(1) sin corregir el bosque, que tiene de ser
corregido mas tarde, que puede ser en tiempo O(n) peor
caso, pero sera O(lg n) en tiempo amortizado.
* Mínima
- leí la lista de al máxima $\lfloor \lg (n+1) \rfloor$ raíces
- Complejidad O(lg n)
- Puede ser O(1) si precalculando un puntero al mínima, que
tiene de ser corregido (en tiempo O(\lg n)) a cada modificación.
* DeleteMin
- encontra el min
- remuda el min de su arbol (la raíz)
- reordena su hijos para su orden, en un bosque binomial
- hace la union con el bosque binomial original, menos el arbol del min
- complejidad O(lg n)
* DecreaseKey
- sigue el camino abajo hasta que la condición del heap es
corregida.
- cada arbol tiene altura lg n, entonces la complejidad es
O(lg n) en el peor caso.
* Delete
- reducido a DecreaseKey+DeleteMin
4) Colas de prioridades de Fibonacci ("Fibonacci Heaps")
[en.wikipedia.org/wiki/Fibonacci_heap] o pagina 135 de
Melhorn y Sanders.
* Diferencia con la cola binomial:
- relax la estructura de los arboles (heap-forma), pero de
forma controlada.
- el tamaño de un sub-arbol cual raíz tiene k hijos es al
máxima F_k+2, donde F_k es el k-ésimo numero de
Fibonacci.
* Operaciones
Operación Peor Caso Amortizado
------------------+-----------+------------
Merge O(lg n) O(1)
FindMin O(lg n) O(1)
ExtractMin O(lg n) .
Insert(C,x) O(lg n) O(1)
Heapify O(n) .
------------------+-----------+------------
remove(h) O(lg n) .
decreaseKey(h,k) O(lg n) O(1)
merge(Q) O(lg n) O(1)
5) Overview
(copy de [en.wikipedia.org/wiki/Fibonacci_heap])
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
6) BONUS Heapsort
- in place
- O(n lg n) con cualquiera de estas variantes.
=========================================================
Author: Jérémy Barbay
Date: 2010-10-07 17:36:41 XXX
SCHEDULED: <2010-10-07 Thu 12:00-13:30>
Table of Contents
=================
1 Análisis amortizada
2 Colas de Prioridades
1 Análisis amortizada
~~~~~~~~~~~~~~~~~~~~~~
* Costo Amortizado:
- Se tiene una secuencia de n operaciones con costos
c1,c2,...,cn. Se quiere determinar C=\sum c_i.
- Se puede tomar el peor caso de ci\leq t para tener una
cota superior de C\leq t n.
- Un mejor análisis puede analizar el costo amortizado,
con varias técnicas:
- análisis agragada
- contabilidad de costos
- función potencial.
* Ejemplo simple: Incremento binario
- Incrementar n veces un numero binario de k bits,
- e.g. desde cero hasta 2^k-1, con n=2^k.
- costo \leq k n (brute force)
- costo \leq n + n/2 + ... \leq 2n (costo amortizado)
- La técnica usada aquí es la contabilidad de costos:
- un flip de 0 a 1 cuesta 2
- un flip de 1 a 0 cuesta 0
- cada incremento cuesta 2.
* Función Potencial para contar el costo
- \phi_0 = 0
- \phi_i es el tamaño de la bolsa luego de ejecutar c_1,\ldots,c_i
- \Delta \phi_i = \phi_i - \phi_{i-1}
- costo amortizado = \overline{c_i} = c_i + \Delta\phi_i
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0 \geq \sum c_i
- Ejemplo : la analisis del algoritmo para min y max al mismo tiempo.
* En el ejemplo de Incrementacion binaria:
- \phi = cantidad de unos en el numero
- \phi_0 = 0
- c_i = l+1 cuando hay l unos
- \Delta \phi_i = -l+1
- \sum \overline{c_i} = \sum c_i + \phi_n -\phi_0
\geq 2
* Ejemplo: realocación amortizada
- considera el tipo "Vector" en Java.
- de tamaño fijo n
- cuando accede a n+1, crea un otro arreglo de tamaño 2n, y
copia todo.
- cual es el costo amortizado si agregando elementos uno a
uno?
2 Colas de Prioridades
~~~~~~~~~~~~~~~~~~~~~~~
* REFERENCIA: [www.leekillough.com/heaps/]
* Problema: Dado un conjunto (dinámica) de $n$ tareas con
valores, elegir y remudar la tarea de valor máxima.
* operaciones básicas:
- M.build({e1,e2,...,2n})
- M.insert(e)
- M.min
- M.deleteMin
* operaciones adicionales ("Addressable priority queues")
- M.insert(e), volviendo un puntero h ("handle") al elemento insertado
- M.remove(h), remudando el elemento especificado para h
- M.decreaseKey(h,k), reduciendo la llave del elemento especificado para h
- M.merge(Q), agregando el heap Q al heap M.
* Soluciones (conocidas o no):
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
1) Colas de prioridades binarias ("Binary Heaps")
* La solución tradicional
- un arreglo de n elementos
- hijos del nodo i en posiciones 2i y 2i+1
- la valor de cada nodo es mas pequeña que las valores de su hijos.
* Complejidad: Espacio n+O(1), y
Operación Tiempo
-------------------------+----------
M.build({e1,e2,...,2n}) O(n)
M.insert(e) O(\lg n)
M.min O(1)
M.deleteMin O(\lg n)
* Detalles de implementacion (mejorando las constantes)
- Cuidado de no implementar M.build({e1,e2,...,2n}) con n
inserciones (sift up -> O(n\lg n)), pero con n/2
sift-down (-> O(n)).
- En M.deleteMin(), algunas variantes de implementación
(después de cambiar el min con A[n]):
1. dos comparaciones en cada nivel hasta encontrar la
posición final de A[n]
- 2\lg n comparaciones en el peor caso
- \lg n copias
2. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda binaria para encontrar
la posición final
- \lg n + O(\lg \lg n) comparaciones en el peor caso
- \lg n copias en el peor caso
3. una comparación en cada nivel para definir un camino
de tamaño lg n, y una búsqueda *secuencial* up para encontrar
la posición final
- 2\lg n comparaciones en el peor caso
- \lg n copias en el peor caso
- pero en practica y promedio mucho mejor.
* Flexibilidad de estructuras
+ Porque la complejidad es mejor con un heap que con un
arreglo ordenado?
- Para cada conjunto, hay solamente un arreglo ordenado
que puede representarlo, pero muchos heaps posibles:
eso da mas flexibilidad para la mantención dinámica de
la estructura de datos.
+ Colas de prioridades con punteros ("Addressable priority queues")
- Algún que mas flexible que los arreglos ordenados, las
colas de prioridades binarias todavía son de estructura
muy estricta, por ejemplo para la union de
filas. Estructuras mas flexibles consideran un "bosque"
de arboles. Además, estas estructuras de arboles son
implementadas con puntadores (en ves de implementarlos
en arreglos).
- Hay diferentes variantes. Todas tienen en común los
puntos siguientes:
- un puntero *minPtr* indica el nodo de valor mínima
en el bosque, raíz de alguno arbol.
- *insert* agregas un nuevo arbol al bosque en tiempo O(1)
- *deleteMin* remudas el nodo indicado par minPtr,
dividiendo su arbol en dos nuevos arboles. Buscamos
para el nuevo min y fusionamos algunos arboles (los
detalles diferencian las variantes)
- *decreaseKey(h,k)* es implementado cortando el arbol
al nodo indicado por h, y rebalanceando el arbol
cortado.
- *delete()* es reducido a *decreaseKey(h,0)* y
*deleteMin*
2) "Pairing Heaps"
- Malo rendimiento en el peor caso, pero bastante buena en
practica.
- rebalancea los arboles solamente en deleteMin, y solamente
con pares de raises (i.e. la cantidad de arboles es
reducida por dos a cada deleteMin).
Operación Amortizado
------------------+--------------------------
Insert(C,x) O(1)
Merge O(1)
ExtractMin O(lg n)
decreaseKey(h,k) \Omega(n \lg n \lg\lg n)
3) Colas de prioridades binomiales ("Binomial Heaps")
[en.wikipedia.org/wiki/Binomial_heap]
o p136 de Melhorn y Sanders
* Definición
- Un *arbol binomial* (de orden k) tiene exactamente $k$
hijos de orden distintos k-1,k-2,..., 0. [Un arbol
binomial de orden 0 tiene 0 hijos.]
- Un *bosque binomial* es un conjunto de arboles binomiales
de orden *distintas* (i.e. hay cero o uno arboles de cada
orden).
* Propiedades
- Para cada arbol T
- h(T) \leq lg |T|
- |T| \geq 2^{h(T)}
- Para el bosque
- \forall n hay solamente uno bosque binomial con n nodos.
- al máxima tiene $\lfloor \lg (n+1) \rfloor$ arboles.
- la descomposición del bosque en arboles de orden k
corresponde a la descomposición de n en base de dos.
* Definición
- una *cola binomial* es un bosque binomial donde cada nodo
almacena una clave, y siempre la clave de un padre es
inferior o igual a la clave de un hijo.
* Operaciones
Operación Peor Caso
------------------+-----------
Merge O(lg n)
FindMin O(lg n)
ExtractMin O(lg n)
Insert(C,x) O(lg n)
Heapify O(n)
------------------+-----------
remove(h) O(lg n)
decreaseKey(h,k) O(lg n)
merge(Q) O(lg n)
* Union
- Union de dos arboles binomiales de mismo orden:
- agrega T_2 a T_1 si T_1 tiene la raíz mas pequeña.
- Union de dos bosques binomiales:
- si hay uno arbol de orden k, es lo de la union
- si hay dos arboles de orden k, calcula la union en un arbol de orden k+1
- la propagación es similar a la suma de enteros en binario.
- Complejidad
- O(lg n) en el peor caso
* Insert
- agrega un arbol de orden 0 y hace la union si necesitado
- Complejidad O(log n) en el peor caso
- Puede ser O(1) sin corregir el bosque, que tiene de ser
corregido mas tarde, que puede ser en tiempo O(n) peor
caso, pero sera O(lg n) en tiempo amortizado.
* Mínima
- leí la lista de al máxima $\lfloor \lg (n+1) \rfloor$ raíces
- Complejidad O(lg n)
- Puede ser O(1) si precalculando un puntero al mínima, que
tiene de ser corregido (en tiempo O(\lg n)) a cada modificación.
* DeleteMin
- encontra el min
- remuda el min de su arbol (la raíz)
- reordena su hijos para su orden, en un bosque binomial
- hace la union con el bosque binomial original, menos el arbol del min
- complejidad O(lg n)
* DecreaseKey
- sigue el camino abajo hasta que la condición del heap es
corregida.
- cada arbol tiene altura lg n, entonces la complejidad es
O(lg n) en el peor caso.
* Delete
- reducido a DecreaseKey+DeleteMin
4) Colas de prioridades de Fibonacci ("Fibonacci Heaps")
[en.wikipedia.org/wiki/Fibonacci_heap] o pagina 135 de
Melhorn y Sanders.
* Diferencia con la cola binomial:
- relax la estructura de los arboles (heap-forma), pero de
forma controlada.
- el tamaño de un sub-arbol cual raíz tiene k hijos es al
máxima F_k+2, donde F_k es el k-ésimo numero de
Fibonacci.
* Operaciones
Operación Peor Caso Amortizado
------------------+-----------+------------
Merge O(lg n) O(1)
FindMin O(lg n) O(1)
ExtractMin O(lg n) .
Insert(C,x) O(lg n) O(1)
Heapify O(n) .
------------------+-----------+------------
remove(h) O(lg n) .
decreaseKey(h,k) O(lg n) O(1)
merge(Q) O(lg n) O(1)
5) Overview
(copy de [en.wikipedia.org/wiki/Fibonacci_heap])
Linked List Binary Tree (Min-)Heap Fibonacci Heap Brodal Queue [1]
-------------+-------------+---------------+---------------+----------------+------------------
insert O(1) O(log n) O(log n) O(1) O(1)
accessmin O(n) O(1) O(1) O(1) O(1)
deletemin O(n) O(log n) O(log n) O(log n)* O(log n)
decreasekey O(1) O(log n) O(log n) O(1)* O(1)
delete O(n) O(n) O(log n) O(log n)* O(log n)
merge O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)
6) BONUS Heapsort
- in place
- O(n lg n) con cualquiera de estas variantes.
Algoritmos de Ordenamiento ( Counting Sort, Bucket sort, radix sort, string sort
3
Jérémy Barbay 5 Oct 201005/10/10 a las 17:17 hrs.2010-10-05 17:17:05
Algoritmos de Ordenamiento ( Counting Sort, Bucket sort, radix sort, string sort)
=================================================================================
Author: Jérémy Barbay
Date: 2010-10-05 20:47:32 XXX
SCHEDULED: <2010-10-05 Tue 12:00-13:30>
Table of Contents
=================
1 Counting Sort O(\sigma + n)
2 Bucket Sort O(\sigma+n)
3 Radix Sort O(n \lg_n \sigma) = O(c n)
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
5 BONUS String Sort
1 Counting Sort O(\sigma + n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. p<-1
4. for j=1 to \sigma do
- for i=1 to C[j] do
- A[p++] <- j
Este algoritmo es bueno para ordenar multi conjuntos (donde
cada elementos puede ser presente muchas veces), pero pobre
para diccionarios, para cual es mejor usar la extensión
lógica, Bucket Sort.
2 Bucket Sort O(\sigma+n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. P[1] <- 1
4. for j<- 2 to \sigma do
- P[j] <- P[j-1] + C[j-1]
5. for i<-1 to n
- B[P[A[i]]++] <- A[i]
Este algoritmo es particularmente practica para ordenar
llaves asociadas con objetos, donde dos llaves pueden ser
asociadas con algunas valores distintas. Nota que el
ordenamiento es *estable*.
3 Radix Sort O(n \lg_n \sigma) = O(c n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Considera un arreglo A de tamaño n sobre alfabeto $\sigma$
- si $\sigma=n$, se recuerdan que bucket sort puede
ordenar A en O(n)
- si $\sigma=n^2$, bucket sort puede ordenar A en O(n):
- 1 ves con los $\lg n$ bits de la derecha
- 1 ves con los $\lg n$ bits de la izquierda
(utilizando la estabilidad de bucket sort)
- si $|A|=n^c$, bucket sort puede ordenar A
- en tiempo $O(cn)$
- con espacio 2n + \sigma \approx 3n
(\sigma \approx n a cada iteración de bucket sort)
El espacio se puede reducir a 2n+\sqrt{n} con \lg n/ 2
bits a cada iteración de Bucketsort, cambiando la
complejidad solamente por un factor de 2.
En final, si $A$ es de tamaño $n$ sobre un alfabeto de
tamaño $\sigma$, radix sort puede ordenar $A$ en tiempo
O( n \lceil \frac{\lg \sigma}{\lg n}\rceil )
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Se puede o no?
- Ordenar en $n H_i$ comparaciones
5 BONUS String Sort
~~~~~~~~~~~~~~~~~~~~
+ Problema: Ordenar $k$ strings sobre alfabeto [\sigma], de
largo total n=\sum n_i.
+ Si \sigma \leq k, y cada string es de mismo tamaño.
- Si utilizamos bucket-sort de la derecha a la izquierda,
podemos ordenar en tiempo $O(n)$, porque O(n \lceil \lg
\sigma/\lg l \rceil ) y \sigma<n.
+ Si \sigma \in O(1)
- Radix Sort sobre $c$ simboles, donde $c$ es el tamaño
mínima de una string, y iterar recursivamente sobre el
restos de la strings mas grande con mismo prefijo.
- En el peor caso, la complejidad corresponde a la suma de
las superficias de los bloques, aka O(n).
[1] FOOTNOTE DEFINITION NOT FOUND: 1
=================================================================================
Author: Jérémy Barbay
Date: 2010-10-05 20:47:32 XXX
SCHEDULED: <2010-10-05 Tue 12:00-13:30>
Table of Contents
=================
1 Counting Sort O(\sigma + n)
2 Bucket Sort O(\sigma+n)
3 Radix Sort O(n \lg_n \sigma) = O(c n)
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
5 BONUS String Sort
1 Counting Sort O(\sigma + n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. p<-1
4. for j=1 to \sigma do
- for i=1 to C[j] do
- A[p++] <- j
Este algoritmo es bueno para ordenar multi conjuntos (donde
cada elementos puede ser presente muchas veces), pero pobre
para diccionarios, para cual es mejor usar la extensión
lógica, Bucket Sort.
2 Bucket Sort O(\sigma+n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. for j=1 to \sigma do C[j] <- 0
2. for i=1 to n do C[A[i]]++
3. P[1] <- 1
4. for j<- 2 to \sigma do
- P[j] <- P[j-1] + C[j-1]
5. for i<-1 to n
- B[P[A[i]]++] <- A[i]
Este algoritmo es particularmente practica para ordenar
llaves asociadas con objetos, donde dos llaves pueden ser
asociadas con algunas valores distintas. Nota que el
ordenamiento es *estable*.
3 Radix Sort O(n \lg_n \sigma) = O(c n)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Considera un arreglo A de tamaño n sobre alfabeto $\sigma$
- si $\sigma=n$, se recuerdan que bucket sort puede
ordenar A en O(n)
- si $\sigma=n^2$, bucket sort puede ordenar A en O(n):
- 1 ves con los $\lg n$ bits de la derecha
- 1 ves con los $\lg n$ bits de la izquierda
(utilizando la estabilidad de bucket sort)
- si $|A|=n^c$, bucket sort puede ordenar A
- en tiempo $O(cn)$
- con espacio 2n + \sigma \approx 3n
(\sigma \approx n a cada iteración de bucket sort)
El espacio se puede reducir a 2n+\sqrt{n} con \lg n/ 2
bits a cada iteración de Bucketsort, cambiando la
complejidad solamente por un factor de 2.
En final, si $A$ es de tamaño $n$ sobre un alfabeto de
tamaño $\sigma$, radix sort puede ordenar $A$ en tiempo
O( n \lceil \frac{\lg \sigma}{\lg n}\rceil )
4 BONUS Prevechando de las repeticiones en el modelo de Comparaciones
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- Se puede o no?
- Ordenar en $n H_i$ comparaciones
5 BONUS String Sort
~~~~~~~~~~~~~~~~~~~~
+ Problema: Ordenar $k$ strings sobre alfabeto [\sigma], de
largo total n=\sum n_i.
+ Si \sigma \leq k, y cada string es de mismo tamaño.
- Si utilizamos bucket-sort de la derecha a la izquierda,
podemos ordenar en tiempo $O(n)$, porque O(n \lceil \lg
\sigma/\lg l \rceil ) y \sigma<n.
+ Si \sigma \in O(1)
- Radix Sort sobre $c$ simboles, donde $c$ es el tamaño
mínima de una string, y iterar recursivamente sobre el
restos de la strings mas grande con mismo prefijo.
- En el peor caso, la complejidad corresponde a la suma de
las superficias de los bloques, aka O(n).
[1] FOOTNOTE DEFINITION NOT FOUND: 1
Hashing
Jérémy Barbay 30 Sep 201030/09/10 a las 15:19 hrs.2010-09-30 15:19:30
Hashing
=======
Author: Jérémy Barbay
Date: 2010-09-30 19:17:05 XXX
SCHEDULED: <2010-09-30 Thu 12:00-13:30>
Table of Contents
=================
1 Introduccion
2 Hashing Abierto
3 Hashing Cerrado
4 Universal Hashing
5 Hashing en memoria externa
1 Introduccion
~~~~~~~~~~~~~~~
* Motivaciones
- Mejor tiempo *en promedio*
- Uso de todos la herramientas que tenemos
- dominio de las valores
- distribuciones de probabilidades de las valores
* Terminologia
- Tabla de Hash
- Arreglo de tamaño $N$
- que contiene $n$ elementos a dentro de un universo [1..U]
- Funccion de Hash $h(K)$
- $h:[1..U] \rightarrow [0..N-1]$
- se calcula rapidamente
- distribue uniformemente (mas o menos) las llaves en la tabla
en el caso ideal, $P[h(K)=i] = 1/N, \, \forall K,i$
- Collision
- cuando $h(K_{1))= h(K_{2})$
- la probabilidad es alta: "Paradoxe del cumpleanos"
- Cual es la probabilidad que en una pieca de $n$ personas,
dos tiene la misma fecha de cumpleaños (a dentro de $365$
dias)?
- probabilidad que cada cumpleaños es unico:
$ 364! \over {(365 - n)!} \over { 365^{n-1} }$
- Probabilidad que hay al menos un cumpleanos compartido:
$ 1 - 364! \over {(365 - n)!} \over { 365^{n-1} }$
n Proba
-----+----------
10 .12
23 .5
50 .97
100 .9999996
2 Hashing Abierto
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisions con caldenas
2) Ejemplo: (muy irealistico)
- h(K) = K mod 10
- Secuencia de insercion 52,18,70,22,44,38,62
- Insertando al final (si hay que probar por repeticiones)
0 70
1
2 52,22,62
3
4 44
5
6
7
8 18,38
9
- Insertando al final (si no hay que probar por repeticiones)
0 70
1
2 62,22,52
3
4 44
5
6
7
8 38,18
9
3) Analisis:
- factor de carga es $\lambda= {n \over N}$
- Rendimiento en el peor caso: $\Oh(n)$
3 Hashing Cerrado
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisiones con busqueda, i.e.
- ( h(K)+f(i) ) mod N
- differentes tipos de busqueda:
- lineal f(i) = i
- primary "clustering" (formacion de secuencias largas)
- cuadratica f(i) = i^2
- secundario "clustering" (si h(K_1)=h(K2), la
secuencias son las mismas.
- doble hashing f(i) = i . h'(K)
- h'(K) debe ser prima con N
2) Ideal Hashing
- Imagina una funcion de hash que genera una secuencia que
parece aleatoria.
- cada posicion tiene la misma probabilidad de ser la
proxima
- Probabilidad $\lambda$ de elegir una posicion ocupada
- Probabilidad $1-\lambda$ de elegir une posicion libre
- OJO! la secuencia de prueba puede tocar la misma
posicion mas que una vez.
- OJO! llaves identicas todavia siguen la misma
secuencia.
- Cual es el costo promedio $u_j$ de una busqueda negativa
con $j$ llaves en la tabla?
- $\lambda= \frac{j}{N}$
- $u_j = 1 (1-\lambda) + 2\lambda(1-\lambda)+r\lambda^2(1-\lambda)+....$
- = 1 + \lambda + \lambda^2 + ...
- = \frac{1}{1-\lambda}
- = \frac{1}{1-j/N}
- = \frac{N}{N-j} \in[1..N]
- Cual es el costo promedio de una busqueda positiva $s_i$
para el $i$-th elemento insertado?
- $s_i = \frac{1}{1- i/N} = \frac{N}{N-i}$
- $s_n = 1/n \sum \frac{N}{N-i} $
- = \frac{N}{n} \sum_{i=0}^{n-1} \frac{1}{N-i}
- = \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{N-i}
con $\alpha = \frac{n}{N}$
- < \frac{1}{\alpha} \integral_{N-n}^{N} 1/x dx
- = 1/\alpha \ln\frac{N}{N-n}
- = 1/\alpha \ln\frac{1}{\alpha}
- Para $\alpha = 1/2$, el costo promedio es $1.387$
- Para $\alpha = 0.9$, el costo promedio es $2.559
4 Universal Hashing
~~~~~~~~~~~~~~~~~~~~
- h(K) = ( (aK+b) mod p) mod N
- a \in [1..p-1] elegido al azar
- b \in [0..p-1] elegido al azar
- p es primo y mas grande que N
- N no es necesaramente primo
5 Hashing en memoria externa
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Que pasa si la tabla de hashing no queda en memoria?
- IDEA: Simula un B-arbol de altura dos
- organiza el dato con valores de hash
- guarda un index en el nodo raiz
- usa solamente *una parte* de la valor de hash para elegir
el sobre-arbol
- extiende el index cuando mas dato es agregado
2) Descripción
- B - cantidad de elementos en una pagina
- h - funcion de hash -> [0..2^k-1]
- D - *profundidad general*, con D\leq k
- la raiz tiene $2^D$ punteros a las paginas horas
- la raiz es indexada con los $D$ primeros bits de cada
valor de hash.
- $d_l$ - *profundidad local* de cada hora $l$
- Las valores de hash en $l$ tienen en comun los primeros
$d_l$ bits.
- Hay $2^{D-d_l}$ punteros a la hora $l$
- Siempre, $d_l\leq D$
3) Ejemplo
- $B=4, k=6, D=2$
$d_l=2$ 000100
001000
001011
001100
$d_l=2$ 010101
011100
$d_l=1$ 100100
101101
110001
111100
4) Algoritmos
- Buscar
- Insertar
- Remover
5) Analisis
- Buscar, insertar remover
- 1 acceso a la memoria secundariaa si el index se queda
- cantidad Promedio de paginas para tener $n$ llaves
- $\frac{n}{B\lg 2}\approx 1.44 \frac{n}{B}$
- paginas son llenas a 69% mas o menos.
=======
Author: Jérémy Barbay
Date: 2010-09-30 19:17:05 XXX
SCHEDULED: <2010-09-30 Thu 12:00-13:30>
Table of Contents
=================
1 Introduccion
2 Hashing Abierto
3 Hashing Cerrado
4 Universal Hashing
5 Hashing en memoria externa
1 Introduccion
~~~~~~~~~~~~~~~
* Motivaciones
- Mejor tiempo *en promedio*
- Uso de todos la herramientas que tenemos
- dominio de las valores
- distribuciones de probabilidades de las valores
* Terminologia
- Tabla de Hash
- Arreglo de tamaño $N$
- que contiene $n$ elementos a dentro de un universo [1..U]
- Funccion de Hash $h(K)$
- $h:[1..U] \rightarrow [0..N-1]$
- se calcula rapidamente
- distribue uniformemente (mas o menos) las llaves en la tabla
en el caso ideal, $P[h(K)=i] = 1/N, \, \forall K,i$
- Collision
- cuando $h(K_{1))= h(K_{2})$
- la probabilidad es alta: "Paradoxe del cumpleanos"
- Cual es la probabilidad que en una pieca de $n$ personas,
dos tiene la misma fecha de cumpleaños (a dentro de $365$
dias)?
- probabilidad que cada cumpleaños es unico:
$ 364! \over {(365 - n)!} \over { 365^{n-1} }$
- Probabilidad que hay al menos un cumpleanos compartido:
$ 1 - 364! \over {(365 - n)!} \over { 365^{n-1} }$
n Proba
-----+----------
10 .12
23 .5
50 .97
100 .9999996
2 Hashing Abierto
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisions con caldenas
2) Ejemplo: (muy irealistico)
- h(K) = K mod 10
- Secuencia de insercion 52,18,70,22,44,38,62
- Insertando al final (si hay que probar por repeticiones)
0 70
1
2 52,22,62
3
4 44
5
6
7
8 18,38
9
- Insertando al final (si no hay que probar por repeticiones)
0 70
1
2 62,22,52
3
4 44
5
6
7
8 38,18
9
3) Analisis:
- factor de carga es $\lambda= {n \over N}$
- Rendimiento en el peor caso: $\Oh(n)$
3 Hashing Cerrado
~~~~~~~~~~~~~~~~~~
1) Idea principal:
- resolver las colisiones con busqueda, i.e.
- ( h(K)+f(i) ) mod N
- differentes tipos de busqueda:
- lineal f(i) = i
- primary "clustering" (formacion de secuencias largas)
- cuadratica f(i) = i^2
- secundario "clustering" (si h(K_1)=h(K2), la
secuencias son las mismas.
- doble hashing f(i) = i . h'(K)
- h'(K) debe ser prima con N
2) Ideal Hashing
- Imagina una funcion de hash que genera una secuencia que
parece aleatoria.
- cada posicion tiene la misma probabilidad de ser la
proxima
- Probabilidad $\lambda$ de elegir una posicion ocupada
- Probabilidad $1-\lambda$ de elegir une posicion libre
- OJO! la secuencia de prueba puede tocar la misma
posicion mas que una vez.
- OJO! llaves identicas todavia siguen la misma
secuencia.
- Cual es el costo promedio $u_j$ de una busqueda negativa
con $j$ llaves en la tabla?
- $\lambda= \frac{j}{N}$
- $u_j = 1 (1-\lambda) + 2\lambda(1-\lambda)+r\lambda^2(1-\lambda)+....$
- = 1 + \lambda + \lambda^2 + ...
- = \frac{1}{1-\lambda}
- = \frac{1}{1-j/N}
- = \frac{N}{N-j} \in[1..N]
- Cual es el costo promedio de una busqueda positiva $s_i$
para el $i$-th elemento insertado?
- $s_i = \frac{1}{1- i/N} = \frac{N}{N-i}$
- $s_n = 1/n \sum \frac{N}{N-i} $
- = \frac{N}{n} \sum_{i=0}^{n-1} \frac{1}{N-i}
- = \frac{1}{\alpha} \sum_{i=0}^{n-1} \frac{1}{N-i}
con $\alpha = \frac{n}{N}$
- < \frac{1}{\alpha} \integral_{N-n}^{N} 1/x dx
- = 1/\alpha \ln\frac{N}{N-n}
- = 1/\alpha \ln\frac{1}{\alpha}
- Para $\alpha = 1/2$, el costo promedio es $1.387$
- Para $\alpha = 0.9$, el costo promedio es $2.559
4 Universal Hashing
~~~~~~~~~~~~~~~~~~~~
- h(K) = ( (aK+b) mod p) mod N
- a \in [1..p-1] elegido al azar
- b \in [0..p-1] elegido al azar
- p es primo y mas grande que N
- N no es necesaramente primo
5 Hashing en memoria externa
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Que pasa si la tabla de hashing no queda en memoria?
- IDEA: Simula un B-arbol de altura dos
- organiza el dato con valores de hash
- guarda un index en el nodo raiz
- usa solamente *una parte* de la valor de hash para elegir
el sobre-arbol
- extiende el index cuando mas dato es agregado
2) Descripción
- B - cantidad de elementos en una pagina
- h - funcion de hash -> [0..2^k-1]
- D - *profundidad general*, con D\leq k
- la raiz tiene $2^D$ punteros a las paginas horas
- la raiz es indexada con los $D$ primeros bits de cada
valor de hash.
- $d_l$ - *profundidad local* de cada hora $l$
- Las valores de hash en $l$ tienen en comun los primeros
$d_l$ bits.
- Hay $2^{D-d_l}$ punteros a la hora $l$
- Siempre, $d_l\leq D$
3) Ejemplo
- $B=4, k=6, D=2$
$d_l=2$ 000100
001000
001011
001100
$d_l=2$ 010101
011100
$d_l=1$ 100100
101101
110001
111100
4) Algoritmos
- Buscar
- Insertar
- Remover
5) Analisis
- Buscar, insertar remover
- 1 acceso a la memoria secundariaa si el index se queda
- cantidad Promedio de paginas para tener $n$ llaves
- $\frac{n}{B\lg 2}\approx 1.44 \frac{n}{B}$
- paginas son llenas a 69% mas o menos.
Algorimos de Busqueda (Interpolation Search, Extrapolation Search)
Jérémy Barbay 21 Sep 201021/09/10 a las 14:04 hrs.2010-09-21 14:04:21
Algorimos de Busqueda (Interpolation Search, Extrapolation Search)
==================================================================
1) Interpolacion
1. Introduccion:
- Hagaria busqueda binaria en un anuario telefonico para
el nombre "Barbay"? En un diccionario para la ciudad
"Zanzibar"?
- ojala que no: se puede provechar de la informacion
que da la primera letra de cada palabra
2. Algoritmo
- Interaccion
3. Analisis
* La analisis *en promedio* es complicada: conversamos
solamente la intuicion matematica (para mas ver la
publicacion cientifica de SODA04, Demaine Jones y
Patrascu):
- si las llaves son *distribuidas uniformamente*, la
distancia en promedio de la posicion calculada por
interpolacion *lineal* hasta la posicion real es de
$\sqrt{r-l}$.
- entonces, se puede reducir el tamaño del subarreglo
de $n$ a $\sqrt{n}$ cada (dos) comparaciones
- la busqueda por interpolacion
- en promedio,
- si las llaves son *distribuidas uniformamente*,
- toma $O(\lg \lg n)$ comparaciones
* La analisis *en el peor caso*
- Interaccion.
4. Variantas
1. Interpolacion non-lineal
- en un anuario telefonico o en un diccionario, las
frecuencias de las letras *no* son uniformes
2. Busqueda por Interpolacion Mixta con Binaria
- Se puede buscar en tiempo
- $O(\lg n)$ en el peor caso Y
- $O(\lg \lg n)$ en el caso promedio?
- Solucion facil
- Solucion mas compleja
3. Busqueda por Extrapolacion
- Tarea 3
4. Busqueda por Extrapolacion Mixta con Doblada
- Tarea 3
3) Discussion:
- Porque todavia estudiar la complejidad en el modelo de comparaciones?
- Cuando el peor caso es importante
- Cuando la distribucion no es uniforme o no es conocida
- cuando el costo de la evaluacion es mas costo que una
simple comparacion (en particular para la interpolacion
non lineal)
==================================================================
1) Interpolacion
1. Introduccion:
- Hagaria busqueda binaria en un anuario telefonico para
el nombre "Barbay"? En un diccionario para la ciudad
"Zanzibar"?
- ojala que no: se puede provechar de la informacion
que da la primera letra de cada palabra
2. Algoritmo
- Interaccion
3. Analisis
* La analisis *en promedio* es complicada: conversamos
solamente la intuicion matematica (para mas ver la
publicacion cientifica de SODA04, Demaine Jones y
Patrascu):
- si las llaves son *distribuidas uniformamente*, la
distancia en promedio de la posicion calculada por
interpolacion *lineal* hasta la posicion real es de
$\sqrt{r-l}$.
- entonces, se puede reducir el tamaño del subarreglo
de $n$ a $\sqrt{n}$ cada (dos) comparaciones
- la busqueda por interpolacion
- en promedio,
- si las llaves son *distribuidas uniformamente*,
- toma $O(\lg \lg n)$ comparaciones
* La analisis *en el peor caso*
- Interaccion.
4. Variantas
1. Interpolacion non-lineal
- en un anuario telefonico o en un diccionario, las
frecuencias de las letras *no* son uniformes
2. Busqueda por Interpolacion Mixta con Binaria
- Se puede buscar en tiempo
- $O(\lg n)$ en el peor caso Y
- $O(\lg \lg n)$ en el caso promedio?
- Solucion facil
- Solucion mas compleja
3. Busqueda por Extrapolacion
- Tarea 3
4. Busqueda por Extrapolacion Mixta con Doblada
- Tarea 3
3) Discussion:
- Porque todavia estudiar la complejidad en el modelo de comparaciones?
- Cuando el peor caso es importante
- Cuando la distribucion no es uniforme o no es conocida
- cuando el costo de la evaluacion es mas costo que una
simple comparacion (en particular para la interpolacion
non lineal)
2010-09-09 WrapUp Memoria Secundaria
1
Jérémy Barbay 9 Sep 201009/09/10 a las 15:42 hrs.2010-09-09 15:42:09
- Fecha de Auxiliar
- Lunes [2010-09-20 Mon] es feriado
- Gente (en el curso) no quieren en la semana.
- UCursos foro al menos.
- Fecha (y scope) de Control 1
- resumen de memoria secundaria
- Descripcion de la Tarea 2
- Lunes [2010-09-20 Mon] es feriado
- Gente (en el curso) no quieren en la semana.
- UCursos foro al menos.
- Fecha (y scope) de Control 1
- resumen de memoria secundaria
- Descripcion de la Tarea 2
