Searching and Coding: Unbounded Search and Delta Codes
Jérémy Barbay 24 Mar 201024/03/10 a las 19:39 hrs.2010-03-24 19:39:24
<2010-03-25 Thu 14:30-16:00>
1) What did we see
1. Parametrisation
2. Tarea: Complexity of the Disk Pile Pb?
3. Formalisation of Adaptive Algorithms
2) A basic problem: Searching in a sorted array
1. Binary Search
2. Doubling Search
3. Unbounded Search
3) Extension: Searching is coding
1. Unary Code
2. Binary Code
3. Delta Code
***** References:
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
1) What did we see
1. Parametrisation
2. Tarea: Complexity of the Disk Pile Pb?
3. Formalisation of Adaptive Algorithms
2) A basic problem: Searching in a sorted array
1. Binary Search
2. Doubling Search
3. Unbounded Search
3) Extension: Searching is coding
1. Unary Code
2. Binary Code
3. Delta Code
***** References:
J. L. Bentley and A. C.-C. Yao. "An Almost Optimal Algorithm
for Unbounded Searching." Information Processing Letters,
Vol. 5, pp. 82-87, 1976.
@article{anAlmostOptimalAlgorithmForUnboundedSearching,
author = {Jon Louis Bentley and Andrew Chi-Chih Yao},
title = {An almost optimal algorithm for unbounded searching},
journal = {Information processing letters},
year = {1976},
OPTkey = {},
volume = {5},
number = {3},
pages = {82--87},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
| Última Modificación | 24 Mar 201024/03/10 a las 19:47 hrs.2010-03-24 19:47:24 |
|---|---|
| Vistas Únicas | 0 |
| Compartir | |
| Comentarios |
|
