Geodesic
Estimates for the complexity of a method for solving the problem of inclusive search
Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 118-139 
È. È. Gasanov. Estimates for the complexity of a method for solving the problem of inclusive search. Diskretnaya Matematika, Tome 12 (2000) no. 2, pp. 118-139. http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/
@article{DM_2000_12_2_a9,
     author = {\`E. \`E. Gasanov},
     title = {Estimates for the complexity of a method for solving the problem of inclusive search},
     journal = {Diskretnaya Matematika},
     pages = {118--139},
     year = {2000},
     volume = {12},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/}
}
TY  - JOUR
AU  - È. È. Gasanov
TI  - Estimates for the complexity of a method for solving the problem of inclusive search
JO  - Diskretnaya Matematika
PY  - 2000
SP  - 118
EP  - 139
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/
LA  - ru
ID  - DM_2000_12_2_a9
ER  - 
%0 Journal Article
%A È. È. Gasanov
%T Estimates for the complexity of a method for solving the problem of inclusive search
%J Diskretnaya Matematika
%D 2000
%P 118-139
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2000_12_2_a9/
%G ru
%F DM_2000_12_2_a9

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

We suggest a method to solve the problem of inclusive search, which has three versions depending on the chosen base set: the set of monotone Boolean function, the set of elementary monotone conjunctions, and the set of Boolean variables. For each version, we estimate the Shannon function for the method complexity and the mean value of the complexity; we study the asymptotic behaviour of the Shannon function and of the logarithm of the mean value, and find that the Shannon function for the complexity of the method suggested asymptotically behaves as the Shannon function for the complexity of inclusive search. This research was supported by the Russian Foundation for Basic Research, grant 98–01–00130.

[1] Selton G., Avtomaticheskaya obrabotka, khranenie i poisk informatsii, Sov. radio, Moskva, 1973

[2] Gasanov E. E., “Nizhnyaya otsenka slozhnosti informatsionnykh setei dlya odnogo otnosheniya chastichnogo poryadka”, Diskretnaya matematika, 8:4 (1996), 108–122 | MR | Zbl

[3] Gasanov E. E., “Nizhnyaya otsenka slozhnosti vklyuchayuschego poiska v klasse drevovidnykh skhem”, Diskretnaya matematika, 10:1 (1998), 63–72 | MR | Zbl

[4] Gasanov E. E., Kosolapov A. V., “K voprosu o drevovidnosti optimalnykh informatsionnykh setei vklyuchayuschego poiska”, Intellektualnye sistemy, 3:1–2 (1998), 167–192

[5] Gasanov E. E., “Ob odnomernoi zadache intervalnogo poiska”, Diskretnaya matematika, 7:2 (1995), 40–60 | MR | Zbl

[6] Gavrilov G. P., Sapozhenko A. A., Zadachi i uprazhneniya po kursu diskretnoi matematiki, Nauka, Moskva, 1992 | MR | Zbl

[7] Gasanov E. E., “Ob odnoi matematicheskoi modeli informatsionnogo poiska”, Diskretnaya matematika, 3:2 (1991), 69–76 | MR | Zbl