عنوان

The pancake problem

شماره

TLpq304074675

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

انگلیسی

عنوان اصلي

The pancake problem

نام عام مواد

[Thesis]

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

M. H. Heydari

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

I. H. Sudborough

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

The University of Texas at Dallas

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

1993

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

162

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

Ph.D.

کسي که مدرک را اعطا کرده

The University of Texas at Dallas

امتياز متن

1993

متن يادداشت

The pancake problem concerns the maximum, over all positive integers n, of the number of prefix reversals required to sort a sequence of length n. It also corresponds to the diameter of the so-called pancake network, i.e. the maximum, over all nodes x and y, of the distance between x and y. The n-dimensional pancake network is the interconnection network for parallel computation having processors labeled with each of n! distinct permutations of length n and an edge between two processors when one processor's label is obtained from the other by a prefix reversal. Let f(n) represent the diameter of the pancake network of dimension n or, equivalently, the number of prefix reversals required to sort sequences of length n. Values of f(n) for usdn\le 9usd were given previously in the literature. We compute values of f(n) for usd10\le n\le 13usd and show, for example, that usdf(19)\ge 22.usd We describe a usd{9\over 8}n+2usd step sorting sequence for Gates and Papadimitriou's unburnt stack of pancakes, usd\chi\sb{n},usd thus disproving their conjecture that usd{19\over 16}nusd steps are required. We improve the lower bound, for the diameter of unburnt pancakes, by showing that usdf(n)\ge{15\over 14}n.usd In fact, we define a class of permutations of usd1,\...,n,usd denoted by usd\varphi\sb{n}usd (similar to usd\chi\sb{n})usd and show that usd{15\over 14}n\le f(\varphi\sb{n})\le{8\over 7}n - 1,usd thus improving the bounds given by Gates and Papadimitriou (10). We prove that the Pancake Sorting Problem, a problem motivated by the basic pancake problem, is NP-complete. This suggests that optimum routing in the pancake network is NP-hard. On the other hand, we prioritize the steps in (10) for sorting and introduce new rules to achieve quite good, experimental, results. In fact, we achieve routing in an average (experimentally) of approximately 118 steps in the dimension 100 pancake network. This seems to suggest that routing can be done in a number of steps close to the diameter by simple heuristics, even though the optimum routing is very hard. That is, it suggests routing can be achieved in an average of 1.18n steps. We show that the conjectured hardest stack of burnt pancakes, usd-I\sb{n},usd can be sorted in usd{3(n+1)\over 2}usd steps, for all usdn\equiv 3usd(mod 4) with usdn\ge 23.usd If usd-I\sb{n}usd is indeed hardest, then both the "burnt" and "unburnt" pancake networks of dimension n have diameter at most usd{3(n+1)\over2}.usd This bound is tight, as Cohen and Blum, (5), prove that usd{3\over 2}nusd steps are required to sort usd-I\sb{n}.usd

موضوع مستند نشده

Applied sciences

موضوع مستند نشده

Computer science

موضوع مستند نشده

prefix reversals

مستند نام اشخاص تاييد نشده

I. H. Sudborough

مستند نام اشخاص تاييد نشده

M. H. Heydari

نام الکترونيکي

فرمت انتشار

p

نوع ماده

[Thesis]

کد کاربرگه

276903

سطح دسترسي

a

تكميل شده

Y