Connecting Yule Process, Bisection and Binary Sezrch Tree via martingales
Chauvin , B . Rouault, A ص 89
 چكيده مطلب |
 |
|
ارتباطهاي جديدي بين برخي مارتينگلهايي را كه در مطالعه درخت دودويي با مساله دونيم سازي حاصل مي شود، ارائه مي كنيم در حالتي كه بر آنها در يك فضاي احتمال يك فرآيند شاخه اي دودويي زمان پيوسته مي نگريم.
|
|
|
| |
Profile Height of Random Binary Search Trees
Drmota , M ص 117
چكيده مطلب |
|
|
قصد اين مقاله بررسي نتايج اخير درباره خواص توزيعي درختهاي جستجوي دودويي تصادفي است. به ويژه نيم رخ و ارتفاع را در نظر مي گيريم.
|
|
|
| |
Compact Suffix Trees Resemble PATRICIA Tries: Limiting Distribution of the Depht
Jacquet , P , McVey , B , Szpankowski, W ص 139
چكيده مطلب |
|
|
درختهاي پسوند ساختارهاي داده هاي با بيشترين استفاده در الگوريتمهاي روي واژه ها هستند. در اين مقاله، ژرفاي يك درخت پسوند فشرده را، كه به درخت PAT هم موسوم است، تحت برخي فرضهاي احتمالاتي ساده در نظر مي گيريم. براي يك منبع بي حافظه اريب، ثابت مي كنيم كه توزيع حدي براي ژرفا در يك درخت PAT همانند توزيع حدي براي ژرفاي يك تراي PATRICIA است، اگر چه تراي PATRICIA از رشته هاي مستقل از لحاظ آماري ساخته مي شود. در نتيجه نشان مي دهيم كه توزيع حدي براي ژرفا در يك درخت PAT كه روي n پسوند ساخته مي شود، نرما است.
|
|
|
| |
One-Sided Interval Trees
Janson , S ص 149
چكيده مطلب |
|
|
پرداختي ديگر و توسيعي از چند نتيجه ايتو و محمود درباره درختهاي بازه اي يك طرفه ارائه مي كنيم. برهان ها بر نظريه تجديد استوارند و حالتي با تجديدهاي آميخته ضربي و جمعي را شامل مي شوند.
|
|
|
| |
Polya-Type Urn Models with Multiple Drawings
Johnson , N , Kotz , S , Mahmoud, H ص 165
چكيده مطلب |
|
|
توزيع، ميانگين، واريانس و برخي خواص حدي يك مدل آوند شامل گويهاي سفيد و قرمز را تحت برداشتهاي چند گانه تصادفي (با جايگذاري يا بدون جايگذاري) وارسي مي كنيم، زماني كه تعداد گويهاي سفيد و قرمزي كه افزوده مي شوند از برنامه اي تبعيت مي كنند كه به تعداد گويهاي سفيدي كه در هر برداشت انتخاب مي شوند، بستگي دارد.
|
|
|
| |
On the Average Height of b-Balanced Order Trees
kemp , R ص 175
چكيده مطلب |
|
|
درختي مرتب با ارتفاع b، h- متعادل است هرگاه همه برگهاي آن سطحي مانند l با h-b < l < h داشته باشند كه در آن حداقل يك برگ سطحي برابر با h-b دارد. براي n بزرگ، معادلهاي مجانبي براي تعداد همه درختهاي مرتب b - متعادل با n گروه و همچنين درختهايي به ارتفاع h را محاسبه مي كنيم. به علاوه، با فرض اينكه همه درختهاي مرتب b- متعادل با n گره هم شانس باشند، رفتار مجانبي دقيق ارتفاع متوسط چنان درختي را همراه با واريانس آن معين مي كنيم.
|
|
|
| |
Measuring Post-Quickselect Disorder
Panholzer , A , Prodinger, H , Riedel , M ص 219
چكيده مطلب |
|
|
اين مقاله به مقدار بي نظمي مي پردازد كه در يك جايگشت پس از آنكه يكي از عناصر آن با زودگزين يا زودگزين با يا بدون محورسازي ميانه سه انتخاب شده است، باقي مي ماند. پنج اندازه بي نظمي در نظر گرفته شده اند: وارون ها، دورهاي به طول عددي مانند m يا كمتر، دورهاي با طول دلخواه، اميد رياضي طول دوره، و فاصله جايگشت هماني. ميانگين ها كل براي هر اندازه بي نظمي براي يك جايگشت پس از آنكه يكي از عناصر آن با زودگزين انتخاب شد كه در آن 1،2،...n عنصر جايگشت داده شده اند، محاسبه شده اند و نيز نتايج مشخص تري به دست آمده اند.
|
|
|
| |
Periodic Oscillation in the Analysis of Algorithms and their Cancellation
Prodinger , H ص 251
|
 |
|
| |
Quickselect Revisited
Rosler, U ص 271
چكيده مطلب |
|
|
مروري كلي بر تحليل زمان اجراي الگوريتم متفرق كن - و - غلبه كن Find با QUICKSELECT ارائه مي كنيم. نتايج به اين موضوعات مي پردازند: گشتاورها، توزيع زمان اجراي Find، توزيع حدي، يك كردن تصادفي و كليد: يك معادله نقطه ثابت تصادفي.
|
|
|
| |
Probability Generating Functions for Sattolos Algorithm
Wilson, M. C. ص 297
چكيده مطلب |
|
|
در سال 1986 س. سانولوالگوريتم ساده اي را براي توليد تصادفي يكنواخت جايگشت هاي دوري روي تعداد ثابت از علامت ها معرفي كرد. اخيرا ه. پردينگر دو متغير تصادفي مرتبط با اين الگوريتم را مورد تحليل قرار و ميانگين و واريانس آنها را بدست آورد. ح. محمود تحليلي پردينگر را با يافتن توزيع هاي حد براي اين دو متغير تصادفي، بيشتر بود.
مقاله حاضر با شروع از تعريف الگوريتم، كاملا خود بسنده است. پس از ارائه برهان جديدي براي صحت، نتايج احتمالاتي فوق الذكر را با يقين تابع هاي مولد احتمال كل اين متغيرهاي تصادفي تعميم مي دهيم.
كانون توجه در سرتاسر مقاله، استفاده از روش هاي استاندارده است كه به رهيافت يكپارچه اي بينجامد، و باب مطالعه بيشتر را باز نمايد.
|
|
)
)
)
)
)
