متن كامل خبر
یک گام بزرگ در نظریهٔ گراف

تاريخ خبر : 6/10/1394امتياز بده :ارسال به دوستتعدادمشاهده : 484

لازلو بابایی توانست الگوریتمی برای یکریختی گراف‌ها ارائه دهد که مدت زمان اجرای آن دست‌یافتنی است.

لازلو بابایی (László Babai) دانشمند علوم کامپیوتر در 10 نوامبر در سمینار علوم کامپیوتر نظری در دانشگاه شیکاگو اعلام کرد که به الگوریتم جدیدی دست یافته است که می‌تواند مسئلهٔ بزرگی را برای ما حل کند. مسئله این است : چه چیزهایی باید تعیین شوند تا دو مجموعه جداگانه که نقاط داخلی مشترکی با هم دیگر دارند، و به عنوان گراف شناخته می‌شوند، و اعضای مجموعه شان از راه‌های مختلفی به هم وصل می‌شوند و یک گراف بسیار پیچیده می‌سازند. را حل سازیم.
در عمل، الگوریتم‌های موجود، می‌توانند این کار را در یک زمان معقول انجام دهند، اما در مورد گراف‌های بسیار پیچیده، موضوع به این راحتی‌ها نیست و ممکن است مدت زمان حل یک حالت از عمر جهان بیشتر طول بکشد!
لازلو بابایی، الگوریتمی ارائه کرده‌است که این مسئله را که به مسئلهٔ یک‌ریختی گراف (graph isomorphism problem) مشهور است، حل نماید و البته مدت زمان انجام آن شبه‌چندجمله‌ای () است، بدین معنا که برای اثبات یکریخت بودن دو گراف مدت زمان انجام آن می‌تواند در زمانی معقول انجام پذیرد.
کشف بابایی، یک جهش بزرگ در درک ما از مسئله است. و این کشف توانایی این را دارد که بزرگترین کشف در زمینه‌ی تئوری کامپیوتر در دهه‌ی فعلی باشد.
اطلاعات بیشتر در مورد کشف لازلو بابایی  را در لینک‌های زیر بخوانید:
http://people.cs.uchicago.edu/~laci/quasipoly.html
https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem


 


     منبع خبر : شبكه رشد

بازگشت