ON THE MINIMAL TEACHING SETS OF TWO-DIMENSIONAL THRESHOLD FUNCTIONS

被引：5

作者：

Alekseyev, Max A. ^{[1
]}

Basova, Marina G. ^{[2
]}

Zolotykh, Nikolai Yu. ^{[2
,3
]}

机构：

[1] George Washington Univ, Washington, DC 20052 USA

[2] NI Lobachevskii State Univ, Nizhnii Novgorod, Russia

[3] Higher Sch Econ, Nizhnii Novgorod, Russia

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2015年 / 29卷 / 01期

基金：

美国国家科学基金会;

关键词：

threshold function; integer lattice; teaching set; arrangement of lines; NUMBER; LINES;

D O I：

10.1137/140978090

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

It is known that a minimal teaching set of any threshold function on the two-dimensional rectangular grid consists of 3 or 4 points. We derive exact formulae for the numbers of functions corresponding to these values and further refine them in the case of a minimal teaching set of size 3. We also prove that the average cardinality of the minimal teaching sets of threshold functions is asymptotically 7/2. We further present corollaries of these results concerning some special arrangements of lines in the plane.

引用

页码：157 / 165

页数：9

共 14 条

[1] ON THE NUMBER OF LINEAR PARTITIONS OF THE (M, N)-GRID [J].