مرجع مکعب روبیک 360

مقاله علمی در مورد روبیک - روبیک و ریاضی

رابطه بین ریاضی و روبیک
تحقیقات جدید رابطه بین مربع روبیک که در هر ردیف وجود دارد و حداکثر حرکاتی که میتوان ان را حل کرد نشان میدهد.
در اگوست 2010 ، 30 سال پس از اولین پیدایش روبیک یک تیم تحقیقاتی بین المللی نشان داد که بدون توجه به چگوگی scrsmbleکردن روبیک، روبیک میتواند در 20 حرکت یا کمتر از ان حل شود. اگرچه دانشمندان از ترفند های هوشمندانه استفاده کردند تا از ارزیابی43 کوئینتیلون (quintilon= عدد یک با 18 صفر به توان 2) موقعیت شروع اولیه جلوگیری کنند اما شواهد انها هنوز وابستگی به برابری ارزش محاسبه عدد 35 ساله را به یک کامپیوتر مدرن خوب نشان نشان میداد.
متاسفانه برای روبیک های بزرگتر از 3*3 کیفیت حل کردن موقعیت شروع ممکن است فراتر از ظرفیت همه ی کامپیوترهای دنیا باشد.متاسفانه برای روبیک های بزرگتر از 3*3 کیفیت حل کردن موقعیت شروع ممکن است فراتر از ظرفیت همه ی کامپیوترهای دنیا باشد. اما در یک تحقیق موجود در قرن 19 در کنفرانس سالانه الگوریتم در اروپا در ماه سپتامبر،محققانی از MIT و دانشگاه واترلو و دانششگاه تافز رابطه ریاضی بین تعداد روبیک ها در یک روبیک و حداکثر تعداد حرکاتی که برای حل روبیک لازم است را ثابت کردند. شواهد متد انها همچنین یک الگوریتم کارامد را برای حل کردن هر روبیکی حتی در بدترین شرایط گسترش داد.
عتم کامپیوتر همیشه با این سوال درگیر بود که چه مدتی الگوریتم طول میکشد تا اجرا شود. اما دانشمندان کامپیوتر جواب این سوال را در رابطه با تعداد عناصری که ان الگوریتم باید بر اساس ان کار کند اندازه گیری کردند. زمان اجرای یک الگوریتم که بزرگترین عدد مجموعه را بررسی میکند به تعداد اعداد ان لیست بستگی دارد.
یک الگوریتم DUMB برای تعیین نوع کردن اعداد در یک لیست از کوچک به بزرگ، زمان اجرایش بستگی به مربع طول لیست دارد.

[تصویر: demaine1.jpg]


.راه حل با یک چرخش
ارک دماین یک استادیار علم کامپیوتر و مهندسی و پدزش مارتین دماین یک استاد موقت در بخش کامپیوتر و هوش مصنوعی MIT است.

او سارا ایسنستات و انا لوبیو را فارغ التحصیل کرد که راهنمای تز دکترای دماین در دانشگاه واترلو و تافز بود که اندرو ویلسلو را فارغ التحصیل کرد که او نشان داد که رابطه حداکثر حرکات لازم برای حل یک روبیک با N مربع برابر در هر ردیف متناسب است با n2/log n. (منظور n به توان 2 است)

ودماین میگوید جواب این است نه n 2 (منظور n به توان 2 است) , و این سورپرایز کننده است.

دماین توضیح میدهد استاندارد ترین راه برای حل یک روبیک این است که مربع های خارج از موقعیت را پیدا کنیم و انرا حرکت بدهیم تا در جای درستش قرار بگیزد در شرایطی که بقیه مربع ها تغییر بسیار کمی داشته باشند. این روش حتی روبیک هایی در بدترین شرایط را هم حل کرد که با فرمول N2 (منظور n به توان 2 است) متناسب است. دماین و همکارانش تشخیص دادند که تحت شرایط خاصی یک توالی چرخش منفرد میتواند چندین مربع را به جای درستشان حرکت دهد و تعداد کل حرکات را کم کند.
اما پیدا کردن یک توضیح ریاضی برای این و پیدا کردن این که چگونه این حالات در شرایطی ظاهر میشوند که روبیک در بدترین شرایط است، اسان نبود. در ساعت اول ما دیدیم که تعداد حرکات حداقل N2/logn است اما تنها چند ماه قبل توانستیم ثابت کنیم که N2/log n حرکت کافی است.

[تصویر: cubes.jpg]



چون روش انالیز انها چندین مربع را که میتوانند بطور همزمان در یک مکان باشند توضیح میداد،
در نتیجه راهی برای گسترش تشخیص ان نمونه ها و بنابراین الگوریتمی برای حل کردن روبیک های مشکل دار را ارائه داد.
الگوریتم همیشه خوب کار نمیکند و گاهی چند حرکت اضافی لازم است اما هرچه روبیک بزرگتر باشد این حرکات اضافی کمتر لازم است.
سازمان دهی کردن
روبیک یک مثال برای چیزی است که مشکل سازمان دهی نامیده میشود.
بهترین مثال برای سازماندهی کردن جعبه ها در انبار های بسیار بزرگ. دماین میگوید روش حل روبیک او برای سازماندهی انگونه شرایط میتواند مطابقت داده شود.
اما دماین همچنین یک مخالف سرسخت این نظر است که میگوید مطالعات حتما باید کاربرد و تقاضا داشته باشد. او میگوید تمام عمرم را صرف حل مسائلی کردم که به نظرم جالب بودند.و همیشه سخت است که بگوییم در همان زمان کاربرد عملی داشتند. مطالعه اعداد اولیه تا مدتها یک تفریح بود تا اینکه سالها بعد علم رمز نگاری بوجود امد. او میگوید علاوه بر تحقیق در مورد مسائل جالب باید در مورد مسائل ساده ههم تحقیق کرد. او میگوید احتمال اینکه مسایل ساده ریاضی در اینده مورد استفاده عملی قرار بگیرند بیشتر است و روبیک بهترین مثال برای این شرایط است.

[تصویر: rubiks-group.jpg]



مارک ون کریول استاد یار بخش اطلاعات و علم کامپیوتر دانشگاه اوترتچ هلند میگوید دماین همیشه علاقه دارد مسائل محبوب ریاضی را گسترش دهد و نشان دهد که ریاضیات تنها یک علم خسته کننده نیست بلکه بسیار جالب است.
مارک کریول میگوید اریک دماین فوق العاده است. او هم در زمینه ی مطالعات علمی جدی و هم در زمینه ی محبوب تر کردن علم ریاضی برای همه ی مردم تلاش بسیار میکند


رابطه بین ریاضی و روبیک
تحقیقات جدید رابطه بین مربع روبیک که در هر ردیف وجود دارد و حداکثر حرکاتی که میتوان ان را حل کرد نشان میدهد.
در اگوست 2010 ، 30 سال پس از اولین پیدایش روبیک یک تیم تحقیقاتی بین المللی نشان داد که بدون توجه به چگوگی scrsmbleکردن روبیک، روبیک میتواند در 20 حرکت یا کمتر از ان حل شود. اگرچه دانشمندان از ترفند های هوشمندانه استفاده کردند تا از ارزیابی43 کوئینتیلون (quintilon= عدد یک با 18 صفر به توان 2) موقعیت شروع اولیه جلوگیری کنند اما شواهد انها هنوز وابستگی به برابری ارزش محاسبه عدد 35 ساله را به یک کامپیوتر مدرن خوب نشان نشان میداد.
متاسفانه برای روبیک های بزرگتر از 3*3 کیفیت حل کردن موقعیت شروع ممکن است فراتر از ظرفیت همه ی کامپیوترهای دنیا باشد.متاسفانه برای روبیک های بزرگتر از 3*3 کیفیت حل کردن موقعیت شروع ممکن است فراتر از ظرفیت همه ی کامپیوترهای دنیا باشد. اما در یک تحقیق موجود در قرن 19 در کنفرانس سالانه الگوریتم در اروپا در ماه سپتامبر،محققانی از MIT و دانشگاه واترلو و دانششگاه تافز رابطه ریاضی بین تعداد روبیک ها در یک روبیک و حداکثر تعداد حرکاتی که برای حل روبیک لازم است را ثابت کردند. شواهد متد انها همچنین یک الگوریتم کارامد را برای حل کردن هر روبیکی حتی در بدترین شرایط گسترش داد.
عتم کامپیوتر همیشه با این سوال درگیر بود که چه مدتی الگوریتم طول میکشد تا اجرا شود. اما دانشمندان کامپیوتر جواب این سوال را در رابطه با تعداد عناصری که ان الگوریتم باید بر اساس ان کار کند اندازه گیری کردند. زمان اجرای یک الگوریتم که بزرگترین عدد مجموعه را بررسی میکند به تعداد اعداد ان لیست بستگی دارد.
یک الگوریتم DUMB برای تعیین نوع کردن اعداد در یک لیست از کوچک به بزرگ، زمان اجرایش بستگی به مربع طول لیست دارد.

[تصویر: demaine1.jpg]


.راه حل با یک چرخش
ارک دماین یک استادیار علم کامپیوتر و مهندسی و پدزش مارتین دماین یک استاد موقت در بخش کامپیوتر و هوش مصنوعی MIT است.

او سارا ایسنستات و انا لوبیو را فارغ التحصیل کرد که راهنمای تز دکترای دماین در دانشگاه واترلو و تافز بود که اندرو ویلسلو را فارغ التحصیل کرد که او نشان داد که رابطه حداکثر حرکات لازم برای حل یک روبیک با N مربع برابر در هر ردیف متناسب است با n2/log n. (منظور n به توان 2 است)

ودماین میگوید جواب این است نه n 2 (منظور n به توان 2 است) , و این سورپرایز کننده است.

دماین توضیح میدهد استاندارد ترین راه برای حل یک روبیک این است که مربع های خارج از موقعیت را پیدا کنیم و انرا حرکت بدهیم تا در جای درستش قرار بگیزد در شرایطی که بقیه مربع ها تغییر بسیار کمی داشته باشند. این روش حتی روبیک هایی در بدترین شرایط را هم حل کرد که با فرمول N2 (منظور n به توان 2 است) متناسب است. دماین و همکارانش تشخیص دادند که تحت شرایط خاصی یک توالی چرخش منفرد میتواند چندین مربع را به جای درستشان حرکت دهد و تعداد کل حرکات را کم کند.
اما پیدا کردن یک توضیح ریاضی برای این و پیدا کردن این که چگونه این حالات در شرایطی ظاهر میشوند که روبیک در بدترین شرایط است، اسان نبود. در ساعت اول ما دیدیم که تعداد حرکات حداقل N2/logn است اما تنها چند ماه قبل توانستیم ثابت کنیم که N2/log n حرکت کافی است.

[تصویر: cubes.jpg]



چون روش انالیز انها چندین مربع را که میتوانند بطور همزمان در یک مکان باشند توضیح میداد،
در نتیجه راهی برای گسترش تشخیص ان نمونه ها و بنابراین الگوریتمی برای حل کردن روبیک های مشکل دار را ارائه داد.
الگوریتم همیشه خوب کار نمیکند و گاهی چند حرکت اضافی لازم است اما هرچه روبیک بزرگتر باشد این حرکات اضافی کمتر لازم است.
سازمان دهی کردن
روبیک یک مثال برای چیزی است که مشکل سازمان دهی نامیده میشود.
بهترین مثال برای سازماندهی کردن جعبه ها در انبار های بسیار بزرگ. دماین میگوید روش حل روبیک او برای سازماندهی انگونه شرایط میتواند مطابقت داده شود.
اما دماین همچنین یک مخالف سرسخت این نظر است که میگوید مطالعات حتما باید کاربرد و تقاضا داشته باشد. او میگوید تمام عمرم را صرف حل مسائلی کردم که به نظرم جالب بودند.و همیشه سخت است که بگوییم در همان زمان کاربرد عملی داشتند. مطالعه اعداد اولیه تا مدتها یک تفریح بود تا اینکه سالها بعد علم رمز نگاری بوجود امد. او میگوید علاوه بر تحقیق در مورد مسائل جالب باید در مورد مسائل ساده ههم تحقیق کرد. او میگوید احتمال اینکه مسایل ساده ریاضی در اینده مورد استفاده عملی قرار بگیرند بیشتر است و روبیک بهترین مثال برای این شرایط است.

[تصویر: rubiks-group.jpg]



مارک ون کریول استاد یار بخش اطلاعات و علم کامپیوتر دانشگاه اوترتچ هلند میگوید دماین همیشه علاقه دارد مسائل محبوب ریاضی را گسترش دهد و نشان دهد که ریاضیات تنها یک علم خسته کننده نیست بلکه بسیار جالب است.

مارک کریول میگوید اریک دماین فوق العاده است. او هم در زمینه ی مطالعات علمی جدی و هم در زمینه ی محبوب تر کردن علم ریاضی برای همه ی مردم تلاش بسیار میکند

متن انگلیسی:

Last August, 30 years after the Rubik’s cube first appeared, an international team of researchers proved that no matter how scrambled a cube got, it could be solved in no more than 20 moves. Although the researchers used some clever tricks to avoid evaluating all 43 quintillion of the cube’s possible starting positions, their proof still relied on the equivalent of 35 years’ worth of number crunching on a good modern computer.

Erik Demaine and his Rubik's cubes
Erik Demaine's collection of Rubik's cubes -type puzzles includes cubes with five, six, and seven squares to a row, as well as one of the original cubes, signed by its inventor (close-up below).
Photo: Dominick Reuter
Unfortunately, for cubes bigger than the standard Rubik's cube  — with, say, four or five squares to a row, rather than three — adequately canvassing starting positions may well be beyond the computational capacity of all the computers in the world. But in a paper to be presented at the 19th Annual European Symposium on Algorithms in September, researchers from MIT, the University of Waterloo and Tufts University establish the mathematical relationship between the number of squares in a cube and the maximum number of moves necessary to solve it. Their method of proof also provides an efficient algorithm for solving a cube that’s in its worst-case state.

Rubik's cubes
Computer science is concerned chiefly with the question of how long algorithms take to execute, but computer scientists measure the answer to this question in terms of the number of elements the algorithm acts upon. The execution time of an algorithm that finds the largest number in a list, for instance, is proportional to the length of the list. A “dumb” algorithm for sorting the numbers in the list from smallest to largest, however, will have an execution time proportional to the square of the length of the list.

Solution with a twist

Erik Demaine, an associate professor of computer science and engineering at MIT; his father, Martin Demaine, a visiting scientist at MIT’s Computer Science and Artificial Intelligence Laboratory; graduate student Sarah Eisenstat; Anna Lubiw, who was Demaine’s PhD thesis adviser at the University of Waterloo; and Tufts graduate student Andrew Winslow showed that the maximum number of moves required to solve a Rubik's cubes with N squares per row is proportional to N2/log N. “That that’s the answer, and not N2, is a surprising thing,” Demaine says.

The standard way to solve a Rubik's cube, Demaine explains, is to find a square that’s out of position and move it into the right place while leaving the rest of the cube as little changed as possible. That approach will indeed yield a worst-case solution that’s proportional to N2. Demaine and his colleagues recognized that under some circumstances, a single sequence of twists could move multiple squares into their proper places, cutting down the total number of moves.

But finding a way to mathematically describe those circumstances, and determining how often they’d arise when a cube was in its worst-case state, was no easy task. “In the first hour, we saw that it had to be at least N2/log N,” Demaine says. “But then it was many months before we could prove that N2/log N was enough moves.”

Rubik's cubes
From left to right, Sarah Eisenstat, Martin Demaine, Erik Demaine and Andrew Winslow.
Photo: Dominick Reuter
Because their method of analysis characterizes the cases in which multiple squares can be moved into place simultaneously, it provides a way to recognize those cases, and thus an algorithm for solving a disordered cube. The algorithm  isn’t quite optimal: It always requires a few extra moves. But as the number of squares per face increases, those moves dwindle in significance.

Go configure

The Rubik's cubes is an instance of what’s called a configuration problem, the best-known example of which involves finding the most efficient way to reorganize boxes stacked in a warehouse. It’s possible, Demaine says, that the tools he and his colleagues have developed for studying the Rubik’s cube could be adapted to such problems.

But Demaine is also a vocal defender of research that doesn’t have any obvious applications. “My life has been driven by solving problems that I consider fun,” he says. “It’s always hard to tell at the moment what is going to be important. Studying prime numbers was just a recreational activity. There was no practical importance to that for hundreds of years until cryptography came along.”

But, he adds, “the aesthetic is not just to look at things that are fun but also look at problems that are simple. I think the simpler the mathematical problem, the more likely that it’s going to arise in some important practical application in the future. And the Rubik’s cube is kind of the epitome of simplicity.”

“Erik is always very interested in extending the reach of popular mathematics,” says Marc van Kreveld, an associate professor in the Department of Information and Computing Sciences at Utrecht University in the Netherlands, who designs puzzles in his spare time. “That’s really one of the things that he tries to do, to bring across that mathematics is not just some boring area of study, but it’s actually fun, and you can do a lot with it, and it’s beautiful.”

“Erik’s a very brilliant person,” van Kreveld adds. “He is already very successful in his hard-core research. But the popularizing is also very necessary, I think. You should not underestimate the importance of motivating students to learn.”

منبع:http://web.mit.edu/newsoffice/2011/rubik...-0629.html

 

 

   + ؟؟؟ ; ٢:٥٢ ‎ب.ظ ; پنجشنبه ٦ مهر ،۱۳٩۱
comment نظرات ()