کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950749 1440715 2016 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On teaching sets of k-threshold functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On teaching sets of k-threshold functions
چکیده انگلیسی
In this paper we study teaching sets of k-threshold functions, i.e. functions that can be represented as a conjunction of k threshold functions. We reveal a connection between essential points of k threshold functions and essential points of the corresponding k-threshold function. We show that in two-dimensional case the number of minimal teaching sets of a 2-threshold function can grow as Ω(n2). We also consider the class of polytopes with vertices in the d-dimensional cube. Each polytope from this class can be defined by a k-threshold function for some k. We prove that such a polytope has a unique minimal teaching set which is equal to the set of its essential points. For d=2 we describe structure of the minimal teaching set of a polytope and show that its cardinality is either Θ(n2) or O(n) and depends on the perimeter and the minimum angle of the polytope.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 251, December 2016, Pages 301-313
نویسندگان
,