کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871951 | 681683 | 2016 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Decision trees with minimum average depth for sorting eight elements
ترجمه فارسی عنوان
درختان تصمیم گیری با حداقل عمق متوسط برای مرتب سازی هشت عنصر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مرتب سازی، درخت تصمیم گیری، عمق متوسط،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that the minimum average depth of a decision tree for sorting 8 pairwise different elements is equal to 620160/8!. We show also that each decision tree for sorting 8 elements, which has minimum average depth (the number of such trees is approximately equal to 8.548Ã10326365), has also minimum depth. Both problems were considered by Knuth (1998). To obtain these results, we use tools based on extensions of dynamic programming which allow us to make sequential optimization of decision trees relative to depth and average depth, and to count the number of decision trees with minimum average depth.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 203-207
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 203-207
نویسندگان
Hassan AbouEisha, Igor Chikalov, Mikhail Moshkov,