Նրբաբլիթային տեսակավորում

Նրբաբլիթային տեսակավորում
Տեսակ	տեսակավորման ալգորիթմ

Նրբաբլիթային տեսակավորում (անգլ.՝ pancake sorting-ից) - տեսակավորման ալգորիթմ. Ալգորիթմում թույլատրվող միակ գործողությունը - հաջորդական տարրերի շրջումն է մինչև որևէ մի ինդեքս։ Ի տարբերություն ավանդական ալգորիթմների, որտեղ նվազեցվում է համեմատությունների թիվը, նրբաբլիթային տեսակավորման մեջ պահանջվում է կատարել որքան հնարավոր է քիչ շրջումներ։ Գործընթացը վիզուալ կարելի է ներկայացնել նրբաբլիթների բուրգի տեսքով, որը խառնում են գագաթից մի քանի բլիթ վերցնելով և շրջելով։

Ալգորիթմ

Ամենասովորական ալգորիթմը (տարբերակի տեսակավորումը) տալիս է ոչ ավել քան ${\displaystyle 2n-3}$ շրջում, սակայն պահանջվում է ամենամեծ տարրի փնտրումը։ Այս ալգորիթմի մեջ ընտրված տեսակավորման շեղումը հետևյալն է. մեկ շրջումով ամենամեծ դեռևս չտեսակավորված բլիթը ամենավերևում, այնուհետև ևս մեկ անգամ իջեցնում են նրա վերջնական դիրքին, հետո կրկնում այս գործողությունը մնացած բլիթների հետ։ Նկատի ունեցեք, որ մենք չենք հաշվում այն ժամանակը, որը անհրաժեշտ է ամենամեծ բլիթը գտնելու համար. հաշվում ենք միայն շրջումների թիվը։ Եթե մենք ցանկանում ենք ստեղծել իրական մեխանիզմ, որը կիրականացնի այս ալգորիթմը գծային ժամանակով, այն պետք է կատարի երկու բնորոշչի փոփոխություն(շրջում) և պետք է կարողանա գտնել հաստատուն թվերի շարքում առավելագույնին։

Օրինակ՝ ավելի քան 4 շրջում պահանջող կույտերից են (2,4,1,3), (3,1,4,2) և (4,2,3,1), որն էլ կարելի է կատարել (2,4,3,2), (2,3,4,2) և (2,3,2,4)-ի միջոցով։

Այրված նրբաբլիթի խնդիրը

Ավելի բարդ շեղումը կոչվում է այրված նրբաբլիթների խնդիր, կույտի մեջ յուրաքանչյուր բլիթի ներքևի մասը այրվում է տեսակավորումը պետք է ավարտվի յուրաքանչյուր բլիթի ներքևի մասի այրումով։ Վերը նշված պարզ ալգորիթմը ևս աշխատում է այս խնդրի համար, բայց ավելի արագ ալգորիթմ չկա։ 2008 թվականին ավարտական կուրսի ուսանողների միխումբ կառուցեց միկրոօրգանիզմների համակարգիչ, որը կարող է լուծել այրված նրբաբլիթի խնդրի մի պարզ օրինակ E. coli ծրագրավորման միջոցով՝ ԴՆԹ-ի հատվածների շրջումը, որը նման է այրված բլիթներին^[1][2][ԴՆԹ-ն ունի (5' և 3') ուղղվածություն և կարգ (խթանող նախքան կոդավորումը)։ Չնայած ԴՆԹ շրջումով արտահայտված հոսքի շրջումը ցածր է, մշակույթում գտնվող բակտերիաները ապահովում են մի մեծ զուգահեռ հաշվողական հարթակ։ Բակտերիան հաղորդում է, երբ ունենում է խնդրի լուծումը^[3]։ Այս գործընթացի անիմացիոն պատկերը չի արտադրվել^[4]։

Նրբաբլիթային տեսակավորումը հանդես է գալիս նաև ծրագրերի զուգահեռ մշակման ցանցերում, որտեղ այն կարող է ապահովել պրոցեսորների միջև արդյունավետ երթուղավորում։

Այս խնդիրը ուշագրավ է դարձել հայտնի մաթեմատիկոս՝ Microsoftը հիմնադիր Bill Gatesի (ինչպես Ուիլյամ Գեյթս) կողմից գրված հոդվածի միջոցով, որը կոչվում է «Բնորոշչի տեղափոխման միջոցով սահմանների տեսակավորում»։ Այն հրատարակվել է 1979 թ.-ին և բնութագրվում է որպես նրբաբլիթային տեսակավորման արդյունավետ ալգորիթմ^[5]։ Բացի այդ, ամենանշանավոր թուղթը հրատարակվել է Futurama համաստեղծող David X. Cohen (ինչպես Դավիթ Ս. Կոհեն) ի կողմից, որը վերաբերում էր այրված նրբաբլիթի խնդրին^[6]։ Դրա հայտնագործողներն են Christos Papadimitriou (այնուհետև Harvard, հիմա Berkeley) և Manuel Blum (հետո Berkeley, հիմա Carnegie Mellon University), համապատասխանաբար։

2008 թ.-ի սեպտեմբերի 17-ին University of Texas at Dallasի հետազոտողների մի խումբ Founders Professor Hal Sudboroughը հայտարարեց իր որոշումը Theoretical Computer Science ամսագրի միջոցով, որը տեսակավորման առավել արդյունավետ ալգորիթմ էր, քան Gates and Papadimitriou։

Ծանոթագրություններ

1. «Solving the Pancake Problem with an E. coli Computer». Արխիվացված է օրիգինալից 2012 թ․ ապրիլի 6-ին. Վերցված է 2011 թ․ մայիսի 22-ին.
2. «iHOP meets iGEM». Արխիվացված է օրիգինալից 2012 թ․ մարտի 9-ին. Վերցված է 2011 թ․ մայիսի 22-ին.
3. Haynes, K.A., et al. "Engineering bacteria to solve the Burnt Pancake Problem." Journal of Biological Engineering, 2(1), 8, 2008.
4. Creating Living Hardware Using Synthetic Biology
5. Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Արխիվացված 2007-06-10 Wayback Machine Discrete Mathematics, 27, 47-57, 1979.
6. Cohen D.S. և Blum, M. "On the problem of sorting burnt pancakes." Discrete Applied Mathematics, 61, 105-120, 1995.

Հավելյալ ընթերցում

• 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.

Արտաքին հղումներ

• Cut-the-Knot: Flipping pancakes puzzle, including a Java applet for the pancake problem and some discussion.
• Douglas B. West's "The Pancake Problems"
• Pancake sorting - from Mathworld
• Joris J.'s "Bounds for sorting by prefix reversal"
• Animation explaining the bacterial computer that can solve the burnt pancake problem.