Geodesic
The Shannon function of the complexity of interval search on a Boolean cube in the class of trees
Diskretnaya Matematika, Tome 18 (2006) no. 2, pp. 111-122 
T. D. Blaivas. The Shannon function of the complexity of interval search on a Boolean cube in the class of trees. Diskretnaya Matematika, Tome 18 (2006) no. 2, pp. 111-122. http://geodesic.mathdoc.fr/item/DM_2006_18_2_a7/
@article{DM_2006_18_2_a7,
     author = {T. D. Blaivas},
     title = {The {Shannon} function of the complexity of interval search on a {Boolean} cube in the class of trees},
     journal = {Diskretnaya Matematika},
     pages = {111--122},
     year = {2006},
     volume = {18},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_2_a7/}
}
TY  - JOUR
AU  - T. D. Blaivas
TI  - The Shannon function of the complexity of interval search on a Boolean cube in the class of trees
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 111
EP  - 122
VL  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_2_a7/
LA  - ru
ID  - DM_2006_18_2_a7
ER  - 
%0 Journal Article
%A T. D. Blaivas
%T The Shannon function of the complexity of interval search on a Boolean cube in the class of trees
%J Diskretnaya Matematika
%D 2006
%P 111-122
%V 18
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2006_18_2_a7/
%G ru
%F DM_2006_18_2_a7

Voir la notice de l'article provenant de la source Math-Net.Ru

For the problem of interval search on the Boolean cube, we investigate the behaviour of the Shannon function in the class of tree-like circuits called information trees. It is shown that for databases of cardinality coinciding in order with cardinality of the Boolean cube the Shannon function is equal in order to the optimal complexity in the class of balanced tree-like circuits. For databases of cardinality less in order than the cardinality of the Boolean cube we give the asymptotics of the logarithm of the Shannon function.

[1] Blaivas T. D., “Asimptotiki zadachi intervalnogo poiska na bulevom kube v klasse sbalansirovannykh drevovidnykh skhem”, Diskretnaya matematika, 16:4 (2004), 65–78 | MR | Zbl

[2] Gasanov E. E., Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, Fizmatlit, Moskva, 2002 | Zbl

[3] Gasanov E. E., “Otsenki slozhnosti odnogo metoda resheniya zadachi vklyuchayuschego poiska”, Diskretnaya matematika, 12:2 (2000), 118–139 | MR | Zbl