کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951936 | 1441994 | 2017 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient random sampling of binary and unary-binary trees via holonomic equations
ترجمه فارسی عنوان
نمونه گیری تصادفی کارآمد از درخت های دوتایی و یکنواخت با استفاده از معادلات هولوگرام
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present a new uniform random sampler for binary trees with n internal nodes consuming 2n+Î(logâ¡(n)2) random bits on average. This makes it quasi-optimal and out-performs the classical Remy algorithm. We also present a sampler for unary-binary trees with n nodes taking Î(n) random bits on average. Both are the first linear-time algorithms to be optimal up to a constant.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 42-53
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 42-53
نویسندگان
Axel Bacher, Olivier Bodini, Alice Jacquot,