Resumen de la Section y Fechas de Tareas/Controles
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
| Compartir | |
|---|---|
| Última Modificación | 25 Ago 201025/08/10 a las 20:11 hrs.2010-08-25 20:11:25 |
| Vistas Únicas | 1 |
