팬케이크 분류

Pancake sorting
1차 작동 시연. 주걱이 아래 보이는 결과를 가지고 세 개의 팬케이크 위에 뒤집혀 있다. 불에 탄 팬케이크 문제에서, 그들의 윗면은 이제 아랫면 대신 불에 탔을 것이다.

팬케이크 분류는 주걱을 스택의 어느 지점에서나 삽입할 수 있고 그 위에 있는 팬케이크를 뒤집는데 사용될 수 있는 크기 순으로 정렬하는 수학적 문제다. 팬케이크 번호는 주어진 팬케이크 수에 필요한 최소 플립 수입니다. 이 형태에서, 이 문제는 미국 측지계 제이콥 E에 의해 처음 논의되었다. 굿맨.[1] 문제의 변형은 불에 탄 팬케이크와 관련이 있는데, 팬케이크는 각각의 팬케이크가 불에 탄 면이 있고, 게다가 모든 팬케이크는 결국 바닥에 불에 탄 면이 되어야 한다.

모든 정렬 방법에는 비교할 요소 쌍이 필요하다. 전통적인 정렬 문제의 경우, 일반적인 문제는 목록을 정렬하는 데 필요한 비교 횟수를 최소화하는 것이다. 두 요소의 스와핑과 같은 실제 운용 횟수는 그때와 무관하다. 반대로 팬케이크 정렬 문제의 경우, 목적은 작업 수를 최소화하는 것이며, 여기서 유일하게 허용된 작업은 시퀀스의 일부 접두사 요소의 역방향이다. 이제 비교 횟수는 상관이 없다.

팬케이크 문제

원래 팬케이크 문제

대칭의 최소 숫자와 팬 케이크의 스택 정리하는 데 필요한.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{사이에 있는 것으로 나타났다.디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}15/14n과 18/11n(대략 1.07n과 1.64n,)지만 정확한 가치를 알지 않다.[2]

가장 간단한 팬케이크 정렬 알고리즘은 최대 2n - 3플립으로 수행된다. 이 알고리즘에서, 일종의 선택 종류인, 우리는 아직 정렬되지 않은 가장 큰 팬케이크를 한 번 더 뒤집어서 맨 위에 가져오고, 한 번 더 뒤집어서 마지막 위치로 가져가고, 남은 팬케이크에 대해 이 과정을 반복한다.

1979년 빌 게이츠와 크리스토스 파파디미트리오가[3] 1.06n의 하한과 (5n+5)/3의 상한을 주었다. 창업자 할 수드버러 교수가 이끄는 댈러스 텍사스대 연구팀에 의해 30년 후 상한선이 18/11n으로 개선되었다.[4][5]

2011년, Laurent Bulteau, Guillaume Pertin, Irena Russu는[6] 주어진 팬케이크 스택에 대한 최단 순서의 플립을 찾는 문제가 NP-hard라는 것을 증명하여, 30년 넘게 열려온 질문에 대답하였다.

불에 탄 팬케이크 문제

불에 탄 팬케이크 문제라는 변형에서, 더미의 각 팬케이크 바닥은 불에 탔으며, 모든 팬케이크의 불에 탄 면을 아래로 한 채 분류가 완료되어야 한다. 서명한 순열로 팬케이크에 불이 붙으면 음의 요소를 대신해서 순열한다. 2008년, 한 학부생들이 불에 탄 팬케이크와 유사한 DNA 조각들을 뒤집도록 대장균을 프로그래밍함으로써 팬케이크 문제의 간단한 예를 해결할 수 있는 박테리아 컴퓨터를 만들었다. DNA는 방향(5'와 3')과 주문(코딩 전 홍보자)을 가지고 있다. DNA 플립에 의해 표현되는 처리 능력은 낮지만, 한 문화에서 많은 수의 박테리아가 대규모 병렬 컴퓨팅 플랫폼을 제공한다. 그 박테리아는 항생제 내성이 되어 문제를 해결했을 때 보고한다.[7]

똑같은 팬케이크 스택 문제

이것은 인도의 빵(로티 또는 차파티)이 요리되는 방식에서 영감을 얻은 것이다. 처음에는 모든 로티스가 한 칸에 쌓여 있고, 요리사는 주걱을 사용하여 로티스를 뒤집어서 각 로티의 각 면이 어느 시점에 베이스 불에 닿아 토스트를 하게 된다. 로티스는 단면 또는 양면으로 간주될 수 있으며, 같은 면을 두 번 굽는 것이 금지되거나 금지될 수 있다. 이 문제의 버전은 Arka Roychowdhury에 의해 처음 탐구되었다.[8]

현에 있는 팬케이크 문제

위의 논의에서는 각 팬케이크가 고유하다고 가정하며, 즉 접두사 반전이 수행되는 순서는 순열이라고 가정한다. 그러나 "스트링"은 기호가 반복될 수 있는 시퀀스로, 이 반복은 정렬에 필요한 접두사 반전 횟수를 줄일 수 있다. 치투리와 수드버러(2010년)와 허켄스 외 연구진. (2007) 독립적으로 최소 접두사 반전 횟수로 호환되는 문자열을 다른 문자열로 변환하는 복잡성은 NP-완전하다는 것을 보여주었다. 그들은 또한 같은 것에 대해 한계를 부여했다. 허켄스 등은 2진수 문자열과 3진수 문자열을 정렬하기 위한 정확한 알고리즘을 부여했다. Chitturi[9](2011년)는 호환되는 서명된 문자열을 서명된 최소 접두사 반전 횟수와 함께 다른 문자열로 변환하는 복잡성이 NP-완전하다는 것을 증명했다.

역사

팬케이크 분류 문제는 제이콥 E에 의해 처음 제기되었다. Goodman, "Harry Dweater"라는 필명으로 글을 쓴다.[10]

교육용 기기로 더 자주 보여지지만, 팬케이크 정렬은 프로세서 간 효과적인 라우팅 알고리즘을 제공할 수 있는 병렬 프로세서 네트워크의 애플리케이션에서도 나타난다.[11][12]

이 문제는 마이크로소프트 창업자 빌 게이츠(윌리엄 게이츠)가 '접두사 역전별 분류법'이라는 제목으로 크리스토스 파파디미트리오와 공동 집필한 유일한 잘 알려진 수학 논문의 주제로 주목할 만하다. 1979년에 출판된 이 책은 팬케이크 분류에 대한 효율적인 알고리즘을 설명한다.[3] 게다가 퓨처라마 공동창작자 데이비드 X가 발표한 가장 주목할 만한 논문도 있다. 코헨(David S. 마누엘 블럼과 공동 저자인 코헨은 불에 탄 팬케이크 문제를 우려했다.[13]

역순으로 서명한 분류와 역순으로 정렬하는 것과 연관된 문제 또한 최근에 더 연구되었다. 역순으로 서명된 정렬에 대해 효율적인 정확한 알고리즘이 발견된 반면,[14] 역순으로 정렬하는 문제는 특정 상수 요인 내에서 근사치조차 어려운 것으로 입증되었으며,[15] 근사치 계수 1.375 내에서 다항식 시간 내에 근사치인 것으로도 입증되었다.[16]

팬케이크 그래프

팬케이크 그래프3 P
팬케이크 그래프 P는4 각 카피에 접미사로 {1, 2, 3, 4} 세트와 다른 요소를 할당하여 4장의3 P 복사본에서 반복적으로 구성할 수 있다.
주요기사 : 팬케이크 그래프

n-판케이크 그래프는 1에서 n까지의 n 기호의 순열이며 접두사 역순으로 전이되는 순열 사이에 가장자리가 주어지는 그래프를 말한다. 그것은 정점이 n!인 정규 그래프인데, 그것의 정도는 n-1이다. 팬케이크 분류 문제와 팬케이크 그래프의 직경을 구하는 문제는 동일하다.[17]

치수 n, P의n 팬케이크 그래프는 각 사본의 접미사로 세트 {1, 2, …, n}과 다른 요소를 할당하여 P의n−1 n개 복사본으로부터 재귀적으로 구성할 수 있다.

둘레:

( )= > 인경우.

P의n γ(Pn) 속은 다음과 같다.[18]

팬케이크 그래프는 그래프 크기에 비해 대칭 및 재귀 구조, 작은 도, 직경 등 흥미로운 특성이 많기 때문에 병렬 컴퓨터를 위한 상호접속 네트워크 모델로 많은 관심이 쏠린다.[19][20][21] 팬케이크 그래프를 상호연결망의 모델로 간주할 때, 그래프의 지름은 통신 지연을 나타내는 척도다.[22][23]

팬케이크 그래프는 Cayley 그래프(정점-변환성)이며, 병렬 처리에 특히 매력적이다. 그들은 하위 로그 정도와 직경을 가지고 있고 상대적으로 희박하다(예: 하이퍼큐브와 비교).[18]

알고리즘.

팬케이크 분류 알고리즘의 예는 아래에 Python에 제시되어 있다.

반항하다 뒤집다(arr, k):     남겨진 = 0     하는 동안에 남겨진 < k:         arr[남겨진], arr[k] = arr[k], arr[남겨진]         k -= 1         남겨진 += 1  반항하다 max_index(arr, k):     색인을 달다 = 0     을 위해 i 에 범위(k):         만일 arr[i] > arr[색인을 달다]:             색인을 달다 = i     돌아오다 색인을 달다  반항하다 팬케이크_케이크(arr):     n = 렌(arr)     하는 동안에 n > 1:         맥스덱스 = max_index(arr, n)         뒤집다(arr, 맥스덱스)         뒤집다(arr, n - 1)         n -= 1  아레글로 = [15, 8, 9, 1, 78, 30, 69, 4, 10] 팬케이크_케이크(아레글로) 인쇄하다(아레글로)

관련 정수 시퀀스

고유한 플립 k가 필요한 지정된 높이 n의 스택 수
높이
n		 k
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
13 1 12 132 1451 14556 130096 1030505 7046318 40309555 184992275 639783475 1525125357 2183056566 1458653648 186874852 2001

온라인 정수 백과사전 시퀀스:

  • OEIS: A058986 – 최대 플립 수
  • OEIS: A067607 – 최대 플립 수가 필요한 스택 수(위)
  • OEIS: A078941 – "연소" 스택에 대한 최대 플립 수
  • OEIS: A078942 – 정렬된 "번트-사이드-온-탑" 스택에 대한 플립 수
  • OEIS: A092113 – 위 삼각형, 행으로 판독

[9]

참조

  1. ^ Singh, Simon (November 14, 2013). "Flipping pancakes with mathematics". The Guardian. Retrieved March 25, 2014.
  2. ^ Fertin, G.; Labarre, A.; Rusu, I.; Tannier, E.; Vialette, S. (2009). Combinatorics of Genome Rearrangements. The MIT Press. ISBN 9780262062824.
  3. ^ a b Gates, W.; Papadimitriou, C. (1979). "Bounds for Sorting by Prefix Reversal" (PDF). Discrete Mathematics. 27: 47–57. doi:10.1016/0012-365X(79)90068-2. Archived from the original (PDF) on June 10, 2007. Retrieved March 31, 2007.
  4. ^ "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. Archived from the original on April 5, 2012. Retrieved November 10, 2008. A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.
  5. ^ Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, C. O.; Sudborough, I. H.; Voit, W. (August 31, 2009). "An (18/11)n upper bound for sorting by prefix reversals". Theoretical Computer Science. Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday. 410 (36): 3372–3390. doi:10.1016/j.tcs.2008.04.045.
  6. ^ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv:1111.0434. doi:10.1016/j.jcss.2015.02.003.
  7. ^ Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Heard, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J; Poet, Jeffrey L (2008). "Engineering bacteria to solve the Burnt Pancake Problem". Journal of Biological Engineering. 2: 8. doi:10.1186/1754-1611-2-8. PMC 2427008. PMID 18492232.
  8. ^ Roychowdhury, Arka (March 18, 2015). "Itunes: Flipping Pancakes". Crazy1S.
  9. ^ a b Chitturi, Bhadrachalam (2011). "A NOTE ON COMPLEXITY OF GENETIC MUTATIONS". Discrete Mathematics, Algorithms and Applications. 03 (3): 269–286. doi:10.1142/S1793830911001206.
  10. ^ Dweighter, Harry (1975), "Elementary Problem E2569", Amer. Math. Monthly, 82 (10): 1009–1010, doi:10.2307/2318260, JSTOR 2318260
  11. ^ Gargano, L.; Vaccaro, U.; Vozella, A. (1993). "Fault tolerant routing in the star and pancake interconnection networks". Information Processing Letters. 45 (6): 315–320. CiteSeerX 10.1.1.35.9056. doi:10.1016/0020-0190(93)90043-9. MR 1216942..
  12. ^ Kaneko, K.; Peng, S. (2006). "Disjoint paths routing in pancake graphs". Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). pp. 254–259. doi:10.1109/PDCAT.2006.56. ISBN 978-0-7695-2736-9. S2CID 18777751..
  13. ^ Cohen, D.S.; Blum, M. (1995). "On the problem of sorting burnt pancakes". Discrete Applied Mathematics. 61 (2): 105. doi:10.1016/0166-218X(94)00009-3.
  14. ^ Kaplan, H.; Shamir, R.; Tarjan, R.E. (1997). "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals". Proc. 8th ACM-SIAM SODA: 178–87.
  15. ^ Berman, P.; Karpinski, M. (1999). "On Some Tighter Inapproximability Results". Proc. 26th ICALP (1999) LNCS 1644: 200–09.
  16. ^ Berman, P.; Karpinski, M.; Hannenhalli, S. (2002). "1.375-Approximation Algorithms for Sorting by Reversals". Proc. 10th ESA (2002), LNCS 2461: 200–10.
  17. ^ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (September 1, 2006). Computing the Diameter of 17-Pancake Graph Using a PC Cluster. Euro-Par 2006 Parallel Processing: 12th International Euro-Par Conference. Lecture Notes in Computer Science. 4128. pp. 1114–1124. doi:10.1007/11823285_117. ISBN 978-3-540-37783-2.
  18. ^ a b Nguyen, Quan; Bettayeb, Said (November 5, 2009). "On the Genus of Pancake Network" (PDF). The International Arab Journal of Information Technology. 8 (3): 289–292.
  19. ^ Akl, S.G.; Qiu, K.; Stojmenović, I. (1993). "Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry". Networks. 23 (4): 215–225. CiteSeerX 10.1.1.363.4949. doi:10.1002/net.3230230403.
  20. ^ Bass, D.W.; Sudborough, I.H. (March 2003). "Pancake problems with restricted prefix reversals and some corresponding Cayley networks". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX 10.1.1.27.7009. doi:10.1016/S0743-7315(03)00033-9.
  21. ^ Berthomé, P.; Ferreira, A.; Perennes, S. (December 1996). "Optimal information dissemination in star and pancake networks". IEEE Transactions on Parallel and Distributed Systems. 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681. doi:10.1109/71.553290.
  22. ^ Kumar, V.; Grama, A.; Gupta, A.; Karypis, G. (1994). Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings.
  23. ^ Quinn, M.J. (1994). Parallel Computing: Theory and Practice (second ed.). McGraw-Hill.

추가 읽기

외부 링크