شمارش تعداد رشته های قابل تولید برای عبارات پرانتزی خوشساخت

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

Keywords:

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