کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951263 1441199 2017 20 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal-depth sorting networks
ترجمه فارسی عنوان
شبکه های مرتب سازی با عمق مطلوب
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We solve a 40-year-old open problem on depth optimality of sorting networks. In 1973, Donald E. Knuth detailed sorting networks of the smallest depth known for n≤16 inputs, quoting optimality for n≤8 (Volume 3 of “The Art of Computer Programming”). In 1989, Parberry proved optimality of networks with 9≤n≤10 inputs. We present a general technique for obtaining such results, proving optimality of the remaining open cases of 11≤n≤16 inputs. Exploiting symmetry, we construct a small set Rn of two-layer networks such that: if there is a depth-k sorting network on n inputs, then there is one whose first layers are in Rn. For each network in Rn, we construct a propositional formula whose satisfiability is necessary for the existence of a depth-k sorting network. Using an off-the-shelf SAT solver we prove optimality of the sorting networks listed by Knuth. For n≤10 inputs, our algorithm is orders of magnitude faster than prior ones.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 84, March 2017, Pages 185-204
نویسندگان
, , , , ,