ارائه روش جدید برای تولید درختان دودویی تصادفی با توزیع یکنواخت

Publish Year: 1395
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 735

This Paper With 7 Page And PDF and WORD Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

CITCOMP01_291

تاریخ نمایه سازی: 16 شهریور 1395

Abstract:

موضوع اصلی در این مقاله، ارائه روشی برای تولید درختان دودویی تصادفی با توزیع یکنواخت است. روش های موجود برای تولید درختان تصادفی دودویی از لحاظ مرتبه زمانی، حافظه مصرفی، عملیات پیش پردازشی و دیگر خصیصه ها با یکدیگر تفاوت دارند. در این مقاله با به کارگیری یک گرامر مستقل از متن به تولید رشته پرانتز های خوش فرم، به صورت تصادفی و با توزیع یکنواخت پرداخته شده است. نوآوری این مقاله در ارائه ی الگوریتمی جدید با زمان خطی جهت تولید درخت تصادفی با توزیع یکنواخت است که علاوه بر بهینه بودن زمان اجرای آن به دلیل استفاده از یک گرامر مستقل از متن غیر مبهم یکی از مسائل ترکیبیاتی مطرح شده در بحث تئوری گرامرهای مستقل از متن را نیز حل می کند. در روش پیشنهادی ابتدا با مفروض بودن n یک عبارت پرانتزی خوش فرم به طول 2n به صورت تصادفی با توزیع یکنواخت تولید می شود و سپس از روی آن می توان یک درخت دودویی متناظر با آن را ایجاد کرد. میزان مصرف حافظه الگوریتم پیشنهاد شده نیز از 2n تجاوز نمی کند که از این جنبه نیز بهینه محسوب می شود.

Keywords:

درخت تصادفی , توزیع یکنواخت , عبارت پرانتزی خوش فرم

Authors

علی نوراله

استادیار دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی، تهران

حکیمه مظاهری

حکیمه مظاهری، دانشجوی کارشناسی ارشد دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی، تهران

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • Arnold, D. B. and Sleep, M. R. (1980) _ _ ...
  • Zaks, S. (1980)، _ 'Lexicographic generation of ordered trees". Theoret. ...
  • Reingold, E. M., Nievergelt, J. and Deo, N. (1977) _ ...
  • Ro-Yu Wu , Jou-Ming Chang, An-Hang Chen and Chun-Liang Liu. ...
  • Martin, H. W. and Orr, B. O. (1989) _ _ ...
  • Conf., Louisville, KY, 21-23 February, pp. 33-38. ACM _ Press, ...
  • Bultena B. and Ruskey F. (1998)، _ An Eades-McKay algorithm ...
  • Er M.C. (1983)، " A note On generating wellformed parenthesis ...
  • Ruskey F. and Proskurowsk _ (1990)، "Generating binary trees by ...
  • Proskurowsk _ and Ruskey F. (1985)، "Binary free Gray codes, ...
  • نمایش کامل مراجع