سال انتشار: ۱۳۸۶

محل انتشار: سیزدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۵

نویسنده(ها):

هایده اهرابیان – دانشکده علوم کامپیوتر، دانشگاه تهران
حسن علیزاده قادیکلایی – دانشکده علوم کامپیوتر، دانشگاه تهران

چکیده:

در این مقاله الگوریتم جدیدی برای تولید کدهای متناظر بادرختهای- k تایی ارائه میشود که از رسته الگوریتمهای برنامه ریزی پویا است. این الگوریتم تمامz – تایی با -k دنبالههای متناظر با درختهای nگره داخلی را در ترتیب قاموسی B ترتیب تولید میکند. ثابت می شود هر دنباله در زمان ثابت ( ۱O) تولید میشود. ایده اصلی در اینالگوریتم تولید کدهای متناظر با درختهای -k با تایی n گره، از روی کدهای متناظر با درختهای۱ – k تایی با n- گره است که مبتنی بر دوعمل افزایش و الحاق است.