Geodesic
Weighing algorithms of classification and identification of situations
Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 119-134
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper gives lower bounds for the minimum number $m$ of weighings that are necessary for identification of up to $t$ non-standard objects out of the total number of $n$ objects being tested. For the problem with fixed deviation of weights of non-standard objects we construct a perfect algorithms with parameters $n=11$, $m=5$, $t=2$ corresponding to the parameters of the ternary Virtakallio–Golay code. The non-existence of a perfect weighing code with such parameters is proved.
Keywords: weighing, detection of false coins
Mots-clés : classification algorithm. 
@article{DM_2014_26_4_a11,
     author = {A. M. Chudnov},
     title = {Weighing algorithms of classification and identification of situations},
     journal = {Diskretnaya Matematika},
     pages = {119--134},
     year = {2014},
     volume = {26},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2014_26_4_a11/}
}
TY  - JOUR
AU  - A. M. Chudnov
TI  - Weighing algorithms of classification and identification of situations
JO  - Diskretnaya Matematika
PY  - 2014
SP  - 119
EP  - 134
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2014_26_4_a11/
LA  - ru
ID  - DM_2014_26_4_a11
ER  - 
%0 Journal Article
%A A. M. Chudnov
%T Weighing algorithms of classification and identification of situations
%J Diskretnaya Matematika
%D 2014
%P 119-134
%V 26
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2014_26_4_a11/
%G ru
%F DM_2014_26_4_a11
A. M. Chudnov. Weighing algorithms of classification and identification of situations. Diskretnaya Matematika, Tome 26 (2014) no. 4, pp. 119-134. http://geodesic.mathdoc.fr/item/DM_2014_26_4_a11/

[1] Yaglom A.M., Yaglom I.M., Veroyatnost i informatsiya, Nauka, Moskva, 1973 | MR

[2] Kanel-Belov A.Ya., Frenkin B.R., “Dopolnenie k state D.A. Mikhalina, I.M. Nikonova «Odna zadacha o nakhozhdenii falshivoi monety»”, Matematicheskoe prosveschenie, 3:12, 229–231

[3] Alon N., Kozlov D.N., Vu V.H., “The geometry of coin-weighing problems”, Proc. 37th Annu. Found. Comput. Sci. (Burlington), 524–532 | MR

[4] Bshouty N.H., “Optimal algorithms for the coin weighing problem with a spring scale”, COLT 2009 Proceedings, Montreal, 34–43

[5] Berlekamp E.R., Block coding with noiseless feedback, PhD. Thesis, Massachusetts Inst. of Technology, Dept. of Electr. Eng., 1964

[6] Bassalygo L.A., “Nedvoichnye kody, ispravlyayuschie oshibki pri nalichii odnorazovoi bezoshibochnoi obratnoi svyazi”, Problemy peredachi informatsii, 41:2 (2009), 63–67 | MR

[7] Barg A., “At the dawn of the theory of codes”, The Math. Intelligencer, 15:1 (1993), 20–26 | DOI | MR | Zbl

[8] Murota K., Discrete Convex Analysis, SIAM, Philadelphia, 2003 | MR

[9] Danilov V.I, Koshevoi G.A., “Diskretnaya vypuklost”, Zapiski nauchnykh seminarov POMI, 312 (2004), 86–93 | MR | Zbl