Палачинка сортирање

Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци. За разлику од традиционалних алгоритама за сортирање, који покушавају да сортирају са што мање могуће поређења, циљ је да се сортира секвенца са што мање обртања. Ова операција може бити замишљена као гомила палачинки у којој је кориснику дозвољено да узме горњих k палачинки и обрне их. Постоји варијација проблема која се тиче “изгорених” палачинки, код које свака палачинка има једну изгорену страну и на крају свака палачинка мора завршити са изгореном страном окренутом ка дну.

Демонстрација главне операције. Спатула преврће горње три палачинке, а резултат је на слици испод. У проблему изгорених палачинки, њихове горње странице би сада биле изгорене уместо доњих.

Проблеми палачинки

Оригинални проблем палачинки

Максимални број окретања потребан да се сортира гомила од n палачинки је између (15/14)n и (18/11)n али тачна вредност још није позната.^[1]

Најједноставнији алгоритам палачинка сортирања захтева највише 2n−3 обртања. У овом алгоритму варијација сортирања селекцијом, доводимо на врх највећу палачинку која још није сортирана једним обртањем и онда је одводимо доле на њену коначну позицију још једним обртањем, а онда понављамо поступак за остатак палачинки. Приметите да не меримо време потребно за проналазак највеће палачинке већ само број обртања; да смо желели да направимо реалну машину која извршава овај алгоритам у линерном времену, морала би да извршава замену префикса(обртање) и проналажење максимума бројева у низу у константном времену.

17. септембра 2008. године тим истраживача са Тексашког Универзитета у Даласу предвођени професором Хал Судбороу-ом најавио је прихватање ефикаснијег алгоритма за палачинка сортирање од алгоритма предложеног од стране Гејтса и Пападимитроуа у журналу Теоретска Информатика.^[2] Ово побољшање остварује горњу границу од (18/11)n у односу на претходну границу од (5/3)n из 1979.^[3][4]

2. новембра 2011. године рад је послат у arXiv који најављује да је проблем NP-тежак^[5] и тако одговорио на питање отворено више од три деценије. Битно је приметити да се NP-тежак проблем састоји од израчунавања минималног броја окретања потребно да се сортира n палачинки, а не само сортирање палачинки. Као напоменуто изнад, сортирање се може тривијално израчунати у времену O(n), које тај проблем смешта у полиномијалну класу проблема.

Проблем изгорених палачинки

У тежој варијацији проблема званој проблем изгорених палачинки, дно сваке палачинке на гомили је изгорено и сортирање мора да заврши са сваком палачинком са изгореном страном окренуто ка доле. 2008. године група студената направила је “бактеријски рачунар” који израчунава једноставни пример проблема програмирајући “ешерихију коли” да обрће делове ДНК, што је аналогно изгореним палачинкама.^[6][7] ДНК има оријентацију (5' и 3') и правило (промотер пре кодирања). Иако је снага процесирања изражена преко ДНК мала, велики број бактерија у култури даје велику сличност платформи за израчунавање. Извештаји о бактеријама након решавања проблема постајући имуни на антибиотике.^[8] Анимација која описује овај процес је направљена.^[9]

Проблем палачинки на нискама

Претходна дискусија подразумева да је свака палачинка јединствена тј. никоје две нису идентичне. Тако да је секвенца на којој се врши обртање префикса пермутација, тј. секвенца у којој се сваки симбол појављује тачно једном. Међутим “ниске” су секвенце у којима симболи могу да се понављају. Chitturi и Sudborough (2010) и Hurkens et al. (2007) су независно показали да је сложеност трансформисања компатибилне ниске у другу заменом префикса NP-комплетан проблем. Hurkens et al. су дали истоветан алгоритам за сортирање бинарних и тернарних ниски. Chitturi (2011) је доказао да је сложеност трансформирања компатибилне означене ниске у другу помоћу обртања префикса тј. проблем изгорених палачинки на нискама, такође NP-комплетан проблем.

Историјат

Иако више оруђе за образовање, палачинка сортирање се појављује у апликацијама за паралелно процесиране мреже, у којима може да допринесе ефектан алгоритам за рутирање између процесора.^{[тражи се извор]}

Проблем је препознатљив као једини широко познати математички рад написан од стране оснивача Microsoft-а Bill Gates-а, назван "Bounds for Sorting by Prefix Reversal". Објављен 1979. године, даје ефикасан алгоритам за палачинка сортирање.^[2] Такође један од познатих радова од стране ко-креатора Футураме David X. Cohen који се тиче проблема изгорених палачинки.^[10] Њихови сарадници су били Christos Papadimitriou и Manuel Blum респективно.

Повезани проблеми означеног сорирања обртањем и сортирања обртањем су поменута у скорије време. Где је ефикасност истих алгоритама пронађена од стране, за означено сортирање обртањем [Kaplan, Shamir, Tarjan, 1997],^[11] а проблем сортирања обртањем је доказан да је тежак за апроксимизацију чак и за одређене константне факторе[Berman, Karpinski, 1999],^[12] и доказано да је приближан полиномијалном времену у приближавајућем фактору 1.375[Berman, Karpinski, Hannenhalli, 2002].^[13]

Повезане секвенце целих бројева

Број гомила одређене висине којима је потребно N обртања за сортирање

Висина	N
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	1
2	1	1
3	1	2	2	1
4	1	3	6	11	3
5	1	4	12	35	48	20
6	1	5	20	79	199	281	133	2
7	1	6	30	149	543	1357	1903	1016	35
8	1	7	42	251	1191	4281	10561	15011	8520	455
9	1	8	56	391	2278	10666	38015	93585	132697	79379	5804
10	1	9	72	575	3963	22825	106461	377863	919365	1309756	814678	73232
11	1	10	90	809	6429	43891	252737	1174766	4126515	9981073	14250471	9123648	956354	6
12	1	11	110	1099	9883	77937	533397	3064788	14141929	49337252	118420043	169332213	111050066	13032704	167

Секвенце из The Online Encyclopedia of Integer Sequences од стране Neil Sloane:

•  A058986 – максимални број обртања
•  A067607 – број гомила којима је потребан максимални број обртања (изнад)
•  A078941 – максимални број обртања за “изгорену” гомилу
•  A078942 – број обртања за сортирану гомилу “ изгорене стране на врху”
•  A092113 – троугао изнад читан по редовима