علوم کامپیوتر دانشگاه اصفهان

علوم کامپیوتر دانشگاه اصفهان
طبقه بندی موضوعی

روایتی دیگر از خوان ششم رستم و کاربرد گل آفتابگردان در علوم کامپیوتر

پنج شنبه 4 دی ماه 1393 ساعت 16:30
نوید نصر اصفهانی


بخش دانشجویی خانه ریاضیات اصفهان برگزار می‌کند:

ارژنگ دیو، کیکاووس و n-2 نفر از لشکریان وی را به بند انداخت. هنگامی که رستم برای آزاد کردن ایشان به مازندران رسید، دیو، آزادی رستم، کیکاووس و لشکریان را منوط به شرط زیر کرد:

هر یک از n نفر را در دخمه‌ای در بسته و بدون پنجره زندانی کند و دیو به هر ترتیبی که خواست، تک تک ایشان را، یکی یکی، به دشتی با بینهایت صندوقچه در بسته ببرد که در هر صندوقچه سنگیست، یک روی سپید و روی دیگر سیاه. هربار، کسی که به دشت برده شده اجازه دارد به سراغ حداکثر 10loglogn صندوقچه رفته سنگ درون آن را نگاه کرده و درصورت تمایل آن را بچرخاند و سپس به دخمه خود باز گردانده شود. او قول داده که اگر تک تک افراد در هنگام بازگشت از دشت به دخمه خود، بتوانند تشخیص دهند که آیا نفر nام بوده اند یا خیر، همگی ایشان را آزاد کند. او همچنین به رستم اجازه داده که تا قبل از روز شروع، هر تعدادی از صندوقچه‌ها را که می‌خواهد شماره گذاری کرده و در صورت تمایل سنگ درون آن‌ها را بچرخاند.


فردا صبح قرار است رستم برای شماره گذاری و آماده کردن صندوقچه‌ها به دشت برود. او که هم اکنون در کنار کاووس و باقی لشکریان است برای یافتن راهکاری برای نجات، به کمک شما نیاز دارد. روشی را به آن‌ها بیاموزید که هر یک بتوانند تشخیص دهند که آیا نفر آخر هستند یا خیر.


دقت کنید که از فردا صبح هیچ یک از n نفر اجازه صحبت کردن با یکدیگر را ندارند و همدیگر را نخواهند دید. همچنین در نظر داشته باشید که دیو میت‌واند هر تعداد فردی را که بخواهد (جداگانه) به دشت ببرد.


مسئله فوق بیانی از مسئله Cell Probe Model است. در این سمینار با راه حلی برای این مسئله در علوم کامپیوتر آشنا خواهیم شد. سپس به کمک لم گل آفتابگردان به بیان حد پایینی برای تعداد صندوقچه‌هایی که برای حل مسئله نیاز به باز کردن آنها داریم خواهیم پرداخت. و در نهایت نگاهی خواهیم داشت به اثباتی برای لم گل آفتابگردان که توسط اردوش و رادو ارائه شده است.


خانه ریاضیات اصفهان

موافقین ۰ مخالفین ۰ ۹۳/۰۹/۲۸
سعید جزی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی