کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8960180 1646386 2018 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Testing piecewise functions
ترجمه فارسی عنوان
تست توابع قطعه ای
کلمات کلیدی
آزمایش املاک، آزمایش فعال تئوری یادگیری، توابع ارزش واقعی،
ترجمه چکیده
این کار پیچیدگی پرس و جو از آزمون املا را برای عملکردهای عمودی بسته در خط واقعی در تنظیمات آزمایش فعال و غیر فعال بررسی می کند. نتایج به دست آمده تحت شرایط عبور صفر اندازه گیری انتزاعی است، که به عنوان موارد خاص به عنوان توابع ثابت قطعی و توابع چند جملهای قطعه است. ما متوجه می شویم که در تنظیمات آزمایش فعال، پیچیدگی پرس و جو از تست های عمومی به طور مستقل از تعداد قطعات است. ما همچنین وابستگی مطلوب به تعداد قطعات در پیچیدگی پرس و جو از تست های غیر فعال در مورد خاص توابع ثابت قطعی را شناسایی می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
تست توابع قطعه ای
چکیده انگلیسی
This work explores the query complexity of property testing for general piecewise functions on the real line, in the active and passive property testing settings. The results are proven under an abstract zero-measure crossings condition, which has as special cases piecewise constant functions and piecewise polynomial functions. We find that, in the active testing setting, the query complexity of testing general piecewise functions is independent of the number of pieces. We also identify the optimal dependence on the number of pieces in the query complexity of passive testing in the special case of piecewise constant functions.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 745, 12 October 2018, Pages 23-35
نویسندگان
, ,