عنوان

تحلیل درختهای بازگشتی نمایی

شماره

پ۲۹۷۴۹

زبان متن نوشتاري يا گفتاري و مانند آن

per

عنوان اصلي

تحلیل درختهای بازگشتی نمایی

نام نخستين پديدآور

مینا قاسمی

نام ناشر، پخش کننده و غيره

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

تاریخ نشرو بخش و غیره

۱۴۰۲

نام خاص و کميت اثر

۶۲ص.

مواد همراه اثر

سی دی

جزئيات پايان نامه و نوع درجه آن

دکتری

نظم درجات

آمار

زمان اعطا مدرک

۱۴۰۲/۰۶/۱۸

متن يادداشت

در نظریۀ گراف، درختها به عنوان گراف های همبند بدون دور تعریف می شوند. آنها یک شئ اساسی درنظریۀ گراف و ترکیبیات، و همچنین اشیائی برای ساختمانهای داده و الگوریتم ها در علوم کامپیوتر و برایمدلسازی در بسیاری از زمینه ها هستند.در این رساله، درخت k-kیی بازگشتی نمایی ) (k ≥ ٢را تحلیل می کنیم که در آن هر گره حداکثر kفرزند دارد. این درخت با یک گرۀ خارجی )مکان درج یک گرۀ جدید( شروع به رشد می کند. در هر مرحله،هر گرۀ خارجی به طور مستقل به یک گرۀ داخلی با احتمال pتبدیل می شود یا با احتمال ١ − pبدون تغییرباقی می ماند. سپس درخت گسترش می یابد و این روند تکرار می شود.در اینجا به بررسی ویژگیهای اساسی در مورد برگ ها و فواصل در این درختها میپردازیم. برای اندازهو تعداد برگها، یک توزیع حدی، تحت مقیاس بندی مناسب، بهدست می آوریم که توسط گشتاورهای ساختهشده به صورت استقرایی، به طور یکتا مشخص می شود. به وسیلۀ مارتینگل ها، یک حد تقریباً حتمی برایطول مسیر خارجی مقیاس بندی شده در یک درخت k-kیی بازگشتی نمایی پیدا می کنیم. طول مسیر خارجینشان دهندۀ عمق یک گرۀ خارجی به طور تصادفی انتخاب شده در یک درخت k-kیی بازگشتی نمایی است.با روش انقباض، توزیع حدی طول مسیر خارجی مقیاس بندی شده را نیز مشخص می کنیم

متن يادداشت

n graph theory, trees are defined as connected graphs without cycles. They are a fundamental object in graph theory and combinatorics, as well as objects for data structures andalgorithms in computer science, and for modeling in many fields.In this thesis, we analysis exponential recursive k-ary tree (k ≥ 2) where each node hasat most k children. This tree starts out to grow with an external node (a location to insert anew node). At each step, each external node is independently changed into an internal nodewith probability p, or stays unchanged with probability 1 − p. Then the tree is extended, andthe process is repeated.Here, we investigate fundamental properties concerning, size, leaves and distances in thesetrees. For the size and the number of leaves, we find (under appropriate scaling) a limit distribution uniquely characterized by inductively constructed moments. Via martingales, we findan almost-sure limit for the scaled external path length in an exponential recursive k-ary tree.The external path length is indicative of the depth of a randomly chosen external node in anexponential recursive k-ary tree. By contraction method, we also characterize the limitingdistribution of the scaled external path length

عنوان گونه گون

Analysis of exponential recursive trees

عنصر شناسه اي

قاسمی،

ساير عناصر نام

مینا

کد نقش

تهیه کننده

عنصر شناسه اي

‏ایمانی نبیی ،

عنصر شناسه اي

جوانیان،

عنصر شناسه اي

احمدی شالی،

ساير عناصر نام

‏رامین

ساير عناصر نام

‏مهری

ساير عناصر نام

‏جعفر

تاريخ

استاد راهنما

تاريخ

استاد راهنما

تاريخ

استاد مشاور

عنصر شناسه اي

‏تبریز