عنوان پایان‌نامه
تولید درختان t-ary در ترتیب شبه قاموسی
- رشته تحصیلی
- علوم کامپیوتر
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 5724;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 69081
- تاریخ دفاع
- ۲۷ خرداد ۱۳۹۴
- دانشجو
- غزاله پروینی
- استاد راهنما
- عباس نوذری دالینی, مرتضی محمدنوری
- چکیده
- الگوریتم‌های ترکیبیاتی در بسیاری از مسائل ریاضیات و کامپیوتر، نقش مهمی را ایفا می‌کنند. تولید اشیاء ترکیبیاتی از جمله درخت‌ها یکی از موضوعاتی است که تاکنون مورد توجه محققان قرار گرفته است.بیشتر الگوریتم‌های تولید درخت، به جای تولید مستقیم درخت‌ها از تولید کد‌های معادل درخت‌ها استفاده می‌کنند. همچنین هر الگوریتم تولید درخت، از ترتیب مشخصی برای تولید درختان استفاده می‌کند.در این پایان‌نامه دو الگوریتم برای تولید درختان t-تایی با ارتفاع محدود و ارتفاع ثابت ارائه شده است که این ارتفاع به وسیل? متغیر داده شده‌ی h تعیین می‌شود. درخت‌هایt -تاییدر ترتیب B-Order تولید می‌شوند و روی? تولید درختان بر پایه‌ی کدگذاری درختان به وسیله‌ی دنباله‌ی x-sequence است. ترتیب B-Order و دنباله x-sequence اولین بار توسط زکس ارائه شده است. در تولید درختان t-تایی با ارتفاع محدود، ارتفاع درختان تولید شده بین [ logt(n+1) ] و h متغیر است که در آن n نشان دهنده‌ی تعداد گره‌های داخلی درخت است. همچنین در تولید درختان t-تایی با ارتفاع ثابت، ارتفاع درختان تولید شده دقیقا h می‌باشد.کلمات کلیدی : الگوریتم‌های ترکیبیاتی، گراف، درخت‌های t-تایی، رتبه‌گذاری، رتبه‌گشایی، الگوریتم تولید، الگوریتم تالی، درختان با عمق محدود، ترتیب B.
- Abstract
- Combinatorial algorithms play an important role in many applications. Generating combinatorial objects including trees is one of the most important topics in combinatorial algorithms and is considered by many researchers. Most of the generation algorithms for trees use an encoding for trees and generate equivalent codes instead of trees. Every generation algorithm follows a specific order for generating trees. In this thesis, we present two algorithm for generating t-ary trees with bounded height and fixed height whose heights are determined by a given value h. The t-ary trees are generated in B-order and generation process is based on an encoding using integer sequences (x-sequences) due to Zaks. In generating t-ary trees with bounded height, the height of generated trees is between [log_t(n+1)] and h where n is the number of internal nodes in the tree and in generating t-ary trees with fixed height the height of generated trees is exactly h. Keywords: Combinatorial Algorithms, Generation Algorithms, t-ary Trees, B-order, x-sequence, Bounded height.
