Ordenamiento en memoria secundaria 1
Jérémy Barbay 7 Sep 201007/09/10 a las 10:23 hrs.2010-09-07 10:23:07
[EDIT: UCursos tiene problemas con el LaTeX de mis apuntes. Publique en el material Docente una version pdf de estas apuntes (Seccion "Apuntes "Imprimidas"): www.u-cursos.cl/ ... ocente/objeto/315338 ]
2.2 Ordenamiento en memoria secundaria: Mergesort. Cota inferior.
======================================================================
1. Un modelo mas fino
1) Cuantos paginas quedan en memoria local?
- no tan importante para busqueda
- muy importante para applicaciones de computacion con mucho
datos.
2) Nuevas notaciones
- B = Tamano pagina
- N = cantidad de elementos en total
- n = cantidad de paginas con elementos = N/B
- M = cantidad de memoria local
- m = cantidad de paginas locales = M/B
- mnemotechnique:
- N,M,B en # palabras maquinas (=bytes?)
- n,m en # paginas
- n< kB )
* para Ordenar
(corrige y adapte la prueba de [www.daimi.au.dk/~large/ioS06/Alower.pdf] )
- en modelo RAM de comparaciones
- n \lg n
- en modelo Memoria Externa con n/B paginas de tamaño B
* \Omega( N/B \frac{ \lg(N/B) }{ \lg(M/B) } )
* que se puede notar mas simplamente \Omega( n\lg_m n )
- Prueba:
* en vez de considerar el problema de ordenamiento,
supponga que el arregla sea una permutacion y
considera el problema (equivalente en ese caso) de
identificar cual permutacion sea.
* inicialemente, pueden ser n! permutaciones.
- supponga que cada bloque de B elementos sea ya
ordenado (impliqua un costo de al maximo n=N/B
accessos a la memoria externa).
- queda N! / ( n \times (B!) ) permutaciones
posibles.
* para cada accesso a una pagina de memoria externo,
cuantos permutaciones potenciales podemos eliminar?
- con M entradas en memoria primaria
- B nuevas entradas se pueden quedar de \choose{M}{B}
= \frac{M!}{B!(M-B)!} maneras distintas
- calcular la union de los M+B elementos reduce la
cuantidad de permtuaciones por un factor de
1 / \choose{M}{B}
- despues de t accessos (distintos) a la memoria
externa, se reduci la cuantidad de permutaciones a
N! / ( n \times (B!) ( \choose{M}{B} )^t )
* cuanto accessos a la memoria sean necesarios para que
queda al maximo una permutacion?
- N! / ( n \times (B!) ( \choose{M}{B} )^t ) debe ser al maximo uno.
- usamos las formulas siguientes:
- \log(x!) \approx x\log x
- \log \choose{M}{B} \approx B \lg \frac{M}{B}
N! \leq n (B!) (\choose{M}{B})^t
---------+-------------+---------------------------------
N \lg N \leq n B \lg B + t B \lg \frac{M}{B}
---------+-------------+---------------------------------
t \geq \frac { N\lg N - nB \lg B }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { N \lg(N/B) }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { n \lg n }
{ \lg m }
---------+-------------+---------------------------------
\geq n \log_m n
* BONUS: Para ordenar strings, un caso particular (donde la
comparacion de dos elementos tiene un costo variable):
[www.brics.dk/ ... rs/stringsstoc97.pdf]
- \Omega( N_1/B \log_{M/B}(N_1/B) + K_2 \lg_{M/B} K_2 + N/B )
- donde
- N_1 es la suma de los tamanos de las caldenas mas cortas que B
- K_2 es la cuantidad de caldenas mas largas que B
3. Ordenar en Memoria Externa N elementos (en n=N/B paginas)
[en.wikipedia.org/wiki/External_sorting]
* Usando dictionarios o colas de prioridades en memoria externa
- N \lg N / \lg B = N \log_B N
- No es "tight" con la cota inferior
- impliqua
- o que hay un mejor algoritmo
- o que hay una mejor cota inferior
* Queda un algoritmo de ordenamiento: MergeSort
- usa la fusion de $m-1$ arreglos ordenados en memoria
externa:
1) carga en memoria principal $m-1$ paginas, cada una la
primera de su arreglo.
2) calcula la union de estas paginas en la pagina $m$ de
memoria principal,
- botando la pagina cuando llena
- cargando una nueva pagina (del mismo arreglo) cuando
vacilla
3) La complejidad es $n$ accessos.
- Algoritmo:
1) ordena cada de las $n$ paginas -> $n$ accessos
2) Cada nodo calcula la union de $m$ arreglos y escribe su
resultado, pagina por pagina, en la memoria
externa.
- Analisis:
- Cada nivel de recurencia costa $n$ accessos
- Cada nivel reduce por $m-1$ la cantidad de arreglos
- la complejidad total es de orden $n\log_m n$ accessos. (tight)
4. *BONUS* Ahora, cual es la cota inferior para una cola de
prioridad?
- una cola de prioridad se puede usar para ordenar (con $N$ accessos)
- hay una cota inferior para ordernar de $n \log_m n$
- entonces????
2.2 Ordenamiento en memoria secundaria: Mergesort. Cota inferior.
======================================================================
1. Un modelo mas fino
1) Cuantos paginas quedan en memoria local?
- no tan importante para busqueda
- muy importante para applicaciones de computacion con mucho
datos.
2) Nuevas notaciones
- B = Tamano pagina
- N = cantidad de elementos en total
- n = cantidad de paginas con elementos = N/B
- M = cantidad de memoria local
- m = cantidad de paginas locales = M/B
- mnemotechnique:
- N,M,B en # palabras maquinas (=bytes?)
- n,m en # paginas
- n< kB )
* para Ordenar
(corrige y adapte la prueba de [www.daimi.au.dk/~large/ioS06/Alower.pdf] )
- en modelo RAM de comparaciones
- n \lg n
- en modelo Memoria Externa con n/B paginas de tamaño B
* \Omega( N/B \frac{ \lg(N/B) }{ \lg(M/B) } )
* que se puede notar mas simplamente \Omega( n\lg_m n )
- Prueba:
* en vez de considerar el problema de ordenamiento,
supponga que el arregla sea una permutacion y
considera el problema (equivalente en ese caso) de
identificar cual permutacion sea.
* inicialemente, pueden ser n! permutaciones.
- supponga que cada bloque de B elementos sea ya
ordenado (impliqua un costo de al maximo n=N/B
accessos a la memoria externa).
- queda N! / ( n \times (B!) ) permutaciones
posibles.
* para cada accesso a una pagina de memoria externo,
cuantos permutaciones potenciales podemos eliminar?
- con M entradas en memoria primaria
- B nuevas entradas se pueden quedar de \choose{M}{B}
= \frac{M!}{B!(M-B)!} maneras distintas
- calcular la union de los M+B elementos reduce la
cuantidad de permtuaciones por un factor de
1 / \choose{M}{B}
- despues de t accessos (distintos) a la memoria
externa, se reduci la cuantidad de permutaciones a
N! / ( n \times (B!) ( \choose{M}{B} )^t )
* cuanto accessos a la memoria sean necesarios para que
queda al maximo una permutacion?
- N! / ( n \times (B!) ( \choose{M}{B} )^t ) debe ser al maximo uno.
- usamos las formulas siguientes:
- \log(x!) \approx x\log x
- \log \choose{M}{B} \approx B \lg \frac{M}{B}
N! \leq n (B!) (\choose{M}{B})^t
---------+-------------+---------------------------------
N \lg N \leq n B \lg B + t B \lg \frac{M}{B}
---------+-------------+---------------------------------
t \geq \frac { N\lg N - nB \lg B }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { N \lg(N/B) }
{ B \lg(M/B) }
---------+-------------+---------------------------------
\geq \frac { n \lg n }
{ \lg m }
---------+-------------+---------------------------------
\geq n \log_m n
* BONUS: Para ordenar strings, un caso particular (donde la
comparacion de dos elementos tiene un costo variable):
[www.brics.dk/ ... rs/stringsstoc97.pdf]
- \Omega( N_1/B \log_{M/B}(N_1/B) + K_2 \lg_{M/B} K_2 + N/B )
- donde
- N_1 es la suma de los tamanos de las caldenas mas cortas que B
- K_2 es la cuantidad de caldenas mas largas que B
3. Ordenar en Memoria Externa N elementos (en n=N/B paginas)
[en.wikipedia.org/wiki/External_sorting]
* Usando dictionarios o colas de prioridades en memoria externa
- N \lg N / \lg B = N \log_B N
- No es "tight" con la cota inferior
- impliqua
- o que hay un mejor algoritmo
- o que hay una mejor cota inferior
* Queda un algoritmo de ordenamiento: MergeSort
- usa la fusion de $m-1$ arreglos ordenados en memoria
externa:
1) carga en memoria principal $m-1$ paginas, cada una la
primera de su arreglo.
2) calcula la union de estas paginas en la pagina $m$ de
memoria principal,
- botando la pagina cuando llena
- cargando una nueva pagina (del mismo arreglo) cuando
vacilla
3) La complejidad es $n$ accessos.
- Algoritmo:
1) ordena cada de las $n$ paginas -> $n$ accessos
2) Cada nodo calcula la union de $m$ arreglos y escribe su
resultado, pagina por pagina, en la memoria
externa.
- Analisis:
- Cada nivel de recurencia costa $n$ accessos
- Cada nivel reduce por $m-1$ la cantidad de arreglos
- la complejidad total es de orden $n\log_m n$ accessos. (tight)
4. *BONUS* Ahora, cual es la cota inferior para una cola de
prioridad?
- una cola de prioridad se puede usar para ordenar (con $N$ accessos)
- hay una cota inferior para ordernar de $n \log_m n$
- entonces????
Colas de prioridad en memoria secundaria
Jérémy Barbay 2 Sep 201002/09/10 a las 15:09 hrs.2010-09-02 15:09:02
2.3 Colas de prioridad en memoria secundaria.
[en.wikipedia.org/wiki/Priority_queue]
[en.wikipedia.org/ ... %28data_structure%29]
1) Colas de Prioridades tradicional:
- que se necesita?
* Operadores
- insert(key,item)
- findMind()
- extractMin()
* Operadores opcionales
- heapify
- increaseKey, decreaseKey
- find
- delete
- successor/predecessor
- merge
- ...
- diccionarios: demasiado espacio para que se pide
- menos operadores que diccionarios
- => mas flexibilidad en la representacion
- => mejor tiempo y/o espacio
- *binary heap*: una estructura a dentro de muchas otras:
- sequence-heaps
- binomial queues
- Fibonacci heaps
- leftist heaps
- min-max heaps
- pairing heaps
- skew heaps
- *van Emde Boas queues*
[www.itl.nist.gov/ ... TML/vanemdeboas.html]
- Definition: An efficient implementation of priority
queues where insert, delete, get minimum, get maximum,
etc. take O(log log N) time, where N is the total
possible number of keys. Depending on the circumstance,
the implementation is null (if the queue is empty), an
integer (if the queue has one integer), a bit vector of
size N (if N is small), or a special data structure: an
array of priority queues, called the bottom queues, and
one more priority queue of array indexes of the bottom
queues.
- rendimiento en memoria secundaria de "binary heap": muy malo?
2) Colas de Prioridades en Memoria Secundaria: diseno
* Reference:
+ [www.dcc.uchile.cl/ ... ritmos/tesisRapa.pdf]
- paginas 9 hasta 16
+ Otras referencias en [www.leekillough.com/heaps/]
- El equivalente de B-Arbol
- Muchas alternativas en practica
- Buffer trees
- M/B-ary heaps
- array heaps
- R-Heaps
- Array Heaps
- sequence heaps
- Mas en "An experimental study of priority queues in external memory"
[portal.acm.org/ ... cfm?id=351827.384259]
3) Colas de Prioridades en Memoria Secundaria: cota inferior?
- Cota inferior para dictionaries es una cota inferior por
colas de prioridades o no?
[en.wikipedia.org/wiki/Priority_queue]
[en.wikipedia.org/ ... %28data_structure%29]
1) Colas de Prioridades tradicional:
- que se necesita?
* Operadores
- insert(key,item)
- findMind()
- extractMin()
* Operadores opcionales
- heapify
- increaseKey, decreaseKey
- find
- delete
- successor/predecessor
- merge
- ...
- diccionarios: demasiado espacio para que se pide
- menos operadores que diccionarios
- => mas flexibilidad en la representacion
- => mejor tiempo y/o espacio
- *binary heap*: una estructura a dentro de muchas otras:
- sequence-heaps
- binomial queues
- Fibonacci heaps
- leftist heaps
- min-max heaps
- pairing heaps
- skew heaps
- *van Emde Boas queues*
[www.itl.nist.gov/ ... TML/vanemdeboas.html]
- Definition: An efficient implementation of priority
queues where insert, delete, get minimum, get maximum,
etc. take O(log log N) time, where N is the total
possible number of keys. Depending on the circumstance,
the implementation is null (if the queue is empty), an
integer (if the queue has one integer), a bit vector of
size N (if N is small), or a special data structure: an
array of priority queues, called the bottom queues, and
one more priority queue of array indexes of the bottom
queues.
- rendimiento en memoria secundaria de "binary heap": muy malo?
2) Colas de Prioridades en Memoria Secundaria: diseno
* Reference:
+ [www.dcc.uchile.cl/ ... ritmos/tesisRapa.pdf]
- paginas 9 hasta 16
+ Otras referencias en [www.leekillough.com/heaps/]
- El equivalente de B-Arbol
- Muchas alternativas en practica
- Buffer trees
- M/B-ary heaps
- array heaps
- R-Heaps
- Array Heaps
- sequence heaps
- Mas en "An experimental study of priority queues in external memory"
[portal.acm.org/ ... cfm?id=351827.384259]
3) Colas de Prioridades en Memoria Secundaria: cota inferior?
- Cota inferior para dictionaries es una cota inferior por
colas de prioridades o no?
Diccionarios en memoria externa 1
Jérémy Barbay 31 Ago 201031/08/10 a las 15:16 hrs.2010-08-31 15:16:31
2.4 Diccionarios en memoria externa
===========================
Author: Jérémy Barbay
Date: 2010-08-31 19:14:57 XXX
1. B-arbol
1) (2,3) Arbol: un arbol de busqueda donde
- cada nodo tiene 1 o 2 llaves, que corresponde a 2 o 3
hijos, con la excepcion de la raiz;
- todas las hojas son al mismo nivel (arbol completamente balanceado)
- Propiedades:
- altura de un (2,3) arbol?
- tiempo de busqueda?
- insercion en un (2,3) arbol?
- delecion en un (2,3) arbol?
2) (d,2d) Arbol un arbol donde
- cada nodo tiene de d a 2d hijos, con la excepcion de la
raiz (significa d-1 a 2d-1 llaves).
- todas las hojas son al mismo nivel (arbol completamente
balanceado)
- Propiedades:
- altura de un (d,2d) arbol?
- tiempo de busqueda?
- insercion en un (d,2d) arbol?
- delecion en un (d,2d) arbol?
3) B-Arbol, y variantes
- B-Arbol
- [
- [en.wikipedia.org/wiki/B-tree]
- B^* arbol
- non-root nodes to be at least 2/3 full instead of 1/2
- [en.wikipedia.org/wiki/B*-tree]
- B^+ arbol
- the leaf nodes of the tree are chained together in the form of a linked list.
- [
2. Van Emde Boas arbol (vEB)
[en.wikipedia.org/wiki/Van_Emde_Boas_tree]
1) Historia:
- Originalemente (1977) un estructura de datos normal, que
suporta todas las operaciones en $O(\llg n) = O(\lg \lg
n)$, inventada por el equipo de Peter van Emde Boas.
- No considerado utiles en practica para "pequeños"
arboles.
- Applicacion a "Cache-Oblivious" algoritmos y estructuras de datos
- optimiza el cache sin conocer el tamaño B de sus paginas
- => optimiza todos los niveles sin conocer B_1,...,B_k
- otras applicaciones despues en calculo parallelo (?)
2) Definicion
- Cada nodo contiene un arbol van EmdeBoas sobre $\sqrt{n}$ elementos
- \llg n niveles de arboles
- operadores:
* Findnext
* Insert
* Delete
3) Analisis
- Busqueda en "tiempo" O(\lg n / \lg B) a cualquier nivel
$i$, donde el tiempo es la cuantidad de accessos al cache
del nivel considerado
- Insercion
- Delecion
3. Finger Search Tree: la busqueda doblada de los arboles de busqueda
1) Estructura de datos
2) algorimo de busqueda
3) analisis: busqueda en O(\lg p)
===========================
Author: Jérémy Barbay
Date: 2010-08-31 19:14:57 XXX
1. B-arbol
1) (2,3) Arbol: un arbol de busqueda donde
- cada nodo tiene 1 o 2 llaves, que corresponde a 2 o 3
hijos, con la excepcion de la raiz;
- todas las hojas son al mismo nivel (arbol completamente balanceado)
- Propiedades:
- altura de un (2,3) arbol?
- tiempo de busqueda?
- insercion en un (2,3) arbol?
- delecion en un (2,3) arbol?
2) (d,2d) Arbol un arbol donde
- cada nodo tiene de d a 2d hijos, con la excepcion de la
raiz (significa d-1 a 2d-1 llaves).
- todas las hojas son al mismo nivel (arbol completamente
balanceado)
- Propiedades:
- altura de un (d,2d) arbol?
- tiempo de busqueda?
- insercion en un (d,2d) arbol?
- delecion en un (d,2d) arbol?
3) B-Arbol, y variantes
- B-Arbol
- [
- [en.wikipedia.org/wiki/B-tree]
- B^* arbol
- non-root nodes to be at least 2/3 full instead of 1/2
- [en.wikipedia.org/wiki/B*-tree]
- B^+ arbol
- the leaf nodes of the tree are chained together in the form of a linked list.
- [
2. Van Emde Boas arbol (vEB)
[en.wikipedia.org/wiki/Van_Emde_Boas_tree]
1) Historia:
- Originalemente (1977) un estructura de datos normal, que
suporta todas las operaciones en $O(\llg n) = O(\lg \lg
n)$, inventada por el equipo de Peter van Emde Boas.
- No considerado utiles en practica para "pequeños"
arboles.
- Applicacion a "Cache-Oblivious" algoritmos y estructuras de datos
- optimiza el cache sin conocer el tamaño B de sus paginas
- => optimiza todos los niveles sin conocer B_1,...,B_k
- otras applicaciones despues en calculo parallelo (?)
2) Definicion
- Cada nodo contiene un arbol van EmdeBoas sobre $\sqrt{n}$ elementos
- \llg n niveles de arboles
- operadores:
* Findnext
* Insert
* Delete
3) Analisis
- Busqueda en "tiempo" O(\lg n / \lg B) a cualquier nivel
$i$, donde el tiempo es la cuantidad de accessos al cache
del nivel considerado
- Insercion
- Delecion
3. Finger Search Tree: la busqueda doblada de los arboles de busqueda
1) Estructura de datos
2) algorimo de busqueda
3) analisis: busqueda en O(\lg p)
Modelo de computación en memoria secundaria
Jérémy Barbay 26 Ago 201026/08/10 a las 16:01 hrs.2010-08-26 16:01:26
* 2. Algoritmos y Estructuras de Datos para Memoria Secundaria (3 semanas = 6 charlas)
+ Resultados de Aprendisajes de la Unidad
- Comprender el modelo de costo de memoria secundario
- Conocer algoritmos y estructuras de datos básicos que son eficientes en memoria secundaria,
- y el analisis de su desempeño.
* DONE 2.1 Modelo de computación en memoria secundaria. Accesos secuenciales y aleatorios
1. Arquitectura de un computador: la memoria
1) Muchos niveles de memoria
- Procesador
- registros
- Cache L1
- Cache L2
- Memory
- Cache
- Disco Duro magnetico / Memory cell
- Akamai cache
- Discos Duros en la red
- CD y DVDs tambien son "memoria"
2) Diferencias
- velocidad
- precio de construccion
- relacion fisica entre volumen y velocidad
- volatil o no
- accesso arbitrario en tiempo constante o no.
- latencia vs débito
3) Modelos formales
- RAM
- Jerarquia con dos niveles, paginas de tamaño B
- Jerarquia con k niveles, de paginas de tamaños B_1,...,B_k
- "Cache oblivious"
- Otros... mas practicas, mas dificil a analizar.
+ Resultados de Aprendisajes de la Unidad
- Comprender el modelo de costo de memoria secundario
- Conocer algoritmos y estructuras de datos básicos que son eficientes en memoria secundaria,
- y el analisis de su desempeño.
* DONE 2.1 Modelo de computación en memoria secundaria. Accesos secuenciales y aleatorios
1. Arquitectura de un computador: la memoria
1) Muchos niveles de memoria
- Procesador
- registros
- Cache L1
- Cache L2
- Memory
- Cache
- Disco Duro magnetico / Memory cell
- Akamai cache
- Discos Duros en la red
- CD y DVDs tambien son "memoria"
2) Diferencias
- velocidad
- precio de construccion
- relacion fisica entre volumen y velocidad
- volatil o no
- accesso arbitrario en tiempo constante o no.
- latencia vs débito
3) Modelos formales
- RAM
- Jerarquia con dos niveles, paginas de tamaño B
- Jerarquia con k niveles, de paginas de tamaños B_1,...,B_k
- "Cache oblivious"
- Otros... mas practicas, mas dificil a analizar.
Resumen de la Section y Fechas de Tareas/Controles 1
Jérémy Barbay 25 Ago 201025/08/10 a las 20:11 hrs.2010-08-25 20:11:25
1 Fechas de Controles y Tareas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
TAREA 1: Busqueda Binaria vs others [2010-08-26 Thu]--[2010-09-09 Thu]
TAREA 2: static cache-oblivious tree [2010-09-07 Tue]--[2010-09-21 Tue]
TAREA 3: Interpolation vs others [2010-09-21 Tue]--[2010-10-05 Tue]
CONTROL 1 [2010-09-29 Wed]
TAREA 4: LRU vs others [2010-10-05 Tue]--[2010-10-19 Tue]
TAREA 5 [2010-10-19 Tue]--[2010-11-02 Tue]
TAREA 6 [2010-11-02 Tue]--[2010-11-16 Tue]
CONTROL 2 [2010-11-10 Wed]
EXAMEN? [2010-11-22 Mon]--[2010-12-06 Mon]
For six programming homework, they must be two weeks long and end to end.
For the four first ones I have precise ideas: make them compare two or
three algorithms or data-structures on two distinct data-sets. For the two
last ones I will wait till I know them better. The controls are placed in
the middle of project periods: I will make those projects (3 and 6) a bit
simpler and reusing past results, leaving them more time to prepare the
control.
2 Recurrencias y Introduccion a la programacion dinamica
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- X_n = X_{n-1} + a_n
- Torre de Hanoi
- Fibonacci
- Subsecuencia de suma maximal
- Subsecuencia commun mas larga
+ solucion ingenua
+ Solucion en tiempo polynomial (pero espacio O(n^2))
+ Solucion en espacio lineal (y tiempo O(n^2))
+ ?Solucion de Hirshberg en tiempo O(nm) y espacio min (n,m)
3 Resumen de la Section
~~~~~~~~~~~~~~~~~~~~~~~~
1. Conceptos Basicos
- O(), o(), \Omega, \omega, \Theta, \theta
- Complejidad en el peor caso, en promedio
- Modelos computacionales:
- modelo de comparaciones
- modelo de memoria externa
2. Tecnicas de Cotas Inferiores
- lema del ave (reduccion)
- strategia de adversario
- teoria de la informacion (arbol de decision binario)
- Analisis fine
3. Metodologia de experimentacion
- Porque?
- Como hacer la experimentacion
- Como analizar y presentar los resultados
4. Casos de Estudios
- Torre de Hanoi
- "Disk Pile problem"
- Busqueda y Codificacion de Enteros (busqueda doblada)
- Busqueda binaria en \Theta(1+lg n) (mejor que 2\lg n)
- Algoritmo en 2n/3 para min max
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
TAREA 1: Busqueda Binaria vs others [2010-08-26 Thu]--[2010-09-09 Thu]
TAREA 2: static cache-oblivious tree [2010-09-07 Tue]--[2010-09-21 Tue]
TAREA 3: Interpolation vs others [2010-09-21 Tue]--[2010-10-05 Tue]
CONTROL 1 [2010-09-29 Wed]
TAREA 4: LRU vs others [2010-10-05 Tue]--[2010-10-19 Tue]
TAREA 5 [2010-10-19 Tue]--[2010-11-02 Tue]
TAREA 6 [2010-11-02 Tue]--[2010-11-16 Tue]
CONTROL 2 [2010-11-10 Wed]
EXAMEN? [2010-11-22 Mon]--[2010-12-06 Mon]
For six programming homework, they must be two weeks long and end to end.
For the four first ones I have precise ideas: make them compare two or
three algorithms or data-structures on two distinct data-sets. For the two
last ones I will wait till I know them better. The controls are placed in
the middle of project periods: I will make those projects (3 and 6) a bit
simpler and reusing past results, leaving them more time to prepare the
control.
2 Recurrencias y Introduccion a la programacion dinamica
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- X_n = X_{n-1} + a_n
- Torre de Hanoi
- Fibonacci
- Subsecuencia de suma maximal
- Subsecuencia commun mas larga
+ solucion ingenua
+ Solucion en tiempo polynomial (pero espacio O(n^2))
+ Solucion en espacio lineal (y tiempo O(n^2))
+ ?Solucion de Hirshberg en tiempo O(nm) y espacio min (n,m)
3 Resumen de la Section
~~~~~~~~~~~~~~~~~~~~~~~~
1. Conceptos Basicos
- O(), o(), \Omega, \omega, \Theta, \theta
- Complejidad en el peor caso, en promedio
- Modelos computacionales:
- modelo de comparaciones
- modelo de memoria externa
2. Tecnicas de Cotas Inferiores
- lema del ave (reduccion)
- strategia de adversario
- teoria de la informacion (arbol de decision binario)
- Analisis fine
3. Metodologia de experimentacion
- Porque?
- Como hacer la experimentacion
- Como analizar y presentar los resultados
4. Casos de Estudios
- Torre de Hanoi
- "Disk Pile problem"
- Busqueda y Codificacion de Enteros (busqueda doblada)
- Busqueda binaria en \Theta(1+lg n) (mejor que 2\lg n)
- Algoritmo en 2n/3 para min max
Metodologia de experimentación
Jérémy Barbay 19 Ago 201019/08/10 a las 11:43 hrs.2010-08-19 11:43:19
1.1b Metodologia de experimentación
===================================
Author: Jérémy Barbay
Date: 2010-08-19 15:42:11 XXX
1. Al inicio, Ciencias de la computacion fue solamente experimentacion.
* Turing y el codigo Enigma
- el importante estaba de solucionar la instancia del dia
(romper la llave del dia, basado en los messages de
meteo, para decryptar los messages mas importantes)
- no mucho focus en el problema, aunque Turing si escribio
la definicion de la Maquina universal.
* Experimentacion basica
- correga hasta que fonciona (o parece foncionar)
- correga hasta que entrega resultados correctos (o que parecen correctos)
- mejora hasta que fonciona en tiempo razonable (en las instancias que tenemos)
* Problemas:
- Demasiado "Ah Hoc"
- falta de rigor, de reproducibilidad
- desde el inicio, no "test bed" estandard, cada uno tiene sus tests.
- mas tarde, no estandard de maquinas
* Respuestas: Knuth et al.
- complejidad asymptotica: independancia de la maquina
- complejidad en el peor caso y promedio: independancia del "test bed"
- todavia es necesario de completar las estudias teoricas
con programacion y experimentacion: el modelo teorico es
solamente una simplificacion.
* Theoreticos desarollaron un lado "mathematico" de ciencias
de la computacion, con resultados importantes tal que
- NP-hardness
- "Polynomial Hierarchy" ([en.wikipedia.org/wiki/Polynomial_hierarchy])
* Theoria y Practica se completen, pero hay conflictos en ambos lados:
- demasiado theorias sin implementaciones (resultado del
ambiante social tambien).
- todavia hay estudios experimentales "no reproducibles"
2. Sobre la "buena" manera de experimentar
("A Theoretician's Guide to the Experimental Analysis of Algorithms", David S. Johnson, 2001)
1) Fija una hipothesis *antes* de programar.
- aunque el objetivo sea de programar un software
completo, solamente es necesario de implementar de
manera eficiente la partes relevantes. El resto se puede
implementar de manera "brutal". (E.g. "Intersection Problem")
2) "Incremental Programming"
- busca en la red "Agile Programming", "Software Engineering".
- una experimentacion es tambien un proyecto de software, y
las tecnicas de ingeniera de software se aplican tambien.
- Construe un simulador en etapas, donde a cada etapa
fonctiona el simulador entero.
3) "Modular Programming"
- Experimentacion es Investigacion, nunca se sabe por
seguro que se va a medir despues.
- Hay que programar de manera modular por salgar tiempo en
el futuro.
3. Sobre la "buena" manera de presentar sus resultados experimentales.
("Presenting Data from Experiments in Algorithmics", Peter Sanders, 2002)
1) El proceso:
* Experimentacion tiene un ciclo:
1. "Experimental Design" (inclue la eleccion de la hypothesis)
2. "Description of Measurement"
3. "Interpretation"
4. vuelve al paso 1.
* La presentacion sigue la misma estructura, pero solamente
exceptionalemente describe mas que una iteracion (la
mejor, no necesaramiente la ultima) del ciclo.
2) Eliges que quieres comunicar.
- el mismo dato se presenta diferamente en funcion de la
emfasis del reporte.
- pero, siempre la descripcion debe permitir la
*reproducibilidad* de la experimentacion.
3) Tables vs 2d vs 3d plot
* tables
- son faciles, y buenas para menos de 20 valores
- son sobre-usadas
* Grafes 3d
- mas modernos, impresionantes, pero
- en impresion no son tan informativos
- tiene un futuro con interactive media donde el usuario
puede cambiar el punto de vista, leer las valores
precisas, activar o no las surfacas.
* Grafes 2d
- en general preferables, pero de manera inteligente!
- cosas a considerar:
- log scale en x y/o y
- rango de valores en x y/o y.
- regla de "banking to 45 deg":
- "The weighted average of the slants of the line
segments in the figure should be about 45"
- se puede aproximar on un grafo en "paysage"
siguiendo el ratio de oro.
- factor out la informacion ya conocida
* Maximiza el Data-Ink ratio.
===================================
Author: Jérémy Barbay
Date: 2010-08-19 15:42:11 XXX
1. Al inicio, Ciencias de la computacion fue solamente experimentacion.
* Turing y el codigo Enigma
- el importante estaba de solucionar la instancia del dia
(romper la llave del dia, basado en los messages de
meteo, para decryptar los messages mas importantes)
- no mucho focus en el problema, aunque Turing si escribio
la definicion de la Maquina universal.
* Experimentacion basica
- correga hasta que fonciona (o parece foncionar)
- correga hasta que entrega resultados correctos (o que parecen correctos)
- mejora hasta que fonciona en tiempo razonable (en las instancias que tenemos)
* Problemas:
- Demasiado "Ah Hoc"
- falta de rigor, de reproducibilidad
- desde el inicio, no "test bed" estandard, cada uno tiene sus tests.
- mas tarde, no estandard de maquinas
* Respuestas: Knuth et al.
- complejidad asymptotica: independancia de la maquina
- complejidad en el peor caso y promedio: independancia del "test bed"
- todavia es necesario de completar las estudias teoricas
con programacion y experimentacion: el modelo teorico es
solamente una simplificacion.
* Theoreticos desarollaron un lado "mathematico" de ciencias
de la computacion, con resultados importantes tal que
- NP-hardness
- "Polynomial Hierarchy" ([en.wikipedia.org/wiki/Polynomial_hierarchy])
* Theoria y Practica se completen, pero hay conflictos en ambos lados:
- demasiado theorias sin implementaciones (resultado del
ambiante social tambien).
- todavia hay estudios experimentales "no reproducibles"
2. Sobre la "buena" manera de experimentar
("A Theoretician's Guide to the Experimental Analysis of Algorithms", David S. Johnson, 2001)
1) Fija una hipothesis *antes* de programar.
- aunque el objetivo sea de programar un software
completo, solamente es necesario de implementar de
manera eficiente la partes relevantes. El resto se puede
implementar de manera "brutal". (E.g. "Intersection Problem")
2) "Incremental Programming"
- busca en la red "Agile Programming", "Software Engineering".
- una experimentacion es tambien un proyecto de software, y
las tecnicas de ingeniera de software se aplican tambien.
- Construe un simulador en etapas, donde a cada etapa
fonctiona el simulador entero.
3) "Modular Programming"
- Experimentacion es Investigacion, nunca se sabe por
seguro que se va a medir despues.
- Hay que programar de manera modular por salgar tiempo en
el futuro.
3. Sobre la "buena" manera de presentar sus resultados experimentales.
("Presenting Data from Experiments in Algorithmics", Peter Sanders, 2002)
1) El proceso:
* Experimentacion tiene un ciclo:
1. "Experimental Design" (inclue la eleccion de la hypothesis)
2. "Description of Measurement"
3. "Interpretation"
4. vuelve al paso 1.
* La presentacion sigue la misma estructura, pero solamente
exceptionalemente describe mas que una iteracion (la
mejor, no necesaramiente la ultima) del ciclo.
2) Eliges que quieres comunicar.
- el mismo dato se presenta diferamente en funcion de la
emfasis del reporte.
- pero, siempre la descripcion debe permitir la
*reproducibilidad* de la experimentacion.
3) Tables vs 2d vs 3d plot
* tables
- son faciles, y buenas para menos de 20 valores
- son sobre-usadas
* Grafes 3d
- mas modernos, impresionantes, pero
- en impresion no son tan informativos
- tiene un futuro con interactive media donde el usuario
puede cambiar el punto de vista, leer las valores
precisas, activar o no las surfacas.
* Grafes 2d
- en general preferables, pero de manera inteligente!
- cosas a considerar:
- log scale en x y/o y
- rango de valores en x y/o y.
- regla de "banking to 45 deg":
- "The weighted average of the slants of the line
segments in the figure should be about 45"
- se puede aproximar on un grafo en "paysage"
siguiendo el ratio de oro.
- factor out la informacion ya conocida
* Maximiza el Data-Ink ratio.
Técnicas para demostrar cotas inferiores 1
Jérémy Barbay 17 Ago 201017/08/10 a las 14:53 hrs.2010-08-17 14:53:17
cc4102
======
Author: Jérémy Barbay
Date: 2010-08-17 18:52:49 XXX
Table of Contents
=================
* <2010-08-17 Tue 12:00-13:30> CC4102 B 205
* DONE 1.2 Técnicas para demostrar cotas inferiores
1) Busqueda Ordenada (en el modelo de comparaciones)
1. Cota superior: 2lg n vs 1+lg n
2. Cota inferior en el peor caso: Strategia de Adversario
cota inferior en el peor caso de 1+lg n
3. Cota inferior en el caso promedio uniforme
- Teoria de la Informacion
- = Arbol de Decision
- cota inferior de lg(2n+1), i.e. de 1+\lsup\lg(n+1/2)\\rsup
4. La complejidad del problema
- en el peor caso es \Theta(\lg n)
- en el caso promedio es \Theta(\lg n)
5. Pregunta: en este problema las cotas inferiores en el peor
caso y en el mejor caso son del mismo orden. Siempre es verdad?
2) Busqueda desordenada
1. Complejidad en el peor caso es \Theta(n)
2. Complejidad en el caso promedio?
- cota superior
- Move To Front
- ?BONUS? Transpose
- cota inferior
- algoritmo offline, lemma del ave
- A VER EN CASA O TUTORIAL: Huffman?
3) Ordenamiento (en el modelo de comparaciones)
- cota superior O(n\lg n)
- cota inferior en el peor caso
- cual tecnica?
- [ ] lema del ave?
- [ ] Strategia de Adversario?
- [X] Arbol Binario de Decision
- Resultado:
- \Omega(n \lg n)
- cota inferior en el caso promedio
- \Omega(n \lg n)
4) BONUS:
- La relacion entre
- complejidad en promedio de un algoritmo deterministico
- complejidad en el peor caso de un algoritmo aleatorizado (promedio sobre su aleatoria)
======
Author: Jérémy Barbay
Date: 2010-08-17 18:52:49 XXX
Table of Contents
=================
* <2010-08-17 Tue 12:00-13:30> CC4102 B 205
* DONE 1.2 Técnicas para demostrar cotas inferiores
1) Busqueda Ordenada (en el modelo de comparaciones)
1. Cota superior: 2lg n vs 1+lg n
2. Cota inferior en el peor caso: Strategia de Adversario
cota inferior en el peor caso de 1+lg n
3. Cota inferior en el caso promedio uniforme
- Teoria de la Informacion
- = Arbol de Decision
- cota inferior de lg(2n+1), i.e. de 1+\lsup\lg(n+1/2)\\rsup
4. La complejidad del problema
- en el peor caso es \Theta(\lg n)
- en el caso promedio es \Theta(\lg n)
5. Pregunta: en este problema las cotas inferiores en el peor
caso y en el mejor caso son del mismo orden. Siempre es verdad?
2) Busqueda desordenada
1. Complejidad en el peor caso es \Theta(n)
2. Complejidad en el caso promedio?
- cota superior
- Move To Front
- ?BONUS? Transpose
- cota inferior
- algoritmo offline, lemma del ave
- A VER EN CASA O TUTORIAL: Huffman?
3) Ordenamiento (en el modelo de comparaciones)
- cota superior O(n\lg n)
- cota inferior en el peor caso
- cual tecnica?
- [ ] lema del ave?
- [ ] Strategia de Adversario?
- [X] Arbol Binario de Decision
- Resultado:
- \Omega(n \lg n)
- cota inferior en el caso promedio
- \Omega(n \lg n)
4) BONUS:
- La relacion entre
- complejidad en promedio de un algoritmo deterministico
- complejidad en el peor caso de un algoritmo aleatorizado (promedio sobre su aleatoria)
Cotas inferiores y superiores: Hanoi, Disk Pile, Minimo, MinMax 1
Jérémy Barbay 12 Ago 201012/08/10 a las 17:26 hrs.2010-08-12 17:26:12
* Problema de la Torre de Hanoi
- definition
- cota superior
- cota inferior
* Variantes de la Torre de Hanoi
- pesos distintos?
- Disk Pile Problem (n discos pero h<n tamanos)
- cota inferior en funcion de n, en funcion de n,h
- cota superior en funcion de n, en funcion de n,h
* Minimo (resp. maximo) de un arreglo
- cota superior
- cota inferior
* Minimo Maximo de un arreglo
- cota superior
- cota inferior
- definition
- cota superior
- cota inferior
* Variantes de la Torre de Hanoi
- pesos distintos?
- Disk Pile Problem (n discos pero h<n tamanos)
- cota inferior en funcion de n, en funcion de n,h
- cota superior en funcion de n, en funcion de n,h
* Minimo (resp. maximo) de un arreglo
- cota superior
- cota inferior
* Minimo Maximo de un arreglo
- cota superior
- cota inferior
Introduccion
Jérémy Barbay 11 Ago 201011/08/10 a las 15:11 hrs.2010-08-11 15:11:11
Introduccion
============
Author: Jérémy Barbay
Date: 2010-08-11 15:11:12 CLT
Table of Contents
=================
1 Presentaciones
1.1 Quien somos
1.2 Quien son?
1.3 El curso
2 Programación
3 Conceptos básicos (test)
3.1 Notaciones
3.2 Definiciones
3.3 Complejidad Computacional
4 BONUS
1 Presentaciones
~~~~~~~~~~~~~~~~~
1.1 Quien somos
================
- franco-ingles-castellano
- curso interactivo?
- dos auxiliares
1.2 Quien son?
===============
* Quien
- tomo el curso CC40A en los ultimos semestres?
- toma CC53A
* Quien
- piensa seguir en la universidad despues de magister?
1.3 El curso
=============
* Tematicas
1. Conceptos básicos y complejidad (3 semanas = 6 charlas)
2. Algoritmos y Estructras de Datos para Memoria Secundaria (3 semanas = 6 charlas)
3. Técnicas avanzadas de diseño y análisis de algoritmos (4 semanas = 8 charlas)
4. Algoritmos no convencionales (5 semanas = 10 charlas)
* Modo
- *Clases expositivas* del profesor de cátera
- buscando la participación de los alumnos en pequeños
problemas que se van proponiendo durante la exposición.
- *Clases auxiliares* dedicadas a explicar ejemplos más
extensos, resolver ejercicios propuestos, y preparación pre y
post controles.
- *Exposición* de las mejores tareas de los alumnos, como casos
de estudio de implementación y experimentación.
* Evaluacion
- [2/9] Control 1 (unidades 1, 2 y parte de 3)
- [2/9] Control 2 (unidades 3,4)
- [2/9] Examen (todas unidades)
- [1/9] Tarea 1
- [1/9] Tarea 2
- [1/9] Tarea 3
* Nota Final
- controles y examen se promedian a partes iguales (el
examen reemplaca el peor control si la nota del examen es
mayor.)
- tareas se promedian a partes iguales
- nota final es 2/3 nota de controles y 1/3 de la nota de
tarea.
2 Programación
~~~~~~~~~~~~~~~
- Cuanto memoria hay en un computador? Como se maneja?
- Cual es la diferencia entre el disque duro y la memoria?
- Cuanto procesadores hay en un computador? Como se programan?
- Cual algoritmo elegir a implementar para un problema dicho?
- Cual es la diferencia entre programacion imperativa y funcional?
3 Conceptos básicos (test)
~~~~~~~~~~~~~~~~~~~~~~~~~~~
3.1 Notaciones
===============
- O(), o(), \Omega, \omega, \Theta, \theta
3.2 Definiciones
=================
- Complejidad en el peor caso
- Complejidad en promedio
- Otros modelos computacionales?
3.3 Complejidad Computacional
==============================
- Cual Algoritmos conocen? Cual son sus complejidad?
- para buscar en un arreglo (ordenado? no ordenado?)
- para ordenar un arreglo (en el modelo de comparaciones o no?)
- Cual cotas inferiores conocen?
- buscar?
- ordenar?
- Cual problemas dificiles conocen?
- elegir sus cursos
- assignar salas y horarios a los cursos
- assignar infermeros a hospitales
4 BONUS
~~~~~~~~
- Busqueda y Codificacion de Enteros
============
Author: Jérémy Barbay
Date: 2010-08-11 15:11:12 CLT
Table of Contents
=================
1 Presentaciones
1.1 Quien somos
1.2 Quien son?
1.3 El curso
2 Programación
3 Conceptos básicos (test)
3.1 Notaciones
3.2 Definiciones
3.3 Complejidad Computacional
4 BONUS
1 Presentaciones
~~~~~~~~~~~~~~~~~
1.1 Quien somos
================
- franco-ingles-castellano
- curso interactivo?
- dos auxiliares
1.2 Quien son?
===============
* Quien
- tomo el curso CC40A en los ultimos semestres?
- toma CC53A
* Quien
- piensa seguir en la universidad despues de magister?
1.3 El curso
=============
* Tematicas
1. Conceptos básicos y complejidad (3 semanas = 6 charlas)
2. Algoritmos y Estructras de Datos para Memoria Secundaria (3 semanas = 6 charlas)
3. Técnicas avanzadas de diseño y análisis de algoritmos (4 semanas = 8 charlas)
4. Algoritmos no convencionales (5 semanas = 10 charlas)
* Modo
- *Clases expositivas* del profesor de cátera
- buscando la participación de los alumnos en pequeños
problemas que se van proponiendo durante la exposición.
- *Clases auxiliares* dedicadas a explicar ejemplos más
extensos, resolver ejercicios propuestos, y preparación pre y
post controles.
- *Exposición* de las mejores tareas de los alumnos, como casos
de estudio de implementación y experimentación.
* Evaluacion
- [2/9] Control 1 (unidades 1, 2 y parte de 3)
- [2/9] Control 2 (unidades 3,4)
- [2/9] Examen (todas unidades)
- [1/9] Tarea 1
- [1/9] Tarea 2
- [1/9] Tarea 3
* Nota Final
- controles y examen se promedian a partes iguales (el
examen reemplaca el peor control si la nota del examen es
mayor.)
- tareas se promedian a partes iguales
- nota final es 2/3 nota de controles y 1/3 de la nota de
tarea.
2 Programación
~~~~~~~~~~~~~~~
- Cuanto memoria hay en un computador? Como se maneja?
- Cual es la diferencia entre el disque duro y la memoria?
- Cuanto procesadores hay en un computador? Como se programan?
- Cual algoritmo elegir a implementar para un problema dicho?
- Cual es la diferencia entre programacion imperativa y funcional?
3 Conceptos básicos (test)
~~~~~~~~~~~~~~~~~~~~~~~~~~~
3.1 Notaciones
===============
- O(), o(), \Omega, \omega, \Theta, \theta
3.2 Definiciones
=================
- Complejidad en el peor caso
- Complejidad en promedio
- Otros modelos computacionales?
3.3 Complejidad Computacional
==============================
- Cual Algoritmos conocen? Cual son sus complejidad?
- para buscar en un arreglo (ordenado? no ordenado?)
- para ordenar un arreglo (en el modelo de comparaciones o no?)
- Cual cotas inferiores conocen?
- buscar?
- ordenar?
- Cual problemas dificiles conocen?
- elegir sus cursos
- assignar salas y horarios a los cursos
- assignar infermeros a hospitales
4 BONUS
~~~~~~~~
- Busqueda y Codificacion de Enteros
