عنوان

نمایۀ گره های حامی دار درخت های تصادفی

پ۲۶۹۴۸

per

نمایۀ گره های حامی دار درخت های تصادفی

ژاله طوفان پور

ریاضی،آمار و علوم کامپیوتر

۱۴۰۱

۱۱۷ص.

سی دی

کارشناسی ارشد

آمار

۱۴۰۱/۰۳/۱۷

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

Trees are widely used in artificial intelligence, sophisticated algorithms to provide effective data storage mechanisms and as models for some stochastic processes. The data is stored in the tree in a structure called a node. A node that is not a leaf and none of its children are leaves is called a protected node. The number of protected nodes and the number of non-protected nodes that are at the same distance from the root of the tree are called the protected node profile and the non-protected node profile, respectively. In this dissertation, when the number of nodes in the recursive tree increases, we obtain the expectations, variances, covariance, and asymptotic joint distribution of both protected node profile and non-protected node profile. We have also presented the asymptotic expectation of protected and non-protected node profile in digital search trees. All results are based on the use of Poissonization, Mellin transform, recursive equations, generating functions, singularity analysis and saddle point method.

Protected node profile of random trees

طوفان پور،

ژاله

تهيه کننده

ایمانی نبیی،

‏جوانیان،

وحیدی اصل،

رامین

مهری

محمدقاسم

استاد راهنما

استاد راهنما

استاد مشاور

‏تبریز