شمارش تعداد رشته های قابل تولید برای عبارات پرانتزی خوشساخت
سال انتشار: 1395
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 446
فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
NPECE01_498
تاریخ نمایه سازی: 6 بهمن 1395
چکیده مقاله:
مسیله شمارش تعداد عبارات خوشساخت قابل تولید با توزیع یکنواخت با جفت پرانتز، به عنوان یک مسیله کاربردی در زمینههای اساسی علوم کامپیوتر عمل مینماید و با روشهای مختلفی قابل حل است. اکثر مسایل مربوط به تولید عبارات خوشساخت دارای الگوریتمی با مرتبه زمانی هستند و همه آنها با توجه به مقدار مرتبه زمانی، میزان حافظه مصرفی، عملیات پیش پردازشی و دیگر خصیصهها کارایی متفاوتی دارند. نوآوری این مقاله در ارایهی الگوریتمی جدید با زمان خطی جهت تولید و شمارش تعداد رشته های قابل تولید از روی عبارات پرانتزی خوشساخت و سپس اثبات رابطهی به دست آمده با استفاده از مولد عدد کاتالان و رابطهی ضرایب چند جملهای است. این روش نه تنها دارای زمان اجرا و حافظه مصرفی بهینه است بلکه به دلیل استفاده از یک گرامر مستقل از متن غیر مبهم یکی از مسایل ترکیباتی مطرح شده در بحث تیوری گرامرهای مستقل از متن را نیز حل میکند.
کلیدواژه ها:
نویسندگان
علی نوراله
استادیار دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی، تهران
حکیمه مظاهری
دانشجوی کارشناسی ارشد دانشکده مهندسی کامپیوتر دانشگاه تربیت دبیر شهید رجایی، تهران