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

سال انتشار: 1395
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 446

فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد

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

لینک ثابت به این مقاله:

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

NPECE01_498

تاریخ نمایه سازی: 6 بهمن 1395

چکیده مقاله:

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

نویسندگان

علی نوراله

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

حکیمه مظاهری

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