Several aspects related to the combinatorial properties of heapsort are discussed in this thesis. A recursion formula for the number of heaps satisfying a given condition between any two offsprings with the same parent Is given and several properties of heaps are discussed Including a new algorithm to generate the set of all heaps of any size. Also In this work we define second order trees which have a great Importance In the study of the complexity of Williams’ algorithms to generate a heap. We discuss this kind of trees and we prove that the generating function of the number of trees satisfies a nonlinear differential difference equation. The numerical computation and the asymptotic expansion for a quantity related to this nonlinear differential difference equation Is given In this work . Finally, we give an upper bound for the number of the second order trees generated from the set of all heaps of size N where N has the form 2-1 for any positive integer k.
ترجمه فارسی (ترجمه ماشینی)
چندین جنبه مربوط به خواص ترکیبی heapsort در این پایان نامه مورد بحث قرار می گیرد. یک فرمول بازگشتی برای تعداد پشتههایی که شرایط معینی را برآورده میکنند بین هر دو فرزند با والدین یکسان ارائه شده است و چندین ویژگی پشتهها از جمله یک الگوریتم جدید برای تولید مجموعهای از همه پشتهها با هر اندازه مورد بحث قرار میگیرد. همچنین در این کار ما درختان مرتبه دوم را تعریف می کنیم که اهمیت زیادی در مطالعه پیچیدگی الگوریتم های ویلیامز برای تولید یک پشته دارند. ما در مورد این نوع درختان بحث می کنیم و ثابت می کنیم که تابع مولد تعداد درختان معادله اختلاف دیفرانسیل غیرخطی را برآورده می کند. محاسبات عددی و بسط مجانبی برای یک کمیت مربوط به این معادله اختلاف دیفرانسیل غیرخطی در این کار آورده شده است. در نهایت، ما یک کران بالایی برای تعداد درختان مرتبه دوم ایجاد شده از مجموعه همه پشتههای اندازه N میدهیم که در آن N برای هر عدد صحیح مثبت k شکل 2-1 دارد.
نقد و بررسیها
هنوز بررسیای ثبت نشده است.