866

سمينار آقاي نويد نصر اصفهاني: رويايتي ديگر از خوان ششم رستم و كاربرد گل آفتابگردان در علوم كامپيوتر، 4/10/1393

كتابخانه خانه رياضيات اصفهان

رژنگ ديو، كيكاووس و n-2 نفر از لشكريان وي را به بند انداخت. هنگامي كه رستم براي آزاد كردن ايشان به مازندران رسيد، ديو، آزادي رستم، كيكاووس و لشكريان را منوط به شرط زير كرد : هر يك از n نفر را در دخمه‌اي در بسته و بدون پنجره زنداني كند و ديو به هر ترتيبي كه خواست، تك تك ايشان را، كي يكي، به دشتي با بينهايت صندوقچه در بسته ببرد كه در هر صندوقچه سنگيست، يك روي سپيد و روي ديگر سياه. هربار، كسي كه به دشت برده شده اجازه دارد به سراغ حداكثر 10loglogn صندوقچه رفته سنگ درون آن را نگاه كرده و درصورت تمايل آن را بچرخاند و سپس به دخمه خود باز گردانده شود. او قول داده كه اگر تك تك افراد در هنگام بازگشت از دشت به دخمه خود، بتوانند تشخيص دهند كه آيا نفر nام بوده اند يا خير، همگي ايشان را آزاد كند. او همچنين به رستم اجازه داده كه تا قبل از روز شروع، هر تعدادي از صندوقچه‌ها را كه مي‌خواهد شماره گذاري كرده و در صورت تمايل سنگ درون آن‌ها را بچرخاند. فردا صبح قرار است رستم براي شماره گذاري و آماده كردن صندوقچه‌ها به دشت برود. او كه هم اكنون در كنار كاووس و باقي لشكريان است براي يافتن راهكاري براي نجات، به كمك شما نياز دارد. روشي را به آن‌ها بياموزيد كه هر يك بتوانند تشخيص دهند كه آيا نفر آخر هستند يا خير. دقت كنيد كه از فردا صبح هيچ يك از n نفر اجازه صحبت كردن با يكديگر را ندارند و همديگر را نخواهند ديد. همچنين در نظر داشته باشيد كه ديو ميت‌واند هر تعداد فردي را كه بخواهد (جداگانه) به دشت ببرد. مسئله فوق بياني از مسئله Cell Probe Model است. در اين سمينار با راه حلي براي اين مسئله در علوم كامپيوتر آشنا خواهيم شد. سپس به كمك لم گل آفتابگردان به بيان حد پاييني براي تعداد صندوقچه‌هايي كه براي حل مسئله نياز به باز كردن آنها داريم خواهيم پرداخت و در نهايت نگاهي خواهيم داشت به اثباتي براي لم گل آفتابگردان كه توسط اردوش و رادو ارائه شده است.

ل10