Técnicas para demostrar cotas inferiores
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)
| Última Modificación | 17 Ago 201017/08/10 a las 14:53 hrs.2010-08-17 14:53:17 |
|---|---|
| Vistas Únicas | 1 |
| Compartir |
