Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 02.06.2004, 17:13   #1
Moderator
 
acid's Avatar
 
Join Date: 09 2001
Location: South Korea, Gumi
Posts: 7,699
Downloads: 102
Uploads: 34
Blog Entries: 16
Reputation: 561 | 6
Default Pancake flipping problem

Quote:

http://bc.dieron.com/page_2004_06_02.htm#msg6496
Мне мой научный руководитель рассказал интересную историю, которую ему поведал известный проф. Пападимитриу.

Когда Пападимитриу только "выпустился" и приступил к преподавательской деятельности в Гарварде, он задал студентам задачку, которая казалась ему не особо сложной, но тем не менее сразу ему не далась. И пообещал тому, кто ее решит, поставить по своему курсу А (5 по-нашему). Задачка (ныне известная как "pancake flipping problem") такая:

Представьте, что у вас есть стопка из n блинов разного диаметра. Разрешается взять верхнюю "подстопку" из к блинов (k - любое) и перевернуть ее. Требуется за минимальное число таких переворотов отсортировать блины в стопке согласно их диаметру.

Никакой ответной реакции со стороны студентов не последовало, и только в конце семестра к Пападимитриу подошел студент, который сказал, что не знает как решить эту задачу, но у него есть кое-какие идеи. После совместного обсуждения эти идеи вылились в статью

W.H.Gates, C.H. Papadimitriou "Bounds for sorting by prefix reversals". - Discrete Mathematics, 27:47-57, 1979.

По имени вы догадались, кто был тем студентом

Кстати, через некоторое время после выхода статьи Пападимитриу позвонил профессор из другого университета и сказал, что он только что познакомился со статьей, она произвела на него сильное впечатление, и он хотел бы пригласить "этого студента" на собеседование на (не помню какую) должность. На что

Пападимитриу ему ответил, что студент избрал неправильный путь: бросил учебу и организовал компанию Microsoft...

P.S. Кстати, pancake flipping problem до сих пор является открытой проблемой

Reply With Quote
Old 02.06.2004, 20:16   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Default

Известная история по Гатеса...
Reply With Quote
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 23:15.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.