بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 20

»    مسأله‌ی Encrypted SMS

»    ویدئوهای آموزشی کلاس Programming Challenges  

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی اعداد اردوش - الگوریتمستان
الگوریتمستان
315.005.00
  »  

       

بررسی مسأله‌ی اعداد اردوش (Erdos Numbers)  یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی

آنچه در این نوشته می‌خوانید:
   •  مسأله‌ی اعداد اردوش
       »  مسأله
       »  ورودی مسأله
       »  خروجی مسأله
       »  حل مسأله

مسأله

  [بازگشت به فهرست]

    پل اردوش (اردیش - Paul Erdős ) ریاضیدان مشهور و برجسته‌ی قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

    با توجه به آنکه همکاری با ایشان برای هر کس ممکن نبود، تلاش می‌کردند با نفراتی در انتشار مقاله‌ی علمی همکاری کنند که با این دانشمند بزرگ مقاله داشتند. این رویکرد باعث پدید آمدن عدد اردوش (Erdős number)  یا فاصله‌ی همکاری اردوش شد؛ یعنی برای نویسندگانی که به صورت مستقیم با ایشان همکاری داشتند عدد 1  و برای کسانی که با این نفرات مقاله داشتند عدد 2  نسبت داده شد و ارتباطات دورتر نیز به همین ترتیب با اعداد طبیعی بعدی مشخص شدند.

    امروزه هر نویسنده‌ی مقالات علمی ریاضی دوست دارد عدد اردوش خود را بداند. ماموریت شما نوشتن برنامه‌ای است که عدد اردوش نویسندگان را بر اساس پایگاه‌داده‌ی مشخص شده اعلام کند.

      

ورودی مسأله

  [بازگشت به فهرست]

در سطر اول ورودی تعداد سناریوها آمده است. سپس برای هر تست دو عدد P  و N ‌ در یک سطر آمده است که به ترتیب تعداد مقاله‌ها و تعداد نفرات مورد نظر برای محاسبه‌ی عدد اردوش هستند. در P  سطر بعدی مقالات به صورت زیر لیست شده‌اند و در N  سطر بعدی نیز اسامی نویسندگانی آمده است که باید عدد اردوش برای آنها محاسبه شود:

  

1

4 3

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices

Erdos, P., Reisig, W.: Stuttering in petri nets

Smith, M.N., Chen, X.: First oder derivates in structured programming

Jablonski, T., Hsueh, Z.: Selfstabilizing data structures

Smith, M.N.

Hsueh, Z.

Chen, X.

  

خروجی مسأله

  [بازگشت به فهرست]

به ازای هر سناریو ابتدا عبارتی به صورت Scenario i  در یک سطر مستقل چاپ شود که i  شماره‌ی سناریو است. در ادامه اسامی نویسندگان مد نظر و عدد اردوش آنها هر کدام در یک سطر چاپ شود. اسامی نویسندگان باید به همان ترتیبی باشد که در ورودی آمده است.

  

Scenario 1

Smith, M.N. 1

Hsueh, Z. infinity

Chen, X. 2

  

    منبع: وب‌سایت UVa Online Judge -  مسأله‌ی Erdos Numbers

      

حل مسأله

  [بازگشت به فهرست]

همکار بودن افراد در انتشار یک مقاله را می‌توان به صورت گرافی در نظر گرفت که به هر نویسنده یک رأس تخصیص داده شده و اگر دو نفر همکاری علمی داشته باشند، یالی بین رأس‌های متناظر آنها رسم می‌شود. به عنوان مثال، گراف متناظر ورودی نمونه‌ی مسأله به این شکل است:

      

عدد اردوش

      

    همانگونه که از شکل نیز مشخص است، ممکن است چندین مسیر ارتباطی از فرد به سمت رأس متناظر با اردوش وجود داشته باشد. در این مسأله هدف یافتن اندازه‌ی کوتاهترین مسیر (در صورت وجود) است. اگر چنین مسیری وجود نداشته باشد، عدد اردوش inifinity  خواهد بود.
در ادامه سه راهکار مختلف برای محاسبه‌ی کوتاهترین مسیر بررسی می‌شوند.

    الگوریتم فلوید-وارشال: اولین ایده برای حل هر مسأله‌ی مسیریابی استفاده از الگوریتم فلوید-وارشال است. چرا که با یک پیاده‌سازی چند خطی ساده، اندازه‌ی کوتاهترین مسیر بین هر دو رأس دلخواه و همینطور رأس‌های واسط در این مسیر را مشخص می‌کند. اما نکته‌ی اصلی آن مرتبه‌ی زمان اجرای $\theta(n^3)$  آن است که به ازای مقادیر بزرگ $n$  برای حل سوالات برنامه‌نویسی مناسب نیست. در مورد این مسأله نیز الگوریتم فلوید-وارشال کارآیی مطلوب را ندارد.

    الگوریتم دایکسترا: در محاسبه‌ی عدد اردوش هدف یافتن کوتاهترین مسیر از رأس متناظر اردوش به هر یک از رأس‌های دیگر است. بنابراین می‌توان از الگوریتم دایکسترا برای حل مسأله استفاده کرد. این الگوریتم در بدترین حالت از مرتبه‌ی زمان اجرای $O(n^2)$  است که نسبت به الگوریتم فلوید-وارشال مناسب‌تر است. اما پیاده‌سازی پیچیده‌تری نیز دارد.

    الگوریتم جستجوی اول سطح: همانطور که توضیح داده شد، یال‌های بین رأس‌ها همکاری نفرات متناظر دو رأس را نشان می‌دهند. بنابراین یال‌ها وزنی ندارند. در حل مسأله با الگوریتم‌های فلوید-وارشال یا دایکسترا نیز وزن یال‌ها 1  در نظر گرفته می‌شود. با توجه به این موضوع می‌توان کوتاهترین مسیر به هر رأس را با پیمایش اول سطح گراف با شروع از رأس متناظر اردوش محاسبه کرد. نتیجه‌ی چنین پیمایشی یک درخت است که نفرات متناظر رأس‌های آن با اردوش به صورت مستقیم یا غیرمستقیم همکاری داشته‌اند. اگر ریشه را سطح صفر در نظر بگیریم، عدد اردوش برای رأس‌های هر سطح، همان شماره‌ی سطح آنها است. همچین ممکن است برخی رأس‌های گراف در این درخت موجود نباشند که مقدار عدد اردوش برای آنها infinity  است. مرتبه‌ی زمانی اجرای این الگوریتم نیز همانند الگوریتم دایکسترا در بدترین حالت $O(n^2)$  است. اما پیاده‌سازی ساده‌تری نسبت به آن دارد.


نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        متن فارسی مسأله‌ی Encrypted SMS  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016  سایت تهران
        متن فارسی مسأله‌ی Gholam's Simple Game  از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010 ‌ منطقه‌ای سایت تهران
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels) ، از سوالات مسابقات برنامه‌نویسی بیان
        متن فارسی مسأله‌ی شماره‌ی 343  از UVa Online Judge ، ار سوالات تمرینی کتاب Art of Programming Contest
        بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History) ، از سوالات مسابقات برنامه‌نویسی بیان
        ویدئوهای آموزشی کلاس Programming Challenges  شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        عناوین بخشی از مباحث پرکاربرد در سوالات مسابقات برنامه‌نویسی
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left