Penyortiran panekuk

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Langsung ke: navigasi, cari
Demonstrasi operasi primer. Spatula sedang membalikkan tiga panekuk teratas, dengan hasilnya terlihat di bawah. Dalam masalah panekuk gosong, sisi atasnya akan terbakar, bukan sisi bawahnya.

Penyortiran panekuk adalah variasi masalah penyortiran yang satu-satunya operasi yang diperbolehkan adalah membalikkan elemen sejumlah prefiks urutan. Tidak seperti algoritma penyortiran lama, yang berusaha mengurutkan dengan perbandingan sesedikit mungkin, tujuan penyortiran ini adalah mengurutkan sebuah urutan dengan pembalikan sesedikit mungkin. Operasi ini dapat divisualisasikan dengan membayangkan tumpukan panekuk dan seseorang dibolehkan mengambil panekuk k di atas dan membalikannya. Ada satu varian masalah ini yang berkaitan dengan panekuk gosong, yaitu ketika setiap panekuk memiliki sisi gosong dan semua panekuk harus berakhir dengan sisi gosong di atasnya.

Referensi[sunting | sunting sumber]

Chitturi, B. and Sudborough, H. "Prefix reversals on strings". Proc. Int. Conf. Bioinformatics and Computational Biology, Vol. 2 (2010)591–598.

Hurkens, C., Iersel, L. V., Keijsper, J., Kelk, S., Stougie, L. and Tromp J. "Prefix reversals on binary and ternary strings". SIAM J. Discrete Math. 21(3)(2007) 592–611.

Chitturi, B. "A note on complexity of genetic mutations". DMAA 3(3) (2011)269-286 DOI:10.1142/S1793830911001206.

Bacaan lanjutan[sunting | sunting sumber]

  • Mohammad, H.H. and Hal Sudborough, I. "On the Diameter of the Pancake Network," Journal of Algorithms 25 (1), 67-94, 1997.
  • Roney-Dougal, C. and Vatter, V. "Of pancakes, mice and men," Plus Magazine 54, March 2010.

Pranala luar[sunting | sunting sumber]