Қоспалардың ретін келтіру мәселесі немесе тапанша пісіру есептері
Pancake sorting
Қалыпты дөңгелектерді пішімдеу математикалық есеп. Палашықтарды өлшем бойынша реттеу үшін қажетті ең аз қозғалыс саны – "палашық саны". Бүршіктелгендер де қарастырылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық есеп
Mathematics problem
Көкпар пісіруді сұрыптау – бұл көкпардың ретсіз үймегін мөлшері бойынша сұрыптаудың математикалық есебі, онда шпатель үймедегі кез келген нүктеге енгізіліп, одан жоғарыдағы барлық көкпарларды аударып тастауға болады. Көкпар саны – берілген көкпар саны үшін қажетті ең аз аудару саны. Бұл мәселені алғаш рет американдық геометр Джейкоб Э. Гудман талқылаған. Мәселенің бір түрі – күйген көкпарлар, онда әр көкпардың күйген жағы болады және барлық көкпарлардың күйген жағы төмен қарауы керек. Барлық сұрыптау әдістері элементтердің жұптарын салыстыруды қажет етеді. Традициялық сұрыптау есебі үшін әдетте зерттелетін мәселе – тізімді сұрыптау үшін қажетті салыстыру санын азайту. Екі элементті ауыстыру сияқты нақты операциялардың саны маңызсыз. Көкпар пісіруді сұрыптау есебі үшін керісінше, операциялар санын азайту мақсатында, рұқсат етілген операциялар тек тізбектің белгілі бір префиксінің элементтерін кері аудару болып табылады. Салыстыру саны маңызсыз.
Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. All sorting methods require pairs of elements to be compared. For the traditional sorting problem, the usual problem studied is to minimize the number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant. For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some prefix of the sequence. Now, the number of comparisons is irrelevant.
Жанып кеткен кеспек мәселесі
Жанып қалған кеспе проблемасы деп аталатын түрінде, үймедегі әрбір кеспесінің асты күйдірілген, ал сұрыптау әрбір кеспесінің күйген жағымен аяқталуы тиіс. Бұл – белгіленген пермутация, егер i кеспесі "күйген жағы жоғары" болса, пермутацияда i санының орнына теріс i саны қойылады. 2008 жылы студенттер тобы бактериялық компьютер құрастырып, E. coli бактериясын ДНК сегменттерін, жанып қалған кеспелерге ұқсас, аударуға бағдарламалау арқылы жанып қалған кеспе проблемасының қарапайым мысалын шеше алады. ДНК-ның бағыты (5' және 3') және реті (кодирование алдындағы промотор) болады. ДНК аударылысымен берілген өңдеу қуаты төмен болғанымен, мәдениеттегі бактериялардың көп саны үлкен параллельді есептеу платформасын қамтамасыз етеді. Бактериялар антибиотикке төзімділік көрсету арқылы проблеманы шешкендерін хабарлайды.
In a variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. It is a signed permutation, and if a pancake i is "burnt side up" a negative element i` is put in place of i in the permutation. In 2008, a group of undergraduates built a bacterial computer that can solve a simple example of the burnt pancake problem by programming E. coli to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform. The bacteria report when they have solved the problem by becoming antibiotic resistant.
Бірдей піскен тостаған проблемасы
Бұл үнді нанының (roti немесе chapati) пісірілу әдісінен шабыттандырылған. Алғашқыда, барлық ротилер бір бағанға жинақталады, ал аспаз шпательді пайдаланып ротилерді аударып, әр ротидің екі жағы да қыздыруға арналған отқа тиесілі болады. Әртүрлі нұсқалар мүмкін: ротилер бір жақты немесе екі жақты деп қарастырылуы мүмкін, сондай-ақ бір жақты екі рет қыздыруға рұқсат етілуі немесе тыйым салынуы мүмкін. Бұл мәселені алғаш зерттеген – Арка Ройчоудури.
This is inspired from the way Indian bread (roti or chapati) is cooked. Initially, all rotis are stacked in one column, and the cook uses a spatula to flip the rotis so that each side of each roti touches the base fire at some point to toast. Several variants are possible: the rotis can be considered as single sided or two sided, and it may be forbidden or not to toast the same side twice. This version of the problem was first explored by Arka Roychowdhury.
Сөйлемдердегі кеспек мәселесі
Жоғарыдағы талқылау әрбір панкейк ерекше екенін, яғни префикстің кері айналуы орындалатын реттілік – пермутация екенін қарастырады. Дегенмен, "тізбектер" – символдар қайталана алатын реттіліктер, ал мұндай қайталану сұрыптау үшін қажетті префикстік кері айналымдар санын азайтуы мүмкін. Chitturi and Sudborough (2010) және Hurkens және авторлар (2007) сәйкес тізбекті ең аз префикстік кері айналымдар санымен басқа тізбекке түрлендірудің қиындығы NP-толық екенін тәуелсіз түрде көрсетті. Олар сондай-ақ осыған қатысты шектеулерді берді. Hurkens және авторлар екілік және үштік тізбектерді сұрыптау үшін нақты алгоритм ұсынды. Chitturi (2011) үйлесімді белгіленген тізбекті ең аз белгіленген префикстік кері айналымдар санымен басқа тізбекке түрлендірудің қиындығы – тізбектердегі күйдірілген панкейк мәселесі – NP-толық екенін дәлелдеді.
The discussion above presumes that each pancake is unique, that is, the sequence on which the prefix reversals are performed is a permutation. However, "strings" are sequences in which a symbol can repeat, and this repetition may reduce the number of prefix reversals required to sort. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with the minimum number of prefix reversals is NP complete. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi (2011) proved that the complexity of transforming a compatible signed string into another with the minimum number of signed prefix reversals—the burnt pancake problem on strings—is NP complete.
Тарих
Панкейктерді сұрыптау мәселесін алғаш рет Джейкоб Гудман "Гарри Двейтер" ("асыққан официант") деген псевдониммен жазған. Көбінесе оқу құралы ретінде қолданылса да, панкейктерді сұрыптау параллель процессорлар желілерінде де қолданылады, онда процессорлар арасында тиімді маршруттау алгоритмін ұсынуға болады. Бұл мәселе Microsoft негізін қалаушы Билл Гейтстің (Уильям Гейтс ретінде) "Префикс бойынша кері реттеудің шектеулері" атты, Христос Пападимитриумен бірлескен жалғыз танымал математикалық еңбегінің тақырыбы болып табылады. 1979 жылы жарияланған бұл еңбекте панкейктерді сұрыптаудың тиімді алгоритмі сипатталған. Сонымен қатар, Futurama сериалының авторы Дэвид Коэн (Девид С. Коэн ретінде) Мануэль Блумпен бірлескен ең маңызды жұмысы күйген панкейк мәселесіне арналған. Кері реттеу арқылы белгіленген сұрыптау және кері реттеу арқылы сұрыптау сияқты байланысты мәселелер де соңғы кезде зерттелді. Кері реттеу арқылы белгіленген сұрыптау үшін тиімді нақты алгоритмдер табылды, бірақ кері реттеу арқылы сұрыптау мәселесінің тіпті белгілі бір тұрақты коэффициент шегінде жуықтау қиын екені дәлелденді, сонымен қатар, ол көпмүшелік уақытта 1,375 жуықтау коэффициентімен жуықтауға болатыны да дәлелденді.
The pancake sorting problem was first posed by Jacob E. Goodman, writing under the pseudonym "Harry Dweighter" ("harried waiter"). Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors. The problem is notable as the topic of the only well known mathematics paper by Microsoft founder Bill Gates (as William Gates), entitled "Bounds for Sorting by Prefix Reversal" and co authored with Christos Papadimitriou. Published in 1979, it describes an efficient algorithm for pancake sorting. In addition, the most notable paper published by Futurama co creator David X. Cohen (as David S. Cohen), co authored with Manuel Blum, concerned the burnt pancake problem. The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals, the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor, and also proven to be approximable in polynomial time to within the approximation factor 1.375.